Controlul alocarii resurselor la procese concurente - sincronizarea executiei proceselor

Resursele existente intr-un sistem pot fi alocate proceselor in mai multe moduri, in functie de tehnica de exploatare a sistemului folosita:

• prin alocarea tuturor resurselor la un singur proces, pe toata durata executiei sale, ca in cazul monoprogramarii
• prin alocarea in comun a resurselor, la mai multe procese in executie, oferind fiecarui proces cate un segment de timp pentru utilizarea resursei, segmente de timp egale pentru toate procesele sau diferite intre ele, alocare numita multiplexarea resurselor, ca in cazul exploatarii in time-sharing
• prin partajarea resurselor, ca in multiprogramare, adica alocand o resursa solicitata de proces in masura disponibilitatii sale si eliberand-o numai dupa utilizarea ei completa
• permitand accesul concurent la resurse, cu concursul sistemului de intreruperi, ca in cazul exploatarii in timp real, pentru alocarea rapida a resurselor solicitate si eliberarea rapida a celor care nu mai sunt utilizate.

Sistemul de reguli dupa care este luata decizia de alocare a resurselor la un proces se numeste algoritm de alocare; acesta trebuie sa aiba in vedere atat utilizarea eficienta a resurselor sistemului cat si reducerea timpului de raspuns al sistemului la solicitarile proceselor.

Problema impasului este o problema legata de alocarea in comun a unor resurse la mai multe procese concurente; ea poate aparea intre procese a caror executie este conditionata de utilizarea exclusiva a acelorasi resurse.

Sa consideram exemplul a doua procese care folosesc aceleasi doua fisiere. Avem in vedere faptul ca, pentru a fi actualizat, un fisier trebuie deschis pentru acces exclusiv. Daca primul proces trebuie sa deschida, pentru actualizare, doua fisiere F1 si F2 iar al doilea proces trebuie sa utilizeze, tot in regim exclusiv, fisierele F2 si F1, poate aparea situatia in care, in fiecare proces, a fost deschis exclusiv primul fisier si se asteapta sa poata fi deschis exclusiv si al doilea fisier. In acest caz, apare o asteptare circulara a celor doua procese, pentru eliberarea resursei solicitate, care este alocata exclusiv celuilalt proces. Aceasta asteptare circulara poarta numele de impas; ea poate dura un timp nedefinit de lung si nu poate fi intrerupta din interiorul proceselor, daca acestea nu au prevazuta o procedura de exceptie, care sa se execute in cazul in care o cerere a procesului nu poate fi satisfacuta.

Impasul (interblocarea proceselor) este o stare grava care poate duce la un blocaj in functionarea sistemului de calcul si care trebuie avuta in vedere si prevenita de catre sistemul de operare.

Conditiile de aparitie a impasului sunt:

• exista un lant de procese in care fiecare dintre ele asteapta eliberarea unei resurse utilizate de alt proces din lant (conditia de cerere de alocare circulara)
• procesele solicita controlul exclusiv al resurselor pe care le utilizeaza (conditia de excludere mutuala a proceselor)
• procesele pastreaza resursele alocate deja, atunci cand asteapta alocarea altor resurse (conditia de asteptare a alocarii resurselor)
• resursele nu sunt eliberate de procesele la care au fost alocate pana nu au fost utilizate complet (conditia de nepreemptie).

Exista mai multe metode de prevenire a impasului:

• metoda prealocarii resurselor: procesul trebuie sa ceara toate resursele necesare cand solicita incarcarea in sistem; cu metode de detectie a impasului, sistemul verifica daca exista riscul aparitiei unui impas; daca nu, procesul este incarcat, in cazul in care toate resursele solicitate sunt disponibile; daca nu sunt disponibile toate resursele solicitate, procesul asteapta indeplinirea conditiilor de mai sus;
• metoda alocarii controlate a resurselor: procesele trebuie sa declare de la inceput toate resursele care le sunt necesare; procesele sunt lansate in executie, chiar daca nu sunt disponibile toate resursele; alocarea resurselor se face controlat, urmarindu-se evitarea impasului; in cazul in care aparitia impasului este iminenta in momentul alocarii unei noi resurse, se blocheaza procesul care a solicitat resursa pana cand se depaseste iminenta impasului.

