7. DEADLOCK
1. Recursos: é qualquer objeto ao qual deva ser dado acesso exclusivo para cada processo. Recursos podem ser dispositivos de hardware ou trechos de informação. Para a utilização de um recurso, o processo deve realizar a seguinte seqüência: requisitar o recurso; utilizar o recurso e liberar o recurso. Se um recurso não estiver disponível quando for requisitado, o processo que o requisitou é forçado a aguardar, sendo dois métodos utilizados: 1) o processo é bloqueado e acordado quando o recurso estiver disponível; 2) é enviado um código de erro ao processo indicando que a requisição falhou sendo, então, que o próprio processo deve decidir a ação a tomar (ex: aguardar algum tempo e pedir novamente).
2. Modelamento de Deadlock: o deadlock ocorre quando cada processo de um conjunto de processos está esperando por um evento que apenas outro processo do mesmo conjunto pode causar. Em muitos casos, o evento esperado é a liberação de um recurso qualquer, isto é, cada membro do conjunto está esperando pela liberação de um recurso que apenas outro membro do conjunto pode liberar. Condições para que ocorra um deadlock: 1) Exclusão Mútua: cada recurso ou está associado a exatamente um processo ou está disponível; 2) Posse e espera: um processo que já possui algum recurso pode requisitar outros e aguardar por sua liberação; 3) Não existe preempção: recursos dados a um processo não podem ser tomados de volta, precisam ser liberados pelo processo; 4) Espera Circular: deve haver uma cadeia circular de dois ou mais processos, cada um dos quais aguardando um recurso em posse do próximo membro da cadeia. Para modelar a distribuição dos recursos e das requisições vamos utilizar um grafo com dois tipos de nós: circular (processos) e retangular (recursos).
Suponhamos a existência de 3 processos (A B C) e 3 recursos (R S T). Supor a seguinte ordem:
A: pede R, pede S, libera R, libera S;
B: pede S, pede T, libera S, libera T;
C: pede T, pede R, libera T, libera R.
Se o SO executa cada um dos processos por vez, esperando um terminar antes de executar o outro, não haverá deadlock (não há paralelismo). Se quisermos realizar o escalonamento dos processos no método de round-robin, as requisições poderão ocorrer da seguinte forma:
A pede R; B pede S; C pede T; A pede S; B pede T; C pede R.
Então ocorre uma cadeia circular de processos e recursos, indicando um deadlock.
Vamos ver agora as 4 estratégias para se tratar um deadlock:
1. O Algoritmo da Avestruz (ignorar o problema): mais simples estratégia, consiste em fazer como se faz uma avestruz diante a uma situação de perigo: colocar a cabeça num buraco e fingir que o problema inexiste. É a solução mais utilizada, pois há baixa probabilidade de ocorrência de deadlock e baixo custo. O UNIX utiliza este método.
2. Detecção e Recuperação: o SO apenas monitora as requisições e liberações de recursos, através da manutenção de um grafo de recursos, que é constantemente atualizado e onde se verifica a ocorrência de ciclos, se houver algum ciclo, um dos processos deve ser morto. Se o ciclo ainda permanecer, outro processo deve ser morto e assim sucessivamente, até que o ciclo seja quebrado. Técnica utilizada em computadores grandes geralmente em batch, onde um processo pode ser morto e mais tarde reinicializado. Deve-se ter o cuidado de que qualquer arquivo modificado pelo processo morto deve ser restaurado ao seu estado original antes de iniciar o processo novamente.
3. Prevenção de Deadlock (negando uma das quatro condições necessárias): consiste em impor restrições aos processos de forma que o deadlock seja impossível. Possibilidades de eliminar as condições:
1) Exclusão Mútua: para alguns recursos é necessária a exclusão mútua, pois não pode haver acesso por dois processos simultaneamente e nem sempre a técnica de spool pode ser empregada. Portanto esta condição não pode ser eliminada.
2) Posse e Espera: uma forma de negar essa condição é fazer com que cada processo requisite todos os recursos que irá necessitar antes de iniciar a execução, Se todos os recursos estiverem disponíveis então ele é executado, senão, o processo deve aguardar. O problema é que muitos processos não sabem com antecedência quais os recursos de que irão necessitar até começar a execução e também os recursos não serão utilizados otimamente. Uma outra forma de quebrar essa condição é fazer com que, para pedir um novo recurso, o processo deva liberar temporariamente todos aqueles que possui e somente se conseguir o novo recurso é que pode pegar os anteriores de volta.
3) Não preempção: essa condição não pode ser quebrada, pois tomar um recurso de um processo para entregá-lo a outro gera confusão.
4) Espera circular: para evitar que se formem ciclos fechados no grafo de recursos devemos fazer com que cada processo só possa ter um recurso por vez e se desejar outro, deve liberar o que possui (isto impossibilitaria coisas simples como cópia de uma fita para outra) ou senão podemos dar uma numeração global a todos os recursos e os processos só podem requisitar recursos em ordem numérica crescente. O problema é que é difícil encontrar uma numeração que satisfaça a maioria das possíveis condições de acesso.
4. Evitação Dinâmica de Deadlock: procura-se evitar o deadlock sem impor restrições aos processos, isto é possível desde que alguma informação sobre a utilização de recursos pelo processo seja disponível antecipadamente ao SO. Vamos analisar maneiras de se conseguir isso:
1. Algoritmo do Banqueiro para um único Recurso: usado para evitar deadlocks consiste em simular as decisões de um banqueiro no empréstimo de certa quantia de dinheiro sujeita a certas condições. No exemplo abaixo temos 4 clientes (A B C D) cada um especificou o número máximo de crédito que precisará, mas eles não precisam de todas elas imediatamente, de forma que o banqueiro reservou 10 unidades para atender todos os pedidos (totalizando 32 unidades).
Disponível:10 |
Cada cliente pode em cada momento realizar um pedido desde que não ultrapasse seu limite de crédito e o banqueiro pode escolher o momento de atendimento dos pedidos realizados. Após o recebimento de todo o crédito que especificou inicialmente o cliente se compromete a devolver tudo. O banqueiro deve analisar para que não entre numa situação difícil. |
Chamamos de estado, a situação dos empréstimos e dos recursos ainda disponíveis em um dado momento.
Disponível:2 |
O exemplo ao lado demonstra um estado seguro, pois existe uma seqüência de outros estados que leva a que todos os clientes recebam seus empréstimos até seus limites de crédito. O banqueiro pode emprestar 2 unidades à C pegar a devolução da mesma (4) emprestar à B, pegar as 5 unidades de volta e emprestar à A, pegar as 6 unidades de volta e emprestar 3 delas à D, pegando então as 7 unidades de volta, garantindo o atendimento a todos os clientes. Se por exemplo o cliente B fizesse um pedido de mais uma unidade (2) teríamos um estado não seguro, pois não há forma do banqueiro garantir o atendimento de todos os pedidos, podendo vir a gerar um deadlock. Ainda não haverá um deadlock, pois os valores de máximo não precisam necessariamente ser atingido. Por exemplo, o cliente D pode decidir que não precisa mais de novos recursos e devolver os 4 que pediu, voltando novamente a uma situação segura. Mas o banqueiro não pode contar com isso, então para cada pedido que chega, o banqueiro deve verificar se conceder o mesmo leva a uma situação segura, verificando se o disponível é suficiente para atender o cliente mais próximo de seu máximo. Se for, finge que esse cliente já devolveu tudo que possuía, marca o mesmo como terminado e verifica se pode atender o cliente mais próximo do máximo entre os que restam. Se ele puder levar a bom termo esse processo, atendendo todos os clientes então o estado é seguro. |
- Algoritmo do Banqueiro para Vários Recursos: montamos duas matrizes, uma dos recursos entregue e outra de recursos ainda necessários, sendo que cada linha das matrizes corresponde a um processo e cada coluna a um tipo de recurso:
FALTANDO
|
ENTREGUES
|
Temos também 3 vetores E, P e D que indicam:
E (recursos existentes) = [ 6 3 4 2 ]
P (recursos possuídos por algum processo) = [ 5 3 2 2 ]
D (recursos disponíveis) = [ 1 0 2 0 ]
Então os processo precisam avisar com antecedência as suas necessidades de recursos e para descobrir se o estado é seguro devemos: 1) procurar uma linha L cujos recursos ainda necessários sejam todos menores que os correspondentes valores no vetor D. Se não existir essa linha, o sistema entrará em deadlock e o sistema não é seguro; 2) Assumir que o processo da linha L requereu todos os recursos e terminou, liberando todos os recursos que estava ocupando; 3) repetir os dois passos anteriores até que todos os processos sejam marcados como terminados. Se isto for conseguido, o estado é seguro. O problema com este algoritmo é que os processo raramente sabem com antecedência a quantidade máxima de recursos que necessitarão e, além disso, o número de processo no sistema varia dinamicamente, o que invalida as análises realizadas.