Engenharia Informática

Sistemas Operativos I

Trabalho Teórico-Prático N.º1 : Capitulo 10 – Deadlock

Deadlock é um significativo problema de coordenações relativo a sistemas operativos, que quando surge leva os processos a entrarem em ciclos viciosos, esperando indefinidamente por libertação de hardware, libertação essa que depende ciclicamente uns dos outros, senão vejamos o seguinte exemplo:

Processo1 Processo2 Processo3

Recurso1 Recurso2 Recurso3

Legenda:

: Processo possui recurso

: Processo requisita recurso

O requisito nunca pode ser satisfeito porque o recurso está “preso” por outro processo, que por sua vez esta bloqueado, esperando que o recurso do primeiro processo esteja liberto. Sem que um dos processos seja capaz de libertar um recurso, nenhum dos outros processos chega a correr.

Pode-se facilmente observar uma situação de Deadlock na vida real, observando o tráfico automobilístico. Imaginemos uma avenida com a forma quadrada com ruas de sentido único, com filas de carros todos seguidos uns aos outros. Cada fila de carros corresponde a um processo à espera que a intercessão, ou seja o recurso, se liberte para poder passar.

O Deadlock é uma situação global, não uma local, isto é, se procurarmos num programa por um qualquer processo que leve a uma situação de Deadlock, não iremos encontrar nada. A fonte do problema nunca residirá num único processo, mas sim numa acção colectiva de um grupo de processos.

Como pode ser evitada uma situação de Deadlock, certamente não serão os processos a faze-lo, pois quando detectariam a situação já os recursos estariam bloqueados, e seriam incapazes de utilizar o processador para quer que seja. Resta então essa função ficar a cargo do sistema operativo. E pode ser feito através de 4 processos básicos:

- Prevenção:

Suponhamos que as seguintes condições acontecem quando um processo

usa recursos:

§ Exclusão Mutua – Assim que um processo aloque um recurso, possui o exclusivo uso desse recurso. Nenhum outro processo pode usar um recurso esta alocado a outro processo.

§ Reserva e Espera – Um processo pode reservar um recurso enquanto requisita outro.

§ Espera Circular – Uma situação que pode surgir quando o processo P₁ reserva o recurso R₁ e requisita o recurso R₂, enquanto o processo P₂, já com o recurso R₂ reservado para si, requisita o recurso R₁. Este problema pode também surgir num caso com mais de dois processos.

§ Sem Preemptividade – Os recursos podem ser libertos somente por uma acção explicita do processo que o reserva, sem hipótese de ser libertado por uma acção exterior ao processo. Mesmo que o recurso exista, o processo não se resolve, porque não é satisfeito o seu pedido, ficando indefinidamente à espera.

A situação de Deadlock só é possível quando todas estas quatro condições surgem simultaneamente num grupo de processos. Separadamente, cada uma destas situações não é condição suficiente para provocar um Deadlock.

As estratégias de prevenção de Deadlock surgem por conseguir desenhar um gerenciador de recursos que consiga violar uma das condições, sempre que elas surjam simultaneamente, isto é, conseguir que pelo menos uma das condições que levam ao Deadlock seja falsa.

- Antecipação:

As estratégias de evitar um Deadlock consistem na habilidade de um gerenciador de recursos de prever o efeito de satisfazer um pedido individual de alocação, se o pedido levar a uma situação em que possa surgir o Deadlock, as estratégias para o evitar deverão recusar o pedido.

A Antecipação é uma estratégia conservativa, tende a subutilizar recursos recusando a sua alocação se isso representar uma potencial situação de Deadlock.

Uma das estratégias de Antecipação mais conhecidas é a do Algoritmo do Banqueiro. Este método baseia-se no modo de funcionamento de um banco. Um banco possui uma quantia limitada de fundos - recursos – que podem ser emprestados a diferentes pessoas – processos. O banco pode estender a linha de credito a um cliente, linha essa que indica que o banco está preparado para emprestar fundos até esse limite. Os clientes aceitam, e não pedem mais fundos sem primeiro entrarem em novo acordo. A linha de credito é o máximo pedido de recursos feito pelo cliente.

- Detecção e Recuperação:

Alguns sistemas estão desenhados para permitir que a alocação de recursos prossiga sem grandes intervenções, em vez disso, o sistema verifica periodicamente se existe a possibilidade de surgir um Deadlock, quer periodicamente, quer sempre que certos eventos ocorram. Um aspecto negativo acerca desta abordagem reside em determinar quando o algoritmo de detecção deve ser executado. Isto deve-se ao facto de que se é executado muitas vezes, simplesmente torna o sistema demasiado lento, mas se não é executado vezes suficientes os processos em Deadlock e os recursos do sistema ficam entrelaçados de uma maneira não produtiva até que o sistema seja recuperado. Este problema surge devido à presença de um Deadlock resultar da não ocorrência de eventos em vez de ocorrer algum evento excepcional que possa disparar a execução do algoritmo de detecção.

Na estratégia do algoritmo de detecção surgem duas fases, a detecção, que verifica se ocorre uma situação de Deadlock, e a segunda fase, recuperação, que surge após o Deadlock se ter verificado e que resulta no desbloqueio dos recursos, por destruição dos processos que os bloqueavam.

Esta é a estratégia mais utilizada para tratar uma situação de Deadlock.

- Gerenciamento Manual do Deadlock :

Muitos dos sistemas actuais deixam para o utilizador a função de detectar um Deadlock, que através da utilização rotineira o utilizador apercebe-se devido ao tempo que se acha necessário, para que o processo seja executado, já ter sido largamente ultrapassado, ficando a descrição do utilizador achar se os processos entraram em Deadlock, e tentar resolver a situação recorrendo a ferramentas os sistemas ou a maquina fornecem, como por exemplo, e utilizado em ultima instancia, a reinicialização do sistema.

O padrão em que os recursos são requisitados, adquiridos e ficam em Deadlock determina quando o sistema entra em Deadlock.

Um processo bloqueado é incapaz de mudar o estado de um sistema, pois ele não consegue causar qualquer transição para além do estado corrente.