Deadlock — užraktų eiliškumo galvosūkis
Pertvarkyk, kokia tvarka gijos ima užraktus, kad nė viena nelauktų amžinai. Galvosūkis apie globalios užraktų tvarkos taisyklę.
Pertvarkyk kiekvieną giją, kad nė dvi nelauktų viena kitos amžinai.
- 🔒 A
- 🔒 B
- 🔒 B
- 🔒 A
Kaip žaisti
- Kiekviena eilutė — gija, o žetonai — užraktai, kuriuos ji ima iš kairės į dešinę.
- Vilk žetoną (arba naudok rodykles), kad pakeistum užraktų ėmimo tvarką.
- Jei dvi gijos ima tą pačią porą priešinga tvarka, jos gali užstrigti amžiams. Sprendimas — viena globali tvarka visiems. Paspausk Vykdyti patikrinti.
Kaip tai veikia
Kiekviena eilutė yra gija, o kiekvienas žetonas — užraktas, kurį ji ima iš kairės į dešinę. Jei dvi gijos ima tą pačią porą priešinga tvarka, egzistuoja persipynimas, kai kiekviena laiko vieną ir laukia kitos — ir nė viena nebejuda. Paspausk Vykdyti: laukimo grafas tikrinamas dėl ciklo, o kalti užraktai užsidega raudonai. Sprendimas — tikrų kodo bazių taisyklė: pasirinkti vieną globalią užraktų tvarką ir jos laikytis visur.
Mokomasis galvosūkis. Jis modeliuoja hold-and-wait ciklus — aklavietės sąlygą, kurią galima pašalinti projektuojant; tikros sistemos dar turi laukimo laikus, be užraktų veikiančias struktūras ir turi galvoti apie livelock.
Dažnai užduodami klausimai
Kas iš tikrųjų sukelia aklavietę?
Ciklas laukimo grafe. Jei gija 1 laiko A ir nori B, o gija 2 laiko B ir nori A, abi laukia amžinai. Žaidimas nupiešia būtent tą ciklą.
Kodėl užraktų rikiavimas išsprendžia?
Jei visos gijos ima užraktus ta pačia globalia tvarka, ciklas neįmanomas: gija gali laukti tik užrakto, esančio vėliau nei jau laikomi, tad grafas lieka aciklinis.
Ar tikros aklavietės aptinkamos taip pat?
Ciklo tikrinimas — ta pati idėja, kurią naudoja užraktų tvarkos inversijos detektoriai, pvz., ThreadSanitizer. Tikri įrankiai stebi tvarką vykdymo metu; čia matai visą grafą iškart.