Detectarea aparitiei unui impas este prima problema la care trebuie sa raspunda un sistem de operare care nu are implementat un mecanism de prevenire a impasului. Este de dorit ca, odata cu detectarea unui impas, sa se identifice si procesul care a produs impasul.

Iesirea din impas se face, de regula, destructiv, prin una din metodele urmatoare:

• se reseteaza sistemul de calcul, fapt care duce la intreruperea fortata a tuturor proceselor din sistem; aceasta este metoda cea mai radicala, prin aplicarea careia se pierd rezultatele intermediare ale tuturor proceselor in executie din sistem
• se alege un proces prin a carui distrugere se inlatura impasul si se distruge acest proces, in cazul in care sistemul de operare dispune de modalitati de detectare a procesului care a generat impasul; in acest caz, se pierd numai rezultatele intermediare ale executiei procesului care se distruge
• daca procesul care va fi distrus este prevazut cu puncte de reluare, atunci el va putea fi reluat din punctul cel mai apropiat de stadiul curent al executiei sale. Un punct de reluare este o imagine a stadiului executiei procesului, la un moment dat. Crearea punctelor de reluare pentru procesele din sistem implica operatii suplimentare, inclusiv in proiectarea programului care se executa, si consum suplimentar de resurse.

Facem observatia ca dezactivarea si reluarea executarii unui proces, generata sub controlul sistemului de intreruperi, se deosebeste de utilizarea punctelor de reluare a unui proces care va fi distrus si apoi relansat in executie. In cazul intreruperii, procesul trece din starea RUN in starea READY, din care poate fi reactivat ulterior, in acelasi context de lucru; in cazul utilizarii punctelor de reluare, se distruge procesul si, practic, se lanseaza in executie un alt proces care trebuie sa continue procesul distrus, incepand de la punctul de reluare.

Sincronizarea executiei proceselor

Sincronizarea proceselor este necesara in activitatea de gestionare a proceselor, in cazul in care executia anumitor procese trebuie blocata, pana la producerea unor evenimente generate de alte procese. Problema sincronizarii poate sa apara:

• in legatura cu utilizarea in comun a resurselor intre procese concurente, pentru alocarea automata a resurselor
• in cazul proceselor concurente in care executia unui proces este conditionata de rezultatul executiei altui proces
• in cazul comunicarii intre procese, in scopul realizarii unei comunicari corecte.

Sincronizarea proceselor reprezinta inlantuirea automata a starilor unor procese concurente, prin blocarea si deblocarea automata a proceselor in executie.

Mecanisme de sincronizare a proceselor

1. Mecanismele de sincronizare pentru partajarea resurselor intre procese concurente isi propun gestionarea operatiei de alocare a unei resurse la procese, astfel incat, la eliberarea resursei, procesul care a solicitat resursa sa fie trecut automat din starea WAIT in starea READY, in vederea alocarii resursei solicitate.

Fiecarei resurse ii poate fi asociat cate un bit indicator al starii de ocupare a resursei (lock-bit). Mecanismul de utilizare a bitilor indicatori este urmatorul:

• prin conventie, bitul indicator este setat pe 0, daca resursa este disponibila, respectiv pe 1, daca resursa este alocata altui proces;
• inainte de a aloca o resursa unui proces, se verifica starea lock-bit -ului:
• daca valoarea este 0, procesul are acces la resursa si se seteaza bitul pe 1, pana la incheierea utilizarii resursei de catre proces, cand bitul se reseteaza pe 0 si resursa devine disponibila;
• in cazul in care bitul este 1, procesul ramane in asteptare, sistemul executand verificarea periodica a lock-bit -ului, pana cand acesta devine 0 si procesului i se poate aloca resursa.

