Resumo - P2 SO - Aula 22 e Cap 6 - Impasses e Recursos

Prévia do material em texto

Legenda: Já caiu em P2 anterior. | Pode ser interessante estudar 
- Foquem no Capítulo 4 e 5, pois ele disse que do 6 só vai cair uma questão, mas sugiro não 
deixar de estudá-lo. Os que não estão marcados em nada não quer dizer que não pode cair, 
então estudem da maneira como acharem melhor. 
Aula 22 – Recursos e Impasses 
Recursos Preemptíveis - São aqueles que podem ser retirados de um processo sem 
causar prejuízo. Ex: memória, onde as páginas podem ser enviadas para o disco e 
recuperadas posteriormente. A preempção pode ser usada para resolver impasses, 
realocando recursos de um processo para outro. 
Recursos Não Preemptíveis - Não podem ser retirados do proprietário ou 
processo sem potencialmente causar uma falha. Ex: gravadores Blu-ray, onde retirar 
abruptamente pode resultar em problemas. Geralmente, impasses envolvem recursos não 
preemptíveis. 
Sequência de Eventos para Uso de Recurso - Um processo expressa a necessidade de um 
recurso -> após obtê-lo, processo realiza suas operações necessárias -> após concluir o uso, 
processo libera o recurso para que outros processos possam utilizá-lo 
Tratamento de Falhas na Solicitação de Recurso - Se o recurso não está 
disponível quando solicitado, o processo que o requisita é forçado a esperar, e em alguns 
SOs, é automaticamente bloqueado e despertado quando o recurso está disponível. 
Condições para Ocorrência de Impasses - Condição de Exclusão 
Mútua: Cada recurso está atualmente associado a exatamente um processo ou está 
disponível. Solução para Evitá-la: Alocar recursos de maneira que a exclusão mútua não 
ocorra. 
Condição de Posse e Espera: Processos atualmente de posse de recursos que foram 
concedidos antes podem solicitar novos recursos. Solução para Evitá-la: Exigir que os 
processos solicitem todos os recursos necessários antes de iniciar a execução. Porém, pode 
ser impraticável se os processos não souberem quantos recursos precisarão com 
antecedência. 
Condição de Não Preempção: Recursos concedidos antes não podem ser tomados à 
força de um processo, tendo que ser explicitamente liberados pelo processo. Soluções para 
Evitá-la: Virtualizar recursos, como spooling de impressora para evitar impasses, aonde os 
processos que desejam imprimir algo não interagem diretamente com a impressora física, 
enviando as solicitações para uma área de armazenamento temporário chamada spool (fila 
de impressão) antes de serem enviadas para a impressora. O daemon, em segundo plano, 
gerencia a fila e envia os trabalhos para a impressora física um de cada vez. Pode gerar um 
ligeiro atraso na impressão, pelo armazenamento temporário. 
Condição de Espera Circular: Deve haver uma lista circular de dois ou mais 
processos, cada um esperando por um processo de posse do membro seguinte da cadeia. 
Todas essas quatro condições devem estar presentes para que um impasse de recurso 
ocorra. Se uma delas estiver ausente, nenhum impasse de recurso será possível. 
Soluções para Evitá-la: Alocar recursos de forma estrita, ao não permitir que um processo 
aguarde por um recurso enquanto mantém outros, isto é, ele só pode solicitar um novo 
recurso se ele não possui nenhum recurso atualmente. Limitar o número de recursos que um 
processo pode possuir simultaneamente, se já possui um recurso e deseja outro, ele deve 
primeiro liberar o recurso existente, Impedir que um processo solicite vários recursos ao 
mesmo tempo, aonde só poderá solicitar um recurso por vez de acordo em uma ordem 
hieraráquica cresente numérica. 
Estratégias para Lidar com Impasses - Ignorar o Problema: 
Simplesmente ignorar os impasses, esperando que não ocorram ou que se resolvam por 
conta própria. Detecção e Recuperação: Permitir que os impasses ocorram, detectá-
los quando acontecem e tomar medidas para recuperar o sistema. Evitar 
Dinamicamente: Evitar impasses através de uma alocação cuidadosa de recursos, 
suspensões estratégicas e análise contínua do grafo de recursos (Holt). Prevenção 
Estrutural: Modificar estruturalmente o sistema para negar uma ou mais das quatro 
condições necessárias para a ocorrência de um impasse, geralmente é a utilizada para 
prevenir impassses. 
Grafo de Alocação de Recursos - Cada nó (círculo) no grafo representa um 
processo, os quadrados os recursos, e os arcos direcionados representam solicitações e 
alocações de recursos. Se o arco direcionado estiver saindo do processo e chegando ao 
recurso, é uma solicitação. Caso contrário, é uma posse. Se o grafo contém um ciclo, há um 
impasse. 
 
