Programare Concurenta

7/29/2019 Programare Concurenta

http://slidepdf.com/reader/full/programare-concurenta 1/9

Sistemele multiprocesor : calculele sunt repartizate mai multor procesoare fizice.În aceste sisteme multiprocesor, comunicarea între procesoare are loc fie prin zone dememorie comune (partajate), fie prin canale.

Algoritmi de calcul paralel (care determină soluţia unei probleme prin

descompunerea ei în subprobleme independente, rezolvabile în paralel pe procesoaredistincte); de exemplu este evident că suma a doi vectori, calculată prin: for i:=1 to n do

c[i]:=a[i]+b[i]

se efectuează mai rapid dacă avem la dispoziţie n procesoare, fiecare capabil să efectuezeo adunare.

Ce este programarea concurentă ?

Considerentele de mai sus sunt aplicabile mai ales în cazul în care acţiunile careurmează să se execute concomitent sunt independente între ele. imprimantă să aparăamestecate ieşirile programelor mai multor utilizatori).

Vom numi proces un program secvenţial în curs de executare; drept urmare, lafiecare moment de timp este executată cel mult o instrucţiune a sa.

Vom denumi program concurent un program care în timpul executării salecrează mai multe procese care se execută într-un paralelism abstract, adică nu neapărat

pe procesoare distincte. În permanenţă trebuie însă gândit ca şi când fiecărui proces îieste asociat în mod univoc un procesor fizic; desigur că şi implementarea trebuie gândităastfel încât să permită acest lucru.

Aproape întotdeauna, executarea concurentă a proceselor cere o anumită

cooperare între ele, deci sunt necesare anumite mecanisme care să asigure comunicareaşi sincronizarea între procese. Este nevoie de un alt mod de gândire, de alte "unelte", dealtă înţelegere a noţiunii de program corect (deci şi de alte metode de verificare acorectitudinii).

Conform celor de mai sus, putem considera că fiecare proces este executat decâte un procesor ("calculator" ce are unitate centrală, memorie, canale pentru operaţiilede intrare/ieşire).

Programarea concurentă este menită să rezolve interacţiunile dintre procese.Atenţia principală este îndreptată deci asupra modalităţilor în care pot fi realizateinteracţiunile dorite şi mai puţin asupra a ceea ce realizează programele secvenţiale ce

constituie fiecare proces în parte. Natura problemelor este diferită de cea întâlnită în programarea secvenţială. Sunt tratate în special probleme de simulare a unor situaţiiconcurente reale şi nu probleme care urmăresc obţinerea unui rezultat numeric.

Iată două exemple tipice de probleme întâlnite în programarea concurentă:

1) Problema rezervării biletelor : Fiecare terminal al unei reţele de calculatoare este plasat într-un punct de vânzare a biletelor pentru un anumit spectacol. Se cere să se găsească o modalitate de a evita vânzarea a două bilete pentru acelaşi loc.

2) Problema Producător → Consumator: Producătorul fabrică articole de un



2 1. INTRODUCERE ÎN PROGRAMAREA CONCURENTĂ

──────────────────────────────────

anumit tip şi le plasează pe o bandă. Consumatorul ia câte un obiect de pe bandă şi îl "consumă". Se cere să se simuleze aceste activităţi, evitându-se încercările

producătorului de a plasa un articol pe bandă când aceasta este plină, precum şiîncercările consumatorului de a lua un obiect de pe bandă când aceasta este goală(dificultatea constă deci în realizarea unei sincronizări).

Executarea proceselor concurente

În vederea asigurării portabilităţii, dar şi a posibilităţii ca unui procesor fizic să îifie ataşate mai multe procesoare logice, nu se va face nici o presupunere asupra vitezeide lucru a procesoarelor. Cu alte cuvinte, orice supoziţii asupra raportului vitezelor adouă procesoare, ca şi asupra ritmicităţii executării instrucţiunilor în cod maşină dincadrul aceluiaşi proces, sunt neavenite (nu ne ocupăm aici de sistemele concurente întimp real).

Singura ipoteză relativă la timp pe care ne vom baza atunci când scriem sau/şianalizăm programe concurente şi care este esenţial pentru înţelegerea acestui tip de

programare este următorul: "pentru fiecare proces şi pentru fiecare două instrucţiunimaşină consecutive ale sale, intervalul de timp între executarea lor este neprecizat, dar

