Kaj je zastoj v operacijskem sistemu: pogoji in algoritem zaznavanja

Glavni cilj operacijskega sistema je zagotoviti ustrezno komunikacijo med viri strojne in programske opreme ter programom zagotoviti skupne storitve. Ko želi postopek operacijskega sistema dostopati do katerega koli vira, najprej pošlje zahtevo določenemu viru, do katerega želi dostopati, nato ga uporabi in na koncu vir sprosti po uporabi. Predpostavimo, da mnogi procesi poskušajo hkrati dostopati do enega vira, zato je težko zagotoviti en vir vsem procesom hkrati, v takšni situaciji se pojavi koncept z imenom mrtva točka. Zato ta članek opisuje, kako pride do zastoja in kako ga premagati.

Kaj je zastoj v operacijskem sistemu?

Opredelitev: Dead-Lock je situacija, ko dva ali več procesorjev čaka, da se zgodi kakšen dogodek, vendar so takšni dogodki, ki se ne zgodijo, stanje mrtve točke, procesorji pa naj bi bili v stanju mrtve točke. Predpostavimo na primer scenarij v realnem času, kjer sta dva avtomobila A & B, ki ju po enosmerni cesti vozita dva posamezna voznika. Zdaj pride do situacije, ko voznik avtomobila A pravi, da je premikanje proti severu pravilna smer, voznik avtomobila B pa pravi, da je premikanje proti jugu pravilno. Toda nobeden od njih se ne premakne nazaj, da bi drugemu avtomobilu uspelo naprej, temu stanju pravimo stanje mrtve točke.

primer avtomobila

Za boljše razumevanje si oglejmo še en primer, kjer obstajata dva vira R1, R2 in dva procesa P1 in P2, kjer je R1 dodeljen P1, R2 pa P2. Zdaj, če želi P1 dostopati do R2, saj že vemo, da R2 drži P2, zdaj pa želi P2 dostopati do R1, kar pomeni, da se P1 izvrši samo, ko se dostopi do R2, tudi P2 izvede samo, ko dobi dostop do R1 je stanje mrtve točke.

primer procesorja

Dead-Lock pogoji

Sledijo štirje pomembni pogoji zastoja, če se vsi pogoji pojavijo hkrati, obstajajo določene možnosti, da se zastoj zgodi.

Medsebojna izključitev

Pomeni, da se mora kateri koli vir, ki ga uporabljamo, uporabljati na izključujoč se način. Kjer samo en proces hkrati uporablja en vir. Na primer, postopek tiskanja se nadaljuje in naenkrat drug postopek poskuša postopek tiskanja prekiniti. Torej, v primeru medsebojne izključenosti se šele po zaključku tiskalne naloge obdela samo naslednja naloga. Vzajemno izključitev je mogoče odpraviti s hkratno delitvijo virov, kar praktično ni mogoče.

medsebojna izključenost

Brez predkupne pravice

Po navedbah prednostno algoritmi, če obstaja prednostna naloga, ki poskuša prekiniti trenutno nalogo. Prednostni algoritem vsebuje trenutno nalogo, najprej izvrši prednostno nalogo in se vrne na prvo nalogo. Razložen primer v zgornjem primeru, ko proces zadrži vir, dokler se izvede, to je P1, lahko sprosti R1 šele po izvedbi, podobno P2 sprosti R2 šele po izvedbi. Če ni predplačila, lahko pride do zastoja.

primer brez odkupa

Počakaj in počakaj

Proces vsebuje nekaj virov in čaka na dodatne vire, vendar jih pridobi nek drug postopek. Iz zgornjega primera P1 drži R1 in čaka na R2, kjer R2 pridobi R2, P2 pa R2 in čaka na R1, kjer R1 pridobi P1, v sistemu lahko pride do zastoja in čakanja.

držite in počakajte-primer

Krožno počakaj

Niz procesov naj bi bil v mrtvi točki, če en postopek čaka na vir, ki je dodeljen drugemu procesu in ta postopek čaka na vir, je podobno kot v zgoraj pojasnjenem primeru, ko je v obliki zanke. Kjer P1 čaka na R2 in R2 je dodeljen za P2, P2 pa čaka na R1 in R1, dodeljen za P1, ki je krožna čakalna oblika, če ta pogoj izpolnjuje zastoj.

primer krožnega čakanja

Algoritem zaznavanja mrtvih ključavnic

