O algoritmo de exclusão mútua de dois processos de Peterson é responsável pelos processos de morte?

9

Penso que no algoritmo de Peterson para exclusão mútua , se o primeiro processo para entrar na seção crítica morresse ou fosse cancelado, o outro processo entraria em loop para sempre, esperando para entrar na seção crítica.

Na figura, se o processo 1 for parado, o restante dos processos por trás do processo 1 será executado até o local do processo 1, mas depois fará o loop.

insira a descrição da imagem aqui

O que acontece se o processo que atinge a seção crítica primeiro morre antes de sair?

programming-languages concurrency mutual-exclusion ganadara
fonte
Eu editei sua pergunta de acordo. Como você não comentou como estender o algoritmo para mais de dois processos, mudei essa parte da pergunta; Eu acho que o problema já está presente na versão de dois processos. Eu ainda não entendo a imagem, no entanto.
Raphael

Respostas:

1

Isso depende de como os bloqueios são implementados. Se você fizer isso como no artigo da Wikipedia, ou seja, guardar a seção crítica com um booleano por processo¹, certamente estará com problemas. Se um processo morre, ele nunca redefine sua sinalização e o outro processo volta para sempre.

Na prática, você pode proteger seu código contra várias maneiras de morrer. Por exemplo, considere esta implementação no estilo Java:

flag[1] = true;
turn = 1;
while ( flag[0] == true && turn == 1 ) { Thread.yield(); }
try {
  // critical section
}
finally {
  flag[1] = false;
}

Isso garantirá que o sinalizador seja redefinido, aconteça o que acontecer na seção crítica, desde que o sistema esteja lidando com o erro. Em Java, isso é verdade mesmo para estouros de pilha e heap. Portanto, a menos que o processo desapareça literalmente ( kill², falha do processador, desconexão da rede, ...) você estará seguro. Observe que a maioria dos softwares não críticos falha nesses casos - como ele pode lidar com um erro que não está sendo executado? - para que seja aceito em muitos casos. Você pode lidar com inconsistências na reinicialização, se necessário.

Se você usar bloqueios adequados no nível do idioma, o sistema de tempo de execução poderá lidar com os proprietários de bloqueios desaparecidos, ou seja, liberar bloqueios com proprietários mortos. Você pode simular isso dando a cada processo um interruptor de homem morto que os outros podem ler ou verificar diretamente se o processo de propriedade da trava ainda está ativo (se o sistema suportar).

  1. Isso não escala bem, de qualquer maneira.
  2. Em Java, acho que finalizedeveria ser executado mesmo kill, mas isso não é garantido pelas especificações. kill -9é provavelmente uma sentença de morte para qualquer solução que exija que o processo de morrer faça alguma coisa.
Rafael
fonte
1

Observe as suposições, especificamente que nenhum processo permanece na seção crítica indefinidamente (isso certamente inclui apenas ir embora). Eu não acho que haja uma maneira de resolver esse problema geral com qualquer mecanismo de sincronização.

Esta solução também é apenas para dois processos, existem soluções para processos ao redor.n

vonbrand
fonte