Petersonův algoritmus je paralelní programovací algoritmus pro vzájemné vyloučení vláken spouštění kódu, vyvinutý Harrym Petersonem v roce 1981. Přestože byl původně formulován pro případ 2 vláken, lze algoritmus zobecnit na libovolný počet vláken . Algoritmus se podmíněně nazývá softwarový algoritmus, protože není založen na použití speciálních instrukcí procesoru k deaktivaci přerušení , blokování paměťové sběrnice atd., k čekání na vstup do kritické paměti se používají pouze proměnné sdílené paměti a smyčka. části spustitelného kódu.
Před zahájením provádění kritické části kódu musí vlákno zavolat speciální proceduru (nazvěme ji lock() ) s jejím číslem jako parametrem. Musí zajistit, aby vlákno počkalo, až na něj přijde řada a vstoupí do kritické sekce. Po provedení kritické sekce a jejím opuštění vlákno zavolá další proceduru (nazvěme ji unlock() ), po které budou moci do kritické oblasti vstoupit další vlákna. Podívejme se, jak tento obecný princip implementuje Petersonův algoritmus pro dvě vlákna.
Kód v C++
třídy PetersonMutex { veřejnost : PetersonMutex () { chtít [ 0 ]. uložit ( nepravda ); chtít [ 1 ]. uložit ( nepravda ); čekání . uložit ( 0 ); } void lock ( int threadId ) { int other = 1 - threadId ; chtít [ ID vlákna ]. uložit ( pravda ); // indikátor zájmu aktuálního vlákna čekajícího . úložiště ( ID_vlákna ); // říká, že toto vlákno bude v případě potřeby čekat /* Wait loop. Jsme v této smyčce, pokud druhý proces vykonává svou kritickou sekci. Když druhý proces opustí kritickou sekci, provede se unlock(int threadId), příznak zájmu (want[other]) se stane false a smyčka skončí. */ while ( chtít [ other ]. load () && wait . load () == threadId ) { // počkat } } void unlock ( int threadId ) { chtít [ ID vlákna ]. uložit ( nepravda ); } soukromé : std :: pole < std :: atomic < bool > , 2 > chci ; // příznaky zájmu vlákna std :: atomic < int > čekání ; // číslo čekajícího vlákna };Pro názornost uvažujme dva scénáře provádění paralelních vláken s čísly 0 a 1 .
Vlákna volají zámek postupně| Čas | Vlákno 0 | Stream 1 |
|---|---|---|
| t1 _ | int jiné = 1; | |
| t2 _ | chtít[0] = pravda; | |
| t3 _ | čekání = 0; | |
| t4 _ | while (čekání == 0 && chtít[1]); | |
| t5 _ | Oblast kritického kódu |
int jiné = 0; |
| t6 _ | chtít[1] = pravda; | |
| t7 _ | čekání = 1; | |
| t8 _ | while (čekání == 1 && chtít[0]); | |
| t9 _ | while (čekání == 1 && chtít[0]); | |
| t 10 | chtít[0] = nepravda; | Oblast kritického kódu |
| t 11 | ||
| t 12 | ||
| t 13 | chtít[1] = nepravda; |
Vlákno 0 volá lock , což naznačuje, že má „zájem“ nastavením příznaku fronty tak, aby ustoupil vláknu 1 . Vzhledem k tomu, že posledně jmenovaný ještě nemá „zájem“ o zásah do kritické oblasti, provádění se okamžitě vrátí ze zámku a vstoupí do něj vlákno 0 . Nyní je zámek volán vláknem 1 , pro které jsou také provedeny výše uvedené akce. Ale protože vlákno 0 má stále "zájem" (want[0] == true), provádění zůstává v zámku - vlákno 1 čeká (v tabulce je to vyjádřeno opakováním příkazu pro smyčku 'while'). Jakmile vlákno 0 zavolá odemknout a resetuje svůj příznak „zájem“, vlákno 1 vstoupí do kritické oblasti a nakonec samo zavolá odemknout .
Zámek volání vláken téměř současně| Čas | Vlákno 0 | Stream 1 |
|---|---|---|
| t1 _ | int jiné = 1; | |
| t2 _ | int jiné = 0; | |
| t3 _ | chtít[1] = pravda; | |
| t4 _ | chtít[0] = pravda; | |
| t5 _ | čekání = 0; | |
| t6 _ | čekání = 1; | |
| t7 _ | while (čekání == 1 && chtít[0]); | |
| t8 _ | while (čekání == 1 && chtít[0]); | |
| t9 _ | while (čekání == 0 && chtít[1]); | |
| t 10 | Oblast kritického kódu |
while (čekání == 1 && chtít[0]); |
| t 11 | while (čekání == 1 && chtít[0]); | |
| t 12 | while (čekání == 1 && chtít[0]); | |
| t 13 | chtít[0] = nepravda; | Oblast kritického kódu |
| t 14 | ||
| t 15 | ||
| t 16 | chtít[1] = nepravda; |
Vlákna volají lock téměř současně , nastaví svůj příznak „interested“ a předají frontu provádění konkurenčnímu vláknu nastavením hodnoty proměnné čekání . Vzhledem k tomu, že vlákno 1 je poslední, kdo to udělá , bude již muset čekat ve smyčce, dokud vlákno 0 bez zábran vstoupí do kritické oblasti kódu. Čekání na vlákno 1 , stejně jako v předchozí tabulce, je vyjádřeno opakováním příkazu while pro čekací smyčku. Poté, co vlákno 0 opustí kritickou oblast a resetuje svůj příznak „zájem“, vlákno 1 pokračuje ve svém provádění a nakonec samo resetuje odpovídající příznak voláním unlock .
Vlákna 0 a 1 nikdy nemohou vstoupit do kritické sekce současně: pokud do sekce vstoupila 0 , nastaví parametr want[0] na hodnotu true . Potom buď chcete[1] == false (pak vlákno 1 není v kritické sekci), nebo čekáte == 1 (pak se vlákno 1 pokusí vstoupit do kritické sekce a roztočí se ve smyčce), nebo se vlákno 1 pokusí vstoupit do kritická sekce po nastavení chtít [1] == true , ale před nastavením čekání a opakování. Pokud jsou tedy oba procesy v kritické sekci, mělo by to být chtít[0] && chtít[1] && čekat == 0 && čekat == 1 , ale nemůže to být obojí současně a dostali jsme se do rozporu .
Aby oba procesy čekaly, jsou potřeba opačné hodnoty proměnné čekající, což je nemožné.
Je možné, že jeden proces se zmocní kritického úseku několikrát za sebou, zatímco jiný, který vyjádřil přání se tam dostat, bude čekat. V Petersonově algoritmu nebude proces čekat déle než jeden vstup do kritické sekce: po provedení odemknutí a opětovném zadání zámku se proces nastaví jako čekající a upadne do smyčky, která neskončí, dokud nebude dokončen jiný proces.