Buscar

04-Processos-Part3

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 11 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 11 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 11 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

1 SO I – Cap. 3 1 SO I – Cap. 3 
3 Deadlock 
 
Elementos envolvidos: 
 Recursos de uso exclusivo; 
 O SO garante a um processo acesso exclusivo a um recurso; 
 Processos em geral precisam de mais de um recurso para suas 
atividades. 
 
Suponha que 2 processos, A e B, querem imprimir arquivos muito 
grandes de uma fita: 
 A requisita a impressora e obtém o controle dela; 
 B requisita a fita e obtém o controle dela; 
 A requisita a fita e bloqueia até que ela seja liberada; 
 B requisita a impressora e bloqueia até que ela seja liberada. 
 
Conclusão: A e B estão bloqueados, um esperando pelo outro, e 
assim permanecerão indefinidamente! 
Esta situação chama-se deadlock! 
 
Deadlocks podem ocorrer em outras situações além de dispositivos 
de I/O: 
 Num banco de dados, um programa precisa bloquear vários 
registros para uma transação; 
 O processo A pode bloquear o registro R1; 
 B pode bloquear o registro R2; 
 A pede o bloqueio do registro R2 e bloqueia até que ele seja 
liberado; 
 Então B pede o bloqueio de R1! 
 
3.1 Recursos 
 
 Recursos podem ser objetos de hardware, software e dados; 
 Alguns recursos podem ter várias instâncias (ex.: unidades de 
fita); 
 Cada unidade pode atender uma requisição! 
 Um recurso é qualquer coisa que pode ser usado por um único 
processo em um determinado instante. 
 
Tipos de recursos: 
 Preemptíveis: pode ser tirado do processo controlador sem 
problemas (ex.: memória); 
 Não preemptíveis: só pode ser entregue a outro processo 
quando o controlador liberar! 
 
 
 
Funcionamento de uma requisição: 
 Se o recurso está em uso, o processo é posto para dormir; 
 A requisição pode retornar um código de erro; 
2 SO I – Cap. 3 2 SO I – Cap. 3 
 Neste caso, o processo aguarda um pouco e tenta novamente; 
 Para todos os efeitos, o processo está bloqueado porque não 
pode produzir trabalho útil! 
3.2 Introdução a Deadlocks 
 
 
 
Definição: 
 Um conjunto de processos está em deadlock se cada processo do 
conjunto está esperando por um evento que apenas outro 
processo do conjunto pode causar! 
Como todos os processos estão esperando, nenhum deles pode 
causar o evento que pode liberar um dos outros! 
 
3.2.1 Condições para o deadlock 
 
Coffman (1971): 
1. Condição de exclusão mútua: 
 Um recurso está em uso por um processo ou está disponível! 
2. Condição de posse e espera: 
 Processos que têm a posse de um recurso podem pedir 
outros! 
3. Condição de não preempção: 
 Recursos possuídos por um processo não podem ser tirados 
para ser dados a outro! 
4. Condição de espera circular: 
 Deve haver uma cadeia circular entre os processos, cada um 
esperando por uma liberação de outro! 
 
3.2.2 Modelagem de deadlocks 
 
Holt (1972) propôs o uso de grafos dirigidos para modelar a 
ocorrência de deadlocks! 
 
 
3 SO I – Cap. 3 3 SO I – Cap. 3 
a) A tem a posse do recurso R; 
b) B está requisitando o recursos S; 
c) Deadlock entre C e D! 
 
Considere 3 processos com o seguinte comportamento: 
A: 
 Requisita R 
 Requisita S 
 Libera R 
 Libera S 
B: 
 Requisita S 
 Requisita T 
 Libera S 
 Libera T 
C: 
 Requisita T 
 Requisita R 
 Libera T 
 Libera R 
 
O SO pode decidir pela execução de qualquer dos processos, em 
uma ordem qualquer! 
 Ele pode decidir executar A até o fim, depois B e depois C! 
 Esta escolha não leva a deadlock, mas também não se aproveita 
o paralelismo quando um processo faz I/O; 
 Caso A, B e C não façam I/O, o melhor método é o do Menor 
Job Primeiro!!! 
 
 
Execução com Round Robin: 
 
 
4 SO I – Cap. 3 4 SO I – Cap. 3 
O SO pode determinar que um deadlock pode ocorrer e escolher 
uma ordem determinada para evitá-lo (ex.: não escolher B para 
execução). 
 
Estratégias para tratar deadlocks: 
1. Apenas ignorar o problema; 
2. Detecção e recuperação; 
3. Evitar dinamicamente ao fazer alocação de recursos 
cautelosamente; 
4. Prevenção, ao negar estruturalmente uma das 4 condições 
necessárias! 
 
