Deadlock — slēdzeņu secības mīkla
Pārkārto, kādā secībā pavedieni ņem slēdzenes, lai neviens negaidītu mūžīgi. Mīkla par globālās slēdzeņu secības likumu.
Pārkārto katru pavedienu tā, lai neviens negaidītu otru mūžīgi.
- 🔒 A
- 🔒 B
- 🔒 B
- 🔒 A
Kā spēlēt
- Katra rinda ir pavediens, un žetoni ir slēdzenes, ko tas ņem no kreisās uz labo.
- Velc žetonu (vai izmanto bultiņas), lai mainītu secību, kādā pavediens ņem slēdzenes.
- Ja divi pavedieni ņem to pašu pāri pretējā secībā, tie var iesalt uz visiem laikiem. Risinājums ir viena globāla secība visiem — nospied Palaist, lai pārbaudītu.
Kā tas darbojas
Katra rinda ir pavediens, un katrs žetons ir slēdzene, ko tas ņem no kreisās uz labo. Ja divi pavedieni ņem to pašu pāri pretējā secībā, pastāv sapinums, kurā katrs tur vienu un gaida otru — un neviens vairs nekustas. Nospied Palaist: gaidīšanas grafs tiek pārbaudīts uz ciklu, un vainīgās slēdzenes iedegas sarkanas. Risinājums ir īsto kodu bāzu likums: izvēlēties vienu globālu slēdzeņu secību un ievērot to visur.
Mācību mīkla. Tā modelē hold-and-wait ciklus — to strupceļa nosacījumu, ko var novērst ar dizainu; īstās sistēmās ir arī noildzes, bezslēdzeņu struktūras un jādomā par livelock.
Biežāk uzdotie jautājumi
Kas šeit patiesībā rada strupceļu?
Cikls gaidīšanas grafā. Ja pavediens 1 tur A un grib B, bet pavediens 2 tur B un grib A, abi gaida mūžīgi. Spēle uzzīmē tieši šo ciklu.
Kāpēc slēdzeņu sakārtošana palīdz?
Ja visi pavedieni ņem slēdzenes vienā globālā secībā, cikls nav iespējams: pavediens var gaidīt tikai slēdzeni, kas ir vēlāk par jau turētajām, tāpēc grafs paliek aciklisks.
Vai īstos strupceļus meklē tāpat?
Cikla pārbaude ir tā pati ideja, ko izmanto slēdzeņu secības inversijas detektori, piemēram, ThreadSanitizer. Īstie rīki novēro secību izpildes laikā; te redzi visu grafu uzreiz.