so_curs_04

7/21/2019 SO_Curs_04

http://slidepdf.com/reader/full/socurs04 1/40

An universitar: 2014 – 2015Facultatea: Automatică şi Calculatoare

Domeniul: Calculatoare şi Tehnologia Informaţiei

Sisteme de Operare

Gestiunea proceselor Sincronizarea proceselor

Secţiunea critică semafoare, aşteptare activă, monitoare, bariere

Paradigme ale programării concurente

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor 2/40

Sincronizarea proceselor

Pentru execuţie procesele au nevoie de acces laresursele sistemului : P!, memorie, disc etc"

#esursele pot fi:

locale sau globale, private sau comune $parta%abile&"

'oate resursele sunt critice $accesibile numaiunui proces la un moment dat&"

Procesele concurează pentru obţinereaaccesului la resurse"

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor /40

Sincronizarea proceselor Definiţie: Sincronizarea proceselor reprezinta acţiunea de

coordonare a activităţii mai multor procese" Sicronizarea presupune posibilitatea de a modifica starea unui proces

la un moment dat p(nă la apariţia unor evenimente ce nu se afla subcontrolul acestuia"

Sincronizarea impune aplicarea excluderii mutuale şi o ordonare aevenimentelor"

Definiţie: )ona de program prin care se apelează o resursăcritică se numeşte secţiune critică (SC)"

Accesul unor procese la resursele critice se face printr*un

protocol de eclu!ere mutuală ("#)$ ce presupune osincronizare ce permite modificarea stării proceselor şieventual comunicaţii"

7/21/2019 SO_Curs_04



!ccesul la sec"iunea critic#

intrarea +n secţiunea critică

tratarea resursei critice din secţiuneacritică

ieşirea din secţiunea critică"

7/21/2019 SO_Curs_04



Condi"iile pentru realizarea e$cluderiimutuale %ntr-o sec"iune critic#

!n singur proces la un moment dat trebuie să executeinstrucţiunile din secţiunea critică

-acă mai mult de un proces sunt blocate la intrarea +nsecţiunea critică şi nici un alt proces nu execută

instrucţiunile din secţiunea critică, +ntr*un timp finitunul din procesele blocate se debloc.ează şi va intra +nsecţiunea critică $pe r(nd vor intra şi celelalte&"

/locarea unui proces +n afara secţiunii critice să nu +mpiedice intrarea altui proces +n secţiunea critică"

Să nu existe procese privilegiate $mecanismul să fieec.itabil pentru toate procesele&"

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor &/40

'$cluderea mutual# - implementare

Semafoare

Aşteptare pe condiţie $aşteptare activă&

0onitoare

/ariere

7/21/2019 SO_Curs_04

http://slidepdf.com/reader/full/socurs04 7/40[SO - 2014-2015] Curs 4 - Gestiunea proceselor (/40

Sema)oare Definitie: Semaforul este un mecanism !e sincronizare a execuţiei

proceselor care acţionează +n mod concurent asupra unor resurse parta%ate" Poate fi o variabilă sau o structură de date abstractă

1ste utilizat pentru controlul accesului la o resursă comună +ntr*un mediumultiproces, multiutilizator

Semafoarele se caracterizează prin: 2aloare: val$s&

coadă de aşteptare: 3$s&

Semafoarele sunt de două tipuri : binare $lucrează cu valori de 4 şi 5&

+ntregi $lucrează cu valori +ntre *n şi n&"

ozile de aşteptare sunt de tip F6F7"

%peraţiile cu semafoare: creare

distrugere

operaţia de intrare +n secţiunea critică : p$s&, p 8 cerere de intrare +n S""

operaţia de ieşire din secţiunea critică : v$s&, v 8 cerere de ieşire +n S""

7/21/2019 SO_Curs_04

http://slidepdf.com/reader/full/socurs04 8/40[SO - 2014-2015] Curs 4 - Gestiunea proceselor */40

Sema)oare&(s) :

val$s& 8 val$s&*5

if $ val$s& 9 4 &

;;trece procesul în coada de aşteptare a semaforului respectiv

;; schimbă starea procesului în blocat <

