Към съдържанието
wannacode

Deadlock

Накратко: Deadlock е състояние, в което две нишки държат по една ключалка и всяка чака другата завинаги; общ ред на заключване го прави невъзможен.

Проблем

Нощта, в която складовете спряха

Магазинът има два склада: София и Пловдив. Когато в единия свършат слушалки, система мести стока от другия. Всеки превод заключва двата склада, за да не се загубят бройки, както в урока за ключалките.

Една нощ в 3:12 два превода тръгват наведнъж: 5 бройки от София към Пловдив и 3 от Пловдив към София. Програмата спира. Процесорът е на 0%, грешка в лога няма, а нишките стоят и чакат. До сутринта нито един превод не минава, а поръчките в двата склада се трупат.

В урока за нишките видя същото с принтера и скенера. Тук е защо става и как се прави невъзможно.

Идеята

Всеки държи едно и чака друго

Преводът заключва първо склада, откъдето мести, после склада, където мести:

  • превод 1 (София → Пловдив) взима ключа на София;
  • превод 2 (Пловдив → София) в същия момент взима ключа на Пловдив;
  • превод 1 иска ключа на Пловдив: държи го превод 2, затова чака;
  • превод 2 иска ключа на София: държи го превод 1, затова чака.

Всеки чака другия да пусне, а никой не пуска, докато не получи своето. Чакането прави кръг. Това е deadlock (мъртва хватка): нишките не грешат и не падат, а просто спират завинаги.

Най-лошото е, че става рядко. Двата превода трябва да вземат първата си ключалка почти в един и същ момент. Затова минава хиляди пъти на теста и спира в 3:12 през нощта.

Виж го

Кръгът

static void transfer(Warehouse source, Warehouse target,
                     int qty) {
    // общ ред: първо по-малкото id
    var first = source.id < target.id ? source : target;
    var second = source.id < target.id ? target : source;
    first.lock.lock();
    try {
        second.lock.lock();
        try {
            source.stock -= qty;
            target.stock += qty;
        } finally {
            second.lock.unlock();
        }
    } finally {
        first.lock.unlock();
    }
}
Стъпка по стъпка, с думи
  1. Два превода наведнъж. T1 мести 5 бройки от София в Пловдив, T2 мести 3 обратно. Всеки заключва първо склада, от който взима.
  2. T1 взима ключа на София.
  3. В същия момент T2 взима ключа на Пловдив.
  4. Бариерата ги пуска нататък чак когато и двата държат първия си ключ. Тя е тук, за да се случва лошият момент при всяко пускане.
  5. T1 чака ключа на Пловдив, който държи T2. T2 чака ключа на София, който държи T1. Кръг: никой не пуска.
  6. След 200 ms и двата се отказват: deadlock. Без таймаута щяха да чакат вечно и програмата щеше да увисне. Наличност: 500 и 300.
  7. Поправката: един ред за всички. Първо ключът на склада с по-малкото id: София (1), после Пловдив (2), в каквато и посока да е преводът.
  8. И двата започват от София. T1 взима ключа, T2 чака, но не държи нищо.
  9. T1 взима и Пловдив, мести 5 бройки и пуска двата ключа.
  10. Сега T2 взима София, после Пловдив, и мести 3 обратно.
  11. И двата превода минаха: 498 и 302. С един ред никой не държи ключ, докато чака ключ на някого, който чака него: кръг няма.

За да видиш лошия момент при всяко пускане, програмата го прави нарочно. Бариерата meet спира всеки превод, докато и двата не стигнат до нея: така и двата вече държат първия си ключ, когато искат втория. Втората бариера ги държи, докато и двата са опитали. Без нея единият можеше да получи ключа, пуснат от другия, и изходът щеше да зависи от времето.

Втората ключалка се чака с таймаут: най-много 200 ms. Ако не дойде, преводът се отказва и пуска своята.

ReentrantLock (от java.util.concurrent.locks) е ключалка като synchronized, но с повече методи. tryLock(200, MILLISECONDS) чака най-много 200 ms и връща false, ако не е успял. CyclicBarrier(2) пуска двете нишки, щом и двете извикат await(), и може да се ползва пак.
class Warehouse {
    final int id;
    final String name;
    final ReentrantLock lock = new ReentrantLock();
    int stock;


