thread synchronization - delicate issue

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 time开发者_Python百科s, 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

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.

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.

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.

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.

You should use mutual exclusion to solve this problem.

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!

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.

Why would you use a static loop counter?

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

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.

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.

If you need to increment a value with multiple threads at the same time, then Look up "atomic operations". For linux, look up "gcc atomic operations". There is hardware support on most platforms to atomicly increment, add, compare and swap, and more. LOCKING WOULD BE OVERKILL for this....atomic inc is magnitudes faster than lock inc unlock. If you have to change a lot of fields at the same time you may need a lock, although you can change 128 bits worth of fields at a time with most atomic ops.

volatile is not the same as an atomic operation. Volatile helps the compiler know when its a bad idea to use a copy of a variable. Among its uses, volatile is important when you have multiple threads changing data that you would like to read the "most up to date version of" of without locking. Volatile will still not fix your a++ problem as two threads can read the value of "a" at the same time and then both increment the same "a" and then the last one to write "a" wins and you lost an inc. Volatile will slow down optimized code by not letting the compiler hold values in registers and what not.