Algoritmo do Avestruz - Abordagem que visa ignorar o problema, o impasse, e 
fingir que ele não existe. Matemáticos frequentemente consideram essa estratégia 
inaceitável, argumentando que impasses devem ser evitados a todo custo. Por outro lado, 
engenheiros tendem a questionar a necessidade de eliminar impasses se estes ocorrem 
raramente em comparação com outras falhas do sistema, como falhas de hardware e 
defeitos no sistema operacional. 
Detecção e Recuperação de Impasses - Um Recurso de Cada Tipo: É 
possível usar um grafo de recursos para detectar impasses, de tal forma que ele utiliza uma 
busca em profundidade para verificar se há ciclos no grafo de recursos, percorrendo cada nó. 
Se um ciclo é encontrado, os processos envolvidos estão em um impasse. Múltiplos 
Recursos de Cada Tipo: Um algoritmo baseado em matrizes é proposto para detectar 
impasses quando há várias cópias de recursos. Este algoritmo compara vetores entre duas 
matrizes (uma a de alocação atual e a outra a de requisição) para verificar se as solicitações 
de recursos dos processos podem ser atendidas pelos recursos disponíveis: 
- Cada processo é uma linha de cada matriz da de alocação, e as colunas são os recursos que 
ele possui, e cada recurso que ele requer é uma coluna da de requisição. 
- Há uma condição invariante que diz que a os valores do processo na matriz de requisição 
deve ser menor ou igual a dos valores das instâncias de recursos disponíveis (A), aonde E= 
Existente, e A = Disponíveis. 
- Se sim, podemos atender às solicitações desse processo. Caso contrário, ele está em um 
impasse. Veja este Exemplo! 
 
C - Matriz de Alocação (o que os processos possui) | A - Matriz de Requisição (o que os 
processos solicitam) 
A = [0,1,0,2,1] é o vetor das instância dos recursos disponíveis para os processos. A soma 
destes dá 4. Então verifiquemos: 
 P1 - P1 requer [1,1,0,2,1], mas R1 não tem nenhum disponível, então não é preciso checar o 
