Algoritmo de Peterson

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O algoritmo de Peterson é um algoritmo de programação concorrente para exclusão mútua, que permite a dois ou mais processos ou subprocessos compartilharem um recurso sem conflitos, utilizando apenas memória compartilhada para a comunicação. Ele foi formulado por Gary L. Peterson em 1981.[1] Embora a formulação original de Peterson funcionasse apenas com dois processos, o algoritmo pode ser estendido para mais processos.[2]


O algoritmo[editar | editar código-fonte]

//flag[2] é booleana; e turn é um inteiro
flag[0]   = 0;
flag[1]   = 0;
turn;
P0: flag[0] = 1;
    turn = 1;
    while (flag[1] == 1 && turn == 1)
    {
        // ocupado, espere
    }
    // parte crítica
    ...
    // fim da parte crítica
    flag[0] = 0;
P1: flag[1] = 1;
    turn = 0;
    while (flag[0] == 1 && turn == 0)
    {
        // ocupado, espere
    }
    // parte crítica
    ...
    // fim da parte crítica
    flag[1] = 0;

Notas[editar | editar código-fonte]

  1. G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116
  2. Conforme discutido em Operating Systems Review, Janeiro de 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).