Deadlock

- Introdução

- Bases

- Prevenção

- Exclusão Mútua

- Hold and wait

- Espera em circulo fechado

- Sem preempção

- Inibição

- Detecção e Recuperação

- Manual de administração do Deadlock

- Modelo Deadlock do Sistema

Introdução

Deadlock é um termo empregado para traduzir um problema que ocorre quando um grupo ou conjunto de processos compete entre si. Este capítulo pretende generalizar os métodos a aplicar fim de encontrar uma solução através de um gerente de recursos. O problema é especialmente interessante porque, em geral, o aparecimento do mesmo depende das características de dois ou mais programas diferentes e dos respectivos processos a executar pelos diferentes programas ao mesmo tempo. Os programas podem ser executados de forma repetitiva usando diferentes processos sem que se passe à situação Deadlock. No entanto basta um único processo padrão complicado para se entrar em Deadlock. Há três estratégias gerais para evitar o Deadlock: prevenção, inibição, e detecção e recuperação.

Voltar ao topo

10.1 Bases

Dijkstra ilustra a situação de Deadlock através da seguinte figura:

Ou seja, o Processo 1 reserva para si o Recurso 1, por sua vez o Processo 2 e o Processo 3 reservam respectivamente para si o Recurso 2 e o Recurso 3. Por exemplo se um dos outros processos necessitar de um dos recursos anteriormente reservados por outros processos, como acontece no diagrama da figura anterior entramos numa situação de Deadlock.

Nenhum dos processos pode continuar, porque para isso acontecer os mesmos necessitariam que os recursos reservados fossem disponibilizados. A menos que um dos processos detecte a situação e abandonando o pedido do recurso anteriormente reservado por outro processo, e liberte ao mesmo tempo o recurso por si reservado. Com isso, há a possibilidade de pelo menos um processo correr.

O gerente de recurso e outros processos do sistema operativo podem ser envolvidos na situação Deadlock. Suponhamos um processo de aplicação muito grande, reserva para si o recurso do disco. Quando o processo de aplicação for activado, foi reservada quase toda a memória primária pelo gerente de memória. Agora suponhamos que o gestor do disco é um processo que necessita igualmente de memória primária. Como o processo de aplicação não deixou memória suficiente para satisfazer o pedido do disco, ambos os processos entram em Deadlock, como é demonstrado na seguinte figura.

Deadlock também acontece em muitas situações da vida quotidiana. Provavelmente o exemplo mais concreto são os famosos engarrafamentos de automóveis no tráfego urbano. O engarrafamento pode acontecer numa situação em que os carros vêm de quatro estradas diferentes e encontram-se no mesmo cruzamento. No exemplo dado na próxima figura, um fluxo de automóveis que viaja ao longo de uma rua com sentido único corresponde a um processo e cada intersecção corresponde a um recurso compartilhado. Os automóveis que se deslocam para Norte interrompem o trafego que vem de Este, por sua vez os que se deslocam para Este, para Sul e para Oeste, interrompem respectivamente o tráfego que se desloca para Norte, Este e Sul, ou seja, o tráfego que se desloca para Norte reserva para si a intersecção situada a Sudoeste, solicitando também para si a intersecção situada a Noroeste. No entanto essa intersecção já está reservada para o tráfego que se desloca para Este. Por sua vez o tráfego que se desloca para Este reserva para si a intersecção situada a Noroeste, solicitando também para si a intersecção situada a Nordeste. No entanto essa intersecção já está reservada para o tráfego que se desloca para Sul. Por sua vez o tráfego que se desloca para Sul reserva para si a intersecção situada a Nordeste, solicitando para si a intersecção situada a Sudeste. No entanto essa intersecção já está reservada para o tráfego que se desloca para Oeste. Por sua vez o tráfego que se desloca para Oeste reserva para si a intersecção situada a Sudeste , solicitando também para si a intersecção situada a Sudoeste. No entanto essa intersecção já está reservada para o tráfego que se desloca para Norte. Entra-se assim numa situação em que os recursos (intersecções) estão ocupadas por um processo (tráfego), entramos assim na situação de Deadlock.

No Capítulo 7 do livro, o conceito Deadlock foi introduzido como um efeito colateral de estratégias de sincronização, porque dois processos ao actualizar duas variáveis compartilhadas, usam uma lock flag um para requisitar os valores de uma variável, o outro para actualizar valor da variável. Situações semelhantes ocorrem periodicamente num conjunto de processos que estão a compartilhar recursos: De facto, isso é porque um recurso é definido como algo que um processo precisa para correr – consumivel ou reutilizável. Memória, os drives de uma impressora, uma drive de disquetes são tudo exemplos de recursos. Um processo pode bloquear quando pedido qualquer um destes recursos e o os mesmos estão ocupados; assim qualquer um pode contribuir para entrar na situação Deadlock.

Deadlock é uma condição global, nunca um local. Se nós analisássemos um programa qualquer para que o processo envolvido em Deadlock, nós não encontraríamos nenhum erro plausível. O problema não consiste num único processo, mas num conjunto de processos. Como é que então um programador pode lidar com o Deadlock? Um único programa, regra geral não pode detectar o Deadlock, porque este fica bloqueado e é impossibilitado de usar o processador para realizar qualquer trabalho. A detecção do Deadlock deve ser comandado pelo sistema operativo. Como os sistemas operativos podem ser construídos a fim de assegurar que o Deadlock é manipulado correctamente? Há quatro aproximações básicas:

· Prevenção

· Inibição

· Detecção e recuperação

· Deixe administração do Deadlock para o operador de computador

Voltar ao topo

10.1.1 Prevenção

Para ocorrer o Deadlock no sistema, todas os quatro condições que iremos em seguida indicar - exclusão mútua, “Hold and wait”, espera em circulo fechado e sistema operativo sem preempção - tem que acontecer ao mesmo tempo. As estratégias de prevenção permitem que pelo menos uma das condições nunca aconteça. A condição de exclusão mútua não pode deixar de acontecer, desde que esta assegure que um recurso só pode ser usado por um processo de cada vez. Por exemplo, se um programa de aplicação está a ser executado por um único processo, este não permite que este seja utilizado por outro processo por mais insignificante que ele seja. No UNIX é possível violar a condição da exclusão mútua, na utilização de alguns recursos, no entanto não é uma condição universal em todos os tipos de recurso de um sistema convencional.:

Voltar ao topo

· Exclusão mútua - Se um processo alocar um recurso particular, tem uso exclusivo do mesmo enquanto este estiver alocado a si.

Voltar ao topo

· “Hold and wait” - Um processo pode assegurar um recurso ao mesmo tempo que o mesmo está pedido por um outro processo.

Voltar ao topo

· Espera em circulo fechado – É uma situação que pode surgir na qual um processo p₁ requer o recurso R₁ enquanto o primeiro é solicitado pelo recurso R₂, e o processo p₂ requer R₂ e ao mesmo tempo é solicitado pelo recurso R₁. Pode haver mais do que dois processos envolveram na espera circular.

Voltar ao topo

· Sem preempção - Recursos só podem ser corridos através de um processo, a não ser que exista uma ordem externa. Esta suposição inclui o caso de um processo fazer um pedido para um recurso e este não estar disponível. Então o processo não pode retirar o seu pedido.

Estes condicionamentos acontecem em quase todas estratégias de alocação de recursos de quase todos os sistemas operativos modernos. Um Deadlock é possível apenas se todas estas quatro condições aparecerem simultaneamente no conjunto de processos. Estas condições são consideradas necessárias para um Deadlock (embora a presença deles não é condição suficiente para um Deadlock). As estratégias de prevenção de Deadlock, projectam gerentes de recurso que atacam sempre que existe a violação de uma destas condições. Estas estratégias são fáceis de implementar em certos sistemas, tal como no batch system, mas é impossível assegurar o mesmo para todos os recursos como nos timesharing systems.

Voltar ao topo

10.1.2 Inibição

Estratégias de inibição dependem da capacidade do gerente de recursos para prever os pedidos de alocação e requisições de processos e recursos. Se um pedido conduzir a uma situação de Deadlock, esta estratégias recusarão o pedido. Considera-se que esta táctica prevê e apresenta a informação sobre a actividade do recurso que está a ser utilizado pelo processo. Por exemplo, se um processo indicar com antecedência o número de máximo de recursos por ele utilizado, é possível evitar um Deadlock, isto quando é feito o pedidos de um recurso específico. Esta estratégia é a chamada máxima reivindicação. Recorre a recursos subtilizados recusando alocar algum processo no caso de existir uma potencial situação de Deadlock. Consequentemente, é raramente usado nos sistemas operativos modernos.

Voltar ao topo

10.1.3 Detecção e Recuperação

