Aritoni Ovidiu Sisteme de operare 1 Introducere

Problema producator-consumator

Un exemplu pentru modul cum acestea pot fi folosite, sa ne gandim la problema producator-consumator (cunoscuta si sub numele de buffer de legatura). Doua procese impart ace3lasi buffer de marime fixa. Unul dintre ele, producatorul, pune informatie in buffer, iar celalalt, consumatorul, scoate acesta informatie. (putem de asemenea sa generalizam problema si sa avem m producatori si n consumatori, dar vom lua cazul unui singur producator si al unui singur cosumator deoarece astfel solutia este mai simpla).

Problemele apar atunci cand producatorul vrea sa puna o noua informatie in buffer, dar acesta este deja plin. Solutia este intrarea producatorului in repaus si pornirea lui atunci cand consumatorul a scos una sau mai multe informatii. In acelasi mod, in cazul in care consumatorul vrea sa scoata o informatie din buffer si constata ca buffer-ul este gol, intra in repaus pana cand producatorul introduce ceva in buffer, moment in care reporneste.

Acest mod de abordare pare destul de simplu, dar duce la acelasi tip de conditii de competitie pe care le-am vazut mai devreme in cazul directorului de spiralare. Pentru a tine evidenta numarului de informatii din buffer vom avea nevoie de o variabila – contul. Daca N este numarul maxim de informatii pe care le poate sustine buffer-ul, codul producatorului va verifica mai intai daca in cont se afla N informatii. Daca da, producatorul va intra in repaus; daca nu, producatorul va adauga o informatie si va mari contul.

Codul consumatorului este similar: mai intai se testeaza contul pentru a se vedea daca este 0. Daca da, intra in repaus; daca este mai mare de zero, scoate o informatie si scade contul. Fiecare dintre procese verifica de asemenea sa vada daca celalalt ar trebui sa fie in repaus, si daca nu, il reporneste. Atat codul de producator cat si cel de consumator sun aratate in fig. 2-11.

Pentru a exprima in C apeluri ale sistemului cum sunt SLEEP si WAKEUP le vom reprezenta sub forma de apeluri catre rutinele de biblioteca. Ele nu fac parte din biblioteca C standard, dar este foarte posibil ca ele sa fie disponibile pe orice alt sistem care efectiv a avut aceste apeluri ale sistemului. Procedurile enter_item si ­remove_item, care nu sunt aratate, se ocupa cu evidenta informatiilor introduse si scoase din buffer.

#define N 100 /* number of slots in the buffer */

int count = 0; /* number of items in the buffer*/

void producer(void)

{

while (TRUE) { /* repeat forever */

produce_item(); /* generate next item */

if (count == N) sleep(); /* if buffer is full, go to sleep */

enter_item(); /* put item in buffer */

count = count + 1; /* increment count of items in buffer */

if (count == 1) wakeup(consumer); /* was buffer empty? */

}

}

void consumer(void)

{

while (TRUE) { /* repeat forever */

if (count == 0) sleep(); /* if buffer is empty, go to sleep */

remove_item(); /* take item out of buffer */

count = count – 1; /*

Fig. 2-11. Problema producator-consumator cu o conditie fatala de competitie.
Acum sa ne intoarcem la conditia de competitie. Acest lucru poate sa apara datorita accesului nelimitat la cont. Urmatoarea situatie ar putea sa apara. Buffer-ul este gol si consumatorul tocmai a citit contul pentru a vedea daca este 0. In acest moment temporizatorul decide sa opreasca temporar rularea consumatorului si sa inceapa rularea producatorului. Producatorul introduce o informatie in buffer, mareste contul si observa ca in acest moment are valoarea 1. Rationand ca valoarea contului era 0 si consumatorul trebuie sa fie in repaus, producatorul apeleaza wakeup pentru a reporni consumatorul.

Din pacate, consumatorul inca nu este in mod logic in repaus, astfel incat semnalul de repornire este pierdut. La urmatoarea rulare a consumatorului acesta va verifica valoarea contului citit anterior , va constata ca este 0 si va intra in repaus. Mai devreme sau mai tarziu producatorul va umple buffer-ul si va intra si el in repaus. Ambele vor ramane in aceasta stare.

Esenta acestei probleme este faptul ca o comanda de repornire trimisa unui proces care (inca) nu se afla in repaus este pierduta. Daca aceasta nu s-ar pierde, totul ar functiona. O remediere rapida ar fi sa se modifice regulile pentru a adauga in acest cadru un bit de repornire aflat in asteptare. Cand o comanda de repornire este trimisa unui proces care nu se afla inca in stare de repaus, acest bit este pornit. Mai tarziu, cand procesul incearca sa intre in repaus, daca acest bit este pornit va fi oprit, dar procesul va ramane pornit. Acest bit este un fel de banca pentru semnale de repornire.

In timp ce in acest exemplu simplu acest bit salveaza situatia, este foarte usor de construit exemple cu trei sau mai multe procese in care doar un singur bit de acest fel este insuficient. Am putea sa facem o alta cale si sa adaugam un al doilea bit sau poate inca 8 sau inca 32, dar in principiu, problema ramane aceeasi.

E. Semafoare

Aceasta era situatia in 1965 cand E.W. Dijkstra (1965) a sugerat utilizarea unei variabile unitare pentru a numara repornirile pastrate pentru o utilizare ulterioara. In aceasta propunere a fost introdus un nou tip de variabila, numita semafoare. Un semafor putea avea valoarea 0, indicand faptul ca nu exista nici o repornire salvata; daca avea o valoare mai mare de 0 insemna ca exista una sau mai multe reporniri neefectuate.

Dijkstra a propus sa existe doua operatii, DOWN si UP (generalizari pentru SLEEP, respectiv WAKEUP). Operatia DOWN la un semafor verifica daca valoarea este mai mare de 0. Daca da, ii scade valoarea (adica ii utilizeaza o repornire din cele pastrate) si continua. Daca valoarea este 0, procesul intra in repaus fara a incheia operatia DOWN pentru moment. Verificarea valorii, schimbarea ei si, posibil intrarea in repaus, totul este realizat in cadrul unei actiuni atomice unica si indivizibila. Este garantat faptul ca o operatie de semafor odata inceputa nici un alt proces nu poate sa acceseze semaforul pana la incheierea sau blocarea operatiei. Aceasta atomicitate este absolut esentiala pentru solutionarea problemelor de sincronizare si pentru evitarea conditiilor de competitie.

Operatia UP mareste valoarea semaforului tinta. Daca unul sau mai multe procese ar fi in repaus la semaforul respectiva, incapabile sa incheie o operatie DOWN anterioara, unul dintre ele este ales de catre sistem (ex. la intamplare) si ii este permis sa isi incheie operatia DOWN. Astfel, dupa o operatie UP la un semafor unde exista mai multe procese in repaus, bariera va avea tot valoarea 0, dar va exista un proces mai putin in randul celor care se afla in repaus. Operatia de marire a valorii semaforului si repornire a unui proces este de asemenea indivizibila. Nici un proces nu se blocheaza executand o operatie UP la fel cum nici un proces nu se blocheaza in timpul unui proces de repornire in cadrul modelului anterior.

Ca un fapt lateral, in lucrarea originala a lui Dijkstra acesta a utilizat numele P si V in loc de DOWN si UP, dar de vreme ce acestea nu au smnificatie mnemonica pentru oamenii care nu vorbesc limba germana (si chiar pentru cei care vorbesc aceasta limba au doar o semnificatie marginala), vom folosi termenii DOWN si UP. Acestea au fost introduse mai intai in Algol 68.