How to explain the "deadlock" better?

Question

I am struggling to explain "deadlock" in threads in easy words, so please help. What could be the best example of "deadlock" (say, in Java), and how it does happen in steps and how to prevent it? But without getting into details too deep. I know that's like asking two opposite things, but still. If you have any previous concurrent programming training experience -- it would be superb!

Answer 1

Easiest way is for two different threads to try to get two locks in different orders:

thread 1:
lock(a)
lock(b)

thread2:
lock(b)
lock(a)

Assume that thread 1 gets lock A and then goes to sleep. Thread 2 gets lock B and then attempts to get lock A; since lock A is taken, thread 2 will be put to sleep until thread A is unlocked. Now thread 1 wakes back up and tries to get lock B and will be put to sleep.

For this case, there are a couple of ways to prevent it:

1. A thread should never need to hold two locks simultaneously.
2. If two locks must be held simultaneously, they must always be acquired in the same order (so in my example above, thread 2 would need to be modified to request lock A before requesting lock B).

Answer 2

  Thrd 1 --- Lock A        - atmpt lock on B -   
         \                /                   \
          \              /                     \           
           \            /                       \         
            --- Lock A /                         --- wait for lock on B

  Thrd 2--- Lock B         - atmpt lock on A -   
         \                /                   \
          \              /                     \           
           \            /                       \         
            --- Lock B /                         --- wait for lock on A

Thread 1 runs, Locks A, does some stuff, and gets interupted by Thread 2 which Locks B, does some stuff and gets interupted by Thread 1 which attempt to Lock B, but thread 2 has locked B so thread 1 waits, and is interiupted by Thread 2 which attempts tpo lock A, but thread 1 has lock on A so Thread 2 has to wait.

Both threads are waiting for the other thread to release a lock on a resource they are trying to get a lock on...

Deadlock

Answer 3

Deadlock is when two threads wait on each other, neither can proceed until the other does first, and so both are stuck.

Deadlocking requires at least 2 locks, and both threads have to contain code that takes locks and also waits for locks to be released.

Thread 1 has lock A and wants lock B, so it waits for lock B to be released.

Thread 2 has lock B and wants lock A, so it waits for lock A to be released.

Now you have a deadlock. Both threads a waiting for a lock, so neither is executing, so neither can release the lock that the other is waiting for.

Answer 4

Deadlock happens when you have 2 different resources that 2 different threads need to lock in order to use them. The threads lock them in the opposite order, so it becomes impossible for execution to continue until 1 of the threads backs down.

Wikipedia has a couple good real-life examples of deadlock.

Answer 5

A lock chain occurs when a worker is blocked by another worker. A cannot continue because of B. The chain can be longer: A is blocked by B, B is blocked by C, C is blocked by D.

A deadlock is when the lock chain forms a loop. A is blocked by B, B by C, C by A and the chain had formed a loop, no progress is possible.

The typical way of preventing deadlocks is to use lock hierachies: if locks are always aquired by every worker in the same order, then deadlocks are not possible because each blocking occurs between a worker than holds locks ranked X and waits for resources ranked Y, where X > Y always. A loop cannot form in this case, as it would require at least one worker to go against the hierarchy in order to close the loop. That how the theory goes, at least. In prcatice is very very hard to come up with realistic hierarchies (and no, address of resource does not work).

If deadlocks cannot be avoided (eg. database systems) then the solution is to have dedicated threads that check the deadlock chains in search of loops and kill one of the participants to free the loop.

Answer 6

I'd rather explain it in terms totally unrelated to computers since that's often the best way to get an idea across.

I have a five-year-old son and a three-year-old daughter. Both want to do the same colouring-in book.

The daughter grabs the pencils while the son grabs the book. Neither will relinquish what they have until they get the other.

That's deadlock. It doesn't get any simpler than that.

Your processes (or children) are stuck waiting for each other and will continue waiting indefinitely until some other superior process (like Dad) comes in and breaks the deadlock.

At least with the children, you can (sometimes) get one of them to see reason and relinquish their lock. This is not usually possible with computers since the processes are not doing anything except waiting for that resource (although sometimes children enter this state as well).

Following one rule will guarantee that deadlock cannot occur:

• Have all threads of execution allocate resources in the same order.

Following some extra rules will make your threads less likely to slow each other down but keep in mind that the above rule should take precedence over all others:

• Allocate resources only when you need them.
• Release them as soon as you're finished with them.

Answer 7

(Slightly over-simplified) There are two people, screwing nuts onto bolts.

The procedure (same for both) is:

1. Pick up a nut or a bolt
2. Pick up a bolt or a nut (whichever you don't already have)
3. Screw the nut onto the bolt
4. Place the finished assembly into the "Finished" pile.
5. if nuts and bolts remain, go to step 1

So what happens when there is just a nut and a bolt left? The first person picks up a nut, the second grabs a bolt. So far so good, but now they are stuck, each having a resource the other needs.

Without special instructions they will sit there deadlocked forever.

Or you could just show them this video

Answer 8

Dining philosophers - you have 4 people sitting at a table, and 4 chopsticks. You need 2 chopsticks to eat. Imagine each philosopher tries to eat as follows:

1. Pick up left chopstick.
2. Pick up right chopstick.
3. Eat.
4. Set right chopstick back.
5. Set left chopstick back.

Everyone does step 1. Now step 2 is impossible, since each person waits for the one on his right to drop the left, which they won't do. This is deadlock. If they just took turns then they could all eat, but instead they all starve.

Answer 9

Another good way to demonstrate a deadlock is with SQL Server.

Using transactions with different isolation levels, you can demonstrate how one transaction will wait indefinitely for a table which is locked by another transaction.

The plus here, is you can demonstrate it with SQL Management Studio. I've used this in the past to explain deadlocks to people whilst teaching "Introduction to SQL Server" level training courses.

Most participants have trouble with the theory, but it all (usually) becomes clear when they see it in action.

In short: Transaction A (which has not completed) takes an explicit table lock. A second Transaction B attempts to read from the table locked by Transaction A. Transaction B is deadlocked until Transaction A commits or is rolled back.

You could explain this in code fairly easily enough by creating two separate threads which, in turn, create the Transactions. Hope it helps.

Answer 10

Jack and Jill happens to want to make a sandwich at the same time. Both need a slice of bread, so they both goes to get the loaf of bread and a knife.

Jack gets the knife first, while Jill gets the loaf of bread first. Now Jack tries to find the loaf of bread and Jill tries to find the knife, but both find that what they need to finish the task is already in use. If they both decide to wait until what they need is no longer in use, they will wait for each other forever. Deadlock.

Answer 11

Usually the classes of concurrent programming explains deadlock by examples. I think that the problem of the Dining Philosophers will be a good example to use. You can develop this example in Java and explain the occurrence of deadlock when two philosophers holds a left fork and are waiting for the right fork. (or vice versa).

I learned a lot of concepts from concurrent programming using this examples implemented on Java.

Answer 12

Guffa's description is good.

The best way I've found to avoid deadlocks is to only lock around resources that are private to you, and to release the lock before you call anything that you do not have exclusive control over.

The only problem is that this may require you to shift from using locks for maintaing consistency to using compensating actions, but it's probably less likely to cause problems in the long run, anyway.

This article is good to read about this problem.

Answer 13

Sometimes a picture says more that a thousand words.