25

I have two threads running. They share an array. One of the threads adds new elements to the array (and removes them) and the other uses this array (read operations only). Is it necessary for me to lock the array before I add/remove to/from it or read from it?

Further details:

  • I will need to keep iterating over the entire array in the other thread. No write operations over there as previously mentioned. "Just scanning something like a fixed-size circular buffer"
  • The easy thing to do in such cases is to use a lock. However locks can be very slow. I did not want to use locks if their use can be avoided. Also, as it came out from the discussions, it might not be necessary (it actually isn't) to lock all operations on the array. Just locking the management of an iterator for the array (count variable that will be used by the other thread) is enough

I don't think the question is "too broad". If it still comes out to be so, please let me know. I know the question isn't perfect. I had to combine at least 3 answers in order to be able to solve the question - which suggests most people were not able to fully understand all the issues and were forced to do some guess work. But most of it came out through the comments which I have tried to incorporate in the question. The answers helped me solve my problem quite objectively and I think the answers provided here are quite a helpful resource for someone starting out with multithreading.

24
  • 1
    Are we talking about raw C arrays? And are we talking about removing the last item or at arbitrary positions?
    – leemes
    Jul 10, 2014 at 17:12
  • 2
    The point I'm asking is: when during every point of time while the change is taking place, the array will be consistent, then it is not going to be a problem. But if you insert in the middle, you first move entries, leaving in an inconsistent state, and then insert the item. I hope this sheds some light on the problem.
    – leemes
    Jul 10, 2014 at 17:15
  • 1
    Regarding iteration: it is important to not cache the size or an end iterator in the reading thread. I.e. don't use range-for. Also, the writing thread should update the size such that there is no inconsistent point in time. When inserting, first insert and then increase size. When removing, first decrease size then remove.
    – leemes
    Jul 10, 2014 at 17:16
  • 4
    @leemes Good point, and one needs some sort of synchronization (a lock should do the trick; there may be a lockless alternative) to avoid this critical sequence being reordered by compiler or CPU. Edit: Coming to think of it, even that still permits the ordering (T1) read size, determine that index is in range; (T2) decrease size; (T2) invalidate the last element of the array. (T1) read last element based on index. Advise to OP: Just use a lock, none of us is smart enough to make the lockless thing work.
    – user395760
    Jul 10, 2014 at 17:21
  • 1
    @leemes C++ volatile (in contrast with Java volatile) has nothing to do with concurrency. It usually prevents some optimizations that can cause trouble for careless multithreading (e.g. eliding duplicate reads) but doesn't prevent movements w.r.t. other writes (such as the writes to the array), and doesn't affect the CPU's instruction reordering. An atomic or a memory barrier may help.
    – user395760
    Jul 10, 2014 at 17:33

10 Answers 10

19

If two threads perform an operation on the same memory location, and at least one operation is a write operation, you have a so-called data race. According to C11 and C++11, the behaviour of programs with data races is undefined.

So, you have to use some kind of synchronization mechanism, for example:

6
  • 7
    (just to clarify for others:) Also note that this doesn't just apply to operations occurring at the same time. It also applies to operations that are sequential (thread 1 writes, then some time later thread 2 reads). Even if the operations are sequential, some kind of synchronization mechanism is required (especially to make sure CPU caches etc. are synchronized).
    – Cornstalks
    Jul 10, 2014 at 20:34
  • 4
    @Cornstalks: in fact there are two important additions to make: 1) at least one of the operations is not atomic; 2) there's no happens-before relation between the operations.
    – peppe
    Jul 10, 2014 at 22:51
  • @nosid You are right. Synchronization is a must. Would you think the problem can be solved if a counter variable (that refers to the size of the array) is made atomic and this variable is used by the other thread to keep track of the size of the array by the other thread. Would there be a possibility of a data race now ?
    – Chani
    Jul 11, 2014 at 3:57
  • @Wildling NO! If you remove items from the array you have a problem. T1 reads counter=10 and wants to read element 10, but before he can read element 10 T2 becomes active. T2 sets counter=9 and deletes last element. Now T1 becomes active again and tries to read element 10 whichwas deleted... You would have to make the whole access to counter and array atomic - and this is essentially what a mutex does ;-)
    – Falco
    Jul 11, 2014 at 10:46
  • @Falco As I have mentioned in the question, I am dealing with a special case where only T1 does all the updates. T2 just reads. I simply wanted to explore ways of staying minimalistic, fast and still completely error free. hence the question.
    – Chani
    Jul 11, 2014 at 15:03
8

If you are writing and reading from the same location from multiple threads you will need to to perform locking or use atomics. We can see this by looking at the C11 draft standard(The C++11 standard looks almost identical, the equivalent section would be 1.10) says the following in section 5.1.2.4 Multi-threaded executions and data races:

Two expression evaluations conflict if one of them modifies a memory location and the other one reads or modifies the same memory location.

and:

The execution of a program contains a data race if it contains two conflicting actions in different threads, at least one of which is not atomic, and neither happens before the other. Any such data race results in undefined behavior.

and:

Compiler transformations that introduce assignments to a potentially shared memory location that would not be modified by the abstract machine are generally precluded by this standard, since such an assignment might overwrite another assignment by a different thread in cases in which an abstract machine execution would not have encountered a data race. This includes implementations of data member assignment that overwrite adjacent members in separate memory locations. We also generally preclude reordering of atomic loads in cases in which the atomics in question may alias, since this may violate the "visible sequence" rules.

If you were just adding data to the array then in the C++ world a std::atomic index would be sufficient since you can add more elements and then atomically increment the index. But since you want to grow and shrink the array then you will need to use a mutex, in the C++ world std::lock_guard would be a typical choice.

5

To answer your question: maybe.

Simply put, the way that the question is framed doesn't provide enough information about whether or not a lock is required.

In most standard use cases, the answer would be yes. And most of the answers here are covering that case pretty well.

I'll cover the other case.

When would you not need a lock given the information you have provided?

There are some other questions here that would help better define whether you need a lock, whether you can use a lock-free synchronization method, or whether or not you can get away with no explicit synchronization.

Will writing data ever be non-atomic? Meaning, will writing data ever result in "torn data"? If your data is a single 32 bit value on an x86 system, and your data is aligned, then you would have a case where writing your data is already atomic. It's safe to assume that if your data is of any size larger than the size of a pointer (4 bytes on x86, 8 on x64), then your writes cannot be atomic without a lock.

Will the size of your array ever change in a way that requires reallocation? If your reader is walking through your data, will the data suddenly be "gone" (memory has been "delete"d)? Unless your reader takes this into account (unlikely), you'll need a lock if reallocation is possible.

When you write data to your array, is it ok if the reader "sees" old data?

If your data can be written atomically, your array won't suddenly not be there, and it's ok for the reader to see old data... then you won't need a lock. Even with those conditions being met, it would be appropriate to use the built in atomic functions for reading and storing. But, that's a case where you wouldn't need a lock :)

Probably safest to use a lock since you were unsure enough to ask this question. But, if you want to play around with the edge case of where you don't need a lock... there you go :)

1
  • 1
    After edits coming through, it sounds like the real question being asked here should be along the lines of "what is the best performing way to synchronize my data?" And that would lead to some very different answers than what's coming through here. I suggest asking a new question along the lines of performance. Jul 11, 2014 at 4:28
4

One of the threads adds new elements to the array [...] and the other [reads] this array

In order to add and remove elements to/from an array, you will need an index that specifies the last place of the array where the valid data is stored. Such index is necessary, because arrays cannot be resized without potential reallocation (which is a different story altogether). You may also need a second index to mark the initial location from which the reading is allowed.

If you have an index or two like this, and assuming that you never re-allocate the array, it is not necessary to lock when you write to the array itself, as long as you lock the writes of valid indexes.

int lastValid = 0;
int shared[MAX];
...
int count = toAddCount;
// Add the new data
for (int i = lastValid ; count != 0 ; count--, i++) {
    shared[i] = new_data(...);
}
// Lock a mutex before modifying lastValid
// You need to use the same mutex to protect the read of lastValid variable
lock_mutex(lastValid_mutex);
lastValid += toAddCount;
unlock_mutex(lastValid_mutex);

The reason this works is that when you perform writes to shared[] outside the locked region, the reader does not "look" past the lastValid index. Once the writing is complete, you lock the mutex, which normally causes a flush of the CPU cache, so the writes to shared[] would be complete before the reader is allowed to see the data.

2
  • 1
    This look very wrong to me. A mutex creates a critical section not making writes atomic. Either you need to protect the reads of lastvalue with the same mutex or remove the mutex and use atomic
    – adrianm
    Jul 10, 2014 at 22:16
  • @adrianm Oops, I did not realize that I have not mentioned explicitly the need to protect the read of lastValid variable with the same mutex. This is now fixed, thanks! Jul 10, 2014 at 22:27
3

Lock? No. But you do need some synchronization mechanism.

What you're describing sounds an awful like a "SPSC" (Single Producer Single Consumer) queue, of which there are tons of lockfree implementations out there including one in the Boost.Lockfree

The general way these work is that underneath the covers you have a circular buffer containing your objects and an index. The writer knows the last index it wrote to, and if it needs to write new data it (1) writes to the next slot, (2) updates the index by setting the index to the previous slot + 1, and then (3) signals the reader. The reader then reads until it hits an index that doesn't contain the index it expects and waits for the next signal. Deletes are implicit since new items in the buffer overwrite previous ones.

You need a way to atomically update the index, which is provided by atomic<> and has direct hardware support. You need a way for a writer to signal the reader. You also might need memory fences depending on the platform s.t. (1-3) occur in order. You don't need anything as heavy as a lock.

1
  • 1
    For a circular queue, the "stuff" pointer is only written by the writer, and the "fetch" pointer is only written by the reader. If the reader can invalidate queue entries before indicating that it has read them, then no special primitives would be required for correctness if any data written in one thread would eventually be seen in the other [if data written in one thread takes awhile to appear in the other, that may adversely affect throughput but not correctness].
    – supercat
    Jul 10, 2014 at 21:21
2

"Classical" POSIX would indeed need a lock for such a situation, but this is overkill. You just have to ensure that the reads and writes are atomic. C and C++ have that in the language since their 2011 versions of their standards. Compilers start to implement it, at least the latest versions of Clang and GCC have it.

2
  • Hey can you please add some references where I can read up more on this feature.
    – Chani
    Jul 10, 2014 at 17:25
  • @Wildling It's std::atomic he is talking about.
    – leemes
    Jul 10, 2014 at 17:31
1

It depends. One situation where it could be bad is if you are removing an item in one thread then reading the last item by its index in your read thread. That read thread would throw an OOB error.

1

As far as I know, this is exactly the usecase for a lock. Two threads which access one array concurrently must ensure that one thread is ready with its work. Thread B might read unfinished data if thread A did not finish work.

0

If it's a fixed-size array, and you don't need to communicate anything extra like indices written/updated, then you can avoid mutual exclusion with the caveat that the reader may see:

  • no updates at all
    • If your memory ordering is relaxed enough that this happens, you need a store fence in the writer and a load fence in the consumer to fix it
  • partial writes
    • if the stored type is not atomic on your platform (int generally should be)
    • or your values are un-aligned, and especially if they may span cache lines

This is all dependent on your platform though - hardware, OS and compiler can all affect it. You haven't told us what they are.

The portable C++11 solution is to use an array of atomic<int>. You still need to decide what memory ordering constraints you require, and what that means for correctness and performance on your platform.

2
  • 5
    -1 Without proper synchronization, the reader may never see the written values. Jul 10, 2014 at 17:17
  • True, but it's highly platform-dependent.
    – Useless
    Jul 10, 2014 at 17:33
0

If you use e.g. vector for your array (so that it can dynamically grow), then reallocation may occur during the writes, you lose.

If you use data entries larger than is always written and read atomically (virtually any complex data type), you lose.

If the compiler / optimizer decides to keep certain things in registers (such as the counter holding the number of valid entries in the array) during some operations, you lose.

Or even if the compiler / optimizer decides to switch order of execution for your array element assignments and counter increments/decrements, you lose.

So you certianly do need some sort of synchronization. What is the best way to do so (for example it may be worth while to lock only parts of the array), depends on your specifics (how often and in what pattern do the threads access the array).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.