Deadlocks e Recursos em Sistemas Operacionais

Prévia do material em texto

Sistemas 
Operacionais
Prof. Marcelo Aires
Engenharia da Computação
6º Período
2019.2
Deadlocks
Prof. Marcelo Aires
Engenharia da Computação
6º Período
2019.2
Recurso
● Exemplos de recurso:
○ Memória
○ HD
○ GPU
○ Informação
● Recurso é tudo aquilo que pode ser usado;
● Processos necessitam de acesso aos recursos em ordem 
racional (organizado, raciocinado, sabedoria);
Recurso
● Exemplo de impasse (deadlock):
○ Suponha que um processo 1 possui o recurso A e solicita o 
recurso B;
○ No mesmo momento, o recurso B esteja sendo usado pelo 
processo 2 que também solicita o recurso A;
○ Ambos processos querem usar os dois recursos;
○ Ambos processos são bloqueados e irão permanecer 
assim eternamente;
○ Quando dois processos necessitam de um mesmo 
recurso, eles estão na região crítica.
Recursos
● Os recursos podem ser:
○ Preemptíveis:
■ podem ser retirados de um processo sem quaisquer 
efeitos;
■ Exemplo: memória (podemos atualizar informações)
○ Não preemptíveis:
■ vão induzir o processo a falhar se retirados.
■ Exemplo: impressora (uma impressão não pode 
sobrepor à outra)
Recursos
● Eventos necessários para os processos usarem um recurso:
○ solicitar o recurso;
○ usar o recurso;
○ liberar o recurso;
● Caso o recurso solicitado seja negado:
○ o processo que solicitou pode ser bloqueado; ou
○ pode falhar, resultando em um código de erro.
O que é um 
Deadlock?
Deadlock
● Conceito formal:
○ Um conjunto de processos do Sistema Operacional está 
em situação de Deadlock se todo processo pertencente 
ao conjunto estiver esperando por um evento que 
somente outro processo desse mesmo conjunto poderá 
fazer acontecer.
● Normalmente, o evento é uma liberação de um recurso 
atualmente retido;
● Devido ao impasse, nenhum processo consegue:
○ executar;
○ liberar recursos;
○ ser acordado.
Deadlock
● Deadlocks ocorrem quando os processos detém acesso 
exclusivo aos recursos;
● Existem quatro condições para ocorrer Deadlocks (obrigatório):
○ Condição de exclusão mútua
■ todo recurso está associado a um processo ou disponível
○ Condição de posse e espera
■ processos que retém recursos podem solicitar novos recursos
○ Condição de não preempção
■ recursos concedidos previamente não podem ser tomados à força
○ Condição de espera circular
■ deve ser uma cadeia circular de 2 ou mais processos;
■ cada um está à espera de recurso retido por outro processo da 
cadeia.
Modelagem de Deadlock
● (a) recurso R alocado ao procedo A;
● (b) processo B solicita o recurso S;
● (c) processos C e D estão em deadlock sobre os recursos T e U.
Tratamento de Deadlock
● ignorar por completo o problema
○ tô nem aí
● detecção e recuperação
○ espero acontecer e depois trato
● evitação dinâmica
○ alocar cuidadosamente os recursos
● prevenção
○ negar uma das quatro condições necessárias
Como ocorre o Deadlock
Como pode evitar um Deadlock
Algoritmo do Avestruz
● Finge que o problema não existe (mete a cabeça na areia)
● Resolve razoavelmente se
○ deadlocks ocorrem muito raramente
○ custo de prevenção é alto
● UNIX e Windows seguem esta abordagem
● Abordagem de ponderação entre conveniência e correção
● Sistemas robustos
○ ocorrência rara
○ se ocorrer, não é fim do mundo
Detecção de deadlock
Detecção de deadlock
● Observe a posse e solicitações de recursos
● Um ciclo pode ser encontrado dentro do grafo
Prevenção do Deadlock
● Estruturas de dados necessárias ao algoritmo de
detecção de deadlock
Exemplo de algoritmo de detecção
● E: Todos os recursos
● A: Disponível
● C: em uso
● R: recursos solicitados
● Cada linha equivale a um 
processo
● Como funciona:
○ Olhando para A, qual 
processo em R pode 
ser executado?
Recuperação de Deadlock
● Recuperação através de preempção
○ retira um recurso de algum outro processo, a depender da 
natureza do recurso
● Recuperação através de reversão de estado
○ verifica um processo periodicamente e salva o estado;
○ reinicia o processo ou parte se este é encontrado em 
estado de deadlock
● Recuperação através da eliminação de processos
○ forma mais grosseira, mas é mais simples
○ elimina um dos processos do ciclo de deadlock
○ escolhe um processo que pode ser reexecutado desde seu 
início
Trajetórias de recursos (prevenção)
Estados Seguros e Inseguros
● Demonstração de que o estado em (a) é seguro
Estados Seguros e Inseguros
● Demonstração de que o estado em (b) é inseguro
Algoritmo do Banqueiro
● É um algoritmo de alocação de recursos com prevenção de 
impasses;
● Desenvolvido por Edsger Dijkstra;
● Testa a segurança pela simulação da alocação e em seguida 
faz uma verificação de estados-seguros para testar a 
possibilidade de condições de impasse.
● Ele precisa saber três coisas:
○ Quanto de cada recurso cada processo poderia solicitar;
○ Quanto de cada recurso cada processo atualmente detém;
○ Quanto de cada recurso o sistema tem disponível.
Algoritmo do Banqueiro (1 recurso)
● Três estados de alocação de recursos
○ (a) seguro
○ (b) seguro
○ (c) inseguro
algoritmo_do_banqueiro(conjunto de processos P, recursos disponíveis A) {
while (P não vazio) {
boolean achou = false
for each (processo p in P) {
Cp = atual alocação de recursos para o processo(p)
Mp = requisito máximo de recursos para o processo(p)
if (Mp − Cp ≤ A) {
// p pode obter tudo de que necessita.
// Suponha que ele faz isso, termina, e libera o que ele já tem.
A = A + Cp
remove_elemento_do_conjunto(p, P)
achou = true
}
}
if (not achou) { return INSEGURO }
}
return SEGURO
}
Algoritmo do Banqueiro
● Recursos do sistema disponíveis são:
A B C D
3 1 1 2
● Processos (recursos atualmente alocados):
A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 1 1 0
● Processos (máximo de recursos):
A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 1 5 0
Algoritmo do Banqueiro
● Exemplo anterior é um estado de segurança, cada processo 
adquire o máximo de seus recursos e, em seguida, finaliza:
○ P1 adquire os recursos 2 A, 1 B e 1 D, atingindo o seu máximo
■ Disponíveis: 1 A, nenhum B, 1 C e 1 D
○ P1 termina, retornando os recursos 3 A, 3 B, 2 C e 2 D
■ Disponíveis 4 A, 3 B, 3 C e 3 D
○ P2 adquire 2 B e 1 D recursos extras, então termina, retornando 
todos os seus recursos
■ Disponíveis: 5 A, 3 B, 6 C e 6 D
○ P3 adquire os recursos 4 C e termina
■ Disponíveis: 6 A, 4 B, 7 C e 6 D
● Todos os processos foram capazes de terminar, esse estado é 
seguro.
Exemplo de Algoritmo do Banqueiro
com múltiplos recursos
Todos os recursos
Em uso
Disponível