Pitersonov algoritam
Pitersonov algoritam (engl. Peterson's algorithm) je algoritam za međusobno isključivanje u konkurentnom programiranju koji omogućava da dva procesa bez sukoba jednokratno dele resurs, koristeći samo deljenu memoriju za komunikaciju. Algoritam je formulisao Gari L. Piterson 1981. godine.[1] U Pitersonovom originalnom radu formulisan je algoritam sa samo dva procesa, međutim algoritam može biti generalizovan i za više procesa.[2]
Algoritam uredi
Algoritam koristi dve promenljive, flag i turn. Kada proces Pn postavi vrednost flag[n] na tačno to ukazuje da proces želi da uđe u kritičnu sekciju. Promenljiva turn ima identifikator procesa čiji je red da uđe u kritičnu sekciju. Ulaz u kritičnu sekciju se dodeljuje procesu P0 ako P1 ne želi da uđe u svoju kritičnu sekciju ili ako P1 je dao prioritet procesu P0 postavljanjem vrednosti turn na 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;
|