Estratégias para Lidar com Impasses em Sistemas Operacionais

Prévia do material em texto

1 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
Estratégicas para lidar com impasses 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
1. O Algoritmo do Avestruz 
Ø  Característica do Avestruz: 
o  Enfia a cabeça na areia e finge que nada está acontecendo. 
Ø  Reações diversas: 
o  Matemáticos – consideram totalmente inaceitável e dizem que impasses 
devem ser evitados a qualquer custo. 
o  Engenheiros – perguntam sobre a freqüência esperada do problema, 
das quedas de sistema por outras razões e sobre a gravidade do 
impasse. 
§  Impasse ocorressem em média um a cada 50 anos e; 
§  Quedas do sistema devida a falha de hardware, erros e bugs ocorressem uma vez por mês. 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
1. O Algoritmo do Avestruz 
Ø  Supor a situação no UNIX: 
o  Tem 100 entradas de processos; 
o  10 programas estão executando, cada um dos quais necessita 
criar 12 processos. 
o  Depois que cada um cria 9 processos, esgota-se as entradas na 
tabela; 
o  Cada um dos 10 processos fica num laço de criação e falha 
(IMPASSE). 
o  Deveríamos abandonar processos e a chamada FORK para 
eliminar o problema???? 
2 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
1. O Algoritmo do Avestruz 
Ø  Em suma: 
o  O sistema UNIX possui uma abordagem simplesmente de ignorar 
o problema na suposição de que a maioria dos usuários 
preferiria um impasse ocasional do que uma regra que 
restringisse todos os usuários a um processo ou a um arquivo 
aberto. 
o  Entra numa negociação desagradável entre conveniência e 
correção. 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
2. Detecção e Recuperação 
Ø  O sistema monitora as solicitações e as liberações dos 
recursos. 
Ø  Cada vez que um recurso é solicitado ou liberado: 
o  Se existir um ciclo – um dos processos do ciclo é eliminado. 
o  Se não quebrar o impasse, outro é eliminado e assim por diante. 
Ø  Estratégica freqüentemente utilizado em grandes 
computadores mainframes. 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
3. Prevenção de Impasses 
Ø  A terceira estratégia é impor restrições convenientes 
para os processos de tal modo que os impassem sejam 
estruturalmente impossíveis. 
Ø  Baseada nas quatros condições declaradas por Coffman 
(1971): 
o  Assegurando que pelo menos uma dessas condições nunca seja 
satisfeita, naturalmente os impasses serão impossíveis. 
3 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
3. Prevenção de Impasses 
Ø  1. Condição de exclusão mútua: 
o  Se nenhum recurso fosse atribuído exclusivamente a um processo, 
nunca teríamos impasses. 
o  Porém, alocar a impressora para dois processos ao mesmo tempo seria 
um terror e caos. 
o  Para solucionar o problema da impressora, podemos fazer spool da 
saída da impressora e um único processo fosse capaz de solicitar a 
impressora (daemon). 
o  Porém, nem todo dispositivo de E/S pode ser realizado spool. 
o  Além disso, se dois processos ocupasse metade do espaço para spool 
com saída e nenhum terminasse. Assim, nenhum processo jamais 
terminaria, ocasionando um impasse. 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
3. Prevenção de Impasses 
Ø  2. Condição de segura e espera: 
o  Se fosse possível prevenir que processos que seguram recursos 
esperem mais recursos, poderíamos evitar um impasse. 
o  Solução: exigir que todos os processos solicitem todos os seus 
recursos antes de iniciar sua execução. 
§  Se tudo tiver disponível, o processo poderia ser alocado e executado até sua 
conclusão. 
§  Se um ou mais recursos estivem ocupados, o processo esperaria. 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
3. Prevenção de Impasses 
Ø  2. Condição de segura e espera: 
o  Problema imediato: muitos processos só irão saber dos 
recursos necessários após o início de sua execução. 
o  Outro problema: os recursos seriam mal utilizados com essa 
abordagem: 
§  Processo que lê dados, analisa por horas e grava e plota. 
4 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
3. Prevenção de Impasses 
Ø  3. condição de nenhuma preempção: 
o  Opção menos promissora. 
o  Imagine um processo que obteve acesso a impressão. 
o  Tirar à força a impressora do processo no meio da impressão 
não seria nada agradável. 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
3. Prevenção de Impasses 
Ø  4. condição de espera circular: A espera circular pode 
ser eliminada de várias maneiras: 
o  Um processo é destinado a apenas um recurso em qualquer 
momento. Se precisar de outro, precisa liberar o primeiro. 
§  Processo que precisa copiar um arquivo enorme de uma fita para a impressora, 
essa restrição é inaceitável. 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
3. Prevenção de Impasses 
o  Outra forma é oferecer um numeração global de todos os 
recursos: a regra é que processos podem solicitar recursos 
sempre que quiserem, mas todas as solicitações devem ser 
feitos em ordem numérica. 
§  Para caso de dois processos: 
–  i e j recursos distintos. 
–  Se i>j, então A não pode 
 solicitar j. 
