Sistemas Operacionais aula 06

Prévia do material em texto

CCT0011 – Sistemas Operacionais
Aula 06 – Comunicação entre Processos (2ª parte)
Professor Ricardo Bernardo
Sistemas Operacionais
Conteúdo da Aula
Breve Revisão Última Aula
Semáforos
Monitores
Troca de mensagens
Deadlock
Sistemas Operacionais
Mecanismo de sincronização que permite implementar, de forma simples, a exclusão mútua e 
sincronização condicional entre processos.
• Um semáforo é uma variável inteira, não negativa, que só pode ser manipulada por duas 
instruções: DOWN e UP. 
• As instruções DOWN e UP são indivisíveis, isto é, suas execuções não podem ser interrompidas.
• A instrução UP incrementa uma unidade ao valor do semáforo, enquanto a instrução DOWN
decrementa a variável.
• Se a instrução DOWN for executada em um semáforo com valor 0, o processo entra em estado 
de espera. 
• Em geral essas instruções são implementadas no processador, que deve garantir todas essas 
condições. 
• Os semáforos podem ser classificados como binários ou contadores. Os semáforos binários, 
também chamados de mutexes, só podem assumir valores 0 e 1, enquanto os semáforos 
contadores podem assumir qualquer valor inteiro positivo além do 0.
Semáforos
Sistemas Operacionais
• Exclusão mútua utilizando semáforos
• Sincronização condicional utilizando semáforos
• Problema dos Filósofos
• Problema do Barbeiro
Semáforos
Sistemas Operacionais
Fila de espera
de processos
Processo acessa
a região crítica
Processo deseja entrar
na região crítica
DO
W
N
 (S=
0)
DO
W
N
 (S
>
0)
UP (S) - processo sai
da região crítica
Libera processo
da fila de espera
A exclusão mútua pode ser implementada através de um 
semáforo binário associado ao recurso compartilhado.
Vantagem é a não ocorrência da espera ocupada.
As instruções DOWN e UP funcionam como protocolos de 
entrada e saída, respectivamente, para que um processo 
possa entrar e sair da sua região crítica.
Valor > 0, indica que nenhum processo está utilizando o 
recurso, enquanto o valor = 0, indica que o recurso está 
em uso e o acesso está impedido para outros processos.
Sempre que deseja entrar na sua região crítica, um processo 
executa uma instrução DOWN. Se o semáforo for igual a 1, 
este valor é decrementado, e o processo pode executar as 
instruções da sua região crítica.
Semáforo binário na exclusão mútua
Sistemas Operacionais
Se uma instrução DOWN é executada em um semáforo com 
valor igual a 0, o processo fica impedido do acesso, 
permanecendo em estado de espera, e 
consequentemente, não gerando overhead para o 
processador.
O processo que está acessando o recurso, ao sair de sua 
região crítica, executa uma instrução UP, incrementando 
o valor do semáforo e liberando o acesso ao recurso.
Se um ou mais processos estiverem esperando pelo uso do 
recurso (operações DOWN pendentes), o sistema 
selecionará um processo na fila de espera associada ao 
recurso e alterará o seu estado para pronto.
Semáforo binário na exclusão mútua
Fila de espera
de processos
Processo acessa
a região crítica
Processo deseja entrar
na região crítica
DO
W
N
 (S=
0)
DO
W
N
 (S
>
0)
UP (S) - processo sai
da região crítica
Libera processo
da fila de espera
Sistemas Operacionais
TYPE Semaforo = RECORD
Valor : INTEGER;
Fila_espera : (* Lista de processos pendentes * );
END;
PROCEDURE DOWN (VAR S : Semaforo);
BEGIN
IF ( S = 0) THEN Coloca_processos_na_fila_espera
ELSE
S := S – 1
END; 
PROCEDURE UP (VAR S : Semaforo);
BEGIN
S := S + 1
IF ( Tem_processo_esperando) then retira_fila_espera;
END; 
DOWN e UP
Instruções DOWN e UP, 
aplicadas a um semáforo S, 
podem ser representadas 
pelas definições ao lado, em 
uma sintaxe Pascal não 
convencional.
Sistemas Operacionais
Program Semaforo_1;
VAR s : Semaforo := 1;
Procedure Processo_A; 
Begin
Repeat
DOWN (s);
Região_critica_A;
UP (s);
Until False;
END;
Procedure Le_dados;
Begin
Repeat
DOWN (s);
Região_critica_B;
UP (s);
Until False;
END;
BEGIN
PABEGIN
Processo_A;
Processo_B;
PAREND;
END.
Processo_A Processo_B S Pendente 
Repeat Repeat 1 *
DOWN (s) Repeat 0 *
Região_critica_A DOWN(s) 0 Processo B
UP (s) DOWN (s) 1 Processo B
REPEAT Região_critica_B 0 *
Semáforos
Sistemas Operacionais
PROGRAM Semaforo_2;
VAR Evento : Semaforo := 0;
PROCEDURE Solicita_Leitura;
BEGIN
DOWN (Evento);
END;
PROCEDURE Le_dados;
BEGIN
UP (Evento);
END;
BEGIN
PARBEGIN
Solicita_Leitura;
Le_dados;
PAREND;
END.
Além de permitirem a implementação da exclusão mútua, os 
semáforos podem ser utilizados nos casos onde a 
sincronização condicional é exigida.
Por exemplo, quando um processo solicita uma operação de E/S. 
O pedido faz com que o processo execute uma instrução 
DOWN no semáforo associado ao evento e fique no estado de 
espera, até que a operação seja completada.
Quando a operação termina, a rotina de tratamento da 
interrupção executa um UP no semáforo, liberando o 
processo do estado de espera.
Sincronização condicional utilizando semáforos
Sistemas Operacionais
Neste algoritmo, o semáforo é inicializado com o valor 0, o 
que garante que o processo Solicita_leitura permaneça 
no estado de espera até que o processo Le-dados o 
libere.
Sincronização condicional utilizando semáforos
PROGRAM Semaforo_2;
VAR Evento : Semaforo := 0;
PROCEDURE Solicita_Leitura;
BEGIN
DOWN (Evento);
END;
PROCEDURE Le_dados;
BEGIN
UP (Evento);
END;
BEGIN
PARBEGIN
Solicita_Leitura;
Le_dados;
PAREND;
END.
Sistemas Operacionais
Monitores
Mecanismos de sincronização de alto nível que tentam tornar mais fácil o desenvolvimento e correção 
de programas concorrentes.
O monitor é formado por procedimentos e variáveis encapsulados dentro de um módulo.
Sua característica mais importante é a implementação automática da exclusão mútua entre os 
procedimentos declarados, ou seja, somente um processo pode estar executando um dos procedimentos 
do monitor em um determinado instante.
A implementação da exclusão mútua via monitores não é implementada diretamente pelo 
programador, assim como no caso do uso dos semáforos; o próprio compilador encarrega-se de garantir 
a exclusão mútua entre os procedimentos previamente definidos.
Sistemas Operacionais
Monitores
Um monitor é definido especificando-se 
um nome, declarando-se variáveis locais, 
procedimentos e um código de inicialização. 
A estrutura de um monitor pode ser feita da 
seguinte forma:
MONITOR monitor_a;
(* Declaração das variáveis do monitor *)
PROCEDURE Regiao_Critica_1;
BEGIN
.
END;
PROCEDURE Regiao_Critica_2;
BEGIN
.
END;
PROCEDURE Regiao_Critica_3;
BEGIN
.
END;
BEGIN
(* Código de inicialização das variáveis)
END.
Declaração de
variáveis globais
Procedimentos
Fila de entrada
Inicialização
de variáveis
Proc. 1
Proc. 2
Proc. n
M
on
ito
r
Sistemas Operacionais
Monitores
A implementação da exclusão mútua utilizando 
monitores não é realizada diretamente pelo 
programador, como no uso de semáforos. As regiões 
críticas devem ser definidas como procedimentos do 
monitor, e o compilador se encarregará de garantir a 
exclusão mútua entre esses procedimentos.
A comunicação do processo com o monitor é feita 
unicamente através de chamadas aos seus 
procedimentos e dos parâmetros passados.
Ao lado um exemplo de um programa que soma um 
valor a uma variável em um
procedimento e diminui um valor a essa mesma variável 
em outro procedimento.
PROGRAM Monitor_1;
MONITOR Regiao_Critica;
VAR X: Integer;
PROCEDURE Soma;
BEGINX:= X + 1;
END;
PROCEDURE Subtrai;
BEGIN
X:= X - 1;
END;
BEGIN
PARBEGIN
Regiao_Critica.Soma;
Regiao_Critica.Subtrai;
PAREND;
END.
Sistemas Operacionais
Através de variáveis especiais de condição, é possível associar a execução de um procedimento que 
faz parte do monitor a uma determinada condição, garantindo a sincronização condicional.
As variáveis especiais de condição são manipuladas por intermédio de duas instruções, conhecidas 
como WAIT e SIGNAL. A instrução WAIT faz com que o processo seja colocado no estado de espera, até 
que algum outro processo sinalize com a instrução SIGNAL que a condição de espera foi satisfeita. Caso 
a instrução SIGNAL seja executada e não haja processo aguardando a condição, nenhum efeito surtirá.
O monitor organiza os processos em espera
utilizando filas associadas às condições de 
sincronização. A execução da instrução SIGNAL
libera apenas um único processo da
fila de espera da condição associada.
Declaração de
variáveis globais
Procedimentos
Fila de entrada
Inicialização
de variáveis
Proc. 1
Proc. 2
Proc. n
Mo
nito
r
Filas de espera
Condição C1
Condição C2
Condição Cn
Monitores
Sistemas Operacionais
Troca de Mensagens
Mecanismo de comunicação e sincronização entre processos.
SEND – Envia uma mensagem a um processo receptor  SEND (Receptor, Mensagem)
RECEIVE – Recebe uma mensagem de um processo transmissor  RECEIVE (Emissor, Mensagem)
ACK (acknowledgement) – enviada pelo processo receptor para informar o recebimento da mensagem. 
• Não ocorre exclusão mútua.
• Uma mensagem só pode ser lida após Ter sido enviada.
• Pode ocorrer perda de mensagens.
• Se o emissor não receber um ACK em determinado tempo, reenvia a mensagem.
Endereçamento direto – só permite a comunicação entre dois processos.
Endereçamento indireto – utiliza uma área compartilhada (buffer conhecido como mailbox) onde as 
mensagens podem ser colocadas pelo emissor e retiradas pelo receptor.
Sistemas Operacionais
Troca de Mensagens
Comunicação síncrona (rendezvous):
• Um processo envia uma mensagem e fica esperando até que o receptor leia a mensagem
• Um receptor tenta receber uma mensagem e fica esperando até que o processo transmissor grave 
alguma mensagem.
• Dispensa necessidade de buffers.
• A necessidade de espera reduz o grau de concorrência.
• O problema dessa implementação é que a execução dos processos fica limitada ao tempo de 
processamento no tratamento das mensagens.
Comunicação assíncrona:
• O transmissor não aguarda o recebimento da mensagem.
• O receptor não aguarda o envio de uma mensagem.
• Necessita de buffers
• Maior paralelismo na execução dos processos em relação a síncrona.
Sistemas Operacionais
Transmissão de mensagem
Processo
transmissor
Processo
receptor
SEND RECEIVE
Canal de comunicação
Troca de Mensagens
Sistemas Operacionais
Deadlock é a situação em que um processo aguarda por um recurso que nunca estará disponível 
ou um evento que nunca ocorrerá. 
Essa situação é consequência, na maioria das vezes, do compartilhamento de recursos, como 
dispositivos, arquivos e registros, entre processos concorrentes onde 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.
Deadlock
Sistemas Operacionais
• Dispositivos e recursos são compartilhados a todo momento: 
Impressora, disco, arquivos, posições nas tabelas internas do sistema etc.
• S.Os. devem ter a habilidade de garantir a um processo acesso exclusivo a certos recursos
Ex: entrada em tabela do sistema de arquivos
Deadlock:
 Processos ficam parados sem possibilidade de poderem continuar seu processamento;
 Ocorrem tanto em recursos de hardware quanto software
