Threads, condições de corrida e travas

Uma thread é uma sequência de execução dentro de um processo. Várias threads podem trabalhar nos mesmos dados do programa, mas cada uma precisa de sua própria posição no código e de suas próprias chamadas de função ainda não concluídas.

O que é compartilhado e o que pertence a uma thread

Threads de um processo compartilham código, variáveis globais e estáticas, objetos da área de alocação dinâmica, descritores de arquivos abertos e o identificador de processo. Cada thread tem seu próprio contador de programa, registradores, pilha e identificador de thread. Uma variável global int total representa um objeto compartilhado. Uma variável local comum int i na função trabalhadora representa um objeto diferente em cada chamada.

Um processo com três threads tem três pilhas em endereços diferentes no mesmo espaço de endereçamento. Uma pilha não é um compartimento protegido: outra thread pode acessar uma variável local se receber seu endereço. Esse compartilhamento só é válido enquanto a variável existir. Um ponteiro para um quadro de pilha de uma função já encerrada não pode manter a variável ativa. Arrays locais grandes e recursão profunda também podem esgotar a pilha de uma thread.

Troca entre threads

O sistema operacional salva o estado de execução de cada thread em um bloco de controle de thread, ou TCB. Quando troca de T1 para T2, ele salva os registradores de T1 e restaura os de T2. O cálculo inacabado de T1 permanece em seus registradores salvos até que ela execute novamente.

Para threads do mesmo processo, o espaço de endereçamento permanece igual durante a troca. As tabelas de páginas não precisam mudar, o que geralmente torna essa troca menos custosa que uma troca entre processos. Memória compartilhada também significa falhas compartilhadas: uma escrita por ponteiro inválido pode danificar dados de outra thread, e uma falha que encerra o processo encerra todas as threads.

Por que usar várias threads?

Paralelismo significa executar no mesmo instante em diferentes núcleos de CPU. Quatro partes independentes de um cálculo podem alcançar uma aceleração próxima de quatro vezes em quatro núcleos, se o trabalho compartilhado e a coordenação não se tornarem gargalos. As threads também permitem que um programa sobreponha espera e trabalho: enquanto uma espera por uma leitura de disco ou resposta da rede, outra pode usar a CPU.

Concorrência significa que execuções progridem durante períodos sobrepostos. Em um núcleo, o escalonador alterna entre threads, portanto elas são concorrentes sem executar em paralelo. Um único núcleo ainda permite erros de concorrência: uma troca pode interromper uma atualização compartilhada entre suas instruções de máquina.

Quem escalona as threads?

Linux e Windows usam um modelo um para um: cada thread comum de aplicação corresponde a uma thread escalonada pelo núcleo. Threads diferentes podem executar em núcleos diferentes, e uma chamada bloqueante bloqueia a thread que a chamou. Uma biblioteca muitos para um escalona várias threads de usuário em uma thread do núcleo. Suas trocas podem ser baratas, mas ela não pode executar essas threads em vários núcleos, e uma chamada de sistema bloqueante pode interromper todo o grupo.

Criar A antes de B não garante que A execute primeiro. Se A imprime “A” e B imprime “B”, pode aparecer “AB” ou “BA”. A ordem de criação determina quando uma thread fica disponível para executar; o escalonador escolhe seu momento de execução.

A interface de threads POSIX, ou pthreads, inicia uma função C em outra thread. Inclua <pthread.h> e compile com um comando como gcc -pthread -o sum sum.c. A opção -pthread fornece as configurações de compilador e vinculador para código com threads.

Crie uma thread com argumentos estáveis

A chamada pthread_create(&t, NULL, worker, arg) armazena um identificador de thread em t e inicia worker(arg). O ponteiro de atributos NULL solicita os padrões. Uma função trabalhadora tem a assinatura void *worker(void *arg): o argumento e o valor de retorno são ponteiros. Uma struct permite que esse único ponteiro transporte vários campos.

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

struct range { int lo, hi; long result; };

void *sum_range(void *arg) {
    struct range *r = arg;
    long sum = 0;
    for (int n = r->lo; n <= r->hi; n++)
        sum += n;
    r->result = sum;
    return NULL;
}

A thread criadora prepara duas structs, {1, 50, 0} e {51, 100, 0}, e passa um endereço diferente a cada trabalhadora. Mantenha ambas as structs válidas até que as trabalhadoras terminem. Cada trabalhadora acumula em sua própria variável local sum e escreve apenas em seu próprio campo result.

pthread_create retorna 0 em caso de sucesso e um número de erro em caso de falha. Verifique diretamente o número retornado; a função não define errno para informar a falha. Somente uma criação bem-sucedida fornece uma thread cujo término pode ser aguardado.

Aguarde o término antes de ler os resultados

Depois de criar ambas as trabalhadoras com sucesso, a thread principal chama pthread_join(t[0], NULL) e pthread_join(t[1], NULL). Uma chamada de join bloqueia até que a thread indicada termine. A conclusão bem-sucedida dessa espera também torna as escritas da trabalhadora visíveis para a thread que aguardou. A thread principal pode então ler 1.275 e 3.775 e somá-los para obter 5.050 sem um mutex: as trabalhadoras escreveram em objetos separados, e a thread principal esperou antes de lê-los.

Iniciar ambas as threads antes de aguardar seu término permite que seus trabalhos se sobreponham. Criar uma trabalhadora e aguardar imediatamente seu término antes de criar a próxima faz com que elas executem uma após a outra.

Veja o código principal. Ele encerra o programa em caso de erro de pthread, portanto nunca usa um identificador de uma criação malsucedida:

static void require_success(int rc) {
    if (rc != 0) {
        fprintf(stderr, "pthread error: %d\n", rc);
        exit(EXIT_FAILURE);
    }
}

int main(void) {
    struct range jobs[2] = {{1, 50, 0}, {51, 100, 0}};
    pthread_t threads[2];
    for (int i = 0; i < 2; i++)
        require_success(pthread_create(&threads[i], NULL,
                                      sum_range, &jobs[i]));
    for (int i = 0; i < 2; i++)
        require_success(pthread_join(threads[i], NULL));
    printf("%ld\n", jobs[0].result + jobs[1].result);
    return 0;
}

