cap07

Sistemas Operacionais I

•
UFPA

Agnaldo Marinho
16/04/2014
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sistemas Operacionais
Capítulo 5
Sincronização e Comunicação entre Processos
Sistemas Operacionais 
*
Departamento de Informática/UFPA
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
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Introdução
Com o surgimento dos sistemas multiprogramáveis, passou a ser possível estruturar aplicações de maneira que parte diferentes do código do programa pudessem ser executados concorrentemente.
Esse tipo de aplicação era denominada de aplicação concorrente.
Em um sistema multiprogramável com um único processador, os processo alternam sua execução segundo critério de escalonamentos estabelecidos pelo sistema operacional 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Introdução
É natural que processos de uma aplicação concorrente compartilhem recurso do sistema, arquivos, registros, dispositivos de E/S e áreas de memória.
O compartilhamento de recurso entre processos pode ocasionar situações indesejáveis, capazes até de comprometer a execução da aplacação.
 Para evitar esse tipo de problema os processos concorrentes devem ter suas execuções sincronizadas com objetivo de garantir o processamento correto dos programas.
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Aplicações concorrentes
Muitas vez em uma aplicação concorrente, é necessário comuniquem-se entre si.
Esta comunicação pode ser implementada através de diversos mecanismos, como:
Variáveis compartilhadas na memória principal 
Troca de mensagens 
Nesta situação, é necessário que os processos concorrentes tenham sua execução sincronizada através de mecanismos do sistema operacional.
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Aplicações concorrentes
Exemplo
Dado dois processos que compartilham um buffer para trocar informações através de operações de leitura e gravação.
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Aplicações concorrentes
Os mecanismos que garantem a comunicação entre os processo e o acesso a recurso compartilhados são chamados de mecanismos de sincronização.
Apesar do termo processo ser utilizado na exemplificação de aplicações concorrentes, os termos subprocessos e thread tem o mesmo significado nesta abordagem
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Especificação de concorrência em programas
Existem várias notações utilizadas para especificar a concorrência em programas, ou seja, partes dos programas devem ser executadas concorrentemente 
As técnicas tentam expressar a concorrência no código dos programas de uma forma clara e estruturada. 
A primeira notação para especificação de concorrência em um programa foram os comandos FORK e JOIN, introduzidos por Conway (1963) e Dennis e Van Horn (1966).
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Especificação de concorrência em programas
PROGRAM A;			PROGRAM B;
	.						.
	.						.	
	.						.
	FORK B;
	.						.	
	.						.
	.						.
	JOIN B;
	.						.	
	.						.
	.						.
