1

Sincronização e Comunicação entre Processos

Sistemas Operacionais Abertos

Comunicação entre Processos

� Processos Independentes.– Não afetam nem são afetados por outros

processos.

� Processos Cooperados.– Compartilham:

• Memória;• Arquivos;• Dispositivos de E/S;• Etc.

Múltiplos Processos

� A filosofia atual dos SOs está focada na gerência de múltiplos processos:

– Multiprogramação;

– Multiprocessamento;

– Processamento Distribuído.

� A questão é: como controlar a Concorrência?

– Gerenciando a interação de todos os processos

Processos Cooperados

� Compartilhamento de dados.– Processo “produtor” de dados.

– Processo “consumidor” de dados,

� Buffer:– Limitado: Produtor e Consumidor.

– Ilimitado: Somente Consumidor.

� Implementação.– Via memória compartilhada;

– Via IPC (Interprocess Comunication - SO)

Buffer Circular

� Implementação como um buffer circular.

� Introdução de um contador de quantidade.

� Produtor e Consumidor manipulam o contador.

4

5

67

8

próximasaídapróxima

entrada

Contador

5

Condições de Corrida

� Mecanismo de Sincronização.– Garante o compartilhamento de recursos e a

comunicação entre os processos;

– Garante a integridade e a confiabilidade dos dados compartilhados.

� Condições de Corrida (ou race conditions):– Situações onde dois ou mais processos estão

acessando dados compartilhados;

– O resultado final pode variar de acordo com a ordem de execução.

2

Race Conditions

� Condições de Corrida (ou race conditions) ocorrem quando:

– Diversos processos ou threads estão efetuando a leitura e/ou a escrita de dados;

– Esse I/O ocorre de forma que o resultado final depende da ordem de execução dos processos.

� A saída irá depender de quem terminar a corrida em último.

Condições de Corrida

� Exemplo 1:

– Resultado Final: Contador = 6 (ERRO!)

7Processo

A7+1

ProcessoB

7-1

1

72

7

5

8

3 4

6

6

Condições de Corrida

� Exemplo 2:

– Valor armazenado peloprocesso B é perdido.

65

4

3

próximaentrada

7

ProcessoA

ProcessoB

1

7

suspensorecebe CPU

2

8

recebe CPUsuspenso

3

7

4

75

8

6

X

10

Y 9

8

Condições de Corrida

� Região Crítica:

– Parte do código fonte onde é feito acesso a recursos compartilhados, e que podem levar a condições de corrida.

� Ex: Processo A.

– Código normal• Início da Seção Crítica (Protocolo de Entrada)• Seção Crítica• Término da Seção Crítica (Protocolo de Saída)

– Código normal

Seção Crítica

…buffer[top]=‘x’;top++;...

Thread A

abuffer

Thread B

3top

b c ? ?

…buffer[top]=‘y’;top++;…

b1b2

a1a2

• Num programa multithreaded, algumas regiões que acessam recursos

compartilhados não podem ser executadas ao mesmo tempo;

• Por exemplo, se a thread A estiver executando a1, o SO não poderá iniciar

a execução de b1,b2 até que a1,a2 sejam completados;

• Denomina-se tal região de seção critica .

Seção Critica:a1-a2 e b1-b2

Concorrência em programas

� Enquanto um processo estiver usando um recurso, os outros devem aguardar até que o recurso esteja liberado.

� Exclusão Mútua.

– Exclusividade no acesso a um determinado recurso.

� A exclusão mútua deve afetar os processos concorrentes, quando um deles estiver em uma região crítica.

3

Exclusão Mutua

…buffer[top]=‘x’;top++;...

Thread A

abuffer

Thread B

3top

b c ? ?

…buffer[top]=‘y’;top++;…

b1b2

a1a2

• Os código sendo executados nas seções criticas devem manter a

exclusão mútua – “Somente uma thread/processo pode estar na seção

critica”.

• Ou seja, se uma thread estiver dentro de sua seção crítica, então as

demais threads não devem entrar nas suas respectivas seções críticas.

�

A Thread B não pode entrar na sua seção crítica, enquanto que a thread A estiver dentro da sua seção crítica.

