Holtpontok

Holtpontok

Sok olyan eszköz van, amelyeket egyszerre csak egy processzus használhat.

CD-ROM, rajzgép, szalagmeghajtó, nyomtató..

Holtpont:

"A" processzus kéri a CD-ROM-ot, "B" a rajzgépet. Egy kis idő elteltével "A" kéri a rajzgépet, és blokkolódik, mert "B" has 222j92c ználja. Ezután ha "B" kéri a CD-ROM-ot, akkor blokkolódik, mert az "A"-nál van. Mind a ketten blokkolódnak örökre. Ez a holtpont.

A holtpont probléma előfordulhat nemcsak monopol B/K esetben.

Pl.: adatbázisban "A" zárolja az R1 rekordot, B az R2-t.

Ezután mindegyik megpróbálja zárolni a másik rekordját..

Holtpontok erőforrások kezelése esetén jöhetnek létre.

Az erőforrások lehetnek:

Megszakíthatatlanok (monopol módú)

Megszakítható (memória)

Erőforrás használatával kapcsolatos tevékenységek:

Erőforrás kérése

Erőforrás használata

Erőforrás elengedése

Holtpont fogalma:

Egy processzusokból álló halmaz holtpontban van, ha mindegyik halmazbeli processzus olyan eseményre várakozik, amit csak egy másik halmazbeli processzus okozhat.

Holtpont feltételei:

Kölcsönös kizárás feltétel:

Minden erőforrás vagy hozzá van rendelve pontosan egy processzushoz, vagy szabad.

Birtoklás és várakozás feltétel:

A processzusok a már korábban kapott erőforrásokat birtokolhatják és kérhetnek új erőforrásokat.

Megszakíthatatlanság feltétel:

Egy processzustól az előzőleg engedélyezett erőforrások nem vehetők el semmi módon.

Ciklikus várakozás feltétel:

Két vagy több processzusból összetevődő ciklikus láncnak kell lennie, amelynek mindegyik processzusa olyan erőforrásra várakozik, amit a láncban következő folyamat tart fogva.

Holtpont modellje:

A gráfmodellben egy kör holtpontot jelent.

A holtpontokkal kapcsolatos stratégiák

A probléma figyelmen kívül hagyása

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

Dinamikus elkerülés az erőforrások óvatos lefoglalásával

Megelőzés, strukturálisan meghiusítva a négy szükséges feltétel egyikét.

A strucc algoritmus

Matematikusok szerint a holtpontot mindig meg kell előzni, mérnökök szerint, ha elég kis eséllyel következik be holtpont (pl. 50 évenként egyszer) akkor nem kell vele foglalkozni.

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

A rendszer figyeli az erőforrásigényeket és elengedéseket. Az erőforrásgráfot ellenőrzi minden elengedéskor vagy kéréskor és köröket keres. Ha kör keletkezett, akkor az egyik processzust megszünteti, és ezt ismétli, amíg holtpontot talál.

Másik módszer, hogy azt figyeli, hogy van e olyan processzus, amely már több órája blokkolt, ha talál ilyet, megszünteti.

Figyeli az erőforrásokat, hogy ne legyen holtpont.

Holtpont megelőzése:

Ha a holtpont 4 feltétele közül biztosítható, hogy legalább egy ne következzen be, akkor a holtpont megelőzhető.

1. Ha egyetlen erőforrás sincs kizárólagosan egy processzushoz rendelve, akkor a holtpont elkerülhető. Nem mindig megoldható, hiszen a nyomtatónál ez elengedhetetlen. Ha háttértárolású nyomtatót alkalmazunk, akkor ez megoldható. A háttértároló módszer nem mindig alkalmazható (processzustáblázat).

2. Megelőzni olyan helyzeteket, amelyekben erőforrásokat birtokló processzusok várakoznak további erőforrásokra. Akkor működik optimálisan, ha az erőforrásigények előre ismertek.

3. Megszakíthatatlanság eldobása kevésbé megbízható.

4. Ciklikus várakozás megszüntetése:

Egy processzus egy erőforrást foglalhat.

Ez akkor hátrányos, ha egy hatalmas állományt szalagról másolunk át egy nyomtatóra.

Erőforrás megszámozással. A processzus igényelheti az erőforrásokat, de csak a megadott sorrendben.

Ha i>j , akkor A-nak nincs engedélyezve a j kérése.

Ha i<j , akkor B-nek nincs engedélyezve az i kérése

Holtpont elkerülése

Bankár algoritmus

A holtpontot úgy kerüli el, hogy a rendszert biztonságos állapotban tartja. Egy állapot akkor biztonságos, ha létezik legalább egy olyan sorozat, amely az összes folyamat erőforrás igényét ki tudja elégíteni.

(A bankár a lehető legtöbb kölcsönt szeretné nyújtani úgy, hogy ha az ügyfél visszafizeti azt, akkor abból más ügyfelek igényeit is ki tudja elégíteni.)

Ez az algoritmus akkor működik jól, ha a folyamatok tudják, hogy maximálisan mekkora az erőforrás igényük futásuk során. Azonban vannak olyan folyamatok, amelyek erőforrás igénye előre nem ismert.

Egy beérkező erőforrásigény teljesítése előtt az erőforráskezelő kiszámolja, hogy ha az igényt teljesítené, akkor biztonságos állapotba kerül e a rendszer. Ez biztosítja a holtpont elkerülését.

Pl.: Egy rendszerben A és B folyamatok futnak, és 12 erőforrás található benne.

A max. igénye 6, B max. igénye 11.

Ha B szeretné mind a 7 erőforrást megkapni, akkor várakozólistára kerül, hiszen nem lehet kielégíteni az igényét.

Az A folyamat viszont kielégíthető, hiszen 2 igényre van 4 szabad erőforrás. Miután A lefutott, a szabad erőforrás száma 10, így B kielégíthető.

A nem biztonságos állapot, nem jelenti a holtpont kialakulását.

Tegyük fel, hogy egy C processzus 8 erőforrásigényt jelent be, és máris kér 2-t.

Nézzük meg, hogy mi történik, ha kielégítjük a C igényét.

Az A lefuthat, futása után 6 szabad erőforrás lesz.

C igényei kielégíthetők, utána B igényei is.

Az állapot biztonságos marad, a folyamatok A, C, B sorrendben lefuthatnak.

Mi történik, ha a C 8 helyett 9 erőforrást igényelne, és 2-t máris kér?

Ha odaadjuk C-nek a 2 erőforrást, még mindig marad 2, amelyikből A igényét kielégíthetjük.

Sem B, sem C igénye nem lenne kielégíthető, ami nem biztonságos állapot. Ezért a C nem kaphatja meg a kért 2 erőforrást. Várakozólistára kerül, blokkolódik.

Bonyolultabb példa több erőforrásra:

Háromféle erőforrás E1, E2, E3 rendre 10, 5, 7 db.

Folyamatok F1, F2, F3, F4, F5

Szabad (2,3,0) látható, hogy csak F2 igénye elégíthető ki.

F2 (0,2,0)-t kap, s ha lefutott visszaadja azt, és a (3,0,2)-t.

Így (5,3,2) szabadhoz jutunk. F4 vagy F5 igény ebből kielégíthető.

Válasszuk F5-öt. Lefutása után (5,3,4) szabad erőforrás lesz.

F4 elégíthető ki, és lefutása után a készlet (7,4,5) lesz.

Ebből F1 és F3 is kielégíthető, F1 lefutása után (7,5,5) szabad lesz.

F3-at kielégítve (10,5,7) szabad lesz, és a folyamatok holtpontmentesen lefutottak.