Mikä on käyttöjärjestelmän umpikuja: ehdot ja tunnistusalgoritmi

Mikä on käyttöjärjestelmän umpikuja: ehdot ja tunnistusalgoritmi

Käyttöjärjestelmän päätavoitteena on tarjota asianmukainen viestintä laitteisto- ja ohjelmistoresurssien välillä ja tarjota myös yhteisiä palveluita ohjelmille. Kun käyttöjärjestelmäprosessi haluaa käyttää mitä tahansa resurssia, se ensin lähettää pyynnön tietylle resurssille, jota haluaa käyttää, sitten käyttää resurssia ja lopulta vapauttaa resurssin käytön jälkeen. Oletetaan, että monet prosessit yrittävät käyttää yhtä resurssia samanaikaisesti, on vaikeaa tarjota yhtä resurssia kaikille prosesseille kerrallaan sellaisessa tilanteessa, jossa syntyy umpikuja. Tästä syystä tässä artikkelissa kuvataan, miten umpikuja tapahtuu ja miten päästä umpikujaan.



Mikä on käyttöjärjestelmän umpikuja?

Määritelmä: Dead-Lock on tilanne, jossa kaksi tai useampi prosessori odottaa jonkin tapahtuman tapahtumista, mutta sellaiset tapahtumat, joita ei tapahdu, ovat umpikujassa, ja prosessorien sanotaan olevan umpikujassa. Oletetaan esimerkiksi reaaliaikainen skenaario, jossa on kaksi A- ja B-autoa, joita ajaa kaksi yksittäistä kuljettajaa yksisuuntaisella tiellä. Nyt syntyy tilanne, jossa auton A kuljettajan mukaan liikkuminen pohjoiseen on oikea suunta, kun taas auton B kuljettajan mukaan eteläsuuntaan liikkuminen on oikein. Mutta kumpikaan ei siirry takaisin, jotta toinen auto voisi liikkua eteenpäin, tätä tilaa kutsutaan umpikujaan.


Esimerkki autosta

auto-esimerkki





Paremman ymmärtämisen vuoksi tarkastellaan toista esimerkkiä, jossa on kaksi resurssia R1, R2 ja kaksi prosessia P1 ja P2, joissa R1 on osoitettu P1: lle ja R2 on osoitettu P2: lle. Nyt jos P1 haluaa käyttää R2: ta, kuten tiedämme jo, R2 on P2: n hallussa, ja nyt P2 haluaa käyttää R1: tä, mikä on P1 suorittaa vain, kun se saa yhteyden R2: een, myös P2 suorittaa vain, kun se saa yhteyden R1: ään, tämä tilanne on umpikujassa.

Prosessori-esimerkki

prosessori-esimerkki



Kuolleen lukon olosuhteet

Seuraavassa on neljä tärkeää umpikujaolosuhetta, jotka tapahtuvat, jos kaikki olosuhteet tapahtuvat samanaikaisesti, ja umpikujaan on olemassa tiettyjä mahdollisuuksia.

Yhteinen poissulkeminen

Se tarkoittaa, että mitä resurssia me käytämme, sitä on käytettävä toisiaan poissulkevalla tavalla. Jos vain yksi prosessi käyttää vain yhtä resurssia kerrallaan. Esimerkiksi tulostusprosessi on käynnissä ja yhtäkkiä toinen prosessi yrittää keskeyttää tulostusprosessin. Joten tässä keskinäisen poissulkemisen tilanteessa vasta seuraava tehtävä käsitellään vasta tulostustehtävän valmistuttua. Keskinäinen syrjäytyminen voidaan poistaa jakamalla resursseja samanaikaisesti, mikä ei ole käytännössä mahdollista.

Yhteinen poissulkeminen

yhteinen poissulkeminen

Ei etuoikeutta

Mukaan ennaltaehkäisevä perustuvat algoritmit, jos jokin prioriteettitehtävä yrittää keskeyttää nykyisen tehtävän. Ennakoiva algoritmi, jolla se pitää nykyistä tehtävää ja suorittaa ensisijaisen tehtävän ja palaa ensimmäiseen tehtäväänsä. Edellisen esimerkin mukaisesti selitetty tilanne, jossa prosessi pitää resurssia niin kauan kuin se suoritetaan, ts. P1 voi vapauttaa R1: n vasta suorituksen jälkeen, samalla tavalla kuin P2-julkaisu R2 vasta suorituksen jälkeen. Jos etuoikeutta ei ole, umpikuja voi tapahtua.


Ei-ennakko-esimerkki

ei-ennakko-esimerkki

Pidä ja odota

Prosessi sisältää joitain resursseja ja odottaa lisäresursseja, mutta nämä resurssit hankitaan jollakin muulla prosessilla. Yllä olevasta esimerkistä P1 pitää R1: tä ja odottaa R2: ta, jossa R2 on P2: n hankkima, ja P2 pitää R2: ta ja odottaa R1: tä, jossa P1 on hankkinut R1: n on pidätys ja järjestelmässä voi esiintyä umpikuja.

Pidä ja odota -esimerkki

pidä ja odota -esimerkki

Pyöreä odotus

Joukon prosesseja sanotaan olevan umpikujassa, jos yksi prosessi odottaa resurssia, joka on allokoitu toiselle prosessille, ja tuo prosessi odottaa resurssia, se on samanlainen kuin yllä selitetty esimerkki, jossa se on silmukan muodossa. Kun P1 odottaa R2: ta ja R2 on allokoitu P2: lle ja P2 odottaa R1: tä ja R1, joka on varattu P1: lle, joka on pyöreä odotusmuoto, jos tämä ehto tyydyttää umpikujan.

Pyöreä-odota-esimerkki