finit ". Vom considera această ipoteză ca fiind condiţia fundamentală a executăriiconcurente a programelor .

Un caz limită este cel al unui singur procesor fizic. Acesta trebuie să aloce "felii"de timp proceselor concurente astfel încât să fie satisfăcută condiţia enunţată mai sus.Modul în care se realizează acest lucru (prin generare aleatoare sau prin alegerea uneianumite structuri ca de exemplu o coadă, o coadă cu prioritate etc.) va fi precizat lafiecare modalitate de abordare a concurenţei.

Programarea concurentă rezervă o serie de surprize informaticianului obişnuit cu

programarea secvenţială. Prezentăm în continuare câteva dintre ele.1) În programarea secvenţială, următoarea secvenţă de instrucţiuni:

i:=1; i:=2

este echivalentă cu a doua instrucţiune. În programarea concurentă secvenţa de mai susnu are nimic redundant. Într-adevăr, în intervalul de timp dintre executarea celor douăinstrucţiuni (în cadrul aceluiaşi proces) este posibil ca celelalte procese să execute diferiteinstrucţiuni care să folosească efectiv faptul că un anumit interval de timp (asupralungimii căruia nu putem face nici o ipoteză) valoarea lui i este egală cu 1.

2) Efectul instrucţiunii: if i=1 then j:=j+i

în cazul în care valoarea lui i era 1 la începutul executării acestei instrucţiunicondiţionale nu constă neapărat în mărirea cu o unitate a valorii lui j, deoarece întremomentul efectuării comparaţiei şi momentul efectuării atribuirii valoarea lui i poate fieventual modificată de un alt proces. Analog, dacă într-un proces apare secvenţa deinstrucţiuni:i:=1; if i=1 then instr

atunci pe de o parte nu este neapărat adevărat că este îndeplinită condiţia i=1 dininstruţiunea if, iar pe de altă parte nu este neapărat adevărat că în momentul executăriiinstrucţiunii instr valoarea lui i este egală cu 1; în schimb afirmaţia valoarea lui i afost egală cu 1 la un moment de timp anterior" este adevărată şi poate fi utilă (deexemplu în a demonstra că procesul are o anumită evoluţie).



Este uşor de observat că aceste comportări "anormale" din punctul de vedere al programării secvenţiale îşi au cauza în utilizarea de către mai multe procese a unei arii(comune) de memorie. De aceea, aşa cum vom vedea în capitolele următoare, multeabordări ale programării concurente evită comunicarea între procese prin intermediulvariabilelor globale, înlocuind-o cu alte mecanisme.

Programarea concurentă se mai deosebeşte de programarea secvenţială şi prinfaptul că programele pot avea comportare nedeterministă: "la executări diferite pentruacelaşi set de date de intrare, rezultatele nu vor fi neapărat aceleaşi".

Pentru executarea proceselor concurente s-a ales modelul aleator , care constă înrepetarea ciclică a următoarelor acţiuni de către fiecare procesor fizic:

1) alege aleator unul dintre procesele concurente cărora nu le este asociat un procesor fizic;

2) execută, pe parcursul unui interval de timp ales aleator, instrucţiuni ale sale.

Noţiunea de secţiune critică

Problema rezervării biletelor . Reamintim că problema constă în simulareaactivităţii mai multor terminale conectate la un calculator central, terminale de la care se

pot face rezervări de bilete pentru un anumit spectacol; bineînţeles că trebuie evitatăvânzarea a două bilete pentru acelaşi loc.

Considerăm următoarea modalitate prin care un proces face rezervarea, înipoteza că mai există locuri libere şi că fiecare persoană ce accesează un terminal areanumite preferinţe pentru locurile din sală, dar este hotărâtă să cumpere un bilet:

repeat

rez:=false; { soseşte un nou client }repeat { până când clientul cere un loc liber }

expune planul săliiread(loc_client); { citeşte locul cerut de client }

if sala[loc_client]=1 { locul este liber } then begin

sala[loc_client]:=0; rez:=true;

eliberează bilet end

else write('Alta optiune: ') until rez

forever

Este uşor de observat că această modalitate este incorectă.

