Dr. Dobb's Journal - July 2008 - (Page 44)

Core Technology LOCK-FREE QUEUES }; Figure 1: Adding an empty T() element in the constructor of the LockFreeQueue . Figure 2: The Ping-Pong test. Consume() may fail to read an element (and return false). Unlike traditional lockbased queues, this queue works fast when the queue is not empty, but needs an external locking or polling method to wait for data. Sometimes you want to wait if there is no element available in the queue, and avoid returning false. A naive approach to waiting is: T Consume() { T tmp; while (!Consume(tmp)) ; return tmp; } Considering how simple this code is, you might wonder how can it be threadsafe. The magic is due to design, not implementation. Take a look at the implementation of the Produce() and Consume() methods. The Produce() method looks like this: void Produce(const T& t) { list.push_back(t); iTail = list.end(); list.erase(list.begin(), iHead); } To understand how this works, mentally separate the data from LockFreeQueue into two groups: • The list and the iTail iterator, modified by the Produce() method (Producer thread). • The iHead iterator, modified by the Consume() method (Consumer thread). Produce() is the only method that changes the list (adding new elements and erasing the consumed elements), and it is essential that only one thread ever calls Produce()—it’s the Producer thread! The iterator (iTail) (only manipulated by the Producer thread) changes it only after a new element is added to the list. This way, when the Consumer thread is reading the iTail element, the new added element is ready to be used. The Consume() method tries to read all the elements between iHead and iTail (excluding both ends). bool Consume(T& t) { typename TList::iterator iNext = iHead; ++iNext; if (iNext != iTail) { iHead = iNext; t = *iHead; return true; } return false; } This method reads the elements, but doesn’t remove them from the list. Nor does it access the list directly, but through the iterators. They are guaranteed to be valid after std::list is modified, so no matter what the Producer thread does to the list, you are safe to use them. The std::list maintains an element (pointed to by iHead) that is considered already read. For this algorithm to work even when the queue was just created, I add an empty T() element in the constructor of the LockFreeQueue (see Figure 1): LockFreeQueue() { list.push_back(T()); iHead = list.begin(); iTail = list.end(); } This Consume() method will likely heat up one of your CPUs red-hot to 100percent use if there are no elements in the queue. Nevertheless, this should have good performance when the queue is not empty. However, if you think of it, a queue that’s almost never empty is a sign of systemic trouble: It means the consumer is unable to keep pace with the producer, and sooner or later, the system is doomed to die of memory exhaustion. Call this approach NAIVE_POLLING. A friendlier Consume() function does some pooling and calls some sort of Listing One #include #include #include template struct WaitFreeQueue { void Produce(const T& t) { queue.Produce(t); cond.notify_one(); } bool Consume(T& t) { return queue.Consume(t); } T Consume(int wait_time = 1/*milliseconds*/) { T tmp; if (Consume(tmp)) return tmp; // the queue is empty, try again (possible waiting ) boost::mutex::scoped_lock lock(mtx); while (!Consume(tmp)) // line A { boost::xtime t; boost::xtime_get(&t, boost::TIME_UTC); AddMilliseconds(t, wait_time); cond.timed_wait(lock, t); // line B } return tmp; } private: LockFreeQueue queue; boost::condition cond; boost::mutex mtx; }; 44 Dr. Dobb’s Journal l www.ddj.com l July 2008 http://www.ddj.com

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

Dr. Dobb's Journal - July 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook Engineers Without Borders Conversations Patricia Tries Event-Based Architectures Graphs Versus Objects Lock-Free Queues Dr. Dobb’s Architecture & Design World Java and the Nokia N10 Internet Tablet Effective Concurrency The Agile Edge Swaine’s Flames

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