Az erőforrás* kezelésnek az a módszere, hogy ha van szabad erőforrás, akkor kielégítjük, ha nincs, akkor pedig a folyamat várakozni kényszerül, végtelenül egyszerűnek tűnik. Ez a probléma nagyvonalú megközelítése, azonban korlátai elég hamar megmutatkoznak.
Veszélye például, hogy ha több folyamat egy olyan erőforrás felszabadulására vár, amit csak egy ugyancsak várakozó folyamat tudna előidézni, akkor mindegyik érintett folyamat csak vár, csak vár, csak vár … Ez az állapot kapta a holtpont nevet. Holtpont esetén a folyamatok körkörösen egymásra várakoznak. Ha megszüntetjük a párhuzamosságot a probléma megelőzhető.
*erőforrás: Minden, ami egy folyamat végrehajtásához szükséges. (CPU, memória, perifériák, állományok, stb.)
preemptív erőforrás: Az erőforrás a folyamat vagy egy erőforrás károsodása nélkül elvehető.
non-preemptív erőforrás: A folyamat vagy az erőforrás az erőforrás használatának megszakítása esetén esetleg sérülhet.
Pédák
Példa-1
közlekedési holtpont
Példa-2
Tételezzük föl, hogy egy taszk le akarja foglalni a nyomtatót, majd utána a CD-írót! Közben egy másik taszk le akarja foglalni a CD-írót, majd utána le szeretné foglalni a nyomtatót! Tegyük fel, hogy az 1. taszk sikeresen lefoglalta a nyomtatót, miközben ezzel egy időben a 2. taszk szintén sikeresen lefoglalta a CD-írót! Most, az 1. taszk megpróbálja lefoglalni a CD-írót, a 2. 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.
Példa-3 (vacsorázó bölcsek)
vacsorázó bölcsek
Öt kínai bölcs ül egy kerek asztal körül. Mindegyik előtt ott egy tányér rizs és a szomszédos tányérok között egy-egy pálcika. Az evéshez két pálcika kell, ezért egy bölcsnek mind a jobb-, mind a baloldali pálcikát meg kell szereznie, hogy elkezdhessen enni. Ha egy bölcs eszik, akkor egyik szomszédja sem tud, hiszen legalább az egyik pálcikája hiányzik hozzá.
Ha mindegyik bölcs egyszerre jut arra a döntésre, hogy először a bal-, majd a jobboldali pálcikát veszi kézbe, mindegyiknek csak egy pálcika jut, senki sem tud enni, holtpontra jutnak.
Ebben az esetben feltehetően születik megoldás, hiszen bölcsekről van szó. Ez azonban az egymásról mit sem tudó folyamatok esetén nem várható. Egy felsőbb erőnek, az operációs rendszernek kell rendet teremtenie, például úgy, hogy egyiktől elveszi a pálcikát és a szomszédjának adja.
A holtpont kialakulásának szükséges feltételei
- kölcsönös kizárás: Legalább egy – többek által igényelt – erőforrás nem megosztható, azaz egyszerre csak egy processzus használhatja.
- foglalva várakozás: Valamelyik processzus már lefoglalt egy erőforrást, és arra vár, hogy továbbiakat lefoglaljon.
- nem elvehető erőforrások: Az erőforrást a foglalótól nem lehet kívülről – operációs rendszer beavatkozással – elvenni.
- körkörös várakozás: A körben álló folyamatok mindegyike a következő által foglalt erőforrásra vár.
Ha a fenti 4 feltétel valamelyike nem teljesül, nincs holtponti helyzet!!!
Holtpont kezelő stratégiák
Ahhoz, hogy a rendszerünk holtpont-mentes legyen alapvetően kétféle stratégia választható: vagy meg kell előzni a holtpont kialakulását, vagy folyamatosan figyelni kell, hogy kialakult-e holtpont, és ha igen, meg kell tenni a megfelelő lépéseket a holtpont felszámolására. A holtpont megelőzése kevesebb veszteséggel jár, mint a már kialakult holtpont megszüntetése, de sajnos, nem mindig tehető meg, ezért kell a holtpont felszámolásával is foglalkozni.
-
Strucc algoritmus: Nem foglalkozunk a holtponttal (strucc-politika). Valószínűtlen eseménynek tekintjük ezt a helyzetet, a kezelése pedig költséges.
Ha a holtpont kialakulásának valószínűsége kicsi, a rendszer újraindításának nincsenek kritikus következményei, akkor megérheti ezt a megoldást választani. -
Az egyetlen foglalási lehetőség stratégiája: Ez a várakozás közbeni erőforrás-lekötést tiltja meg. A folyamat csak egy lépésben (célszerű induláskor) foglalhatja le az összes szükséges erőforrást. Ha bármelyik erőforrás is hiányzik a folyamat várakozó listára kerül. Az a folyamat, amelyik már rendelkezik erőforrással, többletigényt nem nyújthat be, a további kéréseket az operációs rendszer elutasítja. Holtpont nem alakulhat ki, mivel a futó folyamatok nem kényszerülnek várakozni, mindenük megvan, a várakozó folyamatok pedig nem rendelkeznek erőforrásokkal.
Előnye: Egy folyamat, ha már megszerezte az összes erőforrást, soha többé nem kell, hogy erőforrásra várakozzon, azaz gyorsan lefuthat.
Hátrányai: A folyamatok olyankor is kénytelenek foglalva tartani erőforrásokat, ha pillanatnyilag nincs rá szükségük. Nem mindig mérhető fel előre egy folyamat erőforrás igénye. Ha egy folyamat sok és népszerű erőforrást igényel, előfordulhat, hogy soha nem jön el az a pillanat, amikor mindegyik egyidejűleg áll rendelkezésre, így a folyamat bizonytalan ideig várakozni kényszerül, éhezik. -
Rangsor szerinti foglalás: A ciklikus várakozás lehetőségének kiküszöbölésével alkalmas a holtponthelyzetek megelőzésére. Lényege, hogy az erőforrások osztályaihoz egy-egy növekvő sorszámot rendelünk úgy, hogy a leggyakrabban használt erőforrások kapják a legkisebb sorszámot. Ha egy folyamatnak egy osztályon belül több erőforrásra van szüksége, azokat csak egyszerre igényelheti. Egy folyamat csak olyan osztályból igényelhet erőforrást, melynek sorszáma magasabb, mint a már birtokolt erőforrások sorszáma. Ha egy folyamatnak a meglévőknél alacsonyabb sorszámú erőforrásra van szüksége, fel kell szabadítania erőforrásokat egészen addig a szintig, míg az igénylési feltételek nem teljesülnek.
-
Bankár algoritmus: A rendszert mindig ún. biztonságos állapotban tartja. Egy állapotot akkor tekintünk biztonságosnak, ha létezik legalább egy olyan sorozat, amely szerint az összes folyamat erőforrás igénye kielégíthető. Sose elégítsünk ki egy igényt, ha az nem biztonságos állapotot eredményez!
Az algoritmus csak akkor működik, ha a folyamatok indulásukkor tudják, hogy a különböző erőforrásokból egyszerre maximálisan hányat fognak igényelni, és ezt az op. rendszernek – egy rendszerhívás által – be is jelentik. Ez a módszer legnagyobb hátránya, hogy vannak olyan folyamatok, amelyek erőforrás igénye előre nem tudható.
Meg kell jegyezni, hogy ha egy rendszer állapota nem biztonságos, nem jelenti azt, hogy a holtpont kialakul, hanem mindössze azt, hogy lehet hogy kialakul. Azaz az algoritmus úgy garantálja a holtpont mentességet, hogy már egy, a holtpontnál tágabb szituáció a nem biztonságos állapot kialakulását is megakadályozza.
Bankár: az operációs rendszer
Ügyfél: a processz
Hitelegység: az erőforráspélda_1 aktuálisan igénybe vett hitel maximálisan igénybe vehető hitel Négy hitelező (A,B,C,D) adott hitelezési egységgel rendelkezik. Kiszolgálásukra a bankár 10 egységet foglal le a 25 helyett.
Itt mindegy, hogy kinek a hitel igényét elégítjük ki először.
A 0 9 B 0 5 C 0 4 D 0 7 szabad keret: 10 Ez egy biztonságos állapot. példa_2 aktuálisan igénybe vett hitel maximálisan igénybe vehető hitel Ha mindenki a max. keretét igényli, akkor C-nek kifizethető az összeg és felszabadítható az ő maximális kerete (4).
Ebből már B max. hiteligénye fizethető ki és a keret (5) felszabadítása után D további igénye is kielégíthető. Az így felszabadított max. keret (7) felszabadításával A fennmaradó hiteligénye is kifizethető.A 2 9 B 1 5 C 2 4 D 4 7 szabad keret: 2 Ez egy biztonságos állapot. példa_3 aktuálisan igénybe vett hitel maximálisan igénybe vehető hitel Itt senkinek sem tudjuk a hiteligényét maradéktalanul kielégíteni.
A 1 9 B 3 5 C 2 4 D 4 7 szabad keret: 1 Ez egy biztonytalan állapot!!! Egy másik jó kis példa itt található pps-formátumban. (Az eredetit itt találtam:
www.kobakbt.hu/jegyzet/bankar.pps)