'(s):

val$s& 8 val$s& =5

if $ val$s& > 4 &

;;scoate primul proces din coada de aşteptare a semaforului ;; schimbă starea procesului în gata de execuţie

<

7/21/2019 SO_Curs_04

http://slidepdf.com/reader/full/socurs04 9/40[SO - 2014-2015] Curs 4 - Gestiunea proceselor +/40

'$cluderea mutual# pentru 2 procese

7/21/2019 SO_Curs_04



,aloarea unui sema)or la unmoment dat

'(s) '0(s)n*(s) – np(s) 2$s& este valoarea unui semafor la un moment dat

np este numarul de treceri prin P$s&

n* este numărul de treceri prin 2$s&

-acă 2$s& ?4 , acest număr ne dă numărul de procesece pot executa instrucţiunile din secţiunea critică"

-aca 2$s& 94, atunci acest număr ne dă numărul deprocese blocate la semafor"

Secţiunile critice pot fi at(t imbricate c(t şi +ntreţesute" @umărul de procese trecute de semaforul s este:

nt(s)min+'0(s)n*(s)$np(s),

7/21/2019 SO_Curs_04



Sema)oare priate numai un singur proces

poate aplica P şi 2asupra lui

celelalte procese put(nd

executa numai 2" 2aloarea iniţială a unui

semafor privat este 4"

Semaforul privat permite

sincronizarea execuţieiunui proces cu o condiţieexternă lui $eventual cuun alt proces&"

7/21/2019 SO_Curs_04



.roiectarea sema)oarelor

Secţiunile critice trebuie +ncadrate de P şi 2ceea ce uneori este mai greu de urmărit

!n proces nu poate fi distrus +n S

2erificarea corectitudinii programelor nu esteuşoară

Gestiunea cozii poate duce la apariţia unorprobleme de proiectare"

7/21/2019 SO_Curs_04



Sincronizarea proceselor cusema)oare

Semafoarele +ntregi se folosesc pentru agestiona un nr" de resurse identice$componentele unei zone tampon şi

resurse fizice&" #esursele se alocă la cerere şi se

eliberează dupa folosirea lor"

(nd nu mai există copii disponibileprocesele se bloc.ează"

7/21/2019 SO_Curs_04



.rolem#: resurse identice un sema)or i procese

execuţia primitivelor P este critică

7/21/2019 SO_Curs_04



ezolareint s 8, s5 8B

p5$&

"""""""""""""""""""""""""""""""""""""""""

P$s5&

P$s& ;; C se ocupa prima #

P$s&

;; C se ocupa a 66*a #

2$s&

2$s& 2$s5&

<

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor 1&/40

'$emplu de e$ecu"ie pentru procese

Execuţia normală se poate

desfăşura în paralel, dar

regiunile critice sunt

serializate

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor 1(/40

Sincronizarea prin ateptare acti#

condiţii: există variabile comune care sunt testate

testul şi modificarea variabilelor să fie operaţii

indivizibile"

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor 1*/40

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor 1+/40

Dezaanta3ele atept#rii actie

consumarea inutilă de timp P! pentru unproces care aşteaptă"

1xistă B operaţii care trebuie realizate:

testarea şi mo!ificarea flag $de aceeaau fost introduse variabilele flag şi turn&"

Gradul ridicat de dificultate +n elaborareaprotocoalelor de intrare şi iesire lucru ce

poate duce pe l(ngă neclarităţi şi la apariţiade erori"

7/21/2019 SO_Curs_04



Sincronizarea )olosind monitoare

!n monitor reprezintă o structură de dateformată din: *aria-ile !e sincronizare numite şi

*aria-ile con!iţii, resurse parta.ate

proce!uri !e acces la resurse" Procedurilepot fi: externe sau interne"

7/21/2019 SO_Curs_04



Sincronizarea )olosind monitoaremonitor monitor*name

delaraţii variabile locale

procedure P5$D&

D

<

D

procedure Pn$&

D

<

<

2ariabilele locale ale unuimonitor nu sunt vizibile dec(tpentru procedurile lui"

Procedurile unui monitor suntpuncte de intrare $pot fi

accesate din exterior& şi ele seexecuta prin excludere mutuală"

&rimiti*ele !e sincronizare /ait C suspendă procesul care

execută Eait pe o variabilă decondiţie şi face disponibil monitorulpentru un alt apel

sinal C reactivează un proces +naşteptare pe o variabilă decondiţie"

7/21/2019 SO_Curs_04



Structura unui monitor

7/21/2019 SO_Curs_04



Cozile de ateptare ale unuimonitor Fiecare variabilă ci are ataşată o coadă şi odată

accesată o procedură a monitorului, un proces +naşteptare pe o condiţie va ceda accesul unui alt proces

+n aşteptare la intrarea +n monitor"

Procesele suspendate după execuţia lui signal ( c i .signal) nu eliberează excluderea mutuala +n monitor deoarece: fie există un proces +n execuţie a unei proceduri +n monitor,

eventual +n aşteptare pe o condiţie

fie este acelaşi proces care*si continuă execuţia c(nd nu mai

sunt altele de reactivat" oada proceselor suspendate este mai prioritara faţă de

aceea de la intrarea +n monitor şi a cozilor de aşteptarepe condiţie

7/21/2019 SO_Curs_04



St#rile unui proces la accesareaunei proceduri din monitor

aşteptare +n coada de intrare a monitorului

aşteptare +ntr*o coadă pe o variabilă decondiţie $wait&

suspendarea prin execuţia signal, carereactivează un proces +n aşteptare pe ovariabilă de condiţie

execuţia normală a instrucţiunilor unei

proceduri din monitor"

7/21/2019 SO_Curs_04



Sincronizarea )olosind ariere

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor 2&/40

Sincronizarea prin transmiterea demesa3e

0esa%ele pot avea dimensiune fixă sau nu"

-acă două procese P şi 3 vor să transmitămesa%e trebuie să stabilească o legătură +ntre

ele" -etalii de implementare şi gestionare a

comunicaţiilor sunt lăsate +n gri%a sistemuluide operare"

Sistemul de transmitere a mesa%elor trebuiesă ofere funcţii de tip: send(destinaţie, mesaj)

receive(sursă, mesaj)

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor 2(/40

Sincronizarea prin transmiterea demesa3e

At(t procesul care trimite mesa%ele, c(t şi cel carele primeşte pot fi blocate sau nu

Sen!recei*e -locante: ambele procese suntblocate p(nă la terminarea comunicării

Sen! ne-locant$ recei*e -locant : procesul ceexecută send +şi continuă execuţia imediat ce atrimis mesa%ul, iar procesul ce execută receiveeste blocat p(nă la sosirea mesa%ului

Sen!recei*e ne-locante: nici un proces nuaşteptă terminarea operaţiilor de comunicaţie

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor 2*/40

Sincronizarea prin transmiterea de mesa3e !dresarea

!irectă: +n acest caz, funcţiilesend;receive includ identificatorulprocesului destinaţie

in!irectă: +n acest caz mesa%ele sunttrimise unei structuri de date parta%ate ceconstau +n cozi numite mailbox $casuţepoştale&

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor 2+/40

'$cluderea mutual# )olosindmesa3econst int n ; number of processes ;

void P$int i&

message msg

E.ile $true&

receive $mutex, msg& ; critical section ;

send $mutex, msg&

; remainder ;

<

<

void main$&

createmailbox $mutex&

send $mutex, null&

parbegin $P$5&, P$B&, " " ", P$n&&

<

7/21/2019 SO_Curs_04



.aradime ale proram#riiconcurente

Problema celor H filosofi

Problema producător C consumator

Problema cititori;scriitori

Problema bărbierului

7/21/2019 SO_Curs_04



.rolema celor 5 )iloso)i

#esurse: furculite

Procese: filosofi"

7/21/2019 SO_Curs_04



.rolema celor 5 )iloso)i

semap.ore forIJHK 8 5,5,5,5,5<

int i

void p.ilosop.er$int i&

E.ile$true&

t.inI$ &

P$forIJiK&

P$forIJ$i=5& mod HK&

eat$ &

2$forIJ$i=5& mod HK&

2$forIJiK&<

<

int forIJHK 8 5,5,5,5,5<

int valet 8 L int i

void p.ilosop.er$int i&

E.ile $true&

P$valet& ;; C intră in cameră

P$forIJiK& ;; C ridică furculiţa st(nga

P$ forIJ$ i = 5& M HK& ;; C ridică furculiţadreapta

;; C măn(ncă

2$forIJiK& ;; C eliberează furculiţa st(nga

2$ forIJ$ i = 5& M HK& ;; C elibereazăfurculiţa dreapta

2$valet& ;; C iese din cameră<

<

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor /40

.rolema produc#tor consumator

implementează un protocol de comunicaţie +ntre B sau mai multe procese careutilizează B sau mai multe resurse duale

$locaţiile ocupate sau libere dintr*un buffer&: unul sau mai mulţi producători introduc

datele +n buffer

un singur consumator extrage datele din

buffer"

7/21/2019 SO_Curs_04



.rolema produc#tor consumator u))er-ul circular cu n loca"ii

ondiţii statice: elementele din buffer sunt citite de consumator +n aceeaşi

ordine +n care sunt scrise de producător

nici un element nu trebuie pierdut sau introdus +n plus" onstante:

io C locaţia unde este un mesa% care se poate citi

il C locaţia de la care putem scrie"

ilio

10 2 n-1

7/21/2019 SO_Curs_04



.rolema produc#tor consumatorCondi"ii de sincronizare:

dacă buffer*ul este gol consumatorul sebloc.ează p(nă c(nd există cel puţin unmesa%"

dacă buffer*ul este plin producatorul sebloc.ează p(nă c(nd există cel puţin olocaţie liberă"

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor &/40

.rolema produc#tor consumator1 produc#tor - 1 consumator int io 8il 84

int liber 8n, ocupat 84

int bufJnK

void producator $int mes&

DDDDD"

P$liber&

buf JilK 8mes ;;adaugă mesa%

il8 $il =5& Mn 2$ocupat&

<

int consumator$&

DDDDD""

P$ocupat&

mes8buf JioK ;;citeşte mesa%

io 8 $io =5& Mn

2$liber&

DDDDD"

consuma$mes&

<

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor (/40

678 produc#tori i 6l8 consumatori

il este resursă critică pentru producători

se introduce un semafor li-er pe care +liniţializăm cu n"

io resursă critică pentru consumatori se introduce semaforul ocupat iniţializat

cu 4"

Semaforul s asigură accesul la secţiuneacritică şi este iniţializat cu 5"

. l d #

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor */40

.rolema produc#tor consumator678 produc#tori i 6l8 consumatoriint io 8 il84

int liber 8n, ocupat 84, s 85

void producator$int mes&

DDD" P$liber&

P$s&

bufJilK 8mes ;; adaugă mesa%

il 8$il =5& Mn

2$s&

2$ocupat&

DDD""

<

int consumator$&

DDD"" P$ocupat&

P$s&

mes8bufJioK ;;citeşte mesa%

io 8$io =5& Mn

2$s&

2$liber&

consuma$mes&

<

. l d #t t

7/21/2019 SO_Curs_04


[SO - 2014-2015] Curs 4 - Gestiunea proceselor +/40

.rolema produc#tor consumator u))er in)init

un semafor s pentru a realiza excludereamutuală asupra buffer*ului

un semafor n pentru a sincroniza

producătorul şi consumatorul asupradimensiunii buffer*ului

. l d #t t

7/21/2019 SO_Curs_04


.rolema produc#tor consumator u))er in)initint n 8 4, s 8 5 ;;semafoare

int io 8 il 84

void producător $&

E.ile $true&

produce$&

P$s&

bufJilK 8mes ;; adaugă mesa%

il 8$i

l =5& Mn

2$s&

2$n&

<

<

void consumator$&

E.ile $true&

P$n&

P$s&

mes8bufJioK ;;citeşte mesa%

io 8$io =5& Mn 2$s&

consume$&

<

<

so_curs_04

Documents