The latest Effective Concurrency column, “The Many Faces of Deadlock”, just went live on DDJ’s site, and also appears in the print magazine. From the article:
… That’s the classic deadlock example from college. Of course, two isn’t a magic number. An improved definition of deadlock is: “When N threads enter a locking cycle where each tries to take a lock the next already holds.”
“But wait,” someone might say. “I once had a deadlock just like the code you just showed, but it didn’t involve locks at all—it involved messages.” …
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 |
Sutter’s Mill 
Herb, you may be interested in this blog post from Intel which appears to contradict your assertion about messaging-based deadlocks:
http://softwareblogs.intel.com/2008/08/25/is-dos-the-ideal-parallel-environment-part-i
I don’t think the author understood you aright (see the comments), but I could be wrong.
Hi Herb,
I would like to say thank you very much for this article of deadlock, especially for one of its faces about message. Since I’m a developer of Chinese input method, there’s always something mysterious to me such as why ImmGenerateMessage is better to be invoked by non-member (even global) function rather than member function that may be involved within stack/heap. This article provides a clearer hint to my situation: maybe I have more blocks than I assumed, including OS, IMM32, my RPC client-server, my C# and C++/CLR GUI, and so on……
Hi
I find this article one of the most important one in this series of articles. I have a question regarding this code:
// Global data Mutex mut;
MessageQueue queue;
// Thread 1
mut.lock(); // A
queue.receive(); // B: blocks
mut.unlock();
// Thread 2
mut.lock(); // C: blocks
queue.send( msg );
I guess that there is no way to escape the deadlock considering this single queue approach that is not synchronized between sending/receiving by other means.
What could be possible solutions to that problem ?