Aritoni Ovidiu Sisteme de operare 1 Introducere

3.Probleme clasice de IPC

A.Problema producătorilor şi consumatorilor

Se dă un recipient care poate să memoreze un număr limitat de obiecte în el. Se presupune că sunt active două categorii de procese care accează acest recipient:

• 
  producători;
  
• 
  consumatori.
  

Producătorii introduc obiecte în recipient iar consumatorii extrag obiecte din recipient.

Pentru ca acest mecanism să funcţioneze corect, producătorii şi consumatorii trebuie să aibă acces exclusiv la recipient. În plus, dacă un producător încearcă să acceseze un recipient plin, el trebuie să aştepte consumarea cel puţin a unui obiect. Pe de altă parte, dacă un consumator încearcă să acceseze un recipient gol, el trebuie să aştepte până când un producător introduce obiecte în el.
Vom prezenta mai jos o soluţie cu semafoare pentru această problemă. În acest scop vom folosi trei semafoare.

1. 
   semafoarele plin şi gol pentru sincronizarea proceselor producător şi consumator;
   
2. 
   semaforul mutex care asigură accesul exclusiv la recipientul de obiecte.
   

Problema producătorilor şi a consumatorilor se implementează folosin algoritmii descrişi în urmatorul program .

var

int n; //dimensiunea recipientului de mesaje

semaphore mutex=1; //controleaza accesul la regiunea critica

semaphore gol=n; //retine nr. pozitii libere din recipient

semaphore plin=0; //retine nr. pozitii ocupate din recipient
Producator ( ) {

int obiect;

while (TRUE) {

creeaza (obiect); // produce un nou obiect obiect

P(gol); // decrementeaza semaforul gol

P(mutex); // intra în regiunea critica

depune (obiect); // introduce obiectul obiect în recipient

V(mutex); // iese din regiunea critica

V(plin); // incrementeaza semaforul plin
}

} // Producator

Consumator ( ) {

int obiect;

while (TRUE) {

P (plin); // decrementeaza semaforul plin

P (mutex); // intra în regiunea critica

extrage (obiect); // scoate un obiect obiect din recipient

V (mutex); // iese din regiunea critica
V(gol); //incrementeaza semaforul gol

consuma (obiect); //consuma obiectul

}

} // Consumator

Programul principal:

PARBEGIN

Producator ( );

|

Consumator ( );

PAREND

B.Problema cititorilor şi a scriitorilor

Se dă o resursă numită bază de date la care au acces două categorii de procese:

• 
  cititori;
  
• 
  scriitori.
  

Procesele cititori accesează resursa numai în citire, iar scriitorii numai în scriere. Se permite ca mai mulţi cititori să citească simultan baza de date. În scimb fiecare proces scriitor trebuie să acceseze exclusiv baza de date.

Vom modela soluţia acestei probleme, folosind două semafoare:

• 
  un semafor bd care asigură acces exclusiv al scriitorilor la baza de date;
  
• 
  un semafor mutex care controlează operaţiile de incrementare şi decrementare a variabilei nrCit, care reţine numărul de cititori activi la un moment dat.
  

Algoritmii după care se lucrează sunt prezentaţi în urmatorul program :

var

semaphore mutex=1;

semaphore bd=1;

int nrCit;

Cititor ( ) {

while (TRUE) {

P (mutex); // obtine accesul la variabila nrCit

nrCit=nrCit + 1;

if (nrCit >=1) {

P(bd); // blocheaza eventualii scriitori

V (mutex); // elibereaya semaforul mutex

citeste_bd ( ); // citeste baza de date

P (mutex);

nrCit = nrCit – 1;

if (nrCit == 0)

V9bd); // elibereaza semaforul bd

V (mutex);

utiliz_data( ) // foloseste datele citite

}

} // Cititor

Scriitor ( ) {

while (TRUE) {

creeaza_date ( ); // creeaza date care vor fi introduse

P (bd); // obtine accesul in scriere

scrie_bd ( ); // scrie informatia in baya de date

V (bd); // elibereaza accesul exclusiv la baza de date

}

} // Scriitor

Programul principal:

PARBEGIN

Scriitor ( );

|

Cititor ( );

PAREND

C.Problema celor 5 filozofi

