APD - Note Curs - 4 Semafoare

8/8/2019 APD - Note Curs - 4 Semafoare

1/7

Semafoare

Sectiuni critice

Problema: fiecare proces P(i) al unei colectii de procese P(i:1..n) executa ciclic o sectiune

critica in care are acces exclusiv la anumite resurse partajate urmata de o sectiune

necritica in care foloseste doar resurse locale.Se utilizeaza tipul special sem si primitivele P si V. Rolul lor este asigurarea excluderii

mutuale intre procesele care acceseaza sectiunea critica.

var mutex: sem := 1;

P(i:1..n)::

do true ->

P(mutex);

Sectiune critica;

V(mutex);

Sectine necritica

od

Producatori si consumatori

Problema: se considera mai multi producatori si mai multi consumatori care comunica

printr-un singur tampon partajat. Un producator pune o valoare in tampon, iar un

consumator ia o valoare din tampon.

Trebuie asigurat ca valorile nu sunt suprascrise si nu sunt citite din tampon de mai multe

ori.

var buf: T;

var gol: sem := 1; plin: sem := 0;

Producator (i: 1..M)::

var v: T;

do true ->

v := produce ();

P(gol);

buf := v;

V(plin)

od;

Consumator (i: 1..N)::

var w: T;

do true ->P(plin);

w := buf;

V(gol);

consuma (w);

od;


2/7

Semafoarele gol si plin sunt binare si asigura excluderea mutuala. La un moment dat, un

singur proces (fie Producator, fie Consumator) depune sau extrage o valoare din buf.

Comunicarea producator si consumator prin tampon limitat

Un producator si un consumator care comunica printr-un tampon limitat la k valori.

var buf: array [1:k] of T;

var gol: sem := k; plin: sem := 0;

Producator::

var v: T;

var ultim: int := 1;

do true ->

v := produce ();

P(gol);

buf[ultim] := v; ultim := ultim mod k + 1;

V(plin)

od;

Consumator::

var w: T;

var prim: int := 1;

do true ->

P(plin);

w := buf[prim]; prim := prim mod k + 1;

V(gol);

consuma (w);

od;

Semafoarele gol si plin sunt generale. Ele numara locurile goale din buf, respectiv

valorile depuse in buf. Procesul Producator acapareaza un loc gol (daca nu exista atunci

se blocheaza pana apare unul) si depune o valoare. Procesul Consumator acapareaza o

valoare depusa (daca nu exista atunci se blocheaza pana apare una) si preia valoarea din

buf. Operatiile de depunere si de extragere nu se exclud. Producator poate depune o

valoare in pozitia ultim din bufin timp ce Consumator preia una din pozitia prim din

buf.

Mai multi producatori si mai multi consumatori

var buf: array [1:k] of T;

var prim: int := 0; ultim: int := 0;

var gol: sem := k; plin: sem := 0;

var mutexP: sem := 1; mutexC: sem := 1;

Producator(i:1..M)::

var v: T;

do true ->


3/7

v := produce ();

P(gol);

P(mutexP);

buf[ultim] := v; ultim := ultim mod k + 1;

V(mutexD);

V(plin)

od;

Consumator (i: 1..N)::

var w: T;

do true ->

P(plin);

P(mutexC);

w := buf[prim]; prim := prim mod k + 1;

V(mutexC);

V(gol);

consuma (w);

od;

Variabilele prim si ultim au devenit partajate intre procesele Consumator respectiv

Producator. Accesul si modificarea lor trebuie facute in excludere mutuala. Pentru

aceasta se foloseste semaforul mutexP pentru procesele Producator, respectiv mutexC

pentru procesele Consumator.

Problema filozofilor

Cinci filozofi stau in jurul unei mese rotunde si isi petrec timpul gandind si mancand. In

mijlocul mesei este o farfurie cu spaghete. Pentru a putea manca, un filozof are nevoie dedoua furculite. Pe masa sunt cinci furculite, fiecare situate intre doi filozofi vecini.

Regula este ca fiecare filozof poate folosi furculitele din imediata sa apropiere. Problema

este sa se scrie un program care simuleaza comportarea filozofilor. In particular, trebuie

evitata situatia in care nici un filozof nu poate acapara ambele furculite (de exemplu

furculita din stanga sa si nu ii mai da drumul).

var f: array [1:5] of sem := ([5] 1);

Filozof (i:1..4)::

do true ->