    Warehouse(int id, String name, int stock) {
        this.id = id;
        this.name = name;
        this.stock = stock;
    }
}
static boolean transfer(Warehouse source,
        Warehouse target, int qty, CyclicBarrier meet)
        throws Exception {
    source.lock.lock();
    try {
        meet.await(); // всеки държи по една
        var got = target.lock.tryLock(200, MILLISECONDS);
        meet.await(); // двата опитаха (за примера)
        if (!got) return false; // чакал е твърде дълго
        try {
            source.stock -= qty;
            target.stock += qty;
            return true;
        } finally {
            target.lock.unlock();
        }
    } finally {
        source.lock.unlock();
    }
}
Warehouse sofia = new Warehouse(1, "София", 500);
Warehouse plovdiv = new Warehouse(2, "Пловдив", 300);
CyclicBarrier meet = new CyclicBarrier(2);
boolean[] done = new boolean[2];
Thread first = new Thread(() -> done[0] = run(() -> transfer(sofia, plovdiv, 5, meet)));
Thread second = new Thread(() -> done[1] = run(() -> transfer(plovdiv, sofia, 3, meet)));
first.start();
second.start();
first.join();
second.join();
if (!done[0] && !done[1]) System.out.println("deadlock: всеки превод чака другия");
else System.out.println("и двата превода минаха");
System.out.println(sofia.name + ": " + sofia.stock + ", " + plovdiv.name + ": " + plovdiv.stock);
Изход
deadlock: всеки превод чака другия
София: 500, Пловдив: 300

Без таймаута програмата щеше да увисне и никога да не отпечата нищо. Таймаутът не оправя deadlock-а, а го хваща: преводът знае, че не е минал, и може да опита пак или да вдигне тревога.

Идеята

Един ред за всички

Кръгът се затваря, защото двата превода заключват в различен ред: единият София, после Пловдив, другият обратно. Поправката е всички да заключват в един и същ ред, независимо накъде мести преводът. Например по номера на склада: първо по-малкото id.

Тогава и двата превода започват от София. Който вземе ключа ѝ, продължава към Пловдив. Другият чака още на първия ключ и не държи нищо, затова никого не спира. Кръг не може да се затвори: всеки чака само ключ с по-голямо id от тези, които вече държи.

static void transfer(Warehouse source, Warehouse target,
                     int qty) {
    // общ ред: първо по-малкото id
    var first = source.id < target.id ? source : target;
    var second = source.id < target.id ? target : source;
    first.lock.lock();
    try {
        second.lock.lock();
        try {
            source.stock -= qty;
            target.stock += qty;
        } finally {
            second.lock.unlock();
        }
    } finally {
        first.lock.unlock();
    }
}

Хиляда превода по 2 бройки в едната посока и хиляда по 1 в другата, едновременно:

Warehouse sofia = new Warehouse(1, "София", 5000);
Warehouse plovdiv = new Warehouse(2, "Пловдив", 3000);
Thread there = new Thread(() -> {
    for (int i = 0; i < 1000; i++) transfer(sofia, plovdiv, 2);
});
Thread back = new Thread(() -> {
    for (int i = 0; i < 1000; i++) transfer(plovdiv, sofia, 1);
});
there.start();
back.start();
there.join();
back.join();
System.out.println(sofia.name + ": " + sofia.stock + ", " + plovdiv.name + ": " + plovdiv.stock);
System.out.println("Общо: " + (sofia.stock + plovdiv.stock));
Изход
София: 4000, Пловдив: 4000
Общо: 8000

Наличностите са точни при всяко пускане, а сборът е 8000, колкото в началото. Ключалките пазят бройките, а редът пази програмата да не спре.

Пробвай

Предвиди изхода

Три склада: София (1), Пловдив (2), Варна (3). Функцията само печата в какъв ред би заключила. Какво ще отпечата?

static void transfer(Warehouse source, Warehouse target) {
    Warehouse first = source.id < target.id ? source : target;
    Warehouse second = source.id < target.id ? target : source;
    System.out.println(first.name + ", после " + second.name);
}


Warehouse sofia = new Warehouse(1, "София", 0);
Warehouse plovdiv = new Warehouse(2, "Пловдив", 0);
Warehouse varna = new Warehouse(3, "Варна", 0);
transfer(plovdiv, sofia);
transfer(sofia, varna);
transfer(varna, plovdiv);
Отговор

Пробвай

Попълни

first е складът с по-малкото id. Кой е second?
var first = source.id < target.id ? source : target;
var second = source.id < target.id ?  : source;

Пробвай

Намери грешката

