Aritoni Ovidiu Sisteme de operare 1 Introducere

A. Resurse

Impasurile pot aparea atunci cand proceselor le-a fost garantat acces exclusiv la fisiere dispozitive etc. Pntru a generaliza cat mai mult discutia despre impasuri ne vom referi la obiectele garantate ca resurse. O resursa poate fi un dispozitiv hardware (o banda) sau o informatie (o inregistrare blocata dintr-o baza de date). In mod normal un computer poate avea mai multe resurse diferite care pot fi obtinute. Pentru unele resurse pot fi disponibile mai multe exemplare identice asa cum este unitatea cu trei benzi. Cand sunt disponibile mai multe copii ale unei resurse oricare din ele poate fi folosita pentru a satisface orice cerere de resurse. Pe scurt numim resursa orice care poate fi folosit la un moment dat de un singur proces.

Resursele sunt de doua feluri: preemptibila si nepreemptibila. O resursa preemptibila este una care poate fi luata procesului care o foloseste fara efecte secundare pentru acesta. Memoria este un exemplu in acest sens. Ganditi-va, de exemplu la un sistem cu memorie utilizabila de 512k, o imprimanta, si doua procese de 512k ambele dorind sa printeze ceva. Procesul A cere si primeste imprimanta, apoi incepe sa calculeze valorile care trebuie printate. Inainte ca el sa termine calculul ii expira quantum-ul si este schimbat.

Acum ruleaza procesul B si incearca fara sa reuseasca, sa obtina imprimanta. Acum avem o potentiala situatie de impas deoarece A are imprimanta si B are memoria si nici unul nu poate sa mearga mai departe fara resursa detinuta de celalalt. Din fericire este posibil sa I se ia memoria procesului B prin schimbarea lui cu procesul A. acum A poate sa ruleze, sa printeze si apoi sa elibereze imprimanta; astfel nu apare nici un impas.

O resursa nonpreemptibila este una care nu ii poate fi luata utilizatorului ei curent fara a produce o esuarea a procesului. Daca un proces a inceput sa printeze rezultatul si ii luam imprimanta si o dam altui proces rezulatul va fi deformat. Imprimantele nu sunt preemptibile.

In general impasurile implica resurse nonpreemptibile. Impasurile potentiale care implica resurse preemptibile pot fi rezolvate prin realocarea resursei de la un proces la altul. Astfel analiza noastra se va concentra asupra resurselor nonpreemptibile.

Succesiunea evenimentelor, necesara pentru a folosi o resursa este

1 solicitarea resursei

2 utilizarea resursei

3 eliberarea resursei

Daca resursa nu este disponibila in momentul solicitarii procesul de solicitare este nevoit sa astepte. La unele sisteme de operare procesul este blocat automat in momentul in care o solicitare de resurse esueaza si este repornit in momentul in care este disponibila. La alte sisteme solicitarea esueaza cu un cod de eroare, si procesul apelant trebuie sa astepte un timp si apoi sa reancerce.

B. Principii ale impasului

Impasul poate fi definit astfel:
O serie de procese se afla in impas daca fiecare proces din serie asteapta un eveniment care poate fi cauzat doar de alt proces din serie.
Deoarece toate procesele sunt in asteptare nici unul dintre ele nu va cauza vreodata unul din evenimentele care ar putea sa porneasca oricare alt membru al seriei si astfel, toate procesele asteapta la nesfarsit.

In majoritatea cazurilor evenimentul pe care-l asteapta fiecare proces este eliberarea unei resurse detinuta in momentul respectiv de alt membru al seriei. Cu alte cuvinte fiecare membru al seriei de procese aflate in impas asteapta o resursa care este detinuta de un proces aflat in inpas. Nici unul dintre procese nu poate sa ruleze, nici unul dintre ele nu poate sa elibereze vreo resursa si nici unul nu poate fi repornit. Nu este important numarul proceselor si nici numarul si tipul resurselor detinute si solicitate.

• 
  Conditi de impas
  

Coffman et al. (1971) a aratat ca exista 4 conditii de impas:

1-Conditia de excludere reciproca. Ficare resursa este ori disponibila ori detinuta

in mod curent de un singur proces.

2-Conditia retine si asteapta. Procesele care detin in mod curent resurse garantate

anterior pot sa solicite noi resurse.

3-Conditia de nepreemtiune. Resursele garantate date anterior nu pot fi luate

abuziv unui proces. Ele trebuie sa fie in mod explicit eliberate de catre procesul

care le detine.
4-Conditia asteptarii circulare. Trebuie sa existe o inlantuire de doua sau mai

multe procese fiecare dintre ele asteptand o resursa detinuta de urmatorul membru

al inlatuirii.
Toate aceste 4 conditii trebuie sa fie prezente pentru ca un impas sa apara. Daca una sau mai multe dintre aceste conditii nu apare impasul nu este posibil.

• 
  Modelarea impasului
  

