Prof. MSc. Ricardo RiosProf. MSc. Ricardo Rios

Escola Superior de Tecnologia

Universidade do Estado do Amazonas

105/11/2008

Introdução� Suponha dois processos, A e B, cada um desejando

imprimir um arquivo armazenado em fita� O processo A solicita e consegue permissão para utilizar a

impressoraO processo B solicita e conseguem permissão para utilizar a � O processo B solicita e conseguem permissão para utilizar a unidade de fita

� A solicita acesso à unidade de fita, mas fica bloqueado até que B libere a unidade

� B solicita permissão para utilizar a impressora, mas fica bloqueado até que A libere a impressora

� Essa situação é conhecida como deadlock

2

Introdução (Cont.)� Deadlocks podem ocorrer em várias outras situações,

além daquelas onde processos solicitam acesso a dispositivos de entrada/saída� Em um sistema de banco de dados, no que diz respeito � Em um sistema de banco de dados, no que diz respeito

ao acesso de vários processos a vários registros

3

Recursos� Os deadlocks podem ocorrer quando se garante a

processos o acesso exclusivo a dispositivos de entrada/saída, arquivos, etc.

� Um recurso pode ser um dispositivo de hardware, tal � Um recurso pode ser um dispositivo de hardware, tal como um registro em um base de dados

� Um recurso só pode ser utilizado por um único processo em um determinado instante de tempo

� Os recursos são� Preemptíveis

� Não-preemptíveis

4

Recurso (Cont.)� Recurso preemptível

� Pode ser tomado do processo que estiver usando o recurso, sem nenhum prejuízo para o processo� Memória� Memória

� Situação: processos requisitando acesso à impressora e à memória

� Recurso não-preemptível� Não pode ser tomado de seu proprietário atual sem

causar problemas no processamento corrente� Impressora

5

Recurso (Cont.)� Geralmente deadlocks ocorrem quando recursos não-

preemptíveis estiverem envolvidos� Em situações potenciais para ocorrência de deadlocks,

quando recursos preemptíveis estiverem envolvidos, quando recursos preemptíveis estiverem envolvidos, sempre poderão ser resolvidas com a realocação dos recursos entre os processos

� A seqüência de eventos necessária para garantir o uso de determinado recurso é� Requisitar o recurso� Usar o recurso� Liberar o recurso

6

Recurso (Cont.)� Se o recurso não estiver disponível, o processo deve esperar� Um processo que teve negado o acesso a um recurso

normalmente é colocado em um loop, onde solicita o recurso, dorme e tenta novamente, até ter sucesso

Sempre que a um processo tiver sido negado o acesso a um � Sempre que a um processo tiver sido negado o acesso a um recurso, esse processo será considerado como se estivesse bloqueado

� A forma de se requisitar um recurso é extremamente dependente do sistema� Em alguns sistemas existe a chamada REQUEST, feita de

forma explícita� Em outros a solicitação é feita através da chamada OPEN

7

Deadlock

� Formalmente pode ser definido como� Um conjunto de processos está em uma situação de deadlock, se cada processo do conjunto estiver esperando por um evento que somente outro processo esperando por um evento que somente outro processo pertencente ao conjunto poderá fazer acontecer

� Na maioria dos casos o evento que cada processo está esperando é a liberação de algum dos recursos, no momento alocado a outro processo do conjunto

8

Condições de ocorrência� Condição de exclusão mútua

� Cada recurso ou está alocado a exatamente um processo ou está disponível

� Condição de posse e de espera� Processos que estejam de posse de recursos obtidos anteriormente

podem solicitar novos recursosProcessos que estejam de posse de recursos obtidos anteriormente podem solicitar novos recursos

� Condição de não-preempção� Recursos já alocados a processos não podem ser tomados à força.

Eles precisam ser liberados explicitamente pelo processo que detém sua posse

� Condição de espera circular� Deve existir uma cadeia circular de dois ou mais processos, cada um

dos quais esperando por um recurso que está com o próximo membro da cadeia

9

Condições de ocorrência (Cont.)� Todas as quatro condições devem estar presentes para

que possa ocorrer deadlock

10

O Modelo de Deadlock� Essas quatro condições podem ser modeladas com o uso de grafos

dirigidos

� Processo A está de posse do recurso R� Processo B aguarda pelo recurso S� Processos C e D estão em deadlock sobre os recursos T e U

11

O Modelo de Deadlock (Cont.)� Como deadlock

ocorre

12

O Modelo de Deadlock (Cont.)� Como deadlockpode ser evitado

13

O Modelo de Deadlock (Cont.)� Há quatro estratégias para tratar os deadlocks

