Zastoj (pojam, prevencija, detekcija i oporavak zastoja)

Univerzitet u Novom Sadu

Tehnički fakultet „Mihajlo Pupin“

Zrenjanin

SEMINARSKI RAD

predmet: Operativni sistemi

tema:

 Zastoj (pojam, prevencija, detekcija i oporavak zastoja)

Profesor:

  Student:

prof. dr Branko Markoski

           Siniša Mihajlović IT 51/13

                                                                    Smer: Informacione tehnologije
Asistent:
MSc Predrag Pecev

Zrenjanin, 2015. 

1

SADRŽAJ

Predmetni cilj.............................................................................................................................. 2
1. Uvod........................................................................................................................................3
2. Sistemski model i osobine zastoja.......................................................................................... 4

2.1. Uslovi pod kojima nastupa zastoj....................................................................................4
2.2. Graf dodeljenih resursa.................................................................................................... 5

3. Metode upravljanja zastojem – prevencija.............................................................................7

3.1. Prevencija zastoja.............................................................................................................7

4. Izbegavanje zastoja................................................................................................................. 8

4.1. Bezbedna i nebezbedna stanja.........................................................................................8
4.2. Graf dodele resursa za izbegavanje zastoja.....................................................................9
4.3. Bankarski algoritam....................................................................................................... 10
4.4. Bankarski algoritam za jedan resurs..............................................................................12
4.5. Bankarski algoritam za više resursa...............................................................................12
4.6. Nedostaci Bankarskog algoritma...................................................................................13
4.7. Primer upotrebe bankarskog algoritma..........................................................................14

5. Nojev algoritam.................................................................................................................... 15
6. Detekcija i oporavak zastoja.................................................................................................16

6.1. Detekcija u slučaju da resursi imaju samo jednu instancu.............................................16
6.2. Detekcija u slučaju da resursi imaju više instanci.........................................................16
6.3. Korišćenje algoritma za detekciju..................................................................................18
6.4. Oporavak od zastoja.......................................................................................................18

7. Dvo-fazno zaključavanje...................................................................................................... 19
8. Izgladnjivanje........................................................................................................................20
9. Zaključak...............................................................................................................................21
LITERATURA......................................................................................................................... 22

3

1. Uvod

Računarski sistemi imaju dosta resursa koji istovremeno ne mogu biti korišćeni od strane više 
procesa.   Prost   primer   su   štampači,   magnetne   trake   i   zapisi   u   unutrašnjim   sistemskim 
tabelama. Ako dva procesa istovremeno pristupaju štampaču dolazi do zabune, takođe ako 
dva procesa koriste isti zapis sistemske tabele dolazi do greške sistema fajliranja. Usled toga 
svaki operativni sistem ima mogućnost trenutnog dodeljivanja ekskluzivnog prava procesu za 
pristup određenim resursima.

Kod mnogih aplikacija proces mora imati ekskluzivni pristup ne samo jednom već nekoliko 
resursa. Na primer, dva procesa koji imaju isti zadatak: da snime skeniran dokument na CD. 
Proces A traži dozvolu za upotrebu skenera i dobija je. Proces B, koji je programiran na drugi 
način, traži prvo dozvolu za upotrebu CD snimača i takođe ju dobija. Sada A traži dozvolu za 
upotrebu CD pisača, ali zahtev se odbija sve dok B ne oslobodi CD pisač. Međutim, B umesto 
da   oslobodi   CD   pisač,   traži   dozvolu   za   upotrebu   skenera.   U   ovom   trenutku   procesi   su 
blokirani i tako će ostati u nedogled. Ova situacija naziva se zastoj (deadlock).

Zastoji se takođe dešavaju i između više mašina. Mnoge kancelarije imaju lokalnu mrežu 
(LAN) instaliranu na većem broju računara. Često su uređaji (kao što su skeneri, CD pisači, 
štampači i magnetni čitači) povezani u mrežu kao deljeni resursi koji su dostupni svakom 
korisniku na svakom računaru u mreži. Ako se ovi uređaji mogu rezervisati “na daljinu" (tj. sa 
korisnikovog računara) može se pojaviti ista vrsta zastoja. Komplikovanija situacija može 
izazvati zastoje koje uključuju tri, četiri ili više uređaja i korisnika.

Zastoji se mogu pojaviti u raznim situacijama, a ne samo u onim koje uključuju zahteve za 
upotrebu   određenih   ulazno/izlaznih   (I/O)   uređaja.   U   sistemu   baze   podataka,   na   primer, 
program   nekad   mora   da   zaključa   nekoliko   slogova   podataka   koje   koristi,   da   bi   izbegao 
takmičenje nad dozvolom za rad sa tim slogovima. Ako proces A zaključa slog R

1

, a proces B 

zaključa slog R

2

, i zatim svaki proces pokušava da zaključa slog onog drugog, tada se takođe 

desi   zastoj.   Znači   zastoj   se   može   pojaviti   kako   na   hardverskim   resursima   tako   i   na 
softverskim. 

[3]