Преводите вече заключват по id и седмици наред няма проблем. После някой добавя нощна ревизия, която сумира двата склада. От тогава програмата пак спира понякога. На кой ред е грешката?

Избери реда с грешката.

Виж го

Когато редът не е възможен: опитай и отстъпи

Понякога не знаеш предварително коя ключалка ще ти трябва. Тогава вместо ред се ползва опитай и отстъпи (tryLock with backoff): вземи първата, опитай втората без чакане. Ако не стане, пусни всичко, изчакай малко и започни отначало. Никой не държи ключ, докато чака, затова кръг няма.

static void transfer(Warehouse source, Warehouse target, int qty) {
    while (true) {
        source.lock.lock();
        try {
            if (target.lock.tryLock()) {
                try {
                    source.stock -= qty;
                    target.stock += qty;
                    return;
                } finally {
                    target.lock.unlock();
                }
            }
        } finally {
            source.lock.unlock();
        }
        // пусни всичко и опитай пак след малко
        LockSupport.parkNanos(ThreadLocalRandom.current().nextInt(2_000_000));
    }
}

Със същите два превода (по 300 във всяка посока) резултатът пак е точен:

Изход
София: 4700, Пловдив: 3300
Общо: 8000

Чакането е случайно, и това е важно. Ако двата превода отстъпват за едно и също време, могат да се блъскат отново и отново в един ритъм: и двата работят, а никой не напредва. Това се казва livelock. Случайното чакане разваля ритъма.

По-точно, за любопитните

Четирите условия на Coffman. Deadlock става само ако са изпълнени четири неща наведнъж:

  1. взаимно изключване: ключалката може да е само у един;
  2. държи и чака: нишката държи една ключалка, докато чака друга;
  3. без отнемане: никой не може да вземе ключалката насила;
  4. кръгово чакане: чакането прави кръг.

Махни едно и deadlock не може да стане. Общият ред маха кръга (4). Отстъпването маха „държи и чака“ (2). Атомарните операции и неизменимите обекти от предишния урок често махат самата ключалка (1).

Базите данни се справят по трети начин. Те търсят кръга сами и убиват едната транзакция с грешка „deadlock detected“. Затова кодът, който работи с база, трябва да е готов да повтори транзакцията.

Как е в другите езици: ReentrantLock.tryLock(време) в Java (synchronized няма таймаут); Monitor.TryEnter(обект, време) в C# (lock няма таймаут); Lock.acquire(timeout=…) в Python; в JavaScript ключалки има само между Worker-и, написани с Atomics.wait с таймаут. В async код в една нишка ключалки няма, но кръг пак е възможен: две функции, които await-ват обещанието една на друга, чакат вечно, а програмата просто свършва, без да отпечата нищо.

В Java 21 виртуалните нишки (Thread.ofVirtual()) са евтини и могат да са милиони, но deadlock-ът при тях е същият: правилата за реда важат и там.

Упражнение

Три портфейла в кръг

Реши задачата в редактора си.

Три портфейла с по 1000 € и три нишки. Първата мести по 5 € от портфейл 1 в портфейл 2, втората от 2 в 3, третата от 3 в 1, всяка по 1000 пъти. Това е кръг: без общ ред програмата заседва рано или късно. Напиши transfer така, че да не може да заседне, и отпечатай портфейлите и сбора:

Изход
Портфейл 1: 1000 €
Портфейл 2: 1000 €
Портфейл 3: 1000 €
Общо: 3000 €

Още задачи

  • Хвани го. Махни реда и сложи таймаут на втората ключалка. Брой колко превода са се отказали и ги опитай пак, докато минат всички.
  • Ревизията. Добави нишка, която 1000 пъти сумира трите портфейла под ключалките им. Сборът трябва да е винаги 3000 €. В какъв ред заключва тя?
  • Без id. Ако обектите нямат номер, по какво друго може да се подредят? (Подсказка: System.identityHashCode, и какво става, ако два обекта имат еднакъв.)

Тест

Провери се

1. Кога две нишки заседват в deadlock?
2. Всички преводи заключват складовете по id, от по-малкото към по-голямото. Могат ли три превода София → Пловдив, Пловдив → Варна и Варна → София да заседнат?
3. Защо програмата с deadlock в урока не увисва?
4. Два превода се отказват при неуспех, чакат 1 ms и опитват пак. И двата пак се блъскат, отново и отново. Как се казва това и как се оправя?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·