View
116
Download
1
Category
Preview:
Citation preview
Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Capítulo 7: Deadlocks
7.2 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
O Problema do Deadlock
Um conjunto de processos bloqueados, cada um bloqueando um recurso e esperando adquirir um recurso bloqueado por outro processo do conjunto
Exemplo
Sistema com dois drivers de disco
P1 e P2 possuem um driver e querem adquirir mais um driver
Exemplo
Semáforos A e B, inicializados como 1
P0 P1
wait (A); wait (B);
wait(B) ; wait(A);
7.3 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Exemplo do cruzamento da ponte
Apenas uma mão por vez
Cada seção da ponte pode ser vista como um recurso
Se um deadlock ocorrer, ele pode ser resolvido se um dos carros der ré (libera recursos e desfaz a ação)
Pode ser necessário mover muitos carros se um deadlock ocorrer
Inanição é possível
Observação
A maioria dos OSs não evitam ou lidam com deadlocks
7.4 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Exemplo de deadlock
Thread-sem-deadlock.py
Thread-com-deadlock.py
7.5 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Modelo do Sistema
Tipos de recurso: R1, R2, . . ., Rm
Exemplos: Ciclos de CPU, espaço de memória, dispositivos de E/S
Cada recurso do tipo Ri tem Wi instâncias
Cada processo usa um recurso da seguinte forma:
requisita
usa
libera
7.6 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Caracterização do deadlock
Exclusão mútua: apenas um processo pode usar um certo recurso de cada vez
Posse e espera: um processo bloqueando pelo menos um recurso está esperando para obter recursos adicionais bloqueados por outros processos
Sem preempção: um recurso pode ser liberado apenas voluntariamente por um processo, após o processo ter concluído as suas tarefas
Espera circular: existe um conjunto {P0, P1, …, Pn} de processos esperando de tal forma que P0 está esperando por um recurso que está bloqueado por P1, P1 está esperando por um recurso que está bloqueado por P2, …, Pn–1 está esperando por um recurso que está bloqueado por Pn, e Pn está esperando por um recurso que está bloqueado por P0.
O deadlock pode ocorrer se 4 condições ocorrem simultaneamente:
7.7 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Grafo de alocação de recursos
V é particionado em dois tipos:
P = {P1, P2, …, Pn}
Conjunto com todos os processos do sistema
R = {R1, R2, …, Rm}
Conjunto de todos os recursos do sistema
Aresta de requisição – aresta direcionada Pi Rj
Aresta de atribuição – aresta direcionada Rj Pi
Conjunto de vértices V e conjunto de arestas E.
7.8 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Grafo de alocação de recursos
Processo
Tipo de recurso com 4 instâncias
Pi requisita uma instância de Rj
Pi está bloqueando uma instância de Rj
Pi
Pi
Rj
Rj
7.9 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Exemplo de grafo de alocação de recursos
7.10 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Grafo de alocação de recursos com deadlock
7.11 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Grafo de alocação de recursos com ciclo, mas sem deadlock
7.12 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Fatos básicos
Se um grafo não contém ciclos ausência de deadlock
Se um grafo contém ciclos Se existe apenas um instância de cada tipo de recurso, então
tem deadlock
Se existem diversas instâncias por tipo de recurso, possibilidade de deadlock
7.13 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Métodos para lidar com Deadlocks
Garantir que o sistema nunca entrará em um estado de deadlock
Permitir que o sistema entre em um estado de deadlock e, então, recuperar
Ignorar o problema e fingir que deadlocks nunca ocorrem no sistema
Usado pela maioria dos sistemas operacionais, incluindo UNIX
7.14 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Prevenção de deadlock
Exclusão mútua - não é necessário para recursos compartilháveis; contudo, deve ser aplicada aos recursos não compartilháveis
Posse e espera – deve garantir que, sempre que um processo solicita um recurso, não possui quaisquer outros recursos
Exigir que o processo solicite e aloque todos os seus recursos antes de iniciar a execução, ou permitir que o processo solicite recursos somente quando o processo não tem nenhum recurso alocado
Desvantagens
Baixa utilização de recursos
Inanição possível
Restringir a forma como os pedidos podem ser feitos, tratando ao menos uma das condições de deadlock:
7.15 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Prevenção de deadlock (Cont.)
Ausência de preempção – Se um processo que está em posse de alguns recursos solicita outro recurso que não pode ser imediatamente alocado para ele, então todos os recursos possuídos são liberados
Recursos liberados são adicionadas à lista de recursos que o processo está aguardando
O processo será reiniciado somente quando ele conseguir todos os recursos que está requisitando
Espera circular – impor uma ordenação de todos os tipos de recursos e exigir que cada processo solicite recursos na ordem crescente de numeração
Problemas
Como numerar recursos?
Pedidos de recursos são feitos pelo programador, que desconhece a ordem imposta pelo sistema
7.16 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Impedimento de Deadlock
Modelo mais simples e mais útil
Exige que cada processo declare o número máximo de recursos de cada tipo que pode precisar
O algoritmo para evitar deadlock examina dinamicamente o estado de alocação de recursos para garantir que nunca pode haver uma condição de espera circular
O estado de alocação de recursos é definido pelo número de recursos disponíveis e alocados
Exige que os processos declarem a sua demanda máxima
Requer que o sistema tenha informações adicionais a priori
A ideia é garantir que o processo fique em um estado seguro.
7.17 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Estado Seguro
Quando um processo solicita um recurso disponível, o sistema deve decidir se a alocação imediata deixa o sistema em um estado seguro
O sistema está em estado seguro se existe uma sequência <P1, P2, …, Pn> de todos os processos do sistema de tal forma que, para cada Pi, os recursos que Pi ainda pode solicitar podem ser atendidos pelos recursos atualmente disponíveis + recursos mantidos por todos Pj, com j <i
Isto é:
Se as necessidades de recursos do Pi não estão imediatamente disponíveis, então Pi pode esperar até que todos os Pj ter terminado
Quando Pj terminar, Pi pode obter os recursos necessários, executar, retornar os recursos alocados e terminar
Quando termina Pi, Pi +1 pode obter seus recursos necessários, e assim por diante
7.18 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Fatos básicos
Se um sistema está em estado seguro não ocorre deadlocks
Se um sistema está em estado inseguro possibilidade de deadlock
Para evitar deadlocks assegurar que um sistema nunca entrará em um estado inseguro
7.19 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Estados seguro, inseguro e de deadlock
7.20 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Algoritmos para evitar deadlocks
Única instância de um tipo de recurso
Use um gráfico de alocação de recursos
Várias instâncias de um tipo de recurso
Use o algoritmo do banqueiro
7.21 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Esquema Gráfico de Alocação de Recursos
Aresta de reivindicação Pi Rj indica que o processo Pj pode solicitar recursos Rj
Representada por uma linha tracejada
A aresta de reivindicação é convertida para aresta de pedido quando o processo solicita o recurso
A aresta de pedido é convertida para uma aresta de atribuição quando o recurso é alocado ao processo
Quando um recurso é liberado por um processo, a aresta de atribuição é convertida em uma aresta de reivindicação
Os recursos devem ser reivindicados a priori no sistema
7.22 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Gráfico de Alocação de Recursos
7.23 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Estado inseguro em Gráfico de Alocação de Recursos
7.24 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Algoritmo Gráfico de alocação de Recursos
Suponha que o processo Pi requisite o recurso Rj
O pedido pode ser concedido apenas se a conversão da aresta de pedido para uma aresta de atribuição não resultar na formação de um ciclo no gráfico de alocação de recursos
7.25 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Algoritmo do Banqueiro
Usado quando existem várias instâncias de cada recurso
Cada processo precisa informar a quantidade máxima que pode utilizar de cada recurso
Quando um processo solicita um recurso, talvez precise esperar para poder alocá-lo
Quando um processo recebe todos os seus recursos, deve devolvê-los em uma quantidade finita de tempo
7.26 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Estruturas de Dados para o algoritmo do banqueiro
Disponível: Vetor de tamanho m. Se disponível [j] = k, existem k instâncias do tipo de recurso Rj disponíveis
Max: matriz n x m. Se Max [i, j] = k, então o processo Pi pode solicitar no máximo k recursos do tipo Rj
Alocação: matriz n x m. Se Alocação [i, j] = k então Pi tem atualmente k instâncias do recurso Rj
Precisa: matriz n x m. Se Precisa [i, j] = k, então Pi pode precisar de mais k instâncias do Rj para completar sua tarefa
Precisa [i, j] = Max [i, j] - Alocação [i, j]
Seja n o número de processos e m o número de tipos de recursos:
7.27 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Algoritmo de segurança
1. Sejam Trabalho e Fim vetores de comprimento m e n, respectivamente. Inicialize:
Trabalho = Disponível
Fim [i] = falso para i = 0, 1, …, n- 1
2. Encontre um i de tal forma que ambas as condições sejam verdadeiras:
(a) Fim [i] = falso
(b) Precisa[i] Trabalho
Se esse i não existir, ir para passo 4
3. Trabalho = Trabalho + Alocação[i] Fim[i] = verdadeiroVá para passo 2
4. Se Fim [i] == verdadeiro para todo i, então o sistema está em um estado seguro
7.28 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Algoritmo de pedido de recursos para o Processo Pi
Pedido = vetor de pedido para o processo Pi. Se Pedido[i][j] = k, então o processo Pi quer k instâncias do tipo de recurso Rj
1. Se Pedido[i] Precisa[i], vá para o passo 2. Do contrário, gere uma exceção, pois o processo pediu mais do que o máximo.
2. Se Pedido[i] Disponível, vá para passo 3. Do contrario, Pi precisa esperar, pois os recursos não estão disponíveis
3. Finja alocar os recursos requisitados para Pi modificando os estados da seguinte forma:
Disponível = Disponível – Pedido
Alocação[i] = Alocação[i] + Pedido[i]
Precisa[i] = Precisa[i] – Pedido[i] Execute o algoritmo de segurança
Se seguro aloque os recursos para Pi Se inseguro Pi precisa esperar e o estado anterior de
alocação deve ser restaurado
7.29 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Exemplo de Algoritmo do Banqueiro
5 processos: P0 até P4
3 tipos de recursos:
A (10 instâncias), B (5 instâncias) e C (7 instâncias)
Estado em T0:
Alocação Max Disponível
A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
7.30 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Exemplo (Cont.)
O conteúdo da matriz Precisa é definido como Max – Alocação
Precisa
A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
O sistema está em um estado seguro, pois a sequência < P1, P3, P4, P2, P0> satisfaz o critério de segurança
7.31 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Exemplo: P1 pede (A=1,B=0,C=2)
Verifique que Pedido Disponível (ou seja, (1,0,2) (3,3,2))
Alocação Precisa Disponível
A B C A B C A B C
P0 0 1 0 7 4 3 2 3 0
P1 3 0 2 0 2 0
P2 3 0 2 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
A execução do algoritmo de segurança mostra que a sequência < P1, P3, P4, P0, P2> satisfaz o requisito de segurança
O pedido (3,3,0) feito por P4 pode ser concedido?
O pedido (0,2,0) feito por P0 pode ser concedido?
7.32 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Detecção de Deadlock
Permitir que o sistema entre no estado de deadlock
Algoritmo de detecção
Regime de recuperação
7.33 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Única instância de cada tipo de recurso
Manter gráfico de espera
Nós são processos
Pi Pj se Pi está esperando por Pj
Periodicamente, invocar um algoritmo que procura por um ciclo no gráfico. Se houver um ciclo, existe um deadlock
Um algoritmo para detectar um ciclo em um gráfico requer uma ordem de n2 operações, onde n é o número de vértices no gráfico
7.34 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Gráfico de alocação de recursos e gráfico de espera
Gráfico de alocação de recursos Gráfico de espera correspondente
7.35 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Recuperação de deadlock:encerramento de processos
Opções
Abortar todos os processos em deadlock
Abortar um processo de cada vez, até o ciclo de bloqueio seja eliminado
Em que ordem devemos abortar?
– Prioridade do processo
– Quanto tempo o processo já executou e quanto tempo ainda falta de execução
– Recursos que o processo usou
– Recursos necessários para completar a execução do processo
– Quantos processos precisarão ser terminados
– É um processo interativo ou batch?
7.36 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Recuperação de deadlock:preempção de recursos
Seleção de uma vítima - minimizar o custo
Rollback - retornar o processo a um estado seguro
Reiniciar o processo nesse estado seguro
Problema
Inanição - o mesmo processo pode sempre ser escolhido como vítima
Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition
Fim do Capítulo 7
Recommended