Više   procesa   se   u   višeprocesnom   okruženju   mogu   međusobno   takmičiti   za   konačan   broj 
resursa. Resurse zahteva proces, i kada resurs nije raspoloživ, proces će ući u stanje čekanja 
na resurs (WAIT) i blokira se. Ako potrebni resurs ostane neraspoloživ blokirani proces može 
zauvek ostati u tom stanju. To se može desiti ako je resurs prethodno dodeljen na korišćenje 
drugom procesu koji tokom vremena prelazi u stanje čekanja na drugi neraspoloživ resurs. 
Ova situacija se naziva zastoj, tj. blokada. Pri radu sa savremenim višenitnim procesima 
pojava je moguća, i treba je izbeći. Onaj sistem koji je doveden u stanje zastoja mora se 
oporaviti. 

[1]

Na primer:

„Potreban je novac da bi zaradili novac“.

„Ne može se dobiti posao bez iskustva, iskustvo se ne može dobiti bez posla“.

Uzrok zastoja je: Svakom procesu je potrebno što drugi proces ima. To proističe iz deljenja 
memorija i uređaja. Resurs je sve što se može koristiti od strane jednog procesa u svakom 
deliću vremena. 

[2]

4

2. Sistemski model i osobine zastoja

Konkurentne procese koristi konačan broj resursa koji čine sistem. Konkurentni procesi su 
memorijski   prostor,   procesor,   datoteke,   ulazno-izlazni   uređaji.   Jedna   ili   više   identičnih 
instanci čini svaki resurs. Procesor je resurs sa dve instance kada server ima dva procesora. 
Ako proces zahteva više instanci, a resurs ima više instanci, i ako se dodeli bilo koja slobodna  
instanca ona će zadovoljiti proces.

Pre korišćenja proces zahteva resurs, a posle korišćenja mora osloboditi resurs. Više različitih 
resursa može da zahteva jedan proces, a teorijski, i sve resurse koje poseduje sistem. Proces u 
normalnom režimu rada može da koristi resurse na sledeći način:



Zahtev, u ovoj fazi proces zahteva resurs. Zahtev za dodelu resursa ako nije u stanju 
da se trenutno ispuni, proces mora da čeka dok se resurs ne oslobodi.



Korišćenje, u ovoj fazi proces je dobio resurs i može ga slobodno koristiti.



Oslobađanje, nakon što se resurs koristio, proces mora da oslobodi resurs.

Ako svaki proces drži resurs skup procesa je u zastoju, a nov resurs koji drži neki drugi proces 
iz skupa traži se na korišćenje. U takvoj situaciji niko ne oslobađa svoje resurse, a traži nove – 
skup tih procesa se zaglavljuje. Na primer (Slika 1.), sistem ima jedan štampač i jednu traku. 
Proces P

1

 je dobio traku, a P

2

 je dobio štampač. Ako P

1

 zatraži štampač, a da pri tome nije 

oslobodio traku, a P

2

 zatraži traku, a prethodno nije oslobodio štampač, tada procesi P

1

 i P

2 

ulaze u zastoj. Nikada ne završavaju svoje aktivnosti i ne oslobađaju resurse, oni procesi koji 
su u zastoju. 

[5]

Slika 1. Sistem sa jednim štampačom i jednom trakom

2.1. Uslovi pod kojima nastupa zastoj

Ako su istovremeno ispunjeni sledeći uslovi tada zastoj nastupa:

1. Međusobno isključenje

U   jednom   trenutku   samo   jedan   proces   može   da   koristi   resurs   ili   jednu   njegovu 
instancu. Drugi proces koji zahteva taj isti resurs ili instancu, mora da čeka dok se 
resurs ne oslobodi.

2. Nema pretpražnjenja

Sve dok proces koji koristi resurs ne završi posao i ne oslobodi resurs, taj resurs se ne 
može nasilno oduzeti i predati drugom procesu.

6

Skupovi objekata su P = {P

1

, P

2

, P

3

} i R = {R

1

, R

2

, R

3

, R

4

}. Resursi R

1

, R

2

, R

3

 i R

4

 imaju 1, 2, 

1 i 3 instance. Skup strelica je E = {P

1

->R

1

, P

2

->R

3

, R

1

->P

2

, R

2

->P

2

, R

2

->P

1

, R

3

->P

3

, P

3

->R

2

}. 

Stanja procesa su sledeća: P

1

  koristi jednu instance resursa R

2

, a čeka na jednu instancu 

resursa R

1

. P

2

 koristi jednu instancu resursa R

1

 i R

2

, a čeka na jednu instance resursa R

3

. P

3 

koristi jednu instance resursa R

3

, a čeka na jednu instance resursa R

2

. Na ovom grafu postoje 

dve kružne putanje koje mogu izazvati zastoj:



P

1

->R

1

->P

2

->R

3

->P

3

->R

2

->P

1



P

2

->R

3

->P

3

->R

2

->P

2

Zaključak je da su procesi P

1

, P

2

 i P

3

 najverovatnije u zastoju, jer



proces P

2

 čeka na resurs R

3

, koji drži proces P

3

;



proces P

3

 traži resurs R

2

, koji drže procesi P

1

 i P

2

;



procesi P

2

 i P

3

 su blokirani zbog resursa R

3

;



proces P

1

, koji bi tada jedini mogao da oslobodi resurs R

2

, blokiran je zbog procesa P

2 

koji drži resurs R

1

.

Graf sa kružnim tokom ne znači obavezno zastoj. Kružni tok P

1

->R

1

->P

3

->R

2

->P

1 

je prikazan 

na grafu (Slika 3.). 

[1]

[4]

Slika 3. Graf dodele resursa – kružni tok bez zastoja