Sistemas Operacionais
Comunicação Entre Processos
Sleep / Wakeup
EX. Problema do produtor_consumidor (BUFFER LIMITADO)
•
Quando o buffer está cheio o produtor é colocado para dormir.
•
Quando o buffer está vazio o consumidor é colocado para dormir.
•
Verifica se count<=N (numero máximo)
•
deposita o item e incrementa
•
Cada processo deve verificar se o outro está dormindo para acordá-lo.
VER EX.
•
Buffer vazio
•
Consumidor verifica se count é = 0
•
Ocorre a interrupção.
•
Roda o processo produtor.
•
Produtor coloca um item e incrementa count (count=1), e acorda o consumidor [perda do
sinal] (que não está dormindo)
•
Consumidor lê o valor antigo “0” e dorme
•
Produtor começa a encher o buffer.
•
Buffer cheio produtor dorme.
•
Ambos dormem para sempre.
Para resolver isso, usa-se flags
• Indicando se o processo está ou não dormindo.
• Isso funciona bem para 2 processos, mas para 3 ou
mais temos que adicionar uma flag para cada
processo, complicando a implementação.
Solução de Peterson
1 int T;
1 void Sai_Região(int processo)
2 int solicita[2];
2 {
3 void Entra_Região(int processo)
3
4 {
4 }
5
int outro;
6
outro = 1 – processo;
7
solicita [processo] = Verdadeiro;
8
T = processo;
9
while (T = = processo && solicita[outro] =
= Verdadeiro
1
{
0
1
}
1
1 }
2
solicita[processo] = Falso;
Semáforos
• Resolve problemas de exclusão mútua e sincronia.
• Usa Down e Up (generalização de Sleep e Wakeup)
• Operação DOWN sobre o semáforo verifica se o val do
semáforo é >0
• Se for seu valor é decrementado e o processo continua
• Se for 0 o processo que executou a operação down, dorme.
• Ações únicas, atômicas.
• Operação UP incrementa o valor do semáforo
• Se um ou mais processo estiverem dormindo eles são
acordados, diminuindo a fila.
• Nenhum processo pode ser bloqueado ao executar UP
Solução do problema usando
semáforos
• Nas ações de acordar, dormir, atualizar
semáforo, etc, o SO inibe as interrupções
• As instruções acima são muito rápidas não
interferindo no processamento dos outros
processos
Contador de Eventos
• Resolve problemas de sincronia de
processos, mas os processos não dormem.
Monitores
• Evitar deadlock
• É uma seqüência de código
• Cada processo deve chamá-lo para entrar na
RC
• Apenas um processo pode estar dentro dele
• Tarefa do compilador implementar tal
diferença
Troca de mensagens
•
•
•
•
Send e Receiver
Um processo envia para outro uma msg
Se não receber nada é bloqueado.
Problemas quando o processamento é feito
com redes, podemos perder a msg (para
resolver usamos um sinal de
reconhecimento – acknowledgement – se
não recebe, retransmite a msg).
Troca de mensagens
• Problema: msg de reconhecimento perdida,
será enviada duas msg iguais.
• Solução: numerar com um contador as
msg’s (se receber duas msg com o mesmo
número ignora uma delas)
Troca de mensagens
• Problema: Operando em uma rede temos
que duas máquinas tem o mesmo processo
enviando msg’s para um receptor comum,
como saber de quem vem a msg?
• Solução: identificar as msg’s como
PROCESSO@MÁQUINA.
Troca de mensagens
• Problema: Duas organizações podem dar o
mesmo nome para duas de suas máquinas e
o receptor não saber de qual organização
vem a msg.
• Solução: Agrupa-se as máquinas em
DOMÍNIOS, sendo que cada organização
possui um domínio único. Ex.
[email protected].
Troca de mensagens
• Problema: Como saber se o receptor
(servidor de arquivos) é real ou um
impostor?
• Solução: Criptografar as msg’s (ex da
matriz)
Troca de mensagens
• Problema: Performance baixa se os
processo estão na mesma máquina.
• Solução: Usar semáforo, ou ainda em
estudos, dividir as msg em micro msg,
usando os registradores da CPU para troca
de msg.
Problemas Clássicos de
Comunicação entre
Processos.
Problema dos Filósofos Glutões
• Cinco pratos de
macarrão (representa
o uso de um recurso)
• Cinco garfos
(representa que o
recurso está ou não
disponível)
• Cinco filósofos
(representa o
processo em si)
1. Cada filósofo pode comer (representa a ação do
uso de um recurso)
2. Cada filósofo pode pensar (representa outra
atividade do processo)
3. Cada filósofo necessita de dois garfos (representa
que para efetuar uma determinada ação
necessitamos de dois recursos livres). Ex. Gravar
direto da memória para o disco.
• Problema1: Cada filósofo pega o garfo da direita,
ocorrendo assim o deadlock
• Solução: Cada filósofo pega o garfo da direita e
verifica se o da esquerda está livre, se não estiver,
libera o garfo da direita.
•
• Problema2: Todos os filósofos pegam os garfos da
direita e todos verificam que o garfo da esquerda
está ocupado, todos liberam os garfos, (repete
ciclo) Starvation => Morte provocada pela fome.
• Solução: Fazer com que cada filósofo pense e
devolva o garfo em tempos aleatórios.
• Problema3: Mesmo com os filósofos
pensando e devolvendo em tempos
aleatórios, existe a remota possibilidade de
todos fazerem isso ao mesmo tempo, e isso
não pode ser admitido em certos casos
(controle de uma usina nuclear, aviões,
espaçonaves, etc)
• Solução: Utilizamos semáforo.
• Problema4: Na teoria os semáforos resolvem, mas
na prática, teríamos apenas um filósofo se
alimentando e todos os demais parados.
• Solução: Utiliza-se uma matriz para que cada
filósofo controle a atividade de seu vizinho, para
checar se o mesmo está comendo ou não e ainda
se utiliza se um vetor de semáforo, um para cada
filósofo.
Problema dos Leitores e
Escritores
• Base de dados única
• Diversos processos tentando ler e escrever nela
1. O primeiro escritor a acessar o banco fecha o
semáforo.
2. Os leitores que quiserem ler são impedidos e
incrementam um contador.
3. Cada leitor que deixa o banco decrementa o
contador e o último a sair libera o semáforo,
permitindo que o escritor bloqueado, se existir
algum, seja liberado.
Problema dos Leitores e
Escritores
• Problema1: Os leitores tem prioridade sobre
os escritores, podendo o escritor ficar para
sempre esperando.
• Solução: Apresentada no artigo Courtois.
Problema do Barbeiro
Dorminhoco
Problema do Barbeiro
Dorminhoco
• 1 barbeiro (Impressora)
• 1 cadeira de barbeiro
(representa a impressão)
• N lugares de espera. Ex=5. (fila
de impressão – spool)
1. Se o barbeiro estiver sem
clientes ele dorme.
2. Se o barbeiro estiver ocupado e
um cliente chegar ele senta em
um lugar de espera.
3. Se todos os lugares estiverem
ocupados ele vai embora.
Problema do Barbeiro
Dorminhoco
• Problema1: Se dois clientes chegarem ao
mesmo tempo com dois lugares para espera
desocupados, pode haver a condição de
corrida.
• Solução: Usar semáforos, um para os
clientes, um para os barbeiros e um para
garantir a exclusão mútua.
Problema do Barbeiro
Dorminhoco
• Problema2: Se o barbeiro se desocupar os
clientes, podem ter a condição de corrida.
• Solução: Já resolvida anteriormente com os
semáforos, ou ainda podemos usar quando
temos apenas um barbeiro podemos usar
prioridades por ordem de chegada.