Petersons algoritm är en parallell programmeringsalgoritm för ömsesidig uteslutning av kodexekveringstrådar, utvecklad av Harry Peterson 1981. Även om den ursprungligen formulerades för 2-trådsfallet, kan algoritmen generaliseras till ett godtyckligt antal trådar . Algoritmen kallas villkorligt en mjukvarualgoritm, eftersom den inte är baserad på användningen av speciella processorinstruktioner för att inaktivera avbrott , blockera minnesbussen, etc., endast delade minnesvariabler och en loop används för att vänta på inträdet i den kritiska avsnitt av den körbara koden.
Innan man startar exekvering av en kritisk sektion av koden, måste en tråd anropa en speciell procedur (låt oss kalla det lock() ) med dess nummer som parameter. Den måste ordna så att tråden väntar på sin tur att komma in i det kritiska avsnittet. Efter att ha kört den kritiska sektionen och lämnat den, anropar tråden en annan procedur (låt oss kalla den unlock() ), varefter andra trådar kommer att kunna gå in i den kritiska regionen. Låt oss se hur denna allmänna princip implementeras av Peterson-algoritmen för två trådar.
Kod i C++
klass PetersonMutex { offentliga : PetersonMutex () { vill ha [ 0 ]. lagra ( falskt ); vill ha [ 1 ]. lagra ( falskt ); väntar . lagra ( 0 ); } void lock ( int threadId ) { int annan = 1 - tråd-ID ; vill ha [ threadId ]. lagra ( sant ); // intresseindikator för den aktuella tråden som väntar . store ( threadId ); // säg att denna tråd kommer att vänta om det behövs /* Wait loop. Vi är i denna loop om den andra processen exekverar sin kritiska sektion. När den andra processen lämnar den kritiska sektionen exekveras unlock(int threadId), den intresserade flaggan (want[other]) blir falsk och slingan slutar. */ while ( vill ha [ annan ]. ladda () && väntar . ladda () == threadId ) { // vänta } } void unlock ( int threadId ) { vill ha [ threadId ]. lagra ( falskt ); } privat : std :: array < std :: atomic < bool > , 2 > want ; // tråd intresse flaggor std :: atomic < int > väntar ; // väntande trådnummer };För tydlighetens skull, låt oss överväga två scenarier för exekvering av parallella trådar med nummer 0 och 1 .
Trådar samtal låser sekventiellt| Tid | Tråd 0 | Streama 1 |
|---|---|---|
| t1 _ | int annan = 1; | |
| t2 _ | vill[0] = sant; | |
| t3 _ | väntar = 0; | |
| t4 _ | while (väntar == 0 && vill[1]); | |
| t5 _ | Kritiskt kodområde |
int annan = 0; |
| t6 _ | vill[1] = sant; | |
| t7 _ | väntar = 1; | |
| t8 _ | while (väntar == 1 && vill[0]); | |
| t9 _ | while (väntar == 1 && vill[0]); | |
| t 10 | vill[0] = falskt; | Kritiskt kodområde |
| t 11 | ||
| t 12 | ||
| t 13 | vill[1] = falskt; |
Tråd 0 samtal låser , vilket indikerar att den är "intresserad" genom att ställa in köflaggan för att ge vika för tråd 1 . Eftersom den sistnämnda ännu inte är "intresserad" av att träffa den kritiska regionen, återgår exekveringen omedelbart från låset och tråd 0 går in i den. Nu anropas lås av tråd 1 , för vilken ovanstående åtgärder också utförs. Men eftersom tråd 0 fortfarande är "intresserad" (vill[0] == sant), förblir exekveringen låst - tråd 1 väntar (i tabellen uttrycks detta genom att upprepa satsen för 'while'-loopen). Så snart tråd 0 anropar upplåsning och återställer sin "intresserade" flagga, går tråd 1 in i det kritiska området och anropar slutligen upplåsning .
Trådar samtalslås nästan samtidigt| Tid | Tråd 0 | Streama 1 |
|---|---|---|
| t1 _ | int annan = 1; | |
| t2 _ | int annan = 0; | |
| t3 _ | vill[1] = sant; | |
| t4 _ | vill[0] = sant; | |
| t5 _ | väntar = 0; | |
| t6 _ | väntar = 1; | |
| t7 _ | while (väntar == 1 && vill[0]); | |
| t8 _ | while (väntar == 1 && vill[0]); | |
| t9 _ | while (väntar == 0 && vill[1]); | |
| t 10 | Kritiskt kodområde |
while (väntar == 1 && vill[0]); |
| t 11 | while (väntar == 1 && vill[0]); | |
| t 12 | while (väntar == 1 && vill[0]); | |
| t 13 | vill[0] = falskt; | Kritiskt kodområde |
| t 14 | ||
| t 15 | ||
| t 16 | vill[1] = falskt; |
Trådarna anropar lås nästan samtidigt , sätter sin "intresserade" flagga och ger exekveringskön till en konkurrerande tråd genom att ställa in värdet på den väntande variabeln . Eftersom tråd 1 är den sista som gör detta måste den redan vänta i en loop medan tråd 0 obehindrat kommer in i den kritiska delen av koden. Väntan på tråd 1 , som i föregående tabell, uttrycks genom att upprepa while -satsen för wait-loopen. Efter att tråd 0 lämnar det kritiska området och återställer sin "intresse"-flagga, fortsätter tråd 1 dess exekvering och återställer slutligen själva motsvarande flagga genom att anropa unlock .
Trådarna 0 och 1 kan aldrig komma in i det kritiska avsnittet samtidigt: om 0 gick in i avsnittet satte den vill[0] till sant . Sedan antingen vill[1] == false (då är tråd 1 inte i den kritiska sektionen), eller väntar == 1 (då försöker tråd 1 komma in i den kritiska sektionen och snurrar i en slinga), eller så försöker tråd 1 komma in i den kritiska sektionen kritisk sektion efter inställning vill [1] == sant , men före inställning av väntan och looping. Om båda processerna är i det kritiska avsnittet borde det alltså vara want[0] && want[1] && waiting == 0 && waiting == 1 , men detta kan inte vara båda samtidigt och vi har kommit till en motsägelse .
För att båda processerna ska vänta krävs motsatta värden på den väntande variabeln, vilket är omöjligt.
Det är möjligt att en process kommer att lägga beslag på en kritisk sektion flera gånger i rad, medan en annan, som har uttryckt en önskan att nå dit, väntar. I Petersons algoritm kommer processen inte att vänta längre än ett inträde i den kritiska sektionen: efter att ha kört upplåsning och återinmatning av lås kommer processen att ställas in på att vänta och hamna i en loop som inte kommer att sluta förrän en annan process har slutförts.