Upload
hoangbao
View
219
Download
0
Embed Size (px)
Citation preview
BC1518-Sistemas Operacionais
Sincronização de Sincronização de
Prof. Marcelo Z. do [email protected]
Sincronização de Sincronização de ProcessosProcessos(aula 5 (aula 5 –– Parte 2)Parte 2)
Roteiro
• Semáforos
• Monitores
• Passagem de Mensagem• Passagem de Mensagem
• Exemplos em S.O.
• Problemas clássicos de comunicação entre processos
• Leituras Sugeridas
Semáforos� E.W. Dijkstra (1965) sugeriu usar uma variável do tipo
inteira para contar o número de sinais de acordar salvos para uso futuro.
3
� Um novo tipo de variável denominado Semáforo.
� Um semáforo poderia conter valor 0 – indicando que nenhum sinal de acordar foi salvo – ou valor positivo se um ou mais sinais de acordar estivessem pendentes.
Semáforos� Mecanismo de sincronização que permite implementar a exclusão mútua e sincronização condicional (software)
� Variável inteira, não negativa, manipulada por duas instruções: DOWN e UP ;
4
instruções: DOWN e UP ;
� Garante uma única ação atômica e indivisível.
� Duas primitivas de chamadas de sistema: down (sleep) e up (wakeup) – originalmente: P (teste) - proberen (down) e V (incrementa) - verhogen (up) em holandês.
ProblemaProblema dada exclusãoexclusão mútuamútua
� Inicialmente o semáforo -> o valor 1, indicando que
nenhum processo está executando sua região
Semáforos
5
nenhum processo está executando sua região
crítica.
� Se o Processo_A executar a instrução Down, faz
com que o semáforo seja decrementado de 1 ->
passando a ter o valor 0.
� Em seguida => Processo_A ganha o acesso a regiãocrítica.
� O Processo_B também executará a instrução Down,mas como seu valor é igual a 0, ficará aguardando até
Semáforos
6
mas como seu valor é igual a 0, ficará aguardando atéque o Processo_A execute a instrução Up (volte ovalor => para 1).
� Seja qual for o processo que entre primeiro na regiãocrítica => o problema da exclusão será resolvido.
� Chamado de semáforo binário (mutex) que permite aexclusão mútua;
Down( Var empty: Int )
Begin
While empty<=0 Do; (* não faz nada *)
Semáforos
7
empty:=empty-1;
End;
• Garante que, uma vez iniciada uma operação de semáforo, nenhum outro processo pode ter acesso ao semáforo até que a operação tenha terminado ou sido bloqueada.
• Atomicidade absoluta essencial para resolver o problema de sincronização.
Up( Var empty: Int )
Begin
empty:= empty +1;
Semáforos
8
end;
• Se um ou mais processos estiverem dormindo naquele semáforo, incapacitados de terminar uma operação, um deles seria escolhido pelo sistema e seria dado a permissão de terminar o seu down.
Problema: Gerenciamento de recursos em problema Produtor/consumidor:
� Resolve o problema de perda de sinais enviados;
Úteis quando aplicados em problemas de sincronização
Semáforos
9
� Úteis quando aplicados em problemas de sincronização condicional onde existem processos concorrentes alocando recursos do mesmo tipo.
� Necessidade de três semáforos: controle do número de lugares preenchido e vazio e um mutex para controle de acesso.
Semáfaros contadores:
� Full: conta o número de slots no buffer que estão ocupados; iniciado com 0;
� resolve sincronização;
Semáforos
10
� resolve sincronização;
� Empty: conta o número de slots no buffer que estão vazios; iniciado com o número total de slots no buffer;
� resolve sincronização;
Semáfaros mutex
SemáforosMultex em pthreads
� Há várias funções que podem ser usadas para sincronização dos threads
14
sincronização dos threads
� O mecanismo básico usa uma variável mutex, que pode ser travado ou destravada, para proteger a região crítica;
� Cabe ao programador assegurar que os threads os utilizem corretamente
Mutexes em pthreads
O mutex permite bloquear e desbloquear acesso a região crítica, mas há as variáveis de condição
(Continuação)Mutexes em pthreads
libera o uso do libera o uso do bloqueio mutex eespera sinalização em condc
Problema:Problema:
� Primitiva deve ser encaixada dentro do código de cada processo. Portanto, aqueles que escrevem o código devem lembrar-se de inseri-los. Isso esta sujeito a erros por duas razões:
Semáforos
19
código devem lembrar-se de inseri-los. Isso esta sujeito a erros por duas razões:� As pessoas se esquecem das coisas;
� As pessoas podem ignorar a regras para ganhar uma vantagem em desempenho ou violar a segurança
� Erro de programação pode gerar um deadlock;� Suponha que o código seja trocado no processo produtor;
Semáforos
empty.adquire();mutex.adquire();enter_item(item); mutex.release () ;
full.release();
mutex.adquire();empty.adquire();enter_item(item); mutex.release();full.release();
full.adquire();mutex.adquire();remove_item(item); mutex.release();empty.release();
20
� Se o buffer estiver cheio => o produtor será bloqueado;
� Assim, a próxima vez que o consumidor tentar acessar o buffer, ele tenta executar um release sobre o mutex, ficando também bloqueado.
full.release(); full.release(); empty.release();
Monitores� Primitiva de alto nível;� Semáforos exige bastante cuidado, pois qualquer
engano pode levar a problemas de sincronização imprevisíveis;
21
imprevisíveis;� Idealizado por Hoare (1974) e Brinch Hansen (1975):
� Primitiva de alto nível para sincronizar processos implementadas pelo compilador.
� É um conjunto de procedimentos, variáveis e/ou estruturas de dados agrupados em um único módulo (pacote):� Exclusão mútua.
Monitores� Somente um processo pode estar ativo dentro do
monitor em um mesmo instante;� Outros processos ficam bloqueados até que possam estar
ativos no monitor.
O monitor possui uma fila (FIFO) de entrada:
22
� O monitor possui uma fila (FIFO) de entrada:� processos que desejem executar um procedimento do monitor
deve aguardam sua vez.
� Cabe ao compilador implementara exclusão mútua nas entradas do monitor (mutex ou semáforo binário).� Compiladores tratam de forma diferente das outras chamadas
de procedimento� Alguns compiladores implementam a exclusão mútua por meio
dos monitores – exemplo: Java.
Monitores� Procedimentos para Execução:
� Chamada a uma rotina do monitor;� Instruções iniciais => teste para detectar se um
outro processo está ativo dentro do monitor;
24
outro processo está ativo dentro do monitor;� Se positivo, o processo novo ficará bloqueado até
que o outro processo deixe o monitor;� Caso contrário, o processo novo entra no monitor;
Monitores� Exclusão mútua não é realizada pelo programador =>
cria procedimentos no monitor;
� Comunicação ocorre através de chamadas a seus procedimentos e de seus parâmetros passados;
25
procedimentos e de seus parâmetros passados;
� As regiões críticas devem ser definidas como procedimentos no monitor:
� O compilador se encarregará de garantir a exclusão mútua entre esses procedimentos;
Monitores
Declaração devariáveis globais
Procedimentos
26
Procedimentos
Fila de entrada
Inicializaçãode variáveis
Proc. 1
Proc. 2
Proc. n
Monito
r
Filas de espera
Condição C1
Condição C2
Condição Cn
Monitores – Classe Mainpackage monitorjava;
public class Main {
public static void main(String args[]) {
ObjetoBuffer umBuffer = new ObjetoBuffer();
27
// criacao das threadsProdutor umProdutor = new Produtor( umBuffer );
Consumidor umConsumidor = new Consumidor( umBuffer );
// start threadsumProdutor.start();
umConsumidor.start();}
}
Monitores – Class Objetopublic class ObjetoBuffer {
private int memoria = -1;private boolean acessivel = true; //variavel de condicao de escrita
// metodo de escrita de dados na memoriapublic synchronized void escreveBuffer( int valor) {
•A palavra synchronizedsignifica que o método
28
public synchronized void escreveBuffer( int valor) {while (!acessivel) { // nao e a vez de escrever
try {wait(); //suspende a thread
} catch (InterruptedException e) {e.printStackTrace();
}}
System.err.println(Thread.currentThread().getName() +" produzindo o valor: " + valor);
this.memoria = valor;acessivel = false; // desabilita a memoria para es critanotify (); // libera a thread que esta ESPERANDO devido a um wait( )
}
significa que o método será executado se puder adquirir o monitor do objeto a quem pertence o método.
Monitores – Class Objeto// metodo de leitura de dados na memoria
public synchronized int lerBuffer() {while (acessivel) { // nao eh a vez de ler
try {wait(); //suspende a thread que chamou este metodo
} catch (InterruptedException e) {e.printStackTrace();
}
29
}}
System.err.println(Thread.currentThread().getName() +" consumindo o valor: " + this.memoria);
acessivel = true; // libera buffer para escrita
notify (); // libera uma thread que esta ESPERANDO devido a um wait( )
return this.memoria;}
}
Monitores – Class Produtorpublic class Produtor extends Thread {
private ObjetoBuffer o_Buffer;
public Produtor( ObjetoBuffer dado ) {super( "Produtor" );o_Buffer = dado;
}
30
// Thread do Produtor escrevera 10 vezes em interva los de tempopublic void run(){
for ( int i = 1; i <= 10; i++ ) {try { // dorme por um tempo aleatorio
Thread.sleep( ( int ) ( Math.random() * 3000 ) );}catch( InterruptedException exception ) {
System.err.println( exception.toString() );}// chama metodo do objeto buffer
o_Buffer. escreveBuffer ( i );}System.err.println(getName() + " terminou de produz ir");
}}
Monitores – Class Consumidor
public class Consumidor extends Thread {private ObjetoBuffer um_Buffer;public Consumidor(ObjetoBuffer dado) {
super("Consumidor");um_Buffer = dado;
}//Thread Consumidor lera o buffer 10 vezes em inter valos public void run () {
31
public void run () {int valor, soma = 0;do { // dorme por um intervalo aleatorio
try {Thread.sleep((int) (Math.random() * 3000));
} // Tratamento de excecaocatch (InterruptedException exception) {
System.err.println(exception.toString());}valor = um_Buffer.lerBuffer ();soma += valor;
} while (valor != 10);System.err.println(
getName() + " terminou de consumir. Totalizou: " + soma);}
}
Monitores - Java• Método Wait:
– O thread libera o lock do objeto– O estado da thread é definido como bloqueada– O thread é colocada no conjunto de espera do objeto
32
• Chamada Notify– Apanha um thread qualquer na lista de threads no conjunto
de espera;– Move um thread do conjunto de espera para o conjunto de
entrada– Define o estado da thread de bloqueado para executável
Semáforo - Javafinal class Semaforo {
private int valor; //valor do semaforo;
//quantidade de processos bloqueados por semaforopublic semaforo (int i) {
valor = i ; // construtor}
33
}
synchronized void P() { if ( valor > 0 )
valor--; //se valor > 0, decrementa o valor else {
esperando++; //senão, incrementa o numero threadstry { wait(); } catch (InterruptedException e) { }; //o processo que executou a
operacao P é suspenso esperando--; };
} //fim do metodo P()
Semáforo - Java
synchronized void V() { //ou UP() if (esperando > 0) //se tem processo na fila de espe ra
notify(); //tira processo da fila de espera else valor++; //senao, incrementa o valor do semafor o}
34
} } //fim da classe Semaforo
Semáforo - Javapublic class Produtor extends Thread {
private ObjetoBuffer o_Buffer; private Semaforo s1,s2;
public void run() { for ( int i = 1; i <= 10; i++ ) {
35
for ( int i = 1; i <= 10; i++ ) {try { Thread.sleep( ( int ) ( Math.random() * 3000 ) ); }
// tratamento de excecaocatch( InterruptedException exception ) {
System.err.println( exception.toString() ); } //executa o objeto buffer
s1.P(); o_Buffer.escreveBuffer( i ); s2.V();
} System.err.println(getName() + " terminou de produz ir");
}
Monitores x SemáforosLimitações de semáforos e monitores:
• Ambos são boas soluções somente para CPUs com memória compartilhada => não são uma boa solução
36
memória compartilhada => não são uma boa solução para aplicações em sistemas distribuídos; – Nenhuma das soluções previne troca de informações entre
processo que estão em diferentes máquinas;
• Além disso, monitores dependem de uma linguagem de programação – nem todas as linguagens suportam MonitoresMonitores (JAVA)(JAVA);
Passagem de Mensagem• Ocorre uma troca de mensagens entre processos
rodando em máquinas diferentes;
• Utiliza-se de duas primitivas de chamadas de sistema: send (receptor, mensagem) e receive(transmissor,
37
send (receptor, mensagem) e receive(transmissor, mensagem) .
• O procedimento send envia para um determinado destino uma mensagem, enquanto que o procedimento receive recebe essa mensagem em uma determinada fonte;
Passagem de MensagemImplementada de 2 maneiras:• A comunicação direta entre 2 processos exige que, ao
enviar ou receber uma mensagem, o processo enderece explicitamente o nome do processo receptor ou
38
explicitamente o nome do processo receptor ou transmissor:
• Só permite a troca de mensagem entre dois processos;
• Especificação do nome dos processos envolvidos na troca de mensagens => caso de mudança desse nome o código do programa deve ser alterado e recompilado;
Passagem de Mensagem• A comunicação indireta entre processos utiliza uma
área compartilhada, onde as mensagens podem ser colocadas pelo processo transmissor e retiradas pelo receptor.
40
receptor. Buffer conhecido como mailbox ou port definidos no momento da
criaçãoProcesso A Processo B
Mailboxou Port
Passagem de Mensagem• Problema Produtor/Consumidor: Início – consumidor envia uma
mensagem de vazio• Produtor mais rápido – fica bloqueado para enviar mensagem.• Consumidor mais rápido – todas as mensagens estarão vazias
esperando o produtor as preencha
# define N 100
void producer (void){int item;
void consumer (void){int item, i;message m;
41
int item;message m;
while (TRUE){item = produce_item();
//espera que uma //mensagem vazia chegue
receive(consumer,&m);
build_message(&m,item);send(consumer,&m);
}}
//mensagens vaziasfor(i=0;i<N;i++)
send(producer,&m);
while (TRUE){receive(producer,&m);item = extract_item(&m);send(producer,&m);consume_item(item);
}}
Windows XP
• Mascara interrupções para proteger acesso a recurso global em sistema com único processador;
Exemplos
global em sistema com único processador;
• Usa spinlocks em sistema multiprocessado;
• Provê objetos despachantes (mutex, semáforos e eventos) para threads fora do kernel.
Linux
• O kernel provê o spinlocks e semáforos para lock no kernel (multiprocessado);
Exemplos
kernel (multiprocessado);
• Máquinas com apenas um processador esse mecanismo é substituido pela ativação e desativação da preempção do kernel.
Problemas clássicos de comunicação entre processos
� Há um conjunto de problemas que tem sido amplamente discutidos e analisados a partir de vários método de sincronização.
� Em 1965, Dijkstra formulou e resolveu um problema de sincronização que chamou de problema do jantar dos filósofos
� Com isso, cada nova primitiva de sincronização criada obriga a demostrar até que ponto essa nova primitiva é eficiente
Problemas clássicos de comunicação entre processos
� Problema do Jantar dos Filósofos � Cinco filósofos desejam
comer espaguete; No entanto, para poder 3
4
46
entanto, para poder comer, cada filósofo precisa utilizar dois garfo e não apenas um. Portanto, os filósofos precisam compartilhar o uso do garfo de forma sincronizada.
� Os filósofos comem e pensam;
1
2
34
5
Problemas clássicos de comunicação entre processos
� Problemas que devem ser evitados:� Deadlock – todos os filósofos pegam um
47
filósofos pegam um garfo ao mesmo tempo;
� Starvation – os filosófos podem ficar indefinidamente pegando os garfos simultaneamente;
Problemas clássicos de comunicação entre processos
49
Uma solução para o problema do jantar dos filósofos (parte 1)
Problemas clássicos de comunicação entre processos
50
Uma solução para o problema do jantar dos filósofos (parte 2)
• Primitivas Dormir e Acordar
• Semáforo
Aula 06 - Sumário
• Monitores
• Problemas clássicos de comunicação de processos
Leituras Sugeridas• Silberschatz, A., Galvin, P. B. Gagne,
G. Sistemas Operacionais com Java. 7º edição. Editora Campus, 2008 .
• TANENBAUM, A. Sistemas Operacionais Modernos. Rio de Janeiro: Pearson, 3 ed. 2010