Prevenção de Deadlock

Para que um deadlock ocorra é necessário que as quatro condições que caracterizam um deadlock sejam estabelecidas. Assegurando que pelo menos uma dessas condições não se estabeleça, podemos nos prevenir contra a ocorrência de deadlocks. A seguir vamos analisar as quatro condições detalhadamente.

1. Exclusão Mútua. Deve estar presente em recursos não compartilháveis, a exemplo disso uma impressora não pode ser compartilhada simultaneamente por vários processos. Mas os recursos compartilhados necessariamente não precisam ser acessados ao mesmo tempo para ser considerado um recurso compartilhado. Porém a prevenção contra deadlock não pode ser feita através da negação da exclusão mútua, pois alguns recursos não podem ser compartilhados.
2. Posse e espera. Para que essa condição não seja satisfeita, devemos garantir que sempre que um processo solicitar um recurso, ele não esteja em posse de nenhum outro recurso.Um protocolo que pode ser usado requer que os processos solicitem e recebam todos os seus recursos antes de começar a ser executado pelo sistema. Outro protocolo permite que um processo solicite recursos apenas quando ele não tem qualquer recurso. Um processo pode solicitar alguns recursos e usá-los. Nessa condição quando ele estiver em posse dos recursos é necessário que ele libere-os para solicitar os novos. Esses dois recursos apresentam duas grandes desvantagens, a utilização dos recursos pode ser baixa, já que podem ficar muito tempo sem serem utilizados e é possível que haja inanição, já que um processo pode solicitar um recurso que seja muito popular assim ele sempre estará alocado fazendo com que o processo que o solicitou fique esperando indefinidamente.
3. Inexistência de Preempção. Para garantir que essa condição não ocorra pode ser usado o protocolo que se um processo estiver em posse de alguns recursos e solicitar outros recursos que não possam ser alocados, então os recursos que o processo estiver ocupando devem ser liberados, ou seja o processo deve sofrer uma preempção. O processo será reiniciado quando os recursos que ele tinha estiverem liberados e os adicionais que ele havia solicitado também. Enquanto ele está esperando se algum outro processo solicitar os recursos que o mesmo está ocupando seus recursos podem ser interrompidos mas isso ocorre somente se outro processo solicitar os recursos. Esse protocolo pode ser aplicado facilmente quando os recursos cujo estado pode ser facilmente salvo e restaurado posteriormente como os registradores da CPU e espaço de memória.
4. Espera Circular. Uma maneira de garantir que essa condição nunca ocorra é impor uma ordenação absoluta a todos os tipos de recursos e requer que cada processo solicite recursos em uma ordem de enumeração crescente. E também se várias instancias do mesmo tipo de recurso forem necessárias, uma única solicitação deve ser emitida para todas elas.

Impedimento de Deadlocks

Os algoritmos de prevenção de deadlock previnem  a ocorrência de deadlocks restringindo como as solicitações são feitas. Essas restrições garantem que  pelos menos uma das condições necessárias para se estabelecer o deadlock não se cumpra. Os possíveis efeitos colaterais podem ser a baixa utilização de dispositivos e uma reduzida taxa de transferência no sistema.

Outro método para evitar deadlocks é demandar mais informações sobre os recursos que serão solicitados. Com esse conhecimento da sequência completa de solicitações pode se tomar a decisão se o processo deve ou não esperar. Para que o sistema faça isso ele precisa de um mapeamento completo para saber quais recursos estão sendo ocupados, se estiverem ocupados informar qual processo os ocupa e também quais recursos estão livres.

Existem vários algoritmos que tratam esse método, o modelo mais simples e útil requer que cada processo declare a quantidade máxima de recursos que ele pode ocupar de cada tipo. Com essa informação já é possível que através de um algoritmo possa se garantir que a condição de espera circular não se estabeleça impedindo assim que se estabeleça um deadlock. O estado da alocação de recursos é definido através da quantidade de recursos disponíveis e alocados pelas demandas máximas dos processos.

