Sistemas Operacionais I

Gerência de Processos: Deadlocks

Prof. Alexandre Duarte : http://alexandrend.comCentro de Informática | Universidade Federal da Paraíba

Estes slides são baseados no material que acompanha o livro Operating Systems Concepts de Silberschatz, Galvin and Gagne

Objetivos

Apresentar um descrição formal de deadlock, um problema que impede que conjuntos de processos colaborativos possam completar suas tarefas

Apresentar algumas técnicas e métodos para prevenir e impedir a ocorrência de deadlocks em sistemas computacionais

O problema

Um conjunto de processos bloqueados onde cada um possui o controle de um recursos e aguarda para obter o controle de um outro recurso mantido por um outro processo no conjunto

Exemplo O sistema possui dois discos rígidos P1 e P2 mantém cada um o controle de um dos discos e deseja

obter o controle do outro disco

Exemplo semáforos A e B, inicializados com 1

P0 P1

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

Exemplo do cruzamento da ponte

Tráfego em apenas um sentido 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é (preempção e reversão) Vários carros podem precisar dar ré caso ocorra um

deadlockStarvation is possible

A maioria dos SOs não previne ou resolve deadlocks

Caracterização de deadlocks

Exclusão mútua: apenas um processo pode utilizar um recurso por vez

Posse e espera: um processo em posse de um recurso pode esperar para adquirir recursos adicionais em posse de outros processos

Não preempção: um recurso só pode ser liberado voluntariamente pelo processo que o está utilizando

Espera circular: existe um conjunto de processos bloqueados {P0, P1, …, P0} onde P0 aguarda por um recurso em posse de P1, P1 aguarda por um recurso em posse de P2, …, Pn–1 aguarda por um recurso em posse de Pn, e Pn aguarda um recurso em posse de P0.

Modelagem do sistema

Tipos de recursos R1, R2, . . ., Rm

ciclos de CPU, espaço de memória, dispositivos de E/S

Cada tipo de recurso Ri possui Wi instâncias. Cada processo utiliza um recurso como

segue: requisição Uso liberação

Grafo de alocação de recursos

O conjunto V possui dois tipos de vértices: P = {P1, P2, …, Pn}, representando todos os

processos no sistema R = {R1, R2, …, Rm}, representando todos os

recursos no sistema Aresta de solicitação: – uma aresta de um

processo para um recurso (Pi Rj) Aresta de atribuição: um vértice de um

recurso para um processo (Rj Pi)

Grafo de alocação de recursos

Processo

Tipo de recurso com 4 instâncias

Pi requisita uma instância de Rj

Pi está em posse de 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 com um ciclo mas sem deadlock

Fatos básicos

Se o grafo não possui ciclos não há deadlock

Se o grafo possui ciclos se há apenas uma instância por tipo de recurso

então tem-se um deadlock se há mais de uma instância por tipo de recurso

então há a possibilidade de um deadlock

Métodos para lidar com deadlocks

Garantir que o sistema nunca entrará em um estado de deadlock

Permitir que o sistema entre em deadlock e recuperar o sistema

Ignorar o problema e fingir que deadlocks nunca ocorrem (utilizado pela maioria dos sistemas operacionais, incluindo Unix)

Prevenção de deadlocks

Exclusão mútua – não é necessária para recursos compartilháveis; precisa valer para recursos não compartilháveis

Posse e espera – precisa garantir que sempre que um processo requisite novos recursos ele não esteja em posse de nenhum outro recurso Exigir que um processo requisite e receba todos os

recursos antes de iniciar sua execução, ou permitir que um processo só requisite recursos quando não tiver nenhum recurso

Implica em baixa utilização de recurso e possibilidade de starvation

Prevenção de dadlocks

Não-preempção Se um processo que está de posse de um recurso solicita um

outro recurso que não pode ser alocado imediatamente para ele todos os recursos em seu poder são imediatamente liberados

Os recursos liberados são adicionados à lista de recursos necessários para a execução do processo

O processo será reiniciado quando puder obter novamente todos os recursos que já tinha e também os novos recursos de que necessitava

Espera circular – impor uma ordenação total nos tipos de recursos e exigir que todos os processo requisitem os recursos em ordem crescente de numeração

Impedimento de deadlocks

A forma mais simples e útil requer que cada processo declare a quantidade máxima de cada tipo de recurso disponível que ele pode precisar

O algoritmo de impedimento de deadlocks examina dinamicamente o estado da alocação de recursos para garantir que jamais ocorra uma condição de espera circular

O estado da alocação de recursos é definido pela quantidade de recursos disponíveis e alocados e pelas demandas máximas dos processos

Estado seguro

Quando um processo requisita um recurso disponível, o sistema precisa decidir se a alocação imediata deixa o sistema em um estado seguro

O sistema está em um estado seguro se existe uma sequência <P1, P2, …, Pn> com todos os processos do sistema na qual para cada Pi, os recursos que Pi ainda pode precisar podem ser alocados com os recursos disponíveis no momento + recursos em posse dos processos Pj, com j < i

Ou seja: Se os recursos que Pi precisa não puderem ser fornecidos

imediatamente, Pi pode esperar até que todos os processos Pj terminem Quando Pj terminar, Pi pode obter os recursos necessários, executar,

liberar os recursos e terminar Quanto Pi termina, Pi +1 pode obter os recursos de que necessita e

assim por diante

Fatos básicos

Se o sistema está em um estado seguro não há deadlock

Se o sistema está em um estado inseguro há possibilidade de deadlock

Impedimento garantir que o sistema jamais entre em um estado inseguro

Estado seguro, inseguro e de deadlock

Algoritmos para impedimento de deadlocks

Instância única para cada recurso Utilizar um grafo de alocação de

recursos Múltiplas instâncias de algum tipo de

recurso Utilizar o algoritmo do banqueiro

Esquema do grafo de alocação de recursos Aresta de requisição: Pi Rj indica que um processo Pj pode vir a

requisitar o recursos Rj; representada por uma linha pontilhada

Arestas de requisição são convertidas em arestas de solicitação quando o processo efetivamente requisita o recurso

Uma aresta de solicitação é convertida em uma aresta de atribuição quando o recurso é alocado para o processo

Quando o recurso é liberado pelo processo a aresta de atribuição é novamente convertida para uma aresta de requisição

Os processos precisam anunciar a priori para o sistema quais recursos podem vir a solicitar, criando inicialmente todas as arestas de requisição

Grafo de alocação de recursos

Grafo de alocação de recursos inseguro

Algoritmo do grafo de alocação de recursos

Suponha que o processo Pi requisite um recursos Rj

Essa requisição só pode ser autorizado se converter a aresta de requisição em uma aresta de atribuição não resultar na formação de um ciclo no grafo de alocação de recursos

Algoritmo do banqueiro

Múltiplas instâncias

Cada processo deve declarar a priori a utilização máxima de recursos

Quando um processo solicita recursos ele pode ter que esperar

Quando um processo obtém todos os recursos de que necessita ele deve liberá-los em uma quantidade finita de tempo

Estruturas de dados utilizadas pelo algoritmo do banqueiro

Disponível: Vetor de comprimento m. Se disponivel [j] = k, existem k instâncias do recurso Rj disponíveis

Max: matriz n x m matrix. Se Max [i,j] = k, então o Pi pode solicitar, no máximo, k instâncias do recurso Rj

Alocação: matriz n x m. Se alocação [i,j] = k então o processo Pi está atualmente em posse de k instâncias do recursos Rj

Necessidade: matriz n x m. Se necessidade [i,j] = k, então o processo Pi pode precisar de mais k instâncias do recurso Rj para poder completar sua tarefa

Necessidade [i,j] = Max[i,j] – Alocação [i,j]

Algoritmo de segurança

Algoritmo para solicitação de recursos

Exemplo de execução do algoritmo do banqueiro

Exemplo de execução do algoritmo do banqueiro

O estado atual é seguro?

O que acontece se o sistema receber a seguinte sequência de solicitações? P1 requisita (1,0,2)

P4 requisita (3,3,0)

P0 requisita (0,2,0)

Detecção de deadlocks

Permite que o sistema entre em um estado de deadlock

Utiliza um algoritmo de detecção para identificar esta situação

Utiliza um esquema de recuperação para eliminar o deadlock

Instância única de cada recurso

Mantem um grafo de espera Os nós são processos Pi Pj se Pi está esperando por Pj

Um algoritmo de detecção de ciclos é executado periodicamente. Se existe um ciclo, existe um deadlock

Um algoritmo para detecção de ciclos tem complexidade O(n2), onde n é o número de nós no grafo

Grafo de alocação de recursos e grafo de espera

Várias instâncias de um recurso

Disponível: Um vetor de comprimento m indica a quantidade de instâncias disponíveis para cada tipo de recurso

Alocação: Uma matriz n x m define o número de instâncias de cada tipo de recurso alocadas para cada processo

Requisição: Uma matriz n x m indicando as requisições realizadas por cada processo. Se requisição [ij] = k, o processo Pi está requisitando mais k instâncias do recurso Rj.

Algoritmo de detecção

Exemplo do algoritmo de detecção

Exemplo do algoritmo de detecção

O sistema está em deadlock?

O que acontece se P2 requisitar uma instância a mais do recursos C ?

Uso do algoritmo de detecção

Quando e com que frequência invocar o algoritmo depende de: O quão frequente é a ocorrência de um deadlock Quantos processos precisaram ser revertidos?

um para cada ciclo disjunto

Se o algoritmo for executado arbitrariamente ele pode encontrar vários ciclos no grafo de recursos e pode não ser possível identificar qual dentre os processos em deadlock “causou” o problema.

Recuperação: Terminação de processos

Matar todos os processos em deadlock

Matar um processo de cada vez até que o ciclo seja desfeito

Em que ordem matar os processos? Prioridade Tempo de computação e tempo adicional necessário para

conclusão Recursos utilizados pelo processo Recursos necessários para que o processo conclua sua

execução Quantidade de processos a ser finalizada O processo é interativo ou de lote?

Recuperação: Preempção de recursos

Selecionar uma vítima que minimize os custos

Retroceder o processo: voltar para algum estado seguro

Starvation – o mesmo processo pode ser sempre escolhido como vítima