Пређи на садржај

Питерсонов алгоритам

С Википедије, слободне енциклопедије

Питерсонов алгоритам (енгл. 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;

Референце

[уреди | уреди извор]
  1. ^ G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116
  2. ^ M. Hofri: "Proof of a Mutual Exclusion Algorithm", Operating Systems Review, јануар 1990.