–  Se j>i, então B não pode 
 solicitar i. 
–  O impasse torna-se impossível. 
§  Variação desse algoritmo é que o 
 processo não pode solicitar recursos 
 mais baixos. 
5 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
4. Impedimento de Impasses 
Ø  Há um algoritmo que pode evitar impasses fazendo a 
escolha certa da solicitação de recursos. 
Ø  A resposta é sim, mas é necessário certas informações 
de antemão. 
Ø  Evitar impasses mediante a alocação cuidadosa de 
recursos. 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
4. Impedimento de Impasses 
Ø  Algoritmo de agendamento do banqueiro para um único 
recurso, proposto por Dijkstra (1965): 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
4. Impedimento de Impasses 
Ø  Trajetória de recursos: 
6 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
4. Impedimento de Impasses 
Ø  Algoritmo do Banqueiro para Múltiplos Recursos 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
Outras Questões 
Ø  Outras questões podem ser levantadas sobre impasses: 
o  Bloqueio em duas fases (two-phase locking); 
o  Deadlocks que não envolvem recursos; 
o  Condição de inanição (starvation). 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
Bloqueio em duas fases (two-phase locking) 
Ø  Apesar de não existir uma solução genérica utilizando 
os meios para evitar e prevenir deadlocks, para 
aplicações específicas existem excelentes algoritmos. 
o  Banco de dados – os bloqueios. 
Ø  Porém, quando muitos processos estão sendo 
executados simultaneamente, o perigo de deadlock é 
enorme. 
o  Para isso existe o bloqueio em duas fases. 
7 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
Bloqueio em duas fases (two-phase locking) 
Ø  Na primeira fase: 
o  Processa tenta bloquear os registros de que precisa, um por um; 
o  Se conseguir, é iniciado a segunda fase, no qual o processo 
executa suas atividades e libera os registros bloqueados. 
o  Se existir algum bloqueio, o processo liberará todos os registros 
por ele já bloqueados e começa novamente a primeira fase. 
o  Idênticos ao processo de requisição de recursos, visto 
anteriormente. 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
Deadlocks que não envolvem recursos 
Ø  Existem situações deadlocks que acontecem sem a 
existência de recursos: 
o  Por exemplo, dois processos ficarem em situação de deadlock 
devido ao fato de cada um precisar esperar que o outro faça 
algo. 
o  Acontece muito com semáforos. 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
Condição de inanição (starvation) 
Ø  Em sistemas dinâmicos, requisições por recursos 
acontecem o tempo todo. 
Ø  É necessário políticas quem tomem decisões sobre 
quem consegue qual recurso e quando. 
Ø  Essa política pode fazer que algunsprocessos nunca 
obtenham o serviço, embora não estejam em situação de 
deadlock. 
o  Exemplo: alocação da impressora baseada numa política para 
evitar deadlock. 
o  Política: ceder a impressora ao processo com menor arquivo a 
ser impresso. 
8 
Sistemas Operacionais I DIE/CCN/UFPI Erico Meneses Leão 
Condição de inanição (starvation) 
o  Se o sistema for muito dinâmico, com muitos processos com 
pequenos arquivo, um processo com arquivo grande pode 
nunca ter a impressora. 
o  Ele será desprezado indefinidamente, ainda que não esteja 
bloqueado, levando o processo a uma condição de inanição. 
Prof. M.Sc. Erico Meneses Leão 
ericoleao@ufpi.edu.br 
http://www.ufpi.br/eml 
Sistemas Operacionais 
Dispositivos de Entrada/Saída 
UNIVERSIDADE FEDERAL DO PIAUÍ - UFPI 
DEPARTAMENTO DE INFORMÁTICA E ESTATÍSTICA - DIE 
.: BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO :.