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

D10Sutt_p5db 8/14/08 4:05 PM Page 69 The constructor simply initializes the list with a dummy element. The destructor (in C# or Java, the dispose method) releases the list. In a future column, I’ll discuss in detail why constructors and destructors of a shared object don’t need to worry about concurrency and races with methods of the same object; the short answer for now is that creating or tearing down an object should always run in isolation, so no internal synchronization needed. public: LockFreeQueue() { first = divider = last = new Node( T() ); } ~LockFreeQueue() { while( first != nullptr ) { Node* tmp = first; first = tmp->next; delete tmp; } } Figure 2: Ownership rules of the road. // add dummy separator The Consumer Consume is called on the consumer thread only: bool Consume( T& result ) { if( divider != last ) { result = divider->next->value; divider = divider->next; return true; } return false; } }; // // // // if queue is nonempty C: copy it back D: publish that we took it and report success // release the list Next, we’ll look at the key methods, Produce and Consume. Figure 2 shows another view of the list by who owns what data by color-coding: The producer owns all nodes before divider, the next pointer inside the last node, and the ability to update first and last. The consumer owns everything else, including the values in the nodes from divider onward, and the ability to update divider. // else report empty The Producer Produce is called on the producer thread only: void Produce( const T& t ) { last->next = new Node(t); last = last->next; while( first != divider ) { Node* tmp = first; first = first->next; delete tmp; } } // add the new item // publish it // trim unused nodes First, the producer creates a new Node containing the value and links it to the current last node. At this point, the node is not yet shared, but still private to the producer thread even though there’s a link to it; the consumer will not follow that link unless the value of last says it may follow it. Finally, when all the real work is done—the node exists, its value is completely initialized, and it’s correctly connected—then, and only then, do we write to last to “commit” the update and publish it atomically to the consumer thread. The consumer reads last, and either sees the old value (and ignores the new partly constructed element even if the last->next pointer might already have been set) or the new value that officially blesses the new node as an approved part of the queue, ready to be used. Finally, the producer performs lazy cleanup of now-unused nodes. Because we always stop before divider, this can’t conflict with anything the consumer might be doing later in the list. What if while we’re in the loop, the consumer is consuming items and changing the value of divider? No problem: Each time we read divider, we see it either before or after any concurrent update by the consumer, both of which let the producer see the list in a consistent state. First, the consumer checks that the list is nonempty by atomically reading divider, atomically reading last, and comparing them. This one-time check is safe because although last’s value may be changed by the producer while we are running the rest of this method, if the check is true once, it will stay true even if last moves, because last never backs up; it can only move forward to publish new tail nodes—which doesn’t affect the consumer, who only cares about the first node after the divider. If there is a valid node after divider, the consumer copies its value and then, finally, advances divider to publish that the queue item was removed. Yes, we could eliminate the need to make the last variable shared: The consumer only uses the value of last to check whether there’s another node after the divider, and we could instead have the consumer just test whether divider->next is non-null. That would be fine, and it would let us make last an ordinary variable; but if we do that, we must also remember that this change would make each next member a shared variable instead, and so to make it safe, we would also have to change next’s type to atomic . I’m leaving last as is for now to make it easier to compare this code with the original version in [2], which did use such a tail iterator to communicate between the two threads. Do Work, Then Publish You might also have noticed that the original code in [2] did the equivalent of lines C (copy) and D (divider update) in the reverse order. You should always be alert and suspicious when you see code that tries to do things backwards: Remember, we’re supposed to do all the work off to the side (line C) and only then publish that we did it (line D), as previously shown. I’m sure someone is about to point out that we could actually get away with writing D then C in this code. Yes, but don’t; it’s a bad habit. It’s true that, in this particular case and now that divider is an ordered atomic variable (which wasn’t true in the original code), it just so happens that we could get away with writing D then C due to the happy accident of a detail of the implementation combining with a design restriction: October 2008 l www.ddj.com l Dr. Dobb’s Journal Figure 1: The lock-free queue data structure. 69 http://www.ddj.com

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

Dr. Dobb's Journal - October 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook Is Your Next Language COBOL? Conversations Safe Coding Practices Code Signing in Adobe AIR OpenID Single Sign-On The Book Cipher Algorithm Indexing and Searching Image files Extending Continuous Integration Into ALM The Agile Edge Effective Concurrency Swaine’s Flames

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