_________________________________________________________________
76
Capítulo 6
Sistema de entrada/saída
O sistema de entrada e saída de um sistema operacional é a parte responsável
por gerenciar a comunicação com quaisquer dispositivos que estabeleçam uma forma
de comunicação entre o sistema e os aplicativos através de dispositivos de diferentes
funcionalidades que sejam classificados como de E/S.
Neste capítulo são apresentadas as formas de comunicação entre o sistema
operacional e os dispositivos de entrada e saída e as formas de armazenamento e acesso
a arquivos.
_________________________________________________________________
77
6.1. Introdução
O sistema operacional se comunica com os dispositivos de entrada e saída
através da emissão de sinais de comando para estes elementos. Estes sinais de comando
podem ser classificados segundo três funcionalidades básicas:
•
•
•
Controle dos dispositivos;
Interceptar interrupções;
Tratamento de erros;
Para entendermos melhor as formas de comunicação existentes, os dispositivos
de E/S podem ser divididos em duas classes, segundo a forma com que manipulam
dados:
Dispositivos de bloco: armazenam informações em blocos de tamanho fixo, cada um
com seu próprio endereço. Variam de 512 a 32.768 bytes, e cada bloco é lido ou escrito
independentemente dos outros. Este é o modelo mais comum de ser utilizado.
Dispositivos de caractere: envia ou recebe um fluxo de caracteres, sem considerar
qualquer tipo de estrutura, como os blocos do modelo anterior. Este modelo não é
endereçável e não possui operações de posicionamento. Exemplos de dispositivos que
empregam este modelo são impressoras, mouse, interfaces de rede, etc.
6.2. Controle de acesso a dispositivos de E/S
O sistema operacional necessita de uma forma de gerenciar a comunicação entre
os dispositivos de entrada e saída com o restante do sistema, e os seguintes métodos
podem ser empregados nesta tarefa:
• E/S programada: quando um processo inicia uma operação de E/S, a UCP faz a
verificação se o dispositivo já se encontra pronto para a transmissão de outro
dado (estado chamado de espera ociosa ou pooling). Este é um modelo simples,
mas pouco eficaz, pois a UCP fica alocada ao processo até que a operação de
E/S seja concluída, ficando ociosa durante este tempo.
• E/S orientada a interrupção: utiliza interrupções para liberar a UCP para
outros processos enquanto uma operação de E/S é realizada. Assim que um
dispositivo de E/S começa uma operação, a UCP chama o escalonador e outro
processo é iniciado e uma interrupção salva o contexto do processo atual.
Quando a operação de E/S é concluída, o dispositivo gera uma nova interrupção
que detém o processo atual e salva o seu estado.
A desvantagem deste método é que a ocorrência de interrupções
constantes gera uma sequência de trocas de contexto, o que gera um desperdício
de UCP.
• E/S utilizando DMA (Direct Memory Access – Acesso Direto a Memória): O
DMA é um módulo responsável por controlar a comunicação entre a memória
_________________________________________________________________
78
principal e o dispositivo de E/S; o sistema computacional tem que possuir um
controlador de DMA implementado.
O DMA faz uma E/S programada, mas onde o controlador faz todo o
trabalho, ao invés da UCP, que fica liberada para exercer outras tarefas. A única
desvantagem deste método é que o uso de DMA é mais lento do que o controle
feito pela UCP, o que em alguns casos pode ser desvantajoso.
6.3. Drivers de dispositivos
Dependendo do dispositivo de E/S a ser utilizado, pode existir uma grande
variação de características, como o número de registradores utilizados e a natureza dos
comandos. Cada dispositivo de E/S ligado ao computador precisa de um código
específico para controlá-lo, chamado driver do dispositivo.
O driver fornece um conjunto de instruções que, através delas, o sistema
operacional é capaz de acessar o dispositivo de E/S. A figura 6.1 ilustra o modelo de
comunicação entre os drivers de dispositivos e o sistema operacional.
Figura 6.1. Posicionamento lógico dos drivers de dispositivos
_________________________________________________________________
79
Normalmente um driver de dispositivo trata de um tipo ou, no máximo, de uma
classe de dispositivos. Não existem restrições em se ter um driver que faça o controle de
vários dispositivos, mas não é uma boa idéia. Alguns exemplos de cada tipo são
apresentados a seguir:
Drivers de classes de dispositivos: um driver de disco SCSI pode tratar vários discos
SCSI de diferentes tamanhos e velocidades.
Drivers de dispositivos específicos: para o funcionamento de dispositivos com
recursos muito específicos, por exemplo, joystick com sensor de movimento, teclado
virtual, etc.
O ideal é que drivers executassem no espaço de memória do usuário e que
realizassem chamadas ao sistema para realizar operações de leitura e escrita aos
registradores do dispositivo. Este modelo tornaria o núcleo do sistema operacional
isolado dos drivers e os drivers isolados entre si. Desta forma, o maior fator de erros no
sistema operacional, que são drivers defeituosos que interferem no núcleo do sistema,
seria eliminado.
6.4. Software de E/S independente de dispositivo
A questão de existir uma interface uniforme para os drivers de dispositivos é de
extrema importância para o sistema operacional, pois faz com que todos os dispositivos
de E/S e drivers se pareçam os mesmos. Caso contrário, o sistema operacional teria que
ser modificado para cada novo dispositivo que surgisse.
A solução para esta questão é feita através da padronização de interfaces. Desta
forma, é definido um conjunto de funções que são disponibilizadas pelo núcleo do
sistema operacional que os escritores de drivers devem saber que estão disponíveis e
quais respostas podem esperar de cada uma delas. Torna-se mais fácil acoplar um novo
driver se ele estiver em conformidade com a interface provida pelo sistema operacional.
Na prática, nem todos os dispositivos são idênticos, mas podem apresentar muitas
funções em comum, o que torna possível criar modelos “genéricos”, como ilustrado na
figura 6.2. Na esquerda está ilustrado um modelo de projeto sem o uso de uma
interface-padrão para o driver, e na direita, um modelo com uma interface-padrão para o
driver.
Figura 6.2. Projeto de interface de drivers
_________________________________________________________________
80
Alguns exemplos de interfaces uniformes para drivers de dispositivos:
• Alocação e liberação de dispositivos;
• Armazenamento em buffer;
• Relatórios de erros;
• Fornecimento de tamanho de bloco independente do dispositivo (camadas
superiores lidam com dispositivos abstratos que usam o mesmo tamanho de
bloco lógico).
6.5. Software de E/S do espaço do usuário
A maior parte do software de E/S está dentro do sistema operacional, mas parte
dele é formada por bibliotecas ligadas aos programas dos usuários e até mesmo
programas completos que executam fora do módulo. Por exemplos, os procedimentos
de bibliotecas, como funções write, print, open, etc.
Outra categoria importante de software de E/S é o sistema de spooling, que
representa uma forma de lidar com dispositivos dedicados de E/S em sistemas de
multiprogramação. O método usa um processo especial (daemon) e um diretório
especial (diretório de spool)
O uso deste sistema busca respondar a seguinte pergunta: como impedir que um
usuário crie um processo que ocupe um dispositivo de E/S durante longos períodos, mas
que não faça nada?
Por exemplo, no serviço de impressão, inicialmente um processo gera todo o
arquivo a ser impresso e o coloca no diretório de spool. É função do daemon, que é o
único processo com permissão de usar os arquivos do diretório de spool, de imprimir os
arquivos, impedindo o acesso direto pelos usuários e, consequentemente, evitando de
manter o processo desnecessariamente aberto. Além de impressoras, outros sistemas
utilizam o mecanismo de spool, por exemplo, a transferência de arquivos através de
uma rede.
6.6. Escalonamento de Disco
O escalonador de disco influencia no desempenho dos sistemas, uma vez que são
nos discos que ficam armazenados até o momento do processamento os programas e os
dados, tais como compiladores, montadores entre outros. Portanto, o gerenciamento
apropriado do disco é importante para um sistema de computador. Note que este item
trata de estratégias para os discos rígidos “tradicionais”, isto é, composto por partes
móveis3, e não dos compostos por memórias sólidas4, ainda muito recentes e pouco
empregados, mas que certamente serão levados em consideração no projeto de novos
sistemas operacionais.
3
Faça uma revisão sobre a estrutura e funcionamento de discos rígidos, matéria abordada em livros de
Arquitetura de Computadores
4
Aproveite e faça uma pesquisa sobre o funcionamento de memórias SSD – solid state drive
_________________________________________________________________
81
6.6.1. Características físicas relevantes ao desempenho
Fisicamente os discos rígidos possuem duas superfícies, sendo cada uma delas
divididas em trilhas e setores. Um setor é a menor unidade onde pode ser feito um
acesso em um disco, através da cabeça de leitura e escrita. Uma solicitação de acesso
deve especificar superfície, trilha e setor desejados.
A velocidade de acesso ao disco pode ser composta por três partes. Para realizar
o acesso ao setor do disco, primeiro devemos mover a cabeça de leitura e escrita para a
trilha apropriada. O tempo gasto neste movimento é denominado seek time (tempo de
busca). Uma vez atingida a trilha correta, é necessário esperar que o setor desejado seja
rotacionado sob a cabeça de leitura e escrita. Este tempo é denominado latency time
(tempo de latência). Finalmente, há a transferência de dados entre o disco e a memória
principal. O tempo gasto na transferência dos dados é denominado transfer time (tempo
de transferência). O tempo total do serviço de um pedido ao disco é dado pela soma
destas três fatias de tempo.
É importante que os acessos ao disco sejam feitos tão rapidamente quanto
possível. Sempre que existe um pedido de entrada e saída emitido por um processo, é
enviada uma chamada ao sistema operacional. Este pedido deve especificar informações
tais como:
•
•
•
•
Entrada ou saída;
Endereço do disco (disco, trilha, setor);
Endereço de memória;
Quantidade de informação a ser transferida.
Se o disco estiver disponível, o pedido pode ser atendido imediatamente. Caso
contrário é necessário colocar os pedidos dos processos na fila de espera do dispositivo.
6.6.2 Algoritmos de Escalonamento de Disco
Os algoritmos de escalonamento de disco escolhem um processo da fila de
pedidos pendentes para ser atendido. Os algoritmos de escalonamento de disco podem
ser FCFS, SSTF, SCAN, C-SCAN, LOOK e C-LOOK A seguir descreveremos cada
um destes algoritmos.
First-Come-First-Served (FCFS)
Esta é a forma mais simples de escalonamento. Os pedidos são atendidos na
mesma ordem em que chegam à fila do dispositivo. Entretanto, o algoritmo FCFS pode
não fornecer o melhor tempo médio de serviço. Considere, por exemplo, uma fila de
pedidos por trilhas no disco ordenada da seguinte forma:
98, 183, 37, 122, 14, 124, 65 e 67,
Sendo 98 a primeira trilha pedida e 67 a última. Se a cabeça de leitura e escrita está
inicialmente na trilha 53, ela primeiro se moverá para a trilha 98, depois para a 183,
para a 37 e assim por diante. O movimento total da cabeça de leitura e escrita é igual a
_________________________________________________________________
82
640 trilhas e pode ser visto na figura 6.3. Se pudesse ser feita uma troca na ordem de
atendimento dos pedidos, o tempo para atender aos pedidos poderia decrescer
substancialmente. Por exemplo, trocando os pedidos pela trilha 122 e 14. Assim, após
atender ao pedido 37, atenderia ao pedido 14, depois o 122 e 124. Este fato melhoraria
muito o desempenho, pois reduziria o movimento total da cabeça de leitura e escrita
para 425 trilhas.
Figura 6.3. Escalonamento de disco FCFS.
Shortest-Seek- Time- First (SSTF)
Este algoritmo seleciona o pedido com o menor seek time a partir da posição
corrente da cabeça de leitura e escrita. Uma vez que o seek time é proporcional a
diferença de trilhas entre os pedidos, esta abordagem é implementada movendo a cabeça
de leitura e escrita para a trilha mais próxima na fila de pedidos. Para a mesma fila de
pedidos, temos na figura 6.4, a ilustração de como é o procedimento do algoritmo SSTF.
O problema deste algoritmo é starvation. Supondo que sempre chegue a fila de
pedidos trilhas mais próximas a cabeça de leitura e escrita que uma trilha mais distante,
esta vai esperar indefinidamente.
Figura 6.4. Escalonamento de disco SSTF
_________________________________________________________________
83
SCAN
Neste algoritmo a cabeça de leitura e escrita inicia em um dos lados do disco e
se movimenta para o outro extremo, servindo os pedidos quando a cabeça atinge cada
trilha até chegar ao outro extremo. Ao chegar ao outro extremo, o movimento da cabeça
de leitura e escrita é revertido e os pedidos são novamente atendidos. Supondo
novamente a mesma fila de pedidos das figuras anteriores, a figura 6.5 mostra o
procedimento deste algoritmo.
Figura 6.5. Escalonamento de disco SCAN
Uma variação deste algoritmo é denominada C-SCAN ou circular SCAN. A
diferença entre estes algoritmos é que ao atingir o extremo oposto, a cabeça de leitura e
escrita volta imediatamente ao início e recomeça a atender os pedidos.
Existem ainda duas outras versões semelhantes aos algoritmos SCAN e
C-SCAN, denominadas LOOK e C-LOOK. Nestas duas últimas versões, a cabeça de
leitura e escrita não chega a atingir os extremos (só no caso de haver um pedido
explícito por eles), nelas os movimentos são revertidos quando o último pedido por
trilha em cada direção é atingido.
_________________________________________________________________
84
6.7 Resumo
O sistema Operacional tem um importante papel no funcionamento de uma
infinidade de dispositivos responsáveis pela entrada e saída de dados do sistema. Deve
ainda gerenciar as formas de transferência de dados entre tais dispositivos e a memória
do sistema computacional, além de saber se comunicar corretamente com eles, o que faz
necessário o uso de drivers de dispositivos.
Os sistemas de discos são essenciais em muitos computadores. Os pedidos por
entrada e saída de dados armazenados em disco são gerados tanto pelo sistema de
arquivos quanto pelo sistema de memória virtual. Cada pedido especifica o endereço no
disco que é para ser referenciado. Este endereço inclui a superfície, a trilha e o setor. A
idéia dos algoritmos de escalonamento de disco é tentar diminuir o movimento total da
cabeça de leitura e escrita, tais como FCFS, SSTF, SCAN, C-SCAN, LOOK e
C-LOOK.
Leitura Obrigatória: Capítulo 5 do livro “Sistemas Operacionais Modernos”, 2ª
edição, TANEMBAUM, A., até o item 5.3 (inclusive), e o subitem 5.4.3.
_________________________________________________________________
85
Capítulo 7
Comunicação e sincronismo entre processos
A existência de múltiplos processos ou threads, sendo escalonados ou
executados paralelamente em sistemas multiprocessados é uma situação bastante
comum em sistemas operacionais modernos, porém, podemos nos deparar com
situações onde dois ou mais destes processos necessitam fazer acesso exclusivo a
recursos do sistema, originando situações de disputa que, se não forem devidamente
tratadas, podem resultar em resultados incorretos e até mesmo no travamento do sistema
operacional. Este capítulo descreve o problema conhecido como condições de disputa
entre processos e as formas mais empregadas em sua resolução.
_________________________________________________________________
86
7.1. Condições de disputa
Em sistemas operacionais modernos, podem ocorrer diversas situações nas quais
processos em atividade simultaneamente podem compartilhar algum recurso do sistema,
como um dispositivo de E/S, memória principal, arquivos, etc. Diante desta
possibilidade, surgem possíveis condições de disputa (race conditions), caracterizadas
por dois ou mais processos lendo ou escrevendo em dados ou recursos compartilhados,
cujo resultado final depende das informações manipuladas pelos processos e pela ordem
de execução dos mesmos.
Como exemplo, imaginem duas threads, T1 e T2 que compartilham uma
variável x, de seu processo pai P, cujo valor inicial é igual a 5. Ambas leem o valor de x,
e enquanto T1 realiza uma operação de subtrair 1 de x, T2 realiza a adição de 1 ao valor
de x. Se as operações foram realizadas na ordem descrita, x começou com o valor igual
a 5, T1 fez uma subtração, diminuindo este valor para 4, e grava este resultado na
memória. Porém T2 já havia lido o valor de x quando este era igual a 5, e adicionou 1,
em seguida atualizando o valor na memória para 6. Se a thread T1 for utilizar
novamente a variável x, lerá o valor 6, porém, esperava ler o valor 4, o último valor que
ela havia gravado na memória. Situações como esta durante a execução de programas
podem levar a situações de erros inesperados, e difíceis de ser depurados.
Devido a natureza multiprogramada da maioria dos sistemas operacionais
modernos, e o extenso uso de threads, torna-se necessário uma técnica para implementar
a exclusão mútua, ou seja, impedir que processos utilizem um recurso compartilhado
que já se encontre em uso naquele exato momento por algum outro processo do sistema.
No exemplo anterior, se T1 foi a primeira thread a acessar a variável x, ela deveria
“trancar” o acesso a x, impedindo que outros processos a utilizassem5, até o momento
que ela resolvesse “liberar” x.
Uma forma de solucionar condições de disputa seria identificar em um programa
as partes que fazem acesso a recursos compartilhados que podem gerar situações de
disputa. Estes trechos são chamados de regiões (ou seções) críticas, e serão
implementados mecanismos para que dois processos não estejam em suas seções
críticas ao mesmo tempo, evitando situações de disputa. A figura 7.1 ilustra esta
situação.
5
Em alguns casos é possível que outros processos acessem um recurso compartilhado, como a variável
citada, porém, com permissão somente para leitura do valor, incapazes de alterá-la, enquanto não estiver
liberada.
_________________________________________________________________
87
Figura 7.1. Exclusão mútua usando regiões crítica
Apesar de satisfazer as condições de disputa, a utilização de seções críticas não
garante que os processos paralelos funcionem cooperativamente de forma correta e
eficiente. Uma solução considerada boa deve atender as quatro condições apresentadas a
seguir:
•
•
•
•
Nunca dois processos podem estar simultaneamente em suas seções críticas;
Nada pode ser afirmado sobre a velocidade ou sobre o número de CPUs;
Nenhum processo executando for a de sua seção crítica pode bloquear outros
processos;
Nenhum processo deve esperar eternamente para entrar em sua seção crítica.
Algumas técnicas podem ser utilizadas para realizar a exclusão mútua,
impedindo que outros processos acessem áreas da memória compartilhada em sua seção
crítica, são apresentados a seguir.
7.2. Técnicas de exclusão mútua com espera ociosa
7.2.1. Desabilitar interrupções
Consiste em deixar um processo desabilitar todas as interrupções logo após
entrar em sua seção crítica, e reabilitá-las logo após deixar esta seção. Enquanto as
interrupções estão desabilitadas, a CPU não pode ser alternada entre processos. Na
prática, não se mostra uma solução muito interessante, pois dá aos processos do usuário
o poder de desabilitar interrupções, e não garante que seja reabilitada após a saída da
seção crítica. A situação é ainda mais complicada em sistemas multiprocessados, pois
apenas a CPU que desabilitou o uso de interrupções será afetada, outras CPUs existentes
poderão continuar executando outros processos e acessando áreas críticas da memória
compartilhada.
7.2.2. Variáveis de bloqueio
Modelo de bloqueio por software, utilizando uma variável compartilhada (lock),
inicialmente com o valor 0. Quando um processo quer entrar em sua seção crítica, ele
_________________________________________________________________
88
verifica o valor desta variável. Se for igual a 0, ele pode entrar na sua seção crítica e
altera o valor da variável para 1. Se, ao testar a variável, o valor já for igual a 1, o
processo deve aguardar até que o valor passe para 0, indicando que algum outro
processo saiu da seção crítica, liberando os recursos do sistema.
Este método também pode estar sujeito a falhas: suponha que um processo
verificou o valor de lock, que é igual a 0. Existe a possibilidade que, antes que este
primeiro processo altere o valor de lock para 1, um segundo processo seja escalonado,
execute e altere a variável de lock para 1. Ao executar novamente, o primeiro processo
também grava o valor 1 na variável de lock, e então existirão dois processos em suas
seções críticas ao mesmo tempo.
7.2.3. Alternância obrigatória
A primeira vista, este método guarda semelhanças com o uso de variáveis de
bloqueio. Utilizando uma variável de controle turn, um processo A verifica o valor
desta variável, que inicialmente é igual a 0, e entra em sua seção crítica. Neste
momento, um processo B verifica o valor da variável turn, que continua igual a 0, e fica
aguardando em uma espera ociosa6, até que este valor seja alterado para 1.
Quando o processo A deixa sua seção crítica, muda o valor de turn para 1, o que
permite ao processo B entrar em sua região crítica. Apesar de ser uma solução que
obrigue que os processos alternem suas entradas nas regiões críticas, não garante o
impedimento de uma situação de parada do sistema causada por erro na alternância7,
violando a terceira condição da lista já apresentada.
7.2.4. Solução de Peterson
Em 1981, o matemático G. L. Peterson apresentou um modo simples e eficiente
de implementar a exclusão mútua. Antes de entrar em sua seção crítica, cada processo e
faz uma chamada a uma função enter_region, passando como parâmetro seu número de
processo, 0 ou 1, o que servirá para verificar se ele deve esperar até o momento seguro
para entrar em sua seção crítica, caso necessário e manifesta seu interesse em entrar na
seção crítica, marcando uma variável de controle, no vetor interested. Após terminar o
uso das variáveis críticas, o processo chama o procedimento leave_region, para indicar
seu término e liberar as variáveis compartilhadas para uso por outros processos.
No código para a solução de Peterson, exibida a seguir, suponha que nenhum
processo está em sua seção crítica. Se o processo 0 chama a função enter_region, seu
interesse é marcado na sua respectiva posição do vetor interested e a variável turn é
marcada com 0. Como neste exemplo o processo 1 ainda não manifestou nenhum tipo
de interesse, a função enter_region retorna imediatamente, garantindo o acesso a seção
crítica ao processo 0.
Caso o processo 1 se manifeste, chamando a função enter_region, ele ficará
suspenso até que o valor da posição 0 no vetor interested seja modificada para FALSE,
6
Espera ociosa (busy waiting) deve ser evitada, já que gasta tempo de CPU. Só é aceitável quando há
uma expectativa razoável que o tempo de espera seja breve.
7
Como isto pode acontecer? Pesquise a respeito e apresente os resultados.
_________________________________________________________________
89
o que só acontecerá quando o processo 0 chamar a função leave_region para sair de sua
seção crítica. Nesta solução, caso os processos chamem a função enter_region quase
simultaneamente, ambos armazenarão seus valores na variável turn, porém, prevalecerá
o que armazenou por último, sobrescrevendo o anterior.
7.2.5. Instrução TSL
Trata-se de uma solução para o problema da seção crítica que trabalha em um
nível mais baixo do sistema, utilizando a seguinte instrução de montagem (presente
principalmente em sistemas multiprocessados):
TSL RX, LOCK
A Instrução TLS é um mnemônico para test and set lock, isto é, lê o conteúdo da
palavra de memória (neste caso, o lock, no registrador RX), e armazena um valor
diferente de zero no endereço de memória lock; as operações de leitura e
armazenamento de uma palavra são indivisíveis, o que garante que nenhum outro
processador acesse a palavra de memória até o término da instrução, pois bloqueia o
acesso ao barramento de memória para outras CPUs.
Desta forma, a variável lock controla o acesso a memória compartilhada: se seu
valor for igual a 0, qualquer processo pode utilizar a instrução TLS para mudar seu
valor para 1 e ter controle sobre os dados na memória compartilhada; quando terminar,
basta alterar novamente seu valor para 0 (através de uma instrução move).
7.3. Dormir e Acordar
Os métodos de Peterson e o TSL, apesar de funcionais, apresentam a ocorrência
de espera ociosa, o que gasta tempo de CPU desnecessariamente e, em alguns casos,
pode causar o problema da inversão de prioridade8.
Uma alternativa é utilizar algumas funções primitivas de comunicação
interprocessos, que fazem o bloqueio dos processos, ao invés da espera ociosa. As mais
utilizadas são as de sleep, que faz com que um processo ”durma”, isto é, entre em
espera, até que seja “acordado” por um outro processo, através de um wakeup.
O exemplo clássico da utilização destas duas primitivas é o problema do
produtor-consumidor, com buffer limitado (bounded buffer). Trata-se de um buffer
compartilhado, de capacidade limitada, entre dois processos. Um destes processos
assume a função de produtor, criando e armazenando itens neste buffer compartilhado, e
o outro, o consumidor, retira estes itens do buffer, um por vez, esvaziando-o. O mesmo
problema pode ser adaptado para múltiplos produtores e consumidores.
Neste problema, as situações que devem ser consideradas para a comunicação
interprocessos são:
8
Pesquise a respeito, parece uma daquelas perguntas que o professor gosta de colocar na prova.
_________________________________________________________________
•
•
90
Quando o produtor quer colocar um novo item produzido no buffer, mas este
encontra-se cheio. Neste caso, o produtor deve ser colocado para dormir, e ser
acordado quando ao menos um processo consumidor retirar um ou mais itens do
buffer.
Quando o consumidor quer retirar um item do buffer, mas este estiver vazio; de
forma análoga ao processo produtor, o consumidor deve ser colocado para dormir e
ser acordado quando o produtor tiver colocado algum novo item no buffer.
O número de itens no buffer compartilhado é mantido através de uma variável
count. Os processos produtor e consumidor são implementados com procedimentos para
inserir itens e remover itens, respectivamente, conforme ilustrados a seguir:
7.4. Semáforos
A questão sobre a comunicação interprocessos foi abordada em 1965 pelo
conceituado cientista da computação, E. W. Dijkstra9, que propôs a utilização de uma
variável inteira, o semáforo, utilizada para contar o número de sinais de acordar salvos
para uso posterior. Duas operações podem ser feitas sobre o sinal, up e down (apesar de
ser muito comum ver implementações que utilizam as letras P e V para implementar as
operações. Como Dijkstra era holandês, originalmente as operações eram Proberen
(testar), e Verhogen (incrementar)).
O resultado da operação down sobre um semáforo depende do valor desta
variável, o que pode resultar nas seguintes situações:
• Se o valor for maior do que zero, este é decrescido de 1, gastando um sinal de
acordar armazenado, e o processo segue adiante;
• Se o valor for igual a zero, o processo é colocado para dormir, sem terminar a
operação de down, ao menos por enquanto.
Observe que as operações de verificar o valor da variável, alterá-lo e, se
necessário, dormir, são executadas como uma operação atômica e indivisível.
A operação up incrementa o valor de um semáforo em uma unidade. Caso
existam um ou mais processos dormindo no semáforo incrementado (o que quer dizer
que seu valor era igual a zero antes do up), devido a uma operação de down prévia, um
deles será escolhido pelo S.O. para ser acordado. A operação de incrementar o semáforo
e acordar um processo também é indivisível.
A seguir é apresentada uma solução com semáforos para o problema do
produtor-consumidor. As variáveis usadas como semáforo nesta solução são:
• full: conta o número de lugares preenchidos no buffer; inicializada com o valor
0;
• empty: conta o número de lugares vazios do buffer; inicializada com o número
de lugares do buffer;
9
Pesquise sobre a obra de Dijkstra, o site http://en.wikipedia.org/wiki/Edsger_W._Dijkstra contém um
resumo de sua vida e obra
_________________________________________________________________
91
• mutex: usada para garantir que os processos produtor e consumidor não acessem
simultaneamente o buffer. Inicializada com o valor 1, pois é um semáforo
binário. Observe no trecho de código a seguir que em ambos os processos, a
primeira operação feita em um mutex é sempre um down, e ao sair da seção
crítica, um up, o que garante a exclusão mútua.
Semáforos também podem ser empregados na sincronização de processos,
garantindo que certas sequências de eventos ocorram, como o produtor parando de
executar quando o buffer estiver cheio, e parando o consumidor quando o buffer estiver
vazio.
7.5. Mutexes
Um mutex funciona como um semáforo simplificado, pois não possui a
capacidade de contar, e, como o nome diz10, é utilizado para tratar a questão da exclusão
10
Mutex é a abreviação de mutual exclusion – exclusão mútua.
_________________________________________________________________
92
mútua. Pode ser representado com somente 1 bit, já que só pode representar dois
estados: impedido ou desimpedido.
Sobre um mutex operam as operações de lock, para ter acesso a uma seção
crítica, e unlock, para liberá-la. Caso o mutex já esteja em uso e outro processo tente
utilizar o lock, este permanecerá bloqueado até que o processo que esteja na seção
crítica utilize o unlock. Se múltiplos processos estiverem bloqueados sobre um mesmo
mutex, quando este for liberado, o S.O escolherá um deles aleatoriamente para adquirir
o mutex em seguida.
7.6. Monitores
Apesar das funcionalidades, alguns dos métodos anteriores, como os semáforos,
possuem vulnerabilidades contra falhas críticas, podendo enfrentar até situações que
terminem em uma situação de impasse11, o que motivou vários pesquisadores a estudar
métodos alternativos. Na década de 70, dois pesquisadores, Hoare e Brinch Hansen,
desenvolveram pesquisas separadamente, e chegaram a soluções similares, que
consistiam em uma unidade básica de sincronização de alto nível, chamada de monitor.
Monitores são coleções de procedimentos, variáveis e estruturas de dados,
agrupadas em módulos ou pacotes. Um processo pode chamar procedimentos que fazem
parte de um monitor a qualquer momento, mas não tem acesso às estruturas internas de
dados ao monitor a partir de procedimentos declarados fora do monitor.
Para garantir a exclusão mútua, somente um processo pode estar ativo em um
monitor em certo momento, o que pode ser feito simplesmente através de mutexes ou
semáforos binários. Também são utilizadas variáveis condicionais para o bloqueio de
processos que não possam continuar no momento. Sobre estas variáveis podem ser
aplicadas duas operações:
• Wait: faz o bloqueio do processo que está chamando um procedimento do
monitor, por exemplo, quando um produtor descobre que o buffer está cheio.
• Signal: pode acordar processos, alterando o valor de uma variável condicional
que um processo parceiro está esperando, por exemplo, um consumidor que
retira um item do buffer e acorda o produtor.
Através destas operações torna-se permitido a um processo acordar o outro, o
que levanta uma questão: como evitar que dois processos pertençam simultaneamente
ao monitor? Neste ponto, as propostas de Hoare e Hansen se diferenciam:
• Hoare propõe simplesmente manter o processo recém-acordado e suspender o
outro;
• Hansen apresenta uma proposta mais simples conceitualmente e em sua
implementação: o comando signal, que desperta o outro processo só pode
aparecer como o último comando de um procedimento do monitor, o que garante
que após acordar o outro processo, o que estava em execução saia
11
Deadlock, assunto que será tratado no próximo capítulo. Por enquanto, basta saber que deadlocks são
muito, muito ruins. Você não vai querer que um aconteça em seu sistema.
_________________________________________________________________
93
imediatamente. Caso vários processos estiverem esperando por um signal,
somente um deles, a ser escolhido pelo escalonador do sistema, é despertado.
Tanto monitores quanto semáforos apresentam uma deficiência em sistemas
modernos: ambos foram projetados para uso em sistemas dotados de uma ou mais
UCP’s que utilizam uma memória comum a todas. Seus respectivos modelos de
funcionamento não são aplicáveis a um ambiente de processamento distribuído,
formado por múltiplas UCP’s, cada uma com sua memória de acesso local nãocompartilhada, conectadas através de uma rede local.
7.7. Troca de mensagens entre processos
A comunicação entre processos através de troca de mensagens é feita através de
chamadas ao sistema, de maneira similar a utilizada em semáforos, permitindo a criação
de procedimentos de biblioteca representados por chamadas com a seguinte estrutura:
send(destination, &message) → envia uma mensagem para um destino especificado;
receive(source, &message) → recebe uma mensagem, cuja origem pode ser
especificada; caso não existam mensagens disponíveis, o receptor pode ficar bloqueado
até que alguma mensagem chegue.
A estruturação de um sistema de comunicação através de troca de mensagens é
mais complexa do que os casos apresentados anteriormente, pois deve lidar com
questões inerentes da troca de mensagens entre processos em diferentes equipamentos,
como a possibilidade de perda de mensagens pela rede, o que gera a necessidade de um
mecanismo de confirmação de recebimento (acknowledgement, ou simplesmente ack)
para garantir que a mensagem foi entregue ou gerar uma retransmissão. E o quê
acontece se a confirmação for perdida? Outra questão importante é sobre a autenticação:
como saber que a mensagem recebida é realmente do remetente especificado12?
Como exemplo da utilização da troca de mensagens no problema do
produtor/consumidor, considere o exemplo a seguir. Sua execução começa com o
consumidor enviando 100 mensagens vazias (sendo 100 o tamanho estabelecido para o
buffer) ao produtor que, se tiver algum item a ser fornecido ao consumidor, envia de
volta uma das mensagens recebidas, mas agora contendo o item a ser consumido. Caso
o produtor trabalhe mais rápido do que o consumidor e fique sem mensagens vazias, ele
será bloqueado até que uma mensagem vazia retorne do consumidor.
12
Estes são problemas clássicos de transmissão de dados. Maiores detalhes serão discutidos nas
disciplinas de Redes de Computadores
_________________________________________________________________
94
Sistemas de troca de mensagens podem empregar caixas postais, para o
armazenamento temporário de mensagens de forma similar a buffers. Desta forma, os
parâmetros de send e receive são as caixas, e não processos.
7.8. Barreiras
Barreiras são mecanismos de sincronização para grupos de processos, ao invés
de pares que atuam no modelo produtor/consumidor. Certas aplicações utilizam o
conceito de fases, de forma que nenhum processo que tenha concluído pode passar para
a fase seguinte até que todos os outros processos também já estejam em condição de
fazê-lo. Como exemplificado na figura 7.2, ao alcançar uma barreira estabelecida, um
processo ficará no estado de bloqueado (através de uma chamada a um procedimento de
biblioteca barrier) até que todos os demais processos também alcancem a barreira, para
ultrapassá-la juntos.
Figura 7.2. Três momentos do uso de barreira com processos
_________________________________________________________________
95
Como exemplo de sua aplicabilidade, suponha um ambiente de processamento
paralelo heterogêneo onde um programa realize uma operação aritmética que requer um
grande número de cálculos, como a multiplicação de duas matrizes de grandes
dimensões, deva ser realizada. Uma alternativa é que vários processos distintos
trabalhem paralelamente, cada um realizando parte do trabalho (geralmente, a
multiplicação de um subconjunto das linhas da matriz). É esperado que tenham
processos terminando em instantes de tempo distintos, e para que o resultado final seja
apresentado como resultado de um único processo13 é necessário que os processos que
terminaram antes aguardem pelos que ainda estão em execução.
7.9. Problemas clássicos de comunicação interprocessos
Existem diversos problemas na literatura que ilustram situações de impasse
relativamente comuns na comunicação interprocessos. A seguir são apresentados alguns
problemas clássicos
O problema do Jantar dos Filósofos
Problema proposto em 1965 por Dijkstra, desde então é utilizado para analisar o
funcionamento de novas técnicas de sincronização entre processos que venham a surgir.
O problema é caracterizado por cinco filósofos sentados em torno de uma mesa circular,
cada um com seu prato de espaguete. Cada filósofo só faz duas coisas na vida: comer e
filosofar. Quando vai comer, ele deve pegar os garfos à sua direita e à sua esquerda,
pois o espaguete está escorregadio, portando, precisa dos dois, 14 porém, só existem
cinco garfos na mesa. Quando termina de comer, ele coloca os garfos de volta na mesa e
começa a filosofar, até que sinta fome novamente, quando tornará a pegar os garfos para
comer mais. A figura 7.3 ilustra o que seria o ambiente real do problema.
Figura 7.3. A mesa de almoço dos filósofos
13
Geralmente o processo paralelo cria a ilusão que um único sistema computacional de grande porte
tenha feito o processamento, e não que o resultado foi gerado por um conjunto de recursos
computacionais atuando cooperativamente.
14
Em publicações mais recentes, o enunciado foi ‘atualizado’ para comida japonesa e cada filósofo usa
hashis, os ‘pauzinhos’ para comer, o que torna mais plausível a necessidade de pegar os dois talheres
adjacentes, ao invés dos garfos.
_________________________________________________________________
96
Ao observar a figura, é elementar perceber que, quando um filósofo começa a
comer, seus vizinhos não conseguem fazer o mesmo, já que pelo menos um dos talheres
necessários não encontra-se disponível. A grande questão do problema é buscar por uma
solução na qual cada filósofo faça o que precisa fazer, sem nunca ficar travado. Em uma
situação extrema, imagine que cada um dos filósofos pegue o garfo à sua direita (ou
esquerda, o importante é que todos peguem o do mesmo lado) simultaneamente:
nenhum deles irá comer e ficará esperando que o filósofo do lado solte o garfo, o que
nunca irá acontecer, caracterizando uma situação de deadlock, que será discutida com
detalhes no capítulo seguinte.
Existem várias propostas para a solução deste problema, porém, algumas levam
a situações de processos atingirem um estado de starvation, ou que o correto
funcionamento dependerá de uma aleatoriedade em algum fator, ou ainda, limitam a
somente um filósofo estar comendo a cada instante. Existe uma solução que evita
deadlocks, e permite o máximo paralelismo a um número arbitrário de filósofos, através
de arranjos de semáforos, um por filósofo, e um mecanismo de controle para determinar
se o filósofo está comendo, pensando ou faminto (tentando pegar os garfos).
O problema do Barbeiro Sonolento
Neste problema, em uma barbearia há um barbeiro, uma cadeira de barbeiro e n
cadeiras usada para eventuais clientes esperarem a vez de serem atendidos. Quando não
existem clientes a serem atendidos, o barbeiro usa sua cadeira para dormir. Quando um
cliente chega, ele deve acordar o barbeiro para ser atendido, e se outros clientes
chegarem enquanto o barbeiro estiver ocupado, eles se sentarão nas cadeiras (se houver
cadeiras vazias) ou sairão da barbearia. Trata-se de um problema de sincronização de
processos, para que barbeiro e cliente não entrem em condições de disputa. Este é um
problema que representa uma situação de fila, onde o recurso (o barbeiro) acessa uma
fila limitada (as cadeiras de espera) e os processos (clientes) entram nessa fila, desde
que essa não esteja cheia.
Figura 7.3. A mesa de almoço dos filósofos
_________________________________________________________________
97
7.10. Resumo
Em sistemas operacionais modernos, é comum ter vários processos que precisam
se comunicar entre si. Em diversas situações estes processos podem compartilhar
posições de memória, a partir dos quais realizam operações de leitura e escrita de dados.
Eventualmente surgem situações de disputa, onde dois ou mais processos querem fazer
uso simultâneo de um recurso compartilhado, o que pode levá-los a condições de
conflito.
São implementados mecanismos para garantir que não existam conflitos de
acesso a regiões críticas, que são trechos de seus algoritmos onde são feitos acessos a
áreas compartilhadas de memória, através de mecanismos de controle como semáforos,
mutexes e monitores, dentre outros.
Leitura Obrigatória: Capítulo 2 do livro “Sistemas Operacionais Modernos”, 2ª
edição, TANEMBAUM, A., até o item 2.4 (inclusive)
Leitura recomendada: Capítulo 7 do livro “Sistemas Operacionais com Java”, 6ª
edição, SILBERSCHATZ, A.
_________________________________________________________________
98
Capítulo 8
Deadlocks
Em ambientes multiprogramados, diversos processos podem competir por
recursos do sistema. Quando um processo pede por recursos que não estão disponíveis,
o processo entre em estado de espera. Pode ocorrer que o processo nunca mude de
estado, porque os recursos pedidos por ele estão sempre alocados a outros processos.
Esta situação é chamada de deadlock. Neste capítulo serão descritos alguns métodos
utilizados em um sistema operacional para tratar o problema de deadlock.
_________________________________________________________________
99
8.1. Modelo do Sistema
Um sistema computacional consiste de um número finito de recursos, que
podem ser distribuídos entre diversos processos. Os recursos podem ser classificados
em vários tipos, cada um contendo uma ou mais instâncias. Como exemplos de tipos de
recursos, temos os ciclos de CPU, espaço de memória, arquivos, dispositivos de entrada
e saída de dados, dentre outros. Se um sistema possui dois discos, então o tipo de
recurso tem duas instâncias.
Recursos computacionais podem ser classificados como preemptivos, caso ele
possa ser retirado do processo proprietário sem causar nenhum tipo de prejuízo, como o
travamento do processo em si ou até do S.O.; já um recurso não-preemptivo não pode
ser retirado do atual processo proprietário sem que ocorra algum tipo de falha, por
exemplo, uma impressora imprimindo um documento de um processo PA, se for alocada
para um processo PB antes do término da impressão corrente, o processo de impressão
não será corretamente completado, deixando um documento impresso apenas
parcialmente.
Um processo utiliza um recurso através da seguinte sequência de eventos:
pedido, uso e liberação. Todos estes eventos são realizados através de chamadas ao
sistema. Desta forma, o sistema operacional é o responsável por manter uma tabela com
informações sobre quais recursos estão livres, quais estão alocados, e, se alocados, para
qual processo. Se um processo pede por um recurso que no momento se encontra
alocado a outro processo, ele pode ser adicionado a uma fila de espera por aquele
recurso.
A aquisição de certos recursos deve ser feita e gerenciada pelos próprios
processos dos usuários. Uma técnica comum de ser utilizada é através do uso de
semáforos, discutidos anteriormente, um para cada recurso. No caso de um processo
precisar de dois ou mais recursos, eles devem ser adquiridos sequencialmente. A partir
do momento em que existem dois ou mais processos competindo pelos mesmos
recursos do sistema, estamos diante de uma situação de um possível deadlock.
Para compreender melhor os métodos utilizados para tratar o problema de
deadlock, é necessário defini-lo e caracterizá-lo.
Definição: um conjunto de processos está em um estado de deadlock quando todos os
processo do conjunto estão esperando por um evento que só pode ser causado por outro
processo do conjunto. A figura 8.1(a) ilustra um cruzamento de veículos automotivos,
em uma situação onde pode ocorrer um deadlock no sistema, enquanto a figura 8.1(b)
ilustra a ocorrência do deadlock propriamente dito.
_________________________________________________________________
100
Figura 8.1. Um possível deadlock (a) e a ocorrência de um deadlock (b).
Caracterização: uma situação de deadlock ocorre se e somente se as quatro condições
seguintes são mantidas no sistema simultaneamente: mutual exclusion (exclusão
mútua), hold and wait (espera por recursos), no preemption (ausência de preempção) e
circular wait (espera circular). A seguir estão definidas estas quatro condições:
• Exclusão mútua: em um determinado instante, cada recurso está em uma de
duas situações: ou associado a um único processo ou disponível.
• Espera por recursos: processos que, em um determinado instante, retêm
recursos concedidos anteriormente podem requisitar novos recursos.
• Sem preempção: recursos concedidos previamente a um processo não podem
ser forçosamente tomados deste processo – eles devem ser explicitamente
liberados pelo processo que os retém.
• Espera Circular: Deve existir um conjunto de processos {p0, p1, ...pn} tal que
p0 espera por um recurso que está sendo usado por p1, p1 espera por um recurso
que está sendo usado por p2 e assim por diante, até que pn espera por um
recurso que esta sendo usado por p0.
Existem quatro estratégias possíveis para tratar o problema do deadlock, que
podem ser utilizados com diferentes graus de sucesso e complexidade de tratamento,
são elas:
•
15
Ignorar o problema. Se você ignorar a possibilidade de deadlock, talvez ele
ignore você; este método também é conhecido como ‘Algoritmo do Avestruz15’
(enterre a cabeça na areia e finja que nada está acontecendo); método desprezado
pelos matemáticos, mas aceito por engenheiros, caso a ocorrência de deadlocks
no sistema seja baixa; métodos de prevenção podem diminuir a performance do
sistema.
É sério, este é o nome do método, que é adotado por diversas versões de Windows e Unix.
_________________________________________________________________
•
•
•
101
Detecção e recuperação. Neste caso, os deadlocks poderão ocorrer, e neste caso,
deve haver um método para detectá-los e tomar alguma ação;
Anulação dinâmica, por meio de uma alocação cuidadosa de recursos;
Prevenção, negando estruturalmente uma das quatro condições necessárias para
gerar um deadlock.
Em 1972, Richard Holt provou que as quatro condições necessárias para a
ocorrência de deadlock podem ser modeladas utilizando grafos dirigidos, com dois tipos
de nodos: processos, que são representados através de círculos, e recursos, simbolizados
como quadrados. Um arco de um recurso ( ) para um processo (ο) indica que o recurso
foi previamente requisitado, alocado e está sendo usado pelo processo que o solicitou.
Já um arco de um processo (ο) para um recurso ( ) indica que o processo está no estado
de bloqueado, esperando pelo recurso relacionado.
A figura 8.2(a) ilustra um recurso R alocado a um processo A, a figura 8.2(b)
ilustra um processo B, aguardando por um recurso S, e em 8.2(c) ilustra um deadlock,
onde o processo D já tem alocado o recurso T e necessita do recurso U para continuar,
ao mesmo tempo que o processo C tem o recurso U alocado, mas não pode continuar
sua execução (e eventualmente, liberar este recurso), pois também precisa do recurso T.
A presença de um deadlock em uma representação de alocação de recursos no formato
de um grafo pode ser identificada através da presença de ciclos.
Figura 8.2. (a) processo de posse de um recurso; (b) processo aguardando por um recurso; (c)
deadlock.
8.2. Prevenção de Deadlock
Podemos prevenir uma situação de deadlock garantindo que pelo menos uma das
quatro condições necessárias para a ocorrência de deadlock não aconteça. Assim,
examinaremos cada uma delas separadamente.
Exclusão mútua
A condição de exclusão mútua é mantida para tipos de recursos que não podem
ser compartilhados (por exemplo, uma impressora). Já os recursos que podem ser
compartilhados não necessitam de acesso mutuamente exclusivo, e, portanto, não
_________________________________________________________________
102
causam deadlock (arquivo somente de leitura). Um processo nunca espera por um
recurso que pode ser compartilhado. Em geral não é possível prevenir deadlock negando
a condição de exclusão mútua.
Espera por recursos
Para que a condição hold and wait nunca se mantenha no sistema, devemos
garantir que sempre que um processo peça por um recurso, ele não mantenha qualquer
outro recurso. Um protocolo que pode ser utilizado requer que cada processo peça e
receba todos os recursos necessários antes que inicie a execução. Este fato provoca a
subutilização dos recursos.
Sem preempção
Para que a ausência de preempção não ocorra podemos utilizar vários
protocolos. Se um processo está mantendo um recurso e está pedindo por outro recurso
que não pode ser dado a ele imediatamente, isto é, o processo deve esperar então todos
os recursos que ele está mantendo devem ser liberados. O processo deve então
posteriormente pedir pelo recurso novo e por todos aqueles que foram liberados. Num
outro protocolo, se um processo pede alguns recursos, ele primeiro deve verificar se os
recursos estão disponíveis. Se estiverem, alocá-os. Caso contrário, ele deve verificar se
eles estão alocados a outros processos que estão esperando por recursos adicionais. Se
estiverem, retira os recursos desejados do processo que está esperando e alocá-os ao
processo requisitante. Se os recursos não estão mantidos por outros processos em estado
de espera e nem estão disponíveis, então o processo deve esperar.
Um processo só é reiniciado se ele ganha o recurso que está sendo pedido e recupera
qualquer outro recurso que venha a ter perdido.
Espera circular
Para que a espera circular não ocorra é imposta uma ordenação linear de todos os
tipos de recursos. É atribuído a cada recurso um número inteiro único, que permite a
comparação entre os recursos e determinar qual recurso precede outro na ordenação.
Num protocolo para prevenir deadIock cada processo pode pedir somente recursos
numa ordem crescente de numeração. Isto é, um processo pode pedir inicialmente um
tipo de recurso ri, após isto, o processo pode pedir um novo recurso rj se e somente se
F(rj) >F(ri).
8.3 Evitar DeadIock
Para evitar deadlock, em um sistema onde se permita que possam ocorrer as
quatro condições que podem levar a uma situação de deadlock, é necessário ter alguma
informação adicional sobre como cada processo pedirá os recursos. Existem vários
modelos que diferem quanto à quantidade de informações fornecidas. O modelo mais
útil e simples necessita que cada processo declare a priori o número máximo de
recursos de cada tipo que ele poderá necessitar. Dada a informação a priori é possível
construir um algoritmo que evite a situação de deadlock. Este algoritmo examina
dinamicamente o estado da alocação de recursos para garantir que nunca haverá espera
circular. O estado da alocação de recursos é definido pelo número de recursos alocados
_________________________________________________________________
103
e disponíveis, e a demanda máxima dos processos. Um estado é seguro se o sistema
pode alocar recursos para cada processo (até o seu máximo) em alguma ordem e ainda
evitar deadlock
Formalmente, um sistema está em um estado seguro somente se existe uma
sequência segura. Uma sequência de processadores p0, p1, ..., pn é uma sequência
segura para cada pi se os recursos que pi ainda pode pedir podem ser satisfeitos pelos
recursos disponíveis mais os recursos mantidos por todos os pj, com j < i. Quando um
processo pede um recurso que está disponível, o sistema deve decidir se o recurso pode
ser imediatamente alocado ou se o processo deve esperar. O pedido é garantido somente
se leva o sistema a um estado seguro. Um algoritmo clássico utilizado para evitar
deadlock foi estabelecido por Dijkstra e Habemann em 1965, e é comumente conhecido
como ‘algoritmo do banqueiro’.
O algoritmo possui esse nome por tratar do problema através da seguinte
analogia: um banqueiro (o S.O.) de uma pequena cidade pode negociar com um grupo
de clientes (os processos), aos quais ele libera linhas de crédito (que são recursos do
sistema). A função do algoritmo é determinar se a liberação de uma requisição é capaz
de levar o sistema a um estado inseguro; se for este o caso, o banqueiro nega a
requisição.
No caso do algoritmo tratar de um único tipo de recurso, para saber se um estado
é seguro ou não, o banqueiro leva em consideração cada solicitação de empréstimo. Ele
verifica se dispõe de recursos suficientes para atender algum dos clientes. Caso positivo,
ele assume que os empréstimos feitos a este cliente serão pagos (devolvidos); em
seguida, é considerado o cliente mais próximo do limite de recursos e assim por diante.
Se todos os empréstimos puderem ser pagos (devolvidos), o estado é considerado
seguro e a requisição inicial pode ser atendida.
A seguir são ilustradas três situações da alocação de recursos em um sistema.
Em (a), nenhum dos 10 recursos estão alocados a nenhum processo, porém, esta
quantidade é suficiente para atender individualmente a qualquer um deles, portanto, é
um estado seguro; em (b), houve uma distribuição de 8 dos 10 recursos inicialmente
disponíveis; por enquanto, nenhum processo tem os recursos necessários, porém, caso
os dois recursos disponíveis sejam alocados para C, ele irá executar, e no seu término
irá liberar os recursos, permitindo que B ou D entrem em execução logo em seguida,
portanto, também é um estado seguro.
Finalmente, em (C) está representada uma situação em que a alocação de
recursos empregada levou a um estado inseguro. Com apenas mais um recurso livre,
não importa a qual processo ele será alocado, pois nenhum terá a quantidade de recursos
necessários para a execução e posteriormente, a liberação dos recursos.
Apesar de este exemplo ilustrar uma situação de estado seguro que levou a um
deadlock, não podemos afirmar isto para qualquer situação, pois é considerada que a
diferença entre um estado seguro e um inseguro é que o primeiro pode garantir que
todos os processos terminarão; já no estado inseguro, esta garantia não pode ser dada.
Por melhores que sejam as intenções, evitar completamente deadlocks em um sistema é
praticamente impossível, por isso a maior parte dos esforços concentram-se na
prevenção e recuperação do sistema.
_________________________________________________________________
104
No caso de múltiplos recursos, o algoritmo do banqueiro também pode ser
utilizado, o exemplo a seguir ilustra as matrizes C e R e os vetores de recursos
existentes (E), alocados (P) e disponíveis (A).
Para determinar se um estado é seguro, o algoritmo do banqueiro executa os
seguintes passos:
1. Procure uma linha, R, cujas necessidades de recursos sejam todas inferiores ou
iguais a A. Caso não exista uma linha com estas características, o sistema
eventualmente entrará em deadlock, pois nenhum processo pode ser executado
até a sua conclusão;
2. Considere que o processo da linha escolhida requisita todos os recursos de que
precisa (o que garante ser possível) e termina. Marque esse processo como
terminado e adicione ao vetor A todos os recursos que lhe pertenciam;
3. Repita os passos 1 e 2 até que todos os processos sejam marcados como
terminados, que é o caso seguro, ou até ocorrer um deadlock, que é o caso
inseguro.
Apesar de o algoritmo ser considerado ótimo em teoria, dificilmente é utilizado
por sistemas operacionais na prática, pois raramente um processo sabe antecipadamente
prever todos os recursos que irá necessitar durante a sua execução, e que podem variar
dinamicamente à medida que novos processos de usuários sejam criados e terminados.
_________________________________________________________________
105
8.4. Detecção de Deadlock
Se o sistema não possuir algum protocolo que garanta a não ocorrência de
deadlock então deve ser implementado algum esquema que detecte e recupere o
sistema.
8.4.1. Detecção
Um algoritmo que examina o estado do sistema deve ser invocado
periodicamente para determinar se ocorreu deadlock. Para isso, o sistema deve:
• Manter informações sobre a alocação corrente de recursos pelos processadores e
quaisquer pedidos de alocação de recursos pendentes.
• Fornecer um algoritmo que utilize estas informações para determinar se o
sistema entrou num estado de deadlock.
Note que o esquema de detecção e recuperação possui overheads que incluem os
custos de tempo de execução para manter as informações necessárias a execução do
algoritmo de detecção e as perdas potenciais na recuperação do deadlock.
Como dito anteriormente, no caso de existir apenas um recurso de cada tipo, a
detecção de deadlocks pode ser feita através da presença de ciclos no grafo de alocação
de recursos. Caso existam vários elementos no sistema que forneçam o mesmo recurso
(por exemplo, duas unidades de disco; caso uma esteja ocupada, a outra pode atender as
solicitações de um processo da mesma maneira que a outra unidade atenderia), será
necessário outro método para a detecção de deadlocks. Serão utilizados os seguintes
elementos:
• O vetor E, que representa o número total de recursos existentes de uma
determinada classe i, (1 ≤ i ≤ m);
• O vetor A, que representa o número total de recursos disponíveis (isto é, não
alocadas no momento a nenhum processo) de recursos de uma determinada
classe neste instante;
• A matriz de alocação atual, C, onde a i-ésima linha da matriz informa quantas
instâncias de cada classe de recurso o processo Pi possui no momento;
• A matriz de requisições R, que indica quantas instâncias de um recurso j que Pi
precisa.
O exemplo a seguir ilustra o uso de vetores e matrizes na detecção de deadlocks.
Considere que o sistema possui quatro unidades de fita (UF), dois plotters (P), três
scanners (S) e uma unidade de CD-ROM:
_________________________________________________________________
106
Inicialmente, os processos P1 e P2 não podem ser executados, pois eles
demandam de uma unidade de CD-ROM e um scanner, respectivamente, que no
momento não estão disponíveis. Porém, o processo P3 pode ser satisfeito com os
recursos disponíveis, entra em execução e ao terminar, libera todos os recursos
alocados, o que permitirá ao processo P2 entrar em execução e, ao terminar, irá liberar
os recursos necessários para que P1 entre em execução, portanto, não existe deadlock no
sistema.
Usando o mesmo raciocínio, suponha agora que além das duas unidades de fita e
do plotter, o processo P3 necessite de um CD-ROM, o que acontecerá?
8.4.2. Recuperação
A recuperação de uma situação de deadlock deve ocorrer sempre que ela for
detectada. Existem três operações que recuperam o sistema, baseado nas quatro
condições que levam ao deadlock A primeira seria violar a exclusão mútua, o que não
pode ser feito. A segunda é abortar um ou mais processos para quebrar a espera circular
e trazê-los de volta ao sistema em um tempo posterior. A terceira é retirar alguns
recursos de um ou mais processos em deadlock. Assim, se utilizarmos a segunda ou a
terceira operação, devem ser considerados três pontos:
• Seleção de uma vítima. Quais recursos de quais processos devem ser retirados?
• Rollback: Se retirarmos um recurso de um processo, o que deveríamos fazer com
ele' Devemos retornar a execução até atingir um estado seguro?
• Starvation: Como garantir que o starvation não ocorrerá? Isto é, como garantir
que um mesmo processo não será sempre o escolhido para ser retirado do
sistema?
Seleção de um processo como vítima
Dado um conjunto de processos, a escolha de uma vítima é de ordem econômica.
Devemos retornar até um estado seguro os processos, com um custo mínimo. Os fatores
que podem determinar este custo são:
• Prioridade do processo;
_________________________________________________________________
107
• Quanto tempo o processo já completou e o quanto ainda falta para terminar a sua
execução.
• Quantos e quais tipos de recursos o processo usou até o momento?
• Qual a quantidade de processos envolvidos no rollback?
Rollback
Uma vez decidido qual o processo que sofrerá o rollback, devemos determinar o
quanto este processo deve retornar na sua execução. A solução mais simples é retornar
tudo, isto é, parar o processo e reiniciá-lo, porém esta solução é a mais custosa. Outra
solução é retorná-lo o suficiente para quebrar o deadlock, porém isto necessita que o
sistema mantenha mais informações sobre o estado de todos os processos que estão
executando.
Starvation (inanição)
Alguns sistemas podem evitar o deadlock através de uma política que defina
quais processos devem ganhar um recurso e em qual momento, porém, este processo
pode ter suas solicitações negadas indefinidamente, causando a starvation. Deve-se
garantir que um processo só possa ser escolhido como vítima um número limitado de
vezes. Desta forma, impedimos que ocorra starvation.
_________________________________________________________________
108
8.5. Resumo
Deadlocks representam um potencial problema para sistemas operacionais, pois
estão relacionados com a alocação de recursos do sistema aos processos do usuário. Na
ocorrência de uma situação onde um processo obtém acesso exclusivo a alguns recursos
e necessita de recursos alocados a outros processos e assim por diante, gerando uma
situação de impasse, está caracterizado um deadlock.
Deadlocks são difíceis de ser evitados por questões de sua própria natureza,
porém, existem métodos que podem ser utilizados para previnir a sua ocorrência e caso
aconteçam, corrigir o sistema.
Leitura Obrigatória: Capítulo 3 do livro “Sistemas Operacionais Modernos”, 2ª
edição, TANEMBAUM, A.
Leitura recomendada: Capítulo 8 do livro “Sistemas Operacionais com Java”, 6ª
edição, SILBERSCHATZ, A.