Comunicação e Sincronização entre Processos

Prévia do material em texto

Diego Lisboa Cardoso
diego@ufpa.br
Universidade Federal do Pará
Capítulo II: Gerência de Processos
Universidade Federal do Pará
 Comunicação Entre Processos (IPC)
◦ Em sistemas multiprogramáveis, onde há o
compartilhamento de recursos, o SO tem que prover a
comunicação entre processos ou threads.
 Exemplo:
 Dois processos concorrentes trocam
informações através de operações de gravação
e leitura em um buffer.
 Um processo só poderá gravar no buffer caso
ele não esteja cheio.
 Exemplo (Continuação):
 Um processo só poderá ler dados armazenados
no buffer, se existir algum dado para ser lido.
C:\> dir *.cpp | more
 No comando acima, há a criação de dois
processos distintos. O primeiro originado pelo
comando “dir”, e o segundo pelo comando
“more”. Só que esse segundo processo recebe
como entrada a saída de outro processo
(gerado pelo comando dir). Esse tipo particular
de comunicação é chamado de Pipe.
 Exemplo (Continuação):
 Nem sempre a comunicação entre processos é
tão clara como o Pipe. Às vezes, a comunicação
é feita “escondida” do usuário final, como no
caso de troca de mensagens entre processos
ou compartilhamento de endereço de memória
comum.
 Os mecanismos que garantem a comunicação
entre processos concorrentes e o acesso a
recursos compartilhados são chamados de
mecanismos de sincronização.
 Problema na Comunicação entre Processos –
Condições de Corrida:
◦ Condições de Corrida são situações onde dois ou mais
processos estão acessando dados compartilhados, e o
resultado final do processamento depende de quem
roda quando.
Processo A
Processo B
Diretório 
de Spool
Out = 4
In = 7
Impressor
4
5
6
7
.
.
.
.
.
.
abc
Prog.c
Prog.n
 Solução para o problema de Condições de
Corrida
◦ Tem-se que encontrar alguma forma de proibir que
mais de um processo acesse o dado compartilhado ao
mesmo tempo, isto é, estabelecer a Exclusão Mútua
durante a execução.
◦ Regra básica: não permitir que processos entrem em
suas regiões críticas, que são partes do programa, cujo
processamento pode levar à ocorrência de condições
de corrida.
◦ Uma boa solução requer que quatro condições sejam
satisfeitas:
 Dois ou mais processos não podem estar
simultaneamente dentro de suas regiões
críticas correspondentes.
 Nenhuma consideração pode ser feita a
respeito da velocidade relativa dos
processos, ou a respeito do número de
processadores disponíveis no sistema.
◦ Uma boa solução requer que quatro condições sejam
satisfeitas (Continuação):
 Nenhum processo que esteja executando
fora de sua região crítica pode bloquear a
execução de outro processo.
 Nenhum processo pode ser obrigado a
esperar indefinidamente para entrar em sua
região crítica.
 Foram propostas diversas soluções para os
problemas de exclusão mútua e sincronização:
• Soluções de Hardware;
 Desabilitar Interrupções;
 Instruções Test-and-Set;
 Estrita Alternância
• Soluções de Software;
 Semáforos;
 Monitores;
1. Estrita Alternância: Mecanismo de controle
que alterna a execução das regiões críticas
de dois processos, através do uso de uma
variável inteira, chamada turn.
while (TRUE) {
while (turn != 0) 
/* espera */;
regiao critica ( );
turn = 1;
regiao não-critica ( )
/* Processamento
Longo*/;
}
(Processo A)
while (TRUE) {
while (turn != 1) 
/*espera */;
regiao critica ( );
turn = 0;
regiao não-critica ( ) 
/* Processamento
Rápido*/;;
}
(Processo B)
- Starvation:
▪ Situação onde um processo nunca
consegue executar sua região crítica e,
conseqüentemente, acessar o recurso
compartilhado.
▪ Ocorre quando dois ou mais processos
esperam por um recurso alocado a outro
processo.
▪ Quando o recurso for liberado, o sistema
escolhe qual processo ganhará o recurso.
- Starvation (Cont.):
▪Caso essa escolha seja realizada de forma
aleatória, existe a possibilidade de um
processo nunca ser escolhido e sofrer
starvation.
▪Outra implementação que pode gerar esse
problema: O sistema determina prioridades
para os processos acessarem um
determinado recurso.
▪ Inversão de prioridade
- Sincronização Condicional:
▪ Problema: Um recurso compartilhado não se
encontra pronto para ser utilizado pelos
processos. Neste caso, o processo é colocado no
estado de espera, até o recurso ficar pronto para
o processamento.
Exemplo: Comunicação entre dois processos através
de operações de gravação e leitura em um buffer
Processo 
Produtor
Processo 
ConsumidorBuffer
 Soluções de Hardware:
