9. Sincronizarea proceselor

Aceasta pagina este in lucru!

Problema sincronizarii se aplica atit la firele de executie cat si la procese, atunci cand se folosesc resurse partajate sau cand dorim sa secventiem activitati executate in procese (sau fire) distincte.

1. Conditii de cursa. Excluziune mutuala

In cazul in care mai multe procese sau fire de executie folosesc resurse comune, in paralel, rezultatul final al executiei lor poate sa nu fie determinist. Spre exemplu, doua procese pot scrie simultan intr-un fisier linii de text. Rezultatul poate fi diferit la doua rulari succesive, functie de ordinea in care ruleaza cele doua procese. Un alt exemplu tipic este acela in care avem un contor ce este incrementat de doua sau mai multe fire de executie, contorul fiind o variabila globala. Sa presupunem ca urmatoarea portiune de cod realizeaza incrementarea contorului, in fiecare fir de executie in parte:

... contor = contor + 1; ...

Sa presupunem ca din acest cod vor rezulta instructiuni in (pseudo) limbaj de asamblare de genul:

... 1 MOV R0, (contor) ; citeste locatia de memorie 'contor' in registrul r0 2 INC R0 ; aduna 1 3 MOV (contor), R0 ; scrie locatia de memorie 'contor' cu noua valoare ...

Am etichetat, pentru convenienta, instructiunile cu numerele 1, 2, 3. Sa presupunem ca doua fire de executie, A si B, executa concomitent aceasta portiune de cod. Sa analizam doua din scenariile posibile, considerand valoarea initiala a contorului ca fiind '2'. Ne asteptam ca, dupa ce ambele fire de executie termina instructiunea 3, valoarea contorului sa devina '4'.

- A executa instructiunea 1 si citeste valoarea '2' in registrul r0.
- B executa instructiunea 1 si citeste valoarea '2' in registrul (propriu) r0.
- B incrementeaza r0 si il scrie inapoi in memorie (instructiunile 2 si 3). Variabila contor va avea acum valoarea 3.
- A incrementeaza r0 (care contine '2') si il scrie la randul sau in memorie. Variabila contor va avea acum valoarea 3.
- B executa primele doua instructiuni, citind '2' in r0 si apoi incrementandu-l.
- A citeste valoarea '2' din memorie in registrul r0 (instructiunea 1).
- B executa instructiunea 3 scriind valoarea '3' in contor.
- A executa instructiunile 2 si 3. Avand in r0 valoarea '2', contor ajunge sa aiba din nou valoarea '3'.

Ambele scenarii duc la functionare defectuoasa a programului, datorita faptului ca valoarea veche a contorului este citita din memorie de catre unul din firele de executie inainte de a fi scrisa inapoi (dupa incrementare) de catre celalalt.

Observatii:

Cele de mai sus sunt valabile atat in cazul in care mai multe thread-uri sunt rulate in paralel pe mai multe procesoare, cat si atunci cind avem un singur procesor, deoarece exista posibilitatea ca executia unui thread sa fie intrerupta (de exemplu, datorita terminarii cuantei de timp) exact intre instructiunile 1 si 2 sau 2 si 3.
Unii dintre voi vor spune ca existra instructiune ce incrementeaza o locatie de memorie (pe unele procesoare). Un proces (sau fir de executie) nu va fi intrerupt in mijlocul instructiunii. Sa presupunem chiar ca respectiva instructiune e capabila sa adune orice valoare la o locatie de memorie. Probleme tot vor apare in cazul in care avem mai multe procesoare, iar daca avem de efectuat o operatie mai complexa cu valoarea din memorie,
/* sa zicem... */ contor = HZ*tick+(missed)?1:0;
chiar si atunci cind avem un singur procesor.

Definitie: Situatiile in care rezultatul executiei unui sistem format din mai multe procese (fire de executie) depinde de viteza lor relativa de executie se numesc conditii de cursa (in engleza: race conditions).