Deşi insolită prin enunţ, este una dintre cele mai cunoscute probleme de concurenţă. La o masă rotundă stau 5 filozofi, care au doar două misiuni:

- să mănânce;

- să mediteze.

Fiecare filozof are în stânga şi în dreapta lui câte o furculiţă, partajată cu vecinul său, din partea respectivă.

Când un filozof doreşte să mănânce, încearcă să ia cele două furculiţe. Dacă una dintre ele este folosită de un vecin al său, filozoful va trebui să aştepte. UN filozof mănâncă numai când are ambele furculiţe, după care le pune din nou pe masă şi îşi reia operaţia de meditare.

În această problemă, procesele sunt “filozofii”, iar resursele accesate sunt “furculiţele”. Soluţia problemei filozofilor urmăreşte evitarea a două situaţii nedorite:
impasul
apare dacă un filozof aşteaptă la nesfârşit obţinerea unei furculiţe.
infometarea (2.4.2)
apare dacă accesarea furculiţelor se face inechitabil între cei 5 filozofi.

De exemplu, următoarea soluţie poate conduce la impas, când doi filozofi vecini încearcă să obţină o furculiţă ocupată de celălalt. Fiecare dintre ei ocupă mai întâi furculiţa din stânga pe care nu o mai cedă, după care o solicită pe cea din dreapta, care este deja ocupată. Acţiunile celor 5 filozofi sunt descrise în urmatorul program :

Filozof (ind) { // ind – indicele filozofului

Resursa furcSt, furcDr;

While (TRUE) {

Gandeste ( );

ObtineRes (furcSt);

ObtineRes (furcDr);

Mananca ( );

ElibRes (furcSt);

ElibRes (furcDr);

}

} // Filozof

Programul principal:

PARBEGIN

Filozof (1); | Filozof (2); | Filozof (3); |

Filozof (4); | Filozof (5);

PAREND
Soluţii posibile pentru rezolvarea impasului:

Dacă un filozof nu poate obţine şi furculiţa din dreapta, atunci eliberează furculiţa din stânga şi încearcă mai târziu (folosind această soluţie se poate ajunge la “înfometare”).

Un singur filozof să mănânce la un moment dat (serializare).

Obţinerea ambelor furculiţe printr-o operaţie atomică, ceea ce poate conduce la înfometarea de exemplu a filozofului 2, dacă filozofii 1 şi 3 nu “gândesc” nici o dată în acelaşi timp.

Programul urmator dă soluţie corectă, în care gestiunea “furculiţelor” este realizată centralizat de către procesul server ResServer. Programul principal rămâne cel de mai sus.

var

nrFil = 5; // numarul de filozofi

stare [nrFil] // intrarile pot fi: INFOMETAT, MANANCA, GANDESTE

semaphore self [ ] = {1,1,1,1,1}; // semafoare binare asociate

semaphore multex = 1; // pentru acces exclusiv

ResServer ds; // procesul server care gestioneaza furculitele

Filozof (id) { // procedura asociata folozofului cu indicele id

Ds. obtineFurc (id);

mananca ( )

ds. elibFurc (id);

} // Filozof

int dreapta (int i) {

return (nrFil + i – 1) % nrFil;

} // dreapta
int stanga (int i) {

return (i + 1) % nrFil;

} // stanga
obtineFurc (int i) {

P (mutex);

stare [i] = INFOMETAT;

test (i); // verifică dacă vecinii filozofului i nu se află starea

// MANACA - > caz în care filozoful i primeşte cele două

// furculiţe şi trece din starea INFOMETAT în starea

// MANANCA, astfel aşteaptă îndeplinirea condiţiei

respective

V (mutex);

P (self [i]);

} // obtineFurc
elibFurc (int i) {

P (mutex);

stare [i] = GANDESTE;

test (stanga (i));

test (dreapta (i);

V (mutex);

} // elibFurc
test (int k) {

P (mutex);

stare [i] = GANDESTE;

test (stanga (i));

test (dreapta (i));

V (mutex);

} // elibFurc
test (int k) {

if (stare [stanga (k)] ! = MANANCA & &

stare [dreapta (k)] ! = MANANCA & &

stare [k] = = INFOMETAT) {

stare [k] = MANANCA;

V (self [k] );

}

} // test