Alguns sistemas são projectados para permitir distribuição de recursos sem uma intervenção particular. Ao invés, os system checks verificam, ou periodicamente ou sempre que certos eventos acontecem, a existência do Deadlock. Um aspecto difícil desta estratégia é determinar com que frequência é que o algoritmo de detecção deveria ser executado, de forma a que este não desperdice apenas recursos do sistemas. Mas se este não correr frequentemente, o bloqueio de processos e de recursos do sistema está ocupado de uma forma improdutiva até à recuperação do sistema.

Quando um algoritmo de detecção corre, há duas fases. Primeiro é a fase de detecção, durante a qual o sistema é conferido para detectar a existência ou não de Deadlock. Se o sistema estiver na situação Deadlock, este passa a uma segunda fase, recuperação, recorrendo a processos de preempção. Esta recuperação significa que a condição da não preempção foi violada e sendo assim todos os processos serão destruídos. Qualquer trabalho que estes possam ter realizado antes do Deadlock será perdido. A detecção do Deadlock e a estratégia de recuperação é muito usada em sistemas comerciais.

Voltar ao topo

10.1.4 Manual de Administração do Deadlock

Muitos sistemas comerciais não levam muito em conta a possibilidade do aparecimento do Deadlock. Quando este causar danos económicos elevados ao fabricante, o problema Deadlock ganhará outra importância em termos comercias.

Voltar ao topo

10.2 Modelo Deadlock do Sistema

Deadlock do sistema pode ser estudado usando um modelo representativo do estado da distribuição dos recursos dos componentes do sistema. Isto pode ser feito modelando estado do sistema em qualquer momento, analisando então quais são estados de Deadlock. Dado a existência de tal modelo, podemos definir com precisam o que leva ao sistema entrar na situação Deadlock.

Esta secção descreve um modelo de processos e recursos que podem ser traduzidos num modelo matemático preciso.

P é um conjunto de n processos diferentes e R é um conjunto de m recursos diferentes, c_j é o número de unidades do recurso do tipo R_j no sistema. Logo, de que maneira é que os recursos podem ser alocados aos vários processos. Dado que a distribuição de recursos na mudança dos processos é a forma como o processo é executado, o modelo terá que reflectir cada uma destas mudanças. Um modo de mostrar este tipo de comportamento é utilizar um diagrama de estado/transição. Assim o diagrama de estado representa o padrão de pedidos do recurso e respectivas distribuições no sistema, em qualquer instante, ou seja, o diagrama de estado representa o estado do sistema.

S é um conjunto de estados no modelo que representa estados do sistema. O estado inicial é s₀; representa a situação na qual todos os recursos não estão alocados. Enquanto, s_i, representam os outros possíveis estados do sistema, sendo assim cada modelo de estado representa todos os recursos solicitados ou requisitados por cada processo. Para agora, vamos centrar o estudo nas transições estatais. O padrão como são pedidos os recursos e libertados determina se o sistema está desbloqueado.

Um conjunto de processos, P, e um qualquer processo, p_i Î P, poderia causar uma transição de estado que dependente de p_i.

· pedidos de recursos (são designados por uma transição r_i)

· reserva de recursos (são designados por uma transição a_i)

· libertação de recursos (são designados por uma transição d_i)

Sempre que o sistema está no estado s_j Î S, e um evento x_i (x_i é do tipo r_i, ou a_i, ou d_i)ocorre, então dá-se uma mudança de estado do sistema, s_k Î S, que se deve à ocorrência x_i.

Considera-se um modelo que representa a mudanças de estado do sistema. Há que verificar o efeito de uma série de transições. O processo p_i está bloqueado no estado s_j. Se o processo p_i não conseguir efectuar uma transição de estado, o processo fica bloqueado, ou seja, é incapaz de mudar o estado do sistema. Na Figura 4, fica bloqueado o processo p₂ no estado s_j porque todas as transições efectuadas por o estado s_j são causadas por outros processos; nenhum é causado por p₂.

Se p_i ficar bloqueado em s_j, um outro processo diferente de p_i poderia mudar o estado do sistema s_j para o novo estado s_k, onde p_i poderia prosseguir. Se fosse possível determinar as condições para conduzir o estado actual a um no qual o processo p_i fique desbloqueado, isto implicaria que o processo nunca mais fosse executado nestas condições. Por outras palavras, o processo p_i de bloqueia no estado s_j se para todo sk que pode ser alcançado por alguma série de transições de sj, pi é bloqueado ainda em sk. Se há qualquer processo bloquear em um s_k, então este, é o chamado Deadlock State.

Voltar ao topo