Conditiile de cursa apar atunci cind accesam resurse partajate, fara a ne asigura ca aceste resurse nu sunt folosite de catre alte procese (sau fire). Astfel de resurse pot fi: memoria comuna (shared memory, vezi mai jos), fisierele, inregistrarile unei baze de date, etc. Problemele mai sus mentionate nu ar apare daca acele portiuni din programe care lucreaza cu astfel de resurse partajate nu ar fi executate niciodata simultan. Aceste portiuni din programe, care efectueaza operatii asupra unor resurse comune se numesc zone sau sectiuni critice (critical sections). Daca ne asiguram ca doua sau mai multe fire de executie (sau procese) nu se executa niciodata simultan in zonele lor critice, atunci problema conditiilor de cursa a disparut. Acest lucru se numeste excluziune mutuala.

2. Semafoare

Exista numeroase mecanisme de sincronizare, de la cele mai simple la unele complexe. Aici vom vorbi despre semafoarele. Un alt astfel de mecanism, cu care sunteti probabil familiari este cel de monitor, intalnit in Java (vezi synchronize).

Semafoarele sunt un tip de date abstract ce poate avea o valoare intreaga nenegativa si asupra caruia se pot efectua operatiile: init, up, down. Operatia init initializeaza semaforul cu o valoare (nenula) data. Operatia down decrementeaza valoarea semaforului, daca aceasta este pozitiva. Daca este nula, procesul sau firul de executie se blocheaza. Operatia up incrementeaza valoarea semaforului, daca nu exista nici un proces blocat pe acel semafor. Daca exista, valoarea semaforului ramane zero, dar unul din procesele (de exemplu, la intamplare) blocate vor fi deblocate. Operatiile up si down sunt, evident, atomice (ce este o operatie atomica?).

O categorie des folosita de semafoare este cea a semafoarelor binare, a caror valoare poate fi 0 sau 1. Acestea sunt folosite cel mai des pentru a obtine excluziune mutuala.

Pentru a face ca portiunea de (pseudo)cod de mai sus sa fie corecta, o vom rescrie astfel:

int counter; semaphore sem; init(sem,1); ... down(sem); contor = contor + 1; up(sem); ...

Semafoarele cu valori intregi (mai mari ca 1) pot fi folosite, de exemplu, pentru a asigura accesul la resurse multiple, identice:

init(semaphore, 10); /* 10 tapes */ ... down(semaphore); get_next_tape(); do_backup(); up(semaphore); ...

Exemplul este pur ilustrativ, in lumea reala probabil nu asa se obine accesul la o banda magnetica!
Numeroase implemetari de semafoare permit operatii down si up care sa decrementeze/incrementeze cu mai mult decat 1.

Mecanisme System V IPC

Semafoarele si memoria partajata, mecanisme pe care le vom discuta in continuare, fac parte din mecanismele de comunicare si sincronizare a proceselor cunoscute ca System V IPC (InterProcess Communication). System V IPC include si cozile de mesaje, pe care nu le vom discuta in cadrul acestui laborator.

