Probleme clasice de coordonare si sincronizare a proceselor

PROBLEME CLASICE DE COORDONARE Si SINCRONIZARE A PROCESELOR

Exista o serie de exemple clasice de coordonare si sincronizare a proceselor in care se regasesc principalele probleme ce apar in astfel de situatii. Multe din aceste probleme se afla in structura oricarui sistem se operare. Totodata aceste probleme clasice se regasesc si in programarea concurenta. Le vom aborda incercand sa le solutionam cu mijloacele specifice prezentate anterior.

Problema producator-consumator

Fie o serie de procese concurente care produc date (procese PRODUCATOR). Aceste date sunt consumate de alte procese (procese CONSUMATOR). Datele sunt consumate in ordinea in care au fost produse. Este posibil ca viteza de producere sa difere mult de viteza de consum.

Aceasta problema s-ar rezolva usor daca ar exista un buffer de dimensiuni foarte mari, teoretic infinit, care ar permite operarea la viteze diferite ale producatorilor si consumatorilor. Cum o astfel de solutie este practic imposibila, vom considera cazul practic al unui buffer finit. Principalele probleme care apar in acest caz sunt:

-buffer gol (consumatorii nu pot consuma date si trebuie sa astepte);

-buffer plin (producatorii nu pot inscrie date in buffer si trebuie sa astepte).

Indiferent de solutiile alese, vor trebui rezolvate situatiile de citire din buffer-ul gol si de inscriere in buffer-ul plin.

1.1. Rezolvarea problemei producator - consumator cu ajutorul semafoarelor.

Fie un buffer de dimensiune n organizat dupa structura coada circulara. Bufferul are n locatii pe care le-am notat cu tampon[n].

Vom considera urmatoarele variabile, semafoare si mutexuri:

Variabilele cu care se scrie si se citeste in buffer au fost notate cu scriere si citire. Ele asigura accesul proceselor la pozitia unde se doreste operatia de scriere sau citire, in ordinea in care au venit.

Semafoarele , semscriere si semcitire, au rolul de a asigura excluderea mutuala intre procesele producator si consumator. Semaforul semscriere contine numarul de pozitii libere din buffer iar semaforul semcitire contine numarul de pozitii pline. Semscriere se initializeaza cu n si semcitire cu 0. Cand semscriere =0 sau semcitire=n , se va semnala situatia de buffer plin respectiv buffer gol si procesele vor fi blocate. Se intra intr-o excludere mutuala cu protocolul bussy-wait si procesele vor fi deblocate atunci cand semscrieren sau semcitire0.

Mutexurile mutexscrieresi mutexcitire folosesc pentru excluderea mutuala intre doua procese de acelasi tip. mutexscriere pentru procesele de tip producator si mutexcitire pentru procesele de tip consumator.

Procesele producator vor citi numere intregi la tastatura iar procesele consumator vor "consuma" aceste numere.

Iata o implementare a problemei producator/consumator, scrisa in limbajul C:

declaratii de variabile, semafoare, mutexuri si initializatori

typedef int semafor; typedef int mutex;

#define n 1000;

int tampon[n];

int scriere=0, citire=0;

semafor semscriere=n, semcitire=0;

mutex mutexscriere, mutexcitire;

Procese producator

int valoare, tastatura;

while(1)

Procese Consumator

int valoare;

while(1)

Procesele producator functioneaza in felul urmator:

Se considera o bucla while din care practic nu se iese. Se citeste un numar intreg de la tastatura in variabila valoare. Prin wait(semscriere) se asigura excluderea mutuala a procesului respectiv producator fata de alte eventuale procese consumator. Prin lock(mutexscriere) se asigura excluderea mutuala a procesului respectiv producator fata de alte procese producatoare. Prin tampon[scriere]=valoare se scrie efectiv valoarea in buffer. Prin scriere=(scriere+1)%n se actualizeaza pozitia de scriere in buffer. Prin unlock(mutexscriere) se elibereaza mutexul de scriere, permitand altor producatori sa foloseasca bufferul. Prin signal(semcitire) se contorizeaza semaforul de citire cu 1, semnaland ca, dupa ce procesul producator a inscris o valoare in buffer, numarul de pozitii din buffer pentru procesele consumatoare s-a marit cu 1.

