Impasses em Computação

Prévia do material em texto

Sistemas Operacionais
DeadLock
 
Impasses - Deadlock
● Os computadores possuem inúmeros recursos 
que são adequados ao uso de somente um 
processo por vez.
● Um exemplo desses dispositivos são: 
impressoras, unidades de fita, gravadores de 
cd/dvd/blu-ray
● O único problema ocorre quando 2 ou mais 
processos tentam utilizar uma impressora ao 
mesmo tempo
 
Impasses - Deadlock
● Nesse caso, o SO deve ser capaz de garantir 
(temporariamente) o acesso exclusivo de um 
processo a certos recursos
● Podem ocorrer impasses em diversas 
situações, sendo que quando ocorra a essas 
situações, os 2 processos travam gerando 
assim, deadlock
 
Deadlock
● Temos 2 tipos de recursos, os recursos 
preemptíveis e não preemptíveis.
● No primeiro caso, podemos evitar o deadlock 
simplesmente retirando do recurso o processo 
que ele esta usando.
● Já no segundo caso isso não é possível, pois o 
processo não permite tal situação.
 
Deadlock
● Em geral, os deadlocks envolvem recursos não 
preemptíveis
● Situações de deadlock que envolvem recursos 
preemptíveis podem ser resolvidos facilmente, 
sendo assim, trataremos apenas os recursos 
não preemptíveis
 
Deadlock
● Para compreendermos os deadlocks, devemos 
entender a sequencia de eventos necessários 
para o uso de um determinado recurso:
– Requisitar o recurso
– Usar o recurso
– Liberar o recurso
● Caso o recurso não esteja disponível, o 
processo solicitante será forçado esperar.
 
Introdução a Impasses
● Um impasse pode ser definido como:
– “Um conjunto de processos estará em 
situação de impasse se todo processo 
pertencente ao conjunto estiver esperando 
por um evento que somente outro processo 
desse mesmo conjunto poderá fazer 
acontecer”
 
Introdução a Impasses
● Há quatro condições que geram uma condição 
de impasse:
– Condição de Exclusão Mútua. Em um 
determinado instante, cada recurso está em 
uma das situações: ou associado a um único 
processo ou disponível.
– Condição de Posse e espera. Processos 
que, em um determinado instante, retêm 
recursos concedidos anteriormente podem 
requisitar novos recursos
 
Introdução a Impasses
– Condição de não Preempção. Recursos 
concedidos a um processo que não podem 
ser forçosamente tomados desse processo.
– Condição de Espera Circular. Deve existir 
um encadeamento circular de dois ou mais 
processos, onde cada um deles encontra-se 
em espera de um recurso que esta ocupado.
 
Introdução a Impasses
● Todas essas 4 condições devem estar 
presentes para que um impasse ocorra. Se 
faltar uma delas, o impasse não ocorrerá
 
Introdução a Impasses
● Em geral, 4 estratégias são usadas para lidar 
com impasses:
– Ignorar por completo o problema;
– Detecção e Recuperação;
– Anulação dinâmica por meio de uma 
alocação cuidadosa de recursos;
– Prevenção, negando estruturalmente uma 
das 4 condições necessárias para gerar um 
impasse.
 
Algoritmo do Avestruz
● É o método mais simples, pois nesse algoritmo 
devemos fazer como o avestruz: enterre sua 
cabeça na areia e finja que nada esta 
acontecendo.
● Ignora por completo o problema;
● Caso ocorra o deadlock (impasse), 
simplesmente reinicie o computador.
 
Detecção e Recuperação
● Nessa metodologia, os algoritmos não tentarão 
evitar o deadlock e sim tentará detectar e 
recuperar após a ocorrência.
 
Detecção de impasses com um recurso
● Essa situação é o caso mais simples, onde 
existem apenas um recurso de cada tipo
● Para esse sistema podemos construir um grafo 
de recursos 
● Haverá impasse se existir, no grafo, um ou 
mais ciclos. 
● Se não houver nenhum ciclo, não haverá 
impasses.
 
