Dr. Dobb's Journal - September 2008 - (Page 68)

d09sutt_p3ds 7/14/08 12:46 PM Page 68 Effective Concurrency by Herb Sutter Lock-Free Code: A False Sense of Security Writing correct lock-free code is harder than it looks GIVEN THAT LOCK-BASED synchronization has serious problems [1], it can be tempting to think lock-free code must be the answer. Sometimes that is true. In particular, it’s useful to have libraries provide hash tables and other handy types whose implementations are internally synchronized using lock-free techniques, such as Java’s ConcurrentHashMap, so that we can use those types safely from multiple threads without external synchronization and without having to understand the subtle lock-free implementation details. But replacing locks wholesale by writing your own lock-free code is not the answer. Lock-free code has two major drawbacks. First, it’s not broadly useful for solving typical problems—lots of basic data structures, even doubly linked lists, still have no known lock-free implementations. Coming up with a new or improved lockfree data structure will still earn you at least a published paper in a refereed journal, and sometimes a degree. Second, it’s hard even for experts. It’s easy to write lock-free code that appears to work, but it’s very difficult to write lock-free code that is correct and performs well. Even good magazines and refereed journals have published a substantial amount of lock-free code that was actually broken in subtle ways and needed correction. To illustrate, let’s dissect some peer-reviewed lockfree code that was published here in DDJ just two months ago [2]. The author, Petru Marginean, has graciously allowed me to dissect it here so that we can see what’s wrong and why, what lessons we should learn, and how to write the code correctly. That someone as knowledgable as Petru, who has published many good and solid articles, can get this stuff wrong should be warning enough that lock-free coding requires great care. Marginean uses a nice technique that is designed to prevent conflicts between the writer and reader: • The producer and consumer always work in separate parts of the underlying list, so that their work won’t conflict. At any given time, the first “unconsumed” item is the one after the one iHead refers to, and the last (most recently added) “unconsumed” item is the one before the one iTail refers to. • The consumer increments iHead to tell the producer that it has consumed another item in the queue. • The producer increments iTail to tell the consumer that another item is now available in the queue. Only the producer thread ever actually modifies the queue. That means the producer is responsible, not only for adding into the queue, but also for removing consumed items. To maintain separation between the producer and consumer and prevent them from doing work in adjacent nodes, the producer won’t clean up the most recently consumed item (the one referred to by iHead). The idea is reasonable; only the implementation is fatally flawed. Here’s the original code, written in C++ and using an STL doubly linked list as the underlying data structure. I’ve reformatted the code slightly for presentation, and added a few comments for readability: // Original code from [1] // (broken without external locking) // template struct LockFreeQueue { private: std::list list; typename std::list ::iterator iHead, iTail; public: LockFreeQueue() { list.push_back(T()); iHead = list.begin(); iTail = list.end(); } // add dummy separator Produce is called on the producer thread only: void Produce(const T& t) { list.push_back(t); // add the new item iTail = list.end(); // publish it list.erase(list.begin(), iHead); // trim unused nodes } Consume is called on the consumer thread only: bool Consume(T& t) { typename std::list ::iterator iNext = iHead; ++iNext; if (iNext != iTail) { // if queue is nonempty iHead = iNext; // publish that we took an item t = *iHead; // copy it back to the caller return true; // and report success } return false; // else report queue was empty } }; A Limited Lock-Free Queue Marginean’s goal was to write a limited lock-free queue that can be used safely without internal or external locking. To simplify the problem, the article imposed some significant restrictions, including that the queue must only be used from two threads with specific roles: one Producer thread that inserts into the queue, and one Consumer thread that removes items from the queue. 68 Dr. Dobb’s Journal l www.ddj.com l September 2008 The fundamental reason that the code is broken is that it has race conditions on both would-be lock-free variables, iHead and iTail. To avoid a race, a lock-free variable must have two key properties that we need to watch for and guarantee: atomicity and ordering. These variables are neither. Atomicity First, reads and writes of a lock-free variable must be atomic. For this reason, lockfree variables are typically no larger than the machine’s native word size, and are http://www.ddj.com

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

Dr. Dobb's Journal - September 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook A Conversation With Erik Demaine Application Lifecycle Management Meets Model-Driven Development Building a Robust Development Environment Real Users Really Matter Matching Wildcards: An Algorithm The Android Mobile Phone Platform Managing Application Thread Use Signalling Integer Overflows in Java .NET Development & the IBM WebSphere Portal Server The Agile Edge Effective Concurrency Swaine’s Flames

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