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

by Petru Marginean Core Technology Lock-Free Queues One thread can write and another read— at the same time! Queues can be useful in a variety of systems involving data-stream processing. Typically, you have a data source producing data—requests coming to a web server, market feeds, or digital telephony packets—at a variable pace, and you need to process the data as fast as possible so there are no losses. To do this, you can push data into a queue using one thread and process it using a different thread—a good utilization of resources on multicore processors. One thread inserts data into the queue, and the other reads/deletes elements from the queue. Your main requirement is that a high-rate data burst does not last longer than the system’s ability to accumulate data while the consumer thread handles it. The queue you use has to be threadsafe to prevent race conditions when inserting/removing data from multiple threads. For obvious reasons, it is necessary that the queue mutual exclusion mechanism add as little overhead as possible. In this article, I present a lock-free queue (the source code for the lockfreequeue class is available online; see “Resource Center,” page 3) in which one thread can write to the queue and another read from it—at the same time without any locking. To do this, the code implements these requirements: • There is a single writer (Producer) and single reader (Consumer). When you have multiple producers and consumers, you can still use this queue with some external locking. You cannot have multiple producers writing at the same time (or multiple consumers consuming the data simultaneously), but you can have one producer and one consumer (2x threads) accessing the queue at the same time (Responsibility: developer). • When inserting/erasing to/from an std::list , the iterators for the existing elements must remain valid (Responsibility: library implementor). • Only one thread modifies the queue; the producer thread both adds/erases elements in the queue (Responsibility: library implementor). • Beside the underlying std::list used as the container, the lock-free queue class also holds two iterators pointing to the not-yet-consumed range of elements; each is modified by one thread and read by the other (Responsibility: library implementor). • Reading/writing list ::iterator is atomic on the machine upon which you run the application. If they are not on your implementation of STL, you should check whether the raw pointer’s operations are atomic. You could easily replace the iterators to be mentioned shortly with raw pointers in the code (Responsibility: machine). Because I use Standard C++, the code is portable under the aforementioned “machine” assumption: template struct LockFreeQueue { LockFreeQueue(); void Produce(const T& t); bool Consume(T& t); private: typedef std::list TList; TList list; typename TList::iterator iHead, iTail; Petru is a Vice President for Morgan Stanley, where he works as a C++ senior programmer in investment banking. He can be contacted at petru.marginean@gmail.com. July 2008 l www.ddj.com l Dr. Dobb’s Journal 43 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.