Hi guys,
Yesterday I was playing with threads and using a global variable to determine if a thread had finished or not.
Pseudo code
// thread
loop until finished
set 'done' to true when finished
// main loop
loop until 'done' is true
I found that the program would stall in the main loop and never terminate.
I also found by locking 'done' in both the thread and main loop resolved the issue.
Is this an example of a deadlock?
result = 0
done = false
Worker:
result = 42; // do some work
done = true; // publish our results to main thread
Main:
Launch Worker
while(!done) {;} // busy wait
print( result );mutex
result = 0
done = false
Worker:
lock(mutex)
{
result = 42;
done = true;
}
Main:
Launch Worker
while(1)
{
lock(mutex)
{
if done then break;
}
}
print( result );result = 0
done = false
Worker:
result.AtomicWrite(42, sequential_consistency)
done.AtomicWrite(true, sequential_consistency)
Main:
Launch Worker
while(!done.AtomicRead(sequential_consistency)) {;} // busy wait
print( result.AtomicRead(sequential_consistency) )Nice! Thanks Hodgman for clearing this up for me.
In my case I started locking the variable in the end, as it was the only way that would work 'consistently'. Your explanation explains why.
Exactly as Sean said, I will try to recapital it more shortly.
If a single CPU core (or CP unit) does a write operation, and ends by that moment, there is no reason for moving the writen operation out from closest cache up the laddder to the RAM, and if another CPU core reads a value, there is no need to read it up the ladder from RAM if it is being hit in the cache (L1,L2 whatever). A lock keyword for example ensures that- reading this variable entity is assured done from RAM (or L3 shared), and ending a lock says that, this variable entity is written to RAM (or L3 shared at least).
(Remember lock keyword carries () operator in which you specify the criticaly obseved variable entity. The inside of block has nothing to do with specific of other safe variable, only the operations done to do the achievement)
Simply, a single assignment operation does not happen on a level visible to RAM or other cores. That what may get you confused as - I did this =, why my thread reading this is not this :)
That's a primitive (with a reader-writer) which means updating it is atomic which means it's not a locking problem.
He didn't use 'volatile' so the check got optimized out.
Adding locking will probably fix the issue but it's not guaranteed! and it's overkill for such a simple case.
volatile int g_done;
volatile int g_done;
That is not what volatile means in C or C++. Some compilers through history adopted volatile for threading and for their own other purposes, but it is not portable and not standard. Java and C# adopted that meaning, but this thread is marked as C++. That improper usage introduces unnecessary costs and performance penalties and still may not solve the problem.
The correct solution is std::atomic, as described by Hodgman and others above. The atomic templates are fully specialized to use low-overhead functionality (such as interlocked values) to get great performance while still enforcing thread safety.
To add to the above, adding volatile probably will "fix" it, but even if it does, it would still be theoretically undefined code that's just happening to work in practice, and could break in any future build...
Adding volatile will tell the compiler not to optimize (A) into (B):
(A) while( !done ) { doStuff }
(B) bool local = done; while( !local ) { doStuff } // uh oh, infinite loop!So volatile will "fix" that one problem.
But volatile has nothing to do with multi-threading, so it does nothing for the memory ordering issues. I gave the example above of:
result = 42; // do some work
done = true; // publish our results to main threadEven if you're using volatile, it's possible for the other thread to see the "done = true" write appear in memory first, and the "result = 42" write appear in memory second... which means that other thread might try to print result before it's been written, which is a race condition.
