Example 3: Don't Try to Turn Critical Sections Inside Out
Although every entry/exit of a critical section implies a use of locks or atomics, not every use of locks or atomics correctly expresses a critical section. Consider this evil, smelly code of questionable descent, where x is initially zero (Note: this example is drawn from [3]):
// Thread 1 x = 1; // a mut.lock(); // b ... etc. ... mut.unlock(); // Thread 2: wait for Thread 1 to take the lock, then use x while( mut.trylock() ) // try to take the lock... mut.unlock(); // ... if we succeeded, unlock and loop r2 = x; // not guaranteed to see the value 1!
This programmer is certainly nobody we would know or associate with. But what is he doing? He is trying to abuse the fact that locking is a global operation, and is visible in principle to all threads.
Specifically, a thread can use a trylock-like facility to find out whether some other thread currently holds the lock, by trying to acquire the lock and seeing if that attempt succeeded or failed. Pretty much every threading library has a way to determine if someone else has entered a locked critical section: In Java, you can use Lock.tryLock; on Windows and .NET, there's Monitor.TryEnter or WaitOne with a timeout; in proposed C++0x, try_lock or timed_lock; and in pthreads, pthread_mutex_trylock and pthread_mutex_timedlock.
Thread 2, which we might now refer to as Machiavelli, doesn't really want the lock. Machiavelli only wants to try to eavesdrop on Thread 1 in the next room, listening with a trylock glass against the wall until he hears the telltale sound that means Thread 1 got to line b, and therefore presumably has already set x.
The most obvious red flag in this code is that the read and write of x are outside critical sections; that is, while we don't hold a lock on mut. That technique only works when there's enough synchronization to hand off an object from one thread to another (it belongs to one thread before the synchronization, and another thread after the synchronization), and there isn't enough synchronization here to do that. Let's see why.
The problem is that this anti-idiom is trying to abusively invert the usual meanings of a locked section. Thread 2 is abusively trying to use Thread 1's entering a critical section as a release event, which it isn't. Remember, entering a critical section is an acquire event, and leaving a critical section is a release event. On this, the whole world depends, as we saw last month [1]. In particular, compiler and processor optimizations are guaranteed to respect normal critical section boundaries, and therefore not change the semantics of correctly synchronized code; specifically, they respect the rule that code can be reordered to move into, but not out of, a critical section. In the context of Thread 1, that means an optimizer or processor is free to actually execute line a after line b... and therefore, Thread 2 could well see a value of 0 for x, despite its attempts to abuse the global visibility of locking.
In reality, the code may happen to work all the time on a given system that doesn't happen to reorder lines a and b. The original programmer might be long gone by the time some other poor sod tries to port it to a new compiler or platform that does manifest the race, and gets to experience the joy of debugging the intermittent problem over a holiday weekend. (Note that, besides the issues we've discussed, this code has other potential problems; for example, Thread 2 can wait forever if Thread 1's lock is taken too early.)
Treat a critical section as you would treat another person: Turning either inside out is at least cruel, and usually illegal. For all the sensational, lurid, and unsavory details, see [3].
Summary
Apply critical sections consistently to protect shared objects: Enter a critical section by taking a lock or reading from an ordered atomic variable; and exit a critical section by releasing a lock or writing to an ordered atomic variable. Never pervert these meanings; in particular, don't abuse trylock to (try to) make a lock acquire in another thread act like the end of a critical section.
Notes
[1] H. Sutter. "Use Critical Sections (Preferably Locks) to Eliminate Races," Dr. Dobb's Journal, October 2007.
[2] H. Sutter. "The Trouble With Locks," C/C++ Users Journal, March 2005. Available at http://gotw.ca/publications/mill36.htm.
[3] H. Boehm. "Reordering Constraints for Pthread-Style Locks," Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'07), March 2007.
Herb is a software architect at Microsoft and chair of the ISO C++ Standards committee. He can be contacted at www.gotw.ca.
