The critical section is our One True Tool for guaranteeing mutual exclusion on mutable shared variables. Table 1 summarizes several common ways to express exclusive critical sections (see last month's column [1] for details). A useful way to think about the synchronization in your program is as a daisy-chain of these "release-acquire" handoffs that stitch all the threads' critical sections together into some linear order, so that each one "acquires" the cumulative work done and is "released" by all the others that preceded it.
Like most tools, these must be applied consistently, and with the intended meanings. A program must ensure that every use of a mutable shared object is properly protected using exactly one of these mechanisms at any given point in its lifetime. Chaos can erupt if code tries to avoid or invert these meanings (e.g., trying to abuse taking a lock or reading an atomic variable as a "critical section exit" operation; see Example 3), or tries to use inconsistent synchronization techniques at the same time.
Let's consider some examples to illustrate the proper and improper uses of critical sections, to get us used to looking for where the critical sections' synchronization points should appear in the code.
Synchronization Type | To Enter a Critical Section | To Exit a Critical Section | Notes |
Locks | Acquire lock | Release lock | Preferred, despite their drawbacks [2] |
Condition variables | Wait for cv | Notify cv | Useful with locks to express an efficient wait point in the middle of a locked section |
Semaphores | Acquire semaphore | Release semaphore | Use judiciously; significant care required |
Ordered atomics (e.g., Java/.NET volatile, C++0x atomic | Read from variable * | Write to variable ** | Use judiciously, significant care required |
Unordered atomics and explicit fences (e.g., aligned integers and Linux mb or Win32 MemoryBarrier) | Read from variable followed by fence*** | Fence followed by write to variable*** | Avoid, difficult to use correctly and usually nonportable |
* or equivalent, such as calling a compare-and-swap function having at least acquire semantics | |||
** or equivalent, such as calling a compare-and-swap function having at least release semantics | |||
*** when in doubt, use a full fence |