Aula 10 — Problemas Clássicos de Sincronização
Os programas C desta aula compilam em Linux com gcc -lpthread. Execute-os para observar o comportamento concorrente em ação.
Objetivos
Ao final desta aula você deve ser capaz de:
- Descrever os três problemas clássicos de sincronização e identificar o padrão de cada um em aplicações reais.
- Implementar a solução do Buffer Limitado com três semáforos (
mutex,empty,full) e explicar o papel de cada um. - Explicar por que a ordem dos
wait()importa no Produtor/Consumidor e o que acontece se invertida. - Analisar o problema dos Leitores-Gravadores nas suas duas variantes (favorece leitores / favorece gravadores) e identificar qual grupo pode sofrer starvation em cada uma.
- Demonstrar o deadlock na solução ingênua do Jantar dos Filósofos e apresentar pelo menos três estratégias para evitá-lo.
- Comparar a solução com semáforos e com monitor para o Jantar dos Filósofos, identificando a vantagem de cada abordagem.
Conteúdo
Contexto: por que problemas clássicos?
Os três problemas desta aula são mais do que exercícios acadêmicos — são padrões arquitetônicos que aparecem em sistemas reais:
| Problema | Padrão real |
|---|---|
| Buffer Limitado (Produtor/Consumidor) | Filas de mensagens, pipelines de processamento, buffers de E/S, logs assíncronos |
| Leitores-Gravadores | Caches, bancos de dados, sistemas de arquivos, configuração compartilhada |
| Jantar dos Filósofos | Alocação de múltiplos recursos não-compartilháveis entre processos concorrentes |
Cada um representa uma classe de problemas. Dominar as soluções aqui dá ferramentas para resolver variantes em qualquer domínio.
Problema 1: Buffer Limitado (Produtor/Consumidor)
Descrição
Um ou mais produtores geram itens e os inserem num buffer circular de tamanho N. Um ou mais consumidores retiram itens do buffer para processá-los.
Restrições a serem garantidas:
- O produtor não pode inserir se o buffer está cheio.
- O consumidor não pode retirar se o buffer está vazio.
- Apenas um processo acessa o buffer por vez (exclusão mútua).
Estrutura de dados
Buffer circular com N slots:
┌───┬───┬───┬───┬───┐
│ │ │ │ │ │ capacity = N
└───┴───┴───┴───┴───┘
↑in ↑out
Três semáforos:
| Semáforo | Valor inicial | Significado |
|---|---|---|
mutex | 1 | Exclusão mútua no acesso ao buffer |
empty | N | Número de slots vazios (produtor pode inserir?) |
full | 0 | Número de slots cheios (consumidor pode retirar?) |
Solução com semáforos (pseudocódigo)
Produtor: Consumidor:
───────────────────────── ────────────────────────
loop: loop:
produz item wait(full) ← espera haver item
wait(empty) ← espera slot wait(mutex)
wait(mutex) retira item do buffer
insere item no buffer signal(mutex)
signal(mutex) signal(empty) ← libera slot
signal(full) ← sinaliza item consome item
Por que wait(empty) vem ANTES de wait(mutex) no Produtor?
Se a ordem fosse invertida (wait(mutex) primeiro, depois wait(empty)):
- Produtor adquire
mutex, buffer está cheio →wait(empty)bloqueia com mutex em posse - Consumidor tenta
wait(mutex)→ bloqueia (mutex ocupado) - Deadlock: produtor aguarda consumidor liberar espaço, consumidor aguarda mutex que produtor detém
A ordem correta: semáforos de condição (empty/full) sempre antes do mutex.
Implementação em C com pthreads e semáforos POSIX
/* Executável — Produtor/Consumidor com buffer limitado */
/* Compile: gcc -o prod_cons prod_cons.c -lpthread */
#include <semaphore.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define N 5 /* tamanho do buffer */
#define N_PROD 2 /* número de produtores */
#define N_CONS 2 /* número de consumidores */
#define ITEMS_EACH 8 /* itens produzidos/consumidos por cada */
int buffer[N]; /* buffer circular compartilhado */
int in = 0; /* próxima posição de inserção */
int out = 0; /* próxima posição de retirada */
sem_t mutex; /* exclusão mútua no buffer */
sem_t empty; /* slots vazios disponíveis */
sem_t full; /* slots cheios disponíveis */
void *produtor(void *arg)
{
int id = *(int *)arg;
for (int i = 0; i < ITEMS_EACH; i++) {
int item = rand() % 100; /* produz item */
sem_wait(&empty); /* espera slot vazio */
sem_wait(&mutex); /* entra na SC */
buffer[in] = item;
printf("[P%d] inseriu %d na pos %d\n", id, item, in);
in = (in + 1) % N;
sem_post(&mutex); /* sai da SC */
sem_post(&full); /* sinaliza item */
usleep(rand() % 200000); /* simula produção */
}
return NULL;
}
void *consumidor(void *arg)
{
int id = *(int *)arg;
for (int i = 0; i < ITEMS_EACH; i++) {
sem_wait(&full); /* espera item */
sem_wait(&mutex); /* entra na SC */
int item = buffer[out];
printf("[C%d] retirou %d da pos %d\n", id, item, out);
out = (out + 1) % N;
sem_post(&mutex); /* sai da SC */
sem_post(&empty); /* sinaliza slot */
usleep(rand() % 300000); /* simula consumo */
}
return NULL;
}
int main(void)
{
pthread_t prod[N_PROD], cons[N_CONS];
int ids[N_PROD + N_CONS];
sem_init(&mutex, 0, 1);
sem_init(&empty, 0, N);
sem_init(&full, 0, 0);
for (int i = 0; i < N_PROD; i++) {
ids[i] = i;
pthread_create(&prod[i], NULL, produtor, &ids[i]);
}
for (int i = 0; i < N_CONS; i++) {
ids[N_PROD + i] = i;
pthread_create(&cons[i], NULL, consumidor, &ids[N_PROD + i]);
}
for (int i = 0; i < N_PROD; i++) pthread_join(prod[i], NULL);
for (int i = 0; i < N_CONS; i++) pthread_join(cons[i], NULL);
sem_destroy(&mutex);
sem_destroy(&empty);
sem_destroy(&full);
return 0;
}
Atividade prática rápida: altere
Npara 1 e observe como produtor e consumidor se revezam estritamente. Depois aumente para 10 e veja mais paralelismo.
Problema 2: Leitores-Gravadores
Descrição
Um banco de dados (ou qualquer recurso) é acessado por dois tipos de processos:
- Leitores: podem ler concorrentemente — múltiplos leitores simultâneos são seguros.
- Gravadores: precisam de acesso exclusivo — nenhum outro leitor ou gravador pode estar ativo.
Restrições:
- Vários leitores podem ler simultaneamente.
- Apenas um gravador por vez, com exclusividade total.
Primeira variante: favorece leitores
Nenhum leitor espera a menos que um gravador já tenha obtido o acesso.
Dados compartilhados:
semaphore rw_mutex = 1; /* exclusão mútua gravadores ↔ leitores */
semaphore mutex = 1; /* protege read_count */
int read_count = 0; /* quantos leitores estão lendo agora */
Gravador: Leitor:
───────────────────── ─────────────────────────────────
loop: loop:
wait(rw_mutex) wait(mutex)
escreve read_count++
signal(rw_mutex) if read_count == 1:
wait(rw_mutex) ← 1º leitor bloqueia gravador
signal(mutex)
lê dados
wait(mutex)
read_count--
if read_count == 0:
signal(rw_mutex) ← último libera gravador
signal(mutex)
Lógica do leitor: o primeiro leitor que chega "bloqueia" gravadores adquirindo rw_mutex. Os leitores subsequentes simplesmente incrementam read_count sem precisar do rw_mutex. O último leitor a sair libera rw_mutex, permitindo que um gravador entre.
Problema desta variante: gravadores podem sofrer starvation — se leitores chegam continuamente, read_count nunca chega a 0, e o gravador espera indefinidamente.
Segunda variante: favorece gravadores
Uma vez que um gravador está pronto, nenhum novo leitor pode começar a ler.
Problema desta variante: leitores podem sofrer starvation se gravadores chegam continuamente.
Tabela comparativa
| Aspecto | 1ª variante (favorece leitores) | 2ª variante (favorece gravadores) |
|---|---|---|
| Concorrência de leitura | Alta | Menor |
| Starvation de gravadores | Possível | Não |
| Starvation de leitores | Não | Possível |
| Uso típico | Dados raramente modificados (config) | Dados atualizados frequentemente |
Read-write locks em POSIX:
/* Somente leitura — pthread_rwlock_t: abstração de nível mais alto */
pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;
/* Leitor */
pthread_rwlock_rdlock(&rwlock); /* múltiplos leitores simultâneos */
/* lê dados */
pthread_rwlock_unlock(&rwlock);
/* Gravador */
pthread_rwlock_wrlock(&rwlock); /* exclusão total */
/* escreve */
pthread_rwlock_unlock(&rwlock);
Problema 3: Jantar dos Filósofos
Descrição
Cinco filósofos sentam em torno de uma mesa circular. Entre cada par de filósofos adjacentes há um chopstick (palito). Para comer, um filósofo precisa dos dois chopsticks adjacentes — o da esquerda e o da direita. Quando não come, pensa.
F0
/ \
ch4 ch0
/ \
F4 ... F1
\ /
ch3 ch1
\ /
F3 — ch2 — F2
O problema: como garantir que filósofos possam comer sem deadlock e sem starvation?
Solução ingênua (com deadlock)
/* Somente leitura — solução com deadlock */
semaphore chopstick[5] = {1, 1, 1, 1, 1};
/* Filósofo i */
do {
wait(chopstick[i]); /* pega o da esquerda */
wait(chopstick[(i+1) % 5]); /* pega o da direita */
/* come */
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
/* pensa */
} while (true);
Cenário de deadlock: todos os 5 filósofos ficam com fome ao mesmo tempo e cada um pega seu chopstick esquerdo. Agora chopstick[0..4] = 0. Cada um tenta pegar o direito → todos bloqueiam. Espera circular fechada.
As quatro condições de Coffman estão presentes: exclusão mútua (chopstick), retenção e espera (tem um, espera outro), sem preempção, espera circular.
Três soluções para o deadlock
Solução 1: Limite de 4 filósofos à mesa
Permitir no máximo 4 filósofos sentados simultaneamente. Com 4 filósofos e 5 chopsticks, pelo menos um sempre consegue pegar os dois — a espera circular é impossível.
/* Somente leitura — semáforo de capacidade */
semaphore cadeiras = 4; /* no máximo 4 filósofos à mesa */
wait(cadeiras);
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
/* come */
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
signal(cadeiras);
Solução 2: Pegar ambos os chopsticks atomicamente
Um filósofo só pega os chopsticks se ambos estiverem disponíveis — em seção crítica:
/* Somente leitura */
wait(mutex); /* entra na SC global */
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
signal(mutex);
/* come */
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
Problema: reduz concorrência — apenas um filósofo por vez pode tentar pegar chopsticks.
Solução 3: Ordenação assimétrica (quebra espera circular)
Filósofos ímpares pegam primeiro o chopstick esquerdo; filósofos pares pegam primeiro o direito. Isso quebra a simetria que causa a espera circular:
/* Somente leitura */
if (i % 2 == 0) {
wait(chopstick[(i+1) % 5]); /* par: direita primeiro */
wait(chopstick[i]);
} else {
wait(chopstick[i]); /* ímpar: esquerda primeiro */
wait(chopstick[(i+1) % 5]);
}
Solução com Monitor (livre de deadlock)
A solução mais elegante usa um monitor com três estados por filósofo (THINKING, HUNGRY, EATING) e variáveis de condição:
/* Somente leitura — monitor DiningPhilosophers (pseudocódigo) */
monitor DiningPhilosophers {
enum {THINKING, HUNGRY, EATING} state[5];
condition self[5];
void pickup(int i) {
state[i] = HUNGRY;
test(i); /* tenta comer imediatamente */
if (state[i] != EATING)
self[i].wait(); /* espera ser liberado */
}
void putdown(int i) {
state[i] = THINKING;
test((i + 4) % 5); /* notifica vizinho esquerdo */
test((i + 1) % 5); /* notifica vizinho direito */
}
void test(int i) {
if (state[(i+4)%5] != EATING &&
state[i] == HUNGRY &&
state[(i+1)%5] != EATING) {
state[i] = EATING;
self[i].signal(); /* acorda filósofo i */
}
}
initialization_code() {
for (int i = 0; i < 5; i++) state[i] = THINKING;
}
}
Por que não há deadlock: um filósofo só muda para EATING se ambos os vizinhos não estão comendo — checagem atômica dentro do monitor. Nunca há situação em que um filósofo detém um recurso parcial esperando o outro.
Cuidado: esta solução é livre de deadlock mas não é livre de starvation — um filósofo pode morrer de fome se seus dois vizinhos se revezarem continuamente.
Implementação em C com pthreads
/* Executável — Jantar dos Filósofos com mutex e variáveis de condição */
/* Compile: gcc -o filosofos filosofos.c -lpthread */
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define N 5
typedef enum { THINKING, HUNGRY, EATING } Estado;
Estado state[N];
pthread_mutex_t mutex_monitor = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t self[N]; /* uma condição por filósofo */
void test(int i)
{
if (state[(i+4)%N] != EATING &&
state[i] == HUNGRY &&
state[(i+1)%N] != EATING) {
state[i] = EATING;
pthread_cond_signal(&self[i]); /* acorda filósofo i */
}
}
void pickup(int i)
{
pthread_mutex_lock(&mutex_monitor);
state[i] = HUNGRY;
printf("Filósofo %d está com fome\n", i);
test(i);
while (state[i] != EATING) /* verifica spurious wakeup */
pthread_cond_wait(&self[i], &mutex_monitor);
printf("Filósofo %d está COMENDO\n", i);
pthread_mutex_unlock(&mutex_monitor);
}
void putdown(int i)
{
pthread_mutex_lock(&mutex_monitor);
state[i] = THINKING;
printf("Filósofo %d está PENSANDO\n", i);
test((i+4)%N); /* notifica vizinhos */
test((i+1)%N);
pthread_mutex_unlock(&mutex_monitor);
}
void *filosofo(void *arg)
{
int i = *(int *)arg;
for (int r = 0; r < 3; r++) { /* 3 refeições cada */
usleep(rand() % 500000); /* pensa */
pickup(i);
usleep(rand() % 300000); /* come */
putdown(i);
}
return NULL;
}
int main(void)
{
pthread_t tid[N];
int ids[N];
for (int i = 0; i < N; i++) {
state[i] = THINKING;
pthread_cond_init(&self[i], NULL);
ids[i] = i;
}
for (int i = 0; i < N; i++)
pthread_create(&tid[i], NULL, filosofo, &ids[i]);
for (int i = 0; i < N; i++)
pthread_join(tid[i], NULL);
for (int i = 0; i < N; i++)
pthread_cond_destroy(&self[i]);
return 0;
}
Visão unificada dos três problemas
Problema Recurso compartilhado Quem pode acessar Primitiva-chave
─────────────────────────────────────────────────────────────────────────────────
Buffer Limitado Buffer circular N slots 1 prod. ou 1 cons./vez empty, full, mutex
Leitores-Gravers Banco de dados N leitores OU 1 gravador rw_mutex, read_count
Jantar Filósofos 2 chopsticks por vez 1 filósofo p/ par vizinho state[], condição
Padrão comum: os três problemas precisam de dois tipos de sincronização simultâneos:
- Exclusão mútua (quem acessa o recurso)
- Sincronização condicional (quando pode acessar — buffer cheio, buffer vazio, vizinhos comendo)
Exercícios
Questões dissertativas
No problema do Buffer Limitado, explique o papel de cada um dos três semáforos (mutex, empty, full) e o que aconteceria se qualquer um deles fosse removido.
O que acontece se no Produtor a ordem for wait(mutex) antes de wait(empty) (invertida)? Demonstre com um cenário concreto.
Na solução do problema dos Leitores-Gravadores (1ª variante), explique por que o semáforo rw_mutex é adquirido apenas pelo primeiro leitor e liberado apenas pelo último. Qual o propósito do read_count?
Na solução ingênua do Jantar dos Filósofos, demonstre o deadlock com os 5 filósofos. Identifique as quatro condições de Coffman neste cenário.
Explique a solução assimétrica para o Jantar dos Filósofos. Por que quebrar a simetria elimina a espera circular?
Na solução com monitor para o Jantar dos Filósofos, por que a função test() é chamada tanto em pickup() quanto em putdown()? O que cada chamada verifica?
Compare as soluções do Jantar dos Filósofos com semáforos (solução ingênua + correção) e com monitor. Qual é mais fácil de raciocinar sobre corretude? Por quê?
A solução com monitor para o Jantar dos Filósofos é livre de deadlock mas não de starvation. Descreva um cenário onde um filósofo morreria de fome.
O problema dos Leitores-Gravadores pode aparecer em bancos de dados. Explique como pthread_rwlock_t resolve este problema na prática e quando você preferiria usá-lo no lugar de um mutex simples.
Trace a execução da solução com monitor para o Jantar dos Filósofos: F0 faz pickup(0), depois F1 faz pickup(1), depois F0 faz putdown(0). Quais transições de estado ocorrem? F1 consegue comer?
Quiz de múltipla escolha
1. No Buffer Limitado com semáforos, qual é o valor inicial correto de cada semáforo para um buffer de 5 slots?
- a)mutex=0, empty=0, full=5
- b)mutex=1, empty=5, full=0
- c)mutex=1, empty=0, full=5
- d)mutex=5, empty=1, full=0
- e)mutex=1, empty=1, full=1
2. No Produtor/Consumidor, o Produtor executa wait(mutex) ANTES de wait(empty) com o buffer cheio. O que ocorre?
- a)O produtor insere no buffer normalmente
- b)O produtor libera o mutex e aguarda o buffer ter espaço
- c)Deadlock — produtor bloqueia em wait(empty) com mutex em posse; consumidor não pode adquirir mutex para liberar espaço
- d)Starvation — produtor nunca consegue inserir
- e)O buffer circular é expandido automaticamente
3. Na solução dos Leitores-Gravadores (1ª variante), quantos leitores podem estar lendo simultaneamente enquanto nenhum gravador está ativo?
- a)Apenas 1 — o mutex garante exclusão
- b)Exatamente 2 — um para cada semáforo
- c)N leitores ilimitados — múltiplos leitores são permitidos concorrentemente
- d)O número de leitores definido na inicialização de rw_mutex
- e)Apenas N/2 onde N é o tamanho do banco de dados
4. Na solução ingênua do Jantar dos Filósofos, todos os 5 filósofos ficam com fome e pegam seu chopstick esquerdo. Qual condição de deadlock é satisfeita pelo comportamento 'ninguém larga o chopstick que tem'?
- a)Exclusão mútua
- b)Retenção e espera
- c)Inexistência de preempção
- d)Espera circular
- e)Starvation
5. A solução assimétrica do Jantar dos Filósofos (pares pegam direita primeiro, ímpares pegam esquerda) elimina qual condição de Coffman para prevenir deadlock?
- a)Exclusão mútua — os chopsticks tornam-se compartilháveis
- b)Retenção e espera — filósofos pegam ambos de uma vez
- c)Inexistência de preempção — o SO pode tomar chopsticks
- d)Espera circular — a assimetria garante que a cadeia de espera não fecha um ciclo
- e)Não elimina nenhuma — apenas reduz a probabilidade
6. Na solução com monitor para o Jantar dos Filósofos, um filósofo i só pode passar para EATING se qual condição é verificada em test()?
- a)state[i] == HUNGRY E state[i-1] == THINKING E state[i+1] == THINKING
- b)state[i-1] != EATING E state[i] == HUNGRY E state[i+1] != EATING
- c)state[i-1] == HUNGRY E state[i+1] == HUNGRY
- d)read_count == 0 para ambos os vizinhos
- e)O filósofo esperou mais de N segundos na fila
7. Qual é a função de pthread_rwlock_rdlock() versus pthread_rwlock_wrlock()?
- a)rdlock bloqueia todos; wrlock permite leitura simultânea
- b)rdlock permite múltiplos leitores simultâneos; wrlock garante acesso exclusivo ao escritor
- c)Ambos garantem exclusão mútua total — a diferença é apenas semântica
- d)rdlock é para threads; wrlock é para processos separados
- e)rdlock é não-bloqueante; wrlock sempre bloqueia
8. A solução com monitor DiningPhilosophers é livre de deadlock. Qual aspecto do design garante isso?
- a)O uso de variáveis de condição impede qualquer bloqueio
- b)O filósofo só muda para EATING se ambos os vizinhos não estão EATING — verificação atômica dentro do monitor impede retenção parcial
- c)O monitor usa apenas um semáforo para todos os filósofos
- d)Os filósofos não podem ficar HUNGRY ao mesmo tempo
- e)O monitor implementa timeout automático
9. No problema dos Leitores-Gravadores (1ª variante), gravadores podem sofrer starvation. Qual condição cria essa possibilidade?
- a)Gravadores fazem wait(mutex) muito frequentemente
- b)Se leitores chegam continuamente, read_count nunca chega a 0, e rw_mutex nunca é liberado para o gravador em espera
- c)A primeira variante não permite que gravadores esperem
- d)Gravadores têm prioridade menor que leitores no escalonador
- e)O semáforo rw_mutex tem capacidade limitada de processos em fila
10. A solução do Buffer Limitado com semáforos suporta múltiplos produtores e múltiplos consumidores simultaneamente?
- a)Não — a solução só funciona com exatamente 1 produtor e 1 consumidor
- b)Sim — o semáforo mutex garante que apenas um processo (produtor OU consumidor) modifica o buffer por vez, e empty/full controlam as condições independentemente
- c)Apenas múltiplos produtores — múltiplos consumidores precisam de solução diferente
- d)Apenas se N (tamanho do buffer) for maior que o número de produtores + consumidores
- e)Não — produtores e consumidores não podem compartilhar o mesmo mutex
Referências
Principais (essenciais)
- SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Fundamentos de Sistemas Operacionais. 9. ed. LTC, 2015.
- §5.7.1 — Buffer Limitado (Produtor/Consumidor)
- §5.7.2 — Leitores-Gravadores
- §5.7.3 — Filósofos Comensais
- §5.8.2 — Solução com Monitor para Filósofos
Aprofundamento (opcionais)
- TANENBAUM, A. S. Sistemas Operacionais Modernos. 4. ed. Pearson, 2016. §2.3.6 — Problemas clássicos de IPC.
- KERRISK, M. The Linux Programming Interface. No Starch Press, 2010. Cap. 30 — Threads: sincronização.
man 3 pthread_rwlock_rdlock,man 3 pthread_rwlock_wrlock— referência POSIX de rwlocks.
Recursos Complementares
Opcional — Vídeos para reforçar os conceitos desta aula.
18:40Producer Consumer Problem Using Semaphores
Neso Academy
Solução completa do Buffer Limitado com três semáforos, passo a passo. Cobre §5.7.1 do Silberschatz.
25:00:00Operating Systems — Full Course (25h)
freeCodeCamp.org
Para esta aula, foque nos módulos Classic Synchronization Problems e Dining Philosophers.