Deadlock
Sistemas Operacionais
Deadlock
Sistemas Operacionais
Espera circular: cada processo está esperando que o outro libere o recurso alocado.
Recurso 2 Recurso 1
Processo A
Processo B
Processo A
solicita o
Recurso 2
Recurso 1
alocado ao
Processo A
Recurso 2
alocado ao
Processo B
Processo B
solicita o
Recurso 1
Deadlock
Sistemas Operacionais
Condições necessárias para que um deadlock ocorra: 
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  Um recurso não pode ser liberado de um processo só porque outros 
processos desejam o mesmo recursos;
4. Espera circular  Um processo pode ter de esperar por um recurso alocado a outro processo 
e vice-versa. 
Deadlock
Sistemas Operacionais
Deadlocks ocorrem quando processos obtêm acesso exclusivo a recursos.
• Hardware (ex: HD) 
• Software (entrada em base de dados)
Podem ser:
• Preemptivos: 
 podem ser retirados do processo sem prejuízos:
 Memória;
 CPU (como no escalonamento);
Deadlock
Sistemas Operacionais
• Não preemptivos:
 não podem ser retirados do processo, pois causam prejuízos;
 Criar CD-ROM;
 Unidades de fita;
 Impressora
• Deadlocks ocorrem em geral com recursos não preemptivos .
• Normalmente, com preemptivos, são resolvidos pela realocação de recursos de um processo 
a outro.
Deadlock
Sistemas Operacionais
• Eventos necessários para uso de recursos:
• Requisição do recurso; 
• Utilização do recurso; Pode ser feito via mutexes
• Liberação do recurso;
• Se o recurso requerido não está disponível, duas situações podem ocorrer:
• Processo que requisitou o recurso fica bloqueado até que o recurso seja liberado, ou;
• Processo que requisitou o recurso falha, com uma mensagem de erro, cabendo a ele 
esperar um pouco e tentar novamente
Deadlock
Sistemas Operacionais
Definição formal:
• Um conjunto de processos está em deadlock se cada processo no conjunto estiver 
esperando por um evento que somente outro processo no conjunto pode causar. 
• Muitas vezes, um processo espera por um recurso que outro processo nesse 
conjunto detém.
Deadlock de Recurso
Sistemas Operacionais
S.O. devem implementar mecanismos para:
 Prevenção
 Detecção
 Correção
Deadlock
Sistemas Operacionais
A detecção do deadlock é o mecanismo que determina, realmente, a existência dessa situação, 
permitindo identificar os recursos e processos envolvidos no problema.
Para detectar deadlocks, os sistemas operacionais devem manter estruturas de dados capazes de 
identificar cada recurso do sistema, o processo que está alocando tal recurso e os processos que 
estão à espera da liberação do recurso. 
Toda vez que o recurso é alocado ou liberado por um processo, a estrutura deve ser atualizada.
Deadlock - Detecção
Sistemas Operacionais
Após a detecção do deadlock, o sistema operacional deverá corrigir o problema. Uma solução bastante 
utilizada pela maioria dos sistemas é, simplesmente, eliminar um ou mais processos envolvidos no 
deadlock e liberar os recursos. A escolha do processo a ser eliminado é feita, normalmente, de forma 
aleatória ou com base em algum tipo de prioridade.
Outra solução seria a liberação de apenas alguns recursos alocados aos processos para outros 
processos, até que o ciclo de espera termine. Para que esta solução seja realmente eficiente, é 
necessário que o sistema possa suspender um processo, liberar seus recursos e, após a solução do 
problema, retornar à execução do processo, sem perder o processamento já realizado.
Este mecanismo é conhecido como rollback e gera um overhead muito grande.Deadlock - Correção