Nyíregyházi Főiskola Matematika és Informatika Intézete. Holtpont (Deadlock) Alapfogalmak, példák, ábrázolás. Biztonságos és nem biztonságos állapot

Nyíregyházi Főiskola Matematika és Informatika Intézete

04

Holtpont (Deadlock)  Alapfogalmak, példák, ábrázolás  Kialakulási feltételek  Biztonságos és nem biztonságos állapot  Holtpont kezelési stratégiák  Problémák

Dr. Bajalinov Erik

Operációs rendszerek (PMB1206)

1


04

Alapfogalmak 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 lefoglalni akarja a nyomtatót, majd utána a CDírót. Közben egy másik taszk lefoglalni akarja a CD-írót, majd utána lefoglalni szeretné a nyomtatót. Tegyük fel, hogy az első taszk sikeresen lefoglalta a nyomtatót, miközben ezzel egy időben a második taszk szintén sikeresen lefoglalta a CD-írót. Most, az első taszk megpróbálja lefoglalni a CD-írót, a második taszk pedig a nyomtatót. Egyik taszk sem fog sikerrel járni, mert a másik taszk már tartja a zárat. Mindkét taszk a végtelenségig fog várni arra, hogy a másik elengedje az erőforrást, de ez nem fog bekövetkezni.

Dr. Bajalinov Erik


2


04

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. Mindegyik 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 éhen hal.

Dr. Bajalinov Erik


3


04

Példák:

Dr. Bajalinov Erik


4


04

Grafikus ábrázolás:

Dr. Bajalinov Erik


5


04

Erőforrás-használati gráf:

Kölcsönös blokkolás Dr. Bajalinov Erik


6


04

A holtpont kialakulásának szükséges feltételei (Coffman) 1. kölcsönös kizárás (mutex): legalább egy – többek által igényelt – erőforrás nem megosztható, azaz egyszerre csak egy processzus használhatja; 2. foglalva várakozás (hold & wait): valamelyik processzus már lefoglalt egy erőforrást, és arra vár, hogy továbbiakat lefoglaljon; 3. nem elvehető erőforrások (nonpreemptive): az erőforrást a foglalótól nem lehet kívülről – operációs rendszer beavatkozással – elvenni; 4. körkörös várakozás (circular waiting): a körben állók folyamatok mindegyike a következő által foglalt erőforrásra vár. Megjegyzés: a négy feltételnek egyszerre kell teljesülnie (de nem függetlenek), Azaz ha valamelyik nem teljesül, nincs holtponti helyzet

Dr. Bajalinov Erik


7


04

Holtpont kialakulásának ábrázolása

I

II

III

IV

V

VI holtpont

Dr. Bajalinov Erik


8


04

9

És elkerülése:

I

II

III

IV

V

VI B folyamat várakozik

Dr. Bajalinov Erik



04

Grafikus módszer

Biztonságos és nem biztonságos állapot Biztonságos állapot az, amiből legalább egy végrehajtási sorrend lehetséges, mely nem holtponttal végződik (nem biztonságos állapot az, amire ez nem igaz) Dr. Bajalinov Erik


10


04

Holtpont kezelési stratégiák 1. Nem foglalkozunk a Deadlock-kal (strucc-politika: Unix, Windows; valószínűtlen eseménynek tekintjük ezt a helyzetet; a kezelése pedig költséges) 2. Felismerés és helyreállítás (csak a holtpont kialakulásánál avatkozunk be) Holtpont felismerés (deadlock recognition) Holtpont felszámolása (deadlock recovery) 3. Megelőzés (strukturálisan meghiúsítva, deadlock prevention) 4. Dinamikus megoldás

Dr. Bajalinov Erik


11


04

2. Felismerés és helyreállítás

 ha kör alakulna ki egy kéréskor, megszüntetjük a processzust  azokat a processzusokat, amelyek hosszú ideig allokálnak erőforrást megszüntetjük (batch rendszerekben újra indítjuk, de a rendszer állapot visszaállítás problémás – check points, roll back.) 3. Megelőzés –a Coffman 4 feltételből legalább az egyikének kizárása. 1. Kölcsönös kizárást nem lehet kiküszöbölni. 2. Foglalva várakozás kizárása – egy folyamat csak akkor kérhet új erőforrást, ha nem tart lefoglalva másikat (vagy futás elején lefoglalja az összes szükséges erőforrást!) 3. Nem elvehető erőforrások kezelése – hogyan lehet elvenni nyomtatót vagy DVD-írót?) 4. Körkörös várakozás kizárása – a várakozó folyamtokból az egyikének (?) megszüntetése.

Dr. Bajalinov Erik


12


04

4. Dinamikus megoldás - az erőforrások óvatos allokálásával elkerülhető a holtpont kialakulása. Egyetlen (vagy több) erőforrás - Bankár algoritmus (Dijkstra, 1965). Lényege: Csak azokat a folyamatokat engedjük futni, melyek erőforrásigénye kielégíthető, ha az összes erőforrást igényli, amire szüksége van. Azaz ha jelen pillanatban ki tudjuk elégíteni valamely folyamat maximális igényét, akkor biztonságos állapotban vagyunk, a folyamat futhat. Ha nem, akkor az állapot bizonytalan, a folyamat nem futhat.

Dr. Bajalinov Erik


13


04

Problémák  Előre meg kell mondania a folyamatnak, hogy hány erőforrást fog igényelni.  Real-time kérdések, on-fly módban történő kezelés, a kötegelt feldolgozás (batch) feldolgozásnál előre meghatározott sorrend.  NINCS, vagy legalább is eddig még nem tudunk tökéletes megoldásról!!!

Dr. Bajalinov Erik


14

Nyíregyházi Főiskola Matematika és Informatika Intézete. Holtpont (Deadlock) Alapfogalmak, példák, ábrázolás. Biztonságos és nem biztonságos állapot

Recommend Documents