Питерсонов алгоритам
Питерсонов алгоритам (енгл. Peterson's algorithm) је алгоритам за међусобно искључивање у конкурентном програмирању који омогућава да два процеса без сукоба једнократно деле ресурс, користећи само дељену меморију за комуникацију. Алгоритам је формулисао Гари Л. Питерсон 1981. године.[1] У Питерсоновом оригиналном раду формулисан је алгоритам са само два процеса, међутим алгоритам може бити генерализован и за више процеса.[2]
Алгоритам
[уреди | уреди извор]Алгоритам користи две променљиве, flag и turn. Када процес Pn постави вредност flag[n] на тачно то указује да процес жели да уђе у критичну секцију. Променљива turn има идентификатор процеса чији је ред да уђе у критичну секцију. Улаз у критичну секцију се додељује процесу P0 ако P1 не жели да уђе у своју критичну секцију или ако P1 је дао приоритет процесу P0 постављањем вредности turn на 0.
//flag[] је низ Булових вредности; а turn је целобројна вредност
flag[0] = false;
flag[1] = false;
turn;
| |
P0: flag[0] = true;
turn = 1;
while (flag[1] == true && turn == 1)
{
// запослено чекање
}
// критична секција
...
// крај критичне секције
flag[0] = false;
|
P1: flag[1] = true;
turn = 0;
while (flag[0] == true && turn == 0)
{
// запослено чекање
}
// критична секција
...
// крај критичне секције
flag[1] = false;
|