Alocação de recursos e deadlocks

Prévia do material em texto

SISTEMAS 
OPERACIONAIS
Izabelly Soares 
de Morais
Alocação de recursos 
e deadlocks
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
 � Identificar os princípios de alocação de recursos e deadlock.
 � Reconhecer técnicas de prevenção ao deadlock.
 � Identificar técnicas de recuperação do deadlock.
Introdução
Vamos analisar nossas necessidades atuais e verificar quais atividades de 
seu cotidiano dependem de um recurso computacional? Aposto que 
quase todas, já que, hoje em dia, mal conseguimos decorar nosso próprio 
número telefônico. Neste capítulo, você vai lidar com alguns contextos 
voltados para a alocação de recursos pelos processos que executamos 
ao utilizarmos as funcionalidades oferecidas pelo sistema operacional 
que utilizamos.
Você vai conhecer também os principais conceitos que tratam de um 
evento que pode ou não ocorrer — dependendo da demanda de acesso 
aos recursos — e que pode paralisar um computador: o deadlock. Além 
dos motivos que podem ocasionar este fator, você vai aprender sobre 
prevenção e recuperação de um deadlock. 
Alocação de recursos e deadlock
Conforme Silberschatz, Galvin e Gagne (2015), talvez a melhor ilustração de 
um deadlock possa ser extraída de uma lei outorgada pela legislatura do Kansas, 
no início do século XX. Ela dizia, em parte: “Quando dois trens se aproximam 
um do outro em um cruzamento, ambos devem parar completamente e nenhum 
dos dois deve ser posto em marcha novamente até que o outro tenha partido.”
O relato anterior se refere ao momento em que os processos solicitam, quase 
simultaneamente, acesso ao mais variado tipo de recursos. Complementando a 
analogia, imagine que você está no trânsito, em horário de pico, num momento 
em que todos estão tentando se locomover por um único caminho. Aqui, 
caracteriza-se, claramente, um congestionamento no trânsito. 
Ainda sob a ótica de Silberschatz, Galvin e Gagne (2015), um processo deve 
solicitar um recurso antes de usá-lo e deve liberar o recurso após. O processo 
pode solicitar tantos recursos quantos precisar para executar sua tarefa. É 
claro que o número de recursos solicitados não pode exceder o número total 
de recursos disponíveis no sistema. Em outras palavras, um processo não 
pode solicitar três impressoras, se o sistema tem apenas duas. Sob condições 
normais de operação, um processo pode utilizar um recurso obedecendo 
somente à seguinte sequência:
1. Solicitação — o processo solicita o recurso. Se a solicitação não puder 
ser atendida imediatamente (por exemplo, se o recurso estiver sendo 
usado por outro processo), o processo solicitante deve esperar até que 
possa adquirir o recurso.
2. Uso — o processo pode operar sobre o recurso (por exemplo, se o 
recurso for uma impressora, o processo pode imprimir na impressora).
3. Liberação — o processo libera o recurso.
Deadlock é a situação em que um processo aguarda por um recurso 
que nunca estará disponível ou um evento que não ocorrerá. Essa situação 
é consequência, na maioria das vezes, do compartilhamento de recursos, 
como dispositivos, arquivos e registros, entre processos concorrentes em que 
a exclusão mútua é exigida. O problema do deadlock torna-se cada vez mais 
frequente e crítico na medida em que os sistemas operacionais evoluem no 
sentido de implementar o paralelismo de forma intensiva e permitir a alocação 
dinâmica de um número ainda maior de recursos (MACHADO; MAIA, 2013, 
p. 119). Na Figura 1, a seguir, o autor retrata bem a situação em que ocorre 
um deadlock. 
Alocação de recursos e deadlocks2
Figura 1. Espera circular.
Fonte: Machado e Maia (2013, p.119).
Ainda conforme Machado e Maia (2013, p. 119), a figura acima, ilustra 
graficamente o problema do deadlock entre os processos PA e PB, quando 
utilizam os recursos R1 e R2. Inicialmente, PA obtêm acesso exclusivo de 
R1, da mesma forma que PB obtêm de R2. Durante o processamento, PA 
necessita de R2 para poder prosseguir. Como R2 está alocado a PB, PA ficará 
aguardando que o recurso seja liberado. Em seguida, PB necessita utilizar 
R1 e, da mesma forma, ficará aguardando até que PA o libere. Como cada 
processo está esperando que o outro libere o recurso alocado, é estabelecida 
uma condição conhecida como espera circular, caracterizando uma situação 
de deadlock.
O exemplo retratado na Figura 1 traz uma demonstração bem simples de 
uma deadlock. Sabemos, porém, que os sistemas operacionais estão a cada dia 
mais complexos, disponibilizando mais funcionalidades aos usuários. Dessa 
forma, é natural que, em ambientes de multiprogramação, diversos processos 
sejam executados quase que simultaneamente e que suas funcionalidades 
acabem necessitando, consequentemente, de muito mais recursos. 
3Alocação de recursos e deadlocks
A situação denominada de deadlock tem início quando um processo ne-
cessita de um recurso e realiza sua solicitação. Caso os recursos estejam 
disponíveis, o processo irá entrar em estado denominado de espera. Nesse 
estado, geralmente aguarda que ocorra algo como, por exemplo, o recebimento 
de um sinal, ou a finalização de um evento de entrada e saída. Nem sempre, 
porém, o processo consegue voltar ao estado anterior, ou seja, ao que ele 
estava antes de entrar em espera, já que os recursos que ele havia solicitado se 
encontram reservados para outros processos que também estavam em espera. 
Para que ocorra a situação de deadlock, quatro condições são necessárias 
simultaneamente (COFFMAN; ELPHICK; SHOSHANI, 1971 apud MA-
CHADO; MAIA, 2013, p. 120), como observa-se a seguir.
1. Exclusão mútua — cada recurso só pode estar alocado a um único 
processo em um determinado instante.
2. Espera por recurso — um processo, além dos recursos já alocados, 
pode estar esperando por outros recursos.
3. Não preempção — recursos concedidos previamente a um processo não 
podem ser tomados à força desse processo, eles devem ser explicitamente 
liberados pelo processo que os retém.
4. Espera circular — um processo pode ter de esperar por um recurso 
alocado a outro processo, e vice-versa.
Técnicas para prevenção de deadlock
Anteriormente, listamos as quatro condições para que o deadlock ocorra. Como 
prevenção, devemos ter em mente que, caso alguma destas quatro condições 
não ocorra, também o deadlock não ocorre. Portanto, de acordo com Silbers-
chatz, Galvin e Gagne (2015), algumas situações em relação a cada condição 
citada anteriormente, previnem que haja o deadlock, como listamos abaixo:
 � Exclusão mútua — a condição de exclusão mútua deve estar presente 
