Skip to content
wannacode

Deadlock

In short: A deadlock is a state in which two threads each hold one lock and wait for the other forever; a common locking order makes it impossible.

Problem

The night the warehouses stopped

The shop has two warehouses: Sofia and Plovdiv. When one runs out of headphones, a system moves stock from the other. Every transfer locks both warehouses so that no items are lost, as in the lesson on locks.

One night at 3:12 two transfers start at once: 5 items from Sofia to Plovdiv and 3 from Plovdiv to Sofia. The program stops. The processor is at 0%, there is no error in the log, and the threads just stand and wait. Until morning not one transfer goes through, and the orders in both warehouses pile up.

In the lesson on threads you saw the same with the printer and the scanner. Here is why it happens and how to make it impossible.

The idea

Each holds one and waits for the other

A transfer first locks the warehouse it moves from, then the warehouse it moves to:

  • transfer 1 (Sofia → Plovdiv) takes the lock of Sofia;
  • at the same moment transfer 2 (Plovdiv → Sofia) takes the lock of Plovdiv;
  • transfer 1 wants the lock of Plovdiv: transfer 2 holds it, so it waits;
  • transfer 2 wants the lock of Sofia: transfer 1 holds it, so it waits.

Each waits for the other to let go, and nobody lets go until it gets what it wants. The waiting makes a circle. This is a deadlock: the threads do not make a mistake and do not crash, they just stop forever.

The worst part is that it happens rarely. The two transfers have to take their first lock at almost the same moment. So it passes a thousand times in testing and stops at 3:12 at night.

See it

The circle

static void Transfer(Warehouse source, Warehouse target,
                     int qty)
{
    // one order: the smaller id first
    var first = source.Id < target.Id ? source : target;
    var second = source.Id < target.Id ? target : source;
    lock (first.Sync)
    {
        lock (second.Sync)
        {
            source.Stock -= qty;
            target.Stock += qty;
        }
    }
}
Step by step, in words
  1. Two transfers at the same time. T1 moves 5 items from Sofia to Plovdiv, T2 moves 3 back. Each locks first the warehouse it takes from.
  2. T1 takes the lock of Sofia.
  3. At the same moment T2 takes the lock of Plovdiv.
  4. The barrier lets them go on only when both hold their first lock. It is here so that the bad moment happens on every run.
  5. T1 waits for the lock of Plovdiv, which T2 holds. T2 waits for the lock of Sofia, which T1 holds. A circle: nobody lets go.
  6. After 200 ms both give up: deadlock. Without the timeout they would wait forever and the program would hang. Stock: 500 and 300.
  7. The fix: one order for everyone. First the lock of the warehouse with the smaller id: Sofia (1), then Plovdiv (2), whatever the direction.
  8. Both start with Sofia. T1 gets the lock; T2 waits, but holds nothing.
  9. T1 takes Plovdiv too, moves 5 items and lets go of both locks.
  10. Now T2 takes Sofia, then Plovdiv, and moves 3 back.
  11. Both transfers went through: 498 and 302. With one order nobody holds a lock while waiting for one held by somebody who waits for them: no circle.

So that you see the bad moment on every run, the program makes it happen on purpose. The barrier meet stops each transfer until both have reached it: so both already hold their first lock when they want the second. The second barrier holds them until both have tried. Without it one of them could get the lock released by the other, and the output would depend on timing.

The second lock is waited for with a timeout: at most 200 ms. If it does not come, the transfer gives up and releases its own.

