Pesquisa Semestre Deadlock

[pic 1][pic 2][pic 3]

---

Exclusão Mútua, alternativas que serão abordadas:

• Desabilitando interrupções;
• Variáveis de impedimento;
• Alternância obrigatória;
• Solução de Peterson;
• A instrução TSL;
• O problema produtor-consumidor;
• Semáforos;
• Monitores;
• DeadLock.

Desabilitando interrupções:

Em um sistema de único processador este sistema é o que mais se encaixa, pois, cada processo desabilita todas as interrupções logo após entrar em sua região crítica e as reabilita imediatamente após a sua saída ou seja com as interrupções desabilitadas não pode ocorrer qualquer interrupção de clock.       A CPU é chaveada de processo em processo somente como um resultado da interrupção do clock ou de outra interrupção, com as interrupções desligadas a CPU não será mais usada para outros processos, desta maneira uma vez que estejam desabilitadas as interrupções, um processo pode verificar a memória compartilhada e também pode atualizar a mesma sem a intervenção de outro processo.

De um modo geral, não é prudente dar aos processos de usuário o poder de desativar as interrupções, suponhamos que o mesmo tenha desabilitado e nunca mais o tenha reabilitado, com certeza traria graves consequências ao sistema operacional, se houver mais de um processador (sistema multiprocessador) desabilitar as interrupções afetará somente a CPU que executou a instrução disable (desabilitar). As outras continuarão executando tendo acesso à memória compartilhada.

Por outro lado, frequentemente convém ao próprio núcleo desabilitar interrupções, para algumas poucas instruções, enquanto estiver alterando variáveis ou listas. Se ocorrer uma interrupção-- por exemplo, enquanto a lista de processos prontos estiver em um estado inconsistente --, poderá haver condições de corrida. A conclusão é: desabilitar interrupções muitas vezes é uma técnica bastante útil dentro do próprio sistema operacional, mas inadequada como um mecanismo geral de exclusão mútua para processos de usuário.

Variáveis de impedimento (lock)

Como uma segunda tentativa, utilizaremos uma solução de software. Considere que haja uma única variável compartilhada (trava), inicialmente contendo o valor 0. Para entrar em sua região crítica. Um processo testa antes se há trava, verificando o valor da variável trava. Se trava for 0, o processo altera essa variável para 1 e entra na região crítica se trava já estiver com o valor 1, o processo simplesmente aguardará até que ela se torne 0. Assim, um 0 significa que nenhum processo está em sua região crítica e um 1 indica que algum processo está em sua região crítica. Infelizmente, essa ideia apresenta exatamente a mesma falha que vimos no diretório de spool, suponha que um processo leia a variável trava e veja que ela é 0. Antes que possa alterar a variável trava para 1, outro processo é escalonado, executa e altera a variável trava para l. Ao executar novamente, o primeiro processo também colocará 1 na variável trava e, assim, os dois processos estarão em suas regiões críticas ao mesmo tempo. Agora você pode pensar que seria possível contornar esse problema lendo primeiro a variável trava e, então, verificá-la novamente, um pouco antes de armazená-la. Mas deque isso adiantaria? A disputa então ocorreria se o segundo processo modificasse a variável trava um pouco depois de o primeiro processo ter terminado sua segunda verificação.

Alternância obrigatória

[pic 4]

Na Figura acima, a variável inteira turn, inicialmente 0, serve para controlar a vez de quem entra na região crítica e verifica ou atualiza a memória compartilhada. Inicialmente, o processo 0 inspeciona a variável turn encontra lá o valor 0 e entra em sua região crítica. O processo 1 também encontra lá o valor 0 e, então fica em um laço fechado testando continuamente para ver quando a variável turn se torna 1. Testar continuamente uma variável até que algum valor apareça, é chamado de espera ociosa (busy waiting).

A espera ociosa deveria em geral ser evitada, já que gasta tempo de CPU. Somente quando há uma expectativa razoável de que a espera seja breve e que ela seja usada.

Uma variável de trava que usa a espera ociosa é chamada de trava giratória (spin lock).

Quando deixa a região crítica, o processo 0 põe a variável turn em 1 para permitir que o processo 1 entre em sua região crítica. Suponha que o processo 1 tenha terminado rapidamente sua região crítica e, assim, ambos os processos não estejam em suas regiões críticas com a variável turn em 0. Agora o processo 0 executa todo o seu laço rapidamente saindo de sua região crítica e colocando a variável turn em 1. Nesse ponto a variável turn 1 e os dois processos estão executando em suas regiões não-críticas. De repente, o processo 0 termina sua região não crítica e volta ao início de seu laço. Infelizmente, a ele não será permitido entrar em sua região crítica agora, pois a variável turn está em 1 e o processo 1 está ocupado com sua região não crítica. O processo O fica suspenso em seu laço while até que o processo 1 coloque a variável turn em 0. Em outras palavras, chavear a vez não é uma boa ideia quando um dos processos for muito mais lento que o outro. Essa situação viola a condição 3 estabelecida anteriormente: o processo O está sendo bloqueado por um processo que não está em sua região crítica. Voltando ao diretório de

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.