Aritoni Ovidiu Sisteme de operare 1 Introducere

Solutionarea problemei producator-cosumator cu ajutorul semafoarelor

Semafoarele rezolva problema repornirilor pierdute, asa cum se vede in figura 2-12. este foarte important ca acestea sa fie implementate ca indivizibile. In mod normal ele se implementeaza apeluri ale sistemului, cu sistemul de operare dezactivand pentru foarte scurt timp toate intreruperile in timp ce testeaza semaforul, o actualizeaza si trece procesele in stare de repaus, daca este necesar. Deoarece toate aceste actiuni au nevoie doar de cateva instructiuni, dezactivarea intreruperilor nu cauzeaza nici o problema. Daca se utilizeaza mai multe procesoare, fiecare semafor ar trebui protejata de o variabila de blocare, utilizandu-se instructiunile TSL pentru a ne asigura ca semaforul este verificat doar de un procesor odata. Asigurati-va ca intelegeti faptul ca utilizarea TSL pentru a impiedica accesarea semaforului de mai multe procesoare in acelasi timp este diferita de asteptarea activa a producatorului sau a consumatorului ca celalalt sa umple sau sa goleasca buffer-ul. Operatia de semafor dureaza doar cateva microsecunde, in timp ce producatorul sau consumatorul ar putea dura foarte mult.

#define N 100 /* numarul de sloturi in buffer

