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

d11sutt_p6ma 9/10/07 11:28 AM Page 58 Effective Concurrency Example 2: One Producer, Many Consumers, Using Lock-Free Mailboxes Next, let’s consider a similar example, but instead of locks ,we’ll use ordered atomic variables to synchronize the Producer-toConsumers handoff…and no synchronization at all for interConsumers contention. The idea in this second approach is to use a set of ordered atomic variables (e.g., Java/.NET volatile, proposed C++0x atomic), one for each Consumer, that will serve as “mailbox” slots for the Consumers individually. Each mail slot can hold exactly one item at a time. As the Producer produces each new task, he puts it in the next mailbox that doesn’t already contain an item using an atomic write; this lets the Consumers run concurrently with the Producer, as they check their slots and perform work while the Producer is still manufacturing and assigning later tasks. For further efficiency, to avoid making the Consumer busy-wait whenever its slot is initially or temporarily empty, we’ll also give each Consumer a semaphore sem that the Producer will signal every time it puts a task into the Consumer’s mail slot. Finally, once all the tasks have been assigned, the Producer starts to put “done” dummy tasks into mailboxes that don’t already contain an item until every mailbox has received one. Here’s the code: // One Producer thread: Changes any box from null to nonnull // curr = 0; // keep a finger on the current mailbox // Phase 1: Build and distribute tasks (use next available box) while( ThereAreMoreTasks() ) { task = AllocateAndBuildNewTask(); while( slot[curr] != null ) // acquire null: look for next curr = (curr+1)%K; // empty slot slot[curr] = task; // release nonnull: "You have mail!" sem[curr].signal(); } // Phase 2: Stuff the mailboxes with"done" signals numNotified = 0; while( numNotified < K ) { while( slot[curr] == done ) // acquire: look for next not-yetcurr = (curr+1)%K; // notified slot if( slot[curr] == null ) { // acquire null: check that the // mailbox is empty slot[curr] = done; // release done: write sentinel sem[curr].signal(); ++numNotified; } } A few notes: First, you can easily generalize this to replace each slot with a bounded queue; the previous example just expresses a bounded queue with a maximum size of 1. Second, this Producer code can needlessly busy-wait when it’s trying to write a new task (or the remaining done sentinels) and there are no free slots. This can be addressed by adding another semaphore, which the Producer waits for when it has no free slots and that is signaled by each Consumer when it resets its slot to null. I’ve left that logic out for now to keep the example clearer. In Example 2, it’s not quite as easy to check that we did it right as it was when we used locks back in Example 1, but we can reason about the code to convince ourselves that it is correct. First, note how each Consumer’s read of its slot “acquires” whatever value the Producer last wrote there, and the Producer’s read of each slot “acquires” whatever value the corresponding Consumer last wrote there. We avoid conflicts because while the slot is null, it’s owned by the Producer (only the Producer can change a slot from null to non-null); and while it’s nonnull, it’s owned by its corresponding Consumer (only the Consumer can change its slot from nonnull to null). 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; mut.lock(); … etc. … mut.unlock(); // a // b // 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! On the other side of the mailbox wall, each Consumer checks only its own mailbox. If its slot holds a new task, the Consumer takes the task, resets its mail slot to “empty,” and then processes the task. If the mailbox holds a “done” dummy task, the Consumer knows it can stop. // K Consumer threads (mySlot = 0..K-1): // Each changes its own box from non-null to null // myTask = null; while( myTask != done ) { while( (myTask = slot[mySlot]) == null ) // sem[mySlot].wait(); // if( myTask != done ) { slot[mySlot] = null; // // DoWork( myTask ); } } acquire nonnull, without busy-waiting release null: tell him we took it 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 58 Dr. Dobb’s Journal l www.ddj.com l November 2007 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.