A Peterson -algoritmus egy párhuzamos programozási algoritmus a kódvégrehajtási szálak kölcsönös kizárására , amelyet Harry Peterson fejlesztett ki 1981-ben. Bár eredetileg 2 szálas esetre fogalmazták meg, az algoritmus tetszőleges számú szálra általánosítható . Az algoritmust feltételesen szoftveralgoritmusnak nevezik, mivel nem a megszakítások letiltására , a memóriabusz blokkolására stb. szóló speciális processzorutasításokon alapul, csak a megosztott memória változóit és egy hurkot használják a kritikusba való belépésre várva. a végrehajtható kód része .
Mielőtt elkezdené a kód egy kritikus szakaszának végrehajtását , egy szálnak meg kell hívnia egy speciális eljárást (nevezzük lock() ) a számával paraméterként. Úgy kell gondoskodnia, hogy a szál megvárja a sorát, hogy belépjen a kritikus szakaszba. A kritikus szakasz végrehajtása és elhagyása után a szál egy másik eljárást hív meg (nevezzük unlock() ), amely után más szálak is beléphetnek a kritikus régióba. Nézzük meg, hogyan valósítja meg ezt az általános elvet a Peterson-algoritmus két szálra.
Kód C++ nyelven
osztály PetersonMutex { nyilvános : PetersonMutex () { akar [ 0 ]. bolt ( hamis ); akar [ 1 ]. bolt ( hamis ); vár . üzlet ( 0 ); } void lock ( int threadId ) { int másik = 1 - threadId ; akar [ threadId ]. bolt ( igaz ); // az aktuális szál érdeklődési mutatója vár . bolt ( szálId ); // mondjuk ez a szál várni fog, ha szükséges /* Várakozási ciklus. Ebben a ciklusban vagyunk, ha a második folyamat végrehajtja a kritikus szakaszát. Amikor a második folyamat kilép a kritikus szakaszból, az unlock(int threadId) végrehajtásra kerül, az érdekelt jelző (want[other]) hamis lesz, és a ciklus véget ér. */ while ( akar [ más ]. load () && vár . load () == threadId ) { // várj } } void unlock ( int threadId ) { akar [ threadId ]. bolt ( hamis ); } privát : std :: array < std :: atomic < bool > , 2 > want ; // szál érdeklődési zászlók std :: atomic < int > várakozás ; // szál száma vár };Az érthetőség kedvéért nézzünk meg két forgatókönyvet a 0 és 1 számú párhuzamos szálak végrehajtására .
Szálak hívászár szekvenciálisan| Idő | 0. szál | 1. adatfolyam |
|---|---|---|
| t1_ _ | int egyéb = 1; | |
| t2_ _ | akar[0] = igaz; | |
| t3_ _ | várakozás = 0; | |
| t4_ _ | while (várakozás == 0 && akar[1]); | |
| t5_ _ | Kritikus kódterület |
int egyéb = 0; |
| t6_ _ | akar[1] = igaz; | |
| t7_ _ | várakozás = 1; | |
| t8_ _ | while (várakozás == 1 && akar[0]); | |
| t9_ _ | while (várakozás == 1 && akar[0]); | |
| t 10 | akar[0] = hamis; | Kritikus kódterület |
| t 11 | ||
| t 12 | ||
| t 13 | akar[1] = hamis; |
0. szál hívások zárolása , jelezve, hogy „érdekelte” azáltal, hogy a sorjelzőt úgy állítja be, hogy átadja helyét az 1. szálnak . Mivel ez utóbbit még nem "érdekelte" a kritikus régió elérése, a végrehajtás azonnal visszatér a lock -ból, és a 0 -ás szál lép be. Most az 1. szál hívja a zárat , amelyhez a fenti műveletek is végrehajtódnak. De mivel a 0. szál továbbra is "érdekel" (want[0] == true), a végrehajtás zárolásban marad - az 1. szál vár (a táblázatban ez a 'while' ciklus utasításának megismétlésével fejeződik ki). Amint a 0. szál meghívja a feloldást , és visszaállítja az „érdeklődés” jelzőjét, az 1. szál belép a kritikus régióba, és végül magát a feloldást hívja .
Szinte egyidejűleg kapcsolja be a hívászárat| Idő | 0. szál | 1. adatfolyam |
|---|---|---|
| t1_ _ | int egyéb = 1; | |
| t2_ _ | int egyéb = 0; | |
| t3_ _ | akar[1] = igaz; | |
| t4_ _ | akar[0] = igaz; | |
| t5_ _ | várakozás = 0; | |
| t6_ _ | várakozás = 1; | |
| t7_ _ | while (várakozás == 1 && akar[0]); | |
| t8_ _ | while (várakozás == 1 && akar[0]); | |
| t9_ _ | while (várakozás == 0 && akar[1]); | |
| t 10 | Kritikus kódterület |
while (várakozás == 1 && akar[0]); |
| t 11 | while (várakozás == 1 && akar[0]); | |
| t 12 | while (várakozás == 1 && akar[0]); | |
| t 13 | akar[0] = hamis; | Kritikus kódterület |
| t 14 | ||
| t 15 | ||
| t 16 | akar[1] = hamis; |
A szálak szinte egyszerre hívják a lockot , beállítva az „érdeklődés” jelzőjét, és a várakozási változó értékének beállításával átadják a végrehajtási sort egy versengő szálnak . Mivel az 1. szál az utolsó, amelyik ezt megteszi , már várnia kell egy ciklusban, amíg a 0. szál akadálytalanul belép a kód kritikus régiójába. A várakozás az 1. szálra , mint az előző táblázatban, a while utasítás megismétlésével fejeződik ki a várakozási ciklusra. Miután a 0. szál kilép a kritikus régióból, és visszaállítja az „érdeklődés” jelzőjét, az 1. szál folytatja a végrehajtást, és végül magát a megfelelő jelzőt állítja vissza az unlock meghívásával .
A 0 és 1 szál soha nem léphet be egyszerre a kritikus szakaszba: ha 0 lépett be a szakaszba, akkor a want[0] értéket true értékre állítja . Ezután vagy want[1] == false (akkor az 1. szál nincs a kritikus szakaszban), vagy vár == 1 (akkor az 1. szál megpróbál belépni a kritikus szakaszba, és körben pörög), vagy az 1. szál megpróbál belépni a kritikus szakasz a want beállítása után [1] == true , de a várakozás és ciklus beállítása előtt. Így ha mindkét folyamat a kritikus szakaszban van, akkor akar[0] && akar[1] && vár == 0 && vár == 1 , de ez nem lehet egyszerre mindkettő, és ellentmondáshoz jutottunk .
Ahhoz, hogy mindkét folyamat várakozzon, a várakozó változó ellentétes értékeire van szükség, ami lehetetlen.
Előfordulhat, hogy az egyik folyamat egymás után többször is megragad egy kritikus szakaszt, míg egy másik, amelyik kifejezte, hogy el akar jutni, vár. Peterson algoritmusában a folyamat nem vár tovább, mint egy belépés a kritikus szakaszba: a feloldás végrehajtása és a zárolás újbóli belépése után a folyamat várakozásnak állítja be magát, és egy olyan hurokba esik, amely addig nem ér véget, amíg egy másik folyamat be nem fejeződik.