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
Sutter’s Mill 
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.
Looks like the URL for LockFree Code: A False Sense of Security has been changed to
http://www.ddj.com/cpp/210600279
The URL published above http://www.ddj.com/cpp/209903274 isn’t valid
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.