P(f[i]); P(f[i+1]);

mananca;V(f[i]); V(f[i+1]);

gandeste

od;

Filozof (5)::

do true ->

P(f[1]); P(f[5]);


4/7

mananca;

V(f[1]); V(f[5]);

gandeste

od;

Daca toti filozofii ar lua mai intai furculita din stanga si apoi pe cea din dreapta se poateajunge la blocare definitiva prin asteptare circulara: fiecare asteapta o resursa pe care

procesul care a acaparat-o nu o elibereaza. Solutia ca sa se evite asteptarea circulara este

ca unul din filozofi sa procedeze altfel si anume sa ia mai intai furculita din dreapta si

apoi pe cea din stanga.

Problema cititorilor si scriitorilor

Problema: exista doua tipuri de procese, cititori si sciitori care impart o resursa. Mai multi

cititori pot avea acces simultanla resursa comuna daca nici un scriitor nu o modifica in

acelasi timp. Un scriitor poate modifica resursa daca ea nu este acesata de nici un cititor.

var nr: int := 0; mutexR: sem := 1; rw: sem := 1;

Cititor (i: 1..m)::

do true ->

P(mutexR);

nr := nr+1;

if nr = 1 -> P(rw) fi;

V(mutexR);

citeste din resursa comuna;

P(mutexR)

nr := nr-1;

if nr = 0 -> V(rw) fi;

V(mutexR);

od;

Scriitor (j: 1..n)::

do true ->

P(rw);

scrie in resursa comuna;

V(rw);

od;

Algoritmul tine evidenta numarului de cititori nr care folosesc resursa. Solutia acorda

preferinta cititorilor: daca un cititor acapareaza resursa, alti cititori pot sa i se alature si saciteasca. Doar cand ultimul cititor a terminat, resursa este eliberata (V(rw)).

Pentru a aplica alte politici, se introduc alte variabile de contorizare a cititorilor si

scriitorilor:

nw - numarul de scriitori care folosesc resursa

nr - numarul de cititori care folosesc resursa

dw - numarul de scriitori care asteapta sa foloseasca resursa


5/7

dr - numarul de cititori care asteapta sa foloseasca resursa.

"Split binary semaphore": folosit pentru a implementa atat excluderea mutuala cat si

sincronizarea conditionata. Implementat astfel:

e semafor de intrare controleaza intrarea intr-o actiune atomicar semafor pentru intarzierea cititorilor (asteapta ca nw=0)

w semafor pentru intarzierea scriitorilor (asteapta ca nw=0 si nr=0)

Semafoarele formeaza impreuna un "split binary semaphore":

- cel mult un semafor este 1 la un moment dat 0 dr := dr-1; V(r)

[] dr=0 -> V(e)

fi;


P(e)

nr := nr-1;

if nr = 0 and dw>0 -> dw := dw-1; V(w)

[] nr>0 or dw=0 -> V(e)

fi;

od;


do true ->

P(e);

if nr>0 or nw>0 -> dw := dw+1; V(e); P(w) fi;


6/7

nw := nw+1;

V(e);


P(e)

nw := nw-1;

if dr>0 -> dr := dr-1; V(r)

[] dw>0 -> dw := dw-1; V(w)

[] dr=0 and dw=0 -> V(e)

fi;

od;

In solutia urmatoare se prezinta o alta varianta in care:

- noile cereri de la cititori sunt intarziate daca un scriitor asteapta

- un cititor intarziat este trezit doar daca nu exista un scriitor in asteptare.

var nr: int := 0; nw: int := 0; /*(nr=0 or nw=0) and nw0 -> dr := dr+1; V(e); P(r) fi;

nr := nr+1;

if dr>0 -> dr := dr-1; V(r)

[] dr=0 -> V(e)

fi;


P(e)

nr := nr-1;

if nr = 0 and dw>0 -> dw := dw-1; V(w)

[] nr>0 or dw=0 -> V(e)

fi;

od;


do true ->

P(e);

if nr>0 or nw>0 -> dw := dw+1; V(e); P(w) fi;nw := nw+1;

V(e);


P(e)

nw := nw-1;

ifdr>0 and dw=0 -> dr := dr-1; V(r)

[] dw>0 -> dw := dw-1; V(w)


7/7

[] dr=0 and dw=0 -> V(e)

fi;

od;

APD - Note Curs - 4 Semafoare

Documents

Transcript of APD - Note Curs - 4 Semafoare