thread synchronization - delicate issue

Question

let's i have this loop :

static a;
for (static int i=0; i<10; i++)
{
   a++;
   ///// point A
}

to this loop 2 threads enters...

i'm not sure about something.... what will happen in case thread1 gets into POINT A , stay there, while THREAD2 gets into the loop 10 times, but after the 10'th loop after incrementing i's value to 10, before checking i's value if it's less then 10, Thread1 is getting out of the loop and suppose to increment i and get into the loop again. what's the value that Thread1 will increment (which i will he see) ? will it be 10 or 0 ?

is it posibble that Thread1 will increment i to 1, and then thread 2 will get to the loop again for 9 times (and them maybe 8 ,7 , etc...)

thanks

Answer 1

It's not really a delicate issue because you would never allow this in real code if the synchronization was going to be an issue.

Answer 2

If i is shared between multiple threads, all bets are off. It's possible for any thread to increment i at essentially any point during another thread's execution (including halfway through that thread's increment operation). There is no meaningful way to reason about the contents of i in the above code. Don't do that. Either give each thread its own copy of i, or make the increment and comparison with 10 a single atomic operation.

Answer 3

I'm just going to use i++ in your loop:

for (static int i=0; i<10; i++)
{
}

Because it mimics a. (Note, static here is very strange)

Consider if Thread A is suspended just as it reaches i++. Thread B gets i all the way to 9, goes into i++ and makes it 10. If it got to move on, the loop would exist. Ah, but now Thread A is resumed! So it continues where it left off: increment i! So i becomes 11, and your loop is borked.

Any time threads share data, it needs to be protected. You could also make i++ and i < 10 happen atomically (never be interrupted), if your platform supports it.

Answer 4

You should use mutual exclusion to solve this problem.

Answer 5

Yes, it's possible that either thread can do the majority of the work in that loop. But as Dynite explained, this would (and should) never show up in real code. If synchronization is an issue, you should provide mutual exclusion (a Boost, pthread, or Windows Thread) mutex to prevent race conditions such as this.

Answer 6

And that is why, on multi-threaded environment, we are suppose to use locks.

In your case, you should write:

bool test_increment(int& i)
{
  lock()
  ++i;
  bool result = i < 10;
  unlock();
  return result;
}

static a;
for(static int i = -1 ; test_increment(i) ; )
{
   ++a;
   // Point A
}

Now the problem disappears .. Note that lock() and unlock() are supposed to lock and unlock a mutex common to all threads trying to access i!

Answer 7

You have to realize that an increment operation is effectively really:

read the value
add 1
write the value back

You have to ask yourself, what happens if two of these happen in two independent threads at the same time:

static int a = 0;

thread 1 reads a (0)
adds 1 (value is 1)
thread 2 reads a (0)
adds 1 (value is 1)
thread 1 writes (1)
thread 2 writes (1)

For two simultaneous increments, you can see that it is possible that one of them gets lost because both threads read the pre-incremented value.

The example you gave is complicated by the static loop index, which I didn't notice at first. Since this is c++ code, standard implementation is that the static variables are visible to all threads, thus there is only one loop counting variable for all threads. The sane thing to do would be to use a normal auto variable, because each thread would have its own, no locking required.

That means that while you will lose increments sometimes, you also may gain them because the loop itself may lose count and iterate extra times. All in all, a great example of what not to do.

Answer 8

Why would you use a static loop counter?

This smells like homework, and a bad one at that.

Answer 9

Both the threads have their own copy of i, so the behavior can be anything at all. That's part of why it's such a problem.

When you use a mutex or critical section the threads will generally sync up, but even that is not absolutely guaranteed if the variable is not volatile.

And someone will no doubt point out "volatile has no use in multithreading!" but people say lots of stupid things. You don't have to have volatile but it is helpful for some things.

Answer 10

If your "int" is not the atomic machine word size (think 64 bit address + data emulating a 32-bit VM) you will "word-tear". In that case your "int" is 32 bits, but the machine addresses 64 atomically. Now you have to read all 64, increment half, and write them all back.

This is a much larger issue; bone up on processor instruction sets, and grep gcc for how it implements "volatile" everywhere if you really want the gory details.

Add "volatile" and see how the machine code changes. If you aren't looking down at the chip registers, please just use boost libraries and be done with it.