Aritoni Ovidiu Sisteme de operare 1 Introducere

C. Algoritmul strutului

Cea mai simpla metoda de abordare este algoritmul strutului: iti bagi capul in nisip si te prefaci ca nu exista nici o problema. Oamenii reactioneaza diferit fata de aceasta strategie. Matematicienii o gasesc inacceptabiala si spun ca impasurile trebuie prevenite prin orice mijloace. Inginerii intreaba cat de des eroneaza sistemul din alte motive si cat de grav este un impas. Daca impasurile apar, in medie o data la 50 de ani dar sistemul se prabuseste datorita erorilor de hardware, erori de compilare si bug-uri in sistemul de operare care apar o data pe luna majoritatea inginerilor nu ar fi dispusi sa piarda atat de mult din performanta sau avantaje pentru a elimina impasurile.

fig. 3-8. Un exemplu pentru modurile cum apare un impas si felul in care poate fi evitat.
Pentru a face acest contrast si mai specific, UNIX (si MINIX) pot suferi de impasuri care nici nu sunt detectate, ca sa nu mai vorbim de defectiunil automate. Numarul total de procese din sistem este determinat de numarul de intrari din tabla de procese. Astfel, slot-urile de pe tabla de procese sunt resurse limitate. Daca o comanda FORK esueaza din cauza ca tabla e plina, programul respectiv ar trebui sa astepte un timp si apoi sa incerce din nou.

Acum sa presupunem ca un sistem UNIX are 100 de slot-uri pentru procese. 10 programe ruleaza, fiecare dintre ele avand nevoie sa creeze cate 12 sub-procese. Dupa ce fiecare a creat 9 procese, cele 10 procese initiale plus cele 90 de procese nou create au umplut tabla. Avem o situatie de impas deoarece fiecare dintre cele 10 procese initiale asteapta intr-un circuit fara nici un capat. Probabilitatea ca aceasta situatie sa apara este minima, dar este totusi posibil. Ar trebui sa abandonam procesele si comanda FORK pentru a rezolva problema?

Si numarul maxim de fisiere deschise este limitat tot de marimea tablei pentru nod I, astfel ca o problema asemanatoare apare atunci cand acesta se umple. Spatiul de schimbare de pe disk este tot o resursa limitata. De fapt, aproape toate tablele din sistemul de operare reprezinta resurse limitate. Ar trebui sa le anulam pe toate pentru ca se poate intampla ca un numar n de procese sa ceara fiecare 1/n din total, si apoi fiecare sa incerce sa il ceara pe celalalt?

Abordarea UNIX este de a ignora pur si simplu problema presupunand ca majoritatea utilizatorilor ar prefera un impas ocazional in locul unei reguli care sa restrictioneze utilizatorii la un singur proces, un singur fisier deschis, si asa mai departe. Daca impasurile ar putea fi eliminate pe gratis nu ar exista multe discutii pe tema asta. Problema este ca pretul este destul de mare, mai ales in ceea ce priveste restrictionarea proceselor, cum vom vedea mai incolo, lucru care este destul de neplacut. Astfel ca suntem in fata unei situatii neplacute in care trebuie sa alegem intre avantaje si corectitudine si a unei discutii aprinse despre care dintre ele este mai importanta.

D. Detectare si remediere

O a doua tehnica este detectarea si remedierea. Atunci cand este folosita aceasta tehnica sistemul nu face altceva decat sa monitorizeze solicitarile si eliberarile resurselor. De fiecare data cand o resursa este solicitata sau eliberata diagrama de resursa este actualizata si se verifica daca exista vreun ciclu. Daca exista, unul dintre procesele ciclului este omorat. Daca ciclul nu este intrerupt, un alt proces este oorat, si tot asa pana se intrerupe ciclul.

O metoda mai dura este aceea in care nici macar nu se mentine diagrama de resursa, dar se verifica periodic daca exista vreun proces care a fost bloca fara intrerupere timp de o ora, de exemplu. Un astfel de proces este omorat.

Strategia de detectare si remediere este adesea folosita pentru computerele principale mari, in special in sistemele de incarcare in care este acceptabila omorarea si apoi restartarea uni proces. Totusi trebuie sa se aiba grija ca toate fisierele modificate sa fie readuse la starea lor initiala prcum si sa se anuleze oricare alt efect secundar care este posibil sa fi aparut.

E. Prevenirea impasurilor

O a treia strategie pentru impasuri este impunerea unor restrictii adecvate proceselor, astfel incat, din punct de vedere structural un impas sa fie imposibil. Cele patru conditii stabilite de Cauffman et al. (1971) furnizeaza un indiciu pentru posibile solutii. Daca ne putem asigura ca cel putin una din aceste conditii nu este indeplinita niciodata, atunci impasurile sunt imposibile (Havender, 1968).

Mai intai sa analizam conditia excluderii reciproce. Daca nici o resursa nu ar fi alocata doar unui singur proces impasurile nu ar putea sa apara. Totusi, este la fel de clar ca daca permitem ca doua procese sa foloseasca imprimanta in acelasi timp vom crea o stare de haos. Prin spiralarea iesirii de imprimanta, mai multe procese vor putea sa scoata rezultatele in acelasi timp. In acest model singurul proces care cere efectiv imprimanta fizica este daemon-ul de imprimanta. De vreme ce acest daemon nu solicita niciodata alta resursa, putem sa eliminam posibilitatea unui impas in ceea ce priveste imprimanta.

