Deadlock

Deadlock

1. Definição

   • Dois ou mais processos ficam bloqueados permanentemente, esperando por recursos que nunca serão liberados

2. Modelo do Sistema

   • Sistema = Conjunto finito de recursos a serem distribuídos entre uma série de processos em competição
   • Tipos de recurso R1 . . . Rm
     • Ciclos de CPU, espaço de memória, dispositivos de E/S
   • Cada recurso pode admitir uma ou mais instancia
     • CPU de 2 núcleos = 2 instâncias
   • Cada tipo de recurso Ri possui instâncias W
     • As instâncias de um mesmo dispositivos possuem exatamente a mesma funcionalidade
   • Cada processo utiliza um recurso da seguinte forma
     • Requisição/Solicitação
     • Uso
     • Liberação

3. Caracterização do Deadlock

   • Condições Necessárias
     • Exclusão mútua
       • Apenas um processo de cada vez pode usar um recurso
     • Manter e esperar
       • Um processo mantendo pelo menos um recurso está esperando para adquirir outros recursos mantidos por outros processos
     • Não preempção
       • Um recurso só pode ser liberado voluntariamente pelo processo que o mantém, depois que esse processo tiver terminado sua tarefa
     • Espera circular
       • Conjunto {P0 , P1 , …, Pn } de processos esperando tal que P0 está esperando por um recurso que é mantido por P1, que espera um recurso em P2 ... Pn espera um recurso em P0
   • Grafo de Alocação de Recursos
     • Um conjunto de vértices V e um conjunto de arestas E
     • V é particionado em dois tipos
       • P = {P1 , P2 , …, Pn }, o conjunto consistindo em todos os processos no sistema
       • R = {R1 , R2 , …, Rm}, o conjunto consistindo em todos os tipos de recurso no sistema
     • Aresta de requisição
       • Aresta direcionada Pi -> Rj
     • Aresta de atribuição
       • Aresta direcionada Rj -> Pi
     • Grafo tem algum ciclo?
       • Não
         • Sem deadlock
       • Sim
         • Se apenas uma instância por tipo de recurso
           • Deadlock
         • Se várias instâncias por tipo de recurso
           • Possibilidade de deadlock

4. Métodos para Tratamento de Deadlocks

   • Garantir que o sistema nunca entrará em um estado de deadlock
   • Permitir que o sistema entre em um estado de deadlock e depois se recupere
   • Ignorar o problema e fingir que os deadlocks nunca ocorrem no sistema
     • Se os deadlocks forem considerados raros (±1 vez/ano) é a opção menos dispendiosa

5. Prevenção de Deadlock

   • Garantir que pelo menos uma das quatro condições necessárias (para haver deadlock) não possa ser atendida
     • Exclusão mútua
       • Não exigido para recursos compartilháveis; deve manter para recursos não compartilháveis
     • Manter e esperar
       • Deve garantir que sempre que um processo solicita um recurso, ele não mantém quaisquer outros recursos
     • Não preempção
       • Se um processo solicitando um recurso não puder recebê-lo imediatamente, ele libera todos os recursos que possui.
       • Esses recursos liberados são adicionados à lista de espera
       • Processo será reiniciado apenas quando puder recuperar os recursos antigos e os novos necessários
     • Espera circular
       • Impõe uma ordenação total de todos os tipos de recurso, e exige que cada processo solicite recursos em uma ordem de enumeração aumentada