1 of 41

MC504 Sistemas Operacionais

Prof. Dr. Eng. Isaías Bittencourt Felzmann

isaias@ic.unicamp.br

Campinas, 2s/2026

Sincronização de Processos

1/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

2 of 41

Aviso Legal

The following set of slides are copyright Silberschatz, Galvin and Gagne, 2018. Modifications were made for their use in conjunction with MC504. The original material is available at os-book.com .

Os direitos autorais do conjunto de slides a seguir pertencem a Silberschatz, Galvin and Gagne, 2018. Foram feitas modificações para seu uso em MC504. O material original está disponível em os-book.com .

Este material foi elaborado com apoio de ferramentas de IA generativa como recurso auxiliar. O conteúdo foi revisado, validado e é de responsabilidade do docente.

2/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

3 of 41

Objetivos

Descrever o problema da seção crítica e ilustrar uma condição de corrida
Ilustrar soluções de hardware para o problema da seção crítica usando barreiras de memória, operações compare-and-swap e variáveis atômicas
Demonstrar como locks mutex e semáforos podem ser usados para resolver o problema da seção crítica

Operating System Concepts – 10^th Edition

3/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

4 of 41

Contexto

Os processos podem ser executados concorrentemente

Um processo pode ser interrompido a qualquer momento, tendo concluído apenas parte de sua execução

O acesso concorrente a dados compartilhados pode resultar em inconsistência dos dados
Manter a consistência dos dados requer mecanismos que garantam a execução ordenada* dos processos cooperantes
No Capítulo 4, ilustramos esse problema ao considerar o Buffer Limitado, com um contador atualizado concorrentemente pelo produtor e pelo consumidor, o que levou a uma condição de corrida.

Operating System Concepts – 10^th Edition

4/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

5 of 41

Condição de Corrida

Os processos P0 e P1 estão criando processos filhos por meio da chamada de sistema fork()
Condição de corrida na variável do kernel next_available_pid, que representa o próximo identificador de processo (PID) disponível��
Sem um mecanismo que impeça P0 e P1 de acessar simultaneamente a variável next_available_pid, o mesmo PID poderia ser atribuído a dois processos diferentes!

Operating System Concepts – 10^th Edition

5/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

6 of 41

Problema da Seção Crítica

Considere um sistema com n processos {p0, p1, ... pn-1}
Cada processo possui um segmento de código denominado seção crítica

Nessa seção, o processo pode alterar variáveis comuns, atualizar tabelas, escrever em arquivos etc.
Quando um processo está em sua seção crítica, nenhum outro processo pode estar em sua própria seção crítica

O problema da seção crítica consiste em projetar um protocolo que atenda a esse requisito
Cada processo deve solicitar permissão para entrar em sua seção crítica na seção de entrada; a seção crítica pode ser seguida por uma seção de saída e, depois, pela seção restante

Operating System Concepts – 10^th Edition

6/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

7 of 41

Seção Crítica

Estrutura geral do processo Pi

Operating System Concepts – 10^th Edition

7/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

8 of 41

Problema da Seção Crítica (Cont.)

Exclusão mútua — Se o processo Pi estiver executando em sua seção crítica, nenhum outro processo poderá estar executando em sua própria seção crítica
Progresso — Se nenhum processo estiver em sua seção crítica e houver processos que desejem entrar nela, a escolha do próximo processo não poderá ser adiada indefinidamente
Espera limitada — Deve existir um limite para o número de vezes que outros processos podem entrar em suas seções críticas depois que um processo solicita entrada e antes que sua solicitação seja atendida

Pressupõe-se que cada processo seja executado a uma velocidade diferente de zero
Não se faz nenhuma suposição sobre a velocidade relativa dos n processos

Requisitos para uma solução do problema da seção crítica

Operating System Concepts – 10^th Edition

8/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

9 of 41

Solução baseada em interrupções

Seção de entrada: desativar interrupções
Seção de saída: habilitar interrupções
Isso vai resolver o problema?

E se a seção crítica for código que roda por uma hora?

Alguns processos podem sofrer starvation, sem nunca entrar na seção crítica?

E se houver duas CPUs?

Operating System Concepts – 10^th Edition

9/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

10 of 41

A Solução de Peterson

Solução para dois processos
Suponha que as instruções de máquina load e store sejam atômicas, isto é, não possam ser interrompidas
Os dois processos compartilham duas variáveis:

int turn;
boolean flag[2];

A variável turn indica de qual processo é a vez de entrar na seção crítica
O array flag indica se um processo está pronto para entrar na seção crítica

flag[i] = true indica que o processo Pi está pronto!

Operating System Concepts – 10^th Edition

10/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

11 of 41

Algoritmo para o Processo P_i

while (true) {

flag[i] = true;

turn = j;

while (flag[j] && turn == j)

;

/* critical section */

flag[i] = false;

/* remainder section */

}

Operating System Concepts – 10^th Edition

11/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

12 of 41

Correção da Solução de Peterson

Pode-se demonstrar que os três requisitos do problema da seção crítica são atendidos:

1. A exclusão mútua é preservada

Pi entra na seção crítica somente se:

flag[j] = false ou turn = i

2. O requisito de progresso é atendido

3. O requisito de espera limitada é atendido

Operating System Concepts – 10^th Edition

12/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

13 of 41

A Solução de Peterson e a Arquitetura Moderna

Embora seja útil para demonstrar um algoritmo, não há garantia de que a solução de Peterson funcione corretamente em arquiteturas modernas.

Para melhorar o desempenho, processadores e/ou compiladores podem reordenar operações que não possuem dependências

Entender por que isso pode falhar ajuda a compreender melhor as condições de corrida.
Em programas com uma única thread, isso é aceitável, pois o resultado será sempre o mesmo.
Em programas multithread, a reordenação pode produzir resultados inconsistentes ou inesperados!

Operating System Concepts – 10^th Edition

13/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

14 of 41

Barreira de Memória (Fence)

O modelo de memória define as garantias que uma arquitetura de computador oferece à memória dos programas de aplicação.
Modelos de memória podem ser:

Fortemente ordenado — uma modificação de memória realizada por um processador torna-se imediatamente visível para todos os demais processadores.
Fracamente ordenado — uma modificação de memória realizada por um processador pode não se tornar imediatamente visível para todos os demais processadores.

Uma barreira de memória é uma instrução que força a propagação de todas as alterações de memória, tornando-as visíveis aos demais processadores.�

Operating System Concepts – 10^th Edition

14/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

15 of 41

Instruções de Barreira de Memória

Quando uma instrução de barreira de memória é executada, o sistema garante que todas as operações de load e store anteriores sejam concluídas antes da execução de novas operações de load ou store.
Assim, mesmo que as instruções tenham sido reordenadas, a barreira de memória garante que as operações de store sejam concluídas e se tornem visíveis aos demais processadores antes das operações posteriores de load ou store.

Operating System Concepts – 10^th Edition

15/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

16 of 41

Hardware de Sincronização

Diversos sistemas oferecem suporte de hardware para implementar o código da seção crítica.
Em uniprocessadores, era possível desabilitar interrupções

O código em execução prosseguia sem preempção
Essa abordagem costuma ser ineficiente em sistemas multiprocessadores

Sistemas Operacionais que usam essa técnica apresentam baixa escalabilidade

Analisaremos duas formas de suporte de hardware:��1. Instruções de hardware��2. Variáveis atômicas

Operating System Concepts – 10^th Edition

16/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

17 of 41

Instruções de Hardware

Instruções especiais de hardware permitem testar e modificar o conteúdo de uma palavra ou trocar o conteúdo de duas palavras atomicamente, sem interrupção.

Instrução test_and_set
Instrução compare_and_swap

Operating System Concepts – 10^th Edition

17/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

18 of 41

A instrução test_and_set

Definição

boolean test_and_set(boolean *target)

{

boolean rv = *target;

*target = true;

return rv;

}

Propriedades

Executada atomicamente
Retorna o valor original do parâmetro fornecido
Define como true o novo valor do parâmetro fornecido

Operating System Concepts – 10^th Edition

18/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

19 of 41

Solução Usando test_and_set()

Variável booleana compartilhada lock, inicializada com false
Solução:

do {� while (test_and_set(&lock))

; /* do nothing */�

/* critical section */�

lock = false;

/* remainder section */

} while (true);

Isso resolve o problema da seção crítica?

Operating System Concepts – 10^th Edition

19/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

20 of 41

A instrução compare_and_swap

Definição

int compare_and_swap(int *value, int expected, int new_value)

{

int temp = *value;

if (*value == expected)

*value = new_value;

return temp;

}

Propriedades

Executada atomicamente
Retorna o valor original do parâmetro value
Define a variável value como o valor do parâmetro new_value, mas somente se *value == expected for verdadeiro. A troca ocorre apenas nessa condição.

Operating System Concepts – 10^th Edition

20/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

21 of 41

Solução usando compare_and_swap

Variável inteira compartilhada lock, inicializada com 0
Solução:

while (true) {� while (compare_and_swap(&lock, 0, 1) != 0)

; /* do nothing */�

/* critical section */�

lock = 0;�

/* remainder section */

}

Isso resolve o problema da seção crítica?

Operating System Concepts – 10^th Edition

21/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

22 of 41

Espera limitada com compare_and_swap

Operating System Concepts – 10^th Edition

22/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

23 of 41

Variáveis atômicas

Em geral, instruções como compare_and_swap são usadas como blocos de construção para outras ferramentas de sincronização.
Uma dessas ferramentas é a variável atômica, que fornece atualizações atômicas, isto é, ininterruptas, sobre tipos de dados básicos, como inteiros e booleanos.
Por exemplo:

Considere sequence uma variável atômica
Considere increment() uma operação sobre a variável atômica sequence
O comando:

increment(&sequence);

garante que sequence seja incrementada sem interrupção:��

Operating System Concepts – 10^th Edition

23/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

24 of 41

Variáveis atômicas

A função increment() pode ser implementada da seguinte forma:�� void increment(atomic_int *v)�{� int temp; � do {� temp = *v; � } � while (temp != (compare_and_swap(v,temp,temp+1)); �} ��

Operating System Concepts – 10^th Edition

24/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

25 of 41

Locks Mutex

As soluções anteriores são complexas e, em geral, inacessíveis aos programadores de aplicações
Projetistas de Sistemas Operacionais fornecem ferramentas de software para resolver o problema da seção crítica
A ferramenta mais simples é o lock mutex

Uma variável booleana indica se o lock está disponível ou não

Uma seção crítica é protegida da seguinte forma:

Primeiro, acquire() o lock
Depois, release() o lock

As chamadas a acquire() e release() devem ser atômicas

Em geral, são implementadas por meio de instruções atômicas de hardware, como compare_and_swap

Essa solução, porém, exige espera ocupada

Por isso, esse tipo de lock é denominado spinlock

Operating System Concepts – 10^th Edition

25/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

26 of 41

Solução do problema da seção crítica usando locks mutex

while (true) {

acquire lock

critical section

release lock

remainder section

}

Operating System Concepts – 10^th Edition

26/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

27 of 41

Semáforo

Ferramenta de sincronização que fornece mecanismos mais sofisticados do que locks mutex para que os processos sincronizem suas atividades.
Semáforo S — variável inteira
Só pode ser acessado por meio de duas operações indivisíveis, isto é, atômicas

wait() e signal()

Originalmente denominadas P() e V()

Definição da operação wait()

wait(S) {

while (S <= 0)

; // busy wait

S--;

}

Definição da operação signal()

signal(S) {

S++;

}

Operating System Concepts – 10^th Edition

27/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

28 of 41

Semáforo (continuação)

Semáforo contador — seu valor inteiro pode variar em um domínio irrestrito
Semáforo binário — seu valor inteiro pode variar apenas entre 0 e 1

Equivalente a um lock mutex

Um semáforo contador S pode ser implementado como um semáforo binário
Semáforos permitem resolver diversos problemas de sincronização

Operating System Concepts – 10^th Edition

28/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

29 of 41

Exemplo de Uso de Semáforo

Solução para o problema da seção crítica

Crie um semáforo “mutex” inicializado com 1

wait(mutex);

signal(mutex);

Considere P1 e P2, com as instruções S1 e S2, e o requisito de que S1 seja executada antes de S2

Crie um semáforo “synch” inicializado com 0

P1:

S1;

signal(synch);

P2:

wait(synch);

S2;

Operating System Concepts – 10^th Edition

29/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

30 of 41

Implementação com Semáforo

Deve-se garantir que dois processos não executem wait() e signal() simultaneamente sobre o mesmo semáforo
Assim, a implementação torna-se o próprio problema da seção crítica, no qual o código de wait e signal é colocado na seção crítica
Pode haver espera ocupada na implementação da seção crítica

Mas o código de implementação é curto
Há pouca espera ocupada quando a seção crítica raramente está ocupada

Aplicações podem permanecer muito tempo em suas seções críticas; portanto, essa não é uma boa solução

Operating System Concepts – 10^th Edition

30/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

31 of 41

Problemas com Semáforos

Uso incorreto de operações de semáforo:�

signal(mutex) ... wait(mutex)�
wait(mutex) ... wait(mutex)

Omissão de wait(mutex) e/ou signal(mutex)

Esses – e outros – são exemplos do que pode acontecer quando semáforos e outras ferramentas de sincronização são usados incorretamente.

Operating System Concepts – 10^th Edition

31/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

32 of 41

Problema dos Filósofos do Jantar

N filósofos sentam-se ao redor de uma mesa redonda, com uma tigela de arroz ao centro.

Eles passam a vida alternando entre pensar e comer.
Eles não interagem com os vizinhos.
De vez em quando, cada filósofo tenta pegar dois hashis, um de cada vez, para comer.

É necessário obter ambos para comer e liberar os dois ao terminar.

Para cinco filósofos, os dados compartilhados são:

Tigela de arroz — conjunto de dados
Semáforo chopstick[5] inicializado com 1

Operating System Concepts – 10^th Edition

32/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

33 of 41

Algoritmo do Problema dos Filósofos do Jantar

Solução com semáforos
A estrutura do filósofo i:

while (true) {

wait(chopstick[i]);

wait(chopstick[(i + 1) % 5]);

/* eat for a while */

signal(chopstick[i]);

signal(chopstick[(i + 1) % 5]);

/* think for a while */

}

Qual é o problema desse algoritmo?

Operating System Concepts – 10^th Edition

33/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

34 of 41

Locks Mutex POSIX

Criação e inicialização do lock��
Aquisição e liberação do lock

Operating System Concepts – 10^th Edition

34/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

35 of 41

Semáforos POSIX sem nome

Criação e inicialização do semáforo:��
Aquisição e liberação do semáforo:

Operating System Concepts – 10^th Edition

35/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

36 of 41

Semáforos POSIX nomeados

Criação e inicialização do semáforo:��
Outro processo pode acessar o semáforo por seu nome SEM.
Aquisição e liberação do semáforo:

Operating System Concepts – 10^th Edition

36/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

37 of 41

Liveness (Progresso)

Processos podem ter que esperar indefinidamente ao tentar adquirir uma ferramenta de sincronização, como um lock mutex ou um semáforo.
A espera indefinida viola os critérios de progresso e espera limitada discutidos anteriormente neste capítulo.
Liveness refere-se a um conjunto de propriedades que um sistema deve satisfazer para garantir que os processos progridam.
A espera indefinida é um exemplo de falha de liveness.

Operating System Concepts – 10^th Edition

37/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

38 of 41

Liveness (Progresso)

Deadlock — dois ou mais processos aguardam indefinidamente por um evento que só pode ser causado por um dos processos em espera
Considere S e Q, dois semáforos inicializados com 1

P₀ P₁

wait(S); wait(Q);

wait(Q); wait(S);

... ...

signal(S); signal(Q);

signal(Q); signal(S);

Considere que P0 execute wait(S) e P1 execute wait(Q). Quando P0 executar wait(Q), deverá aguardar até que P1 execute signal(Q).
Entretanto, P1 estará aguardando até que P0 execute signal(S).
Como essas operações signal() nunca serão executadas, P0 e P1 permanecerão bloqueados.

Operating System Concepts – 10^th Edition

38/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

39 of 41

Deadlock!

39/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

40 of 41

Liveness (Progresso)

Outras formas de falha de liveness, além do deadlock:
Starvation — bloqueio indefinido

Um processo pode nunca ser removido da fila do semáforo na qual está suspenso

Inversão de prioridade — problema de Escalonamento no qual um processo de menor prioridade mantém um lock necessário a processos de maior prioridade

Resolvida por meio do protocolo de herança de prioridade��

Operating System Concepts – 10^th Edition

40/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

41 of 41

Bibliografia

Capítulo 2.

Capítulos 6 e 7.

(Capítulo 5 na 9^a edição em Português).

41/41

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais