algoritmo de peterson

Algoritmo de Peterson

Rodrigo Vieira
Samuel Aquino
Sistema de informação 2º semestre
Professor : Rodrigo Mendonça

Maio – 2012
Itabuna - BA

Introdução

Algoritmo de Peterson é um algoritmo de programação simultânea para exclusão mútua, que permite que dois processos ou threads que têm uma seção crítica em que deve haver exclusão mútua, sem conflito, garantindo a sincronização correta, evitando deadlock e garantindo que apenas um processo possa ser executado na secção critica. utilizando a memória compartilhada para a comunicação.
Peterson desenvolveu o primeiro algoritmo em 1981 para dois processos e era uma simplificação do algoritmo de dois processos de Dekker. Mais tarde, este algoritmo foi generalizado para X processos.

Desenvolvimento

O algoritmo utiliza duas variáveis, flag e turn .A flag[n] o valor true indica que o processo quer entrar na seção crítica. A variável turn guarda o ID do processo que tem a vez. A entrada para a seção crítica é concedido para o processo P0 se P1 não quer entrar em sua seção crítica ou se P1 tem dado prioridade ao P0, definindo turn para 0.

//flag[] is boolean array; and turn is an integer flag[0] = false; flag[1] = false; turn; P0: flag[0] = true; turn = 1; while (flag[1] == true && turn == 1) { // busy wait } // critical section ... // end of critical section flag[0] = false;
P1: flag[1] = true; turn = 0; while (flag[0] == true && turn == 0) { // busy wait } // critical section ... // end of critical section flag[1] = false;

O algoritmo tem que satisfazer três critérios para resolver o problema de secção crítica. Os três critérios são a exclusão mútua, progresso e espera limitada.
Na exclusão mútua P0 e P1 nunca podem estar na seção crítica ao mesmo tempo: Se P0 está em seção crítica ,então, ou flag [1] é falsa (P1 significado deixou a sua seção crítica) ou por sua vez, é 0 (P1significando que