Sistemas Operacionais

Deadlocks

Deadlocks• Problema • Modelo do Sistema • Caracterização• Métodos para Manipulação• Prevenção• Evitar• Detecção • Recuperação

Objetivos

• Devenvolver uma descrição de deadlocks,• os quais impedem que conjuntos de

processos concorrentes completem suas tarefas• Apresentar diferentes métodos para prevenir ou

evitar deadlocks em um sistema computacional

O Problema de Deadlocks • Conjunto de processos bloqueados cada um mantendo

um recurso e esperando para adquirir um recurso, mantido por um outro processo no conjunto

• Exemplo: – Sistema com 2 disk drives– P1 e P2 cada um mantendo um disk drive e cada um

necessitando de um outro• Exemplo: semáforos A e B, iniciados com 1

» P0 P1

» wait (A); wait(B)» wait (B); wait(A)

Exemplo para Atravessar uma Ponte

• Tréfego somente em uma direção• Cada seção da ponte pode ser vista como um recurso• Se ocorre deadlock, pode ser resolvido se um carro

voltar (preempção de recursos e rollback)• Diversos carros podem ter que voltar se ocorre

deadlock• Pode causar starvation

Modelo do Sistema• Tipos de recursos R1, R2, . . ., Rm

• CPU cycles, memory space, I/O devices• Cada tipo de recurso Ri tem Wi instâncias• Cada processo utiliza um recurso da seguinte

forma:– pedido – uso – liberação

Caracterização de DeadlockDeadlockDeadlock ocorre se e somente se quatro ocorre se e somente se quatro condições se mantiverem simultaneamentecondições se mantiverem simultaneamente

• Mutual exclusion: somente um processo de cada vez pode usar um recurso

• Hold and wait: um processo mantendo pelo menos um recurso e está esperando para adquirir recursos adicionais mantidos por outros processos

Caracterização de Deadlock• No preemption: um recurso só pode ser liberado

voluntariamente pelo processo que o mantém, após o processo completar a sua tarefa

• Circular wait: existe um conjunto {P0, P1, …, P0} de processos esperando, tal que P0 está esperando por um recurso que está atribuído P1, P1 está esperando por um recurso que está atribuído a

• P2, …, Pn–1 está esperando por um recurso que está atribuído Pn, e

• Pn está esperando por um recurso que está atribuído a P0

Grafo de Alocação de Recursos

GrafoGrafo : um conjunto de vértices : um conjunto de vértices VV e um conjunto e um conjunto de arestas de arestas EE

• V está particionado em dois tipos:– P = {P1, P2, …, Pn}, o conjunto de todos os processos

no sistema– R = {R1, R2, …, Rm}, o conjunto de todos os tipos de

recursos no sistema

• aresta de pedido – aresta direcionada P1 Rj

• aresta de atribuição – aresta direcionada Rj Pi

Grafo de Alocação de Recursos• Processo

• Tipo de recurso com 4 instâncias

• Pi solicita instância de Rj

• Pi está mantendo uma instância de Rj

•Pi

•Pi

•Rj

•Rj

Exemplo de um Grafo de Alocação de Recursos

Grafo de Alocação de Recursos com Deadlock

Grafo de Alocação de Recursos com Ciclo sem Deadlock

Fatos Básicos

• Grafo – não contém ciclos não há deadlock– contém um ciclo se houver

• somente uma instância por tipo de recurso, então ocorre deadlock

• diversas instâncias por tipo de recurso, então pode correr deadlock

Métodos de Manipulação de Deadlock

• Garante que o sistema nunca entra num estado de deadlock

• Permite que o sistema entre num estado de deadlock e então recupera

• Ignora o problema e pretende que deadlocks nunca ocorram no sistema; usado por muitos sistemas operacionais, incluindo o UNIX

Prevenção de Deadlock

• Mutual Exclusion – – não é necessária para recursos

compartilháveis– deve se manter para recursos que não podem

ser compartilhados

Prevenção de Deadlock• Hold and Wait – deve guarantir que sempre

que um processo solicite um recurso, ele não mantém qualquer outro recurso– Exige que os processos solicitem e sejam

alocados todos os seus recursos antes de iniciar a execução, ou permite que o processo solicite recursos somente quando não tenha nenhum outro

– Baixa utilização de recursos; possibilita starvation

Prevenção de Deadlock• No Preemption –

– Se um processo que está mantendo alguns recursos e solicita um outro recurso que não pode ser imediatamente alocado todos os recursos que ele mantém devem ser liberados

– Recursos com preempção são adicionados a lista de recursos do processo que está esperando

– Processo serão reiniciados somente quando ele puder recuperar seus recursos anteriores, além dos novos que está solicitando

Prevenção de Deadlock

• Circular Wait – – impõe uma ordenação total de todos os

tipos de recursos – requer que cada processo solicite recursos

em uma ordem crescente de enumeração

Evitar Deadlock• Requer que o sistema tenha alguma informação

adicional disponível a priori • Modelo mais simples e útil requer que cada

