Aula_07 - Sincronização e Comunicação entre Processos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Arquitetura de Sistemas Operacionais
Capítulo 7
Sincronização e Comunicação
entre Processos
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Sumário
Introdução
Aplicações concorrentes
Especificação de concorrência em programas
Problemas de compartilhamento de recursos
Exclusão mútua
Sincronização condicional
Semáforos
Monitores
Troca de mensagens
Deadlock
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Introdução
Surgindo os sistemas multiprogramáveis, passou a ser possível uma aplicação ter trechos de códigos sendo executado de forma concorrente – aplicação concorrente;
A base é a execução cooperativa de processos ou threads em prol de um objetivo comum;
Mesmo em sistemas monoprocessados é possível obter ganhos com aplicações concorrentes;
Ao sistema multiprocessados estende as vantagens do uso deste tipo de aplicação;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Introdução
É natural o compartilhamento de recursos pelos processos de uma aplicação concorrente;
Este compartilhamento pode gerar situações indesejáveis;
Para evitar estas situações os processos devem ter a sua execução sincronizadas, a partir de mecanismos oferecidos pelo S.O.;
Este capítulo descreve a sincronização e comunicação entre processos.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Aplicações Concorrentes
Muitas vezes, os processos concorrentes devem comunicar entre si;
Esta comunicação pode ser implementada através de:
Memória compartilha;
Troca de mensagens.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Aplicações Concorrentes
Na próxima figura:
Um processo que lê do buffer;
Outro processo de grava no buffer;
Condições:
O processo só lê se o buffer não tiver vazio;
O processo só grava se o buffer não tiver cheio;
Em ambos os casos, os processos deverão esperar o buffer estar pronto para a operação;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Aplicações Concorrentes
Sincronização e comunicação entre processos
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Aplicações Concorrentes
Os mecanismos que garantem a comunicação e o acesso aos recursos compartilhados são chamados de mecanismos de sincronização;
Nesta abordagem tanto subprocessos como thread tem o mesmo significado que processos, para exemplicação das aplicações;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Especificação de Concorrência em Programas
Existem várias notações para especificar a concorrência em programas (partes do programa que devam ser executadas concorrentemente);
Conway(1963) e Dennis e Van Horm, criaram a primeira notação:
FORK – cria um outro processo;
JOIN – sincroniza com outro programa;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Especificação de Concorrência em Programas
 
O programa A começa;
Encontra o comando FORK:
Começa o programa B em outro processo;
O programa A encontra o comando JOIN:
O programa A espera o término do programa B;
Estes comandos são utilizados no Unix;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Especificação de Concorrência em Programas
Dijkstra em 1965 propôs o PARABEGIN e o PARAEND, uma das implementações mais claras;
Foram chamadas, posteriormente, de COBEGIN e COEND;
O comando PARABEGIN especifica uma seqüência de comandos seja executa de forma concorrente em uma ordem imprevisível, criando um processo para cada comando;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Especificação de Concorrência em Programas
O comando PARAEND define um ponto de sincronização, onde o processamento só continua quando todos os processos tiverem terminados;
Os comandos podem ser simples, como atribuições ou chamadas a procedimentos;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Especificação de Concorrência em Programas
Concorrência em programas
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Especificação de Concorrência em Programas
X := SQRT (1024) + (35.4 * 0.23) - (302 / 7)
PROGRAM Expressao;
 VAR X, Temp1, Temp2, Temp3 : REAL;
BEGIN
 PARBEGIN
 Temp1 := SQRT (1024);
 Temp2 := 35.4 * 0.23;
 Temp3 := 302 / 7;
 PAREND;
 X := Temp1 + Temp2 - Temp3;
 WRITELN ('x = ', X);
END.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Especificação de Concorrência em Programas
O cálculo final de X, só pode ser efetuado após terem terminado o cálculo de Temp1, Temp2 e Temp3;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Problema de Compartilhamento 
de Recursos
Veremos algumas problemas de compartilhamento de recursos:
Compartilhamento de um arquivo em disco;
Compartilhamento de uma variável na memória principal;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Problema de Compartilhamento 
de Recursos
Arquivo em disco:
Atualização de um saldo bancário;
Lançamento de um débito/crédito;
Em um arquivo são armazenados todos os saldos dos clientes de um banco;
O programa (próxima transparência):
Lê o saldo de um cliente;
Lê o valor da operação;
Atualiza o saldo;
Grava o saldo.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Problema de Compartilhamento 
de Recursos
PROGRAM Conta_Corrente;
 .
 .
 READ (Arq_Contas, Reg_Cliente);
 READLN (Valor_Dep_Ret);
 Reg_Cliente.Saldo := 
 Reg_Cliente.Saldo + Valor_Dep_Ret;
 WRITE (Arq_Contas, Reg_Cliente);
 .
 .
END.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Problema de Compartilhamento 
de Recursos
Considerando dois funcionários do banco atualizando o mesmo cliente; Certo 1.100
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Problema de Compartilhamento 
de Recursos
Variável compartilhada:
Dois processos (A e B) executam um comando de atribuição;
Processo A soma 1 à X;
Processo B diminui 1 de X;	
Se X, inicialmente, é igual a 2 e de se esperar que o resultado, após a execução dos processos continue igual a 2;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Problema de Compartilhamento 
de Recursos
Linguagem de alto nível 
Processo A Processo B
X := X + 1; X := X - 1;
Linguagem de baixo nível
Processo A Processo B 
LOAD x,Ra LOAD x,Rb
ADD 1,Ra SUB 1,Rb
STORE Ra,x STORE Rb,x
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Problema de Compartilhamento 
de Recursos
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Problema de Compartilhamento 
de Recursos
Analisando os exemplos conclui-se que em qualquer situação, onde dois ou mais processos compartilham um mesmo recurso, devem existir mecanismos de controle para evitar estes tipos de problemas, conhecidos como race conditions (condições de corrida);
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Solução
é impedir que dois ou mais processos acessem o mesmo recurso simultaneamente;
Portanto, quando um processo estiver acessando um recurso, os demais processos que queiram acessar este recurso deverão esperar pelo término da utilização deste recurso;
Esta idéia é chama de exclusão mútua (mutual exclusion);
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
A exclusão mútua deve afetar apenas os processos concorrentes somente quando um deles tiver fazendo acesso ao recurso compartilhado;
A parte do código onde se acessa o recurso compartilhado é chamada de região crítica (critical region);
Para evitar os problemas causados pelo compartilhamento basta evitar que dois processos entrem na sua região crítica simultaneamente;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Os mecanismos que implementam a exclusão mútua utilizam protocolos de acesso à região crítica;
Quando um processo desejar executar instruções de sua região crítica, deverá executar um protocolo de entrada na região crítica obrigatoriamente;
Da mesma forma quando sair da região crítica deverá executar um protocolo de saída;
Estes protocolos garantem a exclusão mútua da região crítica;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
BEGIN
 .
 .
 Entra_Regiao_Critica; (* protocolo de entrada *) 
 Regiao_Critica;
 Sai_Regiao_Critica; (* protocolo de saída)
 .
 .
END.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Para o programa de Conta_Corrente:
Recurso compartilhado
Arquivo de contas correntes;
Solução
Sempre que o Processo A for atualizar o saldo, antes de ler o acesso exclusivo ao arquivo deve ser garantido protocolo de entrada;
Se conseguir o acesso, significa que outro processo não esta utilizando o recurso, podendo assim atualizar o saldo
Quando gravar o saldo atualizado o Processo A libera o recurso – saída da região crítica – permitindo assim que outro processo utiliza o recurso (arquivo de conta corrente);
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Para garantir a implementação da exclusão mútua os processos envolvidos devem fazer acesso os recursos de forma compartilhada;
Existem diversas soluções para este propósito, mas deve-se evitar duas situações:
Espera indefinida (starvation starvation);
Um processo fora da sua região crítica impede que outros processos utilizem o recurso compartilhado;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Espera indefinida (starvation)
Ocorre quando um processo nunca consegue executar a sua região crítica (utilizar o recurso compartilhado);
Quando um recurso é liberado o S.O. Possui um critério para selecionar o próximo processo que terá acesso ao recurso;
Dependendo do processo de escolha o starvation pode ocorrer;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Espera indefinida (starvation)
Escolha aleatória: não está garantindo que em algum momento um processo terá acesso ao recurso pois a escola é aleatória;
Por prioridade: a baixa prioridade de um processo em relação aos outros pode impedir o acesso ao recurso;
Uma solução simples: criação de filas de pedidos para cada recurso, usando FIFO.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Um processo fora da sua região crítica impede que outros processos utilizem o recurso compartilhado;
Neste caso o recurso estaria livre porém alocado a um processo;
Assim todos os processos que utilizam este recurso estariam impedidos de entrar nas suas regiões críticas;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Soluções de hardware:
Desabilitação de interrupções;
Instrução test-and-set.
Soluções de software
Primeiro algoritmo;
Segundo algoritmo;
Terceiro algoritmo;
Quarto algoritmo;
Algoritmo de Dekker;
Algoritmo de Peterson;
Algoritmo para exclusão mútua entre N processos.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Desabilitação de interrupções
Solução mais simples;
É desabilitado todas as interrupções antes de entrar na região crítica;
É habilitado todas as interrupções após deixar a região crítica;
Como a mudança de contexto só pode ser executada através de interrupções, fica garantindo, assim, o acesso exclusivo;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Desabilitação de interrupções
BEGIN
 .
 Desabilita_Interrupcoes;
 Regiao_Critica;
 Habilita_Interrupcoes;
 .
