Algoritmul lui Peterson este un algoritm de programare paralelă pentru excluderea reciprocă a firelor de execuție a codului, dezvoltat de Harry Peterson în 1981. Deși formulat inițial pentru cazul cu 2 fire, algoritmul poate fi generalizat la un număr arbitrar de fire . Algoritmul este numit în mod condiționat algoritm software, deoarece nu se bazează pe utilizarea instrucțiunilor speciale ale procesorului pentru a dezactiva întreruperile , blocarea magistralei de memorie etc., doar variabilele de memorie partajată și o buclă sunt folosite pentru a aștepta intrarea în sistemul critic . secțiunea codului executabil.
Înainte de a începe execuția unei secțiuni critice de cod, un fir trebuie să apeleze o procedură specială (să o numim lock() ) cu numărul său ca parametru. Trebuie să aranjeze ca firul să aștepte rândul său să intre în secțiunea critică. După ce a executat secțiunea critică și a părăsit-o, thread-ul apelează o altă procedură (să o numim unlock() ), după care alte fire vor putea intra în regiunea critică. Să vedem cum acest principiu general este implementat de algoritmul Peterson pentru două fire.
Cod în C++
clasa PetersonMutex { public : PetersonMutex () { vreau [ 0 ]. magazin ( fals ); vreau [ 1 ]. magazin ( fals ); asteptare . magazin ( 0 ); } blocare nulă ( int threadId ) { int alt = 1 - threadId ; vreau [ threadId ]. magazin ( adevărat ); // indicator de interes al firului curent în așteptare . store ( threadId ); // spune că acest thread va aștepta dacă este necesar /* Așteptați bucla. Suntem în această buclă dacă al doilea proces își execută secțiunea critică. Când cel de-al doilea proces iese din secțiunea critică, se execută unlock(int threadId), indicatorul interesat (want[other]) devine fals și bucla se termină. */ în timp ce ( vreau [ altul ]. încărcare () && așteptare . încărcare () == threadId ) { // așteptați } } void deblocare ( int threadId ) { vreau [ threadId ]. magazin ( fals ); } privat : std :: array < std :: atomic < bool > , 2 > doresc ; // fire interest flags std :: atomic < int > waiting ; // așteaptă numărul firului };Pentru claritate, să luăm în considerare două scenarii pentru execuția firelor paralele cu numerele 0 și 1 .
Blocarea apelului în firele secvenţial| Timp | Firma 0 | Fluxul 1 |
|---|---|---|
| t1 _ | int alt = 1; | |
| t2 _ | vreau[0] = adevărat; | |
| t3 _ | așteptare = 0; | |
| t4 _ | în timp ce (în așteptare == 0 && doresc[1]); | |
| t5 _ | Zona codului critic |
int alt = 0; |
| t6 _ | doresc[1] = adevărat; | |
| t7 _ | așteptare = 1; | |
| t8 _ | în timp ce (în așteptare == 1 && doresc[0]); | |
| t9 _ | în timp ce (în așteptare == 1 && doresc[0]); | |
| t 10 | doresc[0] = fals; | Zona codului critic |
| t 11 | ||
| t 12 | ||
| t 13 | doresc[1] = fals; |
Se blochează apelurile firului 0 , indicând că este „interesat” prin setarea steagului de coadă pentru a lăsa loc firului 1 . Deoarece acesta din urmă nu este încă „interesat” să lovească regiunea critică, execuția revine imediat de la blocare și firul 0 intră în ea. Acum blocarea este apelată de firul 1 , pentru care sunt efectuate și acțiunile de mai sus. Dar, deoarece firul 0 este încă „interesat” (want[0] == adevărat), execuția rămâne blocată - firul 1 așteaptă (în tabel, acest lucru este exprimat prin repetarea instrucțiunii pentru bucla „while”). De îndată ce firul 0 apelurile se deblochează și își resetează indicatorul „interesat”, firul 1 intră în regiunea critică și în cele din urmă se deblochează .
Blocarea apelurilor în fire aproape simultan| Timp | Firma 0 | Fluxul 1 |
|---|---|---|
| t1 _ | int alt = 1; | |
| t2 _ | int alt = 0; | |
| t3 _ | doresc[1] = adevărat; | |
| t4 _ | vreau[0] = adevărat; | |
| t5 _ | așteptare = 0; | |
| t6 _ | așteptare = 1; | |
| t7 _ | în timp ce (în așteptare == 1 && doresc[0]); | |
| t8 _ | în timp ce (în așteptare == 1 && doresc[0]); | |
| t9 _ | în timp ce (în așteptare == 0 && doresc[1]); | |
| t 10 | Zona codului critic |
în timp ce (în așteptare == 1 && doresc[0]); |
| t 11 | în timp ce (în așteptare == 1 && doresc[0]); | |
| t 12 | în timp ce (în așteptare == 1 && doresc[0]); | |
| t 13 | doresc[0] = fals; | Zona codului critic |
| t 14 | ||
| t 15 | ||
| t 16 | doresc[1] = fals; |
Firele de execuție apelează blocare aproape simultan , setând indicatorul „interesat” și cedând coada de execuție unui fir concurent prin setarea valorii variabilei de așteptare . Deoarece firul 1 este ultimul care face acest lucru , va trebui deja să aștepte într-o buclă în timp ce firul 0 intră nestingherit în regiunea critică a codului. Așteptarea firului 1 , ca în tabelul anterior, este exprimată prin repetarea instrucțiunii while pentru bucla wait. După ce firul 0 iese din regiunea critică și își resetează indicatorul de „interes”, firul 1 își continuă execuția și în cele din urmă resetează steag-ul corespunzător, apelând unlock .
Firele 0 și 1 nu pot intra niciodată în secțiunea critică în același timp: dacă 0 a intrat în secțiune, se setează want[0] la true . Apoi fie want[1] == false (atunci firul 1 nu este în secțiunea critică), fie așteptând == 1 (apoi firul 1 încearcă să intre în secțiunea critică și se rotește într-o buclă), fie firul 1 încearcă să intre în secțiune critică după setarea want [1] == true , dar înainte de a seta așteptarea și bucla. Astfel, dacă ambele procese sunt în secțiunea critică, ar trebui să fie want[0] && want[1] && waiting == 0 && waiting == 1 , dar aceasta nu poate fi ambele în același timp și am ajuns la o contradicție .
Pentru ca ambele procese să fie în așteptare, sunt necesare valori opuse ale variabilei de așteptare, ceea ce este imposibil.
Este posibil ca un proces să se ocupe de o secțiune critică de mai multe ori la rând, în timp ce altul, care și-a exprimat dorința de a ajunge acolo, va aștepta. În algoritmul lui Peterson, procesul nu va aștepta mai mult de o intrare în secțiunea critică: după executarea deblocării și reintroducerea blocării , procesul se va seta ca așteptare și va cădea într-o buclă care nu se va încheia până la finalizarea unui alt proces.