Primeri, ko procesom dodelimo vire in operacijski sistem ponovno preveri, če se je v sistemu zgodila zastoj ali ne, z uporabo dveh glavnih algoritmov za odkrivanje zastojev, so

• Posamezen primerek
• Več primerkov vrste vira

En primerek

Posamezen primerek je situacija, ko ima sistem posamezne primerke vseh virov. Znan je tudi kot čakanje na algoritem grafa ali graf dodeljevanja virov. Graf razporejanja virov je sestavljen iz nabora procesov in nabora virov, ki sta predstavljena v dveh različnih točkah. Viri v grafu dodeljevanja virov so spremenjeni in so predstavljeni kot čakalna oblika grafa. Če ima čakalna oblika grafa samo procese, ki so predstavljeni kot oglišča, kot je prikazano spodaj, pri čemer

• Graf dodeljevanja virov: Procesi P1, P2, P3 in viri R1, R2, R3 so predstavljeni v grafu razporejanja virov.
• Čakanje na graf: V čakanju na graf so omenjeni samo procesi P1, P2, P3.
• Če obstaja ciklični pogoj, če neprekinjeno teče postopek v eni smeri, to pomeni, da ciklično stanje izstopi in počaka, da je graf v mrtvi točki.

Primer 1: Spodnji primer kaže, da ni stanja mrtve točke, ker ni čakal neprekinjenega toka v čakanju na graf.

en primerek-primer1

2. primer: Stanje mrtve točke se je zgodilo, ker neprekinjeno teče cikel od P1 do P4.

en primerek-primer2

Če se v sistemu zelo pogosto pojavlja zastoj, se algoritem zaznavanja pogosto uporablja. Če se algoritem zaznavanja uporablja več, bo več stroškov in več računskega časa. Da bi to premagali, algoritem prikličemo potem, ko se enak čas poda tako, da se teža grafa uporabi za odkrivanje mrtve točke.

Več primerkov vrste vira

Več primerov vrste virov je situacija, ko ima sistem več primerkov vseh virov, znan je tudi kot algoritem Bankers. Po algoritmu Bankers takoj, ko proces dobi vsa potrebna sredstva, sprosti svoja sredstva.

Upoštevajmo naslednji primer, predpostavimo, da obstajajo 3 procesi P0, P1, P2 in vrsta virov A, B, C, kjer je A mogoče CPU , B je lahko tiskalnik in C lahko tipkovnica. Števke '0' v stolpcu predstavljajo razpoložljivost virov.

Primer (i): Recimo, če vzamemo, da je zahteva za pogoj stanje »000«, ki je prisotna v P0 in P2, bi morali preveriti, katera zahteva je izpolnjena, procesi P0 sprostijo procese po dodelitvi, nato pa se naslednji postopki P2 sprostijo po dodelitvi. Takole v zaporedju vsak po en postopek sprosti P0, P2, P3, P1, P4 v zaporedju. Na koncu dobimo razpoložljive vire kot P7, P2, P6. Razpoložljivo zaporedje je stanje, ko ni blokade.

bankirji-algoritem-primer1

Hiše (ii): Recimo, če je P2 001 namesto 000, zdaj uporabite algoritem bankirja, da preverite stanje blokade, kjer se med vsemi 5 procesi izvede samo P0. Zato so P1, P2, P3, P4 v zastoju, razen za P0.

bankirji-primer2

Aplikacije Deadlock

Vloge zastojev je mogoče razložiti s sprotnim primerom spletnih rezultatov izpitov, kjer več študentov poskuša dostopati do svojega univerzitetnega spletnega mesta ob izdaji. Opazimo lahko, da se včasih spletna stran ne naloži hkrati na več uporabnikov, kar je zastoj. To je mogoče odpraviti s katerim koli algoritmom.

Prednosti

Prednosti mrtve točke so

• Pri izogibanju blokadi ni opaziti predplačila
• Brez zamude v postopku

Slabosti

Slaba stran mrtve točke je

• Vir, ki ga je treba uporabiti, mora biti znan vnaprej
• Blokada postopka za dolgo časa
• Predkupne izgube se podedujejo.

V tem članku je opisano, kako pride do zastoja, če obstajata dva ali več postopkov in trije pogoji, ki povzročajo zastoj, ter dve vrsti algoritmov, in sicer algoritem za delitev virov, ki zazna, da obstaja stanje mrtve točke in algoritem bankirjev, ki je algoritem za izogibanje zastojem. Tu je vprašanje 'Kaj se zgodi, če se zastoj ne upošteva?'.