Para coletar um ponteiro retornado, passe o endereço que o receberá: void *answer; pthread_join(t, &answer);. O ponteiro deve referir-se a uma área de armazenamento que continue válida após o término da trabalhadora, como memória alocada na área de alocação dinâmica ou uma struct da thread criadora. Retornar &local_result da trabalhadora é inválido porque sua variável local deixa de existir quando a função retorna.

Evite compartilhar uma variável de laço que muda

Passar &i a cada trabalhadora em um laço de criação passa repetidamente um único endereço. As trabalhadoras podem lê-lo depois que o laço o tiver alterado, portanto várias podem receber o mesmo identificador aparente. Use um array: atribua ids[i] = i, passe &ids[i] e mantenha o array válido e inalterado até que todas as esperas terminem.

Encerre threads e processos de forma intencional

Retornar de main ou chamar exit() em qualquer thread encerra todo o processo e pode interromper as trabalhadoras. A thread principal normalmente aguarda o término das trabalhadoras antes de retornar. Chamar pthread_exit() encerra apenas a thread que o chamou; outras threads podem continuar.

Uma thread destacada libera seus recursos automaticamente quando termina e não permite que se aguarde seu término com join. Garanta que o término de cada thread que permite join seja aguardado uma vez ou que ela seja destacada. A espera por término aguarda a conclusão; ela não protege duas trabalhadoras que atualizam o mesmo objeto enquanto ambas executam.

A instrução counter++ parece pequena, mas um incremento comum de inteiro compartilhado não é uma operação indivisível. Ele normalmente carrega um valor, soma em um registrador e armazena o resultado. Outra thread pode executar entre essas etapas.

Um acompanhamento que perde um incremento

Comece com counter igual a 50. Trate carregamento, soma e armazenamento como etapas de máquina separadas:

Dois incrementos deveriam ter produzido 52. Em vez disso, T1 sobrescreve o resultado de T2 com um valor calculado a partir do antigo 50. Essa é uma atualização perdida.

Uma troca de contexto preserva os registradores de T1 em seu TCB. Quando T1 retoma, seu registrador ainda contém 51; ela não recarrega o contador compartilhado só porque T2 executou. O erro está na sequência sem proteção, não na restauração de um registrador incorreto pelo escalonador.

Compare com uma execução serial

Se T1 concluir as três etapas antes que T2 carregue, T1 armazena 51 e T2 depois armazena 52. Inverter a ordem das threads inteiras também resulta em 52. O resultado intercalado 51 não pode surgir de nenhuma das duas ordens seriais. Para encontrar esse tipo de falha, marque uma leitura, coloque depois dela uma escrita de outra thread e retome o cálculo da primeira thread com o valor desatualizado.

Esse acompanhamento é um modelo do erro no nível de máquina. Em C real, acessos conflitantes sem sincronização a um inteiro compartilhado comum formam uma corrida de dados, que causa comportamento indefinido. C não limita esse programa aos resultados de um modelo simples de intercalação de instruções.

Por que passar nos testes é uma evidência fraca

Duas threads que fazem 10.000.000 de incrementos cada deveriam produzir 20.000.000. Execuções experimentais sem proteção podem imprimir totais menores e diferentes, como 19.345.221 e 19.221.041 em exemplos publicados. Uma execução com resultado aparentemente correto significa apenas que o resultado observado por acaso foi aceitável.

A janela vulnerável pode ter apenas algumas instruções. Quantidades diferentes de núcleos, escolhas do compilador ou carga do sistema podem expor um escalonamento que milhares de execuções anteriores não mostraram. Para duas threads que fazem cada uma um incremento modelado a partir de zero, o modelo de acompanhamento permite 1 ou 2. Com pelo menos dois incrementos por thread, escalonamentos raros podem deixar um total tão baixo quanto 2, mesmo quando o número de incrementos pretendidos aumenta.

Corrija a operação, não sua aparência

Declarar o inteiro como volatile não torna seu carregamento, soma e armazenamento indivisíveis e não sincroniza threads. Escrever todo o trabalho em uma linha não muda nada. Mesmo uma instrução x86 que soma diretamente na memória precisa da forma atômica adequada para coordenar os núcleos.

Proteja toda a sequência de leitura, modificação e escrita com um mutex compartilhado ou use uma operação atômica de leitura, modificação e escrita de C11, como atomic_fetch_add. A mesma necessidade existe em um núcleo: uma troca provocada pelo temporizador pode separar o carregamento do armazenamento mesmo sem execução paralela.

Um erro de concorrência pode envolver um acesso à memória ou uma regra de negócio inteira. Identifique tanto os objetos compartilhados quanto a operação que deve parecer indivisível para outras threads.

Condição de corrida ou corrida de dados?

Uma condição de corrida ocorre quando a correção depende da temporização relativa. Uma corrida de dados ocorre quando threads diferentes acessam o mesmo local de memória sem sincronização, pelo menos uma escreve nele e pelo menos um acesso não é atômico. C11 e C++11 atribuem comportamento indefinido a uma corrida de dados.

Acessos atômicos podem evitar uma corrida de dados enquanto uma operação maior ainda tem uma condição de corrida. Por exemplo, leituras e escritas protegidas individualmente não mantêm válida uma decisão entre elas. Duas threads podem ler um saldo suficiente, liberar a trava e depois sacar usando essa decisão desatualizada.

Acompanhe um saque

Um saldo começa em 100. Duas threads solicitam 80 cada uma. A regra é aceitar um saque somente quando o saldo o cobre.

1. T1 verifica 100 e decide que seu saque pode ser realizado.
2. T2 também verifica 100 e toma a mesma decisão.
3. T1 subtrai 80, deixando 20.
4. T2 age com base em sua decisão anterior e subtrai 80 de 20, deixando −60.