processo declare o número máximo de recursos de cada tipo que pode precisar

• Algoritmo de deadlock-avoidance examina dinamicamente o estado de alocação de recursos para garantir que nunca ocorra um condição de espera circular (circular-wait)

Evitar Deadlock

• Estado de alocação de recursos é definido– pelo número de recursos disponíveis e

alocados – demanda máxima dos processos

Estado Seguro• Quando um processo solicita um recurso disponível, o

sistema deve decidir se com a alocação imediata deste recurso, o sistema permanece em um estado seguro

• O sistema está em um estado seguro se exite uma seqüência <P0, P2, …, Pn> de todos os processos o sistema é tal que para cada Pi, o recurso que Pi ainda pode solicitar e pode ser satisfeito pelos recursos correntemente disponíveis + recursos mantido por todos os Pj, com j < i

Estado Seguro• Isto é:

– Se Pi necessita de recursos que não estão disponíveis imediatamente, então Pi pode esperar até que todos Pj tenham teminado

– Quando Pj termina, Pi pode obter os recursos necessários, executar, retornar os recursos alocados e terminar

– Quando Pi termina, Pi +1 pode obter seus recursos necessários, e assim por diante.

Fatos Básicos

• Se um sistema está num – estado seguro não ocorre deadlocks– estado inseguro pode ocorrer deadlock

• Evitar garante que um sistema nunca entrará em um estado inseguro

Algoritmos Avoidance

• Única instânica de um tipo de recurso usar• um grafo de alocação de recurso

• Múltiplas instâncias de um tipo de recurso o banker’s algorithm

Esquema do Grafo de Alocação de Recursos

• Aresta de demanda (claim edge) Pi Rj indica que processo Pj pode solicitar o recurso Rj; representado por uma linha tracejada

• Claim edge converte para aresta de pedido (request edge) quando um processo solicita um recurso

• Aresta de pedido converte para aresta de atribuição (assignment edge) quando o recurso é alocado ao processo

• Quando um recurso é liberado por um processo, a aresta de atribuição se converte para uma claim edge

• Recursos devem ser declarados no sistema a priori

Grafo de Alocação de Recursos

Grafo de Alocação de Recursos em Estado Inseguro

Algoritmo do Grafo de Alocação de Recursos

• Suponha que o processo Pi solicite um recurso Rj

• O pedido pode ser garantido somente se a conversão da aresta de pedido (request edge) para aresta de atribuição (assignment edge) não resulta numa formação de um ciclo no grafo de alocação de recursos

Banker´s Algorithm

• Mútiplas instâncias• Cada processo deve a priori declarar a sua

demanda de uso máxima• Quando um processo solicita um recurso ele pode

ter que esperar • Quando um processo consegue todos os seus

recursos, ele deve liberá-los numa quantidade de tempo finita

Estrutura de Dados: Banker´s Algorithm

• Available: Vetor de tamanho m. Se Available [j] = k, existem k instâncias dos recursos do tipo Rj

disponíveis• Max: matriz n x m. Se Max [i,j] = k, então

processo Pi pode pedir até k instâncias do recurso do tipo Rj

Suponha

n = número de processos,

m = número de tipos de recursos

Estrutura de Dados: Banker´s Algorithm

• Allocation: matriz n x m. Se Allocation[i,j] = k então Pi está alocando k instâncias de Rj

• Need: matriz n x m. Se Need[i,j] = k, então Pi pode necessitar de mais k instâncias de Rj para terminar sua tarefa

• Need [i,j] = Max[i,j] – Allocation [i,j]

Algoritmo Seguro• 1. Deixe Work e Finish serem vetores de

tamanho m e n, respectivamente. Inicie:– Work = Available– Finish [i] = false for i = 0, 1, …, n- 1

• 2. Encontre um i tal que ambos: – (a) Finish [i] = false– (b) Needi Work– Se não existe tal i, vá para o passo 4

• 3. Work = Work + AllocationiFinish[i] = truevá para o passo 2

• 4. Se Finish [i] == true tara todo i, então o sistema está em um estado seguro

Algoritmo de Pedido de Recurso por Processo Pi

• Request = vetor de pedido para o processo Pi. If Requesti [j]=k então processo Pi quer k instâncias do recurso de tipo Rj

• 1. Se Requesti Needi vá para o passo 2. Caso contrário, raise error condição de erro, uma vez que o processo excedeu sua demanda máxima

• 2. Se Requesti Available, vá para o passo 3. Caso contrário Pi deve esperar, uma vez que os recursos não estão disponíveis

Algoritmo de Pedido de Recurso por Processo Pi

• 3. Pretende alocar recursos pedidos para Pi modificando o estado da seguinte forma:

– Available = Available – Request;– Allocationi = Allocationi +

Requesti;– Needi = Needi – Requesti;

Se safe os recursos são alocados a Pi Se unsafe Pi deve esperar e o estado de

alocação antigo é restaurado

Exemplo do Algoritmo do Banqueiro• 5 Processos P0 até P4; • 3 tipos de recursos:• A (10), B (5), e C (7) instâncias• Snapshot do tempo T0:• Allocation Max Available• 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

