Sistemas Operacionais aula 05

Prévia do material em texto

CCT0011 – Sistemas Operacionais
Aula 05 – Comunicação entre Processos (1ª parte)
Professor Ricardo Bernardo
Sistemas Operacionais
Conteúdo da Aula
Breve Revisão Última Aula
Comunicação entre Processos
Solução de Hardware
Solução de Software
Sistemas Operacionais
Estrutura do conteúdo
Especificação de concorrência em programas
Problemas de compartilhamento de recursos
Exclusão mútua
Sincronização condicional
Aplicações concorrentes
É comum processos que trabalham juntos (concorrentes) 
compartilharem recursos do sistema:arquivos, 
dispositivos de E/S e áreas de memória.
Não importa quais recursos são compartilhados, pois os 
problemas decorrentes dessa interação serão os 
mesmos.
O compartilhamento de recursos entre processos pode 
gerar situações indesejáveis, capazes até de 
comprometer o sistema
Sistemas Operacionais
Introdução
A comunicação entre processos de uma aplicação pode ser necessária e alguns mecanismos são 
utilizados para isso, como: variáveis compartilhadas em memória ou troca de mensagens.
Neste caso os processos concorrentes precisam que mecanismos do SO sincronizem suas execuções.
Compartilhamento de recursos entre processos pode gerar situações indesejáveis
Os mecanismos que garantem a comunicação entre processos concorrentes e o acesso a recursos 
compartilhados são chamados de mecanismos de sincronização.
No projeto de sistemas operacionais multiprogramáveis , é fundamental a implementação de 
mecanismos de sincronização que garantam sua integridade e confiabilidade.
Sistemas Operacionais
Processo
gravador
Processo
leitor
dado
Sincronização
leit
ura
gravação
Buffer
Aplicações Concorrentes
• Dois processos concorrentes trocam informações através de operações de gravação e leitura em um 
buffer. Um processo só poderá gravar dados no buffer caso ele não esteja cheio.
• Da mesma forma, um processo só poderá ler dados armazenados do buffer se existir algum dado 
para ser lido.
• Em ambos os casos, os processos deverão aguardar até que o buffer esteja pronto para as operações 
de gravação ou de leitura.
Sistemas Operacionais
O programa A começa a ser processado e, ao 
encontrar o comando FORK, faz com que seja 
criado um outro processo para a execução do 
programa B concorrentemente a A.
O comando JOIN permite que o programa A 
sincroniza-se com B, ou seja, quando o 
programa A encontrar JOIN, só continuará a 
ser processado após o término de B.
Especificação de concorrência
Primeira notação para especificação da concorrência: FORK e JOIN
FORK – Inicia a execução de outro programa concorrentemente
JOIN – O programa chamador espera o outro programa terminar para continuar o 
processamento
PROGRAM A;
. PROGRAM B;
. .
FORK B; .
. .
. .
JOIN B; .
. END
.
END.
Sistemas Operacionais
O comando PARBEGIN (COBEGIN) especifica que 
a sequência de comandos seja executada 
concorrentemente em uma ordem 
imprevisível, através da criação de um 
processo (processo1, processo2, ...).
O comando PAREND (COEND) define um ponto 
de sincronização, onde o processamento só 
continuará quanto todos os processos 
criados já tiverem terminados suas 
execuções.
Especificação de concorrência
Sistemas Operacionais
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.
Os comandos de atribuição situados entre 
PARBEGIN e PAREND são executados 
concorrentemente entre si. 
O cálculo final de X só poderá ser 
realizado quando todas as variáveis 
dentro da estrutura tiverem sido 
calculadas.
Especificação de concorrência
Sistemas Operacionais
Para compreendermos melhor por que a sincronização entre processos é 
fundamental quando recursos são compartilhados em sistemas 
multiprogramáveis, veremos alguns problemas aplicados a duas situações 
práticas:
• A Alteração de uma variável em memória.
• A alteração de um arquivo compartilhado de um arquivo em disco;
Problemas de compartilhamento de recursos
Sistemas Operacionais
Suponha que dois processos (A e B) estejam executando um comando de atribuição, onde o processo A 
some 1 a variável X, e o processo B diminua 1 da mesma variável que está sendo compartilhada. 
Inicialmente vamos considerar que a variável X possua o valor 2.
Processo A Processo B
X := X + 1; X := X - 1;
Os comandos de atribuição, em uma linguagem de alto nível, podem ser decompostos em comandos mais 
elementares:
Processo A Processo B
LOAD x,Ra LOAD x,Rb
ADD 1,Ra SUB 1,Rb
STORE Ra,x STORE Rb,x
Problemas de compartilhamento de recursos
Sistemas Operacionais
Processo Comando X Ra Rb 
A LOAD X,Ra 2 2 *
A ADD 1,Ra 2 3 *
B LOAD X,Rb 2 * 2
B SUB 1,Rb 2 * 1
A STORE Ra,X 3 3 *
B STORE Rb,X 1 * 1
Problemas de compartilhamento de recursos
• Imaginemos que o processo A carregue o valor de 
X no registrador Ra, some 1 a ele , no momento 
em que vai armazenar o valor em X, seja 
interrompido.
• Neste instante, o processo B inicia sua execução, 
carregando o valor de X em Rb e subtraindo 1 
dele. 
• O processo A volta a ser processado e atribui o 
valor 3 a X, terminando, assim, sua execução, 
• Finalmente, o processo B é processado e atribui o 
valor 1 a X, sobrepondo o valor anterior
Sistemas Operacionais
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.
Suponha um arquivo de contas bancárias 
(Arq_contas), onde cada cliente tem seu 
saldo controlado. 
O programa abaixo, atualiza o saldo de um 
cliente, após um lançamento.
O programa lê o registro do cliente no arquivo 
(Reg_Cliente);
Lê o valor a ser depositado ou retirado 
(Valor_dep_Ret), e
Atualiza o saldo no arquivo de contas.
Problemas de compartilhamento de recursos
Sistemas Operacionais
Dois caixas diferentes estão atualizando o saldo de um mesmo cliente simultaneamente:
• O primeiro caixa lê o registro do cliente e soma ao campo Saldo o valor do lançamento.
• Antes de gravar o novo saldo no arquivo, outro caixa lê o registro do mesmo cliente, que está sendo 
atualizado, para realizar outro lançamento.
• Independentemente de qual dos caixas atualize primeiro o saldo no arquivo, o dado gravado estará 
inconsistente.
Caixa Comando Saldo arquivo Valor dep/ret Saldo memória
1 READ 1.000 * 1.000
1 READLN 1.000 -200 1.000
1 := 1.000 -200 800
2 READ 1.000 * 1.000
2 READLN 1.000 +300 1.000
2 := 1.000 +300 1.300
1 WRITE 800 -200 800
2 WRITE 1.300 +300 1.300
Problemas de compartilhamento de recursos
Sistemas Operacionais
Analisando os dois exemplos, concluímos que em 
qualquer situação, onde dois ou mais processos 
tenham acesso a um mesmo recurso compartilhado, 
devam existir mecanismos de controle que evitem 
esses tipos de problemas.
Solução.............
Problemas de compartilhamento de recursos
Sistemas Operacionais
A solução maissimples, para evitar os problemas de compartilhamento, é 
impedir que dois ou mais processos acessem um mesmo recurso no 
mesmo instante.
Enquanto um processo estiver acessando determinado recurso, todos os 
outros que queiram acessar esse mesmo recurso deverão esperar até que 
o primeiro processado termine o acesso.
Essa ideia de exclusividade de acesso é chamada de exclusão mútua.
Exclusão Mútua
Sistemas Operacionais
Região crítica
Protocolos de acesso
BEGIN
.
.
Entra_Regiao_Critica;
Regiao_Critica;
Sai_Regiao_Critica;
.
.
END.
A exclusão mútua deve apenas afetar os processos 
concorrentes quando um deles estiver fazendo o acesso ao 
recurso compartilhado.
A parte do código do programa onde é feito o acesso ao 
recurso compartilhado é denominado região crítica.
Os mecanismos que implementam a exclusão mútua utilizam 
um protocolo de acesso à região crítica.
Toda vez que um processo for executar sua região crítica, ele 
obrigatoriamente executará antes, um protocolo de entrada 
nessa região. 
Da mesma forma que, ao sair, deverá executar um protocolo de 
saída.
Exclusão Mútua
Sistemas Operacionais
Aplicação dos protocolos para dois processos (A e B), manipulando o arquivo contas:
• Sempre que o processo A for atualizar o saldo de um cliente, antes de ler o registro, ele deverá 
garantir o acesso exclusivo através do protocolo de entrada na sua região crítica.
• O protocolo indica se já existe ou não algum processo acessando o registro.
• Caso o processo A esteja em sua região crítica e o processo B tente acessar o mesmo registro, o 
protocolo de entrada faz com que ele fique aguardando, até que o processo A termine o acesso ao 
recurso.
• Quando o processo A termina a execução de sua região crítica, deve sinalizar, aos outros 
processos concorrentes, que terminou o acesso ao recurso.
• Isso é realizado através do protocolo de saída que informa aos outros processos que podem 
tentam acessar o recurso com sucesso.
Região Crítica
Sistemas Operacionais
Processos com diferença nos tempos de processamento podem introduzir 
problemas na exclusão mútua.
Para garantir a implementação da exclusão mútua os processos envolvidos 
devem fazer acesso aos recursos de forma sincronizada
Diversas soluções foram desenvolvidas com este propósito; porém, além da 
garantia da exclusão mútua, duas situações indesejadas também devem 
ser evitadas.
Conclusão
Sistemas Operacionais
A primeira situação indesejada é conhecida como starvation ou espera indefinida. Situação em que um 
processo nunca consegue executar sua região crítica, e consequentemente, acessar o recurso 
compartilhado.
• Ocorre quando dois ou mais processos esperam por um mesmo recurso alocado. Caso o 
sistema escolha o processo aleatoriamente quando o recurso é liberado, um processo pode 
nunca ser escolhido
• Quando um processo tem baixa prioridade também pode nunca ser escolhido.
• Filas FIFO eliminam esse problema.
Starvation
Sistemas Operacionais
Exemplo1: 
No momento em que um recurso é liberado, o sistema operacional possui um critério para selecionar, 
dentre os processos que aguardam pelo uso do recurso, qual será o escolhido;
Em função deste critério, o starvation pode ocorrer.
Exemplo 2:
Outra situação indesejada é aquela que um processo fora da sua região crítica impede que outros 
processos entrem nas suas próprias regiões críticas.
No caso desta situação ocorrer, um recurso estaria livre, porém alocado a um processo.
Neste caso vários processos estariam sendo impedidos de utilizar o recurso, reduzindo o grau de 
compartilhamento.
Starvation
Sistemas Operacionais
Desabilitar interrupções
BEGIN
.
.
Desabilita_Interrupcoes;
Regiao_Critica;
Habilita_Interrupcoes;
.
.
END
O processo desabilita todas as interrupções antes de 
entrar na sua região crítica, e as reabilita após deixar a 
região crítica.
Problemas: 
• Se o processo não habilitar as interrupções ao sair da 
região crítica, o sistema pode ficar comprometido.
• Multiprogramação seriamente comprometida.
Exclusão Mútua – Soluções de Hardware
Sistemas Operacionais
Instrução Test-and-Set
Test-and-Set (X,Y);
Instrução especial que permite ler uma variável, armazenar seu
conteúdo em outra área e atribuir um novo valor à mesma
variável;
Quando executada o valor lógico da variável Y é copiado para X, 
sendo atribuído À variável Y o valor lógico verdadeiro.
• Executa sem interrupção e é uma instrução invisível
• Assim, dois processos não podem manipular uma variável 
compartilhada ao mesmo tempo (exclusão mútua).
• A principal desvantagem é a possibilidade de starvation, pois a 
seleção do processo para acesso ao recurso é arbitrária. 
Exclusão Mútua – Soluções de Hardware
Sistemas Operacionais
PROGRAM Test_And_Set;
VAR Bloqueio : BOOLEAN;
PROCEDURE Processo_A;
VAR Pode_A : BOOLEAN;
BEGIN
REPEAT
Pode_A := True;
WHILE (Pode_A) DO 
Test_ans_set (Pode_A, Bloqueio);
Regiao_Critica_A;
Bloqueio := False;
until False;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
Pode_B := True;
WHILE (Pode_B) DO 
Test_ans_set (Pode_B, Bloqueio);
Regiao_Critica_B;
Bloqueio := False;
until False;
END;
BEGIN
Bloqueio := False;
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END.
Processo Instrução Pode_A Pode_B Bloqueio
A REPEAT * * False
B REPEAT * * False
A Pode_A:= True true * False
B Pode_B:= True * True False
B while * True False 
B test_and_set * False true
A while true * true
A test_and_set true * true
B regiao_critica * False true
A while true * true
B bloqueio := false * False false
B until false * False false
B REPEAT * False false
Instrução test_and_set
Sistemas Operacionais
Fatores para a solução de problemas de sincronização:
O número de processadores e o tempo de execução dos processos concorrentes devem ser irrelevantes;
Um processo, fora de sua região crítica, não pode impedir que outros processos entrem em suas próprias 
regiões críticas;
Um processo não pode permanecer indefinidamente esperando para entrar em sua região crítica.
Soluções:
• Primeiro, segundo, terceiro e quarto algoritmos:
• Algoritmo de Dekker
• Algoritmo de Peterson
• Algoritmo para exclusão mútua entre N processos
Exclusão Mútua – Soluções de Software
Sistemas Operacionais
Este algoritmo apresenta uma solução para a exclusão mútua entre dois processos, onde um 
mecanismo de controle alterna a execução das regiões críticas.
Limitações: 
O acesso ao recurso compartilhado só pode ser realizado por dois processos e sempre de 
maneira alternada. 
Outro problema é que caso ocorra algum problema com um dos processos, de forma que a 
variável de bloqueio não seja alterada, o outro processo permanecerá indefinidamente 
bloqueado, aguardando o acesso ao recurso.
Primeiro Algoritmo
Sistemas Operacionais
PROGRAM Algoritmo1;
VAR vez : CHAR;
PROCEDURE Processo_A;
BEGIN
REPEAT
WHILE (vez = “B”) DO (* Não faz 
nada*);
Região_Critica_A;
Vez := “B”;
Processamento_A;
until False;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
WHILE (vez = “A”) DO (* Não faz 
nada*);
Região_Critica_B;
Vez := “A”;
Processamento_BA;
until False;
END;
BEGIN
vez := A;
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END.
Processo_A Processo_B vez
While(vez = “B”) While(vez = “A” A 
Regiao_critica_A While(vez = “A”) A 
vez := “B” ) While(vez = “A” B 
Processamento_A Regiao_critica_B B 
Processamento_A vez :=“A” A
Processamento_A Processamento_B A 
O acesso ao recurso compartilhado só pode realizado por dois processos e sempre 
da maneira alternada. Com isso, um processo que necessite utilizar o recurso mais 
vezes do que o outro, permanecerá grande parte do tempo bloqueado.
Um outro problema é no caso da ocorrência de algum problema com um dos 
processos, de forma que a variável de bloqueio não seja alterada, o outro recurso 
permanecera indefinidamente bloqueado, aguardando o acesso ao recurso.
Primeiro Algoritmo
Sistemas Operacionais
PROGRAM Algoritmo2;
VAR CA, CB : BOOLEAN;
PROCEDURE Processo_A;
BEGIN
REPEAT
WHILE (CB) DO (* Não faz nada*);
CA := true;
Região_Critica_A;
CA := false;
Processamento_A;
until False;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
WHILE (CA) DO (* Não faz nada*);
CB := true;
Região_Critica_B;
CB := false;
Processamento_B;
until False;
END;
BEGIN
CA:= false; 
CB := false;
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END.
Processo_A Processo_B CA CB
While(CB) While(CB) false false
CA := true CB :+ true true true
Região_critica_A Regiao_critica_B true true
Neste caso é utilizada uma variável distinta para cada processo. 
Caso ocorra algum problema com um dos processo fora da região crítica, o outro 
processo não ficará bloqueado.
Caso um processo tenha um problema dentro da sua região crítica ou antes de 
alterar a variável, o outro processo permanecerá indefinidamente bloqueado.
Outro problema neste caso é que a exclusão mútua nem sempre é garantida.
Segundo Algoritmo
Sistemas Operacionais
PROGRAM Algoritmo3;
VAR CA, CB : BOOLEAN;
PROCEDURE Processo_A;
BEGIN
REPEAT
CA := true;
WHILE (CB) DO (* Não faz nada*);
Região_Critica_A;
CA := false;
Processamento_A;
until False;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
CB := true; 
WHILE (CA) DO (* Não faz nada*);
Região_Critica_B;
CB := false;
Processamento_B;
until False;
END;
BEGIN
CA:= false; 
CB := false;
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END.
Processo_A Processo_B CA CB
While(CB) While(CB) false false
CA := true CB :+ true true true
Região_critica_A Regiao_critica_B true true
O algoritmo tenta solucionar o problema apresentado no segundo, colocando a 
instrução de atribuição das variáveis CA e CB antes do loop de teste.
Esta alteração resulta na garantia da exclusão mútua, porém introduz um novo 
problema, é a possibilidade de bloqueio indefinido de ambos os processos.
Caso os dois processos alterem as variáveis CA e CB antes da execução da instrução 
WHILE, ambos os processos não poderão entrar em suas regiões críticas, como se o 
recurso já estivesse alocado.
Terceiro Algoritmo
Sistemas Operacionais
PROGRAM Algoritmo4;
VAR CA, CB : BOOLEAN;
PROCEDURE Processo_A;
BEGIN
REPEAT
CA := true;
WHILE (CB) DO (* Não faz nada*);
BEGIN 
CA := false
(pequeno intervalo de tempo aleatório)
CA := true
END;
Região_Critica_A;
CA := false;
until False;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
CB := true; 
WHILE (CA) DO (* Não faz nada*);
BEGIN 
CB := false
(pequeno intervalo de tempo aleatório)
CB := true
END;
Região_Critica_B;
CB := false; 
until False;
END;
BEGIN
CA:= false; 
CB := false;
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END.
Apesar de esta solução garantir a exclusão mútua e não gerar o 
bloqueio simultâneo dos processos, uma nova situação indesejada pode 
ocorrer eventualmente. 
No caso dos tempos aleatórios serem próximos e a concorrência gerar 
uma situação onde os dois processos alterem as variáveis CA e CB para 
falso antes do término do loop, nenhum dos dois processos conseguirá 
executar sua região crítica. 
Mesmo com esta situação não sendo permanente, pode gerar alguns 
problemas.
Quarto Algoritmo
Sistemas Operacionais
Primeira solução de software que garantiu a exclusão mútua entre dois 
processos sem a incorrência de outros problemas. Foi proposta pelo 
matemático holandês T. Dekker com base no primeiro e no quarto algoritmos, 
porém possui uma solução bastante complexa. 
Algoritmo de Dekker
Sistemas Operacionais
PROGRAM Algoritmo_peterson
VAR CA, CB : BOOLEAN;
vez : CHAR;
PROCEDURE Processo_A;
BEGIN
REPEAT
CA := true;
Vez := `B`; 
WHILE (CB and Vez = `B`) DO (* Não faz 
nada*);
Região_Critica_A;
CA := false;
processamento_A; 
until False;
END;
PROCEDURE Processo_B;
BEGIN
REPEAT
CB := true;
Vez := `A`; 
WHILE (CA and Vez = `A`) DO (* Não faz 
nada*);
Região_Critica_B;
CB := false; 
Processamento_B;
until False;
END;
BEGIN
CA := false; 
CB := false;
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END.
Antes de acessar a região crítica, o processo sinaliza esse desejo 
através da variável de condição, porém o processo cede o uso do 
recurso ao outro processo, indicado pela variável Vez. 
Em seguida, o processo executa o comando WHILE como protocolo 
de entrada da região crítica.
Neste caso, além da garantia da exclusão mútua, o bloqueio 
indefinido de um dos processos no loop nunca ocorrerá, já que a 
variável Vez sempre permitirá a continuidade da execução de um dos 
processos. 
Algoritmo de Peterson
Sistemas Operacionais
Sincronização condicional é uma situação onde o acesso ao recurso compartilhado exige a 
sincronização de processos vinculada a uma condição de acesso.
Um recurso pode não se encontrar pronto para uso devido a uma condição específica. Neste caso, o 
processo que deseja acessá-lo deverá permanecer bloqueado até que o recurso fique disponível.
Um exemplo clássico desse tipo de sincronização é a comunicação entre dois processos através de 
operações de gravação e leitura em um buffer (processos produtor/consumidor).
Processo
gravador
Processo
leitor
dado
Sincronização
leit
ura
gravação
Buffer
Sincronização Condicional
Sistemas Operacionais
Program Produtor_consumidor_1;
CONST Tambuf = ( * Tamanho Qualquer*);
Type Tipo_Dado = ( * Tipo qualquer *);
Var Buffer : ARRAY [ 1..TamBuf] OF Tipo_dado;
Dado_1 : Tipo_dado;
Dado_2 : tipo_daod;
Cont : 0 …. TamBuf;
PROCEDURE Produtor;
BEGIN
REPEAT
Produz_Dado (Dado);
WHILE (Cont = TamBuf) DO (* Nao faz nada *);
Grava_Buffer (Dado, Cont);
UNTIL False;
END;
PROCEDURE Consumidor;
BEGIN
REPEAT
WHILE (Cont = 0) DO (* Nao faz nada *);
Le_Buffer (Dado);
Consome_Dado (Dado, Cont);
UNTIL False;
END;
O recurso compartilhado é um buffer, definido no algoritmo com o tamanho 
TAMBuf e sendo controlado pela variável Cont. 
Sempre que a variável Cont for igual a 0, significa que o buffer está vazio e o 
processo Consumidor deve permanecer aguardando até que se grave um 
dado. 
Da mesma forma, quando a variável Cont for igual a TamBuf, significa que o 
buffer está cheio e o processo Produtor deve aguardar a leitura de um novo 
dado.
Apesar do algoritmo resolver a questão da sincronização condicional, o 
problema da espera ocupada também se faz presente, sendo somente
solucionado pelos mecanismoc de sincronização semáforo e monitores.
BEGIN
Cont := 0;
PARBEGIN
Produto;
Consumidor;
PAREND;
END.
Problema do produtor/consumidor ou do buffer limitado.