Problema sectiunii critice si a excluderii mutuale

PROBLEMA SECTIUNII CRITICE SI A EXCLUDERII MUTUALE

Cazul cel mai frecvent in care mai multe procese comunica intre ele este acela prin intermediul variabilelor partajate. Dar accesul nerestrictionat a doua sau mai multe procese la resurse partajate poate produce erori de executie.

Exemplu:

Un proces executa o operatie de incrementare a variabilei partajate x dupa secventa cod:

LOAD R x /incarcarea lui x in registrul R;

INC R /incrementarea lui R;

STORE x R /memorarea valorii in X.

Presupunem ca arhitectura calculatorului este cea de load/store, specific procesoarelor de mare viteza cum sunt si cele din arhitectura RISC.

Variabila locala x, in arhitecturi paralele, se numeste temporar inconsistenta, intre variabila locala si variabila globala corespunzatoare. Acest tip de inconsistenta temporara este frecvent intalnita in executia programelor la arhitecturi secventiale (Neumann), dar nu prezinta nici un pericol pentru executia programelor secventiale normale ale caror variabile nu sunt partajate intre procese concurente.

Este important de observat ca inconsistenta temporara intre o variabila globala si copia ei locala reprezinta una din principalele cauze care produce erori atunci cand o astfel de variabila este accesata concurent de procese concurente.

Din acest exemplu reies doua conditii necesare pentru eliminarea erorilor datorate executiei concurente a mai multor procese:

1) Secventa de instructiuni din care este alcatuita operatia de actualizare a unei variabile partajate trebuie sa fie executata de un proces ca o operatie atomica, neintreruptibila de catre alte procese sau chiar de SO.

2) Operatia de actualizare a unei variabile partajate executata de un proces trebuie sa inhibe executia unei alte operatii asupra aceleasi variabile executate de alt proces. Este deci necesara serializarea operatiilor asupra variabilelor partajate, serializare care se obtine prin excludere mutuala a acceselor la variabila partajata.

In acest sens actualizarea unei variabile partajate poate fi privita ca o sectiune critica. O sectiune critica este o secventa de instructiuni care actualizeaza in siguranta una sau mai multe variabile partajate. Cand un proces intra intr-o sectiune critica, el trebuie sa execute complet toate instructiunile sectiunii critice, inainte ca alt proces sa o poata accesa. Numai procesului care executa o sectiune critica ii este permis accesul la variabila partajata, in timp ce tuturor celorlalte procese le este interzis accesul. Acest mecanism est denumit excludere mutuala , deoarece un proces exclude temporar accesul altor procese la o variabila partajata.

Solutionarea problemei excluderii mutuale trebuie sa indeplineasca urmatoarele cerinte:

-sa nu presupuna nici o conditie privind viteza de executie sau prioritatea proceselor care acceseaza resursa partajata;

-sa asigure ca terminarea sau blocarea unui proces in afara sectiunii critice nu afecteaza in nici un fel toate celelalte procese care acceseaza resursa partajata corespunzatoare sectiunii critice respective;

-atunci cand unul sau mai multe procese doresc sa intre intr-o sectiune critica, unul din ele trebuie sa obtina accesul in timp finit.

Mecanismul de baza pe care-l urmareste un proces este:

-protocol de negociere / invingatorul continua executia;

-sectiune critica / utilizarea exclusiva a resursei;

-protocol de cedare / proprietarul se deconecteaza.

Solutionarea corecta a excluderii mutuale nu este o problema triviala. Primul care a solutionat aceasta problema a fost matematicianul olandez Decker. Solutia lui, insa, nu este valabila decat pentru doua procese. Solutii de excludere mutuala au mai dat Peterson si Lampert, solutii pur soft, dar a caror eficienta este discutabila caci nu rezolva in intregime toate cerintele. Implementarea eficienta a excluderii mutuale se poate realiza prin suport hard (validare/invalidare de intreruperi sau instructiuni Test and Set). Aceste facilitati hard sunt utilizate pentru implementarea unor mecanisme de sincronizare (obiecte de sincronizare) ca semafoare, mutexuri, bariere, monitoare etc.

1. Suportul hardware pentru implementarea excluderii mutuale

1.1. Invalidarea / validarea intreruperilor

Instructiunile de invalidare/validare a intreruperilor (DI/EI) sunt disponibile in toate procesoarele. Secventa care asigura accesul exclusiv al unui singur proces la o resursa este:

DI / invalidare intreruperi;

Sectiune critica;

EI / validare intreruperi.

Prin invalidarea intreruperilor se ajunge la blocarea celorlalte procese. Este un mecanism prea dur, un model pesimist de control al concurentei, cu urmatoarele dezavantaje:

-se blocheaza si activitatea altor procese (numite victime inocente) care nu au nici o legatura cu sectiunea critica respectiva;

-daca se executa de catre useri, se poate bloca sistemul iar daca sunt executate din kernel, apare un cost de timp suplimentar (overhead) de comutare a modului de executie kernel/user.

1.2. Instructiunea Test and Set (TS)

In principiu, instructiunea TS are ca operand adresa unei variabile de control si executa urmatorii pasi:

-compara valoarea operandului cu o valoare constanta (de exemplu 0 pentru BUSY) si seteaza flagurile de conditie ale procesorului;

-seteaza operandul la valoarea BUSY .

Acesti pasi sunt executati ca o operatiune unica, indivizibila, numita operatie atomica.

Subinstructiunea cod, TS, poate fi scrisa astfel:

LOAD R, operand

CMP R, BUSY flag ZERO=1 daca R=BUSSY

STORE operand,BUSY

1.3. Protocoale de asteptare in excluderea mutuala

Avem doua tipuri de protocoale:

a)     (busy-wait)

b)     (sleep-wait)

a)     BUSY-WAIT (asteptare ocupata)

Folosind instructiunea TS acest model are urmatoarea implementare:

ADRL TS (acces)

JZ ADRL/asteptare cat variabila acces=BUSY

BUSY-WAIT este simplu de implementat dar are dezavantajul unei eficiente scazute, datorita faptului ca se consuma timp de executie al procesorului de catre un proces care nu avanseaza.

b)     SLEEP-WAIT (asteptare dormanta)

In acest tip de protocol, procesul care nu are resursa disponibila este suspendat (adormit) si introdus intr-o coada de asteptare. Apoi este trezit, cand resursa devine disponibila.

In sistemul uniprocesor este folosit totdeauna SLEEP-WAIT, deoarece nu se consuma timp procesor inutil.

In sistemul multiprocesor se folosesc amandoua protocoalele si chiar o combinatie intre ele.

1.4. Mecanisme de sincronizare intre procese

(obiecte de sincronizare)

a) Semafoare.

Semafoarele sunt obiectele de sincronizare cele mai des si mai mult folosite. Ele au fost introduse de Dijkstra in 1968.

Un semafor este de fapt o variabila partajata care poate primi numai valori nenegative. Asupra unui semafor se pot executa doua operatii de baza:

-decrementarea variabilei semafor cu 1 (DOWN

-incrementarea variabilei semafor cu 1 (UP

Daca o operatie DOWN este efectuata asupra unui semafor care este mai mare decat zero, semaforul este decrementat cu 1 si procesul care l-a apelat poate continua. Daca, din contra, semaforul este zero, operatia DOWN nu poate fi efectuata si spunem ca procesul asteapta la semafor, intr-o coada de asteptare, pana cand un alt proces efectueaza operatia UP asupra semaforului, incrementandu-l.

Exemplu.

Avem un complex cu terenuri de handbal si 20 echipe care joaca 10 meciuri. 1meci = 1proces. Intr-un cos mare (semafor) exista 7 mingi. Semaforul ia valori intre 0-7. Fiecare 2 echipe iau cate o minge din cos, efectuand 7 operatii DOWN. Semaforul este 0 ( nu mai sunt mingi in cos) si celelalte 6 echipe asteapta o minge in cos, deci o operatie UP

Pentru implementare, operatiile DOWN si UP vor fi inlocuite cu doua primitive wait(s) si signal(s) , in felul urmator:

wait(s) - incearca sa decrementeze valoarea variabilei semafor s cu 1 si daca variabila este 0 procesul ramane in asteptare pana cand s0.

signal(s) - incrementeaza cu 1 semaforul s.

Implementarea semafoarelor in protocolul BUSY-WAIT

wait(s)

signal(s++);}

Operatia signal(s) este atomica (indivizibila).

Operatia wait(s) are doua regimuri:

atomica, daca s0;

neatomica, daca s=0.

Este normal ca, daca semaforul este ocupat (s=0), operatia wait(s) sa nu fie atomica; in caz contrar ar impiedica alte operatii, inclusiv signal(s), executate de un alt proces care sa acceseze variabila s pentru a o elibera.

Implementarea cu BUSY-WAIT a semafoarelor are dezavantajul unui consum de timp procesor de catre procesele aflate in asteptare. Un alt dezavantaj este posibilitatea ca un proces sa fie amanat un timp nedefinit (indefinit, postponement) in obtinerea unui semafor, datorita faptului ca nu este nici o ordonare intre procesele care asteapta la semafor. Astfel exista posibilitatea ca un proces sa fie impiedicat un timp nedefinit de a obtine un semafor datorita aglomerarii provocate de alte procese. Un astfel de fenomen de blocare se numeste livelock iar procesul afectat este numit strivit (starved).

Implementarea semafoarelor in protocolul SLEEP-WAIT

Procesele care asteapta la semafor stau intr-o coada de asteptare (FIFO).

wait(s)

signal(s)

In loc sa intre in asteptare ocupata, atunci cand semaforul este ocupat, procesul apelant este suspendat si trecut intr-o coada de asteptare asociata semaforului apelat. Trebuie insa ca si procesul dormant (suspendat) sa afle cand semaforul a devenit liber. Acest lucru se realizeaza prin intermediul operatiei signal. Aceasta operatie incearca mai intai sa trezeasca un proces din coada de asteptare si sa-l treaca in starea de executie (suspendat→run). Numai daca coada de asteptare este goala, incrementaza semaforul.

b) Mutex-uri

