6

Suppose I have two threads A and B that are both incrementing a ~global~ variable "count". Each thread runs a for loop like this one:

for(int i=0; i<1000; i++)
    count++; //alternatively, count = count + 1;

i.e. each thread increments count 1000 times, and let's say count starts at 0. Can there be sync issues in this case? Or will count correctly equal 2000 when the execution is finished? I guess since the statement "count = count + 1" may break down into TWO assembly instructions, there is potential for the other thread to be swapped in between these two instructions? Not sure. What do you think?

mindthief
  • 12,755
  • 14
  • 57
  • 61

4 Answers4

11

Yes there can be sync issues in this case. You need to either protect the count variable with a mutex, or use a (usually platform specific) atomic operation.

Example using pthread mutexes

static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

for(int i=0; i<1000; i++) {
    pthread_mutex_lock(&mutex);
    count++;
    pthread_mutex_unlock(&mutex);
}

Using atomic ops

There is a prior discussion of platform specific atomic ops here: UNIX Portable Atomic Operations

If you only need to support GCC, this approach is straightforward. If you're supporting other compilers, you'll probably have to make some per-platform decisions.

Community
  • 1
  • 1
blucz
  • 1,606
  • 10
  • 13
5

Yes, there can be sync problems.

As an example of the possible issues, there is no guarantee that an increment itself is an atomic operation.

In other words, if one thread reads the value for increment then gets swapped out, the other thread could come in and change it, then the first thread will write back the wrong value:

+-----+
|   0 | Value stored in memory (0).
+-----+
|   0 | Thread 1 reads value into register (r1 = 0).
+-----+
|   0 | Thread 2 reads value into register (r2 = 0).
+-----+
|   1 | Thread 2 increments r2 and writes back.
+-----+
|   1 | Thread 1 increments r1 and writes back.
+-----+

So you can see that, even though both threads have tried to increment the value, it's only increased by one.

This is just one of the possible problems. It may also be that the write itself is not atomic and one thread may update only part of the value before being swapped out.

If you have atomic operations that are guaranteed to work in your implementation, you can use them. Otherwise, use mutexes, That's what pthreads provides for synchronisation (and guarantees will work) so is the safest approach.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • The issue you've exemplified barely makes sense on modern CPUs. Typically the problem is not in atomically updating multiple bytes since machines generally update a word at a time atomically. Furthermore, all you'd need to be safe from your example is a volatile keyword. The problem that you usually see in practice is much simpler: two threads read the same value, each increment it independently in a register, then write back the same value. – blucz Sep 09 '10 at 01:52
  • 2
    @blucz, I've provided a simpler situation (in progress while you were typing your comment by the looks of it) but you're dead wrong. POSIX threads do _not_ make assumptions about the hardware they're running on and whether its writes are atomic or not. If you're going to follow a standard, you should follow it. If you want to introduce further assumptions, that's okay, just be aware of the ramifications and don't pretend to be following the standard :-) – paxdiablo Sep 09 '10 at 01:57
  • I think you misunderstood my comment. I didn't say anything about the pthread standard. I just suggested that in practice, the example you were giving was very unlikely, which it was, for the reason I gave. Is it possible to have that error? Sure..on a system that 99.999% of us will never see. – blucz Sep 09 '10 at 05:55
  • Yes, unfortunately I _work_ on such a beast every day and yet it's almost certainly responsible for tracking every cent that enters or exits your bank account :-) The System z mainframe is very adept at discovering code that makes unwarranted assumptions, things like those people assuming that the characters `A` thru `Z` are contiguous. The fact that 99.999% of the population will never see it doesn't mean it will only affect 0.001% if something goes wrong. – paxdiablo Sep 09 '10 at 06:19
  • But, be that as it may, it's irrelevant since I've replaced that possibility with a much more likely one. That doesn't diminish the seriousness of the earlier problem. As I stated, channelling Yoda: "No. Try not! Do. Or do not!" - either follow the standard or don't Most of the time, you're right in that it may not matter but I'd prefer to be safe. Others may have different priorities. – paxdiablo Sep 09 '10 at 06:21
  • I don't like this kind of answer. The answer essentially says, "you can't do this because I can think of a way it can break". But you can't do things like this even if nobody can think of a way they can break. They're wrong because the pthreads standard explicitly says so, not because we can think of ways they can do the wrong thing. And that invites an argument about how plausible the one particular way of breaking you can imagine is, which is totally irrelevant to the fact that the relevant standards say this code is UB. – David Schwartz Feb 24 '19 at 18:55
  • David, the OP asked if there could be sync problems, I stated that there could, and provided one example, also stating that there may well be others. I'm not sure what else you would want but it appears that you would rather an answer just stating that there could be problems, with NO examples. I'd rather provide the extra info. – paxdiablo Feb 24 '19 at 21:55
  • @paxdiablo There's no harm in presenting it as "extra info". There's harm in presenting it as the reason the code is not safe. That you can think of a way it can fail has nothing to do with whether or not the code is safe. The code is safe if the relevant standards say so even if you can think of a way it can fail. And the code is not safe if the relevant standards say so even if you can't think of a way it can fail. – David Schwartz Feb 25 '19 at 16:56
  • @David, I presented it as *an* example, not *the* reason. In any case , I've edited the answer to more emphasize it's an example of the *possible* problems and to use the features provided by pthreads itself. Hopefully that's better. – paxdiablo Feb 25 '19 at 21:18