3.3 Algoritmo Ostrich 
 
Solução do avestruz: enfiar a cabeça na areia e fingir que o problema 
não existe! 
Adotada pelo UNIX!!! 
 É melhor deixar um deadlock acontecer eventualmente do que 
impor restrições aos usuários para evitá-lo! 
 
Possíveis deadlocks no UNIX: 
 A tabela de processos tem um número máximo de entradas; 
 Se todos os processos ativos decidirem fazer forks, é possível 
que a tabela encha e não possa receber mais processos; 
 Os processos que receberem falhas no fork podem esperar 
um tempo e tentar de novo; 
 Assim, não liberam as entradas que permitiriam aos demais 
encerrar! 
 
 Da mesma forma, há limites para o número de arquivos abertos; 
 Outro recurso finito é a área de swap em disco! 
 
3.4 Detecção de deadlock e recuperação 
 
Tratamento: 
 O sistema não tenta evitar que deadlocks aconteçam; 
 Ele deixa que ocorram, tenta detectá-los e então tenta recuperá-
los. 
 
3.4.1 Detecção de deadlocks com um recurso de cada tipo 
 
 
 
Ex.: o sistema possui 1 impressora, 1 fita, 1 plotter (por enquanto, 
sistemas com 2 impressoras não serão considerados). 
 
Para detectar deadlocks neste caso, basta montar o grafo dirigido 
proposto por Holt (6.2.2). 
5 SO I – Cap. 3 5 SO I – Cap. 3 
 
Ex.: 
1. A controla R e requisita S; 
2. B requisita T; 
3. C requisita S; 
4. D controla U e requisita S e T; 
5. E controla T e requisita V; 
6. F controla W e requisita S; 
7. G controla V e requisita U. 
 
Neste caso, o sistema recupera o deadlock terminando um dos 
processos envolvidos. Se não resolver, termina outro! 
 
3.4.2 Detecção de deadlocks com múltiplos recursos de cada tipo 
 
Algoritmo baseado em matrizes para detectar deadlocks entre n 
processos, P1 a Pn: 
 m - número de classes de recursos; 
 Ei - número de recursos da classe i (1 i m); 
 E - vetor dos recursos existentes; 
 Ex.: classe 1 é a de unidades de fita - E1 = 2 significa que há 
2 unidades de fita; 
 A - vetor de recursos disponíveis; 
 Ai - número de instâncias disponíveis do recursos i; 
 Ex.: A1 = 2 significa que as 2 fitas estão disponíveis; 
 C - matriz de alocação atual; 
 Cij - número de instâncias do recurso j que o processo i 
possui; 
 R - matriz de requisições; 
 Rij - número de instâncias do recurso j que o processo i quer. 
 
Invariante que ocorre para essas 4 estruturas de dados: 
 Todo recurso está alocado ou disponível; 
 
m 
 Cij + Aj = Ej 
i=1 
 
O algoritmo de detecção é baseado na comparação de vetores: 
 A B  i (0 i m, Ai Bi ) 
 
Cada processo é dito inicialmente não marcado. 
É preciso procurar pelos processos que podem terminar. 
 
Algoritmo de detecção de deadlock: 
1. Procurar por um processo não marcado, Pi, para o qual Rin < A; 
2. Se houver, fazer A = * + Cin, marcar o processo e vai para 1; 
3. Se não houver, o algoritmo termina. 
 
Ex.: 3 processos 
Recursos existentes: E = (4 2 3 1) 
 CDs 
 Impressoras 
 Plotters 
 Fitas 
 
Recursos disponíveis: A = (2 1 0 0) 
 
 
 
6 SO I – Cap. 3 6 SO I – Cap. 3 
Matriz de Alocação: 
 
 0 0 1 0 
C = 2 0 0 1 
 0 1 2 0 
 
 
Matriz de Requisição: 
 
 2 0 0 1 
R = 1 0 1 0 
 2 1 0 0 
 
 
Procurando por um processo que pode encerrar: 
 A linha 1 de R é maior que A; 
 A linha 2 de R é maior que A; 
 A linha 3 de R é igual a A! 
 
O processo 3 pode executar e terminar, quando seus recursos (C3n) 
voltam para a relação de disponíveis. 
 
A = (2 2 2 0) 
 
Com essa situação, o processo 2 pode encerrar: 
 
A = (4 2 2 1) 
 
Assim, o processo 3 pode terminar também. 
 
3.4.3 Recuperação de deadlock 
 
Após detectar que um deadlock ocorreu, o que fazer? Há alguns 
métodos, nenhum deles muito agradável. 
 
Recuperação através de preempção 
 