Denumirea MUTEX vine de la mutual exclusion. Mutex-ul este un caz particular de semafor si este utilizat pentru accesul mai multor procese la o singura resursa partajata. Operatiile care se executa asupra unui mutex sunt :

-operatia de acces si obtinere a mutex-ului, notata cu ocupare (mutex) sau lock(mutex) ;

operatia de eliberare a mutex-ului, notata cu eliberare (mutex) sau unlock(mutex).

c) Evenimente (semnale)

Unul dintre primele mecanisme de comunicare intre procese este reprezentat de semnale sau evenimente. In UNIX se numesc semnale iar in WINDOWS se numesc evenimente. Ele anunta aparitia unui eveniment si pot fi trimise de un proces altui proces, de un proces aceluiasi proces sau pot fi trimise de kernel. Momentul aparitiei unui semnal este neprecizat, el aparand asincron.

Semnale UNIX

In sistemul de operare UNIX, semnalele pot proveni de la nucleu sistemului, prin care se notifica evenimente hardware, sau pot fi generate soft, de unele procese, pentru a notifica un eveniment asincron. Un semnal este reprezentat printr-un numar si un nume. In UNIX semnalele dintre procese au denumiri simbolice, SIGUSR 1 si SIGUSR 2

Un proces care primeste un semnal poate sa actioneze in mai multe moduri:

-sa ignore semnalul;

-sa blocheze semnalul; in acest caz semnalul este trecut intr-o coada de asteptare pana cand este deblocat;

-sa receptioneze efectiv semnalul.

Procesul stabileste ce semnale sunt blocate, folosind o masa de semnale, in care fiecare bit corespunde unui numar de semnal. In standardul POSIX exista numere intre 33 si 64, deci 31 semnale. Un semnal poate sa apara in urmatoarele cazuri:

-la actionarea unei taste a terminalului;

-la aparitia unei intreruperi hardware (impartire prin zero, adresa inexistenta etc);

-atunci cand un proces trimite un semnal altui proces sau thread, folosind functiile:

a)sigqueue() - se transmite un semnal unui proces;

b)kill() - se transmite un semnal de terminare a unui proces;

c)pthread - se transmite semnal de terminare a unui thread.

Evenimente WINDOWS

In SO WINDOWS, un eveniment este un obiect de sincronizare care poate fi semnalat sau nesemnalat.

Exista doua tipuri de evenimente:

-evenimente cu resetare manuala (evenimente care trecute in stare semnalat raman in aceasta stare pana cand sunt trecute in mod explicit in starea nesemnalat);

-evenimente cu autoresetare.

In WINDOWS un proces poate crea un eveniment folosind functia CREATE EVENT

Un proces in asteptarea unui eveniment poate executa una din functiile de asteptare WAIT FOR SINGLE OBJECT sau WAIT FOR MULTIPLE OBJECT.

Evenimentele sunt utilizate pentru notificarea unui proces sau thread despre aparitia unui alt eveniment.

Evenimentele creeaza puncte de sincronizare intre procese sau threaduri.

d) Monitoare. Monitoarele sunt mecanisme de sincronizare intre procese concurente care pot suporta abstractizarea datelor.

Prin aparitia monitoarelor (HOARE, 1976), se reuseste sa se acopere unul din neajunsurile principale ale celor mai utilizate mecanisme de sincronizare, semafoarele, care nu suporta abstractizarea datelor.

Sintaxa monitorului este asemanatoare cu cea a unei clase, cuvantul CLASS fiind inlocuit cu MONITOR.

Este de remarcat faptul ca intr-un monitor se asigura excluderea mutuala, astfel ca la un moment dat un singur proces poate fi activ.

Un monitor este bazat pe modularitate si incapsulare.

Coada de intrare in monitor

Fig. Structura unui monitor.

Structura unui monitor consta in trei parti:

-in prima parte se declara numele monitorului si variabilele locale;

-in a doua parte se declara toate procedurile;

-in cea de a treia parte se initializeaza toate variabilele acestui monitor.

In general, procedurile unui monitor sunt constituite din principalele functii care se intalnesc intr-un sistem de operare. De exemplu, o procedura tipica este intrarea intr-o sectiune critica.