Procesele consumator functioneaza in mod asemanator.

4.3.1.2.          Rezolvarea problemei producator/consumator prin transmitere de mesaje

Am studiat in subcapitolul precedent tehnica de transmitere prin mesaje. Prezentam acum o aplicatie a acestei tehnici la problema producator/consumator.

Pentru aceasta sa consideram o linie de transmisie cu capacitate limitata care foloseste un buffer cu  n pozitii.

Modul de comunicatie ales pentru implementare este cel direct, deci fara mailboxuri.

Algoritmul este simplu. Consumatorul trimite mai intai mesaje goale producatorului. Ori de cate ori producatorul are de dat un produs consumatorului, va lua un mesaj gol si va transmite consumatorului un mesaj plin. Prin aceasta numarul de mesaje din sistem ramane constant in timp, nedepasind capacitatea limitata a bufferului de comunicatie.

Bufferul de comunicatie este plin atunci cand producatorul lucreaza mai repede decat consumatorul si toate mesajele sunt pline. In acest moment producatorul se blocheaza, asteptand ca un mesaj gol sa se intoarca.

Bufferul de comunicatie este gol atunci cand consumatorul lucreaza mai repede decat producatorul. Toate mesajele vor fi golite asteptand ca producatorul sa le umple. Consumatorul este blocat asteptand pentru deblocare un mesaj plin.

Iata mai jos o implementare a problemei producator/consumator prin transfer de mesaje.

Se observa in implementarea aleasa ca parametrul mesaj este un parametru referinta.

4.3.2.          Problema barbierului somnoros

Enunt

Pravalia unui barbier este formata din doua camere, una la strada, folosita ca sala de asteptare, si una in spate, in care se gaseste scaunul pe care se aseaza clientii pentru a fi serviti. Daca nu are clienti, barbierul somnoros se culca. Sa se simuleze activitatile care se desfasoara in pravalia barbierului.

Rezolvare

Aceasta problema este o reformulare a problemei producator/consumator, in care locul bufferului de obiecte este luat de scaunul barbierului iar consumatorul este barbierul care isi serveste (consuma) clientii.

In sala de asteptare sunt n scaune pe care se aseaza clientii; fiecare scaun este pentru un client. Daca nu sunt clienti, barbierul doarme in scaunul de frizerie. Cand vine primul client il trezeste pe barbier si barbierul il serveste pe client, asezandu-l in scaunul de frizerie. Daca in acest timp sosesc si alti clienti, ei vor astepta pe cele n scaune. Cand toate scaunele sunt ocupate si mai vine inca un client, acesta paraseste pravalia.

Problema consta in a programa aceste activitati in asa fel incat sa nu se ajunga la asa numitele conditii de cursa. Este o problema clasica cu multe aplicatii, mai ales in cele de help desk.

Pentru implementarea solutiei vom utiliza doua semafoare si un mutex:

clienti - un semafor ce contorizeaza clientii ce asteapta;

barbier - un semafor care arata daca barbierul este ocupat sau nu; el are doua valori, 0 daca barbierul este ocupat si 1 daca este liber;

mutexc - un mutex folosit pentru excludere mutuala; arata daca scaunul de frizerie este ocupat sau nu.

De asemenea mai folosim o variabila:

clientiinasteptare - care, asa cum arata si numele, numara clientii care asteapta. Aceasta variabila trebuie introdusa deoarece nu exista o cale de a citi valoarea curenta a semafoarelor si de aceea un client care intra in pravalie trebuie sa numere clientii care asteapta. Daca sunt mai putini decat scaunele, se aseaza si el si asteapta; daca nu, paraseste frizeria.

Sa descriem algoritmul . Cand barbierul intra dimineata in pravalie, el executa functia barbier(), blocand semaforul clienti care este initial pe zero. Apoi se culca si doarme pana vine primul client. Cand acesta soseste, el executa functia clienti() si ocupa mutexul care arata ca scaunul de frizerie este ocupat. Daca intra un alt client in acest timp, el nu va putea fi servit deoarece mutexul este ocupat. Va numara clientii care asteapta si, daca numarul lor e mai mic decat numarul scaunelor, va ramane, daca nu, va parasi pravalia. Ramanand, va incrementa variabila clientiinasteptare. Cand clientul care este servit a fost barbierit, el elibereaza mutexul, trezind clientii care asteapta si unul din ei va ocupa mutexul, fiind servit la randul sau.