O operador pode, p. ex.: 
 Suspender um processo que está imprimindo (o material 
impressoaté o momento é separado); 
 A impressora é dada para outro processo; 
 Quando o 2º terminar, a impressora é dada outra vez patra o 1º. 
 
Não é em qualquer situação que isto pode ser feito! 
 
Recuperação por Rollback 
 
O sistema permite que os processos tenham pontos de checkpoint: 
 Em certos instantes, todo o estado do processo (incluindo 
eventuais arquivos gravados e atualizações em bancos de dados) 
é gravado em um arquivo; 
 Um checkpoint não sobrescreve os anteriores; 
 Quando um deadlock é detectado, é fácil ver qual recurso é 
necessário para encerrar o círculo; 
 O processo que possuir este recurso tem seu estado retornado 
para um ponto antes de adquiri-lo; 
 Todo o trabalho feito depois deste ponto é perdido! 
 
Pode implicar em desfazer outros processos também! 
 
7 SO I – Cap. 3 7 SO I – Cap. 3 
Recuperação por encerramento de processos 
 
Forma mais simples de tratar o problema: 
 Um processo é encerrado; 
 Suas requisições são canceladas e os recursos possuídos tornam-
se disponíveis; 
 Com sorte, o ciclo é quebrado e os demais podem encerrar; 
 Se isso não ocorrer, outro processo é escolhido. 
3.5 Evitando Deadlocks 
 
O sistema deve ter condições de decidir quando uma requisição de 
recurso pode ou não ser atendida. 
 
3.5.1 Trajetória de recursos 
 
 
3.5.2 Estados Seguros e Inseguros 
 
A informação necessária para determinar estados seguros e 
inseguros é baseada no sistema proposto em 6.4.2 (matrizes E - 
recursos existentes, A - recursos disponíveis, C - alocação de 
recursos pelos processos e R - requisições pendentes). 
 
Um estado é seguro se: não há deadlock e os processos podem ser 
executados em uma ordem em que todos possam encerrar sem 
deadlock. 
 
Considere uma situação com 10 unidades de um recurso qualquer e 
3 processos: 
 
 Tem Máximo 
A 3 9 
B 2 4 
C 2 7 
 
Este estado é seguro porque existe uma seqüência que permite a 
todos os processos terminarem. Com 7 recursos de um total de 10, o 
escalonador pode fazer com que B execute exclusivamente. 
Eventualmente, B pode requisitar 2 recursos e terminar: 
 
 Tem Máximo 
A 3 9 
B 0 - 
C 2 7 
 
8 SO I – Cap. 3 8 SO I – Cap. 3 
Agora, há 5 recursos disponíveis. O escalonador pode executa C 
exclusivo. Eventualmente, C pode requisitar 5 unidades e terminar: 
 
 Tem Máximo 
A 3 9 
B 0 - 
C 0 - 
 
Agora, há 7 recursos sobrando. Finalmente, A pode requisitar 6 e 
encerrar! 
 
Agora, suponha que na posição inicial A faz mais uma requisição: 
 
 Tem Máximo 
A 4 9 
B 2 4 
C 2 7 
 
Neste caso, com 2 recursos disponíveis B pode requisitar 2 e 
encerrar: 
 
 Tem Máximo 
A 4 9 
B 0 - 
C 2 7 
 
Agora, com 4 recursos disponíveis nem A nem B podem encerrar. 
Portanto, o estado inicial é inseguro. Eventualmente, pode levar a 
um deadlock. 
 
3.5.3 O algoritmo do Banqueiro (um recurso) 
 
 Dijkstra, 1965; 
 Funciona como o gerente de banco de uma cidade pequena. 
 
Ex.: 
 Tem Máximo 
A 0 6 
B 0 5 
C 0 4 
D 0 7 
 
Neste caso, há crédito de 22 recursos para os 4 processos. Mas o 
gerente sabe que os processos não vão requisitar todos os seus 
recursos ao mesmo tempo. Assim, ele libera um total de 10 para 
todos os processos. Depois de algumas requisições, chega-se ao 
estado: 
 
 Tem Máximo 
A 1 6 
B 1 5 
C 2 4 
D 4 7 
 
Este estado é seguro porque, com 2 recursos disponíveis, C pode 
encerrar, liberando 4 recursos. Depois, B e D podem encerrar e, 
finalmente, A encerra. 
 
Considere que B faz mais uma requisição: 
 
9 SO I – Cap. 3 9 SO I – Cap. 3 
 Tem Máximo 
A 1 6 
B 2 5 
C 2 4 
D 4 7 
 
Neste caso, temos um estado inseguro porque o SO não pode atender 
o número máximo de requisições de nenhum processo. 
 
