Semáforos e Monitores

Semáforo S: variável inteira ≥ 0

wait(S)  [também chamada P, proberen, "testar"]:
  atomicamente {
    enquanto S == 0: bloqueia (dorme)
    S = S - 1
  }

signal(S)  [também chamada V, verhogen, "incrementar"]:
  atomicamente {
    S = S + 1
    se algum processo está bloqueado em wait(S): acorda um
  }

Invariante: S nunca fica negativo.
As operações são ATÔMICAS: não podem ser interrompidas no meio.

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

sem_t mutex;
int contador = 0;

void* incrementar(void* arg) {
    for (int i = 0; i < 1000000; i++) {
        sem_wait(&mutex);     // P(mutex): decrementa, bloqueia se 0
        contador++;            // seção crítica (protegida)
        sem_post(&mutex);     // V(mutex): incrementa, acorda quem espera
    }
    return NULL;
}

int main() {
    sem_init(&mutex, 0, 1);  // valor inicial = 1

    pthread_t t1, t2;
    pthread_create(&t1, NULL, incrementar, NULL);
    pthread_create(&t2, NULL, incrementar, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("Resultado: %d\n", contador);
    // Agora SEMPRE imprime 2000000

    sem_destroy(&mutex);
    return 0;
}

#define MAX_CONEXOES 5
sem_t pool;

void init_pool() {
    sem_init(&pool, 0, MAX_CONEXOES);  // 5 conexões disponíveis
}

void usar_conexao() {
    sem_wait(&pool);   // adquire 1 conexão (bloqueia se todas em uso)

    // ... usa a conexão ...

    sem_post(&pool);   // libera 1 conexão
}

/*
 Estado do semáforo durante execução:
   Início: S = 5
   Thread A chama wait: S = 4  (A tem conexão)
   Thread B chama wait: S = 3  (B tem conexão)
   Thread C chama wait: S = 2
   Thread D chama wait: S = 1
   Thread E chama wait: S = 0
   Thread F chama wait: F BLOQUEIA (S não pode ficar negativo)
   Thread A chama post: S = 1, F é acordado → S = 0
*/

#define TAM_BUFFER 10

int buffer[TAM_BUFFER];
int in = 0, out = 0;

sem_t mutex;    // exclusão mútua no buffer (init = 1)
sem_t vazio;    // slots vazios disponíveis (init = TAM_BUFFER)
sem_t cheio;    // slots cheios disponíveis (init = 0)

void* produtor(void* arg) {
    while (1) {
        int item = produzir_item();

        sem_wait(&vazio);      // espera slot vazio
        sem_wait(&mutex);      // entra na SC

        buffer[in] = item;
        in = (in + 1) % TAM_BUFFER;

        sem_post(&mutex);      // sai da SC
        sem_post(&cheio);      // sinaliza: +1 slot cheio
    }
}

void* consumidor(void* arg) {
    while (1) {
        sem_wait(&cheio);      // espera slot cheio
        sem_wait(&mutex);      // entra na SC

        int item = buffer[out];
        out = (out + 1) % TAM_BUFFER;

        sem_post(&mutex);      // sai da SC
        sem_post(&vazio);      // sinaliza: +1 slot vazio

        consumir_item(item);
    }
}

/*
 ATENÇÃO à ORDEM dos waits!
 sem_wait(&vazio) ANTES de sem_wait(&mutex)
 Se inverter: deadlock quando buffer cheio!
   Produtor trava mutex, tenta wait(vazio) → bloqueia
   Consumidor tenta wait(mutex) → bloqueia
   Ninguém libera ninguém.
*/

sem_t rw_mutex;       // exclusão mútua para escritores (init = 1)
sem_t mutex;          // protege read_count (init = 1)
int read_count = 0;  // número de leitores ativos

void* leitor(void* arg) {
    sem_wait(&mutex);
    read_count++;
    if (read_count == 1)     // primeiro leitor trava o escritor
        sem_wait(&rw_mutex);
    sem_post(&mutex);

    // LEITURA (múltiplos leitores podem estar aqui)

    sem_wait(&mutex);
    read_count--;
    if (read_count == 0)     // último leitor libera o escritor
        sem_post(&rw_mutex);
    sem_post(&mutex);
}

void* escritor(void* arg) {
    sem_wait(&rw_mutex);  // acesso exclusivo

    // ESCRITA (apenas este escritor está aqui)

    sem_post(&rw_mutex);
}

/*
 Problema: starvation de escritores!
 Se leitores chegam continuamente, read_count nunca chega a 0,
 e o escritor nunca consegue entrar.
 Solução: variantes com prioridade para escritores (Silberschatz cap.7)
*/

         [F0]
      g4 /    \ g0
      [F4]    [F1]
      g3 |    | g1
      [F3]    [F2]
         \ g2 /

  F0..F4 = filósofos
  g0..g4 = garfos (um entre cada par)
  Fi precisa de gi e g((i+1)%5)

Algoritmo ingênuo (DEADLOCK):
  Filósofo i:
    while (1) {
        pensar();
        pegar(garfo[i]);           // pega esquerda
        pegar(garfo[(i+1) % 5]);   // pega direita
        comer();
        largar(garfo[i]);
        largar(garfo[(i+1) % 5]);
    }

  Se todos pegam o garfo da esquerda ao mesmo tempo:
  F0 tem g0, F1 tem g1, F2 tem g2, F3 tem g3, F4 tem g4
  Todos esperam o garfo da direita → DEADLOCK!

sem_t garfo[5];  // cada garfo é um semáforo (init = 1)

void* filosofo(void* arg) {
    int id = *(int*)arg;
    int esq = id;
    int dir = (id + 1) % 5;

    while (1) {
        pensar();

        // Solução: filósofo par pega esquerda primeiro,
        // filósofo ímpar pega direita primeiro.
        // Quebra a circularidade → sem deadlock.
        if (id % 2 == 0) {
            sem_wait(&garfo[esq]);
            sem_wait(&garfo[dir]);
        } else {
            sem_wait(&garfo[dir]);
            sem_wait(&garfo[esq]);
        }

        comer();

        sem_post(&garfo[esq]);
        sem_post(&garfo[dir]);
    }
}

/*
 Outras soluções válidas:
 1. Limitar a 4 filósofos sentados (semáforo contador init=4)
 2. Pegar ambos os garfos atomicamente (com mutex global)
 3. Solução de Chandy/Misra (garfos com prioridade)
*/

┌──────────────────────────────────────┐
│  MONITOR BoundedBuffer               │
│                                      │
│  dados compartilhados:               │
│    buffer[N], count, in, out         │  ← acessíveis apenas
│                                      │     via procedimentos
│  condition variables:                │     do monitor
│    notFull, notEmpty                 │
│                                      │
│  procedure insert(item):             │
│    while count == N:                 │
│      notFull.wait()    ← bloqueia    │
│    buffer[in] = item                 │
│    in = (in+1) % N                   │
│    count++                           │
│    notEmpty.signal()   ← acorda      │
│                                      │
│  procedure remove() → item:          │
│    while count == 0:                 │
│      notEmpty.wait()                 │
│    item = buffer[out]                │
│    out = (out+1) % N                 │
│    count--                           │
│    notFull.signal()                  │
│    return item                       │
│                                      │
│  ┌──────────────────────────┐        │
│  │ Fila de entrada          │        │
│  │ (threads esperando para  │        │
│  │  entrar no monitor)      │        │
│  └──────────────────────────┘        │
└──────────────────────────────────────┘

Regra fundamental:
  Apenas UMA thread pode estar executando dentro do monitor.
  As outras ficam na fila de entrada.
  Não precisa de lock explícito — o monitor garante isso.

#include <pthread.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  nao_vazio = PTHREAD_COND_INITIALIZER;
pthread_cond_t  nao_cheio = PTHREAD_COND_INITIALIZER;

int buffer[10], count = 0, in = 0, out = 0;

void inserir(int item) {
    pthread_mutex_lock(&mutex);

    while (count == 10)  // WHILE, não IF! (spurious wakeup)
        pthread_cond_wait(&nao_cheio, &mutex);
        // wait() atomicamente: libera mutex + bloqueia
        // quando acorda: readquire mutex automaticamente

    buffer[in] = item;
    in = (in + 1) % 10;
    count++;

    pthread_cond_signal(&nao_vazio);  // acorda 1 consumidor
    pthread_mutex_unlock(&mutex);
}

int remover() {
    pthread_mutex_lock(&mutex);

    while (count == 0)
        pthread_cond_wait(&nao_vazio, &mutex);

    int item = buffer[out];
    out = (out + 1) % 10;
    count--;

    pthread_cond_signal(&nao_cheio);  // acorda 1 produtor
    pthread_mutex_unlock(&mutex);
    return item;
}

/*
 Semáforo vs Condition Variable:
 ┌────────────────────┬─────────────────────────────┐
 │ Semáforo           │ Condition Variable           │
 ├────────────────────┼─────────────────────────────┤
 │ Tem valor (inteiro)│ Não tem valor (só fila)      │
 │ signal() acumula   │ signal() perde-se se ninguém │
 │                    │ está esperando               │
 │ wait() pode não    │ wait() sempre bloqueia       │
 │ bloquear (se S>0)  │                              │
 │ Independente       │ Precisa de mutex associado   │
 └────────────────────┴─────────────────────────────┘
*/

┌─────────────┬────────────────┬──────────────────┬─────────────────────┐
│             │ Mutex          │ Semáforo         │ Monitor             │
├─────────────┼────────────────┼──────────────────┼─────────────────────┤
│ Propósito   │ Exclusão mútua │ Sincronização +  │ Abstração completa  │
│             │                │ controle de      │ (dados + operações) │
│             │                │ recursos         │                     │
├─────────────┼────────────────┼──────────────────┼─────────────────────┤
│ Ownership   │ Sim (quem      │ Não (qualquer    │ Implícito           │
│             │ travou destrava│ um pode signal)  │                     │
├─────────────┼────────────────┼──────────────────┼─────────────────────┤
│ Valores     │ 0 ou 1         │ 0 a N            │ N/A (não tem valor) │
├─────────────┼────────────────┼──────────────────┼─────────────────────┤
│ Risco       │ Baixo          │ Alto (ordem      │ Baixo (automático)  │
│             │                │ errada = bug)    │                     │
├─────────────┼────────────────┼──────────────────┼─────────────────────┤
│ Em C/POSIX  │ pthread_mutex  │ sem_t            │ mutex + cond_var    │
├─────────────┼────────────────┼──────────────────┼─────────────────────┤
│ Em Java     │ synchronized   │ Semaphore        │ synchronized block  │
│             │ (implícito)    │ (java.util)      │ + wait/notify       │
└─────────────┴────────────────┴──────────────────┴─────────────────────┘

Produtor-Consumidor no harness.os:

  Produtores:                     Buffer (Postgres):
  ┌─────────┐                    ┌──────────────────┐
  │ Agente A │─── log_decision ──→│                  │
  │ Agente B │─── log_learning ──→│  Neon Postgres   │
  │ Agente C │─── end_session  ──→│  (MVCC = monitor)│
  └─────────┘                    └────────┬─────────┘
                                          │
  Consumidores:                           │
  ┌─────────────┐                         │
  │ Próxima      │←── start_session ──────┘
  │ sessão       │←── get_knowledge ──────┘
  │ (handoff)    │←── get_rules ──────────┘
  └─────────────┘

  Postgres resolve tudo:
  - INSERT não conflita entre agentes (como sem_post)
  - SELECT é lock-free via MVCC (como leitores no RW problem)
  - UPDATE na mesma row: serialização automática (como mutex)
  - Advisory locks: semáforo explícito quando necessário
    SELECT pg_advisory_lock(42);  -- wait(S)
    SELECT pg_advisory_unlock(42); -- signal(S)