1. Inibição das Interrupções: Consiste em inibir as
interrupções de um processo antes do ingresso em sua
região crítica, habilitando-as outra vez imediatamente
após o processo sair de sua rc.
 Solução mais simples;
 Perigosa, pois não é uma boa prática atribuir a
processos de usuários o poder de desabilitar
interrupções;
 Ineficaz em sistemas multiprocessados  Afeta
apenas a CPU que desativou a interrupção.
 Soluções de Hardware:
1. Inibição das Interrupções (Cont.):
Sintaxe:
BEGIN
Desabilita_Interrupçoes;
Regiao_Critica;
Habilita_Interrupçoes;
END;
 E se o processo que desabilitou as interrupções
não tornar a habilitá-las?
 Soluções de Hardware:
2. Instrução Test-and-Set:
 Muitos processadores possuem uma instrução
especial que pode ler uma variável, armazenar
seu conteúdo em um registrador e atribuir um
novo valor a essa variável.
 Essa instrução é chamada de Test-and-Set.
 Instrução executada sem interrupção.
 Possui o seguinte formato: Test-and-Set(X,Y).
 Onde o valor lógico da variável Y é copiado para X,
sendo atribuído à variável Y o valor lógico
verdadeiro.
 Soluções de Hardware:
2. Instrução Test-and-Set (Cont.):
 Utiliza uma variável lógica (Bloqueio) para
coordenar o acesso concorrente a um recurso.
 Quando Bloqueio = False (falso), qualquer
processo poderá alterar seu valor para True
(Verdadeiro), através da instrução Test-and-Set
e, assim, acessar o recurso de forma exclusiva.
 Ao terminar o acesso, o processo deve retornar o
valor da variável para False (falso).
PROGRAM Test_and_Set;
VAR Bloqueio : Boolean;
PROCEDURE Processo_A;
VAR Pode_A: Boolean;
BEGIN
REPEAT
Pode_A := True;
WHILE (Pode_A) DO
Test_and_set(Pode_A, Bloqueio);
Regiao_critica_A;
Bloqueio := False;
UNTIL True;
END;
Entrada da região crítica
PROCEDURE Processo_B;
VAR Pode_B: Boolean;
BEGIN
REPEAT
Pode_B := True;
WHILE (Pode_B) DO
Test_and_set(Pode_B, Bloqueio);
Regiao_critica_B;
Bloqueio := False;
UNTIL True;
END; 
Entrada da região crítica
BEGIN
Bloqueio := False;
Processo_A;
Processo_B;
END; 
Saída da região crítica
 O Problema do Produtor Consumidor + Semáforos
1. O produtor coloca informação no buffer e o consumidor,
retira a informação do buffer.
2. Problemas: O produtor quer colocar informação no buffer e
este está cheio.
3. Solução: Colocar o processo produtor para dormir enquanto
o consumidor não retirar um ou mais itens do buffer.
4. Problema: O consumidor quer retirar informação e o buffer
está vazio.
5. Solução: coloca o processo consumidor para dormir.
 Soluções de Software:
1. Semáforo:
 É uma variável inteira, não negativa, que só pode
ser manipulada por duas instruções: DOWN e UP,
também chamadas instruções P e V.
 No caso de exclusão mútua, DOWN e UP
funcionam como protocolos de E/S à região
crítica de um processo.
 O semáforo fica associado a um recurso
compartilhado.
 Soluções de Software:
1. Semáforo:
 Se o valor do semáforo for maior que 0, nenhum
processo está utilizando o recurso; caso
contrário, o processo fica impedido do acesso.
 Sempre que um processo deseja entrar em sua
região crítica, deve executar uma instrução
DOWN. Se o semáforo for maior que 0, este é
decrementado de 1, e o processo pode executar
sua rc.
 Soluções de Software:
1. Semáforo:
 Entretanto, se uma instrução DOWN é executada
em um semáforo cujo valor seja igual a 0, o
processo solicitante ficará no estado de espera,
em uma fila associada ao semáforo.
 O processo que está de posse do recurso, ao sair
de suarc, executa uma instrução UP,
incrementando o semáforo de 1 e liberando o
acesso ao recurso.
Fila de
espera de
processos
Processo
deseja entrar 
na rc
Processo
acessa
sua rc
Processo
sai de 
sua rc
DOWN
(S=0)
DOWN
(S>0)
UP
Libera processo
fila de espera
TYPE Semaforo = RECORD
Valor : INTEGER;
Fila_Espera : (* Lista processos pendentes *);
END;
PROCEDURE DOWN (VAR S: Semaforo);
BEGIN
IF (S=0) THEN Coloca_processo_fila_de_espera
ELSE S:=S+1;
END;
PROCEDURE UP (VAR S: Semaforo);
BEGIN
IF (tem_processo_esperando) THEN
Tira_processo_fila_de_espera
ELSE S:=S+1;
END;
 Soluções de Software:
