Deadlock e sincronização

A ponte de mão única

Imagine uma ponte estreita de mão única com carros dos dois lados. Um carro da direita entra, depois um da esquerda entra — agora estão frente a frente no meio da ponte. Nenhum pode recuar (sem preempção), cada um segura sua metade da ponte (hold and wait), cada metade só pode ser usada por um (exclusão mútua) e há espera circular. As 4 condições de Coffman estão presentes — é deadlock.

Grafo de alocação de recursos

Alterne entre os cenários para ver quando o grafo tem ciclo (deadlock) e quando está em estado seguro. O problema dos filósofos é um exemplo clássico de deadlock em espera circular.

Mutex, semáforos e seções críticas

// Mutex e semáforo — sincronização de threads

// Seção crítica protegida por mutex
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
int counter = 0;

void* incrementa(void* arg) {
  for (int i = 0; i < 1000000; i++) {
    pthread_mutex_lock(&lock);    // bloqueia se já travado
    counter++;                    // seção crítica (1 thread por vez)
    pthread_mutex_unlock(&lock);  // libera
  }
}
// Sem o mutex: race condition! counter pode ser menor que 2.000.000
// (leitura-modificação-escrita não é atômica)

// Deadlock clássico com dois mutexes:
// Thread 1: lock(A) → lock(B)   ← já tem A, espera B
// Thread 2: lock(B) → lock(A)   ← já tem B, espera A
// → espera circular = deadlock

// Solução: sempre adquirir locks na mesma ordem
// Thread 1 e Thread 2: lock(A) primeiro, depois lock(B)
// → garante que nunca há ciclo

Operações atômicas e primitivas de sincronização

// Alternativas a mutex: operações atômicas

// x86-64 tem instruções atômicas nativas:
int val = 0;
__atomic_fetch_add(&val, 1, __ATOMIC_SEQ_CST);  // atomicamente: val++

// Em C++11:
std::atomic<int> counter(0);
counter.fetch_add(1);  // operação read-modify-write atômica
// Sem mutex! A CPU garante atomicidade via LOCK prefix na instrução
// ex: LOCK XADD [mem], reg — atomic add and fetch

// Quando usar o quê:
// atomic: contadores simples, flags, ponteiros (lock-free)
// mutex: proteção de estruturas complexas (mais de 1 campo)
// semáforo: limitar acessos simultâneos (ex: pool de conexões)
// condition variable: esperar por condição (produtor-consumidor)

// Liveness properties:
// Deadlock: nenhum processo avança
// Livelock: processos "executam" mas sem progresso (ex: dois que cedem ao mesmo tempo)
// Starvation: processo específico nunca recebe recurso que precisa

Implementando sincronização

Mini projeto: reproduza um deadlock em C com pthreads: duas threads, dois mutexes A e B. Thread 1 faz lock(A) → sleep(10ms) → lock(B). Thread 2 faz lock(B) → sleep(10ms) → lock(A). Use pthread_mutex_trylock para detectar o deadlock ao invés de travar para sempre.

Projeto principal: implemente o problema produtor-consumidor com buffer circular de tamanho N usando semáforos: sem_t empty (inicializado com N), sem_t full (inicializado com 0), mutex (para acesso ao buffer). Produtor: sem_wait(empty) → escreve → sem_post(full). Consumidor: sem_wait(full) → lê → sem_post(empty).

Desafio extra: implemente um leitor-escritor (readers-writers) com prioridade para escritores: múltiplos leitores podem ler simultaneamente, mas um escritor precisa de acesso exclusivo. Use pthread_rwlock_t ou implemente manualmente com mutex + condition variables. Teste com 10 threads leitoras e 2 escritoras e meça o throughput vs. a versão com mutex único.

Teste sua intuição

Onde você encontra isso