Deadlock
A HupWiki-ből...
Folyamatok együttműködésének leírásakor használt szakkifejezés
Jelentése:
A deadlock (holtpont) az az állapot, amely akkor következhet be, amikor két (vagy több) folyamat egyidejűleg verseng erőforrásokért, és egymást kölcsönösen blokkolják. Ha 2 folyamat közül egyik sem tud továbblépni, mert mindkettőnek éppen arra az erőforrásra lenne szüksége, amit a másik foglal: ez a holtpont helyzet.
Példa:
Tételezzük fel, hogy egy taszk zárolni akarja az első runqueue-t, majd utána a másodikat. Közben egy másik taszk zárolni akarja a második runqueue-t, majd utána zárolni szeretné az elsőt. Tegyük fel, hogy az első taszk sikeresen zárolta az első runqueue-t, miközben ezzel egy időben a második taszk szintén sikeresen zárolta a második runqueue-t. Most, az első taszk megpróbálja zárolni a második runqueue-t, a második taszk pedig az elsőt. Egyik taszk sem fog sikerrel járni, mert a másik taszk már tartja a zárat. Mindkét taszk a végteleségig fog várni arra, hogy a másik elengedje a runqueue-t, de ez nem fog bekövetkezni.
Másik példa: (az ún. "étkező filozófusok problémája", problem of the dining philosophers)
Adva van valahány filozófus, akik egy kerek asztal körül ülnek. Mindegyikük előtt van egy tányér, a tányérok közt félúton pedig egy-egy villa. Az asztal közepén van a mindnyájuk betevőjét tartalmazó tál. Mindegyik filozófus -- lévén filozófus -- vacsora közben elmélkedik, majd időnként megéhezik. Az étel kiszedésére azonban mindkét keze ügyébe eső villát használnia kell, ha tehát valamelyik nem áll rendelkezésre, akkor várnia kell rá. A kérdés nyilván, hogy milyen stratégiát kövessenek a filozófusok, hogy a véletlen időközönként rájuk törő megéhezést minél kevesebb várakozással mindannyian sikeresen le tudják küzdeni, vagyis senki ne maradjon éhen.
A klasszikus vesztes stratégia: aki megéhezik és vár a sorára, sosem ereszti el a már megkaparintott villát, csak vár, amíg a szomszédja le nem teszi a neki kellő másik villát is. Ha ugyanis minden filozófus egyidőben mondjuk a jobb villát veszi kézbe, akkor mivel soha senki nem mond le önként az egyetlen haszontalan villájáról, soha senki nem fog tudni továbblépni -- és mindenki éhenhal.
Kapcsolódó szócikkek
- Kiéheztetés (starvation)
- Kölcsönös kizárás (mutual exclusion, mutex)
- Szinkronizáció (synchronization)
