4. tétel - Holtpont

Mutassa be az étkező filozófusok problémáját! Definiálja a holtpont fogalmát! Mik a kialakulásának előfeltételei? Ismertesse a kezelésének módszereit!

Étkező filozófusok

• Öt filozófus ül egy kör alakú asztalánál

• Ténykedésük során a filozofálás és étkezés műveleteket végzik végtelen sokáig, felváltva.

• Az étkezéshez két villa kell egy filozófusnak, mert spagettit esznek

• A gondolkodáshoz nem kell semmi

• Az asztalnál pontosan annyi villa van, mint amennyi filozófus, ezek két-két filozófus közé vannak elhelyezve

Megkötések:

• Az erőforrások nem megoszthatóak: egy villát egy filozófus használ egyszerre
• Egy filozófus csak addig tartja magánál a villát, amíg eszik
• Ha a filozófus megéhezik, de a bal vagy jobb-oldali villa foglalt, akkor várakozik annak felszabadulására
• A filozófusok önállóak, nem kommunikálnak

Előfordulhat, hogy minden filozófus rögtön éhes, és felveszi a tőle jobbra lévő villát. Ekkor nincs ütközés, mindenki fel tud venni egy villát. Mivel két villa kell az evéshez, mindegyikük nyúlna a bal villáért is. Mivel azonban az már a tőlük balra ülő filozófus kezében van, várakozni kezdenek a felszabadulásra, ami soha nem következik be, mert mindenki a tőle balra ülőre vár. Ez a helyzet a holtpont.

Holtpont

Általánosságban holtpontról akkor beszélünk, ha egy szál blokkolva van, és annak blokkolása sosem szűnik meg.

Szálak vagy folyamatok halmaza holtpontban van, ha mindegyik vár egy olyan esemény bekövetkeztére, amelyet ugyanezen halmaz egy másik eleme válthat ki. Az elemek egymásra várakoznak, tehát a várakozás sosem fog véget érni

Holtpont kialakulásának feltételei

1. Körkörös várakozás
2. Kölcsönös kizárás: közös, nem megosztható erőforrások
3. Foglal és vár stratégia: egy szál munkájához több erőforrásra is szükség van, és magánál tartja őket az összes megszerzéséig
4. Preemptivitiás hiánya: egy felsőbb szintű felügyelő nem tudja elvenni az erőforrást a száltól

Holtpont kezelése megelőzéssel

A 4 közül az egyik szükséges feltételt megszüntetjük, így nem állhat elő holtpont

• A kölcsönös kizárás elkerülése nem biztonságos, mert megosztottak az erőforrások
• A foglal és vár megszüntetéséhez a szálnak el kellene engednie a már megszerzett erőforrást, hogy egy újat szerezzen meg. Ezesetében ismerünk kell előre az erőforrásokat, és fennáll a kiéheztetés veszélye.
• A preemtivitás esetén beláthatatlan következményei lehetnek, ha egy szál elveszíti az erőforrást
• Legkönnyebben tehát a körkörös várakozás szüntethető meg
  1. Korlátozzuk, hogy egy szál egyidőben legfeljebb csak egy erőforrást tarthat magánál
     • Nem mindig lehetséges, mert van hogy több erőforrás kell
  2. Erőforrás kérés szabályozása, pl. az erőforrások sorbarendezésével
     • Az étkező filozófusoknál például 1-től 5-ig számozzuk a villákat, és megkötjük, hogy előbb a kisebb számú villát kell felvenni a filozófusnak. Ekkor:
       1. filozófus célja: R₁ majd R₂ megszerzése
       2. filozófus célja: R₂ majd R₃ megszerzése
       3. filozófus célja: R₃ majd R₄ megszerzése
       4. filozófus célja: R₄ majd R₅ megszerzése
       5. filozófus célja: R₁ majd R₅ megszerzése
       • Mivel az első és utolsó filozófus közül egyik nem tudja megszerezni R₁-et, nem alakul ki holtpont

Holtpont kezelése elkerüléssel

Futásidőben figyeljük, hogy olyan erőforrás hozzárendelés ne történhessen, amely holtponthoz vezethet. Erőforrás igénylésekor a felügyelő szerv elvégez egy számítást, mi történne, ha a kérést engedélyezné, biztonságos (holtpont nélküli) vagy nem biztonságos (holtpont) állapotba kerülne-e.

Ha biztonságos lenne, engedélyezi az erőforrás-kérést, ha nem, akkor blokkolja a kérést addig, amíg nem lesz biztonságosan teljesíthető.

Holtpont kezelése észlelés és helyreállás által

Erőforrás-foglalási gráf

Olyan irányított gráf, ahol a csomópontok szálakat (P) és erőforrásokat (R) jelölhetnek. A gráf élei minden esetben csak szálak és erőforrások között vezethetnek.

• Ha egy szál csomópontjából él vezet egy erőforrás csomópontjába, akkor a szál igényli az erőforrást.
• Ha egy erőforrás csomópontjából él vezet egy szál csomópontjába, akkor a szál magánál tartja az erőforrást.

Észlelés

• A holtpont felfedezése a gyakorlatban megoldható az erőforrás-foglalási gráf megtekintésével.
• Ha a rendszerben nincs több példányt kiosztó erőforrás, és a szükséges feltételek mellett irányított kört figyelünk meg, akkor a rendszer holtpontba került.
• Amennyiben az érintett erőforrások több példány kiadására is képesek, akkor a kör nem igazolja a holtpont meglétét. Ilyen esetben egyéb feltételek megvizsgálása is szükséges lehet.

Helyreállás

• valamely szálat vagy szálakat meg kell szakítani, és az általuk foglalt erőforrást felszabadítani
• gyors, de költséges megoldás, ha minden érintett szálat megszakítunk
• megszakíthatunk csak egy-egy szálat is, de melyiket?
  • erőforrás-foglalási gráf elemzése segíthet
  • vagy egyesével szakítjuk meg a szálakat addig, amíg a holtpont meg nem szűnik (akár valamilyen prioritás alapján sorrendben => mohó módszer)