resto. Não podemos atender totalmente às solicitações do Processo 1. Impasse. 
P2 - P2 solicita [0,1,0,2,1]. Sim, podemos atender as requisições do P2. Atualiza-se o vetor das 
instância dos recursos disponíveis para marcar a alocação para/e marcar o P2, ficando agora A 
= [0,2,0,3,1] (Alocação de P2 = [0,1,0,1,0] + A = [0,1,0,2,1] = A = [0,2,0,3,1] 
P3 - P3 solicita [0,2,0,3,1]. Sim, podemos atender as requisições do P3. Atualiza-se o vetor das 
instância dos recursos disponíveis para marcar a alocação para/e marcar o P3, ficando agora A 
= [0,2,0,3,2] (Alocação de P3 = [0,0,0,0,1] + A = [0,2,0,3,1] = A = [0,2,0,3,2] 
P4 - P4 solicita [0,2,1,1,0], mas o A não tem nenhum R3 disponível, então não é preciso checar 
o resto. Não podemos atender totalmente às solicitações do Processo 4. Impasse. 
Recuperação de um impasse - Mediante preempção: Pode ser viável 
temporariamente retirar um recurso de seu proprietário/processo atual e atribuí-lo a outro 
processo. A intervenção manual pode ser necessária, especialmente em sistemas operacionais 
de processamento em lote. Mediante retrocesso: Se um impasse é detectado, é possível 
retroceder um processo para um ponto anterior no tempo, antes de adquirir um recurso em 
questão, mas iimplica perder o trabalho feito desde o último ponto de salvaguarda. 
Mediante a eliminação de processos: Matar um ou mais processos para que outros 
possam continuar. A escolha de qual processo matar depende da disponibilidadede recursos e 
da capacidade de reiniciar o processo sem causar danos. 
Algoritmo do Banqueiro - O sistema operacional alocará recursos iniciais para os 
processos com base em uma estimativa de suas necessidades máximas. Antes de conceder 
uma solicitação, o algoritmo verifica se a concessão levará a um estado seguro. Um estado é 
seguro se, com um escalonamento adequado, todos os processos podem ser concluídos, ou 
seja se há recursos disponíveis para todos, e não haverá impasse. Caso contrário, é o estado 
inseguro. Após a liberação de recursos, o algoritmo verifica novamente se o estado permanece 
seguro. Ele funciona de maneira igual ao que foi exibido no algoritmo de detecção de impasse 
com múltiplos recursos de cada tipo, só que com checagem de estados incluído. 
 
Exemplo: 
Primeiramente, é necessário comparar o que há de alocado, para com máximo, para 
determinarmos a coluna de disponíveis dos processos, bastando subtrair, então: 
A tem alocado 1 0 2 1 1 e máximo 1 1 2 1 3, dando na coluna de requisição 0 1 0 0 2 
B tem alocado 2 0 1 1 0 e máximo 2 2 2 1 0, dando na coluna de requisição 0 2 1 0 0 
C tem alocado 1 1 0 1 0 e máximo 2 1 3 1 0, dando na coluna de requisição 1 0 3 0 0 
D tem alocado 1 1 1 1 0 e máximo 1 1 2 2 1, dando na coluna de requisição 0 0 1 1 1 
 
Agora, é necessário checarmos na coluna de requisição, solicitação ou Necessário, para cada 
processo, se o que os processos estão requerindo, tem no vetor de recursos disponíveis. 
com x=0, temos Disponível = 0 0 0 1 1, então: O processo A não requer nenhum R1, requer 1 
do R2, o que não tem no vetor dos disponíveis, ele estará em deadlock. A mesma coisa 
ocorrerá com os B ao requerer 2 do R2, C ao requerer 1 de R1 e D ao requerer 1 de R3 e 
assim vai. Então já irá levar a um estado não seguro, pois todos os processos estarão em 
impasse. 
 
com x=1, temos Disponível = 0 0 1 1 1, então: Os processos A, B continuam em impasse, pelo 
mesmo motivo de x =0, C ao requerer 3 de R3 sendo que só há 1 disponível. Entretanto, D 
não estará em impasse, pois requer 1 de R3, R4, R5, o que existe no vetor de disponíveis. D 
será executado e finalizado, e seus recursos alocados serão somados aos disponíveis para 
sinalizar isso. 
Recursos Alocados ao D = 1 1 1 1 0 + Disponíveis (Atualmente) = 0 0 1 1 1 = Disponíveis = 1 1 
2 2 1 
 
com x=2, não teremos impasse, pois temos Disponivel = 0 0 2 1 1, então: O processo A 
inicialmente estará ainda em impasse, pois irá requer 1 de R2, o que não é possível. O B 
também irá requerer 2 de R2, e estará também em impasse. O C pelo mesmo motivo do A, 
estará em impasse. D não estará em impasse, pois requer 1 de R3, R4, R5, o que existe no 
vetor de disponíveis. D será executado e finalizado, e seus recursos alocados serão somados 
aos disponíveis para sinalizar isso. 
Recursos Alocados ao D = 1 1 1 1 0 + Disponíveis (Atualmente) = 0 0 2 1 1 = Disponíveis = 1 1 
3 2 1 
 
Agora, com Disponíveis = 1 1 3 2 1, voltamos a checar novamente o A. Ele entrará em 
impasse pois requer 2 de R1, o que não é possível. B irá requer 2 de R2, o que também não é 
possível realizar. O C requer 1 de R1, e R3 de R3, e isso está disponível. C não estará em 
impasse, será executado e finalizado, e seus recursos alocados serão somados aos 
disponíveis para sinalizar isso. 
Recursos Alocados ao C = 1 1 0 1 0 + Disponíveis (Atualmente) = 1 1 3 2 1 = Disponíveis = 2 2 3 
3 1 
 
Agora, com Disponíveis = 2 2 3 3 1, só restou os processos A e B. O A continuará em impasse 
pois requer 2 de R5, mas só há 1 disponível. B não estará em impasse, pois suas requisições 
tem disponibilidade. Ele será executado e finalizado, e seus recursos alocados serão 
somados aos disponíveis para sinalizar isso. 
Recursos Alocados ao D = 2 0 1 1 0 + Disponíveis (Atualmente) = 2 2 3 3 1 = Disponíveis = 4 2 
4 4 1 
 
Por fim, com Disponíveis = 2 2 3 3 1, o A finalmente terá disponibilidade, será executado e 
finalizado. Então o menor valor de x nesse caso, seria 2.