Proteger apenas a subtração não corrige essa sequência. Proteja a verificação e a subtração com a mesma trava, mantida continuamente. Assim, uma thread deixa 20, e a seguinte verifica 20 e recusa o saque. Outro escalonamento sem proteção pode perder uma subtração e deixar 20 depois que ambos os saques forem pagos, o que também está errado.

Encontre a seção crítica

Uma seção crítica é a região de dados compartilhados que deve excluir acessos concorrentes. Uma sequência de leitura, modificação e escrita primeiro lê dados, calcula um novo valor e o escreve de volta. Uma sequência de verificação seguida de ação decide se uma ação é permitida e depois a executa. Operações em listas, inicialização tardia e criação de arquivos também podem conter esses padrões.

Uma trava fornece exclusão mútua: no máximo uma thread participante está dentro da região protegida por vez. Uma operação atômica aparece às outras threads participantes como uma operação completa; elas não podem observar um estado parcialmente concluído. Um mutex fornece essa visão apenas para código que segue o mesmo acordo de uso da trava.

Nem todo objeto precisa de uma trava. Dados acessados por uma thread permanecem privados, a menos que seu endereço seja compartilhado. Dados totalmente inicializados antes do início das trabalhadoras e apenas lidos depois podem ser compartilhados sem trava. Avalie quem pode acessar um objeto e se escritas se sobrepõem ao seu uso, não apenas onde ele foi declarado.

O que uma solução correta promete

• Exclusão mútua: threads concorrentes não podem entrar juntas.
• Progresso: quando a seção está livre e threads querem entrar, a escolha de quem entra não pode ser adiada indefinidamente por threads que não estão tentando entrar.
• Espera limitada: após uma solicitação, há um limite para quantas entradas concorrentes podem precedê-la.

atomic_fetch_add(&count, 1) de C11 faz uma atualização atômica em um atomic_int. A atomicidade é garantida mesmo em uma plataforma que implementa a operação com uma trava interna da biblioteca. Tornar dois campos de contas individualmente atômicos ainda não transforma uma transferência entre eles em uma transação atômica; a relação entre os campos também precisa de proteção.

Um mutex é uma trava que permite que uma thread por vez seja proprietária de uma região protegida. Uma thread o adquire antes de acessar os dados protegidos e o libera depois. Se outra thread o detiver, uma chamada bloqueante de aquisição espera.

Inicialize o mutex compartilhado

Use pthread_mutex_t de <pthread.h>. Um mutex estático pode começar com pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;. Um objeto criado dinamicamente pode inicializar seu campo com pthread_mutex_init(&obj->lock, NULL). A inicialização deve terminar antes que qualquer thread use o mutex.

Veja uma operação de contador que usa um mutex compartilhado inicializado estaticamente. A função auxiliar verifica os valores retornados por pthread, que são diretamente os números de erro:

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

static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static long counter = 0;  // guarded by m

static void check(int rc) {
    if (rc != 0) {
        fprintf(stderr, "pthread error: %d\n", rc);
        exit(EXIT_FAILURE);
    }
}

void increment(void) {
    check(pthread_mutex_lock(&m));
    counter = counter + 1;
    check(pthread_mutex_unlock(&m));
}

Toda leitura ou atualização concorrente de counter deve seguir essa mesma regra. Uma função separada que use outro mutex não se coordenaria com increment.

O que acontece enquanto o mutex é mantido?

T1 adquire m, carrega o contador, calcula e armazena. Se T2 chamar pthread_mutex_lock(&m) durante esse intervalo, ela não poderá passar da chamada até adquirir a posse após a liberação por T1. T1 ainda pode sofrer preempção: um mutex impede a entrada concorrente, não as trocas de contexto.

Para a regra do saldo, adquira o mutex antes de avaliar balance >= amount. Subtraia apenas se a verificação for satisfeita, registre o sucesso ou a falha e depois libere o mutex. Um saldo de 100 com duas solicitações de 80 permite exatamente um sucesso e deixa 20.

Escolha como esperar

pthread_mutex_trylock(&m) retorna imediatamente: 0 significa que quem chamou adquiriu o mutex; EBUSY significa que não o adquiriu porque o mutex estava ocupado. No caso de mutex ocupado, a thread pode fazer outro trabalho e não deve acessar os dados protegidos. pthread_mutex_timedlock espera até um prazo absoluto. Essas interfaces ainda exigem a verificação dos códigos de retorno e a liberação de uma trava somente após uma aquisição bem-sucedida.

Respeite a posse e o tempo de vida

A thread proprietária libera um mutex. Um mutex normal, não recursivo, bloqueia se sua proprietária tentar adquiri-lo novamente. Um mutex com verificação de erros informa erros como uma nova aquisição com EDEADLK ou uma liberação por quem não é proprietária com EPERM. Um mutex recursivo conta as aquisições repetidas por sua proprietária e exige o mesmo número de liberações. Não dependa de um mutex padrão para diagnosticar uso incorreto: seu comportamento depende do tipo ao qual a implementação o associa e da operação.

Quando todas as threads tiverem deixado de usar o mutex e ele estiver livre, chame pthread_mutex_destroy. Destruir ou liberar um objeto enquanto outra thread ainda pode adquirir sua trava viola o tempo de vida do mutex. Passar o mutex por ponteiro preserva sua identidade; copiá-lo não cria outro identificador válido para a mesma trava.

A granularidade das travas é a quantidade de estado compartilhado protegida por uma trava. Ela determina quais operações devem esperar umas pelas outras, mesmo quando executam em núcleos diferentes.

Uma trava grande ou várias travas menores?

Um projeto de granularidade grossa coloca um mutex em torno de uma estrutura ou subsistema inteiro. Ele tem uma regra de proteção simples, mas operações não relacionadas são serializadas. Um projeto de granularidade fina atribui mutexes separados a contas, baldes ou regiões distintas. Assim, threads podem trabalhar em regiões diferentes ao mesmo tempo, ao custo de mais operações de trava e regras mais complexas.

Coloque a trava ao lado do estado que ela protege:

struct account {
    pthread_mutex_t lock;
    long balance;
    unsigned id;
};

Uma operação sobre uma conta adquire seu mutex. Uma transferência entre duas contas distintas precisa de ambos, pois altera a relação entre elas. Escolha uma ordem fixa, como a ordem crescente dos identificadores das contas, e use-a em todos os caminhos. Caso contrário, uma thread pode deter A e esperar por B enquanto outra detém B e espera por A.

Uma trava estabelece um limite para a vazão

Suponha que cada operação detenha uma única trava global por 2 µs. O trabalho protegido pode concluir no máximo uma operação a cada 2 µs:

Adicionar núcleos não permite que duas operações detenham o mesmo mutex simultaneamente. A sobrecarga da trava e outros trabalhos podem reduzir ainda mais a taxa alcançada. Portanto, calcular a duração do trecho protegido fornece um limite útil antes de esperar uma aceleração.

Encurte a seção sem comprometer a operação

Prepare o trabalho privado antes de adquirir o mutex. Para inserir em uma lista, primeiro aloque o novo nó e preencha sua chave. Adquira o mutex da lista apenas para ler a cabeça atual e ligar o nó. Assim, uma falha de alocação ocorre sem que a trava esteja adquirida.

Entrada e saída lenta, impressão ou uma função de callback desconhecida podem deixar todas as threads em espera paradas. Mova esse trabalho para fora quando os dados puderem permanecer válidos fora da seção. Mantenha uma decisão e sua atualização dependente juntas: encurtar um saque liberando a trava entre a verificação do saldo e a subtração compromete a correção.

Avalie três propriedades diferentes

A exclusão mútua diz respeito a se o projeto realmente impede a entrada conflitante. A justiça diz respeito a se uma thread em espera acaba tendo sua vez ou pode sofrer inanição. O desempenho diz respeito ao custo da trava com uma thread, várias threads em uma CPU e threads em várias CPUs. Uma trava pode ser correta e ainda assim ser injusta ou lenta.

A contenção ocorre quando threads disputam uma trava já adquirida. Sob contenção intensa, elas também transferem linhas de cache compartilhadas da trava e dos dados entre núcleos. Um experimento publicado com contador levou cerca de 0,03 s para um milhão de atualizações por uma thread, mas mais de 5 s para duas threads fazendo um milhão cada; essas são medições daquela configuração, não tempos universais.

Em um experimento de escalabilidade, mantenha fixo o trabalho de cada thread. A escalabilidade ideal permite que N threads em N núcleos façam N vezes o trabalho no tempo original. Comece com uma estrutura simples e correta, meça a espera e o tempo total e divida uma trava apenas onde a concorrência adicional compensa sua sobrecarga.

Um mutex pode ser implementado perfeitamente e, ainda assim, um programa pode usá-lo de forma incorreta. Revise todo o caminho de uma função, incluindo leituras, erros, funções de callback e destruição de objetos.

Libere a posse em todas as saídas

Esta função deixa a trava adquirida em seu caminho de falha:

pthread_mutex_lock(&m);
if (failed) return -1;
update_shared_state();
pthread_mutex_unlock(&m);

A thread que retorna pode terminar, mas o mutex permanece adquirido. Uma chamada posterior espera por uma liberação que nunca ocorrerá. Use um único caminho de liberação de recursos ou coloque uma liberação antes de cada retorno. Com chamadas pthread verificadas, a estrutura pode ser:

int rc = -1;
check(pthread_mutex_lock(&m));
if (!failed) {
    update_shared_state();
    rc = 0;
}
check(pthread_mutex_unlock(&m));
return rc;

Revisar um ponto de liberação é mais fácil do que revisar vários pontos espalhados. A propriedade importante é que toda trava adquirida com sucesso seja liberada em cada saída normal.

Siga a regra de proteção também nas leituras

Uma função de estado que “apenas lê” pode entrar em condição de corrida com uma atualização. Ela também pode observar campos relacionados em etapas diferentes de uma atualização. Se uma operação de lista publicar um nó antes de preencher seus campos, um leitor sem proteção poderá seguir um ponteiro para dados incompletos. Adquira a trava documentada para cada acesso cuja correção dependa dela.

Usar mutexes diferentes para o mesmo objeto não ajuda. Se T1 adquire lockA e T2 adquire lockB, ambas as aquisições podem ter sucesso. Um mutex declarado como uma nova variável local dentro de cada função trabalhadora torna esse erro fácil de passar despercebido: cada thread adquire seu próprio objeto, portanto não há exclusão compartilhada.

Preserve a identidade e os limites da operação

Um pthread_mutex_t não pode ser copiado por atribuição ou pela cópia da struct que o contém e depois usado como um segundo identificador de mutex. Usar a cópia é comportamento indefinido. Passe um ponteiro para o mutex compartilhado original.

Verifique também onde ocorrem as liberações. Uma função que adquire a trava para verificar um saldo, libera-a e depois a adquire novamente para subtrair protege os acessos individuais, mas deixa a decisão desatualizada. Mantenha toda a sequência de verificação seguida de ação sob posse contínua da trava.

Evite esperar por si mesmo

Chamar código desconhecido enquanto detém um mutex pode reentrar inesperadamente no mesmo objeto protegido. Com um mutex normal, uma segunda chamada de aquisição pela proprietária bloqueia essa proprietária. Um mutex com verificação de erros informa esse erro, enquanto um mutex recursivo permite posse aninhada e precisa de liberações correspondentes. Escolha o tipo conscientemente; não use recursão para ocultar um projeto de proteção pouco claro.

Quando possível, mantenha operações lentas de entrada e saída e suspensões fora de uma seção crítica compartilhada. Antes de destruir o mutex ou liberar o objeto que o contém, garanta que nenhuma thread o detenha ou possa acessá-lo novamente. Inicialização, uso e destruição devem ter uma ordem clara.

Use ferramentas de execução para expor falhas observadas

O ThreadSanitizer, ativado com -fsanitize=thread, e o Helgrind do Valgrind podem relatar corridas de dados e uso incorreto de travas nas execuções que observam. Combine seus relatórios com uma revisão dos acessos compartilhados e das possíveis intercalações. Uma execução sem alertas estabelece que a ferramenta não encontrou problemas naquelas execuções; um caminho não testado ainda precisa ser analisado.

Uma trava precisa de uma maneira confiável de escolher uma proprietária. Uma leitura comum seguida de uma escrita comum deixa uma lacuna nessa decisão, mesmo que o trabalho protegido seja muito curto.

O controle de interrupções tem um papel restrito

Em uma CPU, um núcleo pode desativar brevemente as interrupções em torno de uma seção crítica não bloqueante para impedir ali a preempção causada por interrupções. Isso depende de permanecer na CPU sem bloquear ou trocar voluntariamente. O núcleo usa essa técnica para operações internas curtas.

Isso não é um mutex de uso geral para aplicações. Instruções de controle de interrupções são privilegiadas; permitir seu uso irrestrito por uma aplicação deixaria que ela monopolizasse a CPU. Desativar interrupções em um núcleo não impede que outros núcleos acessem os mesmos dados. Períodos longos com interrupções desativadas também atrasam seu tratamento e podem causar perda de eventos em alguns dispositivos.

Acompanhe a trava com indicador que falha

Considere este pseudocódigo semelhante a C:

while (flag == 1) { }
flag = 1;
// critical section
flag = 0;

Comece com flag em 0. T1 o testa e sai do laço, depois pausa antes da atribuição. T2 testa o mesmo 0, define-o como 1 e entra. T1 retoma, define-o como 1 e também entra. Ambas passaram pelo teste antes que qualquer uma reivindicasse a posse.

Tornar a leitura e a escrita individualmente atômicas eliminaria uma corrida de dados no indicador, mas ainda deixaria duas operações separadas nesse protocolo. A reivindicação de posse precisa de uma operação atômica de leitura, modificação e escrita ou de um algoritmo de sincronização mais completo.

O laço vazio é uma espera ocupada: verificação repetida que consome tempo de CPU. Em uma CPU, uma thread que aguarda ocupadamente após causar a preempção da proprietária não pode fazer com que ela libere a trava mais cedo. Ela precisa, em algum momento, deixar a proprietária executar.

A solução de Peterson para duas threads

O algoritmo de Peterson coordena duas threads com um indicador de interesse por thread e um turno compartilhado. A thread i executa:

flag[i] = 1;
turn = 1 - i;
while (flag[1 - i] == 1 && turn == 1 - i) { }
// critical section
flag[i] = 0;

Ela anuncia interesse, dá prioridade à outra thread em caso de empate e espera apenas enquanto a outra está interessada e tem prioridade. Sob consistência sequencial, as operações de cada thread mantêm a ordem do programa e todas as threads observam uma ordem comum. Nesse modelo, o algoritmo de Peterson fornece exclusão mútua, progresso e espera limitada para duas threads.

A ordem da memória também importa

Processadores e compiladores modernos podem permitir que operações de memória se tornem visíveis em uma ordem diferente da do código-fonte. Um armazenamento pode permanecer em buffer enquanto um carregamento posterior lê a memória. As duas threads podem então ver o indicador de interesse da outra como 0 e ambas entrar. Inteiros compartilhados comuns em C também introduzem corridas de dados em C.

Uma implementação válida precisa de operações atômicas e ordenação adequadas, como operações atômicas de C11 sequencialmente consistentes para os indicadores e o turno. volatile não fornece essa sincronização. Travas práticas combinam uma operação indivisível de posse com garantias de ordenação de memória, para que os acessos protegidos permaneçam do lado correto da aquisição e da liberação.

Uma operação atômica de leitura, modificação e escrita combina a leitura de um local e sua atualização em uma única ação indivisível. Ela elimina a lacuna que permite que duas threads passem juntas por um teste comum de indicador.

Troque o indicador e examine seu valor antigo

Teste e atribuição, ou troca atômica, escreve um novo valor e retorna o antigo. Com um indicador inicialmente em 0, T1 troca seu valor por 1 e recebe 0, portanto entra. T2 troca seu valor por 1 e recebe 1, portanto espera. Até que a liberação escreva 0, nenhuma outra troca pode retornar 0.

Veja uma trava de espera ocupada em C11 que usa as operações atômicas padrão sequencialmente consistentes:

#include <stdatomic.h>

static atomic_flag held = ATOMIC_FLAG_INIT;

void lock(void) {
    while (atomic_flag_test_and_set(&held)) { }
}

void unlock(void) {
    atomic_flag_clear(&held);
}

A ordenação importa tanto quanto o indicador. A aquisição deve manter os acessos posteriores da seção crítica depois da aquisição bem-sucedida; a liberação deve manter os acessos anteriores da seção crítica antes da liberação. Limpar o indicador também deve ser atômico; misturar armazenamentos comuns com acessos atômicos não implementa essa transferência de posse.

Compare antes de substituir

Comparação e troca, ou CAS, altera um valor somente quando ele é igual a um valor esperado. Suponha que duas threads leiam um contador em 7 e cada uma queira somar 1. T2 altera 7 para 8 com sucesso. A tentativa de T1 de alterar 7 para 8 agora falha, portanto T1 tenta novamente a partir de 8 e o altera para 9. A nova tentativa preserva ambos os incrementos.

atomic_compare_exchange_strong de C11 retorna sucesso ou falha e atualiza o argumento esperado em caso de falha. Alguns pseudocódigos no estilo de hardware retornam o valor antigo armazenado. Verifique qual convenção um acompanhamento usa. No x86, xchg com memória implementa a troca, enquanto lock cmpxchg fornece comparação e troca atômica.

Outros componentes de hardware

Leitura vinculada e escrita condicional, ou LL/SC, lê enquanto estabelece uma reserva e depois tenta uma escrita. A escrita condicional falha se outra escrita invalidou a reserva; ela também pode falhar por outros motivos, portanto deve estar em um laço de novas tentativas. LDXR/STXR do ARM e lr/sc do RISC-V oferecem suporte a esse padrão.

Busca e soma soma atomicamente e retorna o valor antigo. C11 a disponibiliza como atomic_fetch_add; o x86 fornece lock xadd. Retornar o valor antigo a torna útil para distribuir números de bilhete únicos.

C garante o comportamento atômico das operações de sua biblioteca atômica. Ela não exige que todo tipo atômico seja livre de travas; algumas operações usam uma trava interna da biblioteca. atomic_flag tem a garantia de ser livre de travas, e atomic_is_lock_free verifica outros objetos.

Ser correta não significa ser justa ou rápida

Uma trava de teste e atribuição fornece exclusão mútua, mas não ordem de chegada: uma thread pode perder repetidamente a disputa após a liberação e sofrer inanição. Em uma CPU, quatro threads com fatias de tempo de 10 ms em escalonamento circular podem desperdiçar 30 ms em espera ocupada por três threads antes que a proprietária que sofreu preempção execute novamente. Em vários núcleos, com a proprietária em execução e seções curtas, uma breve espera ocupada pode evitar a sobrecarga de suspensão e despertar.

Uma trava de teste e atribuição registra se está adquirida, mas não quem está esperando. Uma trava por bilhetes acrescenta uma ordem de chegada usando um distribuidor atômico de bilhetes e um contador de atendimento.

Retire um número e espere sua vez

Ambos os contadores começam em 0. Cada thread que chama a função incrementa ticket atomicamente e mantém seu valor antigo como mine. Ela só entra quando turn é igual a mine. A proprietária libera a trava incrementando turn uma vez.

#include <stdatomic.h>

static atomic_uint ticket = 0;
static atomic_uint turn = 0;

void lock(void) {
    unsigned mine = atomic_fetch_add(&ticket, 1);
    while (atomic_load(&turn) != mine) { }
}

void unlock(void) {
    atomic_fetch_add(&turn, 1);
}

Essas operações atômicas padrão de C11 fornecem tanto atomicidade quanto ordenação sequencialmente consistente. Cada thread mantém mine em sua própria variável local. O contador compartilhado de bilhetes distribui números únicos entre os bilhetes ainda pendentes.

Acompanhe três chegadas

A retira o bilhete 0 e entra porque turn é 0. B retira o bilhete 1 e espera. C retira o bilhete 2 e espera. O próximo bilhete disponível agora é 3, enquanto o turno atual ainda é 0.

Quando A libera a trava, turn passa a 1, portanto B entra. C ainda espera pelo 2. A liberação por B avança turn para 2 e C entra. Uma thread recém-chegada recebe o bilhete 3 e não pode passar à frente de C.

Essa distinção importa ao acompanhar a execução: ticket registra o próximo número a distribuir; turn registra o número em atendimento. Retirar um bilhete altera apenas o distribuidor. A liberação avança o atendimento.

O que a justiça garante

Uma thread espera atrás das threads com bilhetes anteriores. Se cada proprietária acabar por liberar a trava e as threads à frente puderem executar, chegadas posteriores não poderão ultrapassá-la. O número de seções críticas concorrentes à frente é limitado pelos bilhetes anteriores ainda pendentes. Isso fornece espera limitada e impede a inanição nessas condições de progresso.

A garantia diz respeito à ordem de entrada, não ao tempo decorrido. Uma proprietária que fica parada por muito tempo pode fazer todas as chamadas posteriores esperarem muito também. Um número de bilhete não pode obrigar o escalonador a executar sua detentora.

Custos que a ordem dos bilhetes mantém

Todas as threads em espera ainda aguardam ocupadamente. Se a thread cuja vez será a próxima estiver fora de execução, threads posteriores prontas esperam mesmo que nenhuma thread ocupe atualmente a seção crítica. Esse é um custo de escalonamento da ordem estrita.

As threads em espera também leem um único local compartilhado turn. Cada liberação altera a linha de cache que todas observam, produzindo tráfego entre núcleos. Travas de espera ocupada baseadas em filas reduzem esse tráfego permitindo que cada thread observe um local separado; o Linux passou das travas de espera ocupada por bilhetes para projetos baseados em filas.

Contadores de bilhetes reais usam aritmética sem sinal. Verificações de igualdade podem funcionar após o retorno cíclico quando o número de bilhetes pendentes permanece menor que a quantidade de valores possíveis do contador. Reutilizar um número enquanto um bilhete anterior igual ainda está pendente destruiria a unicidade e a exclusão.

Uma trava correta pode desperdiçar a maior parte de uma CPU com espera. A estratégia de espera adequada depende de a proprietária poder executar e de quanto tempo ela deterá a trava.

Ceder a CPU abre mão de uma vez

Uma thread em espera pode chamar yield() após uma tentativa malsucedida de adquirir a posse. Ceder a CPU a move do estado de execução para o estado de pronto, para que o escalonador possa selecionar outra thread. Ela ainda está pronta para executar, portanto pode logo ser selecionada e falhar novamente. Com 100 threads em uma CPU, até 99 threads em espera podem executar e ceder a CPU antes que uma proprietária que sofreu preempção tenha outra vez. Ceder a CPU reduz a espera ocupada, mas não fornece uma ordem justa de entrada.

O bloqueio retira a thread em espera do trabalho pronto para executar

Uma trava que suspende coloca quem não conseguiu adquiri-la em uma fila de espera. A thread não consome CPU enquanto está bloqueada. A liberação desperta uma thread em espera para que ela possa executar novamente. Uma pequena trava interna de espera ocupada pode proteger o indicador e a fila; essa trava é mantida apenas para operações breves de controle.

Separar “decidir suspender” de “suspender de fato” cria o risco de um despertar perdido:

1. Uma thread em espera coloca-se na fila e libera a trava interna.
2. Ela é pausada antes de chamar park().
3. A proprietária libera a trava e chama unpark() para ela.
4. Se esse despertar for descartado, a thread será suspensa depois, sem ninguém para despertá-la.

setpark() do Solaris anuncia a intenção de se suspender. Um unpark intermediário faz então o park posterior retornar imediatamente. O protocolo conecta a decisão ao bloqueio real.

O Linux usa uma comparação e bloqueio atômicos

Um futex combina uma palavra na memória de usuário com suporte do núcleo para espera. futex_wait(addr, expected) bloqueia somente se a palavra ainda for igual ao valor esperado; a verificação e a decisão de bloqueio são atômicas em relação às operações sobre essa palavra de futex. Se uma liberação já a tiver alterado, quem chamou não será suspenso com base na expectativa desatualizada.

futex_wake(addr, n) desperta até n threads em espera. Uma trava sem contenção pode ser adquirida e liberada com instruções atômicas no espaço de usuário, evitando uma chamada de sistema. Os mutexes pthread da glibc do Linux usam futexes para esperas com contenção. Um despertar torna uma thread pronta para executar; seu protocolo de travamento ainda deve estabelecer a posse antes de acessar os dados protegidos.

Aguarde ocupadamente por pouco tempo e depois suspenda

Uma trava de duas fases primeiro aguarda ocupadamente por pouco tempo e depois bloqueia se a espera continuar. A espera ocupada pode compensar quando a proprietária está executando em outro núcleo e a espera prevista é menor que o tempo de suspender e despertar. O bloqueio é preferível para esperas longas ou quando há mais threads prontas para executar do que núcleos. Em uma CPU, uma thread em espera ocupada não pode ajudar uma proprietária fora de execução a terminar.

A prioridade de escalonamento pode impedir o progresso

Na inversão de prioridade, uma thread de alta prioridade espera por um mutex detido por uma thread de baixa prioridade enquanto trabalho de prioridade média mantém a proprietária fora da CPU. Suspender a thread de alta prioridade evita a espera ocupada, mas não elimina esse atraso de escalonamento.

A herança de prioridade eleva temporariamente a prioridade da proprietária à da thread em espera de maior prioridade, permitindo que ela termine e libere a trava. A Mars Pathfinder da NASA sofreu reinicializações devido à inversão de prioridade em 1997; ativar a herança de prioridade do mutex corrigiu o problema. Uma thread de alta prioridade em espera ocupada em uma única CPU com escalonamento estrito por prioridade pode ser pior: ela pode impedir completamente a execução da proprietária de baixa prioridade.

Um contador compartilhado é fácil de proteger com um mutex. Suas operações increment, decrement e get adquirem a mesma trava, executam sua ação e a liberam. Ele é exato, mas todas as atualizações passam por um único ponto compartilhado.

Por que o contador exato se torna um gargalo

Em vários núcleos, um mutex serializa as operações do contador. Os núcleos também transferem a posse das linhas de cache da trava e do contador. Adicionar threads trabalhadoras pode aumentar a espera mais rapidamente do que o trabalho útil. Substituir o mutex por atomic_fetch_add remove a sobrecarga explícita da trava em processadores comuns, mas cada atualização ainda escreve no mesmo local compartilhado.

Um contador aproximado, também chamado de sloppy counter, distribui atualizações por contadores locais e as transfere em lotes para um contador global. Seu valor global informado omite deliberadamente incrementos locais recentes.

Construa a atualização local para global

Mantenha um contador e um mutex por núcleo, um contador global com seu próprio mutex e um limiar S. Para cada incremento:

1. Escolha a posição local para essa atualização e adquira seu mutex.
2. Some 1 à contagem local.
3. Se ela atingir S, adquira o mutex global enquanto ainda detém o local.
4. Some essa contagem local à contagem global, reinicie a contagem local em 0 e libere o mutex global.
5. Libere o mutex local.

Mantenha a posição escolhida estável durante toda a atualização. Threads que usam posições diferentes geralmente acessam travas diferentes e adquirem o mutex global apenas em uma transferência. A leitura da contagem global também segue sua regra de travamento.

Acompanhe uma transferência em lote

Com quatro núcleos e S igual a 5, suponha que seus totais de atualizações sejam 7, 3, 4 e 0. O núcleo 1 transfere 5 em seu quinto incremento e deixa 2 incrementos locais depois. As contagens locais finais são 2, 3, 4 e 0. A contagem global é 5, e o total real é 14: nove incrementos permanecem locais.

Após atualizações concluídas com incrementos unitários, cada contagem local fica entre 0 e S − 1. Com P núcleos, o total global pode ficar defasado em no máximo:

Para quatro núcleos e S igual a 5, o limite é 16. Esse limite diz respeito a atualizações concluídas e suas contagens locais restantes; não o aplique no meio de uma transferência.

Escolha o limiar para a tarefa

Um limiar menor melhora a atualidade do valor, mas exige mais aquisições da trava global. Com S igual a 1, cada incremento é transferido globalmente, acrescentando a sobrecarga da trava local sem evitar o gargalo global. Um limiar maior melhora a escalabilidade das atualizações, mas aumenta a defasagem possível. Em um experimento publicado, S igual a 1024 permitiu que quatro threads fizessem quatro milhões de atualizações em quase o mesmo tempo que uma thread precisou para um milhão.

Um retrato exato do estado deve manter todos os mutexes locais em uma ordem fixa e depois o mutex global antes de somar as contagens. Essa ordem é compatível com as atualizações que adquirem uma trava local antes da trava global. O retrato interrompe transferências concorrentes durante a leitura; ler cada campo separadamente poderia contar uma transferência duas vezes ou não contá-la.

Contadores aproximados servem para estatísticas que toleram visibilidade atrasada. Uma contagem de referências que determina quando a memória pode ser liberada precisa de um método exato: uma contagem subestimada poderia liberar um objeto ainda em uso.

Uma lista encadeada compartilhada precisa preservar tanto suas ligações quanto o tempo de vida de seus nós. Um mutex em torno de cada operação é um primeiro projeto útil porque todo percurso e toda modificação compartilhados seguem uma única regra.

Como duas inserções perdem um nó

Suponha que a lista comece em A. T1 prepara o nó X e T2 prepara o nó Y. Sem uma trava compartilhada, ambas podem ler head == A, atribuir A ao next de seu novo nó e depois armazenar seu próprio nó em head. A atribuição posterior à cabeça oculta o primeiro nó inserido. Esse nó fica inacessível, perdendo-se uma inserção e vazando sua memória.

