UNIVERSIDADE FEDERAL DO CEARÁ

BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO

RONILDO OLIVEIRA DA SILVA

THÁRSIS SALATHIEL DE SOUZA VIANA

SISTEMAS OPERACIONAIS:

DEADLOCKS

QUIXADÁ

2014

SUMÁRIO

RECURSOS ........................................................................................................................ 3

RECURSOS PREEMPTÍVEIS E NÃO PREEMPTÍVEIS...................................................... 3

INTRODUÇÃO AOS DEADLOCKS ..................................................................................... 4

CONDIÇÕES PARA OCORRÊNCIA DE IMPASSE DE RECURSO.................................... 4

MODELAGEM DE IMPASSES ............................................................................................ 4

ALGORITMO DO AVESTRUZ ............................................................................................. 6

DETECÇÃO E RECUPERAÇÃO DE DEADLOCKS ............................................................ 6

DETECÇÃO DE DEADLOCKS ......................................................................................... 6

RECUPERAÇÃO DE DEADLOCKS ................................................................................. 8

EVITANDO DEADLOCKS ................................................................................................... 8

ALGORITMO DO BANQUEIRO PARA UM RECURSO ................................................... 8

ALGORITMO DO BANQUEIRO PARA N RECURSOS .................................................... 9

PREVENÇÃO DE DEADLOCKS ....................................................................................... 10

REFERÊNCIAS BIBLIOGRÁFICAS .................................................................................. 11

3

RECURSOS

Sistemas operacionais possuem vários tipos de resursos, cada um deles

apropriados para ser utilizado apenas por um processo de cada vez. Recursos comuns a

nós usuários, podem incluir impressoras, plotters, discos, fitas… Já de um modo mais

interno ao sistema, encontramos, tabelas internas de sistema, estados de um programa,

referências, flags, etc. Caso mais de um processo utilizar a mesma impressora,

presenciaremos um deadlock ou impasse. Essa situação inerentemente ocasiona num

sistema, estados corrompidos. Objetivanso evitar tais problemas, um sistema operacional

deve ser suficientemente capaz de trazer garantias exclusivas e temporárias ao processo

a certos recursos computacionais.

“ Em resumo, um recurso é aìgo que pode ser, usado por somente um único processo

em um dado instante de tempo” (TANENBAUM, 2008, p 118).

RECURSOS PREEMPTÍVEIS E NÃO PREEMPTÍVEIS

Há dois tpos de recursos:

Preemptíveis: É um recurso que pode ser retirado do processo proprietário sem

prejuízos, ou seja, um recurso já usado que possa servir outro processo.

o Exemplo: uma parte alocada de memória;

Não preemptíveis: Se manifesta na situação do recurso preemptível, ele não pode

ser tomado por outro processo em estado de uso.

o Exemplo: um processo de gravação de disco óptico.

Em geral, deadlocks envolvem recursos não-preemptíveis. Em casos que envolvem

recursos preemptíveis, podem ser resolvidas realocando recursos de um processo para

outro.

Tais processos, obedecem uma sequencia lógica de aquisição de recursos:

Requisitar o recurso. Todo processo deve requisitá-lo antes de utilizá-lo, caso a

resposta seja negativa, o mesmo deve continuar (loop).

Usar o recurso. Dentro da garantia de que o processo não será intenrrompido por

tentativa de utilização por outro processo.

Liberar o recurso.

4

INTRODUÇÃO AOS DEADLOCKS

Deadlock pode ser definido como: “Um conjunto de processos estará em situação

de impasse (deadlock) se todo processo pertencente ao conjunto estiver esperando por

um evento que somente outro processo desse mesmo conjunto poderá fazer acontecer”

(TANENBAUM, 2008, p 118). Assim um processo espera o outro e nenhum será

executado. Nos exemplos a seguir considere o sistema como possuindo apenas um único

thread e com preempção desativada.

A maioria dos deadlocks aconteceu quando determinado processo A necessita de

um recurso R mais o recurso R esta sendo usando por um processo B, levando a uma

situação de impasse. Esse tipo de impasse e conhecido como impasse de recursos.

Quando o processo B requer um recurso que o processo A esta usando e só irá liberar

quando conseguir posse do recurso R, temos um impasse circular onde nenhum dos

processos será executado assim a CPU ficará ansiosa.

CONDIÇÕES PARA OCORRÊNCIA DE IMPASSE DE RECURSO

1. Exclusão mútua: Um processo pode ter capacidade alocar um determinado recurso

só para si, assim bloqueando o recurso.

2. Posse e espera: Um processo mesmo com um recurso alocado pode solicitar

novos recursos.

3. Não preempção: Um processo não tem a capacidade de interromper outro para

alocar o recurso que estava sendo usado.

4. Espera circular: Um processo pode usar um recurso e tentar alocar outro que esta

sendo usado por outro processo que por sua vez tenta alocar o recurso do

primeiro.

Essas quatros condições foram mostradas por Coffman et al. (1971). E elas devem existir

em conjunto para que o impasse de recurso possa acontecer.