� Ignorar complemente o problema

� Detectar e recuperar a partir da situação de deadlock

� Evitar dinamicamente o deadlock, pela cuidadosa � Evitar dinamicamente o deadlock, pela cuidadosa alocação dos recursos aos processos

� Prevenir o deadlock, através da negação de uma das quatro condições necessárias para a ocorrência do mesmo

14

Algoritmo do Avestruz� Abordagem mais simples

� Enterre a cabeça na areia e pense que não há nenhum problema acontecendo

� Os matemáticos acham que os deadlocks devem ser � Os matemáticos acham que os deadlocks devem ser prevenidos a qualquer preço

� Os engenheiros não querem pagar a conta da queda de desempenho decorrente da eliminação de deadlocks, caso estes ocorram uma vez a cada cinco anos

15

Algoritmo do Avestruz (Cont.)� O Unix e Windows não se preocupam com a

ocorrência de deadlocks� Raramente ocorrem

� O custo de prevenir é alto� O custo de prevenir é alto

� Decisão� Conveniência

� Correção

16

Detecção e Recuperação� Uma segunda técnica é detectar e recuperar os deadlocks

� O sistema não se preocupa em prevenir a ocorrência

� Ele permite que ocorram, tenta detectar e age no sentido � Ele permite que ocorram, tenta detectar e age no sentido de normalizar a situação, após a ocorrência de deadlocks

17

Detecção com um recurso de cada

tipo� Só existe um recurso de cada tipo� Grafo de recursos

18

Detecção com um recurso de cada

tipo (Cont.)

� Se houver um ou mais ciclos, está garantida a ocorrência de deadlocks

� Situação� Processo A está de posse de R e precisa de S� Processo A está de posse de R e precisa de S

� Processo B não está de posse de recursos, mas precisa de T

� Processo C não está de posse de recursos, mas precisa de S

� Processo D está de posse de U e precisa de S e de T

� Processo E está de posse de T e precisa de V

� Processo F está de posse de W e precisa de S

� Processo G está de posse de V e precisa de U

19

Detecção com um recurso de cada

tipo (Cont.)

� Há possibilidade de ocorrer uma situação de deadlocke, se houver, quais processos estarão envolvidos?

20

Detecção com um recurso de cada

tipo (Cont.)� Apesar de ser simples detectar a condição de deadlock

através do exame gráfico, este método não pode ser utilizado em sistemas reais, pois há a necessidade de um algoritmo para detecção de deadlocks

� Um algoritmo, dos mais simples, inspeciona um grafo e termina quando encontra um ciclo ou quando encontra nenhum� Esse algoritmo utiliza uma estrutura de dados L, que é

uma lista de nós� Durante a execução do algoritmo os arcos são marcados

para indicar que já foram inspecionados

21

Detecção com um recurso de cada

tipo (Cont.)1. Para cada nó N do grafo, realize os cinco passos seguintes, com N

sendo o nó inicial2. Inicie L como uma lista vazia e designe todos os arcos como

desmarcados3. Coloque o nó corrente no fim da lista L e verifique se ele aparece mais

de uma vez em L. Se isto for verdade, o grafo contém um ciclo, listado de uma vez em L. Se isto for verdade, o grafo contém um ciclo, listado em L, e o algoritmo deve terminar

4. A partir deste nó, veja se existe algum arco não-assinalado partindo do nó. Se houver, vá para o passo 5, se não para o passo 6

5. Escolha randomicamente um arco não assinalado, partindo deste nó e o marque. Depois disto, pegue o próximo nó e volte para o passo 3

6. Chegamos então a um beco sem saída. Volte para o nó anterior, isto é, aquele que era o corrente antes do atual. Faça-o ser novamente o nó corrente e volte para o passo 3. Se este nó for o inicial, o grafo não contém ciclos e o algoritmo termina

22

Recuperação de Deadlocks� Após o algoritmo de detecção ter encontrado um deadlock, o que deve ser feito a seguir?� Algo para que o sistema se recupere desta situação e

retorne à sua condição normalretorne à sua condição normal

� Algumas formas de recuperação de uma situação de deadlock

� Recuperação através da preempção

� Recuperação através de volta ao passado

� Recuperação através da eliminação de processos

23

Recuperação de Deadlocks (Cont.)� Recuperação através de preempção de recurso

� Em alguns casos é possível tomar temporariamente um recurso de seu atual dono e entregá-lo a um outro processoprocesso

� Em muitos casos é necessária a intervenção manual

� A capacidade de tomar um recurso de um processo, deixar que outro processo o utilize e devolvê-lo ao processo original, sem que este tenha conhecimento do que ocorre, depende do recurso

