Livelock

Duas pessoas se cruzam num corredor estreito. Uma vai pela direita, a outra também, e elas se bloqueiam. As duas, educadas, pedem desculpa e mudam de lado ao mesmo tempo, e se bloqueiam de novo. Mudam de novo, juntas, e de novo se bloqueiam. Se as duas seguirem a mesma regra de cortesia em perfeita sincronia, elas dançam de um lado pro outro no corredor pra sempre, sem nunca passar.

Isso é um livelock. Como no deadlock, ninguém progride. Diferente do deadlock, ninguém está bloqueado: as threads estão ativas, executando o tempo todo, reagindo umas às outras. Elas só não conseguem chegar a lugar nenhum, porque cada reação de uma provoca uma reação simétrica na outra que desfaz o avanço.

De onde o livelock aparece

Livelock costuma surgir de uma tentativa de evitar deadlock. Lembre que o deadlock do início do capítulo vinha de “segurar e esperar”: a thread pegava um lock e ficava bloqueada segurando ele. Uma ideia natural pra quebrar isso é não ficar bloqueado: em vez de pthread_mutex_lock, que dorme até conseguir, usar pthread_mutex_trylock, que tenta pegar o lock e retorna na hora dizendo se conseguiu ou não. Se não conseguiu o segundo lock, a thread solta o primeiro e tenta tudo de novo, em vez de ficar segurando e esperando.

O Código 8-4 faz exatamente isso, na mesma situação AB/BA do deadlock: a thread 0 quer A e depois B, a thread 1 quer B e depois A. Só que agora, quando falha em pegar o segundo lock, cada uma solta o primeiro e recomeça. Um contador registra quantas tentativas cada thread precisou até levar os dois locks:

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

pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER;

void *pessoa(void *arg) {
    int eu = *(int *)arg;
    pthread_mutex_t *primeiro = eu == 0 ? &lock_a : &lock_b;
    pthread_mutex_t *segundo  = eu == 0 ? &lock_b : &lock_a;

    int tentativas = 0;
    for (;;) {
        tentativas++;
        pthread_mutex_lock(primeiro);
        usleep(1000);                          // dá tempo da outra pegar o dela
        if (pthread_mutex_trylock(segundo) != 0) {
            pthread_mutex_unlock(primeiro);    // solta e desiste dessa tentativa
            continue;                          // tenta tudo de novo
        }
        break;                                 // pegou os dois
    }
    printf("thread %d: peguei os dois locks depois de %d tentativas\n", eu, tentativas);
    pthread_mutex_unlock(segundo);
    pthread_mutex_unlock(primeiro);
    return NULL;
}

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

O usleep entre pegar o primeiro lock e tentar o segundo cumpre o mesmo papel que cumpria no deadlock: alarga a janela pra que as duas threads de fato colidam, em vez de uma pegar tudo antes da outra começar. Rodando:

$ cc main.c -o main -pthread
$ ./main
thread 0: peguei os dois locks depois de 3055 tentativas
thread 1: peguei os dois locks depois de 3071 tentativas
$ ./main
thread 1: peguei os dois locks depois de 744 tentativas
thread 0: peguei os dois locks depois de 750 tentativas
$ ./main
thread 0: peguei os dois locks depois de 139 tentativas
thread 1: peguei os dois locks depois de 139 tentativas

Repare em duas coisas. Primeiro, os dois números de cada execução são quase iguais, 3055 e 3071, ou 744 e 750: as threads recuaram e tentaram de novo em lockstep, milhares de vezes, cada colisão de uma casada com uma colisão da outra. É o corredor acontecendo de verdade. Segundo, o número varia enormemente de uma execução pra outra, de pouco mais de cem a alguns milhares. O programa passou perto de girar pra sempre, e escapou por sorte.

Por que ele quase nunca gira pra sempre

O que quebra o ciclo é o jitter do escalonador. Pra o livelock durar, as duas threads teriam que colidir, recuar e retomar em simetria perfeita, indefinidamente. Na prática o sistema operacional nunca mantém essa simetria por muito tempo: uma das threads sofre um atraso mínimo, uma interrupção, uma migração de core, uma fatia de tempo um pouco maior, e nesse instante ela pega o segundo lock antes da outra reagir. A dança acaba. É por isso que o contador sempre para em algum momento, e é por isso que livelock é bem mais raro que deadlock na prática: o deadlock, uma vez formado, é estável e definitivo, enquanto o livelock precisa de uma coincidência contínua que o mundo real desfaz. Se as duas threads acertassem o passo com precisão absoluta, esse contador nunca pararia de subir.

Essa é também a diferença de fundo entre os dois travamentos. No deadlock, as threads estão dormindo, bloqueadas dentro de pthread_mutex_lock, sem consumir ciclo de CPU nenhum enquanto esperam. No livelock elas estão o oposto de dormindo: rodando a plena carga, pegando lock, soltando, tentando de novo, queimando CPU o tempo todo pra não sair do lugar. Do lado de fora um programa em deadlock e um em livelock podem parecer igualmente pendurados. Por dentro, um está inerte e o outro está a mil por hora.

Quebrando a simetria

Se o livelock vive de simetria, a cura é introduzir assimetria de propósito. A técnica padrão é o backoff aleatório: quando uma thread desiste e vai tentar de novo, ela espera um tempo aleatório antes da próxima tentativa, em vez de recomeçar imediatamente. Basta uma linha a mais no loop anterior:

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

pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER;

void *pessoa(void *arg) {
    int eu = *(int *)arg;
    pthread_mutex_t *primeiro = eu == 0 ? &lock_a : &lock_b;
    pthread_mutex_t *segundo  = eu == 0 ? &lock_b : &lock_a;
    unsigned int semente = eu + 1;             // semente local a cada thread

    int tentativas = 0;
    for (;;) {
        tentativas++;
        pthread_mutex_lock(primeiro);
        usleep(1000);
        if (pthread_mutex_trylock(segundo) != 0) {
            pthread_mutex_unlock(primeiro);
            usleep(rand_r(&semente) % 1000);   // espera um tempo aleatório
            continue;
        }
        break;
    }
    printf("thread %d: peguei os dois locks depois de %d tentativas\n", eu, tentativas);
    pthread_mutex_unlock(segundo);
    pthread_mutex_unlock(primeiro);
    return NULL;
}

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

$ cc main.c -o main -pthread
$ ./main
thread 1: peguei os dois locks depois de 1 tentativas
thread 0: peguei os dois locks depois de 2 tentativas
$ ./main
thread 0: peguei os dois locks depois de 1 tentativas
thread 1: peguei os dois locks depois de 2 tentativas

Os milhares de tentativas viraram uma ou duas. Com esperas de durações diferentes, é quase impossível que as duas threads voltem a colidir exatamente no mesmo instante várias vezes seguidas: uma acaba tentando enquanto a outra ainda está esperando, pega os dois locks, e segue.

Usamos rand_r, com uma semente local a cada thread, em vez de rand(): o rand() comum guarda estado global e não é seguro pra chamar de várias threads ao mesmo tempo, o que seria mais um acesso compartilhado sem proteção.

É a mesma ideia que redes usam pra lidar com colisões: quando dois transmissores falam junto e se atrapalham, cada um espera um intervalo aleatório antes de tentar de novo, e a aleatoriedade desempata. A ironia é que a mesma imprevisibilidade do escalonador que torna o livelock tão difícil de sustentar é o que uma solução deliberada reintroduz de propósito pra escapar dele.