para que o deadlock aconteça. Isto é, pelo menos um recurso deve ser 
não compartilhável. Recursos compartilháveis, por outro lado, não 
requerem acesso mutuamente exclusivo e, portanto, não podem estar 
envolvidos em um deadlock. Machado e Maia (2013, p. 120) comple-
mentam as ideias de Silberschatz, Galvin e Gagne (2015) relatando que 
a ausência da primeira condição (exclusão mútua) certamente acaba 
com o problema do deadlock, pois nenhum processo terá que esperar 
Alocação de recursos e deadlocks4
para ter acesso a um recurso, mesmo que já esteja sendo utilizado por 
outro processo. 
 � Retenção e espera — para assegurar que a condição de retenção e 
espera nunca ocorra no sistema, devemos garantir que, sempre que um 
processo solicitar um recurso, ele não esteja retendo qualquer outro 
recurso. Um protocolo que podemos usar requer que cada processo 
solicite e receba todos os seus recursos antes de começar a ser executado. 
Podemos implementar essa providência requerendo que as chamadas 
de sistema que solicitem recursos para um processo precedam todas 
as outras chamadas de sistema.
 � Inexistência de preempção — se um processo está retendo alguns re-
cursos e solicita outro recurso que não possa ser alocado imediatamente 
a ele (isto é, o processo deve esperar), então todos os recursos que o 
processo esteja retendo no momento sofrem preempção. 
 � Espera circular — a quarta e última condição para a ocorrênciade 