1. Semáforo (Cont.):
 As operações DOWN e UP são indivisíveis.
 Geralmente são implementadas como chamadas
de sistemas (system calls).
PROGRAM Semaforo;
VAR S : Semaforo := 1;
PROCEDURE Processo_A;
BEGIN
REPEAT
DOWN(S);
Regiao_critica_A;
UP(S);
UNTIL False;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
DOWN(S);
Regiao_critica_B;
UP(S);
UNTIL False;
END; 
BEGIN
Processo_A;
Processo_B;
END.
 Soluções de Software:
1. Semáforo (Cont.):
 Semáforos aplicados ao problema de exclusão
mútua são chamados mutexes ou binários, por
apenas possuírem os valores 0 e 1.
 Além de permitirem a implementação da
exclusão mútua, também podem ser utilizados
para implementar a sincronização condicional.
 mutex – assegura que produtor e consumidor não
tenham acesso ao buffer ao mesmo tempo
 Empty – num. Lugares vazios
 full - num. De lugares preenchidos
 Soluções de Software:
2. Monitores:
 São mecanismos de sincronização de alto nível.
 O monitor é um conjunto de procedimentos,
variáveis e estruturas de dados definido dentro
de um módulo.
 Sua característica mais importante é a
implementação automática da exclusão mútua
entre seus procedimentos, isto é, somente um
processo pode estar executando um dos
procedimentos do monitor em um determinado
instante.
 Soluções de Software:
2. Monitores (Cont.):
 Toda vez que algum processo chama um desses
procedimentos, o monitor verifica se já existe
outro processo executando algum procedimento
do monitor. Caso exista, o processo deve ficar
aguardando a sua vez.
 As variáveis globais do monitor são visíveis
apenas a ele e a seus procedimentos. Elas são
inicializadas pelo bloco de comandos do
monitor, situado no programa onde está
declarado o monitor.
MONITOR Exclusao_Mutua;
(* Declaraçao das variaveis do monitor *)
PROCEDURE produtor;
BEGIN
...
END;
PROCEDURE consumidor;
BEGIN
...
END;
BEGIN
(* Bloco de Comandos do monitor *)
END;
◦ Até agora, o que semáforos podem fazer que monitores não
podem?
 Espera ocupada  Quando um processo tenta entrar em sua RC ele são
impedidos por já existir um outro processo usando o recurso;
◦ Para resolver este problema, monitores introduziram uma
estrutura especial chamada variável de condição, sobre a qual as
seguintes operações são definidas:
◦ wait: libera o lock do monitor e coloca o processo para dormir.
Quando o processo acorda, ele tenta re-adquirir o lock do monitor
imediatamente.
◦ signal: acorda um dos processos que estão esperando pela
variável de condição. O processo que executa o signal sai do
monitor imediatamente. Se nenhum processo estiver esperando,
nada acontece. Se mais de um estiver esperando, apenas um
deles, determinado pelo escalonador do S.O. (FIFO, por exemplo),
é acordado.
Declaração de
variáveis globais
Procedimentos
Fila de entrada
Inicialização
de variáveis
Proc. 1
Proc. 2
Proc. n
M
o
n
it
o
r
Filas de espera
Condição C1
Condição C2
Condição Cn
• É Possível que vários processos estejam com suas execuções
suspensas, aguardando a sinalização. Para isso, o monitor
organiza os processos em espera utilizando filas associadas
às condições de sincronização.
• Sempre que um processo produtor deseja gravar um dado no
buffer, ele deverá testar se o número de posições ocupadas no
buffer é igual ao seu tamanho, ou seja se está cheio;
• Caso o teste seja verdadeiro, o processo deverá executar um WAIT
em Cheio, indicando que a continuidade da sua execução depende
dessa condição, e permanece aguardando;
• O processo só poderá guardar informações no buffer se o
Processo Consumidor executar um SIGNAL na variável Cheio,
indicando que um elemento do buffer foi consumido.
• O mesmo acontecerá para o processo consumidor quando
encontrar o buffer Vazio, ele ficará bloqueado até que o produtor
libere a condição vazio para ele voltar a execução.
 Produtor x Consumidor
 Leitor x Escritor
 O jantar dos filósofos
 O Problema do Barbeiro Dorminhoco
 http://escalonamentoprocessos.blogspot.co
m.br/2010/10/problemas-
classicos_127.html
 http://ces33.blogspot.com.br/2009/05/o-
problema-do-barbeiro-dorminhoco-
com_07.html
http://escalonamentoprocessos.blogspot.com.br/2010/10/problemas-classicos_127.html