Detecção de impasses com um recurso
● Embora seja relativamente simples identificar ciclos no 
grafo, para aplicarmos em sistemas reais são necessários 
algoritmos de detecção de ciclos em grafos.
 
Detecção de impasses com um recurso
● A seguir veremos um algoritmo simples para detecção de 
ciclos:
– Para cada nó – N no grafo – execute os 5 passos 
seguintes, usando N como nó inicial
– Inicialize L, como uma lista vazia e assinale todos os 
arcos como demarcados
– Insira o nó atual no final da lista L e verifique se o nó 
agora aparece em L duas vezes. Em caso afirmativo, o 
grafo contem um ciclo e o algoritmo termina.
 
Detecção de impasses com um recurso
– A partir do referido nó, verifique se existe algum arco de 
saída desmarcado. Em caso de afirmativo, vá para o 
passo 5, do contrário vá para o passo 6
– Escolha aleatoriamente um arco de saída desmarcado 
e marque-o. Então, siga o arco para obter o novo nó 
atual e vá para o passo 3
– Se esse nó for inicial, o grafo não conterá ciclo algum e 
o algoritmo terminará. Senão, o final foi alcançado. 
Remova-o e volte para o nó anterior, isto é, aquele que 
era atual antes desse, marque-o como atual e vá para 
o passo 3
 
Detecção de impasses com um recurso
– O que esse algoritmo faz é tomar cada nó, um após o 
outro, como a raiz do que se espera ser uma árvore, e 
fazer uma busca do tipo depth-first. 
– Se tornar a passar por um nó já percorrido, isso 
significa que encontrou um ciclo.
 
Detecção de impasses com múltiplos 
recursos de cada tipo
● Quando existem várias cópias de algum recurso, é 
necessário um método diferente para detectar impasses.
● Uma metodologia interessante é a criação de matrizes de 
processos e recursos.
● Nessa metodologia temos 4 estruturas:
– E – vetor com a quantidade de recursos totais
– A – vetor de recursos disponíveis 
– C – matriz de alocação atual
– R – matriz de requisição
 
Detecção de impasses com múltiplos 
recursos de cada tipo
 
Recuperação de impasses 
● Suponha que o algoritmo de detecção de impasses 
funcione corretamente, o que devemos fazer em seguida?
● Podemos utilizar:
● Recuperação por meio de preempção
● Recuperação por meio de retrocesso
● Recuperação por meio de eliminação de processos
 
Recuperação por meio de preempção
● Essa metodologia retira um recurso de um processo e o 
entrega ao outro para depois devolve-lo ao primeiro, sem 
que o processo perceba
● Essa característica é chamada de preempção e é 
altamente dependente da natureza do recurso.
● Alguns recursos tornam essa operação muito difícil ou 
impossível.
 
Recuperação por meio de retrocesso
● Se os projetistas de sistemas e operadores de máquinas 
souberem da possibilidade de ocorrência de impasses, 
provavelmente poderão fazer com que os processos 
periodicamente gerem pontos de checagem (checkpoints)
● Uma vez criado os pontos de checagem, ao se detectar 
um possível deadlock, o sistema pode analisar a situação 
e voltar em um ponto anterior ao deadlock, realocando os 
recursos a outros processos. 
 
Recuperação por meio de eliminação de 
processos
● A maneira mais simples e grosseira de eliminar um 
deadlock é matar o processo e liberar os recursos que 
esse processo esta mantendo.
● Um outro modo é escolher um processo, não presente no 
ciclo, como vítima para a liberação de recursos, de forma, 
que esse processo possa contribuir para a liberação do 
deadlock
● Nesse caso, o sistema irá escolher cuidadosamente o 
processo que detêm recursos que possam contribuir para 
a eliminação do deadlock.
 
Evitando impasses
● Nesse caso, o SO deve analisar se a requisição de 
recursos de um processo pode levar a uma situação de 
impasse, caso seja positivo essa situação, ele não libera o 
recurso.
● Alguns algoritmos dessa metodologia:
– Trajetória de recursos
– Estados seguros e inseguros
– Algoritmo do banqueiro para um único recurso
– Algoritmo do banqueiro para múltiplos recursosTrajetória de recursos
● Nesse algoritmo, o SO plota um gráfico com os recursos 
disponíveis e os processos em execução.
● Conforme o escalonador de processos executa cada 
processo, ele vai marcando no gráfico a trajetória de 
alocação de recursos e os processos.
● Uma vez detectada a intersecção do gráfico, um possível 
deadlock pode ocorrer, e com essas informaçãos o SO 
pode ou não liberar o recurso.
 
Trajetória de recursos
 
Estados Seguros e Inseguros
● Esse algoritmo trabalha com 2 tipos de estados seguros e 
inseguros.
● Um estado é considerado seguro se ele não esta em 
situação de impasse e se existe alguma ordem de 
escalonamento na qual todo o processo possa ser 
executado até sua conclusão.
● Um estado inseguro podem provocar deadlocks, mas não 
necessariamente os provocam
 
Estados Seguros e Inseguros
 
Algortimo Banqueiro para um recurso
● Aloca o recurso e os processos que precisam desse 
recurso em uma matriz, tendo nessa matriz a quantidade 
máxima de recursos que o processo precisa e a 
quantidade de recursos que ele esta utilizando no 
momento.
● Esse algoritmo faz é verificar se a liberação de uma 
requisição é capaz de levar a um estado inseguro, sendo 
que em caso positivo, a requisição é negada. Caso 
contrário, a requisição é atendida.
 
Algortimo Banqueiro para um recurso
 
Algortimo Banqueiro com múltiplos recursos
● É uma generalização do algoritmo anterior, contudo, 
nesse modelo os vários recursos modelados em matrizes 
de recursos alocados e recursos ainda necessários.
● Apesar da maior complexidade deste algoritmo, ele 
consegue adminstrar os recursos evitando os deadlocks.
 
Algortimo Banqueiro com múltiplos recursos
E → R. Existente
P → R. Alocados
A → R. Disponíveis
 
Prevenção de Impasses
● Visto que evitar impasses é praticamente impossível, pois 
são necessárias informações futuras sobre as requisições 
● Uma alternativa é a prevenção de impasses através do 
ataque as condições que geram os impasses
● Esses ataques são:
– Atacando a condição de exclusão mútua
– Atacando a condição de posse e espera
– Atacando a condição de não preempção
– Atacando a condição de espera circular
 
Atacando a condição de exclusão mútua
● Para evitarmos a condição de exclusão mútua devemos 
primeiramente não permitir que um recurso seja alocado 
exclusivamente para um processo
● O problema desse sistema são os recursos que precisam 
de exclusividade para funcionarem corretamente, como 
por exemplo, as impressoras
● Possivel solução: a utilização de spoolers
 
Atacando a condição de posse e espera
● Esta condição condiz em evitar que processos, que já 
mantem um recurso em sua posse, fique aguardando por 
outros recursos
● Uma forma para atingir tal situação é fazer com que o 
processo requisitem todos os recursos que ele precisará 
para ser concluído antes de executar.
● Um problema encontrado é que muitos processos só tem 
conhecimento sobre os recursos necessários no momento 
de sua execução
 
Atacando a condição de não preempção
● Esta condição tem com principal função retomar a força 
um recurso que não seja preemptível
● O problema dessa situação é que se você interromper 
uma impressão, como por exemplo, e atribuirmos esse 
recurso a outro processo, teremos um problema na saída 
da impressora.
● Uma possível solução é a virtualização dos recursos, 
contudo, nem todos os recursos podem ser virtualizados 
 
Atacando a condição de espera circular
● Para restringirmos a condição de espera circular podemos criar 
uma regra que determina que um processo só tem permissão 
para possuir apenas um único recurso por vez.
● Outra maneira é numerar os recursos e gerar uma regra de 
que cada processo pode requisitar quantos recursos que 
precisar, contudo, essas requisições precisam seguir a ordem 
de numeração dos recursos
● Esse algoritmo poder ser aplicado a diversos processos, porém 
é impossível gerar uma ordenação que consiga suportar essa 
hierarquia.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38