Toate mecanismele System V au ca si caracteristica comuna utilizarea unor chei numerice, prin care diverse procese pot obtine acces la obiecte de tip semafor, memorie partajata sau cozi de mesaje. Dupa cum stiti, un pipe nu poate fi folosit decat din procese inrudite, deoarece un proces oarecare nu are cum sa obtina un descriptor pentru un pipe creat in alt proces, decat prin mostenire (exista si pipe-uri cu nume, vezi fifo(4). Pentru a solutiona aceasta problema, mecanismele System V IPC utilizeaza pentru identificare o cheie numerica. Spre exemplu, atunci cand cream o zona de memorie partajata, dam o astfel de cheie, sa zicem 0x00000123. Dintr-un alt proces, daca dorim sa folosim aceeasi zona de memorie partajata, putem obtine o referinta catre ea utilizand aceeasi cheie.

Semafoare System V IPC

Cu ajutorul apelului sistem int semget(key_t key, int nsems, int semflg) se poate crea un set de semafoare, sau se poate obtine un identificator pentru un set de semafoare preexistent. Parametrul nsems semnifica numarul de semafoare din set. S-a ales gruparea semafoarelor in seturi deoarece, in System V IPC, este posibil sa se efectueze mai multe operatii, asupra mai multor semafoare, in mod atomic.

Functia semget() este asemanatoare cu open() pentru fisiere. Astfel, cheia poate fi considerata ca fiind similara cu calea catre un fisier (este un mod de identificare a acelui obiect) iar campurile IPC_CREAT si IPC_EXCL, ce pot fi setate in semflg, sunt similare cu O_CREAT si O_EXCL: daca este prezent IPC_CREAT si setul de semafoare cu cheia data nu exista, el va fi creat, iar daca este prezent is IPC_EXCL, iar setul de semafoare cu cheia data exista deja, se semnaleaza eroare. semget() intoarce un identificator pentru setul de semafoare caruia ii corespunde cheia data, sau -1 in caz de eroare.

Un set de semafoare poate fi distrus cu ajutorul functiei int semctl(int semid, int semnum, int cmd, ...). Aceasta functie poate face mult mai multe, dar nu vom intra in amanunte. Pentru a distruge un set de semafoare, parametrul cmd va avea valoarea IPC_RMID, semid este identificatorul intors de semget(), iar valoarea lui semnum este ignorata.

Operatiile down si up se realizeaza cu ajutorul functiei int semop(int semid, struct sembuf *sops, unsigned nsops). Datorita gradului mare de generalitate al modului de utilizare a semafoarelor System V, si aceasta functie este destul de complexa. Ne vom limita la a da modul de realizare al operatiilor de decrementare si incrementare (atomice) cu o valoare arbitrara a unui semafor din set. De asemenea, vom efectua o singura astfel de operatie la un moment dat, desi functia semop() permite mai multe operatii concomitente asupra semafoarelor dintr-un set.

Parametrul nsops reprezinta numarul de operatii, iar sops este un pointer spre un tablou ce contine nsops operatii, reprezentata fiecare de un element de tip struct sembuf. Un struct sembuf contine urmatoarele campuri de interes:

unsigned short sem_num;  /* numarul semaforului */
short sem_op;            /* operatia */
short sem_flg;           /* fanioane */

Pentru a vedea mai clar cum se utilizeaza semafoarele System V, studiati exemplul de mai jos.

3. Memorie partajata

Prin mecanismul de memorie partajata (shared memory) doua sau mai multe procese pot pune in comun o zona de memorie. In multe cazuri acest lucru este deosebit de util pentru a lucra pe seturi comune de date sau pentru a transfera rapid informatii. Fiind o resursa partajata, este deosebit de important ca accesul la aceasta zona de memorie sa fie sincronizat.

In SysV IPC, partjarea memoriei se realizeaza prin apelurile sistem shmget(), shmat(), shmctl() si shmdt().

Functia int shmget(key_t key, int size, int flags) este similara functiei open() pentru fisiere. Cheia "numeste" segmentul de memorie, asa cum o cale numeste unui fisier, iar identificatorul intors de functie este simiar cu un descriptor de fisier. Cu ajutorul lui shmget() se poate crea un segment nou de memorie partajata.

Initial, o zona de memorie nou creata nu apartine nici unui proces, si chair daca un proces detine un identificator pentru aceasta zona, el nu o poate accesa. Pentru a o putea folosi, procesul trebuie sa ataseze segmentul de memorie la spatiul de adrese, cu ajutorul lui void *shmat(int shmid, const void *addr, int flags). In urma acesei operatii, segmentul de memorie identificat prin shmid va fi mapat in spatiul de adrese al procesului. Functia intoarce, in caz de succes, adresa segmentului de memorie in cadrul procesului. Prin parametrul addr se poate specifica o adresa anume, in cadrul procesului, la care sa se faca atasarea. Recomandam utilizarea valorii NULL, care lasa sistemul sa aleaga adresa la care va atasa segmentul.

Atunci cand nu mai are nevoie de o zona de memorie partajata, un proces o poate detasa prin operatia int shmdt(const void *addr), unde addr este adresa intoarsa de functia shmat().

Un segment de memorie partajata este distrus doar in mod explicit, prin apelul sistem int shmctl(int shmid, int cmd, struct shmid_ds* buf). Acesta poate efectua mai multe operatii asupra memoriei partajate identificate prin shmid. In cazul in care dorim distrugerea memoriei partajate, folosim IPC_RMID ca si comanda (cmd) iar al treilea parametru il dam NULL. Segmentul de memorie nu va fi distrus imediat decat in cazul in care nici un proces nu il mai are atasat. Altfel, el este marcat pentru a fi distrus si acest lucru se va intimpla la ultima operatie shmdt().

Studiati paginile de manual pentru apelurile sistem descrise mai sus!

4. Exemple

Cititi si executati exemplul de mai jos:
- sync.h
- semlib.h
- semlib.c
- sync1.c
- sync2.c
- Makefile
Copiati fisierele de mai sus intr-un director separat, si executati comanda make. Programul se va compila fara utilizarea semafoarelor. Lansati programul in executie. Dupa o vreme, veti constata ca unele din liniile tiparite nu sunt asa cum v-ati fi asteptat. Explicati de ce.
Acum, modificati fisierul Makefile comentand linia a doua si stergand caracterul # de pe linia a treia:
CFLAGS=-Wall -I. #CFLAGS=-Wall -I. -DDO_SYNC
Executati comanda make clean (pentru a sterge executabilele) iar apoi make. Lansati din nou programul. De data asta, programul ar trebui sa se comporte corect.

Problema "Cititori/Scriitori":
Intr-un sistem exista un numar de procese. O parte din acestea (cititori) citesc o zona de memorie si mai apoi o afiseaza iar alte citeva procese (scriitori) scriu in acea zona de memorie un mesaj (un text). In asa fel trebuie coordonat accesul la zona comuna de memorie incat atunci cand un scriitor scrie, nici un alt proces sa nu aiba acces la ea. Mai multi cititori trebuie sa poata citi in acelasi timp, insa, textul respectiv.

O rezolvare posibila, in pseudocod, este data mai jos:

semaphore sem_readers = NR_CITITORI; shared char *textbuf[TEXTSIZE];

void cititor() { down(sem_readers, 1); read_and_print(textbuf); up(sem_readers, 1); }

void scriitor() { down(sem_readers, NR_CITITORI); compose_and_write(textbuf); up(sem_readers, NR_CITITORI); }

Explicati logica programului. Implementati programul de mai sus folosind semafoare si memorie partajata SysV IPC!

5. Tema

Sa se rezolve problema cu enuntul de mai jos folosind mecanismele IPC cunoscute: memorie comuna sau semafoare.

Se considera o frizerie deservita de un barbier. Acesta dispune de cinci scaune in holul de asteptare. Barbierul nu poate deservi decat un client la un moment dat, iar in criza de clienti barbierul atipeste (procesul care simuleaza barbierul se blocheaza; vezi mai jos). Un client, in functie de situatia existenta in frizerie in momentul sosirii, poate actiona intr-unul din modurile urmatoare:

daca barbierul doarme, il trezeste si cere sa fie barbierit;
daca barbierul este ocupat, dar exista scaune libere in holul de asteptare ocupa un scaun asteptand sa-i vina randul;
daca holul de asteptare este plin atunci clientul pleaca (nemultumit!).

Sa se scrie un program care simuleaza cele descrise mai sus prin procese: barbierul si clientii sunt procese distincte, numarul clientilor putand fi dat ca si parametru. Programul va afisa de asemenea o statistica a clientilor deserviti si a celor nemultumiti, la final.

Autor: Petre Mierlutiu