Aula08_Deadlock

Prévia do material em texto

Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Aula 08 
Capítulo 8 – Deadlocks 
• 8.1 Modelo do sistema 
• 8.2 Caracterização do deadlock 
• 8.3 Métodos para tratamento de deadlocks 
• 8.4 Prevenção de deadlock 
• 8.5 Evitar deadlock 
• 8.6 Detecção de deadlock 
• 8.7 Recuperação do deadlock 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
O Problema do Deadlock 
• Um conjunto de processos bloqueados, cada um 
retendo um recurso e esperando para adquirir um 
recurso retido de outro processo no conjunto. 
• Exemplo: 
– O sistema possui 2 unidades de fita 
– P1 e P2 mantêm, cada um, uma unidade de fita, e cada 
uma delas precisa de outra unidade. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Exemplo do Cruzamento da Ponte 
 
• Tr fego em um nico sentido. 
• Cada se ão de uma ponte pode ser vista como um 
recurso. 
• Se ocorrer um deadlock, ele pode ser resolvido se um 
dos carros recuar (preemptar recursos e reverter). 
• V rios carros podem ter de recuar se um deadlock 
ocorrer. 
 poss vel haver Starvation. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.1 Modelo do Sistema 
• Um sistema consiste em um número finito de recursos 
a serem distribuídos entre processos concorrentes. 
• Os recursos são divididos em vários tipos, cada qual 
consistindo em múltiplas instâncias idênticas. 
• Um processo deve solicitar um recurso antes de usá-
lo, e deverá liberar o recurso após o uso. 
• O processo pode solicitar tantos recursos quantos 
achar necessários para realizar sua tarefa. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.1 Modelo do Sistema 
• Mas o número de recursos solicitados não pode 
exceder o número total de recursos disponíveis no 
sistema. 
• Tipos de recursos R1, R2, . . ., Rm 
Ciclos de CPU, espaço de memória, dispositivos 
de E/S 
• Cada tipo de recurso Ri possui Wi instâncias. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.1 Modelo do Sistema 
• Cada processo usa um recurso desta forma: 
– Requisitar => o processo requisita o recurso, se o 
pedido não puder ser satisfeito o processo entrar em 
estado de espera. 
– Usar => o processo pode operar o recurso. 
– Liberar => o processo libera o recurso. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.2 Caracterização do Deadlock 
• Deadlocks são indesejáveis. 
• Os processos nunca terminam sua execução e os 
recursos do sistema ficam comprometidos, impedindo 
que outras tarefas sejam iniciadas. 
• Vamos examinar mais de perto as características dos 
deadlocks. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.2.1 Condições necessárias 
• Pode haver deadlock se quatro condições ocorrerem 
simultaneamente: 
– Exclusão mútua: Somente um processo de cada vez 
pode usar um recurso. 
– Manter e esperar: Um processo retendo pelo menos 
um recurso está esperando para adquirir recursos 
adicionais mantidos por outros processos. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
– Sem preempção: Um recurso pode ser liberado 
apenas voluntariamente pelo processo que o mantém, 
após esse processo ter completado sua tarefa. 
– Espera circular: Existe um conjunto {P0, P1, …, Pn} de 
processos esperando de modo que P0 está esperando 
um recurso que é mantido por P1, P1 está esperando 
um recurso que é mantido por P2, …, Pn–1 está 
esperando um recurso que é mantido por Pn, e Pn está 
esperando um recurso que é mantido por P0. 
8.2.1 Condições necessárias 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.2.2 Grafo de Alocação de Recursos 
• Um conjunto de vértices V e um conjunto de arestas A 
– V é particionado em dois tipos: 
• P = {P1, P2, …, Pn}, o conjunto consistindo em todos 
os processos ativos no sistema 
 
• R = {R1, R2, …, Rm}, o conjunto consistindo em todos 
os tipos de recursos no sistema 
– aresta de requisição – aresta direcionada P1  Rj 
– aresta de atribuição – aresta direcionada Rj  Pi 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Processo 
 
• Tipo de recurso com 4 instâncias 
 
 
• Pi requisita instância de Rj 
 
 
• Pi está mantendo 
 uma instância de Rj 
Pi
Pi 
Rj 
Rj 
8.2.2 Grafo de Alocação de Recursos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Os conjuntos P, R e A: 
– P = {P1, P2, P3} 
– R = {R1, R2, R3 , R4} 
– A = {P1  R1, P2  R3, R1  P2 , R2  P2 , R2  P1, R3 
 P3} 