typedef int semaphore ; /* semafoarele sunt un tip special de intregi

semaphore mutex=1; /*accesul controlerului in regiunea critica

semephore empty=N; /*numarul sloturilor goale de pe buffer

semaphore full=0; /*numarul sloturilor pline de pe buffer
void producer()

{

int item;

while(true) /*true este constanta 1

{

produce_item(&item); /*genereaza ceva pentru a pune in buffer

down(&empty); /*decrementeaza variabila empty

down(&mutex); /*intra in regiune critica

enter_item(item); /*pune noul item in buffer

up(&mutex); /*paraseste regiunea critica

up(&full); /*incrementeaza variabila full

}

}

void consumer()

{

int item;

while(true) /*ciclu infinit

{

down(&full); /*incrementeaza variabila count

down(&mutex); /*intra in regiune critica

remove_item(&item); /*scoate un item din buffer

up(&mutex); /*paraseste regiunea critica

up(&empty); /*incrementeaza variabila empty

consume_item(item); /* face ceva cu itemul

}

}

Fig. 2-12. Problema utilizator-consumator in cazul utilizarii barierelor.
Aceasta solutie utilizeaza trei semafoare: unul numit full pentru numararea slot-urilor pline, unul numit empty pentru numararea slot-urilor goale si unul mutex pentru a se asigura ca producatorul si consumatorul nu acceseaza buffer-ul in acelasi timp. Full este initial 0, empty este initial egal cu numarul de slot-uri din buffer, iar mutex este initial 1. Barierele care incep de la 1 si sunt utilizate de 2 sau mai multe procese pentru a se asigura ca doar unul dintre ele poate sa intre in zona sa critica la un moment dat se numesc semafoare binare. Daca fiecare proces executa o comanda DOWN chiar inainte de a intra in zona sa critica, si o comanda UP imediat dupa iesire, este garantata excluderea reciproca.

Acum ca avem la dispozitie o buna comunicare iterprocesorala, sa ne intoarcem si sa analizam din nou secventa de intrerupere din fig. 2-5. intr-un sistem care utilizeaza semafoare, modul natural de a ascunde intreruperile este asocierea unui semafor, initial setata la 0, pentru fiecare dispozitiv I/O. Imediat dupa pornirea unui dispozitiv I/O, procesul administrator executa o comanda DOWN la semafor asociata, astfel blocandu-se imediat. Cand se produce intrerperea, un remediator al intreruperii executa o comanda UP la semaforul asociat, lucru care face ca procesul relevant sa fie din nou pregatit pentru rulare. In acest model, pasul 6 din figura 2-5 consta in executarea unei comenzi UP la bariera dispozitivului astfel incat la pasul 7 administratorul sa poata rula managerul dispozitivului. Bineinteles, daca in acest moment exista mai multe procese pregatite, administratorul poate sa decida rularea unui proces mai important mai intai. Modul in care se face administrarea il vom analiza mai tarziu in cadrul acestui capitol.

In exemplul din fig. 2-12 am folosit semafoarele in doua moduri diferite. Aceasta diferenta este destul de importanta incat sa merite a fi explicata. Semaforul mutex este utilizata pentru excluderea reciproca. Este astfel proiectata incat sa garanteze faptul ca un singur proces va scrie sau va citi in buffer si variabilele asociate la un moment dat. Excluderea reciproca este necesara pentru evitarea haosului.

Cealalta utilizare a semafoarelor este pentru sincronizare. Semafoarele full si empty sunt necesare pentru a garanta ca anumite secvente de evenimente apar sau nu. In acest caz ele se asigura ca producatorul nu mai ruleaza in momentul in care buffer-ul e plin si ca, de asemenea, consumatorul nu mai ruleaza in momentul cand buffer-ul e gol. Aceasta utilizare este diferita de excluderea reciproca.

Desi seamfoarele sunt cunoscute de mai bine de 25 de ani, inca mai este cercetat modul in care se utilizeaza. Pentru exemplificare vezi (Tai si Carver, 1996).

E. Monitoare

Cu semafoare comunicarea interprocesorala pare usoara, nu? Nici vorba. Priviti mai atent ordinea comenzilor DOWN inaintea introducerii sau scoaterii informatiilor din buffer din fig. 2-12. Sa presupunem ca cele doua comenzi DOWN din codul producatorului ar fi in ordine inversa, astfel ca mutex ar fi scazut inainte de empty si nu dupa el. Daca buffer-ul ar fi plin, producatorul s-ar bloca, cu mutex setat la 0. In consecinta, data urmatoare cand consumatorul ar incerca sa acceseze buffer-ul ar executa o comanda DOWN la mutex, acum setat la 0 si s-ar bloca si el. Ambele procese ar ramane blocate si nu s-ar mai putea lucra nimic. Aceasta situatie nefericita se numeste impas. Vom studia impasurile in amanunt in capitolul 3.

Aceasta problema este subliniata pentru a va arata cat de atenti trebuie sa fiti cand utilizati bariere. Este de ajuns o greseala mica si totul se opreste in lant. Este ca si programarea intr-un limbaj de asamblare numai ca mult mai rau deoarece greselile duc la conditii de competitie, impasuri, si alte forme de comportament neprevazut si unic.

Pentru a usura scrierea corecta a programelor, Hoare (1974) si Brinch Hansen (1975) au propus un nivel mai mare de sincronizare, numit monitor. Propunerea lor era putin diferita, dupa cum se vede mai jos. Un monitor este o colectie de proceduri variabile si structuri de date, toate grupate intr-un tip special de modul sau pachet. Procesele pot sa apeleze procedurile intr-un monitor ori de cate ori doresc, dar nu pot sa acceseze direct structurile interne de date din proceduri declarate exterioare monitorului. Fig. 2-13 ilustreaza un monitor scris intr-un limbaj imaginar, pidgin Pascal.

Monitor example

Integer i ;

Condition c;
Procedure producer(x);

……………………….

………………………

………………………

………………………

end;
Procedure consunner(x);

……………………….

………………………..

……………………….

End;

End monoitor;

Fig. 2-13 Un monitor
Monitoarele au o caracteristica importanta care le face utile pentru realizarea excluderii reciproce: un singur proces poate fi activ intr-un monitor la un moment dat. Monitoarele sunt construite ca limbaje de programare, deci compilatorul stie ca sunt deosebite si ca poate sa trateze apelurile catre procedurile monitorului altfel decat alte proceduri de apel. De obicei, cand un proces apeleaza o procedura de monitor, primele instructiuni ale procedurii vor verifica daca mai exista in mod curent vreun proces aciv in cadrul monitorului. Daca da, procesul apelant va fi suspendat pana celalalt proces paraseste monitorul. Daca nu, procesul poate sa intre.

Compilatorul este cel care trebuie sa implementeze excluderea reciproca la intrarile in monitor, dar in mod obisnuit se foloseste o bariera binara. Deoarece compilatorul si nu programatorul se ocupa de excluderea reciproca este mult mai putin probabil ca ceva sa nu mearga bine. In orice caz, persoana care scrie monitorul nu trebuie sa fie constienti de modul in care compilatorul realizeaza excluderea reciproca. Este suficient sa stie ca prin transformarea zonelor critice in proceduri de monitor nu se va intampla niciodata ca doua procese sa intre in acelasi timp in zonele lor critice.

Desi monitoarele furnizeaza un mod simplu de realizare a excluderii reciproce, dupa cum am vazut mai sus, acest lucru nu este suficient. Mai avem nevoie de un mod de blocare a proceselor in momentul in care acestea nu pot continua. In cazul problemei producator-consumator este destul de usor sa includem in procedurile monitorului toate testele pentru buffer, dar cum ar trebui sa se blocheze producatorul cand gaseste buffer-ul plin?

Solutia consta in introducerea variabilelor de conditie, impreuna cu doua operatii WAIT si SIGNAL. Cand o procedura de monitor descopera ca nu poate merge mai departe (ex. producatorul gaseste buffer-ul plin) executa o operatie de asteptare pe o variabila de conditie, de exemplu, full. Aceasta actiune produce blocarea procesului apelant. De asemenea, permite altui proces sa intre in monitor in acest moment.

Acest alt proces, de exemplu consumatorul, poate sa-si porneasca partenerul aflat in repaus executand operatiunea SIGNAL la variabila de conditie unde asteapta partenerul sau. Pentru a nu avea in monitor doua procese active in acelasi timp avem nevoie de o regula care sa stabileasca ce se intampla dupa SIGNAL. Hoare a propus sa se permita rularea procesului abia repornit si suspedarea celuilalt. Hansen a propus sa se ceara unui proces care a executat un SIGNAL sa paraseasca imediat monitorul. Cu alte cuvinte, o comanda SIGNAL poate sa apara doar ca ultima comanda intr-o procedura de monitor. Vom utiliza propunerea lui Hansen deoarece este mai simpla si mai usor de implementat. Daca operatiunea SIGNAL se executa pe o variabila de conditie pe care asteapta mai multe procese, este repornit doar unul dintre ele, cel stabilit de administratorul sistemului.

Variabilele de conditie nu sunt contoare. Ele nu acumuleaza semnale pentru o utilizare ulterioara, asa cum fac barierele. Astfel daca este semnalata o variabila de conditie unde nu asteapta nici un proces, semnalul este pierdut. Comanda WAIT trebuie sa vina inaintea comenzii SIGNAL. Aceasta regula face ca implementarea sa fie mult mai simpla. In practica nu este o problema deoarece este usor de tinut evidenta starii fiecarui proces cu variabile, daca acest lucru este necesar. Un proces care ar executa o comanda SIGNAL poate sa vada ca acest lucru nu mai este necesar, doar consultand variabilele.

O schema a problemei producator-consumator cu monitoare este data in fig.2-14 in pidgin Pascal.

Poate va ganditi ca operatiile WAIT si SIGNAL arata similar cu SLEEP si WAKEUP, care, dupa cum am vazut mai devreme au dus la conditii fatale de competitie. Ele sunt foarte asemanatoare, dar cu o diferenta foarte importanta: SLEEP si WAKEUP au esuat din cauza ca in timp ce un proces incerca sa intre in repaus celalalt incerca sa-l repporneasca. Cu monitoarele acest lucru nu se poate intampla. Excluderea reciproca automata in cazul monitoarelor garanteaza ca daca, producatorul dintr-o procedura de monitor constata ca buffer-ul e plin va putea sa incheie operatia WAIT fara sa trebuiasca sa-si faca griji in legatura cu posibilitatea ca administratorul sa-l schimbe cu consumatorul chiar inainte de a incheia operatia. Consumatorului nu I se va permite nici macar accesul in monitor pana cand aceasta operatiune nu este incheiata si producatorul nu mai ruleaza.

Monitor ProducerConsummer ;

Condition full ,empty ;

Integer count;
Procedure enter;

Begin

If count =N then wait (full);

Enter item;

Count:=count+1;

If count=1 then signal(empty);

End;
Count:=0;
End monitor;
Procedure producer;

Begin

While true do

Begin

Produce_item;

ProducerConsumer.enter;

End

End;
Procedure consumer;

Begin

While true do

Begin

PorducerConsumer.remove;

Consume_item;

End;

End;

Fig. 2-14. O schita a problemei producator-consumator cu monitoare.

La un moment dat doar o procedura a monitorului poate fi activa.buffer-ul are N slot-uri.

Prin marcarea automata a excluderii reciproce in ceea ce priveste zonele critice, monitoarele fac programarea paralela mult mai putin dispusa la erori decat cu bariere. Totusi, si ele au cateva puncte slabe. Nu degeaba fig. 2-14 este scrisa intr-un tip ciudat de pidgin Pascal si nu in C la fel ca celelalte exemple din aceasta carte. Dupa cum am spus si mai devreme, monitoarele sunt un concept de limbaj de programare. Compilatorul trebuie sa le recunoasca cumva si sa le aranjeze pentru excluderea reciproca. C, Pascal si majoritatea limbajelor de programare nu au monitoare, deci este anormal sa le pretindem compilatoarelor lor sa aplice vreo regula de excludere reciproca. De fapt, cum ar putea sa stie compilatorul care proceduri sunt din monitor si care nu?

Aceleasi limbaje nu au nici bariere, dar adaugarea lor se face foarte usor: nu trebuie decat sa adaugi doua scurte coduri de asamblare bibliotecii pentru a emite apelurile sistem UP si DOWN. Compilatoarele nici nu trebuie sa stie de existenta acestora. Desigur, sistemul de operare trebuie sa stie de existenta barierelor, dar cel putin daca avem un sistem de operare bazat pe bariere tot se pot scrie programe utilizatoare pentru ele in C sau C++ (sau chiar BASIC daca sunteti suficient de masochist). In cazul monitoarelor aveti nevoie de un limbaj care le are incluse. Exista cateva limbaje care le au, cum este Concurrent Euclid (Holt, 1983), dar sunt foarte rare.

O alta problema in ceea ce priveste monitoarele si barierele este aceea ca au fost proiectate sa rezolve problema excluderii reciproce in sisteme cu unul sau mai multe procesoare cu acces la memoria principala. Punand barierele in memoria comuna si protejarea lor cu instructiuni TSL putem sa evitam competitia. In cazul unui sistem distribuit, constand in mai multe procesoare, fiecare cu memoria sa, conectate printr-o retea locala, aceste mijloace devin inaplicabile.concluzia este ca barierele au un nivel mult prea scazut, iar monitoarele nu sunt utilizabile decat in cateva limbaje de programare. De asemenea, nici unul dintre mijloace nu asigura schimbul de informatii intre masini. Este nevoie de altceva.

F. Transmiterea mesajelor

Acest altceva este transmiterea mesajelor. Aceasta metoda de comunicare interprocesorala utilizeaza doua operatii SEND si RECEIVE, care asemeni barierelor si spre deosebire de monitoare sunt mai degraba apeluri sistem decat construcii de limbaj. Ca atare, ele pot fi usor puse in proceduri de biblioteca dupa cum urmeaza:

send(destination, &message);
and
receive(source, &message);
primul apel trimite un mesaj la o anumita destinatie, iar cel din urma primeste un mesaj de la o anumita sursa (sau de la orice sursa daca receptorul nu este atent). Daca nu exista nici un mesaj disponibil, receptorul se poate bloca pana soseste unul. In mod alternativ poate sa raspunda imediat printr-un mesaj de eroare.