bc1518 SO Aula07 Deadlock - hostel.ufabc.edu.brhostel.ufabc.edu.br/.../bc1518_SO_Aula07_Deadlock.pdf · BC1518-Sistemas Operacionais Deadlock (Impasse) Prof. Marcelo Z. do Nascimento

BC1518-Sistemas Operacionais

DeadlockDeadlock (Impasse)(Impasse)

Prof. Marcelo Z. do [email protected]

DeadlockDeadlock (Impasse)(Impasse)Aula 07Aula 07

Roteiro• Conceito de Deadlock;

• Recursos;

• Condições de ocorrência;• Condições de ocorrência;

• Estratégias para tratar Deadlocks;

• Prevenção de deadlocks;

• Leituras Sugeridas

• Exercícios

Deadlocks� Na ausência de uma sincronização pode ocorrer um

deadlock;

� Definição: É o congestionamento de requisições de É o congestionamento de requisições de recursos no âmbito de todo o sistema que começa recursos no âmbito de todo o sistema que começa

3

Definição: É o congestionamento de requisições de É o congestionamento de requisições de recursos no âmbito de todo o sistema que começa recursos no âmbito de todo o sistema que começa quando 2 ou mais programas são colocados em espera quando 2 ou mais programas são colocados em espera até que o recurso vital se torne disponível.até que o recurso vital se torne disponível.

� Normalmente não pode ser resolvido pelo S.O. e requer intervenção externa por parte do operador ou dos usuários, forçando a tomar atitudes drásticas, como provocar manualmente o término do programa.

Deadlocks� Analogia: escada muito estreita em um prédio.

� A escada foi construída como uma rota de fuga na eventualidade de um incêndio,

4

eventualidade de um incêndio,

� As pessoas que trabalham no prédio muitas vezes preferem usá-las ao invés de esperar pelos elevadores.

� O tráfego vai bem até que duas pessoas movendo em direção opostas se cruzam - há espaço para apenas uma pessoa em cada degrau.

DeadlocksAnalogia: Congestionamento de trânsito

5Situação de Situação de deadlockdeadlock

Deadlocks - Recursos� Existem 2 tipos de recursos:

�� Preemptivos:Preemptivos: podem ser retirados do processo sem prejuízos;

Exemplo: Memória – 2 processos solicitam a

6

� Exemplo: Memória – 2 processos solicitam a impressão (sistema time-sharing)

� Processo A obtém a impressora;� CPU retira processo A e processo B tenta obter a impressora;

� Situação de deadlock;� Envia processo B para disco e carrega o processo A na memória – elimina o deadlock;

Deadlocks�� NãoNão--preemptivos:preemptivos: não podem ser retirados do processo => causam prejuízos;

� CD-ROM;

7

� Processo A começou a gravar um CD-ROM,

� Retirar repentinamente do processo A o gravador de CD e passar a um outro processo,

� Resultará em um CD com erros.

� Deadlocks ocorrem com esse tipo de recurso;

Deadlocks�� ComoComo éé aa seqüênciaseqüência dede eventoseventos parapara utilizaçãoutilização dede umum

recursorecurso compartilhado?compartilhado?

� Requisição do recurso;

� Utilização do recurso;

8

� Utilização do recurso;

� Liberação do recurso;

�� SeSe nãonão estiverestiver disponível,disponível, oo queque podepode ocorrer?ocorrer?

� Processo que requisitou o recurso fica bloqueado atéque o recurso seja liberado;

� Processo que requisitou o recurso falha e depois deum certo tempo tenta novamente requisitar orecurso;

Deadlocks - Aquisiçãotypedef int semaphore;semaphore recurso_1;semaphore recurso_2;

void processoA(void){down(&recurso_1);

typedef int semaphore;semaphore recurso_1;semaphore recurso_2;

Possibilidade de Impasse

9

down(&recurso_1);down(&recurso_2);

Usar_ambos_itens( ); up(&recurso_2);

up(&recurso_1);}void processoB(void){down(&recurso_1);down(&recurso_2);Usar_ambos_itens( ); up(&recurso_2);up(&recurso_1);

}

