Dr. Dobb's Journal - November 2007 - (Page 57)

d11sutt_p6ma 9/10/07 11:28 AM Page 57 by Herb Sutter Effective Concurrency Apply Critical Sections Consistently Guaranteeing mutual exclusion on shared variables 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 “releaseacquire” 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. mut.lock(); queue.push( done ); mut.unlock(); cv.notify(); // enter critical section // add sentinel value; that’s all folks // exit critical section On the consumption side, the Consumer threads each pull individual tasks off the completed queue. Here, myTask is an ordinary variable local to each Consumer: // K Consumer threads // myTask = null; while( myTask != done ) { mut.lock(); while( queue.empty() ) cv.wait( mut ); myTask = queue.first(); if( myTask != done ) queue.pop(); mut.unlock(); if( myTask != done ) DoWork( myTask ); } // // // // // // // enter critical section if nothing’s there, to avoid busy-waiting we’ll release and reenter critical section take a copy of the task remove it from queue unless it was the sentinel, which we want to leave there for others to see exit critical section Example 1: One Producer, Many Consumers, Using Locks Imagine we have a single Producer thread that produces a number of tasks for Consumer threads to perform. The Producer pushes the tasks into a shared queue, and finally pushes a special done sentinel to mark the end of the work. The queue object is protected at all times using mutex mut, which the Producer holds only as long as necessary for a single push, so that Consumers can start executing their tasks concurrently with the Producer. For further efficiency, to avoid making the Consumers busy-wait whenever the queue is initially or temporarily empty, the Producer will also signal condition variable cv every time something has been added to the queue: // One Producer thread // while( ThereAreMoreTasks() ) { task = AllocateAndBuildNewTask(); mut.lock(); // enter critical section queue.push( task ); // add new task mut.unlock(); // exit critical section cv.notify(); } All of these critical sections are easy to see. This code simply protects the data structure using the same mutex for its entire shared lifetime, and it’s easy to check that you did it right—just look to make sure the code only refers to queue when inside some critical section that holds a lock on mut. The primary expression of critical sections is the explicit locking done on the mutex. The condition variable is just icing on the cake—an optimization that lets us express an efficient wait point in the middle of a locked section so that the Consumer race cars don’t have to expend needless energy spinning their tires (in this case, their lock/unlock loop) while waiting for the Producer to give them the green light. Synchronization Type Locks To Enter a Critical Section Acquire lock To Exit a Critical Section Release lock Notes Preferred, despite their drawbacks [2] Useful with locks to Condition variables Wait for cv wait point in the Notify cv express an efficient middle of a locked Semaphores Acquire semaphore Release semaphore section Use judiciously; significant care required Use judiciously, significant care required Avoid, difficult to use correctly and usually nonportable Ordered atomics (e.g., Java/.NET volatile, C++0x atomic ) Unordered atomics and explicit fences (e.g., aligned integers and Linux mb or Win32 MemoryBarrier) Read from variable * Write to variable ** Read from variable followed by fence Fence followed by write to variable * 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 Table 1: Common ways to express critical sections. November 2007 l www.ddj.com l Dr. Dobb’s Journal 57 http://www.ddj.com

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

Contents Hmmmm Alia Vox Developer Diaries Developer’s Notebook Smart Compilers - But Smart Enough? Conversations Grid-Enabling Resource-Intensive Applications Distributed Computing: Windows and Linux Adobe AIR: Desktop/Web Convergence Transparency on Demand Reusable Associations Effective Concurrency The Agile Edge Swaine’s Flames

Dr. Dobb's Journal - November 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.