• Instância de Recursos: 
– 1 instância para R1 
– 2 instância para R2 
– 1 instância para R3 
– 3 instância para R4 
8.2.2 Grafo de Alocação de Recursos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Estados do processo: 
– P1 mantém 1 instância de R2 e espera por 1 instância 
de R1; 
– P2 mantém 1 instância de R1 e R2 e espera por 1 
instância de R3; 
– P3 mantém 1 instância de R3. 
• Se o grafo não tiver ciclos, nenhum processo no 
sistema está em deadlocks, senão poderá haver 
deadlocks. 
8.2.2 Grafo de Alocação de Recursos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Exemplo de um Grafo de Alocação 
de Recursos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Grafo de Alocação de Recursos com um 
Deadlock 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Grafo de Alocação de Recursos 
com um Ciclo mas sem Deadlock 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Fatos Básicos 
• Se o gr fico não cont m ciclos  nenhum deadlock. 
 
• Se o gr fico cont m um ciclo  
– se apenas uma instância por tipo de recurso, ocorre 
deadlock 
– se v rias instâncias por tipo de recurso, h 
possibilidade de deadlock 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.3 Métodos para Tratamento de 
Deadlocks 
• Podemos lidar com o problema de deadlock de três 
maneiras: 
– Podemos usar um protocolo para prevenir ou evitar 
deadlocks, garantindo que o sistema nunca entre em 
estado de deadlock. 
– Podemos permitir que o sistema entre em um estado de 
deadlock, detectá-lo e recuperar. 
– Podemos ignorar o problema e fingir que os deadlocks 
nunca ocorrem no sistema. 
• Ignora o problema e finge que o deadlock nunca 
ocorre no sistema; usado pela maioria dos sistemas 
operacionais, inclusive o UNIX e o Windows. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.4 Prevenção de Deadlock 
• É um conjunto de métodos utilizados para garantir que 
pelo menos uma das condições necessárias não 
seja válida. 
• Esses métodos previnem deadlocks restringindo o 
modo como as requisições de recursos podem ser 
feitas. 
• Quais são as condições necessárias? Lembra? 
– Exclusão Mútua 
– Manter e esperar 
– Não preempção 
– Espera circular 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.4.1 Exclusão mútua 
• A condição de exclusão mútua precisa ser mantida 
para recursos não compartilháveis. 
• Por exemplo: 
– Uma impressora não pode ser compartilhada 
simultaneamente por vários processos. 
• Recursos compartilháveis, ao contrário, não exigem 
acesso por exclusão mútua e, portanto, não podem 
estar envolvidos em um deadlock. 
• Por exemplo: 
– Arquivo somente de leitura, vários processos podemreceber acesso simultâneo ao arquivo. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Para garantir que a condição de manter e esperar 
nunca ocorra no sistema, precisamos garantir que, 
sempre que um processo requisitar um recurso, ele 
não manterá quaisquer outros recursos. 
– Exige que cada processo requisite e receba a alocação 
de todos os seus recursos antes de iniciar sua 
execução, ou permite que um processo requisite 
recursos apenas quando não tiver nenhum outro. 
8.4.2 Manter e esperar 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.4.3 Não preempção 
• Para garantir que essa condição não seja satisfeita, 
podemos usar o protocolo a seguir: 
– Se um processo que estiver mantendo alguns recursos 
requisitar outro recurso que não possa ser alocado 
imediatamente para ele, então todos os recursos 
atualmente mantidos são liberados. 
– Os recursos preemptados são acrescentados lista de 
recursos pelos quais o processo est esperando. 
– O processo ser reiniciado somente quando puder 
reaver seus recursos antigos, assim como os novos que 
ele est requisitando. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.4.4 Espera circular 
• Um modo de garantir que essa condição nunca 
aconteça é impor uma ordena ão total de todos os 
tipos de recursos e exigir que cada processo requisite 
recursos em uma ordem crescente de enumera ão. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.5 Evitar Deadlock 
• Um método alternativo para evitar deadlocks é exigir 
informações adicionais sobre como os recursos 
devem ser requisitados. 
• Os diversos algoritmos diferem na quantidade e no 
tipo de informações exigidas. 
• O modelo mais simples e útil exige que cada processo 
declare o número máximo de recursos de cada tipo 
que possa ser necessário. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.5 Evitar Deadlock 
• O algoritmo para evitar deadlock examina 
dinamicamente o estado de alocação de recursos 
para garantir que a condição de espera circular nunca 
possa existir. 
• O estado de alocação de recursos é definido pelo 
número de recursos disponíveis e alocados e pelas 
demandas máximas dos processos. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.6 Detecção de Deadlock 
• Se um sistema não emprega um algoritmo para 
prevenção de deadlock nem para evitar deadlock, 
então uma situação de deadlock poderá ocorrer. 
Nesse caso o sistema deverá fornecer uma das 
seguintes opções: 
– Um algoritmo que examine o estado do sistema para 
determinar se ocorreu um deadlock. 
– Um algoritmo para recuperar o sistema do deadlock. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.7 Recuperação do Deadlock 
• Quando um algoritmo de detecção determina a 
existência de um deadlock, há várias alternativas: 
– Uma possibilidade é informar ao operador que ocorreu 
um deadlock e deixar que o operador trate do deadlock 
manualmente. 
– Outra possibilidade é deixar o sistema se recuperar do 
deadlock automaticamente. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.7 Recuperação do Deadlock 
• Existem duas opções para desfazer um deadlock: 
– Uma é abortar um ou mais processos para interromper 
a espera circular – 8.7.1 Término do processo. 
– A outra é fazer a preempção de alguns recursos de um 
ou mais processos em deadlock – 8.7.2 Preempção de 
recursos. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
8.7.1 Término do processo 
• Para eliminar deadlocks abortando um processo, 
usamos um dentre dois métodos. Nos dois métodos, o 
sistema reinvidica todos os recursos alocados aos 
processos terminados. 
• Dois métodos: 
– Abortar todos os processos em deadlock. 
– Abortar um processo de cada vez até que o ciclo de 
deadlock seja eliminado. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
– Abortar todos os processos em deadlock 
• Esse método desfará o ciclo de deadlock, mas com um 
custo alto; os processos em deadlock podem ter sido 
executados por muito tempo, e os resultados da 
computação parcial precisam ser descartados e 
provavelmente terão de ser refeitos mais tarde. 
8.7.1 Término do processo 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
– Abortar um processo de cada vez até que o ciclo de 
deadlock seja eliminado 
• esse método incorre em um custo adicional considerável, 
visto que, depois de cada processo ser abortado, um 
algoritmo de detecção de deadlock precisa ser invocado 
para determinar se quaisquer processos ainda estão em 
deadlock. 
8.7.1 Término do processo 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Abortar um processo pode não ser fácil. Muitos 
fatores podem afetar qual processo é escolhido, 
incluindo: 
– Prioridade do processo 
– Por quanto tempo o processo esteve em execução e 
quanto tempo mais levará para ser concluído 
– Recursos que o processo usou 
– Recursos de que o processo precisa para ser concluído 
– Quantos processos precisarão ser terminados 
– Se o processo é interativo ou em batch 
8.7.1 Término do processo 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Para eliminar deadlocks usando preempção de 
recursos, apropriamos alguns recursos dos processos 
com sucesso e entregamos esses recursos a outros 
processos, até que o ciclo de deadlock ser desfeito. 
• Se a preempção tiver de lidar com deadlocks, então 
três questões precisam ser resolvidas: 
– Seleção de uma vítima 
– Reversão (Rollback) 
– Starvation 
8.7.2 Preempção de recursos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
– Seleção de uma vítima 
• Quais recursos e quais processos devem ser 
preemptados? 
• Assim como no término do processo, temos de determinar 
a ordem da preempção para minimizar o custo. 
• Os fatores de custo podem incluir parâmetros como 
número de recursos que um processo em deadlock está 
mantendo e o tempo que o processo consumiu até aqui 
durante sua execução. 
8.7.2 Preempção de recursos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
– Reversão (Rollback) 
• Se apropriarmos um recurso de um processo, o que 
deverá ser feito com esse processo? 
• Logicamente, ele não pode continuar com sua 
execução normal; ele não possui algum recurso 
necessário. 
• Temos de efetuar o rollback do processo até algum 
estado seguro e reiniciá-lo a partir desse estado. 
8.7.2 Preempção de recursos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
– Starvation 
• Como garantimos que a starvation não ocorrerá? Ou 
seja, como podemos garantir que nem sempre os 
recursos do mesmo processo serão preemptados? 
• Em um sistema em que a seleção da vítima se 
baseia principalmente em fatores de custo, pode 
acontecer que o mesmo processo sempre seja 
escolhido como vítima. 
• Temos de garantir que um processo poderá ser 
escolhido como vítima apenas por um número finito 
(pequeno)de vezes. A solução é incluir o número de 
rollback no fator de custo. 
8.7.2 Preempção de recursos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Técnica Combinada 
para Tratamento de Deadlock 
• Combina os três m todos b sicos: 
– Prevenir 
– Impedir 
– Detectar 
• Usa a t cnica mais apropriada para tratarde 
deadlocks dentro de cada classe de recursos em um 
sistema. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Deadlock de tráfego 
Sistemas Operacionais com Java 
Referências 
• Capítulo 8 da referência abaixo: 
– SILBERSCHATZ, ABRAHAM; GAGNE, GREG; 
GALVIN, PETER BAES. Sistemas operacionais: 
com java. . Rio de Janeiro: Elsevier, 2004. 
 
Silberschatz, Galvin e Gagne (c) 2003