5

Count clearly needs to be protected with a mutex or other synchronization mechanism.

At a fundamental level, the count++ statment breaks down to:

load count into register
increment register
store count from register

A context switch could occur before/after any of those steps, leading to situations like:

Thread 1:  load count into register A (value = 0)
Thread 2:  load count into register B (value = 0)
Thread 1:  increment register A (value = 1)
Thread 1:  store count from register A (value = 1)
Thread 2:  increment register B (value = 1)
Thread 2:  store count from register B (value = 1)

As you can see, both threads completed one iteration of the loop, but the net result is that count was only incremented once.

You probably would also want to make count volatile to force loads & stores to go to memory, since a good optimizer would likely keep count in a register unless otherwise told.

Also, I would suggest that if this is all the work that's going to be done in your threads, performance will dramatically drop from all the mutex locking/unlocking required to keep it consistent. Threads should have much bigger work units to perform.

Drew Hall
  • 28,429
  • 12
  • 61
  • 81
  • 1
    Volatile does not force loads and stores to go to memory, not in the way implied here. Volatile lets the compiler know that for the variable in question, its value can change without the knowledge of the compiler, e.g. say a real-time clock. This means that the compiler will not rely on register copies of that value. It does not however prevent the CPU from, say, deferring the write of that cache line to memory for as long as it possibly can (which is what it will do, since memory writes destroy performance). –  Jan 18 '11 at 21:58
  • 1
    There is really nothing right about this answer. For one thing, there's absolutely no universal guarantee for all platforms that `count++` breaks down into three operations. It might happen to on some platform or it might not. The answer goes downhill from there, IMO. – David Schwartz Feb 22 '19 at 00:08
  • @DavidSchwartz: Ok, I’ll bite. Would you suggest that no synchronization is needed here? – Drew Hall Feb 23 '19 at 20:25
  • Synchronization is needed here because the pthreads standard does not define what happens when one thread accesses an object while another thread is, or might be, modifying it. So unless this is platform-specific code and your platform has some special rules, you have no way to know what's going to happen. It could even crash. – David Schwartz Feb 24 '19 at 18:53
  • @DavidSchwartz I don’t disagree...my example was only intended to show one way that things could go wrong, as a means of motivating my response that synchronization was needed. – Drew Hall Feb 25 '19 at 03:22
  • But synchronization would be needed even if nobody could show any way that things could go wrong. And this is not because you think you can break down the statement, it would be true even if you couldn't. Synchronization is needed here because otherwise the behavior of the code is undefined. – David Schwartz Feb 25 '19 at 16:53
  • @DavidSchwartz: I just read your answer...I think you're right to suggest the OP think at a higher level. However, I don't think there's any harm in understanding how things might go wrong, either. Peace. – Drew Hall Feb 25 '19 at 17:14
  • Except I can probably produce links to dozens of questions and answers that went off the rails due to that type of thinking. There are people who argue that you need to use `volatile` even with mutexes because they can think of ways it might go wrong. And there are people who do things that break because they couldn't think of any way it could go wrong and then the implementation found one they couldn't think of. I honestly believe it is actively harmful to encourage people to reason that way, especially people whose understanding of synchronization is shaky. – David Schwartz Feb 25 '19 at 17:18
2

I guess since the statement "count = count + 1" may break down into TWO assembly instructions, there is potential for the other thread to be swapped in between these two instructions? Not sure. What do you think?

Don't think like this. You're writing C code and pthreads code. You don't have to ever think about assembly code to know how your code will behave.

The pthreads standard does not define the behavior when one thread accesses an object while another thread is, or might be, modifying it. So unless you're writing platform-specific code, you should assume this code can do anything -- even crash.

The obvious pthreads fix is to use mutexes. If your platform has atomic operations, you can use those.

I strongly urge you not to delve into detailed discussions about how it might fail or what the assembly code might look like. Regardless of what you might or might not think compilers or CPUs might do, the behavior of the code is undefined. And it's too easy to convince yourself you've covered every way you can think of that it might fail and then you miss one and it fails.

David Schwartz
  • 179,497
  • 17
  • 214
  • 278