Dr. Dobb's Journal - October 2007 - (Page 58)

Effective Concurrency Figure 1: Anatomy of a critical section. Memory Reordering Figure 1 shows the canonical form and rules governing a critical section. Like any transaction, a critical section follows the basic acquire-work-release structure. Compilers and processors routinely execute your code out of the order you specified in your source file, in order to make it run faster. For example, compiler optimizers want to help you by hoisting invariant calculations out of a loop; that means moving the instructions out of the loop body and actually executing them before the beginning of the loop. Processors want to help you by hiding the cost of accessing memory; that means moving expensive memory instructions ahead so that they can start sooner and overlap by having several in flight at the same time. All of this reordering is fine as long as your program can’t tell the difference—and the definition of “the program can’t tell the difference” is “everybody respects the critical sections.” Specifically: • The programmer shall correctly eliminate races using critical sections. • All reordering transformations shall respect the critical sections (and normal sequential control/flow dependencies as has always been done for plain old sequential optimizations). So, for a reordering transformation to be valid, it must respect the program’s critical sections by obeying the one key rule of critical sections: Code can’t move out of a critical section. (It’s always okay for code to move in.) We enforce this golden rule by requiring symmetric one-way fence semantics for the beginning and end of any critical section, illustrated by the arrows in Figure 1: • Entering a critical section is an acquire operation, or an implicit acquire fence: Code can never cross the fence upward, 58 Dr. Dobb’s Journal l www.ddj.com l October 2007 that is, move from an original location after the fence to execute before the fence. Code that appears before the fence in source code order, however, can happily cross the fence downward to execute later. • Exiting a critical section is a release operation, or an implicit release fence: This is just the inverse requirement that code can’t cross the fence downward, only upward. It guarantees that any other thread that sees the final release write will also see all of the writes before it. [2] mut.lock(); // enter (“acquire”) // critical section y = “universe”; mut.unlock(); // exit (“release”) // critical section z = “everything”; // where can this // line appear to // move to? What are the legal reorderings of the assignments to x and z? Again assuming that x, y, and z are independent and not aliased, it is perfectly legal for the system to transform the above code to: mut.lock(); z = “everything”; // ok: can move as // far up as this y = “universe”; x = “life”; // ok: can move as // far down as this mut.unlock(); Code Must Never Move Out Let’s see what “code can’t move out” means in the context of the following code, which acquires a mutex mut that protects two integers x and y: mut.lock(); x = 42; // // // // enter (“acquire”) critical section where can this line appear to move to? y = 43; mut.unlock(); // exit (“release”) //critical section What are the legal reorderings of the assignment to x? It is perfectly legal for the system to transform the above code to: mut.lock(); y = 43; x = 42; // ok: can move down // past y’s assignment mut.unlock(); Even though the moved lines now run while holding the lock, it doesn’t alter the meaning or correctness of the code. It is always safe to add extra guarantees; in this case, to hold a lock a little longer. But it is not safe to arbitrarily remove guarantees, such as to fail to hold a needed lock. Therefore, a system cannot arbitrarily reorder the code to cross either fence the wrong way: z = “everything”; // invalid: race bait mut.lock(); y = “universe”; mut.unlock(); x = “life”; // invalid: race bait because both assignments still happen inside the protected critical section (and do not otherwise depend on each other, assuming x and y are independent and not aliased). A system may not, however, transform the code to either x = 42; // invalid: race bait mut.lock(); y = 43; mut.unlock(); Note that this is true even though the assignments to x and z were not initially inside the critical section. For example, what if setting y = “universe” is treated as a flag that tells another thread that x is now ready to be shared, so that y publishes x? That is why no code must pass the release fence in the downward direction. [3] or mut.lock(); y = 43; mut.unlock(); x = 42; // invalid: race bait Automate Acquire/Release The whole system has to play by the rules— meaning the rules you wrote into your program. In particular, acquire and release fencing rules have to apply at every point beyond the source code, because when your program does strange things, it doesn’t matter whether it was your compiler that reordered your statements or your processor that reordered the instructions emitted by the compiler. At the processor level, the only way to avoid instruction reordering is to use acquire- and release-style fences that most because either of these would move the assignment outside the critical section and therefore create a potential race on x. So what about moving code into a critical section? It’s Okay For Code to Move In Consider an adapted example: x = “life”; // where can this line // appear to move to? http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - October 2007

Cover Contents Hmmmm Alia Vox Developer Diaries Developer’s Notebook AI: It’s OK Again! Conversations Visual Cryptography and Bit-Plane Complexity Segmentation Inside the Windows Vista Disk Encryption Algorithm Memory-Aware Components Software and the Core Description Process Logging In C++ Effective Concurrency The Agile Edge Swaine’s Flames

Dr. Dobb's Journal - October 2007

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.