� Tomar uma impressora laser de seu proprietário atual

24

Recuperação de Deadlocks (Cont.)� Recuperação através de volta ao passado

� Se for verificado que a ocorrência de deadlocks está muito freqüente os processos podem ser verificados

� Verificar um processo significa escrever seu estado em � Verificar um processo significa escrever seu estado em um arquivo de forma que tais dados possam ser consultados mais tarde� Os arquivos devem conter a imagem da memória e quais

recursos estão alocados ao processo

� Novas verificações não devem ser escritas em cima das antigas, novos arquivos devem ser criados

25

Recuperação de Deadlocks (Cont.)� Quando ocorrer um deadlock é fácil identificar os

recursos necessários à recuperação do processo

� Os processos que possuem os recursos necessários à recuperação do deadlock voltam no tempo, até o recuperação do deadlock voltam no tempo, até o instante anterior à aquisição dos recursos

� Se o processo tentar obter o recurso novamente, ele deve esperar a liberação do recurso

26

Recuperação de Deadlocks (Cont.)� Recuperação através de eliminação de processo

� Modo mais simples de se eliminar uma situação de deadlock

� Elimina-se um dos processos do ciclo e com sorte os � Elimina-se um dos processos do ciclo e com sorte os demais processos podem prosseguir

� Uma outra forma é eliminar um processo fora do ciclo para liberar recursos� O processo deve ser escolhido com cuidado para que sejam

liberados os recursos necessários a algum processo do ciclo

� É melhor eliminar um processo que possa rodar novamente desde o início sem gerar efeito negativo no sistema

27

Prevenção de Deadlocks� Como os sistemas operacionais evitam deadlock?

� Garantindo que pelo menos uma das condições para a ocorrência de deadlock nunca seja satisfeita

28

Prevenção de Deadlocks (Cont.)� Ataque ao problema da exclusão mútua

� Utilização de um processo gerente de recurso� Uma impressora pode ser gerenciada por um processo gerente

de impressão (spool), o único que pode requerer a posse física da impressorada impressora

� Os gerentes de impressão, em geral, são programados para iniciar a impressão apenas depois que toda a saída esteja disponível

� Desse modo, não se tem deadlock� Deve-se evitar entregar um recurso, quando ele não for de fato

mais necessário� Deve-se tentar garantir de que o mínimo possível de processos

está precisando de recursos

29

Prevenção de Deadlocks (Cont.)� Ataque ao problema da posse e da espera

� Impedir processos de manter a posse de recursos enquanto esperam por outros recursos

� Uma forma de alcançar isso é exigir que todos os � Uma forma de alcançar isso é exigir que todos os processos requisitem todos os recursos de que precisam, antes de iniciar a execução

� Se um ou mais recursos estiverem alocados a outros processos, nenhum desses recursos será alocado ao processo, que aguarda pelos recursos

30

Prevenção de Deadlocks (Cont.)� Todos os processos conhecem com antecedência quantos e

quais recursos são necessários à sua execução?� Não. Essa informação está disponível apenas ao longo do

processamentoprocessamento

� Os recursos não são usados de modo ótimo, quando esse método é utilizado� Exemplo: um processo que lê uma unidade de fita, analisa-os

durante 01 hora, só depois envia o resultado para uma fita de saída, bem como para um plotter

� A unidade de fita de saída e o plotter estão sendo ocupados desnecessariamente

31

Prevenção de Deadlocks (Cont.)� Uma outra forma de tratar da posse e espera é exigir que

um processo que solicita um recurso libere, primeiramente, todos os recursos e depois tente adquirir de uma vez todos os recursos necessários

� Ataque ao problema da condição de não-preempção� Ataque ao problema da condição de não-preempção� Apenas recursos não-preemptíveis� É ainda menos promissora do que a condição de posse e

espera� Tomar à força uma impressora de um processo no meio

da impressão de resultados pode até evitar o deadlock, mas transgride a condição de não-preempção

32

Prevenção de Deadlocks (Cont.)� Todas as três condições anteriores não se mostram

atrativas para resolver a questão dos deadlocks

� Ataque ao problema da condição de espera circular� Uma maneira de abordar o problema é seguir a regra de � Uma maneira de abordar o problema é seguir a regra de

que um processo só está autorizado a usar apenas um recurso por vez

� Se precisar de um segundo recurso ele deve liberar o primeiro

� Para um processo que precisa copiar o conteúdo de uma fita para a impressora esta restrição é inaceitável

33

Prevenção de Deadlocks (Cont.)� Uma outra forma é utilizar uma numeração global para todos

os recursos� E adotar a regra: os processos podem solicitar recursos sempre

