O Problema da Exclusão Mútua

Volte pro counter++. Aquela linha vira três instruções: lê counter num registrador, incrementa o registrador, escreve de volta. O bug aparece quando uma thread é interrompida entre a leitura e a escrita, e outra thread lê o mesmo valor antigo antes da primeira salvar o resultado. As duas escrevem por cima uma da outra, e um incremento evapora.

O trecho de código que precisa rodar sem essa interferência (aqui, a sequência lê-incrementa-escreve) é o que queremos proteger. E “proteger” significa uma coisa específica: no máximo uma thread pode estar dentro dele por vez.

Vale insistir nesse ponto, porque é onde muita gente entende errado. Exclusão mútua não é sobre duas threads executarem “ao mesmo tempo” no sentido físico. Num computador single-core, duas threads nunca executam de verdade simultaneamente, e o bug do contador acontece do mesmo jeito, porque o escalonador interrompe uma thread no meio das três instruções. O que importa é a ocupação do trecho: uma thread que foi interrompida no meio do counter++ ainda está “dentro” dele, mesmo parada, sem executar nada. Exclusão mútua exige que, enquanto uma thread ocupa o trecho, nenhuma outra entre, esteja ela rodando ou preemptada.

O protocolo de entrada e saída

Pra impor essa ocupação exclusiva, cada thread precisa pedir permissão antes de entrar no trecho protegido e avisar quando sair. A estrutura geral fica assim:

enquanto (true) {
    // ... código que não mexe no recurso compartilhado ...

    protocolo_de_entrada()      // pede permissão pra entrar

    // trecho protegido: no máximo uma thread aqui dentro

    protocolo_de_saida()        // libera pra próxima

    // ... resto ...
}

A pergunta central é: o que colocar em protocolo_de_entrada e protocolo_de_saida pra que a coisa funcione? Uma resposta correta para essa pergunta precisa satisfazer três propriedades. Elas foram formuladas por Dijkstra nos anos 60, e valem para qualquer mecanismo, seja um mutex, um semáforo, ou um algoritmo feito na unha só com variáveis compartilhadas.

Exclusão mútua. No máximo uma thread ocupa o trecho protegido por vez. É a propriedade que dá nome a tudo, e é o que faltava no contador. Sem ela, o counter++ de duas threads se intercala e incrementos se perdem.

Progresso. Se ninguém está no trecho protegido e uma ou mais threads querem entrar, a decisão de qual entra não pode ser adiada pra sempre. Ou seja, o protocolo não pode travar num impasse quando o recurso está livre. Uma “solução” que simplesmente proíbe todo mundo de entrar satisfaz a exclusão mútua de forma trivial, e é inútil justamente por violar o progresso.

Espera limitada. Existe um limite pra quantas vezes outras threads conseguem entrar depois que uma thread pediu pra entrar e antes dela conseguir. Sem isso, uma thread azarada pode ficar eternamente vendo as outras passarem na frente. Esse problema tem nome próprio, starvation, e um mecanismo pode garantir exclusão mútua e progresso e ainda assim deixar uma thread morrer de fome.

Por que não fazer na unha

Uma reação natural é tentar resolver isso sozinho, com uma variável de flag:

int ocupado = 0;

void entrar(void) {
    while (ocupado) { }   // espera enquanto está ocupado
    ocupado = 1;          // marca como ocupado
}

void sair(void) {
    ocupado = 0;
}

Parece razoável, e está errado. while (ocupado) e ocupado = 1 são duas operações separadas. Duas threads podem, ambas, ver ocupado == 0, sair as duas do while, e as duas marcarem ocupado = 1 e entrarem juntas no trecho. O protocolo de entrada tem, ele mesmo, exatamente a race que estamos tentando eliminar. Aninhar a proteção não resolve, só empurra o problema um nível pra baixo.

Existem algoritmos corretos feitos só com leituras e escritas comuns, como o algoritmo de Peterson e o de Dekker, mas eles são engenhosos, limitados a duas threads na forma clássica, e frágeis diante do reordenamento de instruções que o hardware faz. Na prática, ninguém protege seção crítica assim. O que se usa é uma primitiva que resolve o entrar/sair de forma atômica, com apoio do hardware e do sistema operacional. Essa primitiva é o lock.