DeadLock Sistemas Operacionais I Módulo 7. 24/04/2001Sistemas Operacionais I - Versão Beta 39-2 DEADLOCK Ocorre quando um grupo de processos competem

DeadLockSistemas Operacionais I

Módulo 7

24/04/2001Sistemas Operacionais I - Versão Beta 3 9-2

DEADLOCK

Ocorre quando um grupo de processos competem por acesso a recursos fixos

Definição– Deadlock ocorre entre um conjunto de

processos se todos os processos estão aguardando por um evento que só pode ser gerado por um processo do conjunto


DEADLOCK

Exemplo– Dois processos compartilham dois

recursos que precisam ser requisitados, antes do uso, e liberados, após o uso. A ação de requisição causa bloqueio do processo até o recursos estar disponível

Proc1: Proc2:request taperequest printerrequest printer request tape… <uso> … <uso>release printer release taperelease tape release printer


CONDIÇÃO PARA DEADLOCK

Quatro condições necessárias– Exclusão mutua

Ao menos um processo retém recurso em modo não compartilhado

– Hold-and-waitUm processo pode reter um recurso

enquanto aguarda outro


CONDIÇÃO PARA DEADLOCK

Quatro condições necessárias– Não preempção

Recurso não pode ser preemptado

– Espera circularExiste um conjunto de processos [p1, p2, …,

pn] tal que p1 espera p2, p2 por p3, ….


GRAFO DE ALOCAÇÃO DE RECURSOS

Deadlock pode ser descrito por meio de um Grafo de Alocação de Recursos– Conjunto de vértices

Processos={P1,P2,…,Pn}

Recursos={R1,R2,…,Rm}



Deadlock pode ser descrito por meio de um Grafo de Alocação de Recursos– Uma conexão direta de um Processo para

um Recurso, Pi Rj, indica que Pi requisitou Rj.

– Uma conexão direta de um Recurso para um Processo , RjPi, implica que es that Rj foi alocada por Pi.

– Se não houver ciclos deadlock não existe



.

.

.

.

.

.

.

.

.

.

.

. .R1 R3

R3

R4

R2

P3P2P1

R1

P1 P2 P3

P4R2 R4

Há deadlock.Mesmo ciclos mas sem deadlock.

R3R1


ENFOQUES

Prevenir– Assegure que ao menos uma das quatro

condições não será satisfeitaExclusão mutua

– Torne os recursos compartilháveis (não é sério)Hold-and-wait

– Garanta que um processo não pode reter um recurso quando requisitar outro, ou...

– Requisição coletiva: faça com que os recursos sejam alocados de um só vez e liberados antes de requisitar um novo conjunto


ENFOQUES

Prevenir– Assegure que ao menos uma das quatro

condições não será satisfeitaEspera circular

– Imponha uma ordenação nos recurso

– Só é possível alocar Rj se j>i


ENFOQUES

Evitar– Idéia

Prover informação sobre os recursos que serão necessários para o processo

Garantir que o deadlock não ocorrerá


ENFOQUES

Evitar– Passo 1

Quando requisitado um recurso Rj, mesmo que esteja disponível, não é alocado ao processo solicitante, embora seja garantido o uso

– Processo vai para bloqueio


ENFOQUES

Evitar– Passo 2

Avaliar quando é possível efetuar a alocação seguramente

– Passo 3Se seguro, alocar


ENFOQUES

Evitar– Exemplo

Processos p0, p1 e p2 competem por 12 dispositivos de fita

max corrente solicitado

p0 10 5 5p1 4 2 2p2 9 2 7Existe uma seqüência segura <p1,p0,p2>

– p1 pode completar com os recursos livres– p0 pode completar com os recursos livres+p1– p2 pode completar com os recursos livres+p1+p0


ENFOQUES

Evitar– Exemplo

Se p2 requisitar uma unidade, deve esperar porque o estado se tornará inseguro


ENFOQUES

Algoritmo do banqueiro– Decide quando ceder um recurso

solicitado


ENFOQUES

Deteção– Se não prevenir e não evitar, deadlock vai

atacar– Nesse caso, devemos ter:

Um algoritmo para determinar quando o deadlock ocorre

Um algoritmo para corrigir o deadlock É “lindo”! Mas custa caro


ENFOQUES

Deteção– Algoritmo de deteção de deadlock


ENFOQUES

Deteção– Deteção é cara – Quando detectar?

Depende de:– Qual a possibilidade de deadlock – Quantos processos são afetados quando o

deadlock ocorre


ENFOQUES

Recuperação– Opções

Abortar todos os processos envolvidos no deadlock

– Resulta no custo computacional repetido (submissão dos processos novamente)

Abortar um dos processos por vez até que o ciclo (deadlock) seja eliminado

– Resulta na aplicação do algoritmo de deteção após cada aborto


ENFOQUES

Recuperação– Opções

Preemptar– Liberar recursos até que o deadlock termine– Pontos negativos:

Seleção da vítima Rollback starvation

Ficar quietinho e deixar o sistema parar– Muito utilizado

Documents

DeadLock Sistemas Operacionais I Módulo 7. 24/04/2001Sistemas Operacionais I - Versão Beta 39-2 DEADLOCK Ocorre quando um grupo de processos competem