Petersons algoritme er en parallel programmeringsalgoritme til gensidig udelukkelse af kodeudførelsestråde, udviklet af Harry Peterson i 1981. Selvom den oprindeligt var formuleret til 2-tråds-casen, kan algoritmen generaliseres til et vilkårligt antal tråde . Algoritmen kaldes betinget en softwarealgoritme, da den ikke er baseret på brugen af specielle processorinstruktioner til at deaktivere interrupts , blokere hukommelsesbussen osv., kun delte hukommelsesvariabler og en loop bruges til at vente på indgangen til den kritiske sektion af den eksekverbare kode.
Før du starter udførelse af en kritisk sektion af kode, skal en tråd kalde en speciel procedure (lad os kalde det lock() ) med nummeret som parameter. Den skal sørge for, at tråden venter på sin tur til at komme ind i den kritiske sektion. Efter at have udført den kritiske sektion og forladt den, kalder tråden en anden procedure (lad os kalde det unlock() ), hvorefter andre tråde vil kunne komme ind i det kritiske område. Lad os se, hvordan dette generelle princip implementeres af Peterson-algoritmen for to tråde.
Kode i C++
klasse PetersonMutex { offentligt : PetersonMutex () { ønsker [ 0 ]. lagre ( falsk ); ønsker [ 1 ]. lagre ( falsk ); venter . butik ( 0 ); } ugyldig lås ( int threadId ) { int andet = 1 - threadId ; ønsker [ threadId ]. butik ( sandt ); // interesseindikator for den aktuelle tråd , der venter . store ( threadId ); // sig, at denne tråd vil vente, hvis det er nødvendigt /* Vent loop. Vi er i denne løkke, hvis den anden proces udfører sit kritiske afsnit. Når den anden proces forlader den kritiske sektion, udføres unlock(int threadId), det interesserede flag (want[other]) bliver falsk, og løkken slutter. */ while ( ønsker [ andre ]. indlæs () && venter . indlæs () == trådId ) { // vent } } void unlock ( int threadId ) { ønsker [ threadId ]. lagre ( falsk ); } privat : std :: array < std :: atomic < bool > , 2 > ønsker ; // trådinteresseflag std :: atomic < int > venter ; // venter tråd nummer };For klarhedens skyld, lad os overveje to scenarier for udførelse af parallelle tråde med tallene 0 og 1 .
Tråde opkald låser sekventielt| Tid | Tråd 0 | Stream 1 |
|---|---|---|
| t1 _ | int andet = 1; | |
| t2 _ | ønsker[0] = sand; | |
| t3 _ | venter = 0; | |
| t4 _ | mens (venter == 0 && ønsker[1]); | |
| t5 _ | Kritisk kodeområde |
int andet = 0; |
| t6 _ | ønsker[1] = sand; | |
| t7 _ | venter = 1; | |
| t8 _ | mens (venter == 1 && ønsker[0]); | |
| t9 _ | mens (venter == 1 && ønsker[0]); | |
| t 10 | ønsker[0] = falsk; | Kritisk kodeområde |
| t 11 | ||
| t 12 | ||
| t 13 | ønsker[1] = falsk; |
Tråd 0 opkald låser , hvilket indikerer, at det er "interesseret" ved at indstille køflaget til at vige for tråd 1 . Da sidstnævnte endnu ikke er "interesseret" i at ramme det kritiske område, vender eksekveringen straks tilbage fra lås , og tråd 0 kommer ind i den. Nu kaldes låsen af tråd 1 , for hvilken ovenstående handlinger også udføres. Men da tråd 0 stadig er "interesseret" (want[0] == sand), forbliver udførelsen låst - tråd 1 venter (i tabellen udtrykkes dette ved at gentage sætningen for 'while'-løkken). Så snart tråd 0 kalder unlock og nulstiller sit "interesserede" flag, går tråd 1 ind i det kritiske område og kalder til sidst unlock sig selv .
Tråde opkaldslås næsten samtidigt| Tid | Tråd 0 | Stream 1 |
|---|---|---|
| t1 _ | int andet = 1; | |
| t2 _ | int andet = 0; | |
| t3 _ | ønsker[1] = sand; | |
| t4 _ | ønsker[0] = sand; | |
| t5 _ | venter = 0; | |
| t6 _ | venter = 1; | |
| t7 _ | mens (venter == 1 && ønsker[0]); | |
| t8 _ | mens (venter == 1 && ønsker[0]); | |
| t9 _ | mens (venter == 0 && ønsker[1]); | |
| t 10 | Kritisk kodeområde |
mens (venter == 1 && ønsker[0]); |
| t 11 | mens (venter == 1 && ønsker[0]); | |
| t 12 | mens (venter == 1 && ønsker[0]); | |
| t 13 | ønsker[0] = falsk; | Kritisk kodeområde |
| t 14 | ||
| t 15 | ||
| t 16 | ønsker[1] = falsk; |
Trådene kalder lås næsten samtidigt , sætter deres "interesserede" flag og giver udførelseskøen til en konkurrerende tråd ved at indstille værdien af den ventende variabel . Da tråd 1 er den sidste, der gør dette , skal den allerede vente i en løkke, mens tråd 0 uhindret kommer ind i det kritiske område af kode. Ventetiden på tråd 1 , som i den foregående tabel, udtrykkes ved at gentage while -sætningen for wait-løkken. Efter at tråd 0 forlader det kritiske område og nulstiller sit "interesserede" flag, fortsætter tråd 1 sin udførelse og nulstiller til sidst selve det tilsvarende flag ved at kalde unlock .
Tråd 0 og 1 kan aldrig gå ind i den kritiske sektion på samme tid: hvis 0 kom ind i sektionen, satte den ønsker[0] til sand . Så enten ønsker[1] == falsk (så er tråd 1 ikke i den kritiske sektion), eller venter == 1 (så prøver tråd 1 at komme ind i den kritiske sektion og spinder i en løkke), eller tråd 1 forsøger at komme ind i den kritiske sektion kritisk sektion efter indstilling ønsker [1] == sand , men før indstilling venter og looping. Så hvis begge processer er i den kritiske sektion, burde det være want[0] && want[1] && waiting == 0 && waiting == 1 , men dette kan ikke være begge dele på samme tid, og vi er kommet til en modsigelse .
For at begge processer skal vente, kræves modsatte værdier af ventevariablen, hvilket er umuligt.
Det er muligt, at én proces griber et kritisk afsnit flere gange i træk, mens en anden, der har udtrykt ønske om at nå dertil, venter. I Petersons algoritme vil processen ikke vente længere end én indgang i den kritiske sektion: efter at have udført oplåsning og genindtastning af lås , vil processen indstille sig selv som ventende og falde ind i en løkke, der ikke slutter, før en anden proces er afsluttet.