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!

Goon

Possible duplicate of What is a deadlock? – Telephonic

Answer 1

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.

Swimming

best example to understand the concept..:) – Coralyn

This Should be the formal definition of deadlock. Simple, easy , neat and clean and best example I have ever seen – Margarethe

Why is it that Jack's can't get the loaf from Jill, do his job, and give the rest of the loaf to Jill so that he can also do his work? I mean computationally is this an unsolvable problem? – Cummins

@Nishant: Yes, resources could be negotiated, but it's not trivial. Basically Jack would need John to oversee the use of Jack's resources (and Jill needs Jane), and answer question like "is Jack really using that right now" while Jack is busy. – Swimming

Answer 2

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

Matazzoni

Answer 3

  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 interrupted by Thread 2 which Locks B, does some stuff and gets interrupted by Thread 1 which attempt to Lock B, but thread 2 has locked B so thread 1 waits, and is interrupted by Thread 2 which attempts to 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

Icj

Answer 4

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.

Lonne

Very under rated answer. This captures the essense of the original answer plus also explains the what is it and the reason why it is the way it is. Excellent. However, when you say "At least with the children, you can (sometimes) get one of them to see reason", can this be done programtically? Something like a while loop or something I dont know ... Just a newbie question. – Cummins

@Nishant, unless the threads are using something like a timed trylock, no. Using a "real" lock is akin to the child sticking its fingers in its ears and loudly going "la la la la la ..." :-) There are sometimes ways to force a thread of execution to release locks but this may leave the data it was protecting in a inconsistent state. Far better to engineer you program so that deadlocks are impossible. – Lonne

Answer 5

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.

Patriotism

Answer 6

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.

Phonetician

Answer 7

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.

Lawford

Answer 8

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.

Admeasure

Answer 9

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.

Viewable

Answer 10

(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

Eriha

Answer 11

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.

Super

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.

Derogate

Answer 13

Imagine you and your girlfriend quarrelled over who should open the door in order to leave the house.The person who apologises will open the door. She is waiting for you to apologise, you are waiting for her to apologise which results in the couple never leaving the house as both refuse to apologise.

Montenegro

Answer 14

Imagine a criminal holding a hostage and asking for a ransom. You show up with a suitcase full of money.

The criminal will never release the hostage before he gets the money. You will never release the money before you get the hostage. Deadlock.

---

The analogy here are:

• You and the criminal are the threads
• The suitcase full of money and the hostage are the resources

Ecto

Answer 15

Sample1:

I promised never do promises

Sample2:

Talking with genie of the lamp: My wish is that you never make wishes comes true

Sample3:

recruiter: I will hire you if you explain deadlock.

candidate: If you hire me I will explain what deadlock is about

Barograph