Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Deadlock Dead(b)locks Dealing With Deadlock General Deadlock Detection

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();		// A
mut2.lock(); 		// C: blocks

// Thread 2
mut2.lock();		// B
mut1.lock(); 		// D: blocks

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."

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(); 		// blocks
mq2.send( x );

// Thread 2
mq2.receive(); 		// blocks
mq1.send( y );

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?

1 Deadlock | 2 Dead(b)locks | 3 Dealing With Deadlock | 4 General Deadlock Detection Next Page

RELATED ARTICLES Sun Releases JavaFX 1.0 Engelbart and the Dawn of Interactive Computing Final Python 3.0 Released Multi-Stage Continuous Integration ComponentOne Releases Studio Enterprise 2008 v3		TOP 5 ARTICLES No Top Articles.