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

Effective Concurrency by Herb Sutter Writing a Generalized Concurrent Queue A two-lock queue with pretty good concurrency LAST MONTH [1], I showed code for a lock-free queue that supported the limited case of exactly two threads—one producer, and one consumer. That’s useful, but maybe not as exciting now that our first rush of lock-free coding glee has worn off. This month, let’s tackle the general problem of supporting multiple producers and multiple consumers with as much concurrency as possible. The code in this article uses four main design techniques: First, we’ll use (the equivalent of ) two locks: One for the head end of the queue to regulate concurrent consumers, and one for the tail to regulate concurrent producers. We’ll use ordered atomic variables (C++0x atomic , Java/.NET volatile) directly instead of prefabricated mutexes, but functionally we’re still writing spinlocks; we’re just writing them by hand. Although this means it’s not a purely “lock-free” or nonblocking algorithm, it’s still quite concurrent because we’ll arrange the code to still let multiple consumers and multiple producers make progress at the same time by arranging to do as much work as possible outside the small critical code region that updates the head and tail, respectively. Second, we’ll have the nodes allocate the contained T object on the heap and hold it by pointer instead of by value. [2] To experienced parallel programmers this might seem like a bad idea at first, because it means that when we allocate each node we’ll also need to perform an extra heap allocation, and heap allocations are notorious scalability busters on many of today’s memory allocators. It turns out that, even on a system with a nonscalable allocator, the benefits typically outweigh the advantages: Holding the T object by pointer let us get greater concurrency and scalability among the consumer threads, because we can take the work of 68 Dr. Dobb’s Journal l www.ddj.com l November 2008 actually copying the T value out of the critical section of code that updates the shared data structure. Third, we don’t want to have the producer be responsible for lazily removing the nodes consumed since the last call to Produce, because this is bad for performance: It adds contention on the queue’s head end, and it needlessly delays reclaiming consumed nodes. Instead, we’ll let each consumer be responsible for trimming the node it consumed, which it was touching anyway and so gives better locality. Fourth, we want to follow the advice that “if variables A and B are not protected by the same mutex and are liable to be used by two different threads, keep them on separate cache lines” to avoid false sharing or “ping-ponging” which limits scalability. [3] In this case, we want to add padding to ensure that different nodes (notably the first and last nodes), the first and last pointers into the list, and the producerLock and consumerLock variables are all on different cache lines. A Two-Lock Multiproducer/Consumer Queue The queue data structure itself is a singly linked list. To make the code simpler for the empty-queue boundary case, the list always contains a dummy node at the head, and so the first element logically in the queue is the one contained in the node after first. Figure 1 shows the layout of an empty queue, and Figure 2 shows a queue that holds some objects. Each node holds the T object by pointer and adds padding: template struct LowLockQueue { private: struct Node { Node( T* val ) : value(val), next(nullptr) { } T* value; atomic next; char pad[CACHE_LINE_SIZE - sizeof(T*)- sizeof(atomic )]; }; Like any shared variable, the next pointer needs to be protected by a mutex or, as here, declared as an ordered atomic type (C++0x atomic or Java/.NET volatile). The padding here is to ensure that two Node objects won’t occupy the same cache line; in particular, in a nonempty queue, having the first and last nodes in the same cache line would penalize performance by causing invisible contention between the producer and consumer. Note that the amount of padding shown here and later on errs on the side of being too conservative: Each Node will be allocated on the heap, and a heap allocator may add its own extra overhead to each allocated block for alignment and housekeeping information, 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.