Към съдържанието
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;
    lock (first.Sync)
    {
        lock (second.Sync)
        {
            source.Stock -= qty;
            target.Stock += qty;
        }
    }
}
Стъпка по стъпка, с думи
  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. Ако не дойде, преводът се отказва и пуска своята.

lock чака вечно. Monitor.TryEnter(обект, 200) чака най-много 200 ms и връща false, ако не е успял, а Monitor.Exit пуска ключалката. (lock е съкратено от Monitor.Enter и Monitor.Exit.) Barrier(2) пуска двете нишки, щом и двете извикат SignalAndWait(), и може да се ползва пак.
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(); // всеки държи по една
        bool got = Monitor.TryEnter(target.Sync, 200);
        meet.SignalAndWait(); // двата опитаха (за примера)
        if (!got) return false; // чакал е твърде дълго
        try
        {
            source.Stock -= qty;
            target.Stock += qty;
            return true;
        }
        finally
        {
            Monitor.Exit(target.Sync);
        }
    }
}
var sofia = new Warehouse(1, "София", 500);
var plovdiv = new Warehouse(2, "Пловдив", 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: всеки превод чака другия" : "и двата превода минаха");
Console.WriteLine($"{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;
    lock (first.Sync)
    {
        lock (second.Sync)
        {
            source.Stock -= qty;
            target.Stock += qty;
        }
    }
}

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

var sofia = new Warehouse(1, "София", 5000);
var plovdiv = new Warehouse(2, "Пловдив", 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($"Общо: {sofia.Stock + plovdiv.Stock}");
Изход
София: 4000, Пловдив: 4000
Общо: 8000

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

Пробвай

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

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

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}, после {second.Name}");
}


var sofia = new Warehouse(1, "София", 0);
var plovdiv = new Warehouse(2, "Пловдив", 0);
var 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)
    {
        lock (source.Sync)
        {
            if (Monitor.TryEnter(target.Sync))
            {
                try
                {
                    source.Stock -= qty;
                    target.Stock += qty;
                    return;
                }
                finally
                {
                    Monitor.Exit(target.Sync);
                }
            }
        }
        // пусни всичко и опитай пак след малко
        Thread.Sleep(Random.Shared.Next(3));
    }
}

Със същите два превода (по 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-ват обещанието една на друга, чакат вечно, а програмата просто свършва, без да отпечата нищо.

Упражнение

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

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

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

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

Още задачи

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

Тест

Провери се

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

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