Din pacate, nu toate dispozitivele pot fi spiralate (tabla de procese nu se preteaza la spiralare). In plus, chiar competitia pentru spatiul de disk care poate fi spiralat poate sa duca la impas. Ce s-ar intampla daca ar exista doua procese si fiecare sa umple jumatate din spatiiul de spiralat si n-ar fi incheiat niciunul dintre ele? Daca daemonul ar fi programat sa inceapa printarea chiar inainte ca toate rezultatele sa fie spiralate, se poate ca imprimanta sa nu lucreze daca un proces de iesire ar decide sa astepte cateva ore pana la prima iesire. Din acest motiv, in mod normal daemon-urile sunt programate sa inceapa sa printeze doar cand este disponibil intregul fisier de iesire. Nici un proces nu va termina vreodata, deci avem un impas de disk.

Cea de-a doua conditie formulata de Coffman et al. arata mul mai promitator. Daca putem sa impiedicam procesul care detine resursele sa astepte mai multe resurse, putem sa evitam impasurile. Un mod de a realiza acest lucru este sa cerem proceselor sa solicite resursele inainte de a incepe executarea. Daca toate resursele ar fi disponibile, procesului I-ar fi alocata orice resursa de care are nevoie si ar putea sa ruleze pana la sfarsit. Daca una sau mai multe resurse ar fi ocupate, nimic n-ar fi alocat si procesul ar astepta pur si simplu.

O mare problema a acestui tip de abordare este faptul ca multe procese nu stiu inainte de momentul cand incep sa ruleze de cate resurse vor avea nevoie. O alta problema este aceea ca daca folosim acest mod de abordare resursele nu vor fi utilizate in mod optim. De exemplu, sa ne gandim ca un proces care citeste date de pe o banda de intrare, analizeaza timp de o ora, apoi scrie rezultatul pe banda si il scoate pe plotter. Daca toate aceste resurse ar trebui solicitate dinainte, procesul va ocupa unitatea de iesire pe banda si plotter-ul timp de o ora.

Un mod putin diferit de a nu indeplini conditia “retine si asteapta” este sa cerem procesului care solicita o resursa sa elibereze mai intai, pentru un timp toate resursele pe care le detine. Numai daca aceasta cerere este indeplinita poate procesul sa-si primeasca resursele inapoi.

Abordarea celei de-a treia conditii (fara preemptiune) este si mai putin promitatoare decat a celei de-a doua. Daca unui proces I-a fost alocata imprimanta si se afla in mijlocul printarii rezultatului, vom crea dezordine daca ii luam abuziv imprimanta deoarece plotter-ul de care are nevoie nu este disponibil.

A mai ramas o singura conditie. Asteptarea circulara poate fi eliminata in mai multe moduri. Unul dintre ele este stabilirea unei reguli care sa interzica proceselor sa detina mai mult de o resursa odata. Daca are nevoie de o a doua resursa trebuie sa elibereze prima resursa. Pentru un proces care trebuie sa copieze un fisier foarte mare de pe o banda pe o imprimanta aceasta restricie este inacceptabila.

Un alt mod de a evita asteptarea circulara este furnizarea unei numerotari globale a tuturor resurselor, asa cum se vede in figura 3-9(a). acum regula este urmatoarea: procesele pot sa solicite resurse in orice moment, dar toate solicitarile trebuie facute in ordine numerica. Un proces poate sa solicite intai o imprimanta si apoi o unitate de banda, dar nu poate sa solicite intai un plotter si apoi o imprimanta.

Figura 3-9. (a) Resurse ordonate numeric. (b) O diagrama de resursa.

Cu aceasta regula, diagrama alocarii resurselor nu poate sa aiba cicluri. Sa vedem in figura 3-9(b) de ce acest lucru este valabil si pentru cazul in care exista doua procese. Un impas poate sa apara doar daca A solicita resursa j si B solicita resursa i. Daca presupunem ca i si j sunt resurse diferite, ele vor avea numere diferite de ordine. Daca i>j, atunci A nu are voie sa solicite j. Daca i, atunci B nu are voie sa solicite i. Oricum, un impas este imposibil.

Se procedeaza la fel si in cazul in care exista mai multe procese. In fiecare moment, una dintre resursele alocate va avea pozitia cea mai de sus. Procesul care detine aceasta resursa nu va mai putea sa solicite alta resursa deja alocata. Ori va temina, ori, in cel mai rau caz, va solicita o resursa de pe o pozitie superioara, dintre cele disponibile. In cele din urma va termina si va elibera resursele pe care le detine. In acest moment, alt proces va primi resursa si va putea sa termine si el. Pe scurt, este un scenariu in care toate procesele termina, deci nu apare nici un impas.

O variatie minora a acestui algoritm este sa se ceara ca resursele sa fie obtinute strict in ordine crescatoare si sa insiste doar asupra faptului ca nici un proces sa nu solicite o resursa situata mai jos decat cea pe care o detine deja. Daca, initial un proces solicita resursele 9 si 10, si apoi le elibereaza pe amandoua, efectiv se incepe de la inceput, deci nu exista nici un motiv sa se interzica de acum incolo solicitarea resursei 1.

Desi ordonarea numerica a resurselor elimina problema impasurilor, se poate gasi o ordonare care sa satisfaca pe toata lumea. Atunci cand resursele include si sloturile tablei de procese, spatiul de spiralare al disk-ului, baza de date cu inregistrarile blocate si ale resurse abstracte, numarul resurselor potentiale si utilzarile diferite pot fi atat de numeroase incat nici un fel de ordonare nu ar putea functiona.

Diferitele abordari pentru prevenirea impasurilor sunt rezumate in figura 3-10.

Fig. 3-10. Rezumat al abordarilor folosite pentru prevenirea impasurilor.