Vikigimnazijalac:Operativni sistemi/Detekcija zaglavljivanja

Detekcija zaglavljivanja je koncept koji dopušta da do zaglavljivanja dođe, pa se tek onda primenjuju mere da se takva situacija otkloni.Otkrivanje da je do zaglavljivanja došlo može da bude aktivno i pasivno. Aktivno otkrivanje je pristup u kome se korišdenjem algoritama proverava da li je do zaglavljivanja došlo.Pasivni pristup podrazumeva da se provera vrši samo kad u sistemu nema aktivnosti, ili se registruje da nešto nije u redu.

DETEKCIJA U SLUČAJU DA RESURSI IMAJU JEDNU INSTANCU

Ako svi resursi imaju samo jednu instancu, primenjuje se algoritam za detekciju zastoja koji koristi specijalan graf čekanja na resurse (wait-for graph). Graf čekanjase konstruiše od grafa dodeljenih. Pravila konstrukcije grafa su sledeća:

čvorovi grafa su samo procesi (nema resursa) i
strelice se crtaju samo između procesa koji čekaju jedan drugog za resurse.

Postojanje zastoja utvrđuje se ispitivanjem postojanja kružnih tokova: ako kružni tok postoji, to je zastoj. Dakle, algoritam se periodično poziva da ispita postojanje kružnih tokova, za šta je potrebno n2 operacija, pri čemu je n broj strelica u grafu čekanja. Stanje sistema se može prikazatigrafovima. Čvorovi ovakvih grafova suprocesi (crtamo krugove) i resursi (crtamo pravougaonik).

Grane grafova su oznake da li neki proces drži resurs, što se označava strelicom od resursa ka procesu. Dok strelica od procesa karesursu označava da li neki proces zahteva taj resurs, ali ga trenutno ne drži.

DETEKCIJA U SLUČAJU DA RESURS IMA VIŠE INSTANCI

Algoritam za detekciju pomoću grafa čekanja nije pogodan za korišćenje ukoliko resursi imaju više instanci. U tom slučaju koristi se algoritam sličan bankarskom. Najpre ćemo uvesti sledeće strukture podataka:

Vektor rapoloživosti: available[j], j∈[0,m]. Ako je available[j]=k, tada je k instanci resursa Rj rasploživo.
Matrica alokacije: allocation[n,m]. Ako je allocation[i,j]=k, tada je proces Pi trenutno dobio k instanci resursa Rj.
Matrica trenutnih zahteva request[n,m]. Matrica ukazuje na trenutne zahteve procesa. Ako je request[i,j]=k, tada proces Pi trenutno traži k instanci resursa Rj.

Algoritam funkcioniše na sledeći način: Neka su work i finish vektori dužine m i n, respektivno:

U ovom koraku svi procesi koji imaju bilo kakve resurse se obeležavaju kao nezavršeni, a u protivnom ispadaju iz algoritma work = available for i = 1,2, …, n if allocationi ≠ 0 then finish[i]=0; else finish[i]=1.
U ovom koraku nalazi se proces koji može da zadovolji sve svoje potrebe i završi aktivnost, odnosno proces za koji važi: finish[i]=0 (2.b) requesti ≤ work. Ako nema takvih procesa, idi na korak 4.
U ovom koraku se resursi procesa vraćaju u sistem. work = work + allocationi finish[i]=1.Idi na korak 2.

Ako je finish[i]=0, za bilo koje i∈[1,n], tada je sistem u stanju zastoja. Preciznije, ako je finish[i]=0, tada je proces Pi u zastoju. Algoritam zahteva m x n2 operacija da bi ustanovio da li je sistemu stanju zastoja.

Kada se primeni algoritam za detekciju, može se dokazati da postoji sekvenca koja dovodi do rezultata finish[i]=1 za sve procese, što znači da sistem neće biti doveden u stanje zastoja. Interesantno je da sistem u trenutku t0 nema raspoloživih resursa, ali da se počevši od procesa koji najmanje traže (P0 i P2) može obaviti dodela resursa bez dovođenja do zastoja. Međutim, dovoljno je da proces P2 traži jednu instancu resursa C i sistem će biti doveden u stanje zastoja. Dokazaćemo to primenom prethodno opisanog algoritma za detekciju: proces P0 ima najmanje prohteve, i ako bi završio svoje aktivnosti i vratio resurse, stanje raspoloživih resursa bi bilo (0,1,0) nakon čega nemamo proces koji može da zadovolji svoje potrebe. Znači sistem je u stanju zastoja - procesi P1, P2, P3, i P4 su zaglavljeni.

KORIŠĆENjE ALGORITMA ZA DETEKCIJU

Učestanost pozivanja algoritma za detekciju zastoja zavisi od toga učestanosti pojave zastoja i prosečnog broja procesa zahvaćenog zastojem. Sa jedne strane, zastoj se mora detektovati na vreme jer su svi procesi (a samim tim i resursi koje procesi koriste) zaglavljeni, ali kako detekcija konzumira dosta vremena, algoritam se ne sme pozivati često.