Estado de Segurança

Um estado é seguro quando o sistema pode alocar recursos, em alguma ordem e evitar deadlock. O sistema se encontra em segurança somente se existir uma sequência de segurança. Um estado inseguro é um estado de deadlock, mas nem todos os estados inseguros são deadlocks. Enquanto o estado for seguro o sistema pode evitar estados inseguros. Através do comportamento dos processos é controlado os estados inseguros. Um sistema pode passar de um estado seguro para um estado inseguro.

Através de algoritmos de impedimento de deadlocks é necessário garantir que o sistema sempre esteja em estado seguro. Sempre que um recurso for solicitado o sistema deve analisar e verificar se o processo deve esperar ou ocupar o recurso. A solicitação do processo só é atendida se a alocação deixa o sistema em estado seguro.Mas dessa forma a utilização de recursos pode ser baixa por causa das restrições, um processo pode ficar esperando muito tempo para receber um determinado recurso, isso não ocorreria em uma situação oposta.

Algoritmo do Grafo de Alocação de Recursos

O sistema deve ter alocação de recursos com apenas uma instância de cada tipo de recurso, através do mesmo todos os recursos devem ser solicitados a priori do sistema. Uma aresta de requisição indica que o processo Pi pode solicitar o recurso Rj em algum momento no futuro, quando o processo solicita o recurso essa aresta de requisição é convertida em uma aresta de solicitação. Antes de atender qualquer requisição verifica-se se ao inverter a aresta cria-se um ciclo, esse ciclo é considerado um estado inseguro assim o processo é interrompido temporariamente. Se não existir ciclo o estado é seguro então a solicitação pode ser atendida. 

Algoritmo do Banqueiro

Esse nome foi escolhido pois poderia ser usado em um sistema bancário para garantir que o banco nunca alocasse seu dinheiro disponível de tal modo que não pudesse mais satisfazer as necessidades de todos os seu clientes. 

Quando um novo processo entra no sistema ele deve declarar a quantidade máxima de instâncias de cada tipo de recurso de que ele pode precisar. Essa quantidade não pode exceder a capacidade máxima do sistema.   Quando um processo solicitar recursos o sistema fará a análise se ele estiver em estado seguro ele aloca os recursos para determinado processo caso contrário o processo deve esperar.

Várias estruturas de dados devem ser mantidas para implementar o algoritmo do banqueiro, um vetor de um determinado tamanho indica a quantidade de recursos disponíveis de cada tipo, uma matriz define a demanda máxima de cada processo, a alocação de cada tipo correntemente alocada a cada processo, e também a necessidade de recursos remanescentes a cada processo.

Detecção de Deadlocks

Se um sistema não empregar um algoritmo de prevenção ou de impedimento uma situação de deadlock pode ocorrer. Nesse ambiente o sistema pode fornecer: um algoritmo que examine o estado do sistema determinar se ocorreu deadlock, e um algoritmo de recuperação de deadlock.

Uma Única Instância de cada Tipo de Recurso

Se todos os recursos possuem apenas uma unica instância, podemos definir um algoritmo de detecção de deadlocks que usa uma variante do grafo de alocação de recursos, chamado grafo de espera. Para detectar deadlocks, o sistema precisa manter o grafo de espera e periodicidade, invocar um algoritmo que busque um ciclo no grafo, pois só existe deadlocks se o grafo de espera contiver um ciclo.

Várias Instâncias de um Tipo de Recurso

É semelhante ao algoritmo do banqueiro, ele investiga cada sequência de alocação possível para os processos que permanecem inconclusos.

Recuperação de Deadlocks