lock waits forever. Monitor.TryEnter(object, 200) waits at most 200 ms and returns false if it did not succeed, and Monitor.Exit releases the lock. (lock is short for Monitor.Enter and Monitor.Exit.) Barrier(2) lets both threads go as soon as both have called SignalAndWait(), and can be used again.
class Warehouse(int id, string name, int stock)
{
    public int Id { get; } = id;
    public string Name { get; } = name;
    public int Stock { get; set; } = stock;
    public object Sync { get; } = new object();
}
static bool Transfer(Warehouse source, Warehouse target,
                     int qty, Barrier meet)
{
    lock (source.Sync)
    {
        meet.SignalAndWait(); // both hold one lock
        bool got = Monitor.TryEnter(target.Sync, 200);
        meet.SignalAndWait(); // both tried (demo only)
        if (!got) return false; // waited too long
        try
        {
            source.Stock -= qty;
            target.Stock += qty;
            return true;
        }
        finally
        {
            Monitor.Exit(target.Sync);
        }
    }
}
var sofia = new Warehouse(1, "Sofia", 500);
var plovdiv = new Warehouse(2, "Plovdiv", 300);
var meet = new Barrier(2);
var done = new bool[2];
var first = new Thread(() => done[0] = Transfer(sofia, plovdiv, 5, meet));
var second = new Thread(() => done[1] = Transfer(plovdiv, sofia, 3, meet));
first.Start();
second.Start();
first.Join();
second.Join();
Console.WriteLine(!done[0] && !done[1] ? "deadlock: each transfer waits for the other" : "both transfers went through");
Console.WriteLine($"{sofia.Name}: {sofia.Stock}, {plovdiv.Name}: {plovdiv.Stock}");
Output
deadlock: each transfer waits for the other
Sofia: 500, Plovdiv: 300

Without the timeout the program would hang and never print anything. The timeout does not fix the deadlock, it catches it: the transfer knows it did not go through and can try again or raise an alarm.

The idea

One order for everyone

The circle closes because the two transfers lock in a different order: one Sofia then Plovdiv, the other the other way round. The fix is for everyone to lock in the same order, whatever the direction of the transfer. For example by the warehouse number: the smaller id first.

Then both transfers start with Sofia. Whoever gets its lock goes on to Plovdiv. The other still waits on the first lock and holds nothing, so it blocks nobody. A circle cannot close: everyone waits only for a lock with a larger id than the ones they already hold.

static void Transfer(Warehouse source, Warehouse target,
                     int qty)
{
    // one order: the smaller id first
    var first = source.Id < target.Id ? source : target;
    var second = source.Id < target.Id ? target : source;
    lock (first.Sync)
    {
        lock (second.Sync)
        {
            source.Stock -= qty;
            target.Stock += qty;
        }
    }
}

A thousand transfers of 2 items in one direction and a thousand of 1 in the other, at the same time:

var sofia = new Warehouse(1, "Sofia", 5000);
var plovdiv = new Warehouse(2, "Plovdiv", 3000);
var there = new Thread(() =>
{
    for (int i = 0; i < 1000; i++) Transfer(sofia, plovdiv, 2);
});
var back = new Thread(() =>
{
    for (int i = 0; i < 1000; i++) Transfer(plovdiv, sofia, 1);
});
there.Start();
back.Start();
there.Join();
back.Join();
Console.WriteLine($"{sofia.Name}: {sofia.Stock}, {plovdiv.Name}: {plovdiv.Stock}");
Console.WriteLine($"Total: {sofia.Stock + plovdiv.Stock}");
Output
Sofia: 4000, Plovdiv: 4000
Total: 8000

The stock is exact on every run, and the total is 8000, as at the start. The locks protect the items, and the order keeps the program from stopping.

Try it

Predict the output

Three warehouses: Sofia (1), Plovdiv (2), Varna (3). The function only prints in what order it would lock. What will it print?

static void Transfer(Warehouse source, Warehouse target)
{
    var first = source.Id < target.Id ? source : target;
    var second = source.Id < target.Id ? target : source;
    Console.WriteLine($"{first.Name}, then {second.Name}");
}


var sofia = new Warehouse(1, "Sofia", 0);
var plovdiv = new Warehouse(2, "Plovdiv", 0);
var varna = new Warehouse(3, "Varna", 0);
Transfer(plovdiv, sofia);
Transfer(sofia, varna);
Transfer(varna, plovdiv);
Answer

