Comunicação entre Processos em Sistemas Operacionais

Prévia do material em texto

CCT0011 – Sistemas Operacionais
Aula 06 – Comunicação entre Processos (2ª parte)
Sistemas Operacionais
Estrutura do conteúdo
 Semáforos
 Monitores
 Troca de mensagens
 Deadlock
Sistemas Operacionais
Semáforos
O conceito de semáforos foi o mecanismo de sincronização que permitiu implementar, a 
exclusão mútua e sincronização condicional entre processos, de forma simples e 
eficiente.
• 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.
Sistemas Operacionais
Semáforos
• 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.
Sistemas Operacionais
Semáforo binário na exclusão mútua
 A exclusão mútua pode ser implementada através de um semáforo binário associado 
ao recurso compartilhado. A 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.
Sistemas Operacionais
Semáforo binário na exclusão mútua
 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.
Sistemas Operacionais
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.
Sincronização condicional utilizando semáforos
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.
Sistemas Operacionais
Sincronização condicional utilizando semáforos
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.
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
Problema dos Filósofos
O problema dos filósofos é um exemplo clássico de sincronização de processos.
Ele se resume em uma mesa onde os filósofos podem sentar, comer e pensar. A mesa é 
composta por cinco pratos e cinco garfos. Sempre que um filósofo para de pensar e 
deseja comer, precisa utilizar dois garfo (direita e esquerda).
Um problema ocorre quando os filósofos estão segurando, cada um, um único garfo e 
nenhum conseguirá comer.
Algumas soluções foram propostas.
Sistemas Operacionais
Problema dos Filósofos
• Permitir que apenas quatro filósofos 
sentem-se à mesa simultaneamente.
• Permitir que um filósofo pegue um garfo 
apenas se o outro estiver disponível.
• Permitir que um filósofo ímpar pegue 
primeiro o garfo da esquerda e depois o da 
direita, enquanto um filósofo par pegue o 
garfo da direita e depois o da esquerda.
Sistemas Operacionais
Monitores
Estes mecanismos de sincronização de alto nível 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, 
são considerados mecanismos de sincronização estruturados, diferente dos 
semáforos.
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çãoda 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 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;
BEGIN
X:= X + 1;
END;
PROCEDURE Subtrai;
BEGIN
X:= X - 1;
END;
BEGIN
PARBEGIN
Regiao_Critica.Soma;
Regiao_Critica.Subtrai;
PAREND;
END.
Sistemas Operacionais
Monitores
Através de variáveis especiais, é 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á.
Sistemas Operacionais
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
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.
Sistemas Operacionais
Troca de Mensagens
A troca de mensagens é um tipo de mecanismo de comunicação e sincronização entre 
processos.
O sistema operacional pode executar a troca de mensagem, sem o uso de variáveis 
compartilhadas através de um subsistema de mensagem.
A comunicação entre processos pode ser feita de com uso de buffer ou por um link de 
uma rede de computadores.
A troca de mensagens pode ser implementada por comunicação direta ou comunicação 
indireta. Processo
transmissor
Processo
receptor
SEND RECEIVE
Canal de comunicação
Sistemas Operacionais
Troca de Mensagens
A comunicação indireta utiliza área compartilhada (buffer) conhecido como mailbox ou 
port.
Rotinas SEND e RECEIVE são utilizadas neste processo
• SEND – permite o envio de uma mensagem para um processo receptor ;
• RECEIVE – permite recebimento da mensagem enviada por um processo 
transmissor.
Sistemas Operacionais
Troca de Mensagens
A comunicação direta só permite a troca de mensagens entre dois processos.
• O processo transmissor deve indicar explicitamente o nome do processo receptor, e 
vice-versa (mudança na identificação dos processo exige recompilação).
• Uma mensagem só pode ser lida após Ter sido enviada.
• Podem ocorrer perdas de mensagens.
• Se o emissor não receber um ACK em determinado tempo, reenvia a mensagem.
Sistemas Operacionais
Troca de Mensagens
Processos que estão trocando mensagens devem ter suas execuções sincronizadas, 
independente do mecanismo de comunicação que utilizam.
Existem três diferentes esquemas de implementar a sincronização entre processo que 
trocam mensagens.
1) Garantir que um processo fique esperando até que o processo receptor possa ler 
(forma síncrona). Limitada ao tempo de processamento das mensagens.
2) Como variação do mecanismo anterior, pode permitir que o processo transmissor não 
fique bloqueado, enquanto o receptor não lê a mensagem;
3) Mecanismo que não deixa aguardando os processos, transmissor e receptor (forma 
assíncrona).
Sistemas Operacionais
Troca de Mensagens
Comunicação síncrona (conhecida como 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.
Sistemas Operacionais
Troca de Mensagens
Comunicação assíncrona:
• O transmissor não aguarda o recebimento da mensagem;
• O receptor não aguarda o envio de uma mensagem;
• Necessidade do uso buffers;
• Maior paralelismo na execução dos processos em relação a comunicação síncrona;
• Exige outros mecanismos de sincronização que permita ao processo identificar se 
uma mensagem já foi enviada ou recebida;
• Como vantagem aumenta a eficiência de aplicações concorrentes.
Sistemas Operacionais
Deadlock
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.
Sistemas Operacionais
Deadlock
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 continuar seu processamento;
 Ocorrem tanto em recursos de hardware quanto software.
Sistemas Operacionais
Deadlock de Recurso
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.
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
Deadlock
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 pode estar esperando por recursos , além dos 
já alocados.
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. 
Sistemas Operacionais
Deadlock
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);
Sistemas Operacionais
Deadlock
• 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 resolvidospela realocação de recursos de um 
processo a outro.
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
Deadlock
S.O. devem implementar mecanismos para:
 Prevenção
 Detecção
 Correção
Sistemas Operacionais
Deadlock - Prevenção
A ocorrência de deadlock pode ser prevenida garantindo que uma das quatro condições 
citadas não se satisfaça.
• A ausência da exclusão mútua garante que o deadlock não ocorra. Vários problemas 
podem ocorrer decorrentes do compartilhamento de recursos;
• Evitando que processos que já possuem recursos solicitem novos, garante que não 
vai ocorrer espera por recursos. Pode provocar a retenção de recurso por um longo 
tempo para utilizar apenas por alguns instantes.
• Garantir a retida de um recurso alocado por um processo caso outro processo 
necessite dele (não-preempção). Pode provocar sérios problemas ou impedir a 
continuidade de execução de outros processos.
• Garantir que um processo tenha apenas um recurso por vez, evita a espera circular. 
Restringiria o grau de compartilhamento e processamento.
Sistemas Operacionais
Deadlock - Detecção
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.
Sistemas Operacionais
Deadlock - Correção
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.
Sistemas Operacionais
Reflexão e Dúvidas