Vom numi secţiune critică o secvenţă de instrucţiuni a căror executare trebuie săse supună următoarei reguli: în momentul în care un proces P începe executarea primeiinstrucţiuni din secvenţă, toate celelalte procese îşi întrerup temporar activitatea pânăla terminarea executării ultimei instrucţiuni din secvenţă de către procesul P. În acestecondiţii spunem că are loc o excludere reciprocă (cel mult un proces se poate afla într-osecţiune critică).

Să observăm că dacă în codul de mai sus ataşat instrucţiunii if primele patruacţiuni (linii de cod) ar forma o secţiune critică, atunci modalitatea de rezervare de maisus ar fi corectă.




──────────────────────────────────

Problema grădinilor ornamentale. Intrarea în grădinile ornamentale ale unuioraş oriental se face prin două porţi. Se pune problema ţinerii evidenţei numărului de

persoane care au intrat în grădină.Se introduce variabila globală n, a cărei valoare curentă reprezintă numărul

persoanelor ce au intrat în grădini. Fiecărei porţi i se asociază în mod natural un proces,

cele două procese urmând a fi executate concurent. În cadrul fiecărui proces valoareavariabilei n este mărită cu o unitate de fiecare dată când o persoană intră în grădini pe poarta asociată procesului.

La fiecare executare a lui rezultatul va fi altul! Explicaţia constă în primul rând înfaptul că instrucţiunea n:=n+1 nu este nedivizibilă (nu este o acţiune "atomică"), iar înal doilea rând în modul de executare al programelor concurente. Într-adevăr,instrucţiunea n:=n+1 este în realitate formată din trei instrucţiuni în cod maşină:

LOAD n,r { încarcă n în registrul r al CPU }INC r { incrementează valoarea lui r cu 1 }

STORE r,n { salvează valoarea registrului în n }Fie r1 şi r2 registrele unităţii centrale folosite de cele două procese. Atunci în

cazul în care pe fiecare poartă intră trei persoane, este posibilă următoarea succesiune deacţiuni:

Pentru exemplificare, să considerăm cazul a două porţi (procese) P1 şi P2. Fier1 şi r2 registrele unităţii centrale folosite de cele două procese. Atunci în cazul în care

pe fiecare poartă intră trei persoane, este posibilă (printre multe altele) următoareasuccesiune de acţiuni (următorul scenariu):

Acţiune total r1 r2

0

P1 încarcă 0

P1 incrementează 1

P2 încarcă 0

P2 incrementează 1

P2 salvează 1

P2 încarcă 1

P2 incrementează 2

P2 salvează 2

P1 salvează 1

urmată de o succesiune analoagă în care se interschimbă P1 cu P2. Rezultatul final va fi2, mai mic chiar decât numărul persoanelor ce intră prin fiecare poartă!

Să observăm că dacă instrucţiunea n:=n+1 (mai corect spus cele treiinstrucţiuni maşină în care se descompune) ar forma o secţiune critică, programul ar ficorect.

Modelul aleator

Fiecare procesor:1) alege aleator un proces "liber"2) execută un interval de timp aleator instrucţiuni ale sale3) goto 1)



Excludere reciprocă

Forma fiecărui proces P i :repeat

protocol_intrarei

SCi // se folosesc resurse comuneprotocol_ieşirei

SNCi // nu se folosesc resurse comuneuntil false

ER (exclucere reciprocă propriu-zisă)cel mult un proces este în SC a sa

CC (competiţie constructivă)dacă mai multe procese vor să intre in SC a lor, nu se împiedică unul pe altul

CL (conexiune liberă)dacă un proces "întârzie" în SNC a sa, celelate nu sunt împiedicate să intre deoricâte ori în SC a lor

= = = = = = = = = = = = = = = = = = = =

Varianta_1

process P1; process P2;

repeat repeatwhile ales=2 do; while ales=1 do;

SC1 SC2

ales:=2; ales=1;

SNC1 SNC2

until false until falseend; end;

ales:=1;{ P1; P2 }

Obs. ER, CC, dar nu CL=====================================================

Varianta_2





──────────────────────────────────

repeat repeat

while ind2 do; while ind1 do;

ind1:=true; ind2:=true;

SC1 SC2ind1:=false; ind2:=false;

SNC1 SNC2

until false until false

end; end;

ind1:=false; ind2:=false;

{ P1; P2 }

