Dr. Dobb's Journal - August 2008 - (Page 53)

by Herb Sutter Effective Concurrency The Many Faces of Deadlock Despite the name, deadlock isn’t (only) about locks QUICK: WHAT IS “DEADLOCK”? How would you define it? One common answer is: “When two threads each try to take a lock the other already holds.” Yes, we do indeed have a potential deadlock anytime two threads (or other concurrent tasks, such as work items running on a thread pool; for simplicity, I’ll say “threads” for the purposes of this article) try to acquire the same two locks in opposite orders, and the threads might run concurrently. The potential deadlock will only manifest when the threads actually do run concurrently, and interleave in an appropriately bad way where each successfully takes its first lock and then waits forever on the other’s, as in the execution A->B>C->D in the following example: // Thread 1 mut1.lock(); mut2.lock(); // Thread 2 mut2.lock(); mut1.lock(); // A // C: blocks // B // D: blocks Dead(b)locks The key thing to recognize is that deadlock doesn’t arise from a locking cycle exclusively. Any blocking (or, waiting) cycle will do. So a complete definition of deadlock could be put something like this: deadlock, n.: When N concurrent tasks enter a cycle where each one is blocked waiting for the next. Clearly, blocking operations include all kinds of blocking synchronization: acquiring a lock (of course); waiting for a semaphore or condition variable to be signaled; waiting to join with another thread or task…But it also includes any other kind of call that waits for a result, including: • Acquiring exclusive access to any resource (notably I/O, such as opening a file for writing). • Waiting for a future or write-once variable to be available (the result of an asynchronous task). • Waiting for any other kind of message to arrive from elsewhere, whether inprocess (waiting for a queue container to become nonempty, waiting for a message to be placed into a GUI message queue) or out-of-process or out-ofbox (performing a blocking receive call on a TCP socket, for instance). • Anything else that waits for some other condition to be satisfied. 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.” Complex Combinations For a more complex example, consider Figure 1. There are four things going on: • Thread 1 is a GUI window message handler that’s in the middle of processing a message. As part of that processing, it needs to use some shared state and so wants to take a lock on mutex mut—which is currently held by Thread 4. • Thread 4 is doing something with the same shared state and so has acquired mut already, and is just waiting to receive a message from a message queue—a message that is yet to be sent from Thread 2. (Doing communication inside a critical section is problematic and should be avoided where possible. See [2] for more about why to avoid doing communication while holding a lock.) • Thread 2 hasn’t got around to sending that message yet, because it’s waiting to open a file for writing, which is an exclusive mode—a file currently opened for writing and appending on Thread 3. • Thread 3 is working with the file, and posts a message to the window, which is a synchronous call that blocks to wait for the message to be handled—but Thread 1 is already handling a message and so can’t pump and handle this one. Finally, for extra fun and just to emphasize the point that any kind of blocking operation will do, consider that deadlock can involve a human—you! For example: // Thread 1 (running in the CPU hardware) mut.lock(); char = ReadKeystroke(); // Task 2 (running in your brain's wetware) Wait for the prompt to appear. OK, now start typing. // Thread 3 (back in the hardware again) mut1.lock(); Print ( "Press 'Any' key to continue " ); // blocks Deadlock Among Messages “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.” For example, consider this code, which is similar to the lock-based deadlock example: // Thread 1 mq1.receive(); mq2.send( x ); // Thread 2 mq2.receive(); mq1.send( y ); // blocks // blocks Now Thread 1 is blocked, waiting for a message that Thread 2 hasn’t sent yet. Unfortunately, Thread 2 is also blocked, waiting in turn for a message that Thread 1 hasn’t sent yet. The result: A deadlock that is qualitatively the same as the one that arose from locks. So, then, what is a complete definition of deadlock? // blocks // blocks Figure 1: Sample deadlock among locks, message pumps, messages queues, and file access. Here, Thread 1 can’t make progress because it’s blocked waiting for you to press a key. You haven’t pressed a key because you’re still waiting for a prompt. Thread 3 can’t print the prompt until it returns from being blocked waiting to lock a mutex…held by Thread 1. Around and around we go. August 2008 l www.ddj.com l Dr. Dobb’s Journal 53 http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - August 2008

Dr. Dobb's Journal - August 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook A Conversation with Christos Papadimitriou OpenGL and Mobile Devices: Round 2 Ellipse Specification Using Vectors Embed Custom GUIs in WPF Building RIAs on J2EE Foundations Disentangling Concepts in Object-Oriented Systems The Agile Edge Effective Concurrency Swaine’s Flames

Dr. Dobb's Journal - August 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.