DeadLocks

O QUE É?

No contexto de Sistemas Operacionais, Deadlock pode ser definido como uma situação onde ocorre um impasse, onde dois ou mais processos ficam impedidos de continuar suas execuções.

EXEMPLO DE CRUZAMENTO DE PONTE

·  Tráfego apenas em uma direção.

·  Cada seção de uma ponte pode ser vista como um recurso.

· Se houver deadlock, ele pode ser resolvido se um carro parar (apropriar recursos e reverter).

·  Vários carros podem ter que parar se houver um deadlock.

COMO?

O Processo A fica bloqueado pelo sistema operacional esperando por dados do processo B, ao mesmo tempo o processo B também fica bloqueado, esperando por dados do processo.

CARACTERIZAÇÃO DO DEADLOCK

Deadlock pode surgir se quatro condições mantidas simultaneamente:

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:  existe um conjunto {P0, P1, …, P0} de processos esperando tal que P0 está esperando por um recurso que é mantido por P1, P1 está esperando por um recurso que é mantido por P2, …, Pn–1 está esperando por um recurso que é mantido por Pn, e P0 está esperando por um recurso que é mantido por 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 P1 → Rj

Aresta de atribuição – aresta direcionada Rj → P

EXEMPLO DE UM GRAFO DE ALOCAÇÃO DE RECURSO

  

GRAFO DE ALOCAÇÃO DE RECURSO COM UM DEADLOCK

GRAFO COM UM CICLO, MAS SEM DEADLOCK

FATOS BÁSICOS

Se o grafo não contém ciclos ⇒ sem deadlock.

Se o grafo contém um ciclo ⇒ se apenas uma instância por tipo de recurso, então deadlock.

 se várias instâncias por tipo de recurso, possibilidade de deadlock.

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; usado pela maioria dos sistemas operacionais, incluindo UNIX.

PREVENÇÃO DE DEADLOCK

· Limite as formas como a requisição pode ser feita.

· 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.

  -Exige que o processo solicite e tenha todos os seus recursos alocados antes de iniciar a execução, ou permite que o processo solicite recursos somente quando o processo não tiver recursos.

   -Baixa utilização de recursos; starvation possível.

·   Sem preempção

  -Se um processo que está mantendo alguns recursos solicitar outro recurso que não pode ser alocado imediatamente a ele, então todos os recursos atualmente sendo mantidos são liberados.

  -Recursos preempatados são acrescentados à lista de   recursos pelos quais o processo está esperando.

  -O processo só será reiniciado quando puder obter seus antigos recursos, além dos novos que está solicitando.

· 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.

EVITANDO DEADLOCK

· Exige que o sistema tenha alguma informação adicional à prioridade.

· Modelo mais simples e mais útil exige que cada processo declare o número máximo de recursos de cada tipo que ele pode precisar.

· O algoritmo para evitar impasse examina dinamicamente o estado de alocação de recurso para garantir que nunca poderá haver uma condição de espera circular.

· O estado de alocação de recurso é definido pelo número de recursos disponíveis e alocados, e as demandas máximas dos processos.

DETECÇÃO DE DEADLOCK

· Permita que o sistema entre no estado de deadlock;

· Algoritmo de detecção;

· Esquema de recuperação.

ÚNICA INSTÂNCIA DE CADA TIPO DE RECURSO

· Manter grafo de espera

· Nós são processos.

· Pi → Pj   se Pi estiver esperando por Pj.

· Periodicamente, chame um algoritmo que procure um ciclo no grafo. Se houver um ciclo, existe um deadlock.

· Um algoritmo para detectar um ciclo em um grafo requer uma ordem de n2 operações, onde n é o número de vértices no grafo.

GRAFO DE ALOCAÇÃO DE RECURSO E GRÁFICO DE ESPERA

VÁRIAS INSTÂNCIAS DE UM TIPO DE RECURSO

· Disponível: Um vetor de tamanho m indica o número de recursos de cada tipo.

· Alocação: Uma matriz n x m define o número de recursos de cada tipo atualmente alocados a cada processo.

· Requisição: Uma matriz n x m indica a requisição atual de cada processo. Se requisição [ij] = k, então o processo Pi está requisitando k mais instâncias do tipo de recurso Rj.

EXEMPLO DE ALGORITMO DE DETECÇÃO

Cinco processos de P0 a P4; três tipos de recurso A (7 instâncias), B (2 instâncias) e    C (6 instâncias). Instantâneo no instante T0:

              Alocação       Requisição      Disponível

                A B C            A B C               A B C

P0            0 1 0               0 0 0                 0 0 0

P1            2 0 0               2 0 2

P2            3 0 3               0 0 0

P3            2 1 1               1 0 0

P4            0 0 2               0 0 2

REFERÊNCIAS

- Pendente

Alunos: Daniéla Barrachi, Isaque Bassi e Angélica Brentan