END.					END.
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Especificação de concorrência em programas
FORK e JOIN são bastante poderosos e práticos, sendo utilizados de forma semelhante em sistemas operacionais UNIX.
Umas das implementações mais claras e simples de expressar concorrência em um programa é a utilização dos comando PARBEGIN e PAREND (Disjkstra, 1965).
O comando PARBEGIN especifica que um seqüência de comando seja executada concorrentemente em uma ordem imprevisível, através da criação de processos (Processo_1, Processo_2, ..., Processo_n) para cada comando (Comando_1, Comando_2, ..., Comando_n). 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Especificação de concorrência em programas
O Comando PAREND define um ponto de sincronização, onde o processamento só continuará quando todos os processos ou thread criados já tiverem terminados suas execuções. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Especificação de concorrência em programas
Exemplo.
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.
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Problemas de Compartilhamento de Recursos 
Para compreensão de como a sincronização de entre processo concorrentes é fundamental para confiabilidade dos sistemas multiprogramáveis . A seguir são apresentados alguns problemas de compartilhamento de recursos.
A primeira situação envolve o compartilhamento de um arquivo em disco.
A segunda apresenta o compartilhamento de uma variável. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Problemas de Compartilhamento de Recursos 
O primeiro problema é analisado a partir da Conta_Corente, que atualiza o saldo bancário de um cliente após o lançamento de débito ou crédito no arquivo de contas correntes Arq_Contas. 
	
	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.
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Problemas de Compartilhamento de Recursos 
Considerando processos concorrentes pertencentes a dois funcionários do banco que atualizem o saldo de um mesmo cliente simultaneamente, a situação de compartilhamento de recurso pode ser compartilhada.
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Problemas de Compartilhamento de Recursos 
No outro exemplo, ainda mais simples, onde o problema de concorrência pode levar a resultados inesperados, é a situação onde dois processo (A e B) executam um comando de atribuição.
O processo A soma 1 a variável X e o processo B subtrai 1 a mesma variável X que está sendo compartilha. Inicialmente a variável X possui valor 2
 Processo A				Processo B
 X := X + 1;				X := X - 1;
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Problemas de Compartilhamento de Recursos 
Seria razoável pensar que o resultado final da variável X após a execução dos Processos A e B, continuasse em 2. 
Porém os comandos de atribuição, em uma linguagem de alto nível, podem ser decompostos comando mais elementares.
		
			Processo A Processo B
			X := X + 1; X := X - 1;
			Processo A Processo B 
			LOAD x,Ra LOAD x,Rb
			ADD 1,Ra SUB 1,Rb
			STORE Ra,x STORE Rb,x
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Problemas de Compartilhamento de Recursos 
Considere que o processo A carregue o valor de X no registrador Ra, some 1 e, no momento em que vai armazenar
o valor X, seja e interrompido. Neste momento o processo B inicia a sua execução e também é interrompido no momento em que vai armazenar o valor de X. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Problemas de Compartilhamento de Recursos 
Analisando os dois exemplos é possível concluir que em qualquer situação, onde os dois ou mais processos compartilham o mesmo recurso, deve existir mecanismo de controle para evitar esse tipo de problemas, conhecidos como race conditions. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Uma solução simples para evitar os problemas de compartilhamento apresentado no item anterior é impedir que dois ou mais processos acessem um mesmo recurso simultaneamente.
Para isso, enquanto um processo estiver acessando determinado recurso, todos os demais processos que queiram acessá-lo deverão esperar pelo termino da utilização do recurso.
Essa idéia de exclusividade de acesso é chamada de exclusão mútua (mutual exclusion). 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
A exclusão mútua deve afetar apenas os processo concorrentes somente quando um deles utilizando acesso ao recurso compartilhado.
A parte do código do programa onde é feito o acesso ao recurso compartilhado é denominada de região crítica (critical region).
Se for garantido que a execução mutuamente exclusiva das regiões críticas, os problemas decorrentes do compartilhamento serão evitados.
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Os mecanismos que implementam a exclusão mútua utilizam protocolos de acesso à região crítica.
Os protocolos de acesso a região crítica tem como funcionalidade avisar aos demais processos que queriam ter acesso a um recurso compartilhado, que um determinado processo está entrando na sua região crítica e que o processo está saindo da sua região crítica.
			BEGIN
 			.
 			Entra_Regiao_Critica; (protocolo de entrada;)
 			Regiao_Critica;
 			Sai_Regiao_Critica; (protocolo de saida)
 			.
 		END. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Como é possível, então, observar, para garantir a implementação da exclusão mútua os processos envolvidos devem fazer acesso aos recurso de forma sincronizada.
Diversas soluções foram desenvolvidas com esse propósito; porém , além de garantia da exclusão mútua, duas situações indesejáveis também devem ser evitadas.
A primeira situação indesejada é conhecida como starvation ou espera indefinida. Starvation é uma situação em que um processo nunca consegue executar sua região crítica e, consequentimente o recurso compartilhado. 
No momento em que o recurso é liberado o SO possui um critério para selecionar dentre os que esperam o recurso qual será escolhido. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
A outra situação indesejada na implementação de exclusão mútua é aquela em que um processo fora da região crítica impede que outros processo entrem nas suas próprios regiões críticas .
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via hardware
Desabilitação de interrupção 
A solução mais simples para o problema da exclusão mútua é fazer com que o processo desabilite todas a interrupções antes de entrar na sua região crítica, e as habilite após deixar a região. 
		BEGIN 
			.
			Desabilita_Interrupção
			Região_Critica
			Habilita_Interrupção 
			.
		END
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via hardware
Desabilitação de interrupção 
Nesta solução apesar de simples apresenta algumas limitações:
A multiprogramação pode ficar seriamente comprometida. Já que concorrência entre processo tem como base a interrupção.
Um caso mais grave seria se caso um processo desabilitasse as interrupções e não tornasse a habilitá-las.
Em sistemas com múltiplos processadores, essa solução se tornaria ineficiente devido ao tempo de propagação da sinalização a outros processadores 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via hardware
Instrução Test-and-Set
Muitos processadores possuem uma instrução de maquina especial que permite ler uma variável, armazenar seu conteúdo em uma outra área e atribuir um novo valor à mesma variável.
Essa instrução especial é chamada de Test-and-Set e tem como característica ser executada sem interrupção, ou seja, trata-se de uma instução indivisível.
 Desta forma, é garantido que dois processos não manipulem uma variável compartilhada. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via hardware
Instrução Test-and-Set
A instrução test-end-set possui o seguinte formato, quando executada o valor lógico da variável Y é copiado para X, sendo atribuído à variável Y o valor lógico verdadeiro.
Para coordenar o acesso concorrente a um recurso, a instrução test-and-set utiliza uma variável global chamada Bloqueio. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
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 False;
END;
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 False;
END;
BEGIN
Bloqueio := False;
PARBEGIN
	Processo_A;
	Processo_B;
PAREND;
END;
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via hardware
Instrução Test-and-Set
O uso de uma instrução especial de máquina oferece algumas vantagens.
Simplicidade de implementação da exclusão mútua 
Possibilidade de exclusão mútua em múltiplas regiões críticas.
E o uso de arquiteturas com múltiplos processadores 
A principal desvantagem é a possibilidade de starvation 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via Software
Diversas algoritmos foram propostos na tentativa de implementar a exclusão mutua através de soluções de software.
As primeiras soluções tratavam apenas da exclusão mútua entre dois processos e, inicialmente, apresentavam alguns problemas.
A partir de agora vamos é apresentado de forma evolutiva como foi o desenvolvimento de uma solução definitiva para a exclusão mútua entre N processo 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via Software
Primeiro Algoritmo
Este algoritmo apresenta uma para solução de exclusão mútua entre dois processos onde um mecanismo de controle alterna a execução da região crítica.
Cada processo é representado (A e B) é representado por um procedimento que possui um loop infinito onde é feito o acesso a um recurso por diversas vezes.
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
PROGRAM Algoritmo_1;
	VAR Vez : CHAR;
PROCEDURE Processo_A;
BEGIN
	REPEAT
		WHILE (Vez = ‘B’) DO (* Não faz nada *)
		Regiao_Critica_A;
		Vez := ‘A’;
		Processamento_A;
	UNTIL False;
END;
PROCEDURE Processo_B;
BEGIN
	REPEAT
		WHILE (Vez = ‘A’) DO (* Não faz nada *)
		Regiao_Critica_B;
		Vez := ‘A’;
		Processamento_B;
	UNTIL False;
END;
BEGIN
	Vez := ‘A’;
	PARBEGIN
		Processo_A;
		Processo_B;
	PAREND
END;
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via Software
Primeiro Algoritmo
Este algoritmo, apesar de implementar a exclusão mútua, apresenta duas limitações.
A primeira surge do próprio mecanismo de controle utilizado, o acesso ao recurso compartilhado só pode ser feito por dois processos e sempre de maneira alternada, por isso o processo que necessite utilizar o recurso mais vezes ficará boa parte do tempo Bloqueado.
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via Software
Primeiro Algoritmo
Este algoritmo, apesar de implementar a exclusão mútua, apresenta duas limitações.
Outro problema existente nesta solução é que, 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 processo permanecerá indefinidamente bloqueado. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via Software
Segundo Algoritmo
O problema principal do primeiro algoritmo é que ambos os processos trabalham com a mesma variável global , cujo o conteúdo indica qual variável tem direito de entra na região crítica. 
Para evitar essa situação o segundo algoritmo introduz uma variável para cada processo (CA e CB) que indica se o processo está ou não em sua região crítica 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
PROGRAM Algortimo_2;
	VAR CA, CB : BOOLEAN;
PROCEDURE Processo_A;
BEGIN
	REPEAT
		WHILE (CB) DO (*Não faça nada*);
		CA := True;
		Regiao_Critica_A;
		CA := False;
		Processamento_A;
	UNTIL False;
END;
PROCEDURE Processo_B;
BEGIN
	REPEAT
		WHILE (CA) DO (*Não faça nada*);
		CB := True;
		Regiao_Critica_B;
		CB := False;
		Processamento_B;
	UNTIL False;
END;
BEGIN
	CA := false;
	CB := false;
	PARBEGIN
		Processo_A;
		Processo_B;
	PAREND
END;
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via Software
Segundo Algoritmo
Neste segundo algoritmo, o uso do recurso não é realizado necessariamente alternado. Caso ocorra algum problema com um dos processo fora da região_critica, o outro processo não ficará bloqueado. Porem não resolve por completo o problema.
Caso um processo tenha um problema na sua região critica ou antes de alterara variável, o outro processo ficará indefinidamente esperando. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via Software
Segundo Algoritmo
Mais grave que o problema do bloqueio é que essa solução é pior que o primeiro algoritmo pois nem sempre a exclusão mútua é garantida . 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via Software
Terceiro algoritmo
Tenta solucionar o problema apresentado no segundo algoritmos, colocando a instrução das variáveis CA e CB antes do loop de teste
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
PROGRAM Algortimo_3;
	VAR CA, CB : BOOLEAN;
PROCEDURE Processo_A;
BEGIN
	REPEAT
		CA := True;
		WHILE (CB) DO (*Não faça nada*);
		Regiao_Critica_A;
		CA := False;
		Processamento_A;
	UNTIL False;
END;
PROCEDURE Processo_B;
BEGIN
	REPEAT
		CB := True;
		WHILE (CA) DO (*Não faça nada*);
		Regiao_Critica_B;
		CB := False;
		Processamento_B;
	UNTIL False;
END;
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via Software
Terceiro algoritmo
Está alteração resulta na garantia na exclusão mútua, porém introduz um novo problema, que é a possibilidade do bloqueio indefinido de ambos os processos. Caso os dois processo alterem suas variáveis CA e CB antes da execução da instrução WHILE, ambos os processo não poderão entrar em sua região crítica. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via Software
Quarto Algoritmo 
No terceiro algoritmo cada processo altera o estado da sua variável indicando que irá entrar na sua região crítica sem conhecer o estado do outro processo.
No quarto o algoritmo apresenta uma implementação onde o processo, da mesma forma altera o estado da variável entes de entrar na sua região crítica, porem existe a possibilidade de esta alteração ser revertida. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
PROGRAM Algortimo_3;
	VAR CA, CB : BOOLEAN;
PROCEDURE Processo_A;
BEGIN
	REPEAT
		CA := True;
		WHILE (CB) DO (*Não faça nada*);
		BEGIN
		 CA := false;
		 {Pequeno intervalo aleatorio }
		 CA := true;
		END;
		Regiao_Critica_A;
		CA := False;
		Processamento_A;
	UNTIL False;
END;
PROCEDURE Processo_B;
BEGIN
	REPEAT
		CB := True;
		WHILE (CA) DO (*Não faça nada*);
		BEGIN
		 CB := false;
		 {Pequeno intervalo aleatorio }
		 CB := true;
		END;
		Regiao_Critica_B;
		CB := False;
		Processamento_B;
	UNTIL False;
END;
BEGIN
	CA := False;
	CB := False;
	PARBEGIN
		Processo_A;
		Processo_B;
	PAREND;
END;
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via Software
Quarto Algoritmo 
Apesar de garantir a exclusão mútua e não gerar o bloqueio simultâneo dos processos, uma nova situação indesejada pode ocorrer, no caso dos tempos aleatórios serem proximos e a concorrencia gerar uma situação onde os dois processos alterem as variaveis CA e CB para false antes do termino do loop.
Mesmo que essa situação não seja permanente, pode gerar algum problema.
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Exclusão Mútua
Soluções via Software
Algoritmo de Peterson
O algoritmo proposto por G. L. Peterson apresenta uma solução para o problema da exclusão mútua entre dois processos.
Essa solução pode tambem ser facilmente generalizada para os caso de N processos.
Essa solução é um híbrido do terceiro algoritmo com o primeiro algoritmo. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
PROGRAM Algortimo_Peterson;
	VAR CA, CB : BOOLEAN;
	Vez : CHAR;
PROCEDURE Processo_A;
BEGIN
	REPEAT
		CA := True;
		Vez := ‘B’;
		WHILE (CB and Vez := ‘B’) DO (*Não faça nada*);
		Regiao_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 faça nada*);
		Regiao_Critica_B;
		CB := False;
		Processamento_B;
	UNTIL False;
END;
BEGIN
	CA := False;
	CB := False;
	PARBEGIN
		Processo_A;
		Processo_B;
	PAREND;
END;
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Sincronização Condicional
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 processo através de operações de gravação e leitura em um buffer.
Neste caso os processo que geram as informações são chamados de 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Sincronização Condicional
Neste caso os processo que geram as informações são chamados de processos produtores 
E os processos que utilizam essas informações são chamados de processos consumidores.
Nesta comunicação, enquanto um processo grava os dados em um buffer, o outro lê os dados concorrentemente
O problema de sincronização condicional, também é conhecido como problema do produtor/consumidor. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Semáforos
O conceito de semáforos foi proposto por Dijkstra em 1965, sendo apresentado como um mecanismo de sincronização que permitia implementar de forma simples a exclusão mútua e sincronização condicional entre processo.
O uso dos semáforos tornou-se um dos principais mecanismo utilizados em projetos de sistemas operacionais e em aplicações concorrente
Atualmente, a maioria das linguagem de programação disponibiliza rotinas para uso de semáforos.
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Semáforos
Um semáforo é uma variável inteira, não negativa que só pode ser manipulada por duas instruções DOWN e UP, também chamadas de instruções P (proberem, teste em holandês) e V (verhogen, incremento em holandês)
A instrução UP incrementa uma unidade ao valor do semáforo e a instrução DOWN decrementa a variável .
Os Semáforos podem ser classificados como Binários ou contadores
Os semáforos binários, também chamados de mutexes (mutual exclusion semaphores) só podem assumir valores 0 e 1.
Os semáforos contadores podem assumir qualquer valor inteiro positivo, além do 0. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Semáforos
Exclusão Mútua Utilizando Semáforos 
A exclusão mútua poder ser implementada através de um semáforo binário associado ao recurso compartilhado.
A principal vantagem dessa solução em relação aos algoritmos anteriores apresentados é a não ocorrência de espera ocupada.
As instruções DOWN e UP funcionam como protocolos de entrada e saída a região crítica.
O semáforo fica associado a um recurso compartilhado , indicando quando o recurso está sendo acessado por um dos processos concorrentes 
O valor do semáforo igual a 1 indica que nenhum processo está utilizando o recurso, caso contrário está ocupado. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Semáforos
Exclusão Mútua Utilizando Semáforos 
Sincronização e Comunicação entre Processos
DOWN(S=1)
DOWN(S=0)
Processo Deseja entrar na região crítica
Fila de espera de processos
Processo acessa a região critítica
UP (S) – Processo Sai da região crítica
Libera processo da fila de espera 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Semáforos
Sincronização Condicional usando Semáforos
Além de permitirem a implementação da exclusão mútua, os semáforos podem ser utilizados nos casos onde a ocorre sincronização condicional é exigida.
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 seja completada a operação 
Quando a operação termina executa-se um UP no semáforo, liberando o processo do estado de espera
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Trabalho de implementação usando semáforos
Solucionar dois dos Três problemas utilizando Semáforos usando a linguagem Java.
Problema do Produtor/Consumidor
Problema dos Filósofos na mesa de jantar 
Problema do barbeiro dorminhoco
Trabalho em equipe de 4 membros 
Valor do trabalho de 3 pontos 
Deveres(o atraso em um dos itens resultará na no decréscimo de 0,25pts por dia de atraso )
Apresentar o trabalho 1,0pt
Entregar o relatório 1,0pt
Entregar o código fonte 1,0pt 
 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Trabalho de implementação usando semáforos
Problema do produtor/consumidor
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Trabalho de implementação usando semáforos
Problema dos filósofos na mesa de jantar 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Trabalho de implementação usando semáforos
Problema dos Barbeiro Dorminhoco
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Monitores
Monitores são mecanismos de sincronização de alto nível que tornam mais simples o desenvolvimento de aplicações concorrentes.
O conceito de monitores foi proposto por Brinch Hansen em 1972, e desenvolvido por C.A.R. Hoare em 1974.
O uso de semáforos exige do desenvolvedor bastante cuidado, pois qualquer engano pode levar a problemas de sincronização imprevisíveis.
O monitor é formado por procedimentos e variáveis encapsulados dentro de uma módulo. Sua característica mais importante é a sua implementação automática da exclusão mútua e entre os procedimentos declarados 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Monitores
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Monitores
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Troca de Mensagens
Troca de mensagens é um mecanismo de comunicação e sincronização entre processos.
O sistema operacional possui um subsistema de mensagem que suporta esse mecanismo sem que haja necessidade de uso variáveis compartilhadas. 
Para que haja a comunicação entre os processos, deve existir um canal de comunicação,podendo esse meio ser um buffer ou um link de uma rede de computador.
Os processos cooperativos podem fazer uso de um buffer para trocas de mensagens através de duas rotinas: SEND(receptor, mensagem) e RECEIVE(transmissor, mensagem).
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Troca de Mensagens
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Troca de Mensagens
A rotina SEND permite o envio de mensagem para um processo receptor, enquanto a rotina RECEIVE possibilita o recebimento de mensagem enviada por um processo transmissor 
A troca de mensagem entre processos pode ser implementada de duas maneiras: 
Comunicação direta (Síncrona) 
Comunicação indireta (Assíncrona).
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Troca de Mensagens
Comunicação direta (Síncrona)
Neste tipo de comunicação ambos os processo devem esta ativos para haver a comunicação entre os processos. 
Sistemas Operacionais 
*
Departamento de Informática/UFPA
Sincronização e Comunicação entre Processos
Troca de Mensagens
Comunicação indireta (Assíncrona)
 Neste caso existe uma área compartilhada onde as mensagem podem ser colocadas pelo processo transmissor e retiradas pelo receptor sem a necessidade de ambos os processos estarem ativos 
UP(S) incrementa S ou seja, S = S + 1 e retira processo da fila 
DOWN (S) verifica o valor do semáforo S verifique se S=0 se afirmativo coloca o processo na fila de espera caso contrario decrementa S de uma
unidade 
*
*
*
*
*
*
*
*
*
*
*
*
*