Problemas de Concorrência

Thread A              Thread B
────────              ────────
load  R1, [contador]
                      load  R2, [contador]
add   R1, 1
                      add   R2, 1
store [contador], R1
                      store [contador], R2

Se contador = 5 inicialmente:
  Thread A lê 5, soma 1, escreve 6
  Thread B lê 5, soma 1, escreve 6
  Resultado final: 6 (deveria ser 7!)

Esse é o problema: a atualização de B sobrescreveu a de A.
O incremento foi "perdido" (lost update).

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

int contador = 0;  // variável compartilhada

void* incrementar(void* arg) {
    for (int i = 0; i < 1000000; i++) {
        contador++;  // NÃO é atômico! (load, add, store)
    }
    return NULL;
}

int main() {
    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("Esperado: 2000000\n");
    printf("Obtido:   %d\n", contador);
    // Resultado típico: algo entre 1000000 e 2000000
    // Nunca é o mesmo valor duas vezes!
    return 0;
}

while (true) {
    ┌─────────────────────────────┐
    │  SEÇÃO DE ENTRADA           │  ← protocolo para entrar
    │  (entry section)            │
    └─────────────────────────────┘
    ┌─────────────────────────────┐
    │  SEÇÃO CRÍTICA              │  ← acesso ao recurso compartilhado
    │  (critical section)         │
    └─────────────────────────────┘
    ┌─────────────────────────────┐
    │  SEÇÃO DE SAÍDA             │  ← protocolo para sair
    │  (exit section)             │
    └─────────────────────────────┘
    ┌─────────────────────────────┐
    │  SEÇÃO RESTANTE             │  ← código que não usa recurso
    │  (remainder section)        │     compartilhado
    └─────────────────────────────┘
}

Uma solução correta deve satisfazer 3 propriedades:

1. Exclusão mútua: no máximo 1 processo na seção crítica
2. Progresso: se nenhum processo está na SC e alguém quer entrar,
   a decisão não pode ser adiada indefinidamente
3. Espera limitada (bounded waiting): existe um limite no número
   de vezes que outros processos entram na SC enquanto um
   processo espera

int turno = 0;  // compartilhada

// Processo 0
while (turno != 0) ;  // espera ocupada (busy wait)
// SEÇÃO CRÍTICA
turno = 1;

// Processo 1
while (turno != 1) ;
// SEÇÃO CRÍTICA
turno = 0;

// Problema: alternância ESTRITA.
// Se P0 precisa entrar duas vezes seguidas, não pode.
// Viola a propriedade de PROGRESSO.

bool flag[2] = {false, false};

// Processo i (i = 0 ou 1, j = 1-i)
flag[i] = true;              // "eu quero entrar"
while (flag[j]) ;             // espera o outro sair
// SEÇÃO CRÍTICA
flag[i] = false;

// Problema: DEADLOCK possível!
// Se ambos setam flag = true ao mesmo tempo,
// ambos ficam esperando infinitamente.
// flag[0]=true, flag[1]=true → ambos em while(true)

int turno;
bool flag[2] = {false, false};

// Processo i (i = 0 ou 1, j = 1-i)
void entrar_secao_critica(int i) {
    int j = 1 - i;
    flag[i] = true;     // "eu quero entrar"
    turno = j;           // "mas dou a vez ao outro"
    while (flag[j] && turno == j)
        ;                // espero enquanto o outro quer E é a vez dele
}

void sair_secao_critica(int i) {
    flag[i] = false;    // "terminei, não quero mais"
}

/*
 Prova de correção:
 - Exclusão mútua: se ambos querem (flag=true), turno só pode ser
   0 OU 1, então um deles passa e o outro espera.
 - Progresso: se só um quer, flag do outro é false → entra direto.
 - Espera limitada: quem dá a vez (turno=j) garante que o outro
   entre antes de si na próxima iteração.

 Limitação: só funciona para 2 processos.
 Para N processos: algoritmo da padaria (Lamport, 1974).
*/

// Implementação conceitual (executa atomicamente no hardware)
bool test_and_set(bool* target) {
    bool antigo = *target;
    *target = true;
    return antigo;  // retorna o valor ANTERIOR
}

// Uso para exclusão mútua:
bool lock = false;  // compartilhada

// Entrada
while (test_and_set(&lock))
    ;  // spin: enquanto retorna true, alguém está na SC

// SEÇÃO CRÍTICA

// Saída
lock = false;

// Em x86: instrução XCHG ou LOCK BTS
// Em ARM: instrução LDREX/STREX

// Implementação conceitual (executa atomicamente no hardware)
bool compare_and_swap(int* ptr, int esperado, int novo) {
    if (*ptr == esperado) {
        *ptr = novo;
        return true;   // sucesso
    }
    return false;      // falha: outro thread modificou
}

// Uso: incremento atômico sem lock
void incremento_atomico(int* contador) {
    int antigo, novo;
    do {
        antigo = *contador;
        novo = antigo + 1;
    } while (!compare_and_swap(contador, antigo, novo));
    // Se alguém modificou entre o load e o CAS,
    // CAS falha e tentamos de novo (retry loop).
}

// Em x86: instrução CMPXCHG
// Em C11: atomic_compare_exchange_strong()
// Fundamento de estruturas lock-free

typedef struct {
    int locked;  // 0 = livre, 1 = ocupado
} spinlock_t;

void spin_lock(spinlock_t* lk) {
    while (__sync_lock_test_and_set(&lk->locked, 1))
        ;  // spin até adquirir
}

void spin_unlock(spinlock_t* lk) {
    __sync_lock_release(&lk->locked);
}

/*
 Quando usar spinlock:
 + Seções críticas CURTAS (poucos ciclos)
 + Contexto de kernel onde não pode dormir
 + Sistemas multiprocessador (spin em um core, trabalho no outro)

 Quando NÃO usar:
 - Seções críticas longas (desperdício de CPU)
 - Uniprocessador (spin impede o holder de executar!)
 - User space (prefira mutex com sleep)
*/

// Usado no kernel do Linux (local_irq_disable/enable)
void secao_critica_kernel() {
    unsigned long flags;
    local_irq_save(flags);    // salva e desabilita IRQs

    // SEÇÃO CRÍTICA
    // Nenhuma interrupção pode ocorrer aqui

    local_irq_restore(flags); // restaura estado anterior
}

/*
 Problemas:
 - Só funciona em uniprocessador (outros cores continuam executando!)
 - Se a SC for longa, interrupções de hardware ficam pendentes
   (pode perder dados de I/O, timer fica impreciso)
 - Não disponível em user space (seria um risco de segurança)
 - Usado no kernel apenas para SCs muito curtas e específicas
*/

Problema: dois agentes logam decisões ao mesmo tempo

  Agente A: INSERT INTO decisions (title) VALUES ('usar React')
  Agente B: INSERT INTO decisions (title) VALUES ('usar Vue')

No banco relacional com MVCC:
  - Cada transação vê um SNAPSHOT consistente do banco
  - INSERTs não conflitam (cada um cria nova row)
  - UPDATEs na mesma row: serialização automática
    (um espera o outro commitar, como exclusão mútua)

Na prática, o Postgres é como um lock manager sofisticado:
  - Row-level locks (granularidade fina, não trava tabela inteira)
  - Deadlock detection automático (grafo de espera)
  - Isolamento configurável (READ COMMITTED, SERIALIZABLE)

Comparação com o que vimos:
  Lock do Postgres ≈ mutex com sleep (não spinlock)
  MVCC ≈ copy-on-write (leitores nunca bloqueiam)
  Deadlock detection ≈ algoritmo de detecção com grafo de alocação