Iata mai jos implementarea acestui algoritm.

#define scaune 20/*se defineste numarul

de scaune*/

type def int semafor;

type def int mutex ;

semafor clienti=0; /*declaratii si

initializari*/

semafor barbier=0;

mutexc=1;

int clientiinasteptare=0;

void barbier()

void clienti()

else

signal(mutexc);}}

4.3.3.      Problema cititori/scriitori

Problema a fost enuntata de Coutois, Heymans si Parnas in 1971.

Un obiect (care poate fi o resursa, de exemplu un fisier sau o zona de memorie) este partajat de mai multe procese concurente. Dintre aceste procese, unele doar vor citi continutul obiectului partajat si aceste procese poarta numele de cititori iar celelalte vor scrie in continutul obiectului partajat, purtand numele de scriitori.

Cerinta este ca scriitorii sa aiba acces exclusiv la obiectul partajat, in timp ce cititorii sa poata accesa obiectul in mod concurent (neexclusiv).

Exista mai multe posibilitati de a solutiona aceasta problema. Vom aminti doua variante.

Varianta 1

Nici un cititor nu va fi tinut in asteptare, decat daca un scriitor a obtinut deja permisiunea de acces la obiectul partajat.

La un acces simultan la obiectul partajat, atat al scriitorilor cat si al cititorilor, cititorii au prioritate.

Varianta 2

Cand un scriitor este gata de scriere, el va executa scrierea cat mai curand posibil.

La un acces simultan, scriitorii sunt prioritari.

Oricum, in ambele cazuri, problema principala ce trebuie rezolvata este infometarea, adica asteptarea la infinit a obtinerii dreptului de acces.

Sa implementam un program pentru prima varianta, folosind urmatoarele semafoare, mutexuri si variabile:

scrie - un semafor cu mai multe roluri; el asigura excluderea mutuala a scriitorilor; este folosit de catre primul cititor care intra in propria sectiune critica; de remarcat ca acest semafor nu este utilizat de cititorii care intra sau ies din sectiunea critica in timp ce alti cititori se afla in propria sectiune critica;

contorcitire - o variabila care are rolul de a tine evidenta numarului de procese existente in cursul citirii;

semcontor - un semafor care asigura excluderea mutuala cand este actualizata variabila contorcitire.

Daca un scriitor este in sectiunea critica si n cititori asteapta, atunci un cititor asteapta la semaforul scriere iar ceilalti n-1 asteapta la semcontor

La signal(scrie), se poate relua fie executia unui singur scriitor, fie a cititorilor aflati in asteptare, decizia fiind luata de planificator.

Iata implementarea programului pentru prima varianta:

typedef int semafor;/*declaratii si

initializari

int contorcitire=0;

semafor scrie=1,semcontor=1 ;

void scriitor()

void cititor()

4.3.4.          Problema cinei filozofilor chinezi

Cinci filozofi chinezi isi petrec viata gandind si mancand in jurul unei mese circulare inconjurata de cinci scaune, fiecare filozof ocupand un scaun. In centrul mesei este un platou cu orez si in dreptul fiecarui filozof se afla o farfurie. In stanga si in dreapta farfuriei cate un betisor. Deci, in total, cinci farfurii si cinci betisoare. Un filozof poate efectua doua operatii: gandeste sau mananca. Pentru a putea manca, un filozof are nevoie de doua betisoare, unul din dreapta si unul din stanga. Dar un filozof poate ridica un singur betisor odata. Problema cere o solutie pentru aceasta cina.

2

1

3

5

4

Fig. 4.7. Problema filozofilor chinezi.

Trebuie rezolvate doua probleme majore:

-Interblocarea care poate sa apara. De exemplu, daca fiecare filozof ridica betisorul din dreapta sa, nimeni nu mai poate sa-l ridice si pe cel din stanga si apare o situatie clara de asteptare circulara, deci de interblocare.

-Problema infometarii unui filozof care nu apuca sa ridice niciodata cele doua betisoare.

Aceasta problema a fost enuntata si rezolvata de catre Dijkstra in 1965.

Exista multe solutii ale acestei probleme, marea majoritate utilizand excluderea mutuala.

Pentru a nu aparea interblocarea se folosesc, in general, solutii de prevenire a acesteia adica se impun unele restrictii in ceea ce priveste actiunile filozofilor, cum ar fi:

-unui filozof i se permite sa ia un betisor numai atunci cand ambele betisoare, din dreapta si din stanga sa, sunt disponibile;

-se creeaza o corespondenta biunivoca intre multimea numerelor naturale si filozofi, fiecare filozof avand un numar natural; o solutie asimetrica impune filozofilor cu numar impar sa apuce mai intai betisorul din stanga si apoi pe cel din dreapta, iar filozofilor cu numar par sa ia mai intai betisorul din dreapta si apoi pe cel din stanga.

Vom prezenta, in continuare, o solutie clasica a acestei probleme, care rezolva si situatia interblocarii si pe cea a infometarii. In acest algoritm, se poate generaliza problema pentru n filozofi. Se urmareste in ce stare poate fi un filozof, existand trei stari posibile: mananca, gandeste si este infometat.

Unui filozof i se permite sa intre in starea "mananca" numai daca cel putin unul din vecinii sai nu este in aceasta stare. Prin aceasta restrictie se previne interblocarea.

Pentru implementare, se utilizeaza urmatoarele structuri:

stare[n] - un vector n-dimensional, in care pe pozitia

i se gaseste starea filozofului la un moment dat; aceasta poate fi:

0pentru starea "gandeste"

1 pentru starea "infometat"

2 pentru starea "mananca"

sem[n] - un vector n-dimensional, in care sem[i] este un semafor pentru filozoful i;

mutexfil - un mutex pentru excludere mutuala;

functia filozof(i) - este functia principala care coordoneaza toate celelalte functii si care se refera la filozoful i;

functia ridica betisor(i) - este functia care asigura pentru filozoful i ridicarea ambelor betisoare;

functia pune betisor i - este functia care asigura pentru fiecare filozof i punerea ambelor betisoare pe masa;

functia test(i) - este functia care testeaza in ce stare este filozoful i.

Implementarea este:

4.3.5.          Probleme propuse pentru implementare

5.1. Problema rezervarii biletelor

Enunt

Fiecare terminal al unei retele de calculatoare este plasat intr-un punct de vanzare a biletelor pentru transportul feroviar. Se cere sa se gaseasca o modalitate de a simula vanzarea biletelor, fara a vinde doua sau mai multe bilete pentru acelasi loc.

Rezolvare

Este cazul in care mai multe procese (vanzatoarele de bilete) incearca sa utilizeze in mod concurent o resursa nepartajabila, care este o resursa critica (locul dintren).

Problema se rezolva utilizand excluderea mutuala iar pentru implementarea ei  cea mai simpla metoda este folosirea semafoarelor.

4.3.5.2.          Problema gradinii ornamentale

Enunt

Intrarea in gradinile ornamentale ale unui oras oriental se face prin n parti. Sa se tina evidenta persoanelor care au intrat in gradina.

Rezolvare

Fiecare poarta de intrare in gradina este o resursa care trebuie accesata exclusiv de unproces ( o persoana care intra in gradina) .

Daca, la un moment dat, pe una din porti intra o persoana, atunci, in acel moment, pe nici oalta poarta nu mai intra vreo persoana in gradina.

Aceasta problema face parte din problema excluderii reciproce.

4.3.5.3.          Problema emitator-receptor

Enunt

Un emitator emite succesiv mesaje, fiecare dintre ele trebuind sa fie receptionate de toti receptorii, inainte ca emitatorul sa emita mesajul urmator.

Solutie

Este o aplicatie de tipul client-server. In acest tip de aplicatii, un proces server este un proces ce ofera servicii altor procese din sistem iar un proces client este unul care solicita servicii de la server si le consuma.

Daca procesele client si server nu sunt pe acelasi calculator, atunci aceasta aplicatie este distribuita. Implementarea ei, cel mai adesea utilizata in sistemele multicalculator, se face prin transmisie de mesaje.