Pesquisa Semestre Deadlock

...

spool discutido há pouco, se associássemos agora a região crítica com a leitura e com a escrita no diretório de spool não seria permitido ao processo 0 imprimir outro arquivo, pois o processo 1 estaria fazendo outra coisa. Na verdade, essa solução requer que os dois processos chaveiem obrigatoriamente a entrada em suas regiões críticas para, por exemplo enviar seus arquivos para o spool, não seria permitido a nenhum deles colocar ao mesmo tempo dois arquivos no spool. Embora esse algoritmo evite todas as disputas ele não é um candidato realmente sério para uma solução, pois viola a condição 3.

Solução de Peterson

Combinando a ideia de alternar a vez (com a variável turn) com a ideia das variáveis de trava e de advertência Dekker, um matemático holandês, desenvolveu uma solução de software para o problema de exclusão mútua que não requeira um chaveamento obrigatório.

Em 1981 G. L Peterson descobriu um modo muito mais simples de fazer a exclusão mútua, tornando obsoleta a solução de Dekker. O algoritmo de Peterson é mostrado na Figura

[pic 5]

Ele consiste em duas rotinas escritas em ANSI C, o que significa que dois protótipos de funções devem ser fornecidos para todas as funções definidas e usadas. Antes de usar as variáveis compartilhadas (ou seja, antes de entrar em sua regiao crítica), cada processo chama enter_region com seu próprio número de processo, 0 ou 1, como parâmetro. Essa chamada fará com que ele fique esperando se necessário, até que seja seguro entrar. Depois que terminou de usar as variáveis compartilhadas, o processo chama leave_region para indicar seu término e permitir que outro processo entre, se assim desejar.

Incialmente, nenhum processo está em sua região critica. Então, o processo 0 chama enter_region. Ele manifesta seu interesse escrevendo em seu elemento do arranjo interested e põe a variável turn em 0. Como o processo 1 não está interessado, enter_region retorna imediatamente. Se o processo 1 chamar enter_region agora, ele ficará suspenso ali até que interesed (0) vá para FALSE, um evento que ocorre somente quando o processo 0 chamar leave_region para sair de sua região crítica.

Considere agora o caso em que os dois processos chamam enter_region quase simultaneamente. Ambos armazenarão seus números de processo na variável turn. O que armazenou por último é o que conta - o primeiro é sobreposto e perdido. Suponha que o processo 1 escreva por último; desse modo, a variável turn contém 1. Quando ambos os processos chegam ao comando while. o processo 0 não executa o laço e entra em sua região crítica. O processo 1 executa o laço e não entra em sua região crítica até que processo 0 saia de sua região crítica.

A instrução TSL

TSL RX, LOCK

(test and set lock- teste e atualize variável de trava), que funciona da seguinte maneira: ela lê o conteúdo da memória, a palavra lock, no registrador RX e então armazena um valor diferente de zero no endereço de memória lock. As operações de leitura e armazenamento da palavra são seguramente indivisíveis- nenhum outro processador pode ter acesso à palavra na memória enquanto a instrução não terminar. A CPU que está executando a instrução TSL impede o acesso ao barramento de memória para proibir que outras CPUs tenham acesso à memória enquanto ela não terminar. É importante notar que impedir o barramento de memória é muito diferente de desabilitar interrupções. Desabilitar interrupções e depois executar a leitura de uma palavra na memória seguida pela escrita não impede que um segundo processador no barramento acesse a palavra entre a leitura e a escrita. Na verdade, desabilitar interrupções no processador 1 não tem nenhum efeito sobre o processador 2.

O único modo de evitar que o processador 2 entre na memória até que o processador 1 tenha terminado é impedir o barramento, o que requer um equipamento de hardware especial (basicamente, uma linha de barramento assegurando que o barramento seja impedido e que não esteja disponível para outros processadores além daquele que o impediu).

Para usar a instrução TSL partiremos de uma variável de trava compartilhada lock, para coordenar o acesso à memória compartilhada. Quando a variável lock for 0, qualquer processo poderá torná-la 1 usando a instrução TSL e então, ler ou escrever na memória compartilhada. Quando terminar, o processo colocará a variável lock de volta em 0, lançando mão de uma instrução ordinária move.

Como essa instrução pode ser usada para impedir que dois processos entrem simultaneamente em suas regiões críticas? A solução é dada na Figura abaixo.

[pic 6]

Na figura é mostrada uma sub-rotina de quatro instruções em uma linguagem assembly fictícia (mas típica). A primeira instrução copia o valor anterior da variável lock no registrador e põe a variável lock em 1.

Então o valor anterior é comparado com 0. Se o valor anterior não for 0, ele já estará impedido assim, o programa apenas voltará ao início e testará a variável novamente. Cedo ou tarde a variável se tomará 0 (quando o processo deixar a região crítica em que está) e a sub-rotina retornará, com a variável lock em 1. A trava é bastante simples. O programa apenas armazena um 0 na variável lock. Nenhuma instrução especial é necessária.

O problema produtor-consumidor

Um exemplo de como essas primitivas podem ser usadas consideremos o problema produtor-consumidor (também conhecido como problema de buffer limitado).

Dois processos compartilham um buffer comum e de tamanho fixo. Um deles o produtor, põe informação dentro do buffer e o outro o consumidor, a retira. (Também é possível generalizar o problema para m produtores e 11 consumidores), mas somente consideraremos o caso de um produtor e de um consumidor, pois essa hipótese simplifica as soluções.)

O problema se origina quando o produtor quer colocar um novo item no buffer, mas ele já está cheio. A solução é pôr o produtor para dormir e só despená-lo quando o consumidor remover um ou mais itens. Da mesma maneira, se o consumidor quiser remover um item do buffer e perceber que está vazio ele dormirá até que o produtor ponha algo no buffer e o desperte. Esse método parece bastante simples mas acarreta os mesmos tipos de condições de corrida que vimos anteriormente, com o diretório de spool para manter o controle do