Holt(1972) a aratat ca aceste 4 conditii pot fi modelate folosind diagramele directionale. Diagramele au 2 tipuri de noduri: procese, reprezentate ca cercuri si resurse reprezentate prin patrate. Un arc de la un nod de resurse (patrat) la un nod de proces (cerc) arata ca resursa a fost solicitata anterior, acordata si momentan este detinuta de procesul respectiv. In figura 3-7(a) resursa R este acordata procesului A in acest moment.

Fig 3-7. Diagrama alocarii resurselor. (a) detinerea unei resurse. (b) solicitarea unei resurse. (c) impas.

Un arc de la un proces la o resursa arata ca procesul este blocat in momentul actual si asteapta resursa respectiva. In figura 3-7(b) procesul B asteapta resursa S. in figura 3-7(c) vedem un impas: procesul C asteapta resursa T care este detinuta in mod curent de procesud D. Procesul D nu este pe punctul de-a elibera resursa T deoarece asteapta resursa U, detinuta de C. Ambele procese vor astepat la nesfarsit. Un ciclu in diagrama arata ca exista un impas in care sunt implicate procesele si resursele din ciclu. In acest exemplu ciclul este C-T-D-U-C.

Acum sa vedem un exemplu despre modul de folosire al diagramelor de resurse. Avem 3 procese A,B si C si 3 resurse R,S si T. Solicitarile si eliberarile celor 3 procese sunt date in figura 3-8(a)-(c). Sistemul de operare este liber sa ruleze in orice moment orice proces care nu este blocat astfel ca ar putea decide sa ruleze A pana A isi termina sarcina, apoi sa ruleze B pana la sfarsit si, in final C.

Aceasta ordonare nu duce la nici un impas (deoarece nu exista competitie pentru resurse) dar nici paralelism nu exista. Pe langa solicitarea si eliberarea de resurse, procesele calculeaza si fac I/O. atunci cand procesele sunt rulate secvential nu exista posibiliatatea ca, in timp ce un proces asteapta I/O altul sa poata folosi procesorul. De aceea se poate ca rularea proceslor strict secvential sa nu fie cea mai buna alegere. Pe de alta parte daca nici unul din procese nu face deloc I/O algoritmul “intai cea mai scurta sarcina” este preferabil in locul celui circular astfel ca in unele conditii rularea secventiala a tuturor proceselor poate fi cea mai buna alegere.

Sa presupunem acum ca procesele fac atat I/O cat si calculare astfel ca algoritmul circular este un mod de temporizare rezonabil. Solicitarile de resursa ar putea aparea in ordinea din figura 3-8(d). Daca aceste 6 cereri sunt indeplinite in aceasta ordina cele 6 diagrame care rezulta sunt aratate in figura 3-8(e-j). Dupa ce solicitarea 4 a fost facuta A se blocheaza asteptan S ca in figura 3-8(h). In urmatorii 2 pasi si B si C se blocheaza, in cele din urma ducand la un ciclu si la impasul din figura 3.8(j).

Totusi dupa cum am mentionat deja sistemului de operare nu I se cere sa ruleze procesele intro ordine anume. In particular, daca satisfacerea unei anumite cereri poate duce la impas sistemul de operare poate sa suspende pur si simplu procesul fara sa-I indeplineasca cererea (adica sa nu includa procesul in temporizare) pana la un moment favorabil. In figura 3-8 daca sistemul de operare ar sti despre iminenta impasului ar putea sa-l suspende pe B in loc sa-I acorde acestuia S. Daca rulam doar A si C vom obtine solicitarile si eliberarile din figura 3-8(k) in loc de cele din figura 3-8(d). aceasta secventa duce la diagrama de resursa din figurile 3-8(l-q), care nu duc la impas.

Dupa pasul (q) procesului B ii poate fi acordat S deoarece A a terminat si C are tot ceea ce ii trebuie. Chiar daca B s-ar bloca in momentul solicitarii T, nu poate sa apara un impas. B va astepta pana C termina.

Mai tarziu in acest capitol von studia un algoritm detaliat folosit pentru luarea deciziilor de alocare care nu duc la impas. Ceea ce trebuie sa intelegem acum este ca diagramele de resurse sunt un instrument care ne permite sa vedem daca o secventa cerere/eliberare data duce la impas. Pur si simplu ducem la bun sfarsit pas cu pas solicitarile si eliberarile si dupa fiecare pas verificam diagrama pentru a vedea daca nu contine un ciclu. Daca acest lucru se intampla avem un impas; daca nu, nu exista nici un impas. Desi aceasta analiza a diagramelor de resursa a fost facut pentru cazul in care exista o singura resursa din fiecare tip, diagramele de resursa pot fi si ele generalizate pentru a se ocupa de mai multe resurse de acelasi tip (Holt,1972).

In general exista 4 strategii de rezolvare a impasurilor.

1.Pur si simplu sa se ignore problema

2.Detectare si remediere

3.Evitarea dinamica prin atenta alocare a resursei

4.Prevenirea prin negarea structurala a uneia dintre cele 4 conditii necesare pentru producerea impasului.

In urmatoarele 4 sectiuni vom analiza pe rand fiecare din aceste metode.