END.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Desabilitação de interrupções
Limitações:
A multiprogramação pode ficar seriamente comprometida, já a concorrência tem como base o uso de interrupções;
Se o processo “esquecer” de habilitar as interrupções, o sistema ficaria seriamente comprometido;
Em sistemas multiprocessados esta solução torna-se ineficiente devido ao tempo de propagação de um processador para os outros da desabilitação/abilitação das interrupções;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Desabilitação de interrupções
Limitações:
Não esquecer que o mecanismo de clock é implementado com o uso de interrupções;
A seção crítica pode executar E/S que dependam de interrupções;
Apesar das limitações, esta solução pode ser útil quando se deseja que partes do núcleo do S.O. sem interrupções, garantindo que não haverão problemas de inconsistências nas estruturas de dados;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Instrução test-and-set
Instrução que:
Le uma variável;
Armazena o conteúdo em outro local;
Atribui um novo valor a mesma variável;
É executada sem interrupção, ou seja, é uma instrução indivisível;
Desta forma, é garantindo que dois processos não acessem uma variável compartilhada ao mesmo tempo – permite implementar a exclusão mútua;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Instrução test-and-set
Test-and-Set (X,Y):
O valor lógico de Y é copiado para X;
Y recebe o valor lógico verdadeiro.
Para coordenar o acesso concorrente, é utilizado uma variável lógica global chamada de bloqueio:
Quando bloqueio for falso qualquer processo poderá alterar o seu valor para verdadeiro e ter acesso ao recurso de forma exclusiva;
Quando terminar de usar o recurso, o processo retorna o valor falso para o bloqueio, liberando o acesso ao recurso. 
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Program Test_and_Set
var
 Bloqueio: boolean;
Procedure Processo_A;
var
 P_A	: boolean; // pode A
begin
 repeat
 P_A:= true;
 while (P_A) do
 Test_and_Set (P_A, Bloqueio);
 Regiao_Critica_A;
 Bloqueio:= false;
 until true;
end;
Procedure Processo_B;
var
 P_B	: boolean; // pode B
begin
 repeat
 P_B:= true;
 while (P_B) do
 Test_and_Set (P_B, Bloqueio);
 Regiao_Critica_B;
 Bloqueio:= false;
 until true;
end;
begin
 Bloqueio := false;
PARBEGIN
 Processo_A;
 Processo_B;
PARAEND
End.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão
Mútua
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Instrução test-and-set
Esta solução apresenta algumas vantagens:
Simplicidade de implementação
Uso em arquitetura com múltiplos processadores;
Principal desvantagem:
Possibilidade de starvation, pois a escolha do processo para acesso ao recurso é aleatória.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Soluções de software
Algoritmo 1
Uma solução para dois processos;
Onde a alternância na execução das seções críticas;
Cada procedimento (A e B) é representado por um loop infinito, onde o recurso é acessado;
É formado por protocolo de entrada, seção crítica e um protocolo de saída;
A região crítica é representada por uma rotina onde o acesso realmente ocorre;
Após a seção crítica as rotinas executam procedimentos individuais.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Algoritmo 1	
É utilizada uma variável de bloqueio indicando qual processo poderá acessar a região crítica;
Inicialmente possui o valor A indicando que o processo A terá acesso;
O processo só terá acesso a região crítica, quando o processo A atribuir a variável de bloqueio o valor ‘B’;
Assim fica garantindo a exclusão mútua dos processos.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
program Algoritmo 1;
var
 Vez	: char;
procedure Proc_A
begin
 repeat
 while (vez = ‘B’) do ; /nada
 Regiao_Critica_A;
 Vez := ‘B’;
 Processa_A;
 until false;
end;
procedure Proc_B
begin
 repeat
 while (vez = ‘A’) do ; /nada
 Regiao_Critica_B;
 Vez := ‘A’;
 Processa_B;
 until false;
end;
begin
 Vez := ‘A’;
 PARBEGIN
 Proc_A;
 Proc_B;
 PAREND;
end.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Algoritmo 1
Problema 1:	
O acesso ao recurso só pode ser efetuado por dois processos e sempre de maneira alternada;
O processo que utiliza o recurso mais vezes que o outro, permanecerá mais vezes bloqueado;
Por exemplo, de Proc_A ficar muito tempo no Processa_A, é possível que Proc_B queria usar o recurso e não o consiga, mesmo Proc_A não necessite do recurso.
Caso um processo tenha o loop mais rápido que o outro, a possibilidade de usar o recurso fica limitado ao processo de velocidade menor.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Algoritmo 1
Problema 2:
Se houver um problema com um processo de forma que o valor da variável de bloqueio não seja alterado, o outro processo permanecerá indefinidamente bloqueado. 
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Algoritmo 2
O problema principal do algoritmo 1 é que ambos processos trabalham com a mesma variável global, que indica qual processo terá acesso a região crítica;
Para resolver este problema o algoritmo 2 introduz uma variável para cada processo (CA e CB), que indica se o processo está na região crítica;
Assim antes de um processo entrar na sua região crítica, testa se o outro processo está usando o recurso;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
program Algoritmo 2;
var
 CA	: boolean;
 CB	: boolean;
procedure Proc_A
begin
 repeat
 while (CB) do ; /nada
 CA := true;
 Regiao_Critica_A;
 CA:= false;
 Processa_A;
 until false;
end;
procedure Proc_B
begin
 repeat
 while (CA) do ; /nada
 CB := true;
 Regiao_Critica_B;
 CB:= false;
 Processa_B;
 until false;
end;
begin
 CA:= false;
 CB:= false;
 PARBEGIN
 Proc_A;
 Proc_B;
 PAREND;
end.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Algoritmo 2
Neste caso o uso do recurso não é realizado, necessariamente, alternado;
Caso um processo tenha um problema fora da região crítica não bloqueia o outro processo;
Mas se um processo tiver um problema na região crítica ou antes de alterar o valor da variável, bloqueará, indefinidamente, o outro processo;
Mas, o mais grave é que este algoritmo nem sempre garante a exclusão mútua;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Algoritmo 3
Este algoritmo tenta solucionar o problema do algoritmo 2, colocando a instrução de atribuição de CA e CB antes do loop de teste;
Este algoritmo garante a exclusão mútua, mas introduz a possibilidade do bloqueio indefinido de ambos os processos;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
program Algoritmo 3;
var
 CA	: boolean;
 CB	: boolean;
procedure Proc_A
begin
 repeat
 CA := true;
 while (CB) do ; /nada
 Regiao_Critica_A;
 CA:= false;
 Processa_A;
 until false;
end;
procedure Proc_B
begin
 repeat
 CB := true;
 while (CA) do ; /nada
 Regiao_Critica_B;
 CB:= false;
 Processa_B;
 until false;
end;
begin
 CA:= false;
 CB:= false;
 PARBEGIN
 Proc_A;
 Proc_B;
 PAREND;
end.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Algoritmo 4
No algoritmo 3, cada processo altera o estado da sua variável desconhecendo o estado do outro processo – este é o problema;
Altera o algoritmo 3 de forma que altera o estado o estado da variável antes de entrar a região crítica (como no algoritmo 3), porém existe a possibilidade de reverter esta alteração;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
program Algoritmo 4;
var
 CA	: boolean;
 CB	: boolean;
 
procedure Proc_A
begin
 repeat
 CA := true;
 while (CB) do 
 begin
 CA:= false; 
 {pequeno intervalo de tempo aleatório}
 CA := true;
 end;
 Regiao_Critica_A;
 CA:= false; 
 Processa_A;
 until false;
end;
procedure Proc_B
begin
 repeat
 CB := true;
 while (CA) do 
 begin
 CB:= false; 
 {pequeno intervalo de tempo aleatório}
 CB := true;
 end;
 Regiao_Critica_B;
 CB:= false; 
 Processa_B;
 until false;
end;
begin
 CA:= false;
 CB:= false;
 PARBEGIN
 Proc_A;
 Proc_B;
 PAREND;
end.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Algoritmo 4
Esta solução garante exclusão mútua e não gera bloqueio simultâneo dos processos;
Mas, no caso dos tempos aleatórios serem próximos e a concorrência gerar uma situação onde os processos alterem as variáveis CA e CB para falso antes do término do loop, nenhum dos processos conseguirá executar a sua região crítica, mesmo não sendo permanente, esta situação pode gerar problemas
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Algoritmo de Dekker
Primeira solução de software que garantiu a exclusão mútua entre dois processos sem problemas foi proposto por T. Dekker;
Este algoritmo possui uma lógica bastante complexa;
Ver no livro texto as referencias;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Algoritmo de Peterson
Facilmente generalizada para N processos;
Similar ao algoritmo 3, além das variáveis de condição (CA e CB), introduz a variável Vez para gerar os conflitos gerados
pela concorrência;
Antes de acessar a região crítica, o processo sinaliza este desejo (variável de condição), porém o processo cede o uso do recurso (variável Vez);
O processo executa o while (protocolo de entrada);
Assim além de garantir a exclusão mútua, o bloqueio indefinido nunca ocorrerá, pelo uso da variável Vez;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
program Algoritmo_Peterson;
var
 CA	: boolean;
 CB	: boolean;
 Vez	: char; 
procedure Proc_A
begin
 repeat
 CA := true;
 Vez := ‘B’;
 while (CB and Vez = ‘B’) do ; /nada
 Regiao_Critica_A;
 CA:= false;
 Processa_A;
 until false;
end;
procedure Proc_B
begin
 repeat
 CA := true;
 Vez := ‘A’;
 while (CA and Vez = ‘A’) do ; /nada
 Regiao_Critica_B;
 CB:= false;
 Processa_B;
 until false;
end;
begin
 CA:= false;
 CB:= false;
 PARBEGIN
 Proc_A;
 Proc_B;
 PAREND;
end.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Exclusão Mútua
Algoritmo para exclusão mútua para N processos:
O algoritmo de Peterson foi generalizado para N processos, Hofri (1990);
O algoritmo do Padeiro (bakey Algorithm) proposto por Lamport(1974);
Problema espera ocupada (busy wait), este caso, quando um processo não consegue entrar em sua região crítica, este processo permanece em loop testando uma condição, consumino recurso do processador;
A solução para este problema foi a introdução de mecanismo de sincronismo que permitem colocar um processo em estado de espera, quando estiver esperando para entrar na região crítica. (semáforos e monitores)
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Sincronização Condicional
Sincronização condicional é quando o acesso a um recurso compartilhado exige uma sincronização entre os processos;
Exemplo clássico é a comunicação entre dois processos através de operações de gravação e leitura em um buffers;
Os processos devem estar sincronizados para que um processo não tente ler um buffer vazio nem gravar em um buffer cheio;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Sincronização Condicional
Este problema é conhecido como problema do produtor/consumidor ou do buffer limitado;
No algoritmo na próximo slide, o recurso compartilhado é um buffer, definido como tamanho TamBuf, sendo o acesso controlado pela variável Cont;
Cont:
Igual a zero: significa que o buffer está vazio, e o processo Consumidor deve esperar;
Igual a TamBuf: significa que o buffer está cheio, e o processo Produtor deve esperar; 
O algoritmo resolve a questão da sincronização condicional, mas apresenta o problema da espera ocupada;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Sincronização Condicional
PROGRAM Produtor_Consumidor_1;
 CONST TamBuf = ( *Tamanho *);
 TYPE Tipo_Dado = (* Tipo *);
 VAR Buffer : ARRAY [1..TamBuf] OF Tipo_Dado;
 Dado : Tipo_Dado;
 Cont : 0..TamBuf;
BEGIN
 Cont := 0;
 PARBEGIN
 Produtor;
 Consumidor;
 PAREND;
END. 
PROCEDURE Produtor;
BEGIN
 REPEAT
 Produz_Dado (Dado);
 WHILE (Cont = TamBuf) DO (*nada*);
 Grava_Buffer(Dado, Cont);
 UNTIL False;
END;
 
PROCEDURE Consumidor;
BEGIN
 REPEAT
 WHILE (Cont = 0) DO (*nada*);
 Le_Buffer (Dado);
 Consome_Dado(Dado, Cont);
 UNTIL False;
END;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Proposto por E. W. Dijkstra em 1965;
Mecanismo de sincronização que permite implementar a exclusão mútua e a sincronização entre processos de forma simples;
Tornou-se um dos principais mecanismos utilizados em projeto de S.O. e aplicações concorrentes;
A maioria das linguagens de programação disponibiliza rotinas para utilizá-los;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Semáforos são:
Uma variável inteira não negativa;
Manipulados através das seguintes operações indivisíveis:
UP (Proberen – teste): incrementa o valor da variável;
DOWN (Verhigen – incremento): decrementa o valor da variável;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Semáforos são:
A variável não pode ser negativa, assim um DOWN em um semáforo com valor zero, faz o processo entrar no estado de espera;
Normalmente implementada em hardware;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Os semáforos podem ser:
Binários (mutexes): só podem assumir os valores zero e um;
Contadores: podem assumir qualquer valor inteiro positivo e zero;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Exclusão mútua:
Pode ser implementada com o uso de semáforos binários associado aos recursos compartilhados;
Principal vantagem: não ocorre a espera ocupada;
As instruções DOWN e UP funcionam como protocolo de entrada e saída;
Quando o valor é um, indica que o recurso está disponível, e se for zero significa que algum processo está utilizando o recurso;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Exclusão mútua:
Quando for entrar na região crítica, o processo executa um DOWN;
Se o semáforo for igual a um, este valor é decrementado e o processo entra na região crítica;
Se o valor for zero, então o processo impedido de entrar na seção crítica, e seu estado passa a ser de espera, liberando o processador.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Exclusão mútua:
O processo ao sair da região crítica, deve liberar o recurso compartilhado, para tanto, basta executar a instrução UP;
Caso existam vários processos esperando a liberação do recurso, o S.O. selecionará um, mudando seu estado de espera para pronto – próximo slide;
Não existe a espera ocupada;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Semáforo binário na exclusão mútua
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
TYPE Semaforo =record
 Valor : integer;
 Fila_espera: (*lista dos processos em espera*)
 end;
Procedure DOWN (VAR S: Semaforo);
begin
 if (S = 0) then Coloca_Processo_na_Fila_de_Espera
 else S = S – 1;
End;
Procedure UP (VAR S: Semaforo);
begin
S = S + 1;
If (Processo_Esperando) then Retira_da_Fila_de_Espera.
End;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Program Semaforo_1
Var 
 S : Semaforo = 1;
Procedure Proc_A;
begin
 repeat 
 DOWN(S);
 Região_Critica_A;
 UP (S);
 until false;
end;
Procedure Proc_B;
begin
 repeat 
 DOWN(S);
 Região_Critica_B;
 UP (S);
 until false;
end;
begin
 PARABEGIN
 Proc_A;
 Proc_B;
 PARAEND;
End.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Sincronização condicional:
Pode-se implementar a sincronização condicional;
Exemplo: solicitação de E/S, o processo que solicita a E/S executa um DOWN e fica em estado de espera até a operação de E/S ser completada;
Quando a operação de E/S finaliza a rotina de tratamento de interrupção excuta um UP, liberando o processo do estado de espera;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Program
Semaforo_2;
var 
 Evento: Semaforo := 0;
Procedure Solicita_Leitura;
begin
 DOWN(Evento)
End;
Procedure Le_Dados;
Begin
 UP(Evento)
End;
Begin
 PARABEGIN
 Solicita_leitura;
 Le_Dados;
 PARAEND;
End;
Algoritmo para sincronização condicional:
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
O problema do produtor/consumidor pode ser resolvido com o uso de semáforos;
Para tanto:
Usa buffer de duas posições;
Um semáforo binário para garantir a exclusão mútua;
Dois semáforos contadores (Vazio e Cheio) para a sincronização condicional;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Program Produtor_consumidor_2
Const TB = 2;
TYPE TDado = (*qualquer*)
VAR
 Vazio: semaforo := TB;
 Cheio: semaforo := 0;
 Mutex: semaforo := 1;
 Buffer: array[1..TB] of TDado;
 Dado_1: TDado;
 Dado_2: TDado;
Procedure Produtor
begin
 repeat
 Produz_Dado (Dado_1);
 Down (Vazio);
 Down (Mutex);
 Grava_Buffer(Dado_1, Buffer);
 Up(Mutex);
 Up(Cheio);
 until false;
end; 
Procedure consumidor;
begin
 repeat
 Down(Cheio);
 Down(Mutex);
 Le_Buffer(Dado_2, buffer);
 Up(Mutex);
 Up(Vazio);
 until false;
End;
begin
 parabegin
 Produtor;
 Consumidor;
 paraend;
end. 
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Semáforos contadores são úteis quando existem processos concorrentes alocando recursos do mesmo tipo (pool de recursos);
O semáforo começa com número total de recursos do pool;
Quando necessitar de recurso executa um DOWN;
Quando liberar o recurso executa um UP;
Caso o semáforo contador seja zero, o processo que executar um DOWN ficará em estado de espera.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Semáforos
Problemas
Problema dos filósofos;
Problema do barbeiro; 
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Monitores são mecanismos de sincronização de alto nível que tornam mais simples o desenvolvimento de aplicações concorrentes;
Proposto por Binch Hansen, 1972 e desenvolvido por C.A.R. Hoare em 1974;
Mecanismo de sincronização estruturado, diferente de semáforos, considerados não-estruturados; 
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Diferentemente dos semáforos, os monitores são implementados pelo compilador, menos sujeito a erros;
Inicialmente implementado em poucas linguagens (Concurrent Pascal, Modula-2, Modula-3) 
Atualmente, a maioria das linguagens disponibiliza este recurso;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
O monitor é formado por procedimentos e variáveis encapsulado dentro de um módulo;
Sua principal característica é a implementação da exclusão mútua entre os procedimentos declarados;
Toda vez que é chamado um dos procedimentos, o monitor verifica se outro procedimento esta sendo executado, em caso afirmativo, o procedimento que quer ser executado fica em espera;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Toda inicialização de variáveis é realizada por um bloco de comandos, sendo executada apenas uma vez, na ativação do programa;
Um monitor é definido especificando:
Um nome;
Declarando:
 variáveis locais;
Procedimentos;
Código de inicialização;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Estrutura do monitor
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Monitor Exclusao_Mutua;
(* variáveis locais *)
procedure Regiao_Critica_1;
begin
:
End; 
Procedure Regiao_Critica_2;
Begin
:
end; 
Procedure Regiao_Critica_3;
begin
:
end; 
begin
 (* código de inicialização *)
end.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Exclusão mútua
A implementação mútua utilizando monitores não é realizada diretamente pelo programador;
As regiões críticas são definidas como procedimentos no monitor e o compilador garante a exclusão mútua;
A comunicação do procedimento e monitor é executada através de chamada a procedimentos e dos parâmetros passados;
A seguir, um exemplo, onde processos somam e subtraem um concorrentemente; 
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
program monitor_1
Monitor Rgião_Critica;
var
 X		: integer;
 procedure Soma;
 begin
 X := X + 1;
 end;
Procudure Subtrai;
 begin
 X := X – 1;
 end;
begin
 X:= 0;
end;	
begin
 PARABEGIN
 Regiao_Critica.Soma;
 Regiao_Critica.Susbtrai;
 PARAEND;
end;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Sincronização condicional:
A sincronização condicional pode ser implementada utilizando-se de monitores 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;
Esta variáveis são manipuladas através de duas instruções:
WAIT;
SIGNAL;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Sincronização condicional:
WAIT coloca o processo no estado de espera, até que outro processo envie um SIGNAL, informado que a condição de espera foi satisfeita;
Caso se execute um SIGNAL sem que um processo esteja aguardando, nenhum efeito terá;
É possível ter vários processos com sua execução suspensa, assim, o monitor organiza filas associadas as condições de sincronização;
O SIGNAL libera apenas um único processo da fila de espera da condição associada;
Um processo pode executar um procedimento no monitor, mesmo quando um ou mais processos estão na fila de espera;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Estrutura do monitor com variáveis de condição
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Sincronização condicional:
Uma solução para o problema do produtor/consumidor usando-se monitor é apresentado no próximo slide;
O monitor condicional é estruturado com duas variáveis especiais de condição (cheio e vazio) e dois procedimentos (produz e consome)
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Monitor Condicional;
Var
 Cheio	: (* variável especial de condição *)
 Vazio	: (* variável especial de condição *)
 procedure Produz;
 begin
 if (Cont = TamBuf) then WAIT (cheio);
 :
 if (Cont = 1) then SIGNAL (vazio);
 end;
 procedure Consume;
 begin
 if (Cont = 0) then WAIT (vazio);
 :
 if (Cont = Tambuf - 1) then SIGNAL (cheio);
 end;
begin
end;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Sempre que o produtor desejar gravar um dado, deve chamar o procedimento Produz, que testa se existe posições vagas no buffer, se não tiver, deve executar um WAIT em cheio, suspendendo a execução até que um outro processo execute um SIGNAL em cheio;
No caso do consumidor, deve executar o procedimento Consume sempre que desejar ler um dado do buffer, caso o buffer esteja vazio deve suspender a sua execução efetuando um WAIT no vazio e esperar um SIGNAL no vazio para continuar;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
No
próximo slide uma solução completa para o problema Produtor/Consumidor utilizando-se de monitor condicional;
Os procedimentos Produz_Dado e Consome_Dado servem para entrada e saída de dados;
Os procedimentos Grava_Dado e Le_Dado são responsáveis pela transferência e recuperação do dado no buffer;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Monitores
Program Pro_Con_3;
Const
 TamBuf = (* tamanho do buffer *)
 Dado : array[1..TamBuf] of (*tipo dado *)
Monitor Condicional;
Var
 Cheio : (* variável especial de condição *)
 Vazio : (* variável especial de condição *)
 Cont : integer;
 procedure Produz;
 begin
 if (Cont = TamBuf) then WAIT (cheio);
 Grava_Dado (Dado, buffer);
 Cont = Cont + 1;
 if (Cont = 1) then SIGNAL (vazio);
 end;
 procedure Consume;
 begin
 if (Cont = 0) then WAIT (vazio);
 Le_Dado (Dado, buffer);
 Cont = Cont - 1;
 if (Cont = Tambuf-1) then SIGNAL (cheio);
 end;
begin
 Cont := 0;
end;
procedure Produtor
begin
 repeat
 Produz_Dado (Dado);
 Condicional.Produz;
until false;
end;
Procedure Consumidor;
begin
 repeat
 Condicional.Consome;
 Consome_Dado (Dado);
 until false;
end;
begin
 PARABEGIN
 Produtor;
 Consumidor;
 PARAEND;
end.
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
Troca de mensagens é um mecanismo de comunicação e sincronização entre processos;
O S.O. possui um subsistema de troca de mensagens, sem que haja necessidade do uso de variáveis compartilhadas;
Para a comunicação entre processos deve existir um canal de comunicação, este podendo ser um buffer ou um linke de comunicação;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
Os processos cooperativos trocam mensagens através de duas rotinas:
SEND(receptor, mensagem);
Envia uma mensagem para um processo receptor;
RECEIVE (transmissor, mensagem);
Recebe a mensagem enviada por um processo transmissor;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
Transmissão de mensagem
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
Este mecanismo exige que os processos envolvidos tenham suas execuções sincronizadas;
Isto é necessário, já que a mensagem só pode ser tratada após o seu recebimento;
Ou que o envio de uma mensagem pode ser condição para a continuação da execução do processo;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
a troca de mensagens pode ser implementada de duas formas:
Comunicação direta; 
Comunicação indireta;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
Comunicação direta
Exige ao enviar ou receber uma mensagem o processo enderece explicitamente o nome do processo receptor ou transmissor;
Só permite a troca de mensagens entre dois processos;
O principal problema é a necessidade de especificação do nome dos processos envolvidos;
Se mudar a identificação dos processos deve-se alterar o código do programa;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
Comunicação direta
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
Comunicação indireta;
Utiliza-se uma área compartilhada, onde as mensagens pode ser escritas e lidas;
Esse tipo de buffer é conhecido como mailbox ou port;
Suas características (identificação, capacidade, etc.) são definidas no momento a criação;
Vários processos podem estar associado a um mailbox, e as rotinas SEND e RECEIVE passam o nome do mailboxes e não mais o nome dos processos;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
Comunicação indireta
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
Independente do mecanismo de comunicação utilizado, os processos envolvidos devem ter suas execuções sincronizadas em função do fluxo de mensagens;
Um processo não pode tratar de uma mensagem que não recebeu;
Um processo não pode receber a mesma mensagem mais de uma vez;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
Esquemas para implementar o sincronismo:
Manter o processo transmissor esperando até a confirmação de leitura;
Um processo ao tentar receber uma mensagem ainda não enviada, deve permanecer esperando até que o processo transmissor faça o envio;
Este esquema implementa uma comunicação síncrona, conhecida como rendezvous;
O problema é que a execução dos processos fica limitado ao tempo de processamento da mensagens;
Uma variação mais eficiente de rendezvous, é não bloquear o processo transmissor; 
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
Esquemas para implementar o sincronismo:
No terceiro esquema é implementado uma forma assíncrona de comunicação;
O processo transmissor e receptor não permanecem esperado o envio e recebimento da mensagem;
Além dos buffers para armazenar as mensagens devem haver mecanismos para permitir ao processo identificar se uma mensagem já foi enviada ou recebida;
A grande vantagem é aumentar a eficiência de aplicações concorrentes;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Troca de Mensagens
Program Prod_Con_4
procedure Produtor;
Var
 msg	: Tipo_Msg;
begin
 repeat 
 Produz_Mensagem(Msg);
 SEND(Msg);
 until false;
end; 
procedure Consumidor;
Var
 msg	: Tipo_Msg;
begin
 repeat 
 RECEIVE(Msg);
 Consome_Mensagem(Msg);
until false;
end;
begin
 PARABEGIN
 Produtor;
 Consumidor;
 PARAEND;
End. 
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Deadlock é a situação em que um processo aguarda por um recurso que nunca estará disponível;
Normalmente, conseqüência de compartilhamento de recursos em processos concorrentes onde a exclusão mútua é exigida;
Torna-se mais freqüente e crítico com a evolução dos S.O. implementado o paralelismo e alocação dinâmica de recursos;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Próxima figura exemplo de deadlock conhecido como espera circular;
Cada processo espera que outro processo libere o recurso alocado;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Espera circular
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Condições necessárias
Exclusão mútua;
 cada recurso só pode estar alocado a um único processo;
Espera por recurso;
Um processo pode estar esperando por outros recursos
Não-preempção;
Um recurso não pode ser liberado de um processo, só porque outros processos desejam o mesmo recurso;
Espera circular;
Um processo pode ter de esperar por um recurso alocado a outro processo e vice-versa;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Deadlock existe em qualquer sistema multiprogramável;
As solução implementas devem considerar o tipo do sistema e o impacto em seu desempenho;
usina nuclear x folha de pagamento
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Prevenção
Para evitar o deadlock evitar que uma das condições citadas não ocorra;
Ausência da primeira condição (exclusão mútua), a falta da exclusão mútua
gerará várias inconsistências já mencionadas;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Ausência da segunda condição (espera por recurso):
Processos que já possuam recursos garantidos não devem requisitar novos recursos;
Uma forma é pré-alocar todos os recursos necessários a um processo;
Esta solução pode gerar um grande desperdício de recursos;
É difícil determinar o número de recursos que um processo utiliza;
O mais grave é a possibilidade sofrer starvation;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Ausência da terceira condição (não-preempção):
Pode ser evita se permitir que um recurso seja retirado do processo no caso de outro precisar;
A liberação de recursos já garantidos pode ocasionar sérios problemas, podendo até impedir a continuidade do processo;
Pode ocorre starvation;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Ausência da quarta condição (espera circular);
Forçar que o processo só tenha um recurso por vez;
Esta condição restringiria muito o grau de compartilhamento e o processamento de programas;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
A prevenção de Deadlock (evitando uma das quatro condições) é bastante limitada e não é utilizada na prática;
É possível evitar o deadlock, mesmo com as quatro condições presentes;
A solução mais conhecida é o Algoritmo do Banqueiro (Bank’s Algorithm) proposto por Dijkstra(1965);
Basicamente, este algoritmo exige que os processos informem o número máximo de cada tipo de recurso necessário a sua execução;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Com estas informações, é possível definir o estado de alocação de cada recurso, que é a relação entre o número de recursos alocados e disponíveis e o número máximo de processos que necessitam desses recursos.
Com estas informações, o S.O. pode alocar os recursos evitando o deadlock (Tanenbaum 2001);
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Este algoritmo possui várias limitações, a maior é a necessidade de um número fixo de processos ativos e de recursos disponíveis;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Detecção do deadlock
É necessário mecanismos de detecção de deadlock, onde não existam prevenção de deadlock;
Esta detecção identifica a existência de deadlock e quais os recursos e processos envolvidos neste problema;
Para tanto é necessário ao S.O. manter estruturas de dados para identificar cada recurso do sistema, o processo que o está alocando e os processos que estão a espera para usar o recurso;
Geralmente os algoritmos que verificam a espera circular percorrem esta estrutura sempre que um processo solicita um recurso;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Detecção do deadlock
Dependendo do S.O. o ciclo de busca de deadlock pode variar;
Em sistema de tempo compartilhado o tempo de busca pode ser maior, sem comprometer-lo;
Sistemas de tempo real devem constantemente verificar, porém a maior segurança leva a um maior overhead;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Correção
Uma solução bastante utilizada é eliminar um ou mais processos envolvidos no deadlock desalocando recursos, quebrando assim a espera circular;
A eliminação de processos não é simples, dependendo do tipo de recurso envolvido;
Por exemplo: impressão e gravação em disco;
Os processos eliminados não tem como ser recuperados, mas os outros processos envolvidos no deadlock continuarão;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Correção
A escolha do processo, normalmente, é feita de forma aleatória, ou com base em algum tipo de prioridade;
Este esquema pode consumir tempo considerável do processador, aumentando overhead;
Uma solução menos drástica envolve a liberação de alguns recursos até que o ciclo termine;
Para esta solução ser eficiente, é necessário que o sistema pode suspender um processo, liberar seus recursos e após a solução, possa retornar ã execução, sem perder o processamento já realizado;
Arquitetura de Sistemas Operacionais – Machado/Maia
Cap. 7 – Sincronização e Comunicação
*
Deadlock
Correção
Este mecanismo é conhecido com rollback:
Além do overhead;
É muito difícil de ser implementado;
É bastante dependente da aplicação;