void processoA(void){down(&recurso_1);down(&recurso_2);Usar_ambos_itens( ); up(&recurso_2);up(&recurso_1);

}void processoB(void){down(&recurso_2);down(&recurso_1);Usar_ambos_itens( ); up(&recurso_1);up(&recurso_2);

}

Condições de ocorrênciaCondições de ocorrência

Deadlocks� Condições para ocorrer um deadlock:

� Analogia com a escada:

� Exclusão mútua: um recurso está sendo utilizado por

11

� Exclusão mútua: um recurso está sendo utilizado poralgum processo ou está disponível (escada);

� Uso e espera (hold and wait): processos que jápossuem algum recurso podem requer outrosrecursos para finalizar(duas pessoas se encontramno lance da escada);

Deadlocks� Condições para ocorrer um deadlock:

� Analogia com a escada:

� Não-preempção: recursos já alocados não podem ser retiradosdo processo que os alocou; somente o processo que alocou o

12

do processo que os alocou; somente o processo que alocou orecurso pode liberá-lo (escada);

� Espera Circular: Deve existir um encadeamento circular de doisou mais processos; cada um deles encontra-se à espera de umrecursos que está sendo usado pelo mebro seguinte dessacadeia (monopoliza o recurso – ocupa um degrau e se recusa aretroceder).

Modelagem de deadlocksModelagem de deadlocks

� Holt (1972) as condições podem ser visualizadasatravés de grafos direcionados;

Processo

Modelagem de Deadlocks

14

Recurso

a) Recurso R alocado ao Processo Ab) Processo B requisita Recurso Sc) Deadlock – ciclo C-T-D-U-C

Aresta de alocação

� Cenário 1 – Grafos de Recursos

P1 requisita e obtém R11

AçãoTempo


15

P3 libera R36


P2 libera R24


P1 libera R12

P1

R1 R2 R3

P2 P2

Processo

� Cenário 2: Processos fazem E/S quanto CPU e utiliza algoritmo de alternância circular


16

P3 requisita R16

P2 requisita R35

P1 requisita R24




AçãoTempo

P1

R1 R2 R3

P2 P3

Bloqueado

� Cenário 2: Algoritmo de alternância circular


AçãoTempoR1 R2 R3


17

P3 requisita R16

P2 requisita R35

P1 requisita R24




P1 P2 P3

ImpasseComo o SO poderia resolver esse problema?

A ordem de execução seria uma solução? => P2?

Estratégias para tratar deadlocksEstratégias para tratar deadlocks

Deadlocks � Quatro estratégias para tratar deadlocks:

� Ignorar o problema;

19

� Detectar e recuperar o problema;

� Evitar dinamicamente o problema – alocação cuidadosa de recursos;

� Prevenir o problema por meio da não satisfação de uma das quatro condições citadas anteriormente;

Deadlocks � Ignorar o problema:

� “Enterre sua cabeça na areia e finja que nada está acontecendo” (ALGORITMO DO AVESTRUZ).

Profissionais reagem diferentemente a essa

20

� Profissionais reagem diferentemente a essa estratégia?

� Matemáticos consideram inaceitável e devem ser evitados / Engenheiros não aceitam perder desempenho para eliminar deadlock

� A maioria dos S.O. sofre potencialmente de deadlocks que normalmente não são detectados e muito menos anulados.

Deadlocks � Exemplo:

� Sistema UNIX tem 100 entradas na tabela de processos;

10 programas estão sendo executados;

21

� 10 programas estão sendo executados; � cada um precisa criar 12 (sub)processos;

� Após cada processo ter criado 9 outros processos, os 10 originais e os 90 novos esgotaram a capacidade da tabela.

� Cada processo entra em um laço infinito de execução de fork e falha, ou seja, ocorre uma situação de deadlock.

Deadlocks � Maioria do S.O. (Windows e Unix) ignora o

problema, supondo que a maior parte dos usuáriospreferiria um deadlock ocasional a uma regra querestrinja cada usuário somente a um processo.

22

restrinja cada usuário somente a um processo.

Problema:

� Custo é alto – implica restrições não convencionaisde processos (criar conjunto de regras).

DeadlocksDetectar e Recuperar o problema:

� Permite que os deadlocks ocorram, tenta detectar as causas e solucionar a situação;

Utilizados em computadores de grande porte (Mainframe);

23

� Utilizados em computadores de grande porte (Mainframe);

� Algoritmos:� Detecção com um recurso de cada tipo;� Detecção com vários recursos de cada tipo;� Recuperação por meio de preempção;� Recuperação por meio de rollback (volta ao passado);� Recuperação por meio de eliminação de processos.

Deadlocks� Detecção com um recurso de cada tipo:

� Tem um recurso de cada tipo: ploter, impressora, CD� Se houverem ciclos, existem potenciais deadlocks;

Situação: com 7 processosSituação: com 7 processosPA usa R e precisa de S;

24

PA usa R e precisa de S;PB precisa de T;PC precisa de S;PD usa U e precisa de S e T;PE usa T e precisa de V;PF usa W e precisa de S;PG usa V e precisa de U;

Modelagem: Grafo de recursos

Deadlocks� Detecção com um recurso de cada tipo:

� Resposta através da construção de um grafo;� Se houverem ciclos, existem potenciais deadlocks;

Processos: A-GRecursos: R-W

Situação:Nós

Sistema => 7 processosSistema => 7 processos P

L

O

T

E

r

25CicloCiclo

R

S

W

U

T

V

A

C

F

D

B

E

G

Recursos: R-WSituação:PA usa R e precisa de S;PB precisa de T;PC precisa de S;PD usa U e precisa de S e T;PE usa T e precisa de V;PF usa W e precisa de S;PG usa V e precisa de U;

Pergunta: Há possibilidade de deadlock?

Nós

Arresta

alocado

precisa

� Algoritmo (aplicação): começa utilizando uma lista L� Execução a partir de R->A,B,C,S,D,T,E,F (ciclo para);

1) Início R => L=[R, A ], L=[R, A, S] =>S não tem arco de saída (retorna);

Deadlocks

26

R

S

W

U

T

V

A

C

F

D

B

E

G

Arcos

INÍCIO

precisa

saída (retorna);2) Início A => L=[A,S] S não

tem arco de saída (retorna);

3) Início B => L=[B,T,E,V,G,U,D] = escolher S vamos para um nó sem saída e retornamos em D

4) Caso contrário: L=[B,T,E,V,G,U,D,T] =>ciclo

Deadlocks� Detecção com vários recursos de cada tipo (baseado

em matrizes):� Classes diferentes de recursos – vetor de recursos existentes (E):

� Classe1= unidade de fita e E1=2 => existem duas unidades

27

� Classe1= unidade de fita e E1=2 => existem duas unidades de fita;

� Vetor de recursos disponíveis (A):� Se ambas as unidades de fita estiverem alocadas, A1=0;

� Duas matrizes:� C: matriz de alocação corrente;

� Cij: número de instâncias do recurso j entregues ao processo i;

� R: matriz de requisições;� Rij: número de instâncias do recurso j que o processo i precisa;

Deadlocks

Recursos existentes

4 unidades de fita;2 plotter;3 impressoras; 1 unidade de CD-ROM

Recursos disponíveisA = (2 1 0 0)

UF P I UCD

Matriz de requisiçõesUF P I UCD

28

Recursos existentesE = (4 2 3 1)

Três processos:P1 usa uma impressora;P2 usa duas unidades de fita e uma de CD-ROM;P3 usa um plotter e duas impressoras;Cada processo precisa de outros recursos (R);

Recursos

UF P I UCD

C =0 0 1 02 0 0 10 1 2 0

Matriz de alocaçãoP1

P2

P3

UF P I UCD

R =2 0 0 11 0 1 02 1 0 0

P1

P2

P3

UF P I UCD

Deadlocks4 unidades de fita;2 plotter;3 impressoras; 1 unidade de CD-ROM

Requisições (satisfazer a condição):P1 requisita 2 unidades de fita e um CD-ROM (não pode atender);P2 requisita 1 unidade de fita e 1 impressora (não pode atender);P3 requisita duas unidades de fita e um plotter;

29


Recursos disponíveisA = (2 1 0 0) P3 pode rodarApós rodar P3 =>A = (2 2 2 0)

C =0 0 1 02 0 0 12 2 2 0

P1

P2

P3

R =2 0 0 11 0 1 00 0 0 0

Matriz de requisiçõesP1

P2

P3

UF P I UCD

Matriz de alocação

Deadlocks4 unidades de fita;2 plotter;3 impressoras; 1 unidade de CD-ROM

Requisições:P1 requisita duas unidades de fita e um CD-ROM;P2 requisita uma unidade de fita e uma impressora;

30


Recursos disponíveisA = (2 1 0 0)A = (2 2 2 0) P2 pode rodarA = (4 2 2 1)

C =0 0 1 03 0 1 10 0 0 0


P2

P3

R =2 0 0 10 0 0 00 0 0 0


P2P3

Deadlocks

Recursos disponíveis

4 unidades de fita;2 plotter;3 impressoras; 1 unidade de CD-ROM

Requisições:P1 requisita duas unidades de fita e um CD-ROM;

31


Recursos disponíveisA = (2 1 0 0)A = (2 2 2 0)A = (4 2 2 1)P1 pode rodar

C =2 0 1 10 0 0 00 0 0 0


P2

P3R =

0 0 0 00 0 0 00 0 0 0


P2

P3

Deadlocks

Recursos existentes Recursos disponíveis

Ao final da execução, temos:4 unidades de fita;2 plotters;3 impressoras; 1 unidade de CD-ROM

32



C =0 0 0 00 0 0 00 0 0 0


P2

P3

R =0 0 0 00 0 0 00 0 0 0


P2

P3

DeadlocksRequisições:

V DEADLOCK: P3 requisita duas unidade de fita, umaimpressora e uma unidade de CD-ROM;

4 unidades de fita;2 plotters;3 impressoras; 1 unidade de CD-ROM

CARO

TEMPO

DE

CPU

33



impressora e uma unidade de CD-ROM;

C =0 0 1 02 0 0 10 1 2 0


P2

P3

UF P I UCD

R =2 0 0 11 0 1 02 1 0 1

Matriz de requisições

P1

P2

P3

UF P I UCD

DeadlocksSe localizado o Impasse. O que deve ser feito?

Recuperação de Deadlocks:

� Por meio de preempção: possibilidade de retirar

34

� Por meio de preempção: possibilidade de retirar temporariamente um recurso de seu atual dono (processo) e entregá-lo a outro processo;

� Por meio de revisão de estado: recursos alocados aum processo são armazenados em arquivos deverificação; quando ocorre um deadlock, osprocessos voltam ao estado no qual estavam antes dodeadlock.

DeadlocksRecuperação de Deadlocks:� Por meio de eliminação de processos: processos queestão no ciclo com deadlock são retirados do ciclo;processos que não causam algum efeito negativo ao

35

processos que não causam algum efeito negativo aosistema;

� Ex1.: compilação – sem problemas;� Ex2.: atualização de um base de dados –problemas nos registros – adiciona 1 (morto) –adicionará 2;

Deadlocks� É possível evitar impasse fazendo uma escolha

correta?

� Evitar dinamicamente o problema:

36

� Evitar dinamicamente o problema:� Alocação individual de recursos;� Utiliza matrizes descritas anteriormente;� Escalonamento cuidadoso;� Trabalhar com Estados Seguros e Inseguros;

Deadlocks� É possível evitar impasse fazendo uma escolha

correta?

� Algoritmos:

37

� Algoritmos:� Extensão do algoritmo de detecção de deadlocks;

� Banqueiro para um único tipo de recurso;� Banqueiro para vários tipos de recursos;

Deadlocks� Estados seguros: não provocam deadlocks e há uma

maneira de atender a todas as requisições pendentes finalizando normalmente todos os processos;

38

processos;

� Existe alguma ordem de escalonamento na qual todo o processo possa ser executado até a sua conclusão;

� Estado inseguros: podem provocar deadlocks, mas não necessariamente provocam;

Deadlocks� Seguro:

utilizado

Total

solicitado

Começa escalonando o processo B

39

72C

42B

93A

72C

44B

93A

72C

-0B

93A

77C

-0B

93A

-0C

-0B

93A

Disponível: 3 Disponível: 1 Disponível: 5 Disponível: 0 Disponível: 7

utilizado

Total

solicitado

Deadlocks� Inseguro (não é deadlock):

� Solicitará e obterá outro recurso� Não há garantia que todos irão terminar

40

72C

42B

93A

72C

42B

94A

72C

44B

94A

72C

--B

94A

Disponível: 3 Disponível: 2 Disponível: 0 Disponível: 4

Começa escalonando o processo A – 1 recurso

Deadlocks� Algoritmos do Banqueiro:

� Idealizado por Dijkstra (1965);� Segue os seguintes princípios (analogia):

Nenhum cliente receberá um empréstimo maior do que o

41

� Nenhum cliente receberá um empréstimo maior do que o capital total do banco.

� Todos os clientes receberão um limite de crédito ao abrir suas contas.

� Nenhum cliente poderá ultrapassar esse limite.� A soma de todos os empréstimos não poderá ultrapassar o capital total do banco.


� Considera cada requisição no momento em que ela ocorre verificando se essa requisição leva a um estado seguro;

42

estado seguro; � Se sim, a requisição é atendida, � Senão, o atendimento é adiado para um outro momento;


� Premissas adotadas por um banqueiro (SO) para garantir ou não crédito (recursos) para seus clientes (processos);

43

clientes (processos);� Nem todos os clientes (processos) precisam de toda a linha de crédito (recursos) disponível para eles;

Deadlocks� Algoritmo do Banqueiro para um único tipo de recurso:

Máximo de linha de crédito = 22Possui

44

A

CD

B0

00

06

47

5A

C*D

B1

24

16

47

5A

CD

B1

24

26

47

5

Livre: 10 Livre: 1Livre: 2

Seguro Seguro Inseguro

• Solicitações de crédito são realizadas de tempo em tempo;• * C é atendido e libera 4 créditos, que podem ser usados por B ou D;

Deadlocks� Algoritmo do Banqueiro para um único tipo de recurso:

Máximo de linha de crédito = 22Possui

45

A

CD

B0

00

06

47

5A

CD

B1

24

16

47

5A

CD

B*1

24

26

47

5

Livre: 10 Livre: 1Livre: 2

Seguro Seguro Inseguro• Solicitações de crédito são realizadas de tempo em tempo;• * B é atendido. Em seguida os outros fazem solicitação, ninguém poderia ser atendido;

Deadlocks� Algoritmo do Banqueiro para vários tipos de recursos:

� Mesma idéia, mas duas matrizes são utilizadas;Recursos � E = (6 3 4 2);Alocados � P = (5 3 2 2);Disponíveis � A = (1 0 2 0);

46

C = Recursos Alocados

A

CD

B3

11

00

11

11

10

01

01

0

E 0 0 0 0

R = Recursos ainda necessários

A

CD

B1

30

01

10

10

01

10

00

2

E 2 1 1 0

Disponíveis � A = (1 0 2 0);

Deadlocks� Algoritmo do Banqueiro para vários tipos de

recursos:

Alocados � P = (5 3 3 2);Disponíveis � A = (1 0 1 0);

47


A

CD

B3

11

00

11

11

10

11

01

0

E 0 0 0 0


A

CD

B1

30

01

10

10

01

00

00

2

E 2 1 1 0


Atender a solicitação de B => seguro

Deadlocks� Algoritmo do Banqueiro para vários tipos de

recursos:

Alocados � P = (5 3 4 2);Disponíveis � A = (1 0 0 0);

48


A

CD

B3

11

00

11

11

10

11

01

0

E 0 0 1 0


A

CD

B1

30

01

10

10

01

00

00

2

E 2 1 0 0


• Deadlock � Solução: Adiar a requisição de E por alguns instantes;Inseguro: negar

Deadlocks� Algoritmo do Banqueiro:

� Desvantagens� Pouco utilizado, pois é difícil saber quais recursos serão necessários;

49

serão necessários;� O número de processos é dinâmico e pode variar constantemente tornando o algoritmo custoso (difícil de implementar);

� Vantagem� Teoricamente => o algoritmo é ótimo;

Deadlocks� Prevenir Deadlocks:

� Atacar uma das quatro condições:

Alocar todos os recursos usando um spoolExclusão Mútua

Condição Abordagem

50

Ordenar numericamente os recursos; Mais atrativa de ser praticada;

Espera Circular

Retirar recursos dos processosNão-preempção

Requisitar todos os recursos inicialmenteUso e Espera

Alocar todos os recursos usando um spoolExclusão Mútua

• Recursos: Preemptivo e não preemptivo

• Impasses: modelagem

Aula 07 - Sumário

• Algoritmo do avestrutz

• Detecção e recuperação de impasses

• Evitando impasses

• Prevenção de impasses

Leituras Sugeridas• Silberschatz, A., Galvin, P. B. Gagne,

G. Sistemas Operacionais com Java. 7º edição. Editora Campus, 2008 .

• TANENBAUM, A. Sistemas Operacionais Modernos. Rio de Janeiro: Pearson, 3 ed. 2010

Acesse o link abaixo:

http://hostel.ufabc.edu.br/~marcelo.nascimento/

Nota de Aula

http://hostel.ufabc.edu.br/~marcelo.nascimento/

Obrigado!!!

1. Considere o deadlock de tráfego indicado na figura abaixo:a) Mostre que as quatros condições para o deadlock

de fato estão presentes nesse exemplo.b) Apresente uma regra simples que evite deadlock

Exercícios - Deadlocks

54

b) Apresente uma regra simples que evite deadlock nesse sistema.

2. Dados que os dispositivos são todos do mesmo tipo e utilizando as definições apresentada sobre o algoritmo do Banqueiro responda às seguintes perguntas:a)Determine as requisições restantes para cada programa no sistema.

Exercícios - Deadlocks

55

a)Determine as requisições restantes para cada programa no sistema.b) Determine se cada sistema é seguro ou inseguro.c) Se o sistema tiver em estado seguro, relacione a seqüência de requisições e liberações que possibilitará a execução completa de todos os processos.d) Se o sistema estiver em estado inseguro, mostre como é possível ocorrer um impasse.

i)Sistema A tem 12 dispositivos; apenas 1 está disponível.

Exercícios

651

Requisições restantes

Máximo de requisições

Dispositivos alocados

Número do programa

56

204

623

742

651

ii)Sistema B tem 14 dispositivos; apenas 2 está disponível.

Exercícios

851

Requisições restantes

Máximo de requisições

Dispositivos alocados

Número do programa

57

843

932

851

Documents

bc1518 SO Aula07 Deadlock - hostel.ufabc.edu.brhostel.ufabc.edu.br/.../bc1518_SO_Aula07_Deadlock.pdf · BC1518-Sistemas Operacionais Deadlock (Impasse) Prof. Marcelo Z. do Nascimento