SO_08 - Sincronização Processos

Prévia do material em texto

Sistemas Operacionais
Prof. Fernando Eryck
2012.2
Redes de Computadores
SUMÁRIO
� Sincronização de Processos
Comunicação Interprocessos
�Processos precisam se comunicar com outros processos
� Quando há a necessidade de comunicação entre processos, 
ocorre a comunicação interprocessos (interprocess communication 
– IPC)– IPC)
� Processos concorrentes:
�Acessam informações em comum
�Dados compartilhados
�Na memória principal 
�Em um arquivo de dados, etc.
�Não é possível determinar a ordem em que os eventos vão ocorrer
Comunicação Interprocessos
�Alguma forma de sincronização entre processos é necessária
�Garantir a sequência adequada para a execução dos eventos
� Um processo espera para adquirir o recurso compartilhado (Wait)
�O processo quando termina de usar o recurso compartilhado emite um �O processo quando termina de usar o recurso compartilhado emite um 
sinal (signal)
Sincronização e comunicação entre processos
Comunicação Interprocessos
�Os mecanismos que garantem a comunicação entre processos 
concorrentes e o acesso a recursos compartilhados são chamados de 
mecanismos de sincronização.
�Problemas de Compartilhamento de RecursosProblemas de Compartilhamento de Recursos
� Exemplos: 
Venda de passagem
Spool de Impressão
Dois processos querem ter acesso 
simultaneamente à memória compartilhada
Comunicação Interprocessos
�Problemas de Compartilhamento de Recursos (cont.)
� Exemplos: 
Venda de passagem
Dois processos (sistemas) querem ter acesso 
simultaneamente a um único processo (passagem)compartilhado
Comunicação Interprocessos – Condições de 
Disputa
�Condições de disputa ou de corrida - são situações onde 2 ou mais 
processos estão acessando dados compartilhados, e o resultado final do 
processamento depende de quem é executado primeiro.
�Como evitar as Condições de Disputa?
É preciso de um mecanismo que evite que dois ou mais processos leiam e É preciso de um mecanismo que evite que dois ou mais processos leiam e 
escrevam a mesma variável/arquivo simultaneamente
Comunicação Interprocessos – Regiões Críticas
�Exclusão Mútua - é o modo de evitar que dois ou mais processos 
tenham acesso simultaneamente a alguma região crítica (variável 
ou um arquivo compartilhado) que já estiver em uso por um 
processo
� impede que dois ou mais processos acessem um mesmo recurso 
ao mesmo tempo;
�Enquanto um processo acessar um recurso, os outros processos 
devem esperar até que o primeiro processo termine o acesso.
Comunicação Interprocessos – Regiões Críticas
�Regiões Críticas – Nome dado a parte do código do programa 
onde é feito o acesso ao recurso compartilhado
� Quatro condições necessárias para prover exclusão mútua:
� Nunca dois processos podem estar simultaneamente em uma região 
crítica; 
� Nenhuma afirmação pode ser feita sobre velocidade ou número de 
CPUs;
� Nenhum processo executando fora de sua região crítica pode bloquear 
outros processos;
� Nenhum processo deve esperar eternamente para entrar em sua região 
crítica;
Comunicação Interprocessos – Regiões Críticas
Exclusão mútua usando regiões críticas
Problemas de Sincronização
� Velocidades muito diferentes dos processos:
�Podem causar problema de solução de sincronização entre 
processos.
�Ex: Problema processo produtor / consumidor.
� Starvation (Indefinitely Postponed):
�Um processo nunca consegue executar sua região crítica e 
acessar o recurso compartilhado.
�Outros processos são sempre prioritários.
�Processos são selecionados de forma aleatória 
� Há possibilidade de um processo nunca ser escolhido
�Solução: 
� Criação de filas de pedidos
� Primeiro a entrar é o primeiro a sair (FIFO)
Soluções para Exclusão Mútua com espera ociosa
� Desabilitação das interrupções:
� Cada processo deve inibir as interrupções logo após 
entrar em uma região crítica, habilitando-as 
imediatamente antes de sair dela.imediatamente antes de sair dela.
� Evita Interrupções de relógios
� Problema
�Multiprogramação pode ficar comprometida
� Processos poderia desabilitar as interrupções e 
não habilitá-las posteriormente.
� Ineficiente para sistemas multiprocessados, 
devido ao tempo de propagação de sinalização 
para habilitar ou desabilitar as interrupções
Soluções para Exclusão Mútua com espera ociosa
� Instrução Test-and-Set
� Para coordenar o acesso concorrente a um recurso, 
utiliza-se uma variável lógica global, Lock (Bloqueio).
� Se a variável Bloqueio for falsa, qualquer processo � Se a variável Bloqueio for falsa, qualquer processo 
poderá alterar seu valor para verdadeiro através da 
instrução test-and-set acessando o recurso de forma 
exclusiva
� Lock=0 (processo pode alterar para 1 e entra na região 
crítica)
� Lock=1 (processo está impedido de entrar na região 
crítica)
Soluções para Exclusão Mútua com espera ociosa
� Instrução Test-and-Set (cont.)
� Problema
� Processo P1 lê o valor de lock e ela está igual a 0 e 
a seguir ele é interrompido, antes de alterar seu a seguir ele é interrompido, antes de alterar seu 
valor para 1.
� Processo P2 lê o valor de lock=0 e muda para 1, 
podendo entrar em sua região crítica. P2 é 
interrompido e a execução volta pra P1.
� P1 atribui lock=1 e entra em sua região crítica 
� P1 e P2 estão na mesma região crítica. 
Soluções para Exclusão Mútua com espera ociosa
� Instrução Test-and-Set (cont.)
� Problema (cont.)
� Starvation
Soluções para Exclusão Mútua com espera ociosa
� Alternância obrigatória
� Uma variável, no código abaixo, representada por vez, 
estabelece de quem é a vez de entrar na região crítica.
� Inicialmente vez=0 e o processo P0 inicia a execução e 
entra na região crítica.entra na região crítica.
� O processo P1 tenta entrar na região crítica e verifica que 
vez=0 ficando bloqueado 
� P1 verifica constantemente o valor da variável 
compartilhada aguardando ela passar para 1 (um) para com 
isso ganhar o acesso a região crítica
� Este tempo e processamento gasto por P1 testando 
continuamente o valor da variável vez é chamado de
espera ociosa (busy waiting).
� Espera ociosa deve ser evitada pois gasta tempo de CPU
Soluções para Exclusão Mútua com espera ociosa
� Alternância obrigatória
� Na espera ociosa toda vez que um processo não consegue 
entrar em sua região crítica, por já existir outro processo 
acessando o recurso, o processo permanece em looping, 
até que lhe seja permitido.
� Ao sair da RC o processo 0 altera o valor da variável vez 
para 1 e libera o acesso a RC para o processo 1.
while (TRUE) { 
while (vez != 0) /* espera */ 
regiao_critica (); 
vez = 1; 
regiao_nao_critica (); 
} 
(a) Processo 0 
while (TRUE) { 
while (vez != 1) /* espera */ 
regiao_critica (); 
vez = 0; 
regiao_nao_critica (); 
} 
(b) Processo 1 
Soluções para Exclusão Mútua com espera ociosa
� Alternância obrigatória
� Problema
� Um processo pode ser impedido de entrar na Região 
Crítica mesmo com o outro estando fora da Região 
CríticaCrítica
� Violação da condição 3 = Nenhum processo executando 
fora de sua região crítica pode bloquear outros 
processos
Soluções para Exclusão Mútua com espera ociosa
� Solução de Peterson
� Em 1981, G.L. Peterson, descobriu uma técnica de se obter 
a exclusão mútua sem a obrigatoriedade da alternância.
� Funcionamento:
� Antes de entrar em sua região crítica cada processo � Antes de entrar em sua região crítica cada processo 
deve chamar enter_region, com seu número de 
processo, 0 ou 1, como parâmetro. 
� Imagine que o processo 0 chame a função enter_region 
para manifestar seu interesse em entrar na RC, 
alterando interested[process] =TRUE e coloca a váriável 
turn=0.� Nesse instante o outro processo P1 não está interessado 
em entrar em sua região crítica, portanto, o 
procedimento retorna imediatamente.
Soluções para Exclusão Mútua com espera ociosa
� Solução de Peterson
� Caso P1 chame enter_region ele ficará bloqueado até que 
interested [0]=FALSE. 
� Tal situação acontecerá somente quando P0 chamar a 
função leave_region.função leave_region.
� Problema
� Espera Ocupada
# include “prototypes.h” 
# define FALSE 0 
# define TRUE 1 
# define N 2 
int turn; 
int interested[N]; 
void enter_region (int process) 
{ { 
int other; 
other = 1 – process; 
interested [process] = TRUE; /*MOSTRA 
INTERESSE PELA RC*/ 
turn = process; 
while (turn == process && 
interested[other] == TRUE) 
} 
void leave_region (int process) 
{ 
interested[process] = FALSE; /*SAÍDA 
DA RC*/
Soluções para Exclusão Mútua com espera ociosa
� Bloqueio e Desbloqueio de Processos: SLEEP/WAKEUP
� A solução de Peterson é correta, mas apresenta o defeito 
de precisar da espera ociosa.
� Implementação: quando um processo não pode entrar na 
região crítica ele é posto para executar um loop até que seja região crítica ele é posto para executar um loop até que seja 
permitido entrar na região.
� Algumas primitivas que bloqueiam o processo em vez de 
gastar tempo CPU são conhecidas como: SLEEP/WAKEUP
� SLEEP: é uma chamada ao sistema que bloqueia o 
processo que chamou = suspende a execução do 
processo até que outro processo o desperte
�WAKEUP: utiliza o parâmetro ID do processo a ser 
despertado
Soluções para Exclusão Mútua com espera ociosa
� Problema do Produtor-Consumidor ou do Buffer Limitado
� Exemplo para ilustrar a primitivas SLEEP/WAKEUP
� Nesta situação dois processos compartilham um buffer 
comum e de tamanho fixo. 
� Um deles, o produtor, põe informação dentro do buffer, e o � Um deles, o produtor, põe informação dentro do buffer, e o 
outro, consumidor retira.
� Problema
� Origina quando o produtor quer colocar um novo item 
no buffer, mas ele está cheio. 
� Solução
� Colocar o produtor para dormir e só despertá-lo quando 
o consumidor remover um ou mais itens.
Soluções para Exclusão Mútua com espera ociosa
� Problema do Produtor-Consumidor ou do Buffer Limitado
� Solução(cont.)
� Da mesma maneira, se o consumidor quiser remover 
um item do buffer e perceber que o mesmo está vazio, 
ele dormirá até que o produtor coloque algo no buffer e ele dormirá até que o produtor coloque algo no buffer e 
o desperte.
Soluções para Exclusão Mútua com espera ociosa
# define N 100 
int count = 0; 
void producer(void) 
{ 
int item; 
void consumer(void) 
{ 
int item; 
while (TRUE){ 
if (count == 0) sleep (); int item; 
while (TRUE){ 
item = produce_item( ); 
if (count == N) sleep(); 
insert_item(item); 
count = count + 1; 
if (count == 1) wakeup(consumer); 
/*Buffer estava vazio? Se sim, 
consumidor esta dormindo*/ 
} 
} 
while (TRUE){ 
if (count == 0) sleep (); 
item = remove_item( ); 
count = count - 1; 
if (count == N -1) wakeup (producer); 
/*Buffer estava cheio? Se 
sim, logo produtor esta dormindo*/ 
consume_item (item); 
} 
} 
Soluções de Software para Exclusão Mútua
�Semáforos (Counting Semaphores);
�Semáforos Binários
(Mutual Exclusion Semaphores);
�Mutex;
�Monitores�Monitores
�Deadlocks