A sequência protegida deve incluir a leitura da cabeça atual, a definição da nova ligação e a publicação da nova cabeça. Uma trava apenas em torno da atribuição final permitiria que ambas as threads construíssem ligações a partir da mesma cabeça desatualizada.

Prepare dados privados antes de adquirir a trava

Um novo nó permanece privado até ser ligado à lista compartilhada. A alocação e a inicialização da chave podem ocorrer antes da aquisição. Usando a função auxiliar de verificação de pthread apresentada antes, a inserção pode ser escrita assim:

int insert(list_t *list, int key) {
    node_t *node = malloc(sizeof(*node));
    if (node == NULL) return -1;
    node->key = key;

    check(pthread_mutex_lock(&list->lock));
    node->next = list->head;
    list->head = node;
    check(pthread_mutex_unlock(&list->lock));
    return 0;
}

Uma falha de alocação retorna antes que qualquer mutex seja adquirido. A seção compartilhada permanece pequena enquanto a verificação de head e a atualização da ligação permanecem juntas. Uma alocação segura para uso por múltiplas threads não torna a lista em si segura para esse uso; suas ligações ainda precisam de proteção própria.

Leitores participam da mesma regra

Uma busca adquire o mutex da lista antes de ler head e o mantém durante o percurso. Isso a coordena com a inserção e a remoção. Defina uma variável de resultado antes do laço, atualize-a ao encontrar uma correspondência e saia do laço para um único ponto de liberação antes de retornar. Caso contrário, um retorno antecipado após uma busca bem-sucedida dentro do laço protegido precisaria de sua própria liberação.

Nesse projeto, a remoção mantém o mesmo mutex enquanto desliga um nó. Outros percursos não podem estar nesse nó porque também precisam do mutex. Libere-o somente quando nenhuma outra operação ainda puder acessá-lo. Se uma API permitir que quem a chamou mantenha um ponteiro para o nó após liberar a trava, esse uso adicional precisa de seu próprio acordo de tempo de vida; a trava da lista, sozinha, não o cobre mais.

Decida se travas por nó compensam

O travamento por acoplamento adquire a trava do próximo nó antes de liberar a do nó atual. Essa sobreposição preserva um caminho protegido à medida que o percurso avança. Assim, várias operações podem ocupar regiões diferentes da lista.

A concorrência adicional tem um preço: cada nó visitado acrescenta operações de aquisição e liberação de trava, mesmo quando nenhuma outra thread está próxima. Uma carga de trabalho com muitos percursos pode tornar-se mais lenta que a versão com um mutex. Travar grupos de nós é uma solução intermediária. Compare o projeto mais complexo com o simples sob a carga de trabalho real, incluindo buscas malsucedidas e caminhos de remoção.

Um mutex por estrutura é um ponto de partida sensato, mas pode serializar operações que acessam regiões diferentes. Dois refinamentos úteis são uma trava por extremidade da fila e uma trava por balde de tabela de dispersão.

Mantenha um sentinela na cabeça da fila

Uma fila com duas travas começa com um nó sentinela D e head == tail == D. D não contém um item atual da fila. O primeiro item real, se existir, está em head->next. Um mutex da cabeça serializa remoções; um mutex da cauda serializa inserções. Uma inserção e uma remoção podem, portanto, avançar juntas.

A inserção prepara de forma privada o valor de um novo nó e sua ligação nula para o próximo nó. Sob o mutex da cauda, ela publica esse nó pelo campo next da cauda antiga e move tail para o novo nó. A remoção usa o mutex da cabeça para ler a ligação para o próximo nó do sentinela antigo. Se for nula, libera a trava e informa que a fila está vazia. Caso contrário, copia o primeiro valor real, move head para esse nó, libera a trava e libera a memória do sentinela antigo.

O nó que continha o valor retornado torna-se o próximo sentinela. Liberar esse nó imediatamente deixaria head pendente.

Acompanhe a mudança do sentinela

Comece com D. Inserir 5 cria N5 e liga D -> N5, com tail == N5. Inserir 8 adiciona N8, produzindo D -> N5 -> N8. Uma remoção retorna 5, move head para N5 e libera D. N5 agora é o sentinela; apenas 8 permanece como valor na fila. Após outra remoção, N8 torna-se o sentinela e a fila fica vazia.

As duas extremidades ainda compartilham uma ligação

Quando a fila está vazia, uma inserção pode escrever no next do sentinela atual enquanto uma remoção o lê sob outro mutex. Os dois mutexes, sozinhos, não sincronizam esses acessos. Em C11, declare next como um ponteiro atômico e publique-o e carregue-o com ordenação adequada; armazenamentos e carregamentos atômicos padrão sequencialmente consistentes são suficientes. A publicação deve tornar visível o valor preparado do nó antes que a remoção o leia.

Esperar por um item exige um mecanismo de sinalização além do travamento.

Distribua pela chave e depois adquira a trava do balde

Uma tabela de dispersão de tamanho fixo pode usar uma lista segura para uso por múltiplas threads em cada balde, cada uma com seu próprio mutex. Com 101 baldes e bucket = key % 101, as chaves 7 e 50 usam travas diferentes. As chaves 7 e 108 são ambas mapeadas para o balde 7 e devem ser serializadas ali. Colisões afetam a contenção e também o tamanho da busca.

Todos os acessos à lista de um balde seguem a regra de travamento desse balde, inclusive as leituras. O redimensionamento altera o mapeamento dos baldes e move entradas, portanto esse projeto simples precisa de acesso exclusivo a toda a tabela durante o redimensionamento. Um mutex de balde sozinho não pode proteger uma alteração que afeta todos os baldes.

Refine somente após encontrar o gargalo

Comece com um mapa do estado compartilhado: quais campos são compartilhados, qual mutex ou operação atômica protege cada um e quando os nós se tornam acessíveis ou podem ser liberados. Verifique todos os caminhos de retorno e de falha de alocação. Analise as intercalações, teste sob carga com um detector de corridas e meça a contenção antes de acrescentar travas mais finas.