Obs. CL, CC, dar nu ER ======================================================

Varianta_3

process P1; process P2;repeat repeatind1:=true; ind2:=true;

while ind2 do; while ind1 do ;

SC1 SC2

ind1:=false; ind2=false;SNC1 SNC2


ind1:=false; ind2:=false;{ P1; P2 }

Obs. ER, CL, dar nu CC (procese prea egoiste)======================================================

Varianta_4


repeat repeatind1:=true; ind2:=true;

while ind2 do while ind1 do

begin begin

ind1:=false; ind2:=false;ind1:=true ind2:=true

end; end;SC1 SC2

ind1:=false; ind2:=false;SNC1 SNC2


ind1:=false; ind2:=false;{ P1; P2 }

Obs. ER, CL, dar nu CC (procese prea politicoase)



Algoritmul Lamport pentru două procese

• Prima formă (greşită)

Variabile globale:n1 : numărul de ordine al primei persoane (iniţial = 0);n2 : numărul de ordine celei de a doua (iniţial = 0);

Procesul P1repeat

n1 ← n2+1;

while (n2<>0) and (n2<n1) do ;

SC1n1 ← 0

SNC1

until false

Procesul P2

repeat

n2 ← n1+1;

while (n1<>0) and (n1<=n2) do ;SC2

n2 ← 0

SNC2

until false

Observaţii:- Se poate întâmpla ca n1=n2=1, deci ca ambele procese să aibă acelaşi număr de ordine (de exemplu dacă întâi se calculează membrii drepţi ai atribuirilor);- Se poate întâmpla ca ambele procese să intre în SC a lor:

P2 : calculează membrul drept=1;P1 : calculează membrul drept =1P2 : n2 ← 1 şi intră în SC2P1 : n1 ← 1 intră în SC1 (datorită faptului că P1 "gândeşte mai greu").

• A doua formă (corectă)

Adăugăm variabilele globale:calcul1 ⇔prima persoană îşi calculează numărul de ordine (iniţial false);calcul2 ⇔ a doua persoană îşi calculează numărul de ordine (iniţial false).

SC

Registru




──────────────────────────────────

Procesul P1

repeat

calcul1 ← true; n1 ← n2+1; calcul1 ← false;

while calcul2 do ;while (n2<>0) and (n2<n1) do ;

SC1

n1 ← 0SNC1

until false

Procesul P2

repeat

calcul2 ← true; n2:=n1+1; calcul2 ← false;

while calcul1 do ;

while (n1<>0) and (n1<=n2) do ;SC2

n2 ← 0

SNC2

until false

CC : Dacă ambele vor să intre în SC a lor, înseamnă că n1≠ 0 şi n2≠ 0. Atunci unadintre condiţiile n2<n1 şi n1≤ n2 este îndeplinită.

CL : Când P1 întârzie în SNC1, avem n1=0 şi calcul1=false. Atunci cele douăinstrucţiuni while din P2 sunt echivalente cu instrucţiunea vidă şi P2 poatetrece de oricâte ori prin SC2. Cealaltă situaţie este analoagă.

ER : Doar una dintre condiţiile n2<n1 şi n1≤ n2 este îndeplinită.

Algoritmul Lamport pentru np procese

Fie np numărul de procese, tabloul nr(np) al numerelor de ordine şi tabloulcalcul(np) al valorilor booleene; elementele celor două tablouri sunt iniţializate cu0, respectiv false.

Vom mai folosi funcţia max, cu rezultat întreg, care calculează 1 + maximuldintre elementele lui calcul, precum şi funcţia cu rezultat boolean:

function preferat(i,j):boolean;if (nr[i]=0) or (nr[i]>nr[j])

then preferat ← false

else if nr[i]<nr[j]then preferat ← true

else preferat ← i<j

end;

care stabileşte dacă procesul i este preferat procesului j; aceasta se întâmplă însituaţiile:

- 0<nr[i]<nr[j];- 0<nr[i]=nr[j] şi i<j.



Procesul Pi

repeatcalcul[i] ← true; nr[i] ← max; calcul[i] ← false;

for j:=1 to np do

while calcul[j] do ;

while preferat(j,i) do ;end;

SCi

nr[i] ← 0

SNCiuntil false

Programare Concurenta

Documents

Transcript of Programare Concurenta