3.5.4 Algoritmo do Banqueiro (múltiplos recursos) 
 
Considere a situação inicial de recursos assinalados: 
 
 Fitas Plotters Impress CDs 
A 3 0 1 1 
B 0 1 0 0 
C 1 1 1 0 
D 1 1 0 1 
E 0 0 0 0 
P 5 3 2 2 
 
A linha P representa o total de recursos alocados. 
Os 5 processos ainda têm a seguinte matriz de necessidades: 
 
 Fitas Plotters Impress CDs 
A 1 1 0 0 
B 0 1 1 2 
C 3 1 0 0 
D 0 0 1 0 
E 2 1 1 0 
Além disso, a matriz de recursos existentes é E = (6342). 
 
Finalmente, os recursos disponíveis: A = (1020). 
 
Este estado é seguro: 
 D pode encerrar  A = (2121); 
 A pode encerrar  A = (5132); 
 B pode encerrar  A = (5232); 
 C pode encerrar  A = (6342); 
 E pode encerrar  A = (6342). 
 
Após a publicação do trabalho de Dijkstra, houve muitas referências 
sobre ele em livros, artigos, etc. 
Infelizmente, apesar de ser excelente, na prática ele é inútil porque 
os processos raramente sabem com antecedência o máximo de 
recursos que utilizarão. 
 
Além disso, o número de processos varia dinamicamente. 
 
Por fim, recursos que constam como disponíveis podem desaparecer 
(uma unidade pode dar defeito!). 
 
3.6 Prevenção de deadlock 
 
Evitar deadlocks é impossível, porque isso depende de 
conhecimento que ainda não existe. Por outro lado, deadlocks 
podem ser prevenidos se for possível evitar pelo uma das condições 
necessárias. 
 
10 SO I – Cap. 3 10 SO I – Cap. 3 
3.6.1 Atacando a condição de exclusão mútua 
 
O uso de spool permite que vários processos possam gerar I/O para o 
mesmo recurso. 
 
Porém, nem todos os recursos podem ter spool. P. ex.: a tabela de 
processos não admite spool. 
 
Além disso, o uso de spool pode levar à competição por espaço em 
disco. 
 
3.6.2 Atacando a condição de posse e espera 
 
Se for possível prevenir processos que já controlam recursos de 
solicitar mais, deadlocks podem ser eliminados. 
Como fazer isso? 
 Todos os recursos devem ser alocados de uma vez. 
 Assim, o processo só executa se todos os recursos que ele 
precisa estiverem disponíveis; 
 A falta de um faz com que o processo entre em wait. 
 
Problema: 
 Os processo, em geral, não sabem quantos recursos vão 
necessitar; 
 Se soubessem, o algoritmo do banqueiro poderia ser usado. 
 Outro ponto: leva ao desperdício de recursos. 
 
3.6.3 Atacando a condição de não preempção 
 
Problema para determinados recursos (impressoras, etc.). 
3.6.4 Atacando a condição de espera circular 
 
Possíveis soluções: 
 Um processo só pode manter 1 recurso; 
 Se precisar de outro, tem que liberar o primeiro. 
 
Problema: impõem restrições ao funcionamento dos processos. 
 
 Os recursos podem ser numerados; 
 A requisição só pode ser feita em ordem crescente. 
 
Problemas: 
 Leva ao desperdício de recursos; 
 Há recursos que não podem ser numerados (tabela de processos, 
espaço em disco, registros de bancos de dados, etc.). 
 
3.7 Outras questões 
 
3.7.1 Bloqueio em 2 fases 
 
Muito usado em bancos de dados: 
 Um processo pretende atualizar vários registros; 
 Ele tenta bloquear todos eles; 
 Se conseguir, atualiza os registros e libera-os no final; 
 Se não conseguir, libera todos os registros já bloqueados e tenta 
novamente. 
 
Não é aceitável em algumas situações (ex.: sistemas de tempo real). 
 
11 SO I – Cap. 3 11 SO I – Cap. 3 
3.7.2 Deadlocks sobre não recursos 
 
Ex.: semáforos! Numa situação com um semáforo Mutex e algum 
outro, a ordem errada pode levar a deadlocks. 
 
3.7.3 Starvation 
 
Uma possibilidade com impressoras é entregar o recurso para o 
processo que vai imprimir o menor arquivo: 
 Maximiza o número de arquivos impressos; 
 Aumenta o número de usuários felizes! 
 
Num sistema carregado, o processo que quiser imprimir um arquivo 
grande não será selecionado enquanto houver outros processos com 
arquivos pequenos. 
 
Solução: eventualmente adotar FIFO.

Materiais relacionados

Perguntas relacionadas

Materiais recentes

Perguntas Recentes