aula18_Eliminando_Deadlocks (1)

Prévia do material em texto

1
Sistemas Operacionais Sistemas Operacionais –– Ciência da ComputaCiência da Computaççãoão
DeadlocksDeadlocks (impasses)(impasses)
Algoritmos para eliminar Algoritmos para eliminar DeadlocksDeadlocks
Prof. Humberto Brandão
humberto@dcc.ufmg.br
aula disponível no site:
http://www.dcc.ufmg.br/~humberto/unifal/
Universidade Federal de Alfenas
Departamento de Ciências Exatas
versão da aula: 0.1
Algoritmos para eliminar Deadlocks
• Estratégias para tratar Deadlocks
– Ignorar por completo o problema
– Detecção e recuperação
– Alocação cuidadosa de recursos (evita o deadlock)
– Prevenção
• Negação de uma das quatro condições necessárias
Algoritmo do Avestruz
Ignorar por completo o problema
Algoritmo do Avestruz
• Método mais simples;
•• Finja que nada estFinja que nada estáá acontecendo;acontecendo;
• O incrível é que esta pode ser uma saída interessante;
•• MatemMatemááticosticos consideram totalmente inaceitável;
•• EngenheirosEngenheiros perguntam com que freqüência o deadlock
ocorre.
Ignorar por completo o problema
Algoritmo do Avestruz
• Questionamentos importantes:
– Qual é importânciaimportância do software que está sendo 
analisado. Ele pode parar?
– Com que freqfreqüüênciaência o deadlock ocorre? (em média)
Ignorar por completo o problema
Algoritmo do Avestruz
• A maioria dos S.O.s, incluindo Unix e Windows, Unix e Windows, 
ignoram situaignoram situaçções de ões de deadlockdeadlock:
– Isso porque consideraram que o custo de seu o custo de seu 
tratamento tratamento éé alto demaisalto demais.
• Evidentemente, em S.O.s com outros propem S.O.s com outros propóósitos, sitos, 
existe a inversão deste valor:existe a inversão deste valor:
– Exemplo: trabalhando com Sistemas Militares.trabalhando com Sistemas Militares.
2
Detecção e Recuperação de Deadlocks
Detecção e Recuperação de Deadlocks
• Na detecdetecçção e recuperaão e recuperaççãoão de deadlocks, o o 
sistema não tenta prevenir a ocorrência dos sistema não tenta prevenir a ocorrência dos 
deadlocksdeadlocks;
• O algoritmo se resume a:
– Detectar que um deadlock ocorreu (operações em 
grafos);
– Detectar quais processos estão envolvidos no deadlock
(operações em grafos);
– Corrigir o problema (várias formas);
Detecção e Recuperação de Deadlocks
• Para detectar que um detectar que um deadlockdeadlock ocorreuocorreu basta saber se o 
grafografo, que representa a interação entre recursos e 
processos, possui ciclospossui ciclos;
• Obrigações do S.O.:
– Sempre que um processo/recurso é criado, um nó do tipo 
“circulo”/”quadrado” é inserido no grafo;
– Sempre que um processo/finalizado é finalizado, seu nó é
removido do grafo (incluindo suas arestas);
– Sempre que um processo aguarda um recurso, uma aresta do nó
do processo é criada em direção ao nó do recurso;
– Sempre que um processo tem a posse de um recurso, uma aresta 
do nó do recurso é criada em direção ao nó do processo;
Modelagem de um deadlock
Relembrando...
• Para facilitar a visualização, podemos utilizar grafos 
para entender um deadlock;
a) recurso R alocado ao processo A
b) processo B está solicitando/esperando pelo recurso S
c) processos C e D estão em deadlock sobre recursos T e U
Detecção e Recuperação de Deadlocks
• Consideremos um grafo qualquer representando 
a interação entre processos e recursos;
– Um deadlockdeadlock existe se somente se o grafo possui ciclosgrafo possui ciclos;
–– Todo processo que faz parte do ciclo, estTodo processo que faz parte do ciclo, estáá dormindo dormindo 
(sem possibilidade de ser acordado)(sem possibilidade de ser acordado);
– Os outros processos do grafo continuam em situação 
normal de operação;
Detecção e Recuperação de Deadlocks
• Sobre os processos de A a G e recursos de R a W, 
consideremos as operaconsideremos as operaççõesões:
– O processo A possui o recurso R e requisita S;
– O processo B requisita T;
– O processo C requisita S;
– O processo D possui o recurso U e requisita S e T;
– O processo E possui o recurso T e requisita V;
– O processo F possui o recurso W e requisita S;
– O processo G possui o recurso V e requisita U;
3
Detecção e Recuperação de Deadlocks
• Visualizando com um grafo planargrafo planar:
– Observe a posse e solicitações de recursos
– Um ciclo pode ser encontrado dentro do grafo, denotando deadlock
Detecção e Recuperação de Deadlocks
• Visualizando com um grafo planargrafo planar:
– Observe a posse e solicitações de recursos
– Um ciclo pode ser encontrado dentro do grafo, denotando deadlock
Utilizando a inspeinspeçção ão 
visualvisual éé ffáácil detectar cil detectar 
que o grafo possui um que o grafo possui um 
ciclociclo.
Mas comocomo isso pode 
ser detectado 
computacionalmente?computacionalmente?
Detecção e Recuperação de Deadlocks
• O algoritmo de busca em profundidade pode busca em profundidade pode 
ser utilizadoser utilizado para detecção de ciclos em grafos;
• Ou seja, pode ser utilizado para detectar se 
existe um deadlock na interação entre 
processos/recursos;
• Para detalhes, consulte o livro: Algoritmos, 
Teoria e Prática, de Thomas Cormen, 2ª edição, 
página 430;
Detecção e Recuperação de Deadlocks
• Após a detecção de um deadlock, o S.O. deve 
restabelecer a normalidade na operação do 
sistema;
• O que/como pode ser feito?
Detecção e Recuperação de Deadlocks
• O que pode ser feito?
– Recuperação por meio de preempção;
– Recuperação por meio de reversão de estado;
– Recuperação por meio de eliminação de processos;
Detecção e Recuperação de Deadlocks
Recuperação por meio de preempção
• Em alguns casos, pode ser posspode ser possíível vel tomartomar
provisoriamenteprovisoriamente um recurso de seu proprietum recurso de seu proprietáário atual rio atual 
para fornecêpara fornecê--lo a outro processolo a outro processo;
• Por exemplo:
– Se a impressora R for tomada do processo A, a 
impressora deve parar a impressão de A, empilhar o 
conteúdo de sua bandeja em outro compartimento, 
para iniciar sua operação com seu novo processo 
proprietário; Ao final, deve desempilhar as folhas da 
impressão de A, e continuar sua impressão;
4
Detecção e Recuperação de Deadlocks
Recuperação por meio de preempção
• Portanto, a recuperação por meio de preemppreempççãoão estestáá
diretamente relacionada com a diretamente relacionada com a natureza do recursonatureza do recurso;
• Visando eliminar o deadlock, O S.O. deveria conhecer 
previamente todos os recursos para efetuar, se possível, 
tal operação;
• É possível?
Detecção e Recuperação de Deadlocks
• O que pode ser feito?
– Recuperação por meio de preempção;
– Recuperação por meio de reversão de estado;
– Recuperação por meio de eliminação de processos;
Detecção e Recuperação de Deadlocks
Recuperação por meio de reversão de estado;
• Para entender este algoritmo, imagine, via grafos, que o 
processo possui um determinado estado em cada 
instante de tempo;
• O S.O. então controlaria uma MMááquina de Estado quina de Estado 
FinitoFinito.
• Sempre, antes de requisitar um recurso, o processo antes de requisitar um recurso, o processo 
deve armazenar em um arquivo tempordeve armazenar em um arquivo temporáário seu estado rio seu estado 
atualatual;
Detecção e Recuperação de Deadlocks
Recuperação por meio de reversão de estado;
•• Sempre que um Sempre que um deadlockdeadlock ocorrerocorrer, o S.O. escolhe um 
processo para processo para ““regredirregredir”” no tempono tempo, assumindo seu 
estado anterior ao pedido do recurso;
• Com isso, seu processo concorrente pode utilizar o 
recurso sem restrições, e o processo que regrediu entra 
no estado bloqueado, aguardando a liberação do 
recurso;
Detecção e Recuperação de Deadlocks
Recuperação por meio de reversão de estado;
•• Quais são os problemas deste mQuais são os problemas deste méétodo?todo?
Detecção e Recuperação de Deadlocks
Recuperação por meio de reversão de estado;
•• Quais são os problemas deste mQuais são os problemas deste méétodo?todo?
– O custo para guardar as imagens pode ser alto 
demais:
• Processo que ocupa muitamemória, ou;
• Processo que efetua muitas requisições invocará muitas 
vezes a função de imagem no disco;
– Processos que interagem com usuários finais:
• Imagine perder tudo que digitou no editor de textos nos 
últimos 10 minutos;
– Processos que interagem com outros processos:
• Exemplo: (comunicação em uma rede). Se um processo 
regredir, a comunicação pode ser totalmente perdida;
5
Detecção e Recuperação de Deadlocks
• O que pode ser feito?
– Recuperação por meio de preempção;
– Recuperação por meio de reversão de estado;
– Recuperação por meio de eliminação de processos;
Detecção e Recuperação de Deadlocks
Recuperação por meio de eliminação de processos;
• Método radical;
• Sempre que um ciclo é identificado no grafo, o S.O. o S.O. 
mata um processomata um processo;
• Se o ciclo ainda existir, ele mata outro, até quebrar o 
ciclo, eliminando consequentemente o deadlock;
• O S.O. tem que ter o cuidado de não matar processos 
que não pertencem ao ciclo;
Detecção e Recuperação de Deadlocks
Recuperação por meio de eliminação de processos;
•• Amenizando os efeitos da eliminaAmenizando os efeitos da eliminaçção de processos:ão de processos:
– Prioridades podem ser definidas entre processos 
(grau de importância entre processos);
– Ou seja, indicar a ordem de importância entre os 
processos, para minimizar os efeitos colaterais na 
eliminação do deadlock;
– Exemplo: um compilador sempre pode ser 
reexecutado sem problemas, então, sua prioridade 
pode ser baixa;
Detecção e Recuperação de Deadlocks
• Resumindo a Detecção e Recuperação de 
Deadlocks:
–– Na recuperaNa recuperaçção de deadlocks, nenhuma estratão de deadlocks, nenhuma estratéégia se gia se 
mostra interessante para sistemas operacionais de mostra interessante para sistemas operacionais de 
uso geral...uso geral...
• Recuperação por meio de preempção;
• Recuperação por meio de reversão de estado;
• Recuperação por meio de eliminação de processos;
Deadlocks
•• PrPróóxima aula:xima aula:
– Eliminando deadlocks por prevenção, através de suas 
condições fundamentais:
• Condição de exclusão mútua;
• Condição de posse-e-espera;
• Condição de não preempção;
• Condição de espera circular;
Referencia
• Sistemas Operacionais Modernos. Tanenbaum, 
A. S. 2ª edição. 2003