Effective Concurrency: Writing a Generalized Concurrent Queue

The next Effective Concurrency column, “Writing a Generalized Concurrent Queue”, just went live on DDJ’s site, and also appears in the print magazine.

From the article:

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: …

I hope you enjoy it. Finally, here are links to previous Effective Concurrency columns (based on the magazine print issue dates):

August 2007: The Pillars of Concurrency

September 2007: How Much Scalability Do You Have or Need?

October 2007: Use Critical Sections (Preferably Locks) to Eliminate Races

November 2007: Apply Critical Sections Consistently

December 2007: Avoid Calling Unknown Code While Inside a Critical Section

January 2007: Use Lock Hierarchies to Avoid Deadlock

February 2008: Break Amdahl’s Law!

March 2008: Going Superlinear

April 2008: Super Linearity and the Bigger Machine

May 2008: Interrupt Politely

June 2008: Maximize Locality, Minimize Contention

July 2008: Choose Concurrency-Friendly Data Structures

August 2008: The Many Faces of Deadlock

September 2008: Lock-Free Code: A False Sense of Security

October 2008: Writing Lock-Free Code: A Corrected Queue

November 2008: Writing a Generalized Concurrent Queue

3 thoughts on “Effective Concurrency: Writing a Generalized Concurrent Queue

  1. It is good that the queue can maintain its own integrity when there are multiple producers and consumers without using mutexes.

    However, if one were to use that queue for building a thread pool, for an instance, how would consumer threads wait till data become available? With no external locking such design assumes busy waiting when the queue is empty, which is useless in practice. If there is external locking, then there is no need for any atomic wrappers and busy wait synchronisation in the queue.

    I wonder where such a queue could be used on practice.

  2. Hi, I’d like to make two comments about the article.

    The first is regarding the DCAS requirement. It is, in fact, not required. See the recent “Non-Blocking Concurrent FIFO Queues with Single Word Synchronization Primitives” by C. Evequoz for a circular-array-based queue; I’m sure the technique can be used for a linked-list-based queue.

    Additionally, while some 64-bit CPUs like the Itanium don’t have a true DCAS, x86-64 Intels and recent x86-64 AMDs have cmpxchg16b, accessible for example in Windows with _InterlockedCompareExchange128.

Comments are closed.