Exemplo do Algoritmo do Banqueiro

• O conteúdo da matriz Need é definido como Max–Allocation

• Need• 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, porque a seqüência < P1, P3, P4, P2, P0> satisfais o critério de segurança

Exemplo: Pi solicita (1,0,2)

• Verfique que Request Available (que é, (1,0,2) (3,3,2) true)

• Allocation Need Available• 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 • P23 0 1 6 0 0 • P3 2 1 1 0 1 1• P4 0 0 2 4 3 1

Exemplo: Pi solicita (1,0,2)

• Execução do algoritmo de segurança mostra que a seqüência < P1, P3, P4, P0, P2> satisfais a necessidade de segurança

• O pedido para (3,3,0) pelo P4 pode ser garantido?

• O pedido para (0,2,0) pelo P0 pode ser garantido?

Detecção de Deadlock

• Permite ao sistema entrar num estado de deadlock

• Algoritmo de Deteção• Esquema de Recuperação

Única Instância para Cada Tipo de Recurso

• Mantém grafo wait-for– Nós são processos– Pi Pj se Pi está esperando por Pj

• Periodicamente invoca um algoritmo que busca por um ciclo no grafo. Se existe um ciclo, existe deadlock

• Um algoritmo para detectar um ciclo em um grafo requer operações da ordem de n2, onde n é o número de vértices no grafo

Grafo de Alocação de Recurso e Grafo Wait-For

Resource-Allocation Graph Corresponding Wait-For Graph

Diversas Instâncias de um Tipo de Recurso• Available: Um vetor de tamanho m indica o

número de recursos disponíveis de cada tipo• Allocation: Uma matriz n x m define o

número de recursos de cada tipo correntemente alocado para cada processo

• Request: Uma matriz n x m indica o pedido corrente de cada processo. Se Request [ij] = k, então o processo Pi está pedindo mais k instâncias do tipo de recurso Rj

Algoritmo de Detecção

• 1. Deixe Work e Finish serem vetores de tamanho m e n, respectivamente. Inicie:– (a) Work = Available– (b) For i = 1,2, …, n, if Allocationi 0, then

Finish[i] = false;otherwise, Finish[i] = true• 2. Encontre um índice i tal que ambos:

– (a) Finish[i] == false– (b) Requesti Work

– Se tal i não existe, vá para o passo 4

Algoritmo de Detecção

• 3. Work = Work + AllocationiFinish[i] = truevá para o passo 2

• 4. Se Finish[i] == false, para algum i, 1 i n, então o sistema está num estado de deadlock. Além disso, se Finish[i] == false, então Pi está em deadlock

•

Algoritmo requer operações da ordem de O(m x n2) para detectar se o sistema está em estado de deadlocked

Exemplo do Algoritmo de Detecção• 5 processos P0 até P4; 3 tipo de recursos

A (7), B (2), e C (6) instâncias• Snapshot no tempo T0:• Allocation Request Available• A B C A B C A B C• P00 1 0 0 0 0 0 0 0• P12 0 0 2 0 2• P2 3 0 3 0 0 0 • P3 2 1 1 1 0 0 • P4 0 0 2 0 0 2• Seqüência <P0, P2, P3, P1, P4> resultará em Finish[i]

= true para todo i

Exemplo do Algoritmo de Detecção

• P2 pede uma instância adicional do tipo C• Request• A B C• P00 0 0• P12 0 1• P2 0 0 1• P3 1 0 0 • P4 0 0 2

Exemplo do Algoritmo de Detecção

• Estado do sistema?– Pode demandar recurso mantido pelo

processo P0, mas recursos insuficientes se ajustam a outros processos; pedidos.

– Deadlock existe, consistindo dos processos P1, P2, P3, e P4

Uso do Algoritmo de Detecção

• Quando e quantas vezes, invocar depende de:– Quantas vezes é provável que ocorra deadlock ?– Quantos processos necessitarão ter a sua

execução retornada para determinado ponto (rolled back)?• um por cada ciclo disjunto

• Se o algoritmo de detecção é invocado arbitrariamente, pode haver muitos ciclos no grafo de recursos e então não seriam capazes de dizer quais dos muitos processos em deadlock causaram o deadlock

Recuperação de Deadlock: Processo de Terminação

• Abortar todos os processos em deadlock• Abortar um processo de cada vez até o ciclo de

deadlock ser eliminado• Em que ordem escolheríamos abortar?

– Prioridade do processo– Quanto tempo o processo computou, e quanto

tempo mais falta para terminar– Recursos usados pelo processo– Recursos necessários para completar o processo– Quantos processos necessitam ser terminados – O process é interativo ou batch?

Recuperação de Deadlock: Preempção de Recursos

• Seleção de uma vítima – minimiza o custo• Rollback – returna para algum estado seguro,

reinicia processo naquele estado• Starvation – algum processo pode sempre ser

escolhido como vítima, incluir número de rollbacks no fator de custo