Starvation

Vamos medir um mutex sob disputa. O experimento coloca duas threads idênticas brigando pelo mesmo lock sem parar, cada uma contando quantas vezes conseguiu adquiri-lo em dois segundos. Nenhuma tem prioridade, nenhuma segura o lock por mais tempo que a outra: o código das duas é exatamente o mesmo. Vejamos os números primeiro:

$ ./main
thread 0: 23700713 aquisicoes
thread 1: 23120329 aquisicoes
pior rajada: 95700 aquisicoes seguidas sem uma das threads entrar

As duas primeiras linhas parecem tranquilizadoras. Cerca de 23 milhões de aquisições pra cada uma, praticamente empatado, que é o que você esperaria de duas threads iguais. Se olhasse só pro total, concluiria que o mutex trata as duas com perfeita justiça.

A terceira linha conta outra história. Em algum momento da execução, uma das threads adquiriu o lock quase 96 mil vezes seguidas antes da outra conseguir a sua vez uma única vez. Durante essa rajada, a thread preterida estava viva, pronta, chamando pthread_mutex_lock, e simplesmente não entrava. O total é justo na média, mas a distribuição tem picos em que uma thread fica de fora por dezenas de milhares de rodadas seguidas. E como as duas threads são iguais, não dá pra culpar nenhuma característica de uma delas: a rajada é uma propriedade do mutex, não das threads.

Esse é o fenômeno da starvation (inanição): uma thread não consegue progredir porque outra está sempre à sua frente na disputa por um recurso. Repare que não é deadlock. No deadlock, ninguém avança; aqui o programa como um todo voa, executando mais de 46 milhões de aquisições em dois segundos. O que falha é a garantia de que cada thread terá a sua vez em tempo razoável, aquela terceira propriedade do problema da exclusão mútua, a espera limitada.

Por que o mutex faz isso

O programa que gerou os números acima está no Código 8-3. Cada thread guarda quantas aquisições no total já tinham acontecido da última vez que ela entrou, e assim mede o maior intervalo em que ficou de fora:

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

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
int rodando = 1;                          // sempre acessado com o lock
long total[2] = {0, 0}, max_gap = 0;

void *worker(void *arg) {
    int eu = *(int *)arg;
    long last = -1;
    for (;;) {
        pthread_mutex_lock(&lock);
        if (!rodando) { pthread_mutex_unlock(&lock); break; }
        long agora = total[0] + total[1];
        if (last >= 0) {                  // pula a primeira aquisição
            long g = agora - last;        // aquisições desde a última minha
            if (g > max_gap) max_gap = g;
        }
        last = agora;
        total[eu]++;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main(void) {
    pthread_t t[2];
    int id[2] = {0, 1};
    pthread_create(&t[0], NULL, worker, &id[0]);
    pthread_create(&t[1], NULL, worker, &id[1]);

    struct timespec ts = {2, 0};
    nanosleep(&ts, NULL);
    pthread_mutex_lock(&lock);
    rodando = 0;
    pthread_mutex_unlock(&lock);

    pthread_join(t[0], NULL);
    pthread_join(t[1], NULL);
    printf("thread 0: %ld aquisicoes\n", total[0]);
    printf("thread 1: %ld aquisicoes\n", total[1]);
    printf("pior rajada: %ld aquisicoes seguidas sem uma das threads entrar\n", max_gap);
}

Rode você mesmo e o número da pior rajada vai variar bastante de uma execução pra outra, de algumas dezenas de milhares a mais de cem mil. Essa própria variabilidade é parte do problema: o pior caso não tem teto previsível.

A variável rodando é lida e escrita sempre com o mutex segurado, tanto pelas threads quanto pela main que a zera pra encerrar o teste. Isso não é firula: se a main escrevesse rodando = 0 fora do lock enquanto as threads leem dentro, teríamos exatamente o data race que estudamos, com todo o comportamento indefinido que ele traz. O flag de parada compartilhado precisa da mesma proteção que qualquer outro dado compartilhado.

A causa da rajada está em como um mutex acorda quem espera. Quando uma thread libera o lock e imediatamente tenta pegá-lo de novo, ela já está executando, com seus dados quentes no cache do core. A outra thread, que estava bloqueada esperando, precisa ser acordada pelo sistema operacional, recolocada em execução, e migrada de volta pro core. Nesse meio tempo, quem acabou de soltar já pegou de novo. O mutex do glibc não promete justiça: ele entrega o lock a quem estiver em melhor posição pra pegá-lo, e quem acabou de rodar está sempre em melhor posição que quem está dormindo. Enquanto uma das duas mantém o embalo, ela fura a fila repetidamente, comportamento que tem nome: barging.

Mutexes justos

A solução é usar um lock que garanta ordem de chegada, um mutex justo (fair). Um mutex justo mantém uma fila de quem está esperando e entrega o lock na ordem em que as threads chegaram, custe o que custar em performance. E custa: forçar a ordem de chegada significa acordar a próxima da fila mesmo quando seria mais rápido deixar a thread atual pegar de novo, o que derruba o número total de aquisições por segundo. Justiça se compra com throughput, e a API padrão da Pthreads nem oferece essa opção diretamente, sinal de que o padrão da indústria é abrir mão da justiça por velocidade.¹

Na maioria dos programas essa escolha é acertada, porque nenhuma thread realmente depende de pegar o lock dentro de uma janela de tempo específica: 96 mil aquisições de atraso, num loop que faz 23 milhões, somem no ruído. O barging vira problema de verdade quando alguma thread tem um prazo a cumprir, um pedido de rede pra responder, um quadro de vídeo pra renderizar, e é justamente aí, quando o pior caso importa mais que a média, que a starvation deixa de ser curiosidade e vira bug.

1. Linguagens de mais alto nível costumam expor a escolha. Na JVM, por exemplo, ReentrantLock(true) pede explicitamente a política justa, enquanto o lock padrão não promete nada sobre ordem de chegada. ↩