Try it

Fill in

first is the warehouse with the smaller id. Which one is second?
var first = source.Id < target.Id ? source : target;
var second = source.Id < target.Id ?  : source;

Try it

Find the bug

The transfers already lock by id, and for weeks there is no problem. Then someone adds a nightly audit that adds up both warehouses. Since then the program sometimes stops again. Which line is the bug on?

Pick the line with the bug.

See it

When an order is not possible: try and back off

Sometimes you do not know in advance which lock you will need. Then instead of an order you use try and back off (tryLock with backoff): take the first, try the second without waiting. If it does not work, release everything, wait a little and start again. Nobody holds a lock while waiting, so there is no circle.

static void Transfer(Warehouse source, Warehouse target, int qty)
{
    while (true)
    {
        lock (source.Sync)
        {
            if (Monitor.TryEnter(target.Sync))
            {
                try
                {
                    source.Stock -= qty;
                    target.Stock += qty;
                    return;
                }
                finally
                {
                    Monitor.Exit(target.Sync);
                }
            }
        }
        // release everything and try again a bit later
        Thread.Sleep(Random.Shared.Next(3));
    }
}

With the same two transfers (300 in each direction) the result is exact again:

Output
Sofia: 4700, Plovdiv: 3300
Total: 8000

The wait is random, and that matters. If both transfers back off for the same time, they can clash again and again in one rhythm: both are working, and nobody makes progress. This is called livelock. The random wait breaks the rhythm.

More precisely, if you are curious

The four Coffman conditions. A deadlock happens only if four things hold at once:

  1. mutual exclusion: a lock can be held by only one;
  2. hold and wait: a thread holds one lock while it waits for another;
  3. no preemption: nobody can take a lock away by force;
  4. circular wait: the waiting makes a circle.

Remove one and a deadlock cannot happen. One order removes the circle (4). Backing off removes "hold and wait" (2). The atomic operations and immutable objects from the previous lesson often remove the lock itself (1).

Databases deal with it in a third way. They look for the circle themselves and kill one of the transactions with a "deadlock detected" error. So code that works with a database has to be ready to repeat the transaction.

How it is in the other languages: ReentrantLock.tryLock(time) in Java (synchronized has no timeout); Monitor.TryEnter(object, time) in C# (lock has no timeout); Lock.acquire(timeout=…) in Python; in JavaScript there are locks only between Workers, written with Atomics.wait with a timeout. In async code on one thread there are no locks, but a circle is still possible: two functions that await each other's promise wait forever, and the program simply ends without printing anything.

Exercise

Three wallets in a circle

Solve the task in your editor.

Three wallets with 1000 € each and three threads. The first moves 5 € from wallet 1 to wallet 2, the second from 2 to 3, the third from 3 to 1, each 1000 times. That is a circle: without one order the program gets stuck sooner or later. Write Transfer so that it cannot get stuck, and print the wallets and the total:

Output
Wallet 1: 1000 €
Wallet 2: 1000 €
Wallet 3: 1000 €
Total: 3000 €

More tasks

  • Catch it. Remove the order and put a timeout on the second lock. Count how many transfers gave up and retry them until all have gone through.
  • The audit. Add a thread that adds up the three wallets 1000 times under their locks. The total must always be 3000 €. In what order does it lock?
  • Without an id. If the objects have no number, what else can they be ordered by? (Hint: RuntimeHelpers.GetHashCode, and what happens if two objects have the same one.)

Test

Check yourself

1. When do two threads get stuck in a deadlock?
2. All transfers lock the warehouses by id, from the smaller to the larger. Can three transfers Sofia → Plovdiv, Plovdiv → Varna and Varna → Sofia get stuck?
3. Why does the deadlock program in the lesson not hang?
4. Two transfers give up on failure, wait 1 ms and try again. Both clash again, over and over. What is this called and how do you fix it?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·