Biztosítóberendezés, feldolgozása holtpontok - life-prog
Holtpont - olyan helyzetben, amikor az egyes csoport folyamatok váró esemény okozhat csak egy másik folyamat ebben a csoportban. Gyakran előfordul, hogy egy ilyen helyzet figyelhető meg a paradoxonok a „tyúk vagy a tojás.” Emellett vannak a nevek a zsákutcából. holtpont. megegyezik. Az angol irodalom, ez a helyzet az úgynevezett angol. holtpont (ejtsd Holtpont).
Az információs technológiák területén, a kölcsönös blokkolás azt jelenti, hogy a helyzet, amikor két vagy több folyamat várhatóan míg a másik nem nem mentesít egy adott erőforrás, vagy ha több mint két folyamat vár a források felszabadításában zárt körben.
Példaként, egy ilyen helyzet okozhat két férfi felhívni a kör, amelynek csak egy vonal és egy ceruzát. Ha az egyik férfi, hogy egy uralkodó, egy ceruza és a többi, köztük van olyan helyzet, amikor a kölcsönös blokkoló bontani a vonalat kell egy ceruzát, és meg kell bontani a vonalat ceruzával.
Általánosságban elmondható, hogy a blokkoló (vagy függő) van olyan helyzet, amikor nem számít, hogy mennyi idő telik el, sem prehid egyik állapotból a másikba nem kerülhet sor.
Feltételek előfordulási holtpont
Bebizonyosodott, hogy az esemény a patthelyzetet, meg kell felelnie a következő négy feltételnek egyidejűleg:
- Feltétel a kölcsönös kizárás (Eng. Kölcsönös kizárás). Minden erőforrás jelenleg elfoglalt vagy pontosan egy folyamat vagy ingyen. Azaz, a források találhatók a kizárólagos használat közben.
- Az az állapot megtartása és elvárások (Eng. Tartás és várjon). Az eljárások jelenleg tart a korábban kapott forrásokat, kérheti az új források.
- A feltétel hiányában kötelező megjelenése források (Eng. Elővásárlási). Lehetetlen kényszerítheti a folyamat, hogy kiadja a korábban kapott resursy.Protsess rendelkező erőforrásokat, hogy utasítsa el őket magának.
- Körkörös várakozás feltétel (Eng. Körkörös várakozás). Ott kell lennie egy gyűrű alakú sorozata két vagy több folyamat, amelyek mindegyike vár megszűnése az erőforrás által tartott a következő tagja a szekvencia. Más szóval, léteznie kell több eljárásra, így az eljárás a P 0 vár FORRÁSOK eljárás P 1, P 1 megvárja P 2. P N - 1, és P N. elvárja P N vár egy erőforrás folyamat P 0.
Az esemény egy patthelyzet, az szükséges, hogy mind a négy feltétel egyszerre. Ha legalább az egyik feltétel nem teljesül, a holtpont lehetetlen.
Modellezés holtpont
Példa grafikon erőforrás. Ebben a példában az összes folyamatot férnek hozzá a szükséges forrásokat, ezért nem lehet a holtpont.
A patthelyzet lehet leírni pontosabban segítségével speciális szerszámok - forráselosztás grafikon (angol rendszer erőforrás-allokáció grafikonon.). Ebben irányított gráfban, több csúcsú tartalmaz két altípus - az összes aktív folyamatok a rendszerben (P =) és a meglévő erőforrás típusok (R =).A szélén a P folyamat, és az erőforrás-vel jelöljük, mint a P J; Ez azt jelenti, hogy a folyamat a P, és nyújtott be kérelmet egységnyi erőforrás típus R J és várakozik a erőforrás (röviden, a borda kérést). Rib erőforrás típus R J, és a folyamatot nevezzük P; Ez azt jelenti, hogy egy erőforrás típus R J kapott folyamat, és a P (rövidítve kiadás él).
Mivel előfordulhat, hogy több egység ugyanolyan típusú források, a források vannak jelölve csúcsokat téglalapok pontok belül. A pontok száma jelzi számú erőforrás egységet az ilyen típusú.
Ezzel a meghatározással az oszlop források elosztását, ki lehet mutatni, hogy ha nincsenek ciklusok a grafikonon, sem a folyamatok nem ebbe a zsákutcába. Feltéve, hogy a ciklus a grafikonon, lehetőség van az esemény holtpontok.
Ha minden erőforrás típus csak egy példány, a jelenléte a ciklus feltételezi a patthelyzet. Minden folyamatot a ciklusban üt egy zsákutca.
Ha vannak erőforrás típust több esetben, a jelen patthelyzet nem következik a jelenléte a ciklus. Ebben az esetben a jelenléte a ciklus szükséges, de nem elégséges feltétele az előfordulása holtpontok.
Petri hálók
A Petri-háló, az úgynevezett zsákutca oly sok találat, hogy minden átmenet, hogy a kimeneti az egyik helyzetben a patthelyzet, patthelyzet használja minden helyzetben inputként. Azaz, ha az összes zsákutca helyzetben egy bizonyos ponton lesz üres, az egész készlet pozíciók üres marad örökre. Egyik átmeneti darab nem tud mozogni a holtpont, mert nincs holtpont chipek lehetővé átmenet, a kimenete, amely a helyzet a holtpont.
Trap nevezzük egy sor pozíciókat, amelyek minden egyes átmenet, amelynek bejáratánál az egyik a több pozíciókat a kimeneti van egy másik helyzetbe beállított. Azaz, ha egy tetszőleges pozícióját a csapdák is jellemző, hogy mindig lesz olyan helyzetben, hogy csapda.
Bizonyítást nyert, hogy a jelzett Petri háló szükséges és elégséges tevékenység szabad választás az a követelmény, hogy minden szereplő a holtpont csapda chip.
feldolgozás holtpont
Feldolgozása és kezelése holtpont helyzetek sorolhatók:
- Elhanyagolása probléma egyáltalán (vagyis. N. „strucc algoritmus”).
- Felderítése és hasznosítása. Hagy történni kölcsönös blokkolás, azonosítására, valamint bizonyos intézkedéseket.
- Dinamikus elkerül holtpont keresztül a megfelelő források elosztását.
- Megelőzés a kudarc az egyik négy feltétel bekövetkezése retesz.
Az első megközelítés használják a legtöbb modern operációs rendszer. A helyes viselkedés egy olyan helyzetben, patthelyzet a felelősséget a szoftver fejlesztő.
megelőzés
Mint már említettük, az esemény patthelyzetet kell egyidejű végrehajtása négy feltétel. Ha egyikük nem teljesül, akkor a patthelyzet nem fordul elő. Íme leírások a megközelítések az egyes feltételektől.
kölcsönös kizárás
Feltétel a kölcsönös kizárás, vagy kizárólagos használatra kell végezni nem szétválasztható források. Például a nyomtatót kell használni Exclusive egy folyamatot. Azonban néhány külön erőforrásokat, mint például a hozzáférés fájlokat a olvasás, lehet hallani a folyamatok számára.
Általában a kölcsönös kizárás feltétele nem lehet elkerülni, mert egyes források kell használni, csak egy exkluzív módban.
Mert elmulasztása, minden alkalommal, amikor a folyamat igényli az új erőforrásokat, nem tartalmazhat egyéb források. A következő algoritmus:
- Kap az összes erőforrás elején a folyamat egyéb műveletek elvégzésére.
- Fogadása új erőforrás alá engedje elfoglalt források. Mielőtt új erőforrás, a folyamat elengedi a források általuk elfoglalt.
A hátránya az első algoritmus egy hatékony erőforrás-felhasználás és egyszerű. Emellett ott van a lehetősége, hogy „éhség”: az a túltöltött rendszer, a folyamat, amely számos népszerű források soha nem hagyja, hogy megszerezzék, mert legalább egyikük lehet használni egy másik folyamat.
Erőltetett források felszabadításában
Elmulasztásáért szempontjából nincs szabad hely az erőforrás, a következő algoritmusok:
Egy ilyen algoritmust használnak erőforrásokat, amelynek állapota könnyen menteni és reprodukálható, mint a processzor regiszterek vagy memóriát.
konjunkturális várakozások
konjunkturális várakozások elkerülésére elérni, hogy az eljárás erőforrásaihoz való hozzáférést a különböző típusú.
Let - sokféle források. Mi azonosulni mindegyik egy egész szám, amely összehasonlítja a forrásokat, illetve prioritásokat (lásd. Poset).
Most, hogy elkerüljék konjunkturális várakozások a következő jogokat: a folyamat kérheti források csak emelkedő számsorrendben. Más esetben az eljárást meg kell felszabadítani az erőforrást egy nagy sorszámot, mielőtt a kérést az erőforrás egy kisebb számot.
Annak ellenére, hogy a létesítmény és betartását a helyes megszerzésére irányuló eljárások erőforrásokhoz való hozzáférést a felelőssége a szoftverfejlesztő, vannak speciális eszközök betartásának ellenőrzését a rend és a hibaüzenetek. Ennek egyik példája a tanú program fut BSD operációsrendszer-család.
Annak elkerülése érdekében, patthelyzet sutatsy, a program kell előre, hogy az operációs rendszer erőforrás információt, amelyeket használni fognak a folyamat során. Ezzel az információval az operációs rendszer úgy dönthet, hogy megfeleljen minden kérést eljárás várhat. Annak eldöntéséhez, hogy várni a folyamat, az operációs rendszer figyelembe kell venni a rendelkezésre álló erőforrások, az erőforrásokat folyamatok és a jövőbeli követelményeknek, amelyek a folyamatok.
műszerek
Köztudott az ilyen eszközöket, hogy működjön együtt a szegecs a számítástechnikai rendszerek:
tanú tanú program fut operatsiniynih BSD-alapú rendszerek, információkat kap a Loki kapott és ellenőrzésének elfogadhatóságát ezeket a kéréseket. Spin rendszer ellenőrzésére elosztott rendszerek modell.