Deadlock

O jeito mais fácil de travar um programa com locks é fazer duas threads esperarem uma pela outra. O Código 8-1 tem dois mutexes, A e B. A thread 1 pega A e depois quer B. A thread 2 pega B e depois quer A.

#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 *thread1(void *arg) {
    pthread_mutex_lock(&lock_a);
    printf("thread 1: peguei A, quero B\n");
    usleep(100000);                    // dá tempo da thread 2 pegar B
    pthread_mutex_lock(&lock_b);
    printf("thread 1: peguei A e B\n");
    pthread_mutex_unlock(&lock_b);
    pthread_mutex_unlock(&lock_a);
    return NULL;
}

void *thread2(void *arg) {
    pthread_mutex_lock(&lock_b);
    printf("thread 2: peguei B, quero A\n");
    usleep(100000);
    pthread_mutex_lock(&lock_a);
    printf("thread 2: peguei B e A\n");
    pthread_mutex_unlock(&lock_a);
    pthread_mutex_unlock(&lock_b);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, thread1, NULL);
    pthread_create(&t2, NULL, thread2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("terminou\n");
}

O usleep está ali só pra tornar o problema confiável: sem ele, uma thread poderia pegar os dois locks antes da outra começar, e o programa terminaria normal às vezes. Com o usleep, garantimos que cada thread pega o primeiro lock e segura enquanto a outra pega o dela. Rodando:

$ cc main.c -o main -pthread
$ ./main
thread 1: peguei A, quero B
thread 2: peguei B, quero A
^C
$

As duas primeiras linhas aparecem, e depois nada. O programa fica pendurado até você matar ele no ^C. A thread 1 está segurando A e bloqueada esperando B. A thread 2 está segurando B e bloqueada esperando A. Cada uma espera um lock que a outra nunca vai soltar, porque a outra também está bloqueada. Isso é um deadlock (ou “abraço mortal”): um conjunto de threads em que cada uma espera por um recurso segurado por outra do mesmo conjunto, num ciclo.

Repare que esse travamento é diferente do mutex esquecido sem unlock: lá, uma thread bloqueava porque o lock nunca era liberado, um problema de código faltando. Aqui, todo unlock está no lugar certo, cada thread está perfeitamente correta olhada isoladamente, e mesmo assim o conjunto trava. O deadlock é uma propriedade da interação entre as threads, não de um bug local que dá pra apontar numa linha.

As quatro condições de Coffman

Um deadlock só acontece quando quatro condições valem ao mesmo tempo. Elas são conhecidas como as condições de Coffman, e são úteis porque quebrar qualquer uma delas já basta pra tornar o deadlock impossível.

1. Exclusão mútua: os recursos em disputa só podem ser usados por uma thread por vez. Se pudessem ser compartilhados, ninguém precisaria esperar. É a razão de existir do lock, então essa raramente é a condição que se ataca.
2. Segurar e esperar (hold and wait): uma thread segura um recurso enquanto espera por outro. No exemplo, a thread 1 segura A e espera B.
3. Não-preempção: um recurso só é liberado voluntariamente pela thread que o segura. Ninguém pode arrancar A da thread 1 à força.
4. Espera circular: existe um ciclo de threads em que cada uma espera por um recurso segurado pela próxima. A thread 1 espera a 2, que espera a 1.

As quatro juntas produzem o travamento. Tire uma, e não tem deadlock.

Quebrando a espera circular: ordem global de locks

A condição mais prática de atacar é a espera circular, e a forma clássica de fazer isso é impor uma ordem global na aquisição de locks: todas as threads sempre adquirem os locks na mesma ordem. Se todo mundo pega A antes de B, nunca vai existir uma thread segurando B e esperando A, e o ciclo é impossível.

A correção no exemplo é mínima: basta a thread 2 pegar A antes de B, igual à thread 1.

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

pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER;

void *thread1(void *arg) {
    pthread_mutex_lock(&lock_a);
    pthread_mutex_lock(&lock_b);
    printf("thread 1: peguei A e B\n");
    pthread_mutex_unlock(&lock_b);
    pthread_mutex_unlock(&lock_a);
    return NULL;
}

void *thread2(void *arg) {
    pthread_mutex_lock(&lock_a);        // mesma ordem da thread 1: A, depois B
    pthread_mutex_lock(&lock_b);
    printf("thread 2: peguei A e B\n");
    pthread_mutex_unlock(&lock_b);
    pthread_mutex_unlock(&lock_a);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, thread1, NULL);
    pthread_create(&t2, NULL, thread2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("terminou\n");
}

$ cc main.c -o main -pthread
$ ./main
thread 1: peguei A e B
thread 2: peguei A e B
terminou
$ ./main
thread 2: peguei A e B
thread 1: peguei A e B
terminou

terminou, toda vez. A ordem entre as threads ainda varia (às vezes a 2 imprime antes da 1), mas o ciclo nunca se forma: quem chega primeiro pega A, e a outra espera A sem segurar B. Quando a primeira libera tudo, a segunda pega os dois e segue.

Em programas reais, com dezenas de locks, manter uma ordem global consistente vira uma disciplina de engenharia. Uma convenção comum é ordenar os locks pelo endereço de memória deles: antes de pegar dois locks, compare os ponteiros e sempre adquira o de menor endereço primeiro. Assim, mesmo funções escritas por pessoas diferentes, sem combinarem nada, acabam concordando na ordem.