pyöreä-odota-esimerkki

Kuollun lukituksen tunnistusalgoritmi

Tapaukset, joissa allokoimme resursseja prosesseille, ja käyttöjärjestelmä tarkistaa uudelleen, onko järjestelmässä umpikuja vai ei, kun käytetään kahta päälukituksen havaitsemisalgoritmia, ne ovat

  • Yksi esimerkki
  • Useita resurssityypin esiintymiä

Yhden oikeusasteen

Yksittäinen esiintymä on tilanne, jossa järjestelmällä on yksittäiset esiintymät kaikista resursseista. Se tunnetaan myös nimellä odottaa kaavion algoritmia tai resurssien allokointikaaviota. Resurssien kohdentamiskaavio koostuu joukosta prosesseja ja joukko resursseja, jotka on esitetty kahtena eri kärkeen. Resurssien kohdentamiskaavion resursseja muokataan ja ne esitetään kaavion odotuksen muodossa. Jos kaavion muodon odottamisella on vain prosessit, jotka esitetään pisteinä, kuten alla on esitetty,

  • Resurssien kohdentamiskaavio: Prosessit P1, P2, P3 ja resurssit R1, R2, R3 on esitetty resurssien kohdentamiskaaviossa.
  • Odota kuvaajaa: Kaavion odottamisessa mainitaan vain prosessit P1, P2, P3.
  • Jos on sykliehto, se tarkoittaa, että jos prosessia kulkee jatkuvasti yhteen suuntaan, se tarkoittaa syklin ehdon poistumista ja odota, että kaavio on umpikujassa.

Esimerkki 1: Alla oleva esimerkki osoittaa, että umpikuja-tilaa ei ole, koska kaaviota odotettaessa ei havaita jatkuvaa virtausta.

Yksittäinen esimerkki 1

yhden tapauksen esimerkki 1

Esimerkki 2: Umpilukko on tapahtunut, koska P1: stä P4: ään kulkee jatkuva syklivirta.

Yhden asteen esimerkki 2

yksittäistapaus-esimerkki2

Jos umpikuja esiintyy järjestelmässä hyvin usein, ilmaisualgoritmia käytetään usein. Jos ilmaisualgoritmia käytetään enemmän, on enemmän yleiskustannuksia ja enemmän laskenta-aikaa. Tästä syystä käytämme algoritmia sen jälkeen, kun annamme yhtä paljon aikaa, kaavion painoa käytetään tällöin havaitsemaan umpikuja.

Useita resurssityypin esiintymiä

Resurssityypin useat esiintymät ovat tilanne, jossa järjestelmällä on useita esiintymiä kaikista resursseista, se tunnetaan myös nimellä Bankers-algoritmi. Bankers-algoritmin mukaan, kun prosessi saa kaikki tarvittavat resurssit, se vapauttaa resurssit.

Tarkastellaan seuraavaa esimerkkiä, oletetaan, että on 3 prosessia P0, P1, P2 ja resurssityyppi A, B, C, joissa A voi olla prosessori , B voi olla tulostin ja C voi olla näppäimistö. Sarakkeen numerot '0' edustavat resurssien saatavuutta.

Tapaus (i): Oletetaan, että jos otamme ehtopyynnön olevan '000' ehto, joka on läsnä P0: ssa ja P2: ssa, meidän pitäisi tarkistaa, mikä pyyntö on täytetty, prosessit P0 vapauttavat prosessit allokoinnin jälkeen, sitten seuraavat P2-prosessit vapauttavat allokoinnin jälkeen. Tällä tavoin, peräkkäin, yksi kerrallaan prosessi vapauttaa P0, P2, P3, P1, P4 peräkkäin. Lopuksi saamme käytettävissä olevat resurssit muodossa P7, P2, P6. Käytettävissä oleva sekvenssi on tila, jossa ei ole umpikujaa.

Pankkiirien algoritmi-esimerkki 1

pankkiirit-algoritmi-esimerkki 1

Talot (ii): Oletetaan, että jos P2 on 001 000: n sijasta, käytä nyt pankkiirin algoritmia tarkistaaksesi umpikujatilan, jossa ainoa P0 suoritetaan kaikkien 5 prosessin joukossa. Siksi P1, P2, P3, P4 ovat umpikujassa lukuun ottamatta P0: ta.

Pankkiirien esimerkki 2

pankkiirien esimerkki2

Deadlock-sovellukset

Umpikujan sovellukset voidaan selittää reaaliaikaisella esimerkillä online-kokeen tuloksista, joissa useat opiskelijat yrittävät päästä yliopiston verkkosivustolle julkaisuhetkellä. Voidaan havaita, että toisinaan web-sivu ei lataudu kerralla usealle käyttäjälle, tämä on umpikujassa. Tämä voidaan voittaa käyttämällä mitä tahansa algoritmeja.

Edut

Umpikujan edut ovat

  • Etuosaa ei havaita umpikujan välttämisessä
  • Ei viivettä prosessissa

Haitat

Umpikujan haittana on

  • Käytettävän resurssin on oltava etukäteen tiedossa
  • Prosessin tukkeutuminen pitkään
  • Ennakkotappiot peritään.

Tässä artikkelissa kerrotaan, kuinka umpikuja tapahtuu, kun on olemassa kaksi tai useampia prosesseja, ja kolmesta olosuhteesta, jotka aiheuttavat umpikujan, ja kahdesta algoritmityypistä, nimittäin resurssien jakamisalgoritmista, joka havaitsee olemassa olevan umpikujaan ja pankkiirien algoritmi, joka on umpikujan välttämisen algoritmi. Tässä on kysymys 'Mitä tapahtuu, jos umpikuja jätetään huomioimatta?'.