Dr. Dobb's Journal - November 2008 - (Page 69)

which effectively adds extra padding. If so, and if we know how much that will be, we could reduce our internal padding proportionately to make a heap-allocated Node exactly fill one cache line. Next, here are our queue control variables: char pad0[CACHE_LINE_SIZE]; // for one consumer at a time Node* first; char pad1[CACHE_LINE_SIZE - sizeof(Node*)]; // shared among consumers atomic consumerLock; char pad2[CACHE_LINE_SIZE - sizeof(atomic )]; // for one producer at a time Node* last; char pad3[CACHE_LINE_SIZE - sizeof(Node*)]; // shared among producers atomic producerLock; char pad4[CACHE_LINE_SIZE - sizeof(atomic )]; void Produce( const T& t ) { Node* tmp = new Node( new T(t) ); while( producerLock.exchange(true) ) {} // acquire exclusivity last->next = tmp; // publish to consumers last = tmp; // swing last forward producerLock = false; // release exclusivity } Again, we add padding to make sure hat data used by different threads stay physically separate in memory and cache. Clearly, we want the consumer-end data and the producer-end data to be on separate cache lines; but even though only one producer and one consumer will be active at a time, we want to keep the locking variable separate so that waiting consumers spinning on consumerLock won’t contend on the cache line that contains first which the active consumer is updating, and that waiting producers spinning on producerLock won’t slow down the active producer who is updating last. The constructor just sets up the initial empty state, and the destructor (in .NET or Java, this would be the disposer) just walks the internal list and tears it down: public: LowLockQueue() { first = last = new Node( nullptr ); producerLock = consumerLock = false; } ~LowLockQueue() { while( first != nullptr ) { // release the list Node* tmp = first; first = tmp->next; delete tmp->value; // no-op if null delete tmp; } } First, we want to do as much work as possible outside the critical section of code that actually updates the queue. In this case, we can do all of the allocation and construction of the new node and its value concurrently with any number of other producers and consumers. Second, we “commit” the change by getting exclusive access to the tail of the queue. The while loop keeps trying to set the producerLock to true until the old value was false because while the old value was true, it means someone else already has exclusivity. The way to read this while loop is, “until I get to be the one to change producerLock from false to true,” which means that this thread has acquired exclusivity. Then we can update last->next and last itself, which are two separate writes and cannot be done as a single atomic operation on most processors without some sort of lock. Finally, we release exclusivity on the tail of the queue by setting producerLock to false. Figure 1: Structure of an empty queue. bool Consume( T& result ) { while( consumerLock.exchange(true) ) {} // acquire exclusivity Next, we read the head node’s next pointer. If it’s not null, we need to take out the first value but we want to do as little work as possible here inside the exclusive critical section: Node* theFirst = first; Node* theNext = first->next; if( theNext != nullptr ) { // if queue is nonempty T* val = theNext->value; // take it out theNext->value = nullptr; // of the Node first = theNext; // swing first forward consumerLock = false; // release exclusivity Now we’re done touching the list, and other consumers can make progress while we do the remaining copying and cleanup work off to the side: result = *val; // now copy it back delete val; // clean up the value delete theFirst; // and the old dummy return true; // and report success } Consume Likewise, we want to support any number of threads calling Consume, and let them run as concurrently as possible. First, we get exclusivity, this time on the head end of the queue: Otherwise, if theNext was null, the list was empty and we can immediately release exclusion and return that status: Produce Now let’s look at the first of the two key methods: Produce. The goal is to allow multiple producers, and to let them run as concurrently as possible: Figure 2: A queue containing four T objectsempty queue. November 2008 l www.ddj.com l Dr. Dobb’s Journal 69 http://www.ddj.com

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

Dr. Dobb's Journal - November 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer's Notebook Saving Open Source Conversations iPhone Building Your Own Web Server Green Telnet What's New In Boost Threads? Testing Service Oriented Architectures Test Case Generation, UML, and Eclipse Unit Testing Web Services C3 Programming The Agile Edge Swaine's Flames Effective Concurrency

Dr. Dobb's Journal - November 2008

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.