Upload
internet
View
116
Download
1
Embed Size (px)
Citation preview
Deadlocks - Impasses
Capítulo 6
6.1. Recurso 6.2. Introdução aos impasses 6.3. Algoritmo do avestruz 6.4. Detecção e recuperação de impasses 6.5. Evitando impasses 6.6. Prevenção de impasses 6.7. Outras questões
Recursos
Exemplos de recursos de computador impressoras unidades de fita Tabelas
Processos precisam de acesso aos recursos numa ordem racional
Suponha que um processo detenha o recurso R1 e solicite o recurso R2 e ao mesmo tempo, outro processo detém R2 e solicita R1 Ambos são bloqueados e assim permanecem
Recursos (1)
Recurso: objeto acessado (dispositivo, trecho de informação como registro em base de dados). Pode ser adquirido, usado e liberado.
Recursos preemptíveispodem ser retirados de um processo sem quaisquer
efeitos prejudiciais. Ex: memória – se processo for retirado da memória, depois volta e continua processamento.
Recursos não preemptíveisOs que em geral são envolvidos em deadlockvão induzir o processo a falhar se forem retirados.
Ex: se gravador de CD for retirado do processo pode resultar em danos no CD sendo gravado.
Recursos (2)
Seqüência de eventos necessários ao uso de um recurso
1. solicitar o recurso
2. usar o recurso
3. liberar o recurso
Processo deve esperar se solicitação é negada processo solicitante pode ser bloqueado, ou pode
falhar resultando em um código de erro tratado como espera ociosa
A forma de solicitação depende do sistema
Aquisição de recursos (1)
Semáforos podem ser usados para gerenciar os recursos. Um único processo protegendo um ou dois recursos:
Aquisição de recursos (2)
Semáforos com dois processos A e B
Introdução aos Impasses
Definição formal:Um conjunto de processos está em situação de impasse se todo processo pertencente ao conjunto estiver esperando por um evento que somente um outro processo desse mesmo conjunto poderá fazer acontecer
Normalmente o evento é a liberação de um recurso atualmente retido
Nenhum dos processos pode... executar liberar recursos ser acordado
Quatro Condições para ocorrer Impasse
1.Condição de exclusão mútua• Em determinado instante, cada recurso ou está associado
a um único processo ou está disponível;
2.Condição de posse e espera• processos que retêm recursos concedidos podem solicitar
novos recursos;
3.Condição de não preempção• recursos concedidos previamente não podem ser
forçosamente tomados, devem ser explicitamente liberados pelo processo que os retém;
4.Condição de espera circular• deve existir uma cadeia circular de 2 ou mais processos• cada um está à espera de recurso retido pelo membro
seguinte dessa cadeia
Modelagem de Deadlock (1)
Deadlocks podem ser modelados com grafos dirigidos
Círculo: processo Quadrado: recurso
a) recurso R alocado ao processo Ab) processo B está solicitando/esperando pelo recurso Sc) processos C e D estão em deadlock sobre recursos T e U
Modelagem de Deadlock (2)
(a)-(c) Processos A,B e C fazem requisições e liberações(d) – uma possível ordem de execução determinada pelo escalonador.(e)-(g) grafo resultante dos passos 1 a 3
Modelagem de Deadlock (3)
O ciclo indicativo de impasse
(h)-(j) Grafo resultante dos passos 4 a 6
Modelagem de Deadlock (4)
Como poderia ser evitado o impasse: se o SO soubesse do impasse iminente, poderia suspender o processo B ao requisitar S, deixar A e C executarem ((l) a (q)) e voltar depois.
Modelagem de Deadlock (5)
Estratégias usadas para tratar Deadlocks
1. Ignorar por completo o problema;
2. Detecção e recuperação;
3. Evitando impasses:Anulação dinâmica por meio de uma alocação cuidadosa de recursos;
4. Prevenção:• negação de uma das quatro condições
necessárias;
Examinaremos cada possibilidade
Estratégia 1: Algoritmo do Avestruz
Enterre cabeça na areia e finja que o problema não existe
Engenheiros acham isto razoável se deadlocks ocorrem muito raramente custo da prevenção é alto
(matemáticos acham inaceitável)
UNIX e Windows seguem esta abordagem: ponderar entre conveniência e correção
Estratégia 2:Detecção com um Recurso de Cada Tipo
Observe a posse e solicitações de recursos Um ciclo pode ser encontrado dentro do grafo, denotando
deadlock: necessário algoritmo de detecção de ciclos em grafos dirigidos (alg no livro – pg 275).
Sistema com 7 processos (A a G) e 6 recursos (R a w)
Estratégia 2: Detecção com Múltiplos Recursos de Cada Tipo
Método para qdo há várias cópias de algum recurso.Ex: Há 2 impressoras, 3 leitoras de fita, e 2 scanners.Há n processos, m classes de recursos. Ei : recursos existentes da classe i; Ai : instâncias do recurso i disponíveis no instante.Cij : número de instâncias do recurso j alocadas ao processo iRij : número de instâncias do recurso j requeridas pelo proces. i
Estratégia 2: Algoritmo de detecção - Premissas
Condição: ou o recurso está alocado ou está disponível.
n
Cij + Aj = Ej
i=1
O algoritmo se baseia em comparação de vetores:A B se e somente se Ai Bi para 1 i m.
Inicialmente todos os processos estão desmarcados. A medida que o algoritmo prossegue, os processos são marcados indicando que estão aptos a completar processamento sem deadlock. No fim, os que permaneceram desmarcados estarão em deadlock.
Estratégia 2: Algoritmo de Detecção
Supõe que todos os processos manterão os recursos que adquirirem até que terminem.
1. Procure um processo desmarcado, Pi, para o qual a i-ésima linha de R seja menor ou igual à correspondente de A;
2. Se esse processo for encontrado, adicione a i-ésima linha de C à correspondente de A, marque o processo e volte para o passo 1;
3. Se não existir este processo, o algoritmo terminará.
Quando o algoritmo terminar todos os processos desmarcados, caso existam, estarão em situação de deadlock
Exemplo do Algoritmo de Detecção
3 processos e 4 classes de recursos.
P1 e P2 não podem ser satisfeitos, mas P3 pode, executa e devolve
recursos: A=(2 2 2 0). Agora P2 pode ser executado, ao fim devolve
recursos A= (4 2 2 1). P1 pode executar.
Detecção de Deadlock
Quando rodar este algoritmo? Toda vez que uma requisição de recurso for feita:
detecta logo, mas gasta CPU demais na detecção;
A cada k minutos;
Sempre que uso de CPU abaixo de certo limiar: quando muitos processos estiverem em situação de impasse, restarão poucos processos aptos a continuar a execução, neste caso a CPU estará abaixo de certo limiar
Recuperação de Deadlock (1)
Suponha que um deadlock foi localizado. Tentemos recuperar o sistema.
Recuperação através de preempção retirar um recurso de algum outro processo depende da natureza do recurso
Recuperação através de reversão de estado verifica um processo periodicamente (checkpoints), salva
o estado; verifica o recurso que é necessário e que processo tem o
recurso; usa o estado salvo para reverter este processo em um
instante anterior ao que adquiriu o recurso. Tudo que foi feito deste ponto em diante, é perdido.
Recuperação de Deadlock (2)
Recuperação através da eliminação de processos forma mais grosseira mas também mais simples de
quebrar um deadlock elimina um dos processos no ciclo de deadlock os outros processos conseguem seus recursos escolher para matar processo que possa ser
reexecutado desde seu início, ou seja, a execução corrente não influencia a próxima execução. Ex: matar um compilador implica em recomeçar a compilação sem efeitos colaterais.
Estratégia 3: Evitando Deadlocks Trajetórias de Recursos
Os recursos são requisitados um de cada vez.
Eixo x: instruções executadas por A; Eixo y executadas por B.
Em I1, A requisita impressora, em I2 requisita plotter, libera-os em I3 e I4. Até q, A executou e B não. Em q escalonador escolheu B, em r escolheu A, em s escolheu B.
Evitando Deadlocks - Trajetórias de Recursos
Diagonais a direita: ambos têm impressora. Diagonais a esquerda: ambos têm plotter: impossível – não entrar aí. Em t, B requisita plotter. Conceder ou não? Ao entrar neste quadrado fatalmente entrará em impasse.
Seguro: execute A até I4, a partir daí qq trajetória é segura até u.
Estados Seguros e Inseguros (1)
Demonstração de que o estado em (a) é seguro: Processo A possui 3 instâncias de recurso e pode precisar de até 9, etc. Existe uma sequencia de alocações que permite que todos os processos sejam concluídos.
A alocação deve ser feita quando é segura.
Estados Seguros e Inseguros (2)
Demonstração de que o estado em (b) é inseguro:
Suponha que a partir de (a), A requisitou e obteve um recurso. Há uma sequencia que funcione?
Se A liberar um recurso, C poderá executar e não acontecerá o deadlock, ou seja, estado inseguro pode não ser deadlock, mas não há garantia.
O Algoritmo do Banqueiro para um Único Recurso
Três estados de alocação de recursosa) Segurob) Seguro (C-> B ou C-> D-> A...)c) Inseguro (De (b) para (c) atendeu uma requisição de B e
agora já não consegue atender ninguém.
Banqueiro libera linhas de crédito. Verificar se liberação leva a estado inseguro, e então não será atendida. Em (a) precisaria 22 créditos para atender todos, porém só tem em caixa 10 unidades.
Prevenção de Deadlock
Se evitar é praticamente impossível pois requer informações acerca de requisições futuras, pode-se tentar atacar as quatro condições estabelecidas por Coffman:
1. Condição de exclusão mútua
2. Condição de posse e espera
3. Condição de não preempção
4. Condição de espera circular
Se uma destas condições não for satisfeita, impasses serão estruturalmente impossíveis.
Prevenção de Deadlock Atacando a Condição (1) Exclusão Mútua (pouco promissora…)
Deixe usarem recurso sem exclusividade! Alguns dispositivos (como uma impressora) que exigem exclusividade podem fazer uso de spool o daemon de impressão é o único que realmente usa o
recurso impressora, desta forma deadlock envolvendo a impressora é eliminado
Não totalmente seguro, pois ainda pode haver impasse com o espaço compartilhado dedicado ao spool. Ex: 2 processos estão “simultaneamente” preenchendo a área que pode se esgotar sem os dois concluirem e ambos não podem prosseguir…)
Princípios: (1) evitar alocar um recurso quando ele não for absolutamente necessário; (2) tentar assegurar que o menor número possível de processos possa de fato requisitar o recurso
Prevenção de Deadlock Atacando a Condição (2) Posse e Espera
Exigir que todos os processos requisitem os recursos antes de iniciarem: se tudo estiver disponível, executa. um processo lê em um unidade de fita, e uma hora depois escreve
em outra unidade de fita: bloqueio ineficiente.
Problemas podem não saber quantos e quais recursos vão precisar no início da
execução ( se soubesse usariam alg. do banqueiro) e também retêm recursos que outros processos poderiam estar
usando.
(Há sistemas em lote que na primeira linha declaram todos os recursos) Variação:
processo que requisitar recurso deve desistir de todos os outros que estão em sua posse; a seguir requisitar todos os que são imediatamente necessários
Prevenção de Deadlock Atacando a Condição (3) Não Preempção
Considere um processo de posse de uma impressora no meio da impressão retoma a impressora a força !!??
Virtualização: possível em algumas situações: armazenar saída da impressora em disco evita impasse.
Nem todos os recursos podem ser virtualizados; ex: registros de banco de dados devem ser travados para uso.
Prevenção de Deadlock Atacando a Condição (4) Espera Circular (1)
a) Recursos ordenados numericamente, requisições devem ser feitas em ordem numérica;
b) Um grafo de recursos; com esta regra não há ciclo: ou A não pode requisitar j ou B não pode requisitar i.
Problema: não há uma ordem que satisfaça a todos.
Gera saída em alta resolução de imagens para filmes.
Prevenção de Deadlock
Resumo das abordagens para prevenir deadlock