MODELAGEM DE IMPASSES

Se em um determinado sistema ocorresse as seguintes situações:

1. A requisita R

2. B requisita S

3. C requisita T

4. A requisita S

5

5. B requisita T

6. C requisita R

Onde de A, B e C são processos e R, S e T são recursos.

Como saber se está havendo impasse? Para visualizar a ocorrência de impasses

Holt (1972) mostrou que era possível desenhar esse sistema em forma de diagramas a

fim de facilitar a visualização de impasses.

Um exemplo pode ser visualizado na figura 6.3(a) onde o circulo A representa um

processo e o quadrado R um recurso. A seta saindo do recurso em direção ao processo

significa que o processo já esta de posse daquele recurso. O inverso, a seta saindo do

recurso em direção ao processo [Figura 6.3 (b)], indica que o processo B esta esperando

pelo recurso R. Na figura 6.3 (c) vemos como a visualização de impasses se torna mais

fácil. Assim o exemplo inicial pode ser melhor visualizado na figura abaixo. È possível

notar que essa sequencia irá gerar um impasse.

6

ALGORITMO DO AVESTRUZ

Deadlocks podem ser tratados, porém fica uma dúvida, se a implementação

corretiva/preventiva traz custo/benefício. Geralmente, esses artifícios utilizados na

detecção e tratamento de situações de impasse produzem uma carga de processamento

muito grande, às vezes, ocasionando danos mais severos que o próprio deadlock, além

de ser uma manobra de alto custo sendo, necessário, ignorar tal evento.

É aí que se “utiliza” do algoritmo do avestruz.

A estratégia mais simples para tratamento, porém não muito eficiente do deadlock,

conhecida como Algoritmo do Avestruz, é simplesmente ignorar a situação ocorrente.

Grande parte dos sistemas operacionais (Unix e Windows), defendem que a

frequência de ocorrência deste tipo de evento é baixa demais para que seja necessário

sobrecarregar a CPU com códigos extras de tratamento, e que, ocasionalmente, é

tolerável reiniciar o sistema como uma ação corretiva.

DETECÇÃO E RECUPERAÇÃO DE DEADLOCKS

Uma técnica usada para o tratamento de deadlocks, é simplesmente deixar com

que os deadlocks ocorram. Desta forma só será necessário detecta-los e recupera-los.

DETECÇÃO DE DEADLOCKS

7

Considere um sistema em que:

1. O processo A possui o recurso R e requisita o recurso S.

2. O processo B nada possui, mas requisita o recurso T.

3. O processo C nada possui, mas requisita o recurso S.

4. O processo D possui o recurso U e requisita os recursos S e T.

5. O processo E possui o recurso T e requisita o recurso V.

6. O processo F possui o recurso W e requisita o recurso S.

7. O processo G possui o recurso V e requisita o recurso U.

Como saber se neste caso esta havendo um impasse? E se estiver como saber quais

processos estão evolvidos?

Para visualizar melhor podemos usar o grafo de recursos, disponível na figura 6.5.

Visualmente é muito fácil perceber que essa situação resultar um impasse, pois

observando a figura 6.5(a) é possível notar um circulo, destacado na figura 6.5(b). Assim,

tudo que precisamos é de algum algoritmo que detecte esses círculos. Um algoritmo

simples é proposto abaixo:

1. Para cada nó - N no grafo - execute os cinco passos seguintes, usando N como nó

inicial.

2. Inicialize L como uma lista vazia e assinale todos os arcos como desmarcados.

3. Insira o nó atual no final da lista L e verifique se o nó agora aparece em L duas

vezes. Em caso afirmativo, o grafo contém um ciclo (assinalado em L) e o algoritmo

termina.

4. A partir do referido nó, verifique se existe algum arco de saída desmarcado. Em

caso afirmativo, vá para o passo 5; do contrário, vá para o passo 6.

5. Escolha aleatoriamente um arco de saída desmarcado e marque-o. Então siga

esse arco para obter o novo nó atual e vá para o passo 3.

8

6. Se esse nó for o inicial, o grafo não conterá ciclo algum e algoritmo terminará.

Senão, o final foi alcançado. Remova-o e volte para o nó anterior - isto é, aquele

que era atual antes desse -, marque-o como atual e vá para o passo 3.

RECUPERAÇÃO DE DEADLOCKS

Agora que o deadlock já foi detectado, o que fazer em seguida? È necessário

recuperar o sistema e coloca-lo novamente em uma situação sem deadlocks. Para isso

existem três técnicas:

1. Recuperação por meio de preempção: Neste caso o processo tem a capacidade de

retirar um determinado recurso de outro processo. Essa tecnica resolveria o

problema para determinados casos em que o recurso pode ser desalocado sem

causar grandes danos, mas isso depende muito da natureza do processo que está

usando aquele recurso.

2. Recuperação por meio de retrocesso: Essa técnica consiste em salvar de tempos

em tempos os processos em arquivos, como um backup. Caso algum deadlock

ocorra o sistema ira procurar por um “backup” do processo que está causando o