que necessário, mas todas as solicitações precisam ser feitas em ordem numéricaem ordem numérica� Um processo tem de solicitar primeiro a impressora e depois a

unidade de fita, não de modo inverso

� Com esta regra o grafo de alocação de recursos nunca conterá ciclos

34

Prevenção de Deadlocks (Cont.)

35

Prevenção de Deadlocks (Cont.)� Uma variação do algoritmo é forçar os processos

solicitem seus recursos numa ordem estritamente crescente e insistir no fato de que nenhum processo possa adquirir um recurso de numeração menor do que possa adquirir um recurso de numeração menor do que qualquer um que ele já possua

� Depois de utilizar os recursos, por exemplo 9 e 10, e liberá-los, o mesmo processo poderá solicitar o recurso 1 sem problema

36

Prevenção de Deadlocks (Cont.)� Apesar de esse método eliminar o problema de deadlocks, é praticamente impossível encontrar uma ordenação que satisfaça a todos os processos

� O número de recursos e seus diferentes usos pode ficar � O número de recursos e seus diferentes usos pode ficar tão grande que nenhum tipo de ordenação funcionará

37

Outras questões� Bloqueio em duas fases

� Deadlocks que não envolvem recursos

� Preterição indefinida

38

Bloqueio em duas fases� Com bases de dados uma operação muito freqüente é a

de solicitar o bloqueio de um conjunto de registros, para então atualizá-los

� Quando muitos processos estiverem rodando ao � Quando muitos processos estiverem rodando ao mesmo tempo, existe uma possibilidade grande de ocorrer deadlock

� Para tratar isso é usada a abordagem do bloqueio em duas fases

39

Bloqueio em duas fases (Cont.)� Na primeira fase o processo tenta bloquear todos os

registros que precisa, um de cada vez� Se tiver sucesso ele começa a segunda fase, realizando as

atualizações e liberando os registros bloqueados� Nenhum trabalho é executado na primeira fase� Nenhum trabalho é executado na primeira fase� Se durante a primeira fase algum dos registros já estiver

bloqueado, o processo simplesmente libera todos os bloqueios a registros efetuados por ele e recomeça a primeira fase

� Esse algoritmo só funciona em situações onde o programador organizou cuidadosamente as coisas, de modo que o programa possa parar em qualquer ponto da primeira fase, podendo ser retomado depois

40

Deadklocks que não envolvem

recursos� Pode ocorrer deadlock entre processos, quando um

aguarda que o outro faça algo

� Ocorre muitas fezes com semáforos

� Se, por exemplo, a operação DOWN sobre dois � Se, por exemplo, a operação DOWN sobre dois semáforos for executada na ordem errada, pode ocorrer uma situação de deadlock

41

Preterição indefinida� Um problema, no que diz respeito ao deadlock, é

quando um processo é preterido indefinidamente pelo algoritmo que concede o direito de uso a determinados recursosrecursos

� As políticas utilizadas para subsidiar decisões para alocação de recursos, apesar de parecerem razoáveis, podem fazer com que alguns processos nunca sejam servidos, mesmo não estando em deadlock

� Por exemplo, a alocação da impressora

42

Preterição indefinida (Cont.)� Um algoritmo justo é o que utiliza a regra de alocar a

impressora ao processo que tiver o menor arquivo a ser impresso

� Em um sistema muito carregado, suponha que um � Em um sistema muito carregado, suponha que um processo tem um arquivo imenso a ser impresso

� O que pode acontecer com esse processo? Ele terá seu arquivo impresso? Por que?

� Starvation

43

Preterição indefinida (Cont.)� A preterição por tempo indeterminado pode ser

resolvida usando a política de alocação baseada na regra FIFO

44

Exercícios� Defina deadlock.� Quais os tipos de recursos considerado em deadlocks?� Em que situações podem ocorrer deadlocks?� Quais as condições de ocorrência de deadlocks? Explique � Quais as condições de ocorrência de deadlocks? Explique

cada uma delas.� Como se pode modelar deadlocks?� Elabore uma situação onde vários processos e vários

recursos estão envolvidos. Em seguida modele, utilizando grafos dirigidos, uma situação para demonstrar, utilizando o algoritmo para detecção de ciclos, como detectar deadlocks.

45

Exercícios (Cont.)� Como um sistema pode se recuperar de uma situação

de deadlock?

� Como pode ser feita a prevenção de deadlocks?

� Explique em que situações pode ocorrer deadlock sem � Explique em que situações pode ocorrer deadlock sem o envolvimento de recursos.

� Um processo pode sofrer starvation? Se sim, quando?

46