Inconvenientul acestei metode consta in faptul ca, desi procesul este in starea WAIT, procesorul este afectat procesului pentru testarea valorii din lock-bit (procesorul executa in mod repetat o aceeasi instructiune de testare a starii bitului indicator); ar fi preferabil ca, pe timpul cat procesul asteapta, procesorul sa fie eliberat, pentru a putea executa alte sarcini, pentru alte procese din sistem.

Inconvenientul metodei prin utilizarea bitilor indicatori poate fi depasit prin crearea unei liste cu toate procesele in asteptare pentru o resursa; introducerea si extragerea proceselor din lista poate fi gestionata automat, cu ajutorul unui bit semafor s, gestionat de functiile pereche pentru alocare A() si pentru dezalocare D(). Modul de functionare al acestui mecanism este urmatorul:

• pentru fiecare resursa partajata din sistem exista un bit semafor s si o lista a proceselor in asteptare, pentru alocarea resursei
• bitul semafor s este setat initial la valoarea 1
• functia de alocare asociata resursei este executata cand un proces solicita alocarea resursei; functia decrementeaza bitul s si aloca resursa procesului numai daca valoarea bitului s este 0; in caz contrar, procesul este trecut in coada de asteptare
• functia de dezalocare asociata resursei este executata cand un proces elibereaza resursa; functia incrementeaza bitul s si scoate din coada primul proces caruia ii aloca resursa numai daca valoarea bitului s este negativa sau 0; in caz contrar, bitul s are valoarea 1, deci coada de asteptare este goala.

In cadrul acestui algoritm se observa faptul ca variabila semafor este resursa critica pentru functiile de alocare si de dezalocare iar cele doua functii sunt sectiuni critice pentru procese; in consecinta, executia celor doua functii nu trebuie blocata si asupra variabilei semafor nu trebuie sa actioneze, la un moment dat, decat una dintre aceste functii.

Mecanismele de sincronizare directa, prin comunicarea intre procese, utilizate pentru procese concurente, pentru care executia unui proces este conditionata de rezultatul executiei altor procese, sau pentru procese care fac schimb de informatii:

1. Cu ajutorul unor functii primitive ale sistemului de operare, care permit deblocarea unui proces care a intrat in starea de asteptare, cu functii de tipul WAIT() pentru un eveniment, de catre un alt proces, care executa o functie de setare a indicatorului de eveniment respectiv. Concomitent, se poate realiza si schimbul de date intre cele doua procese, utilizand directive ale sistemului de operare de tipul SEND(proces destinatar,adresa mesaj) si RECEIVE(adresa mesaj); comunicarea are loc in momentul in care procesul expeditor lanseaza comanda SEND(), urmata de executia comenzii RECEIVE() de catre procesul destinatar; pentru unele sisteme de operare, directivele SEND si RECEIVE opereaza si asupra indicatorilor de eveniment, pentru sincronizarea proceselor;
2. Prin intermediul cutiilor postale, care sunt zone de buffer in memoria interna, destinate comunicarii intre procese; un proces creaza o cutie postala in care depune informatii care pot fi extrase de celelalte procese. Conditia unei comunicari corecte este ca mesajele transmise sa poata fi preluate integral, corect si in ordinea in care au fost produse. In gestionarea comunicatiei prin aceasta metoda trebuie avute in vedere restrictiile determinate de:

• capacitatea limitata a bufferului: expeditorul poate incearca sa expedieze mai multe mesaje decat poate memora bufferul; in acest caz exista posibilitatea ‘acoperirii’ mesajelor, inainte ca ele sa fie preluate;
• vitezele diferite ale proceselor expeditor si destinatar: destinatarul poate sa preia mai repede mesajele decat le poate depune expeditorul; in acest caz exista posibilitatea preluarii repetate a unui mesaj.

Regula de sincronizare a proceselor, in cazul comunicarii prin intermediul cutiilor postale, trebuie sa respecte conditiile:

• mesajele trebuiesc preluate din buffer in ordinea in care au fost scrise
• numarul mesajelor transmise si nereceptionate trebuie sa nu depaseasca numarul mesajelor care pot fi memorate in buffer
• numarul mesajelor receptionate nu trebuie sa depaseasca numarul mesajelor emise.