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

Deadlock

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

Проблем

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

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

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

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

Идеята

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

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

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

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

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

Виж го

Кръгът

def transfer(source, target, qty):
    # общ ред: първо по-малкото id
    first, second = sorted((source, target),
                           key=lambda w: w.id)
    with first.lock:
        with second.lock:
            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. Ако не дойде, преводът се отказва и пуска своята.

with lock: чака вечно. lock.acquire(timeout=0.2) чака най-много 0,2 секунди и връща False, ако не е успял, а release() пуска ключалката. threading.Barrier(2) пуска двете нишки, щом и двете извикат wait(), и може да се ползва пак.
class Warehouse:
    def __init__(self, id, name, stock):
        self.id = id
        self.name = name
        self.stock = stock
        self.lock = threading.Lock()
def transfer(source, target, qty, meet):
    with source.lock:
        meet.wait()  # всеки държи по една
        got = target.lock.acquire(timeout=0.2)
        meet.wait()  # двата опитаха (за примера)
        if not got:
            return False  # чакал е твърде дълго
        try:
            source.stock -= qty
            target.stock += qty
            return True
        finally:
            target.lock.release()
sofia = Warehouse(1, "София", 500)
plovdiv = Warehouse(2, "Пловдив", 300)
meet = threading.Barrier(2)
done = [None, None]




def run(k, source, target, qty):
    done[k] = transfer(source, target, qty, meet)




threads = [threading.Thread(target=run, args=(0, sofia, plovdiv, 5)),
           threading.Thread(target=run, args=(1, plovdiv, sofia, 3))]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print("deadlock: всеки превод чака другия" if not any(done) else "и двата превода минаха")
print(f"{sofia.name}: {sofia.stock}, {plovdiv.name}: {plovdiv.stock}")
Изход
deadlock: всеки превод чака другия
София: 500, Пловдив: 300

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

Идеята

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

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

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

def transfer(source, target, qty):
    # общ ред: първо по-малкото id
    first, second = sorted((source, target),
                           key=lambda w: w.id)
    with first.lock:
        with second.lock:
            source.stock -= qty
            target.stock += qty

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

sofia = Warehouse(1, "София", 5000)
plovdiv = Warehouse(2, "Пловдив", 3000)




def many(source, target, qty):
    for _ in range(1000):
        transfer(source, target, qty)




threads = [threading.Thread(target=many, args=(sofia, plovdiv, 2)),
           threading.Thread(target=many, args=(plovdiv, sofia, 1))]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print(f"{sofia.name}: {sofia.stock}, {plovdiv.name}: {plovdiv.stock}")
print("Общо:", sofia.stock + plovdiv.stock)
Изход
София: 4000, Пловдив: 4000
Общо: 8000
sorted с key=lambda w: w.id подрежда двата склада по id: first е винаги този с по-малкото. with first.lock: и вложеното with second.lock: ги заключват в този ред.

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

Пробвай

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

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

def transfer(source, target):
    first, second = sorted((source, target), key=lambda w: w.id)
    print(f"{first.name}, после {second.name}")




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

Пробвай

Попълни

По какво подрежда sorted двата склада?
first, second = sorted((source, target), key=lambda w: )

Пробвай

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

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

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

Виж го

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

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

def transfer(source, target, qty):
    while True:
        with source.lock:
            if target.lock.acquire(blocking=False):
                try:
                    source.stock -= qty
                    target.stock += qty
                    return
                finally:
                    target.lock.release()
        # пусни всичко и опитай пак след малко
        time.sleep(random.random() / 1000)

Със същите два превода (по 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. Ако обектите нямат номер, по какво друго може да се подредят? (Подсказка: id(), и какво става, ако два обекта имат еднакъв.)

Тест

Провери се

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

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