deadlocks é a condição de espera circular. Uma forma de assegurar 
que essa condição jamais ocorra é impor uma ordem absoluta a todos 
os tipos de recursos e requerer que cada processo solicite recursos em 
uma ordem de enumeração crescente.
Um método alternativo para impedir deadlocks é requerer informações adicionais sobre 
como os recursos devem ser solicitados. Por exemplo, em um sistema com um drive 
de fita e uma impressora, o sistema pode precisar saber que o processo P solicitará 
primeiro o drive de fita e depois a impressora, antes de liberar os dois recursos, en-
quanto o processo Q solicitará primeiro a impressora e então o drive de fita. Com esse 
conhecimento da sequência completa de solicitações e liberações de cada processo, 
o sistema pode decidir, para cada solicitação, se o processo deve ou não esperar para 
que seja evitado um possível deadlock no futuro. Cada solicitação requer que, ao tomar 
essa decisão, o sistema considere os recursos correntemente disponíveis, os recursos 
correntemente alocados a cada processo e as futuras solicitações e liberações de cada 
processo (SILBERSCHATZ; GALVIN; GAGNE, 2015).
Podemos acrescentar que existem algumas situações em que o deadlock 
pode ser evitado. Claro que nem sempre é possível definir com certeza como 
os processos e seus respectivos recursos serão administrados pelo sistema 
5Alocação de recursos e deadlocks
operacional, pois existem contextos em que, embora existam padrões esperados 
de comportamento, estes nem sempre se cumprem.
Um estado é seguro se o sistema pode alocar recursos a cada processo (até 
o seu máximo) em alguma ordem e continuar evitando um deadlock. Mais 
formalmente, um sistema está em um estado seguro somente se existe uma 
sequência segura. Um estado seguro não é um estado de deadlock. Inversa-
mente, o estado de deadlock é um estado inseguro. Nem todos os estados 
inseguros são deadlocks. Um estado inseguro pode levar a um deadlock. 
Enquanto o estado for seguro, o sistema operacional poderá evitar estados 
inseguros (e deadlocks). Em um estado inseguro, o sistema operacional não 
pode impedir que os processos solicitem recursos de tal modo que ocorra 
um deadlock. O comportamento dos processos controla os estados inseguros 
(SILBERSCHATZ; GALVIN; GAGNE, 2015).
Outra possível alternativa retratada pelos autores se refere à alocação de 
recursos. Podemos contar com um sistema de alocação de recursos com apenas 
uma instância de cada tipo de recurso. Dessa forma, a alocação de recursos não 
estaria apta a gerar um deadlock. Algumas outras possíveis soluções podem 
ser citadas, como a utilização de algoritmo do grafo de alocação de recursos, 
e nesse contexto, verificar se estss algoritmos trazem a possibilidade de serem 
aplicáveis em um sistema de alocação de recursos com diversas instâncias 
referentes a cada tipo de recurso.
O algoritmo do grafo de alocação de recursos não é aplicável a um sistema de 
alocação de recursos com múltiplas instâncias de cada tipo de recurso. O algoritmo 
do banqueiro possui este nome porque poderia ser usado em um sistema bancário 
para assegurar que o banco nunca alocasse seu dinheiro disponível de tal modo que 
não pudesse mais satisfazer as necessidades de todos os seus clientes. Quando um 
novo processo entra no sistema, ele deve declarar o número máximo de instâncias 
de cada tipo de recurso de que ele pode precisar. Esse número não pode exceder 
o número total de recursos no sistema. Quando um usuário solicita um conjunto de 
recursos, o sistema deve determinar se a alocação desses recursos o deixará em um 
estado seguro. Se deixar, os recursos serão alocados. Caso contrário, o processo deve 
esperar até que algum outro processo libere recursos suficientes (SILBERSCHATZ; 
GALVIN; GAGNE, 2015).
Alocação de recursos e deadlocks6
Técnicas para recuperação de deadlock
Após a ocorrência do deadlock, o sistema operacional deve possuir meios para 
se recuperar. Um dos passos que podem ser executados é quebrar a espera 
circular, já que ela ocorre devido à espera pela liberação dos recursos por 
parte dos processos.
Conforme Machado e Maia (2013, p. 121), a eliminação dos processos 
envolvidos no deadlock e, consequentemente, a liberação de seus recursos 
podem não ser simples, dependendo do tipo do recurso envolvido. Se um 
processo estiver atualizando um arquivo ou imprimindo uma listagem, o 
sistema deve garantir que esses recursos sejam liberados sem problemas. Os 
processos eliminados não têm como ser recuperados, porém outros processos, 
que antes estavam em deadlock, poderão prosseguir a execução. A escolha do 
processo a ser eliminado é feita, normalmente, de forma aleatória ou, então, 
com base em algum tipo de prioridade. Este esquema, porém, pode consumir 
considerável tempo do processador, ou seja, gerar elevado overhead.
Complementando as ideias de Machado e Maia (2013), Silberschatz, Galvin 
e Gagne (2015) afirmam que, quando um algoritmo de detecção determina 
que existe um deadlock, várias alternativas estão disponíveis. Uma possi-
bilidade é informar ao operador que ocorreu um deadlock e deixá-lo lidar 
com o problema manualmente. Outra possibilidade é permitir que o sistema 
se recupere do deadlock automaticamente. Há duas opções para a interrupção 
de um deadlock. Uma é simplesmente abortar um ou mais processos para 
romper a espera circular. A outra é provocar a preempção de alguns recursos 
de um ou mais dos processos em deadlock. Para isso, são listadas algumas 
particularidades referentes a essas duas possibilidades:
 � Encerramento de processos — para eliminar deadlocks abortando um 