Delimitando uma Seção Critica

...EntraSC();buffer[top]=‘x’;top++;AbandonaSC();

Thread A

abuffer

Thread B

3top

b c ? ?

...EntraSC();buffer[top]=‘y’;top++;AbandonaSC();…

• O programador delimita as seções críticas do programa por meio de algumas

instruções inseridas estrategicamente no código fonte;

• Denominaremos este código genericamente como EntraSC() e AbandonaSC().

• Este código deve assegurar que no máximo um processo/thread pode estar

rodando dentro da sua seção crítica.

Serão vistas diferentes

formas de se implementar

EntraSC e AbandonaSC.

Aguardando a Seção Critica

...EntraSC();buffer[top]=‘x’;top++;AbandonaSC();

Thread A

abuffer

Thread B

3top

b c ? ?

...EntraSC();buffer[top]=‘y’;top++;AbandonaSC();…

�

�

O que a thread 2 pode fazer se ela precisar entrar na seção crítica

enquanto a thread 1 estiver na sua seção crítica?

� Busy waiting ou espera ativa;

� Bloquear

• Este é similar aos diferentes métodos de I/O.

• O SO pode utilizar busywaiting para aguardar a finalização do I/O, ou pode bloquear o processo/thread até que o I/O seja finalizado.

Zonas Críticas

• N processos competem para acessar variáveis compartilhadas;

• cada processo tem uma parte do código, zona crítica, na qual acessa a memória compartilhada;

• Problema: assegurar que quando um processo está executando a sua zona crítica, nenhum outro processo pode executar esta mesma zona crítica;

• Se permitirmos apenas um processo de cada vez na zona crítica, evita-se competição entre processos.

Região Crítica Como evitar competição entre processos em zonas críticas?

1. Exclusão Mútua: nas zonas críticas não poderão estar nunca 2 processos em simultâneo (atomicidade).

2. Nenhum processo deverá ter de esperar eternamente para entrar na sua zona crítica (devemos evitar “starvation”).

3. Nenhum processo que esteja fora da sua zona crítica, poderá bloquear outros processos (devemos evitar “deadlocks”).

4. Não se pode presumir nada sobre a velocidade ou número de CPUs.

4

Deadlock

Situação onde nenhum dos processos pode prosseguir, pois está aguardando alguma condição que somente pode ser atingida pela execução do outro.

Deadlock

Problemas de Sincronização

� Velocidades muito diferentes dos processos:

– Podem causar problema de solução de sincronização entre processos.

– Ex: Problema produtor / consumidor.

� Starvation ou inanição:

– Um processo nunca consegue executar sua região crítica, e acessar o recurso compartilhado.

• Outros processos são sempre prioritários.

Soluções por Hardware� Desabilitar as interrupções:

desligar_interrupçõeszona crítica

ligar_interrupções

– Solução mais simples para a exclusão mútua;– Falha de Proteção:

• O processo precisa voltar a habilitar as interrupções

– com as interrupções desligadas, a CPU não poderá ser comutada para outro processo.

– método útil a nível do kernel, o scheduler o utiliza, mas não é apropriado como mecanismo geral para garantir exclusão mútua entre processos.

– se um processo pudesse desligar interrupções, poderia acontecer o travamento do SO. Por que?

Soluções por Hardware

� Instrução Test-and-Set.

– Utilização de uma variável para testar a possibilidade de executar a região crítica.

– O processo impedido de executar sua região crítica executa um loop de espera.

• Gasto de CPU.

Variáveis de Comporta ou Travamento

� Utiliza uma variável auxiliar, denominada variável de comporta (“lock variable”), que:– Quando =0 indica que a região crítica está livre,– Quando =1 indica que a mesma está ocupada.

� Cada processo, antes de entrar, teste o valor da comporta: se for 0 (aberta), coloca em 1 e prossegue o processamento, colocando em 0 quando terminar, e se for 1 (fechada) aguarda até se tornar 0.

� Problema � a disputa apenas se transferiu da região crítica para a variável de comporta.

5

Alternância Estrita

� Esta é uma solução a qual obriga que a região crítica seja dada a um dos processos por vez, em uma estrita alternância;

� Para isso usa uma variável, que indica de qual processo é a vez de entrar na região crítica;

� O teste contínuo desta variável na espera de um certo valor é chamado de espera ocupada�desperdício de CPU;

� Problema: requer que os dois processos se alternem precisamente, o que significa que o número de acessos de cada processo deve ser exatamente igual ao do outro.

Soluções por Software

� Estrita Alternância.

– Pode levar à condição de Starvation ou inanição!

� Em geral, as soluções por software resolvem a exclusão mútua, mas geram a espera ocupada (ou Busy Wait):

– Teste contínuo de uma variável até que ocorra uma mudança no seu valor;

– O processo impedido de executar sua região crítica executa um loop de espera.

• Gasto de CPU.

Soluções por Software

� Implementações de uso das regiões críticas sem

a espera ocupada:

– Semáforos Contadores (Counting Semaphores);

– Semáforos Binários

(Mutual Exclusion Semaphores);

– Mutex;

– Monitores.

Semáforos

� Ferramenta de sincronização criada por Dijkstra(1965);

� Características:– Variável inteira;– Não negativa.

� Manipulados por duas operações atômicas :– DOWN ou Wait (P - Proberen - Testar)– UP ou Signal (V - Verhogen - Incrementar)

� Implementados como funções proporcionadas pelo SO.

Semáforos

� Semáforos (Counting Semaphores);

– Sincronização entre processos.

– Full / Empty.

� Associado a um recurso compartilhado.

– Indica quando o recurso já está alocado a

algum processo.

Semáforos

� Um semáforo fica associado a um recurso compartilhado, indicando se ele está sendo usado;

� Se o valor do semáforo é maior do que zero, então existe recurso compartilhado disponível;

� Se o valor do semáforo é zero, então o recurso está sendo usado.

Down(S)

if (S == 0)

bloqueia processo

else

S = S - 1;

Up(S)

if (tem processo na fila)

libera processo

else

S = S + 1;

6

Semáforos

� Semáforos Binários(Mutual Exclusion Semaphores);

– Controle da exclusão mútua.

• Down / Wait: Antes da região crítica.

• Up / Signal : Após a região crítica.

– Chamados MUTEX ou BINÁRIOS, por só assumirem valores 0 e 1.

Mutex

� Estrutura de sincronização bastante simples que pode estar em dois estados:– Locked ou bloqueado;

– Unlocked ou desbloqueado.

� Duas operações sãodefinidas sobre um mutex:– Lock;

– Unlock.

lock

Processo 1

Processo 2Mutex

unlock

lock

unlock

Um Alocador de Recursos

� Semáforos contadores (S > 1) podem ser usados para implementar um controlador para um recurso formado por N unidades;

� O controlador é formado por dois procedimentos, request e release. Para request, o argumento U é de saída e para release o argumento U é de entrada;

� A variável T é o contador de unidades disponíveis e indica a posição do array R que contém a próxima unidade a ser alocada;

� O semáforo counter tranca as requisições quando T=0. Mutex garante acesso exclusivo à T e à R.

R: array[5] of integer; /* Supõe-se R iniciado com [ 5,4,3,2,1] */T: integer initial 5; /* Sintaxe: linguagem V4 */counter: semaphore initial 5;mutex: semaphore initial 1;

procedure request(U:integer) { P(counter)P(mutex)U := R[T];T := T - 1;

V(mutex)};

procedure release(U:integer){ P(mutex)

T := T + 1;R[T] := U;

V(mutex);V(counter)

};

P(S):SE S > 0 ENTÂO S := S – 1SENÂO bloqueia processo

V(S):SE algum processo dorme na fila de

SENTÂO acorda processo SENÂO S := S + 1

Deficiência dos Semáforos (1)

� Exemplo: suponha que os dois down do código do produtor estivessem invertidos. � Neste caso, mutex seria diminuído antes de empty. � Se o buffer estivesse completamente cheio, o

produtor bloquearia com mutex = 0. � Portanto, da próxima vez que o consumidor tentasse

acessar o buffer ele faria um down em mutex, agora zero, e também bloquearia.

� Os dois processos ficariam bloqueados eternamente.

� Conclusão: erros de programação com semáforos podem levar a resultados imprevisíveis.

Deficiência dos Semáforos (2)

� Embora semáforos forneçam uma abstração flexível o bastante para tratar diferentes tipos de problemas de sincronização, ele é inadequado em algumas situações;

� Semáforos são uma abstração de alto nível baseada em primitivas de baixo nível, que proveem atomicidade e mecanismo de bloqueio, com manipulação de filas de espera e de escalonamento; � Tudo isso contribui para que a operação seja lenta.

� Para alguns recursos, isso pode ser tolerado; para outros esse tempo mais longo é inaceitável.� Ex: (Unix) Se o bloco desejado é achado no buffer cache, getblk()

tenta reservá-lo com P(). Se o buffer já estiver reservado, não há nenhuma garantia que ele conterá o mesmo bloco que ele tinha originalmente.

7

Exclusão mútua - resumo

• Utiliza-se um mutex:• semáforo binário (0 ou 1).

• O travamento usando o mutex deve ser feito antes do uso o recurso;• Destravamento é realizado após esse uso;

• Enquanto o recurso estiver em uso, qualquer outro processo que o utilize deve esperar a sua liberação.

• Pode causar a espera infinita por recursos, isto é, deadlock.

Monitores

� Mecanismo de sincronização de alto nível proposto por Hoare (1974) e Brinch Hansen(1975);

� Conjunto de procedimentos, variáveis e estruturas de dados agrupados em um módulo especial;

� Característica mais importante é a implementação automática da exclusão mútua:

– Somente um processo pode estar ativo em um monitor em um determinado instante de tempo.

Monitores

� A implementação da exclusão múltipla passa a ser de responsabilidade do compilador;

� Utilização de variáveis de condição associadas a uma fila de processos;

� Um processo em uma fila (bloqueado) só poderá prosseguir quando outro processo executar um SIGNAL sobre a respectiva variável de condição.

Monitores

� A comunicação do processo com o monitor é feita unicamente através de chamadas a seus procedimentos e dos parâmetros passados para eles;

� Podem ser chamadas duas operações:

– Wait (variável)

– Signal (variável)

Monitores

� Exemplo de implementação de um Monitor:

Inicialização

Procedimento A• Teste de Unicidade

• Corpo do procedimento

• Signal (A)

Procedimento B• Teste de unicidade

• Corpo do procedimento

• Signal (B)

Etc...

FIM

Troca de Mensagens

� Mecanismo de comunicação e sincronização entre processos.

� É implementada pelo Sistema Operacional através das rotinas SEND e RECEIVE.

� SEND é responsável pelo envio de mensagem para o processo receptor:– SEND (Receptor, Mensagem).

� RECEIVE é responsável pelo recebimento da mensagem de um processo transmissor:– RECEIVE (Transmissor, Mensagem).

8

Troca de Mensagens

� Para garantir que uma mensagem não se perca, o receptor deve enviar uma mensagem de recebimento.

� Duas formas de endereçamento:

– Direto• Apenas dois processos trocam mensagens.

– Indireto• Mailbox.

Endereçamento Indireto

� Duas formas de comunicação entre os processos:

– Comunicação Síncrona .• Comunicação 1 a 1 (limitada ao tempo de

processamento da mensagem).

– Comunicação Assíncrona .• Necessidade de buffer para as mensagens.• Necessidade de mecanismos de sincronização.• Maior paralelismo na execução dos processos.

Exercícios de fixação

� Responda: Verdadeiro ou Falso:

Um sistema operacional pode prover

mecanismos para comunicações entre

processos por trocas de mensagens ou por

memórias compartilhadas.

Ambos exigem que as aplicações se

sincronizem via semáforos.

O algoritmo de controle de concorrência mais comum em SO é conhecido por:

a) time stamps;

b) deadlock;

c) Escalonamento round-robin;

d) semáforos;

e) starvation.

Em sistemas operacionais, um processo pode conter um conjunto de linhas de execução, que compartilham o seu espaço de execução.

Dentre as alternativas abaixo, assinale aquela que identifica o mecanismo usado pelo sistema operacional para impedir a interferência entre as linhas de execução sobre os dados que elas compartilham.

A) Execução multi-linha.

B) Despachante.

C) Semáforo.

D) Tabela de processo.

E) Linha em nível de usuário.

9

Um processo pode ser definido como:

a) a memória disponível para execução de um programa.

b) a memória utilizada durante a execução de um programa.

c) a memória compartilhada entre dois ou mais programas.

d) um programa em execução.

e) as chamadas ao sistema.

Starvation ocorre quando:

a) Pelo menos um processo é continuamente postergado e não executa.

b) A prioridade de um processo é ajustada de acordo com o tempo total de execução do mesmo.

c) Pelo menos um evento espera por um evento que não vai ocorrer.

d) Dois ou mais processos são forçados a acessar dados críticos alternando estritamente entre eles.

e) O processo tenta, mas não consegue acessar uma variável compartilhada, pois está bloqueado.

O que caracteriza os algoritmos de escalonamento de processos chamados de preemptivos é: a) permitir que cada processo execute até o final; b) suspender temporariamente processos em execução

para que outros possam ser executados; c) suspender definitivamente o sistema operacional

para que os processos usuários possam ser executados até o final.

d) suspender temporariamente as operações de entrada de saída, para que as operações de cálculo sejam executadas:

e) suspender temporariamente as rotinas de calculo para que as operações de entrada e saída possam ser executadas.

Assinale a opção correta com relação aos mecanismos e às técnicas de sincronização de processos e suas implementações.

A) Condições de corrida normalmente ocorrem apenas em sistemas com kernel não preemptivos.

B) O kernel do Linux 2.6 é não preemptivo.

C) Um semáforo implementado com variável inteira normalmente é denominado mutex.

D) Semáforos são vistos como uma evolução dos monitores, uma vez que minimizam vários problemas encontrados na implementação dos monitores.

E) As soluções para resolver o problema de seção crítica devem satisfazer, entre outros, os requisitos de exclusão mútua.

Quando dois processos A e B não concluem as suas execuções porque o processo A depende do término do processo B que, por sua vez, depende da conclusão do processo A, tem-se uma situação denominada:

a) deadlock.

b) compartilhamento de recursos.

c) pipeline.

d) starvation

e) interrupção de CPU.

� Considere um gerenciador de bancos de dados sendo executado num ambiente operacional Unix. Durante a execução desse ambiente Unix, em parte do tempo um processo está ocupado, realizando um processamento que não resultará em condição de corrida, por não estar manipulando dados ou arquivos compartilhados.

No entanto, em outros momentos, o processo pode estar acessando uma parte da memória ou arquivo compartilhado com outros processos. Essa parte do programa, cujo processamento pode levar à ocorrência de condições de corrida, é denominada:A) região crítica.B) trashing.C) threshold.D) wakeup.

10

Analise as seguintes afirmações, levando em conta as chamadas de sistemas usadas com semáforos, e assinale a opção verdadeira.

I. A chamada de sistema UP adiciona uma unidade ao valor corrente de um semáforo.

II. Se o valor do semáforo é zero, uma chamada de sistema DOWN não será completada e o processo será suspenso.

III. Quando um processo inicia a execução de uma chamada de sistema UP ou DOWN, nenhum outro processo terá acesso ao semáforo até que o processo complete a execução ou seja suspenso.

a) Apenas I e II são verdadeiras.

b) Apenas I e III são verdadeiras.

c) Apenas II e III são verdadeiras.

d) I, II e III são verdadeiras.

e) I, II e III são falsas.

Em um sistema operacional sendo executado em um determinado computador, o processo A obteve acesso exclusivo ao recurso X e o processo B obteve acesso exclusivo ao recurso Y. Momentos depois, A, está aguardando a liberação de Y antes de ele próprio liberar X, enquanto B está aguardando a liberação de X antes de ele próprio liberar Y.

Esta situação recebe o nome de:

(a) mutex. (B) deadend.

(C) multi-thread. (D) deadlock

(E) inanição ou starvation.