Quando um algoritmo de detecção de determina que ocorreu um deadlock, existem várias alternativas. Uma delas é informar ao operador que ocorreu um deadlock e deixá-lo lidar com o problema manualmente. Outra é permitir que o sistema se recupere do deadlock automaticamente . Exitem duas possibilidades para interrupção de um deadlock. Uma é simplesmente abortar um ou mais processos para romper a espera circular. Outra é provocar a preempção de alguns recursos de um ou mais processos envolvidos no deadlock.

Encerramento de Processos

Para eliminar deadlocks abortando um processo, podemos usar dois métodos.

1. Abortar todos os processos em deadlock. Ele romperá com o ciclo de deadlock, mas os processos em deadlock podem ter sido executados por muito tempo, e os resultados desses processamentos parciais devem ser descartados e  refeitos posteriormente.
2. Abortar um processo de cada vez até o ciclo de deadlock ser eliminado. Esse método pode causa uma sobrecarga já que após cada processo ser abortado, um algoritmo de detecção de deadlocks deve ser executado para determinar se algum processo ainda está em deadlock.

Abortar um processo não é tarefa fácil, já que se o processo estava no meio de uma atualização de um arquivo e for encerrado esse arquivo ficará em um estado incorreto.

Se o método de encerramento parcial for usado uma politica para o encerramento dos processos deve ser estabelecida

1. A prioridade do processo.
2. Por quanto tempo esse processo foi executado e quanto tempo falta para ele ser concluído.
3. Quantos recursos o processo usou e de que tipos o processo usou, leva-se em consideração se os recursos são facilmente interceptáveis. 
4. De quantos recursos o processo precisa para concluir sua tarefa.
5. Quantos processos terão de ser encerrados.
6. Se o processo é interativo ou batch

Preempção de Recursos

Para eliminar deadlock através da preempção de recursos, um preempção sucessiva de alguns recursos dos processos e dar esses recursos a outros processos até que o ciclo do deadlock seja rompido. Para isso três aspectos devem ser considerados.

1. Seleção de uma Vítima. Devemos levar em consideração o custo dessa preempção, que inclui a quantidade de recursos que um processo em deadlock está mantendo e quanto tempo o processo levou para ser executado até o momento.
2. Reversão. Ao abortar um processo através da preempção de algum recurso que ele estava utilizando a melhor maneira de executar esse processo é reiniciando-o, embora seja mais fácil continuar de onde o processo foi interrompido isso requer que o sistema mantenha mais informações sobre o estado de todos os processos em execução.
3. Inanição. Em um sistema de seleção de vitima baseado principalmente em fatores de custo, pode ocorrer que sempre o mesmo processo seja selecionado como vitima. Com isso o processo nunca concluirá sua tarefa. Desta forma o sistema deve garantir que um único processo seja selecionado apenas uma determinada quantidade de vezes como vitima, para não entrar em inanição. A solução mais eficaz é colocar o numero de reversões no fator de custo.

Descrição do Algoritmo

   Esse algoritmo usa o sistema do tipo 'pegue a ficha', como os utilizados nas padarias muito movimentadas por isso foi apelidado de Algoritmo da Padaria de Lamport. Esse algoritmo toma como modelo um cenário do mundo real, ou seja, esperar para ser atendido em uma padaria. Ele é modelado segundo um modelo de padaria no qual um funcionário atende aos pedidos no balcão, onde esse funcionário só pode atender um cliente por vez.

    Em uma sequência ascendente de fichas pegas pelos clientes na entrada da padaria o funcionário faz o atendimento pelo cliente que estiver com a ficha de menor 'valor', o cliente faz o seu pedido, o funcionário pega as mercadorias, o cliente paga pelo que comprou e sai da padaria. Mas diferente de um distribuidor de fichas do mundo real, o algoritmo  de Lamport permite que vários threads obtenham o mesmo número de ficha. O algoritmo de Lamport inclui um mecanismo de resolução de impasse que garante que somente um thread por vez possa executar em sua seção crítica, no caso da padaria é quando o cliente está na sua vez de ser atendido.  O código foi desenvolvido na linguagem C++ e pode ser baixado AQUI!