deadlock e ira substituir o processo pelo seu “backup”. Assim o processo volta a

um estado em que não havia deadlocks.

3. Recuperação por meio da eliminação de processos: A maneira mais simples de se

evitar um deadlock é simplemente matando o processo que esta causando o

deadlock. É notável que essa não é a melhor opção pois muitos processos quando

“mortos” perdem todas suas informações.

EVITANDO DEADLOCKS

ALGORITMO DO BANQUEIRO PARA UM RECURSO

Um algoritmo de escalonamento que pode evitar deadlocks, desenvolvido por

Dijkstra (1965), é conhecido como algoritmo do banqueiro e constitui uma extensão do

algoritmo de detecção de deadlocks. O algoritmo citado é modelado da seguinte maneira:

um banqueiro de uma pequena cidade pode negociar com um grupo de clientes para os

quais ele libera linhas de crédito. O que o algoritmo faz é verificar se a liberação de uma

requisição é capaz de levar a um estado inseguro. Em caso positivo, a requisição será

negada. Se a liberação de uma requisição levar a um estado seguro, ela será atendida.

Na Figura 6.11(a) vemos quatro clientes, A, B, C e D. A cada um deles foi alocado certo

número de unidades de crédito. O banqueiro sabe que nem todos os clientes Precisam

9

imediatamente de todas as suas unidades de crédito, de modo que ele tem em caixa

somente dez unidades de crédito para servi-los, em vez de 22 unidades. (Nessa analogia,

os clientes são os processos, as unidades de crédito são, digamos, unidades de fita, e o

banqueiro é o sistema operacional).

ALGORITMO DO BANQUEIRO PARA N RECURSOS

Na Figura 6.12 vemos duas matrizes. A primeira, do lado esquerdo, mostra quanto de cada recurso está atualmente alocado para cada um dos cinco processos. A matriz do lado direito mostra de quantos recursos cada processo ainda precisa para completar sua execução. Como no caso de um único tipo de recurso, os processos devem declarar antes da execução todos os recursos de que vão precisar, para que o sistema possa a cada instante calcular a matriz do lado direito.

10

Os três vetores à direita da figura mostram, respectivamente, os recursos

existentes, E, os recursos alocados, P, e os recursos disponíveis, A. E revela que o

sistema tem seis unidades de fita, três plotters, quatro impressoras e duas unidades de

CD-ROM. Desses recursos, cinco acionadores de fita, três plotters, duas impressoras e

duas unidades de CD-ROM se encontram alocados. Esse fato pode ser observado

somando-se as quatro colunas de recursos da matriz do lado esquerdo. O vetor de

recursos disponíveis é simplesmente a diferença entre aquilo que o sistema tem e aquilo

que está atualmente em uso pelos processos.

PREVENÇÃO DE DEADLOCKS

Evitar deadlocks é algo praticamente impossível, pois o sistema teria que saber

sobre ações futuras dos processos. Então para evitar os deadlocks temos que voltar as

quatro condições criadas por Coffman et al. (1971). Como todas as condições precisam

ser verdadeiras para que haja impasse de recurso, basta “quebrar” uma condição que os

deadlocks seriam evitados.

1. Atacando a condição de exclusão mutua: Essa condição diz respeito a um

determinado processo poder alocar certo recurso só para si. Para atacar essa

condição podemos usar uma técnica chamada Spooling. Assim se dois processos

precisam de uma impressora, por exemplo, eles jogam suas saias no spool e a

impressora imprime todo spool. Essa técnica pode da errada caso o spool fique

cheio antes do processo terminar de colocar sua saída.

11

2. Atacando a condição de posse e espera: Um processo em condição de posse e

espera já possui um recurso e deseja alocar outro. Uma forma de atacar isso seria

ter pose de uma lista de todos os recursos que o processo vai usar. Mas essa

técnica é ineficaz e praticamente impossível, pois nem mesmo o processo sabe

quais os recursos que ele ira usar. Alem disso um determinado processo poderia

precisar de certo recurso por apenas alguns segundos, mesmo assim o processo

só usa esse recurso no final de sua execução que pode demorar muito tempo.

Assim o recurso ficaria muito tempo inutilizável.

3. Atacando a condição de não preempção: A condição de não preempção garante

que nenhum processo ira “tomar” recursos de outros. Uma forma simples de atacar

essa condição e ativando a preempção. Esse caminho é visivelmente ineficiente

pois alguns recursos, como um impressora, não podem simplesmente parar o que

estão fazendo e começar a fazer outra coisa.

4. Atacando a condição de espera circular: A espera circular e o caso em que

determinado processo espera um recurso enquanto está de posse de outro. Para

atacar essa condição uma técnica aceitável seria enumerar os recursos assim

determinado processo só poderia acessar recursos em uma ordem numérica. O

único problema e encontrar uma ordem numérica que satisfaça todos os

processos.

REFERÊNCIAS BIBLIOGRÁFICAS

TANENBAUM, Andrew S. Sistemas Operacionais Modernos. 2. Ed. Prentice Hall

(Pearson), 2003.