processo, usamos um entre dois métodos. Nos dois métodos, o sistema 
reclama todos os recursos alocados aos processos encerrados.
 ■ Abortar todos os processos em deadlock — esse método claramente 
romperá o ciclo do deadlock, mas a um alto custo. Os processos em 
deadlock podem ter sido executados por muito tempo e os resultados 
dessas computações parciais devem ser descartados e provavelmente 
terão que ser refeitos posteriormente.
 ■ Abortar um processo de cada vez até que o ciclo do deadlock 
seja eliminado — esse método incorre em overhead considerável, 
já que após cada processo ser abortado, um algoritmo de detecção 
7Alocação de recursos e deadlocks
de deadlocks deve ser invocado para determinar se algum outro 
processo ainda está em deadlock.
 � Preempção de recursos — para eliminar deadlocks usando a preempção 
de recursos, provocamos a preempção sucessiva de alguns recursos dos 
processos e damos esses recursos a outros processos até que o ciclo do 
deadlock seja rompido.
Se a preempção for necessária para lidarmos com os deadlocks, então três 
questões devem ser abordadas:
1. Seleção de uma vítima — Que recursos e que processos devem sofrer 
preempção? Como no encerramento de processos, devemos determinar 
a ordem da preempção para minimizar o custo. Fatores de custo po-
dem incluir parâmetros como o número de recursos que um processo 
em deadlock está retendo e quanto tempo o processo levou para ser 
executado até o momento.
2. Reversão — Se provocarmos a preempção de um recurso de um pro-
cesso, o que deve ser feito com esse processo? É claro que ele não pode 
continuar a ser executado normalmente, pois algum recurso necessário 
está faltando. Devemos reverter o processo para algum estado seguro e 
reiniciá-lo a partir desse estado. Já que, em geral, é difícil determinar o 
que é um estado seguro, a solução mais simples é uma reversão total: 
abortar o processo e então reiniciá-lo. Embora seja mais eficaz reverter 
o processo somente até onde for necessário para interromper o deadlock, 
esse método requer que o sistema mantenha mais informações sobre o 
estado de todos os processos em execução.
3. Inanição — Como assegurar que a inanição não ocorrerá? Isto é, como 
podemos garantir que os recursos interceptados não serão sempre do 
mesmo processo? Em um sistema em que a seleção da vítima é baseada 
principalmente em fatores decusto, pode ocorrer que o mesmo processo 
seja sempre selecionado como vítima. Como resultado, esse processo 
nunca completará sua tarefa, uma situação de inanição que deve ser 
resolvida em qualquer sistema. É claro que devemos assegurar que 
um processo possa ser selecionado como vítima apenas um número 
finito (pequeno) de vezes. A solução mais comum é incluir o número 
de reversões no fator de custo.
Alocação de recursos e deadlocks8
Sistemas operacionais como Linux, Windows e Mac OS X irão: 
 � Prevenir a ocorrência de deadlocks no interior do próprio SO. 
 � Ignorar sua ocorrência em processos de usuários, e deixar que eles resolvam, 
manualmente, o problema (muito provavelmente encerrando um dos processos 
envolvidos). 
MACHADO, F. B.; MAIA, L. P. Arquitetura de sistemas operacionais. 5. ed. Rio de Janeiro: 
LTC, 2013.
SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Fundamentos de sistemas operacionais. 9. 
ed. Rio de Janeiro: LTC, 2015.
Leituras recomendadas
DELGADO, J.; RIBEIRO, C. Arquitetura de computadores. 5. ed. Rio de Janeiro: LTC, 2017.
PAIXÃO, R. R. Arquitetura de computadores – PCs. São Paulo: Érica, 2014.
STALLINGS, W. Arquitetura e organização de computadores. 8. ed. São Paulo: Pearson, 2009.
TANEMBAUM, A. Organização estruturada de computadores. 6. ed. São Paulo: Pearson, 
2013.
9Alocação de recursos e deadlocks
Conteúdo: