Sistemas Operacionais II - aula01

Prévia do material em texto

Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
11
Todos temos problemas, algum fáceis de resolver outros nem tanto, mas muitas 
vezes nos deparamos com problemas diante dos quais ficamos completamente estáticos. 
São aqueles problemas que, quando surgem, pensamos: “se ficarmos parados não 
resolvemos o problema e se agimos o problema também não é resolvido ou até mesmo 
pode piorar a nossa situação”. Enfim, temos que encontrar alguma solução ou então 
Aula 01
DEADLOCKS (IMPASSES)
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
12
todo um trabalho que foi desenvolvido até aquele ponto será jogado ao vento e não 
conseguimos ter um avanço até alcançarmos o nosso objetivo.
Vamos imaginar uma situação,para a qual irão existir várias soluções, mas o 
objetivo é “demonstrar o que pode ocorrer quando se tem um problema entre processos”. 
Imagine você sendo proprietário de uma transportadora de cargas e a sua empresa tem 
uma entrega a cumprir. É obvio que todos os seus custos foram calculados, tais como 
despesas de combustível, gastos com pneus e com automóvel. O cliente aguarda a entrega 
com muita ansiedade, contando os dias e as horas para a chegada de sua mercadoria; 
na data e hora marcada a mercadoria sai do ponto origem e parte para o destino. Uma 
situação inesperada acontece, uma ponte é quebrada, ou uma parte do asfalto desmorona 
e isso causa um enorme transtorno, você já deve imaginar o que vai acontecer: a sua 
entrega vai se atrasar, o prazo estabelecido não vai ser cumprido. Até aí tudo mais ou 
menos normal na medida do possível, vamos dizer que só não está normal porque a 
entrega vai se atrasar.
O seu cliente está aguardando a entrega e percebe que o prazo já expirou, mas ele 
não sabe o que aconteceu para que sua mercadoria no prazo estabelecido. Vamos observar 
na fi gura 1 o que está ocasionando o atraso da entrega: o automóvel da empresa saiu do 
ponto de partida, mas fi cou preso no congestionamento que foi se formando em virtude do 
problema como mencionado seja ele a queda de uma ponte ou o desmoronamento da estrada 
ou qualquer outro problema que possamos imaginar. O automóvel da empresa fi ca preso 
no centro do congestionamento não podendo voltar e nem dar continuidade ao transporte 
da carga. Imagine agora que o problema que houve não seja solucionado nos próximos 
anos, isso faria seu cliente fi car em uma espera infi nita sem poder fazer atividade alguma 
enquanto a sua mercadoria não chega, caminhão da transportadora vai se deteriorar, ou 
seja, acabará durante esse tempo. É dessa forma que ocorrem os impasses ou deadloks, 
vamos a um exemplo prático dos processos: vamos supor que haja dois processos e esses 
dois processos querem gravar em CD um documento obtido de um scanner. O processo X 
faz a solicitação para usar o scanner e tem a autorização. O processo Y, que é programado 
de uma maneira diferente, faz a solicitação de primeiro obter a permissão para usar o 
gravador de CD e também obtém essa autorização. Então o processo X pede para usar 
o gravador de CD, mas esta solicitação lhe é negada até que o processo Y o libere. No 
entanto, ao invés de liberar o gravador de CD, o processo Y pede para usar o scanner. Neste 
instante os dois processos fi cam bloqueados e assim fi carão para sempre. A fi gura 1 ilustra 
o que pode ocorrer em cidades, onde vários automóveis estão tentando transitar por uma 
via, mas o tráfego está totalmente engarrafado. È claro que pode haver uma intervenção, 
como a de um policiamento, a fi m de resolver o problema i tráfego e melhorar o tráfego, 
mas isso ainda causaria muito aborrecimento, esforço e perda de tempo.
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
13
Ainda podem ocorrer impasses com máquinas em muitas empresas que têm redes 
locais com vários computadores interligados, muitos dispositivos com scanners, impressoras, 
gravadores de CD que fi cam conectados a essas redes como recursos compartilhados, isto 
é, esses dispositivos fi cam disponíveis a vários usuários. Aí vem a questão: e se esses 
dispositivos puderem ser reservados remotamente1? Isso pode ocasionar impasses assim 
como aconteceu quando o processo Y fez a solicitação para primeiro obter a permissão para 
utilizar o gravador.
Como os impasses podem ocorrer tanto em dispositivos de hardware como e 
arquivos, para generalizarmos e assim fi car mais compreensível o assunto sobre impasses 
vamos referenciar os objetos acessados como recursos, ou seja, um recurso pode ser um 
hardware (como por exemplo, uma impressora, um scanner) ou uma informação (por 
exemplo, um arquivo, um registro de um banco de dados). Em um computador podemos 
ter vários tipos de recursos conectados como duas ou três unidades de disco, duas ou 
mais unidades de fi ta, assim vários recursos idênticos podem estar disponíveis e podemos 
constatar que quando vários isso ocorre, qualquer um deles pode ser usado para satisfazer 
qualquer requisição daquele recurso. Um recurso é um item que pode ser utilizado por 
somente um único processo em um dado instante do tempo.
Ainda falando em recursos, temos dois tipos deles que são, os recursos 
preemptíveis e os não preemptíveis. Os primeiros preemptíveis são recursos que podem 
ser interrompidos e retirados da área de uso sem ter qualquer perda ao sistema, ou seja sem 
causar impasses. Um exemplo de recurso preemptivo é a memória, pois quando um processo 
é parado e enviado para o disco como, por exemplo, na situação de termos um sistema com 
64mb de memória disponível para usuários, uma impressora e dois processos de 64mb que 
queiram imprimir algum documento. O processo X requisita e obtém a impressora e então 
passa a computar os dados para impressão. Antes que ele fi nalize o seu processo, a sua fatia 
de tempo de uso da CPU termina ele é retirado da memória, então entra em ação o processo 
Y que agora está em execução e tenta, mas não obtém nenhum êxito em obter para si o uso 
da impressora, pois ela já tinha sido requisitada pelo processo X. Estamos diante de uma 
típica situação de impasse: o processo X tem a impressora e o processo Y tem a memória, 
assim nenhum deles consegue prosseguir sem o recurso mantido pelo outro, mas como 
1 Remotamente: Computador ou rede de computadores a que se tem acesso por meio de linha de comunicação.
Figura: 1
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
14
estamos falando de um recurso preemptivo que é a memória, pode-se enviar o processo Y 
para o disco e depois carregar o processo X; com isso o processo X termina a sua execução, 
fi naliza a impressão e logo libera a impressora, isso torna os recursos livres para o processo 
Y, não ocasionando nenhum impasse.
Já com os recursos não preemptiveis, ao inverso dos preemptiveis, não há a 
possibilidade do processo ser interrompido e depois de um tempo continuar a execução, pois 
caso isso ocorra pode ocasionar falhas, ou seja, impasses. Um exemplo clássico quando isso 
pode ocorrer é quando estamos gravando um CD: se um processo começou a gravar um CD-
ROM e, de repente, retirar dele o gravador de CD e dar a um outro processo, isso ocasionará 
uma falha e o resultado será um CD com erros. Resumindo: gravadores de CD são recursos 
que não podem ser tomados a qualquer instante, pois são recursos não preemptiveis. De 
um forma geral os impasses envolvem recursos não preemptiveis, teoricamente temos um 
sequência de eventos necessários ao uso de um determinado recurso. São eles.
1. Requisitar o recurso.
2. Usar o recurso.
3. Liberar o recurso.
Caso um processo requisite um recurso e esse recurso esteja ocupado no exato 
momento em que ele foi requisitado, o que pode ocorrer é que em alguns sistemas operacionais 
o processo que solicitou é forçado a esperar. O processo será automaticamente bloqueado 
quando a requisição do recurso falhar, mas será novamente chamado quando o recurso 
se tornar livre. Em alguns sistemas a falha da requisição irá gerar um código de erro, aí 
cabeao processo solicitante esperar e tentar novamente mais tarde. Um processo que teve 
a sua requisição negada poderá permanecer em um loop2 e vai fi car requisitando o recurso 
continuamente, depois vai parar e tentará novamente. De certo modo esse processo não está 
bloqueado, mas como ele não poderá realizar nenhum trabalho útil, então é como se estivesse.
A forma real de como é feita a solicitação do recurso é totalmente dependente do 
sistema. Em alguns sistemas é utilizado uma chamada ao sistema do tipo request, a qual 
permite que processos solicitem recursos. Em outros, os únicos recursos que o sistema 
operacional reconhece são alguns arquivos que apenas um processo por vez pode abrir. 
Caso o arquivo no momento estiver em uso, o processo é bloqueado até que seja fi nalizado 
pelo proprietário atual.
Nos três passos relacionados anteriormente, são seguidos por operações como para 
a aquisição do recurso (down) depois vem a utilização do recurso e em seguida liberação 
do recurso (up), cada recurso pode ser associado a um semáforo. Veja os passos mostrados 
na tabela 1 a seguir. 
2 Loop: Técnica de trabalho denominada laços de repetição, que também pode ser referenciada como malhas de repetição ou pelo termos 
análogos em inglês loopings ou loops.
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
15
Processo “X”
type int semaphore;
semaphore resource_1
void process_A(void){
 down(&resource_1);
 use_resource_1();
 up(&resource_1);
}
Processo “Y”
type int semaphore;
semaphore resource_1;
semaphore resource_2;
void process_A(void) {
 down(&resource_1);
 down(&resource_2);
 use_both_resources();
 up(&resource_2);
Up (resource_1);
}
Temos dois processos “X” e “Y”, onde é utilizado o semáforo para proteger 
recursos, o processo “X” com um recurso e processo “Y” com dois recursos. Em alguns 
momentos hà processos que necessitam de mais de um recurso e, nesse caso, os recursos, 
são adquiridos sequencialmente, como mostra o exemplo do processo “Y”: quando houver 
a necessidade de mais de um recurso eles serão adquiridos um após o outro. Bom, por 
enquanto está tudo na normalidade, nada de extraordinário aconteceu, ou seja, até aqui 
estamos apenas acompanhando um processo e esse processo tem acesso a recursos sem 
maiores transtornos, não há a concorrência entre processos pois estamos acompanhando 
o acesso a recursos com apenas um processo.
Agora vamos imaginar uma situação com dois processos e dois recursos, em que, 
em uma das situações os dois processos solicitam os recursos na mesma ordem e na outra 
os processos solicitam os recursos em ordem diferente. Essa diferença pode até parecer 
sem importância, mas devemos pensar totalmente ao contrário.
Em um dos exemplos que se seguem um dos processos vai adquirir o primeiro 
recurso antes do outro. Com isso esse processo terá sucesso na aquisição do segundo 
recurso e assim terá êxito em seu trabalho. Se o outro processo tentar adquirir o recurso 1 
antes de ser liberado, por uma definição clara esse processo será bloqueado até o recurso 
1 ser liberado.
No outro processo o caso muda isso porque pode ocorrer que, um dos processo 
adquira os dois recursos e nesse caso o outro processo é bloqueado, até que seu trabalho 
finalize. Existe então a possibilidade de um deles ficar bloqueado quando tentar adquirir o 
outro recurso. Assim nenhum dos processos poderá continuar o seu trabalho ocasionando 
um impasse. Observe o exemplo da tabela 2 que se segue:
Tabela 1
Sistemas Operacionais Modernos-2° Ed, Andrew S. Tanenbaum- p. 119
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
16
Typedef int semaphore;
 semaphore resource_1;
 semaphore resource_2;
 void process_A(void) {
 down(&resource_1);
 down(&resource_2);
 use_both_resources();
 up(&resource_2);
 up(&resource_1);
 }
 void process_B(void) {
 down(&resource_1);
 down(&resource_2);
 use_both_resources();
 up(&resource_2);
 up(&resource_1);
 }
semaphore resource_1;
 semaphore resource_2;
 void process_A(void) {
 down(&resource_1);
 down(&resource_2);
 use_both_resources();
 up(&resource_2);
 up(&resource_1);
 }
 void process_B(void) {
 down(&resource_2);
 down(&resource_1);
 use_both_resources();
 up(&resource_1);
 up(&resource_2);
 }
Temos nos exemplos acima, um processo livre de impasse e um processo com a possibilidade 
de impasse. Podemos verifi car que em uma simples diferença de programação em que é defi nido qual 
recurso será adquirido primeiro tem a fi nalidade de demonstrar se o programa vai funcionar ou não. É 
uma difícil missão a de detectar qual programa vai funcionar, pois os programas são muito semelhantes, 
a única diferença realmente palpável é qual processo vai adquirir o recurso primeiro.
Podemos dizer que impasses são situações em que um processo espera por um recurso que 
nunca estará disponível, ou seja, é um evento que nunca ocorrerá. Um processo em situação de impasse 
encontra-se á espera de um recurso que está sendo usado por um outro processo também em situação de 
impasse, um processo não pode continuar o seu trabalho e o outro processo não pode liberar qualquer 
recurso. Veja a fi gura 2 em que os processos se encontram em situação de impasse. 
Tabela 2
Sistemas Operacionais Modernos-2° Ed, Andrew S. Tanenbaum- p. 119
*
*
Processo A
Recurso 2 Recurso 1
Processo A 
solicita o 
Recurso 2
Processo B
solicita o 
Recurso 1
Recurso 2 
alocado ao
Processo B
Recurso 1 
alocado ao
Processo A
Processo B
Figura: 2
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
17
Situações de impasses ocorrem, na maioria das vezes, por consequência do 
compartilhamento de recursos entre processos concorrentes em que a exclusão mútua e exigida.
EXCLUSÃO MÚTUA
Exclusão mútua é a solução mais simples para evitar impasses. A intenção é impedir 
que dois ou mais processos acessem um mesmo recurso ao mesmo tempo. A exclusão 
mútua faz com que enquanto um processo acessa um recurso, todos os outros processos 
que queiram acessá-lo devam esperar pelo término de sua utilização. A idéia de que há uma 
exclusividade de acesso é que é chamada de exclusão mútua (mutual exclusion).
O método de exclusão mútua tem o dever de afetar somente os processos 
concorrentes quando tais processos estiverem fazendo acesso ao recurso compartilhado. 
Essa parte do código do programa onde é feito o acesso ao recurso compartilhado é chamado 
de região crítica (critical region). Por isso podemos afi rmar que se for garantida a execução 
mutuamente exclusiva da região crítica, os problemas causados por compartilhamentos 
serão evitados. Uma das soluções é a utilização de um protocolo de acesso a regiões 
criticas. Todas as vezes que um processo for executar em sua região crítica, um protocolo 
de entrada deverá ser antes executado nessa região e isso também vale quando for sair da 
região crítica.
Esses protocolos de entrada e de saída garantem a exclusão mútua da região crítica de um 
programa e uma das soluções mais simples de exclusão mútua é a de desabilitar as interrupções.
O procedimento é simples: o processo desabilita todas as interrupções antes de 
entrar na área crítica do programa e ao sair da área critica, ele as habilita. Com isso o 
processo que habilitou as interrupções terá acesso exclusivo garantido.
A solução de desabilitar e habilitar as interrupções pode apresentar algumas 
limitações, primeiramente a multiprogramação fi caria seriamente comprometida, pois a 
concorrência entre processos tem como base o uso de interrupções. Um problema muito 
grave que pode ocorrer e o de um processo desabilitar as interrupções e não tornar a habilitá-
las. Nesse caso e bem provável que o seu funcionamento será comprometido.
Podemos notar que, em sistemas com múltiplos processadores, essa solução não 
e eficiente por conta do tempo de propagação quando um processador sinaliza aos demais 
que as interrupções devem ser habilitadas ou desabilitadas. Mas, por outro lado, essa 
solução pode se tornar bastante útil, quando se pretende que a execução de parte do núcleo 
do sistema operacional seja utilizada sem que tenha interrupção.
Dessa maneira o sistema tem a garantia de que não ocorrerão problemas de 
inconsistência ao executar algumas rotinas.
Em alguns processadores existe uma instrução de máquina especial que permite ler uma 
variável, armazenar o seu conteúdo em outra área e atribuir um novo valor à mesma variável. 
(Pág. 108 Sistemas Operacionais Modernos, Francis Berenger Machado e Luiz Paulo Maia)
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
18
Essa instrução é chamada de test-and-set. A instrução tem como principal 
funcionalidade o fato de ser executada sem interrupção, ou seja, trata-se de uma instrução 
indivisível, com isso pode-se garantir que dois processos não manipulem uma variável 
compartilhada ao mesmo tempo.
CONDIÇÕES PARA EXISTIR DEADLOCK
Coffman, Elphick e Shoshani provaram que as quatro condições seguintes são 
necessárias para existir deadlock:
1. Um recurso (impressora, arquivo) pode ser requisitado com exclusividade por 
um único processo por vez (condição de exclusão mútua).
2. Um processo que obteve um recurso exclusivo pode reter esse recurso enquanto 
espera para obter outros recursos (condição de espera, também denominada condição de 
posse e espera).
3. Uma vez que o processo obtenha um recurso (condição de não preempção).
4. Dois ou mais processos fi cam travados em uma “cadeia circular” na qual 
cada processo está esperando por um ou mais recursos que o processo seguinte da cadeia 
(condição de espera circular).
Sistemas Operacionais: terceira edição/H.M.Deitel, P.J. Deitel, D.R. Choffnes; 
Ed.Pearson Prentice Hall, 2005; São Paulo.
Assim como há condições para existência de impasses, foram desenvolvidas 
também condições para se evitar os impasses. Vamos analisar algumas das principais 
condições para a prevenção, detecção e correção de deadlocks.
1. Se houver impasses, você pode simplesmente ignorá-lo, pois pode ser que com 
essa atitude talvez o impasse ignore você.
2. Prevenção de Deadlock.
3. Detecção do Deadlock.
4. Correção do Deadlock.
ALGORITMO DO AVESTRUZ
A estratégia é muito simples, enfi a a cabeça na terra e fi nge que não tem problema 
algum. Existem pessoas que reagem a essa estratégia de formas muito diferentes. Os 
matemáticos acham isso um absurdo é inaceitável, pois eles dizem que os impasses devem 
ser evitados a qualquer custo. Já os engenheiros perguntam com que frequência o problema 
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
19
é esperado, com que frequência o sistema falha por outros motivos e qual a gravidade 
do impasse. Se os impasses ocorrerem em longos espaços de tempo devido a algumas 
falhas ocasionadas por hardware, erros de compilador e erros dos sistemas operacionais 
se ocorrerem uma vez por semana, a maioria dos engenheiros penalizará fortemente o 
desempenho ou a conveniência para eliminar os impasses.
PREVENÇÃO DE DEADLOCK
Para a prevenir a ocorrência de deadlocks é necessário ter a certeza de que uma das quatro 
condições mostradas anteriormente, que são necessárias para a sua existência, nunca ocorra.
Se não houvesse a primeira condição (exclusão mútua), com toda certeza seria eliminado o 
problema de deadlock porque, com a sua ausência, nenhum processo precisaria esperar para ter acesso 
a qualquer recurso, mesmo que o recurso estivesse sendo usado por algum outro processo.
Já na condição de espera, que também e conhecida por condição de posse e espera, 
processos que já tem recursos garantidos não podem requisitar novos recursos. Uma das formas de 
se implementar isso é, antes do início da execução, fazer com que um processo deva pré-requisitar os 
recursos necessários. Com isso todos os recursos necessários para a execução devem estar disponíveis 
para o início da execução, pois algum dos recursos não estiver disponível para o andamento, a operação 
volta ao início nenhum recurso é alocado e o processo permanecerá aguardando.
A outra condição, a de não preempção, poderá ser evitada quando é permitido que um recurso 
seja retirado de um processo no caso de algum outro processo necessitar do mesmo recurso que está 
sendo usado pelo atual processo.
 A última condição, a de espera circular, para evitar um deadlock é a sua exclusão. Uma 
forma de sua implementação é forçar o processo a ter apenas um recurso de cada vez, no caso do 
processo precisar de outro recurso, o recurso que já estiver sendo usado ele deve ser liberado.
Prevenir deadlocks não deixando que ocorra qualquer uma das quatro condições apontadas 
por Coffman, Elphick e Shoshani a prevenção de deadlock torna-se bastante limitada e, por isso, não é 
utilizada na prática. Podemos afi rmar que é possível evitar o deadlock mesmo que todas as condições 
necessárias à sua ocorrência estejam presentes.
A solução mais conhecida para essa situação é o algoritmo do banqueiro (Banke´s 
Algorithm) proposto por Dijkstra (1965). Esse algoritmo basicamente faz com que seja 
exigido que os processos informem o número máximo de cada tipo de recurso necessário 
para sua execução. É uma boa maneira para evitar deadlock, mas possui várias limitações. A 
maior delas é a necessidade de um número fi xo de processos ativos e de recursos disponíveis 
no sistema. Essa limitação faz com que a solução não seja implementada na prática porque é 
muito difícil prever o número de usuários e o número de recursos disponíveis.
DETECÇÃO DE DEADLOCKS
Em alguns sistemas não existe o mecanismo de prevenção de deadlocks, então 
é necessário um esquema de detecção e correção de deadlocks. Detecção de deadlocks é 
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
20
o mecanismo que reconhece uma situação de deadlocks, assim permitindo identifi car os 
recursos e processos envolvidos.
Na detecção de deadlocks é necessária uma estrutura de dados capaz de identifi car 
cada recurso do sistema, principalmente o processo que está sendo usado e os processos que 
estão à espera da liberação do recurso. Toda vez que um recurso é requisitado ou estiver 
em uso, essa estrutura de ser atualizada. Em geral, os algoritmos que implementam esse 
mecanismo verifi cam a existência da espera circular, percorrendo toda a estrutura sempre 
que um processo solicita um recurso e ele não pode ser imediatamente garantido para o uso.
CORREÇÃO DO DEADLOCK
Depois de detectar o deadlock, o sistema operacional terá de alguma forma corrigir 
o problema encontrado. Na maioria dos sistemas a forma encontrada é muito simples: ele 
elimina um ou mais processos envolvidos no deadlock e desloca os recursos já garantidos 
por eles, quebrando a espera circular. 
Essa eliminação não é tão simples quanto parece, pois depende do tipo do recurso 
envolvido. Se um processo estiver atualizando um arquivo ou imprimindo um relatório, o 
sistema deve garantir que esses recursos sejam liberados sem causar nenhum problema. Os 
processos eliminados não poderão ser recuperados, mas outros processos que estavam em 
deadlock, esses poderão prosseguir a execução.
A escolha de qual processo deve ser eliminada normalmente é feita de forma 
aleatória ou então com base em algum tipo de prioridade.
ATIVIDADES 
As atividades referentes a esta aula estão disponibilizadas na ferramenta “Atividades”. 
Após respondê-las, envie-nas por meio do Portfólio- ferramenta do ambiente de aprendizagem 
UNIGRANET. Em caso de dúvidas, utilize as ferramentas apropriadas para se comunicar com 
o professor.