Variáveis de condição, semáforos e impasses

Um mutex responde “Quem pode acessar estes dados agora?” Ele não responde “O trabalho terminou?” Para esperar por um evento, uma thread precisa de um registro do evento e de uma forma de dormir até que esse registro mude.

Por que a espera ocupada é uma forma ruim de esperar

O laço while (done == 0) ; gasta tempo de CPU verificando repetidamente um indicador. Em uma única CPU, esse trabalho atrasa a filha que precisa definir o indicador. Em C, uma leitura não sincronizada de uma variável comum enquanto outra thread escreve nela também é uma corrida de dados. O compilador não precisa recarregar o indicador a cada iteração.

Uma variável de condição fornece uma fila de espera às threads. O POSIX fornece pthread_cond_t, inicializado com PTHREAD_COND_INITIALIZER ou pthread_cond_init(). A fila é separada do estado que está sendo testado: done registra a conclusão; a variável de condição fornece um lugar para dormir.

Mantenha a verificação e a espera juntas

pthread_cond_wait(&c, &m) exige que quem a chama mantenha o mutex m adquirido. Ela libera esse mutex e começa a esperar atomicamente. Antes de retornar, adquire o mutex novamente. Isso elimina o intervalo perigoso no qual outra thread poderia alterar o estado e sinalizar antes que a thread em espera tivesse realmente começado a esperar.

Veja uma thread pai esperando a conclusão de uma filha. Os nomes lock, wait, signal e unlock abreviam as chamadas correspondentes da biblioteca de threads.

/* Parent */
lock(&m);
while (done == 0)
    wait(&c, &m);
unlock(&m);

/* Child */
lock(&m);
done = 1;
signal(&c);
unlock(&m);

Inicialmente, done é 0. Se a thread pai executar primeiro, ela adquire a trava, encontra trabalho não concluído e espera. A espera libera m, permitindo que a filha o adquira, defina done e sinalize. A pai acaba adquirindo m novamente, verifica done outra vez e continua.

Se a filha executar primeiro, ela registra a conclusão antes de a pai chegar. Seu sinal não desperta ninguém, mas a pai, ao chegar depois, vê done == 1 e não espera. O funcionamento correto deve resistir às duas ordens.

Sinais não armazenam eventos

pthread_cond_signal(&c) desbloqueia pelo menos uma thread em espera quando há threads esperando; o POSIX permite que mais de uma desperte. Sem threads em espera, ela não tem efeito. pthread_cond_broadcast(&c) desperta todas as threads que estão esperando naquele momento. Nenhuma das chamadas guarda uma notificação para threads futuras.

Omitir done compromete, portanto, o padrão de espera pelo término: uma filha pode sinalizar antes de sua pai esperar, após o que a pai dorme sem que venha outro sinal. Isso é um despertar perdido. Verificar done fora do mutex cria outra janela para um despertar perdido: a pai verifica e encontra falso, a filha define como verdadeiro e sinaliza, e então a pai começa a esperar.

Proteja a verificação e toda alteração de estado com o mesmo mutex. Mantenha-o adquirido desde a verificação até a chamada de espera. Uma sequência simples de sinalização altera o estado e sinaliza enquanto ainda mantém esse mutex adquirido. O POSIX permite sinalizar sem mantê-lo adquirido, mas o protocolo de estado compartilhado ainda deve impedir um despertar perdido.

Retornar da espera significa que a thread pode tentar novamente. Isso não significa que a condição de que ela precisa ainda seja verdadeira. Essa distinção importa sempre que várias threads competem pelos mesmos dados.

Semânticas de Mesa e Hoare

POSIX, Java, variáveis de condição do C++ e condições do Python seguem o comportamento de Mesa. Os monitores de Hoare introduziram o modelo de passagem mais forte; a abordagem de Mesa é a escolha prática comum.

Suponha que C1 espere um buffer de uma posição deixar de estar vazio. Um produtor o preenche e sinaliza C1. C1 agora está pronta, mas C2 pode adquirir o mutex primeiro e retirar o item. Quando C1 finalmente adquire o mutex novamente, o buffer está vazio outra vez.

lock(&m);
while (count == 0)
    wait(&filled, &m);
v = get();
unlock(&m);

O while repete o teste após cada retorno. Um if testa apenas antes da primeira espera e permitiria que C1 chamasse get() em um buffer vazio. Mesmo com um produtor e um consumidor, use while: o POSIX também permite despertares espúrios, nos quais wait retorna sem um sinal correspondente.

Despertar uma thread ou todas?

Um sinal é adequado quando as threads em espera precisam da mesma condição e qualquer uma pode aproveitar a mudança. Um broadcast é útil quando várias podem prosseguir ou quando diferentes threads em espera precisam de quantidades diferentes e quem sinaliza não consegue selecionar a correta.

Considere um alocador com 0 bytes livres. Ta precisa de 100 bytes e Tb precisa de 10. Outra thread libera 50 bytes. Um sinal pode despertar Ta, que ainda não consegue prosseguir, deixando Tb dormindo mesmo havendo o suficiente para sua requisição. Um broadcast desperta ambas. Elas adquirem o mutex novamente uma por vez; Tb pode alocar, enquanto Ta volta a esperar. Essa é uma condição abrangente: a notificação abrange todas as threads em espera potencialmente aptas a prosseguir.

Um broadcast pode causar despertares extras, trocas de contexto e disputa pelo mutex. Variáveis de condição separadas para predicados distintos podem tornar a sinalização mais seletiva. Em um buffer, produtores e consumidores não devem compartilhar uma única fila de sinais indiferenciada.

A relação com monitores

Um monitor reúne dados compartilhados com operações que admitem uma thread por vez e variáveis de condição para espera. Objetos Java fornecem uma trava e um conjunto de espera. Dentro de synchronized, uma thread pode chamar wait(), notify() ou notifyAll(); chamá-los sem possuir o monitor desse objeto lança IllegalMonitorStateException.

A espera libera apenas o mutex associado ou a trava do objeto Java. Se uma thread também mantiver outra trava adquirida, essa segunda trava permanece adquirida. Um produtor que precise dela pode não conseguir tornar a condição verdadeira. Verifique todas as travas adquiridas ao esperar, não apenas a indicada na chamada.

Produtores adicionam itens a um buffer de tamanho fixo; consumidores os removem. Um buffer limitado correto impede a sobrescrita de um buffer cheio, a remoção de um buffer vazio e alterações concorrentes em seus dados de controle. Uma fila de requisições de servidor web e o canal de comunicação entre grep error log.txt e wc -l seguem esse padrão.

Acompanhe os índices circulares

Um buffer circular usa um array e dois índices. fill_ptr indica a próxima escrita; use_ptr indica a próxima leitura. Ambos avançam módulo MAX. Um count separado distingue vazio de cheio, mesmo quando os dois índices são iguais.

void put(int v) {
    buffer[fill_ptr] = v;
    fill_ptr = (fill_ptr + 1) % MAX;
    count++;
}
int get(void) {
    int v = buffer[use_ptr];
    use_ptr = (use_ptr + 1) % MAX;
    count--;
    return v;
}

Comece com capacidade 3 e ambos os índices em 0. Inserir 7, 8 e 9 preenche as posições 0, 1 e 2. O índice de escrita retorna a 0 e count chega a 3. A retirada retorna 7 e avança o índice de leitura para 1. Inserir 10 reutiliza a posição 0. O array agora é [10, 8, 9], mas a remoção FIFO segue o índice de leitura: primeiro vem 8, depois 9 e depois 10.

Direcione cada sinal ao papel oposto

Use um mutex, empty para produtores que esperam por espaço e fill para consumidores que esperam por um item. Inicialize ambas as variáveis de condição e o mutex antes de iniciar as threads.

/* Producer: repeat for each item v */
lock(&m);
while (count == MAX)
    wait(&empty, &m);
put(v);
signal(&fill);
unlock(&m);

/* Consumer */
lock(&m);
while (count == 0)
    wait(&fill, &m);
v = get();
signal(&empty);
unlock(&m);

A verificação e a atualização do buffer permanecem em uma única seção crítica. Caso contrário, dois produtores poderiam ver a mesma posição livre e sobrescrever o trabalho um do outro. A espera libera m, permitindo que o papel oposto altere o buffer.

Por que uma única fila pode parar

Com uma variável de condição e sinais, produtores e consumidores podem despertar o papel errado. Para capacidade 1, C1 e C2 primeiro dormem porque o buffer está vazio. P insere um item, desperta C1 e então espera porque o buffer está cheio. C1 remove o item e sinaliza, mas o sinal pode despertar C2 em vez de P. C1 espera novamente; C2 também encontra o buffer vazio e espera. P continua dormindo embora haja espaço disponível. Duas filas direcionam cada sinal ao papel que agora pode prosseguir. Um broadcast em uma fila compartilhada pode evitar esse problema de seleção, ao custo de despertares extras.

Uma capacidade maior absorve rajadas e permite a sobreposição do trabalho de produção e consumo fora da curta seção crítica do buffer. As próprias atualizações do buffer continuam serializadas. A capacidade 1 força a alternância de cada inserção e remoção.

Para um encerramento correto, primeiro espere que todos os produtores terminem de inserir seus itens reais. Depois, enfileire um item reservado de fim dos dados por consumidor, como -1 quando os itens reais não são negativos. Cada consumidor sai após retirar um deles. Enviar esses marcadores enquanto os produtores ainda estão ativos pode deixar itens reais sem consumidor.

Um semáforo mantém um inteiro alterado por operações atômicas wait e post. Dijkstra o apresentou na década de 1960 como P e V; o POSIX chama as operações de sem_wait() e sem_post(). Atômico significa que duas threads não podem realizar parcialmente a mesma operação de contador ao mesmo tempo.

As unidades disponíveis determinam o valor inicial

sem_init(&s, 0, X) cria um semáforo sem nome com valor X. O segundo argumento 0 seleciona o compartilhamento entre threads de um processo. Para compartilhamento entre processos, um argumento diferente de zero exige que o semáforo fique em memória compartilhada.

Um semáforo binário usado como trava envolve uma seção crítica com wait e post. Iniciá-lo em 0 bloqueia a primeira thread que tenta entrar. Iniciá-lo em 2 permite a entrada de duas threads e não fornece exclusão mútua.

Dois modelos equivalentes de contagem

Na definição de Dijkstra, o valor permanece não negativo: wait dorme até poder decrementar sem ficar abaixo de zero, e post adiciona uma unidade. O Linux segue essa convenção de valores não negativos.

Para acompanhamentos manuais, use o modelo de contador com sinal: wait decrementa e bloqueia se o novo valor for negativo; post incrementa e desperta uma thread em espera quando há uma bloqueada. Nesse modelo, o módulo de um valor negativo corresponde ao número de threads bloqueadas em espera. É uma convenção de raciocínio, não um valor negativo a esperar da API de semáforos do Linux.

Acompanhe uma trava inicializada em 1:

1. T0 executa wait: 1 passa a 0, então T0 entra.
2. T1 executa wait: 0 passa a −1, então T1 bloqueia.
3. T0 executa post: −1 passa a 0, permitindo que T1 continue.
4. T1 termina e executa post: 0 passa a 1.

O despertar transfere a permissão existente a T1; não é necessário outro wait antes de T1 entrar em sua seção crítica.

Um post é lembrado

Sem nenhuma thread em espera, um post aumenta a contagem disponível. Um wait futuro pode consumir essa permissão. Isso é útil quando uma thread termina antes que a thread que espera por ela tenha começado. Um sinal de variável de condição não tem essa memória.

Semáforos não têm dono: uma thread pode executar wait e outra pode executar post. Um mutex pertence à thread que o adquiriu; liberar um mutex POSIX padrão de outra thread é comportamento indefinido. O semáforo sem dono permite a sinalização, mas também dificulta o diagnóstico de um post extra.

Um semáforo pode ser construído com um mutex, uma variável de condição e um inteiro não negativo. Wait adquire a trava, executa um laço enquanto value <= 0, espera, decrementa e libera a trava. Post adquire a trava, incrementa, sinaliza e libera a trava. O mutex torna atômicas as operações no contador; o laço lida com despertares que não deixam uma unidade disponível. Travas com variáveis de condição e semáforos podem implementar uns aos outros, embora uma implementação correta de variável de condição com semáforos seja mais complexa.

O mesmo par wait/post pode representar um evento ou uma quantidade limitada de recursos. Decida o que uma permissão significa antes de escolher a contagem inicial e onde cada operação deve ficar.

Faça a conclusão preceder o uso

Para uma thread pai que espera por uma filha, inicialize finished em 0. A filha executa post após terminar seu trabalho. A pai executa wait antes de usar o resultado.

/* Child */
produce_result();
sem_post(&finished);

/* Parent */
sem_wait(&finished);
use_result();

Se a pai chegar primeiro, o valor com sinal muda de 0 para −1 e ela dorme. O post da filha retorna o valor a 0 e a desperta. Se a filha chegar primeiro, seu post muda 0 para 1; o wait posterior muda 1 para 0 sem bloquear. Um evento concluído permite um wait bem-sucedido.

Conte um conjunto de recursos

Um conjunto de quatro conexões de banco de dados usa um semáforo inicializado em 4. Cada cliente executa wait antes de obter uma conexão e post depois de devolvê-la. Um quinto cliente simultâneo dorme. O semáforo conta as admissões; um mutex separado ainda protege a lista compartilhada que identifica qual conexão está livre. Duas threads admitidas não devem remover a mesma entrada da lista.

A limitação de concorrência aplica a mesma ideia a uma fase exigente. Suponha que 100 threads precisem de 500 MB cada uma durante o processamento. Juntas, poderiam precisar de 50.000 MB. Uma máquina com 8 GB tem 8.000 MB em unidades decimais do SI. Admitir no máximo 12 trabalhadoras limita essa fase a 6.000 MB e deixa 2.000 MB para outros usos.

sem_wait(&processing_slots);
run_memory_heavy_phase();
sem_post(&processing_slots);

Todo caminho após um wait bem-sucedido deve devolver sua permissão, incluindo um caminho de erro. Esquecer um post reduz gradualmente a capacidade. Executar post duas vezes cria uma permissão extra e permite mais usuários simultâneos que o previsto.

Encontre-se em um ponto de encontro

Um ponto de encontro exige que duas threads cheguem antes que qualquer uma continue. Inicialize a_arrived e b_arrived em 0.

/* A */
sem_post(&a_arrived);
sem_wait(&b_arrived);

/* B */
sem_post(&b_arrived);
sem_wait(&a_arrived);

Se A chegar primeiro, ela registra sua chegada e bloqueia esperando por B. B registra sua chegada e pode consumir a permissão guardada de A. A pode então consumir a permissão de B. Inverter ambas as sequências para executar wait antes de post deixa cada thread dormindo antes de anunciar qualquer coisa.

Esses dois semáforos implementam um encontro. Reutilizar a sincronização em rodadas repetidas exige impedir que as rodadas consumam as chegadas umas das outras; um acompanhamento bem-sucedido não constitui um projeto de barreira reutilizável.

Um semáforo é adequado para uma contagem ou um evento simples. Uma variável de condição é adequada para um predicado mais elaborado, como esperar até que uma fila conter vários itens de um tipo necessário. Nesse caso, o mutex protege o estado a partir do qual a condição é calculada.

Um buffer com semáforos separa duas perguntas: “Há um item ou uma posição disponível?” e “Quem pode atualizar o array agora?” Dois semáforos contadores respondem à primeira pergunta, e um mutex responde à segunda.

Configure três controles distintos

Para a capacidade MAX, inicialize empty em MAX, full em 0 e o mutex como não adquirido. Aqui, empty e full são semáforos, não variáveis de condição. Uma permissão de empty reserva uma posição; uma permissão de full reserva um item.

/* Producer */
sem_wait(&empty);
lock(&mutex);
put(v);
unlock(&mutex);
sem_post(&full);

/* Consumer */
sem_wait(&full);
lock(&mutex);
v = get();
unlock(&mutex);
sem_post(&empty);

O produtor adquire espaço antes de acessar o buffer circular e depois disponibiliza o item concluído com uma operação post em full. O consumidor adquire um item, remove-o sob a proteção do mutex e devolve espaço com uma operação post em empty. Uma operação wait bem-sucedida no semáforo já reserva o recurso, portanto essas chamadas não precisam de um laço para verificar o predicado, como no uso de variáveis de condição.

Acompanhe uma posição

Inicialmente, empty é 1 e full é 0. Um consumidor executa wait em full, alterando-o para −1 no modelo com sinal, e dorme. O produtor executa wait em empty, passando-o de 1 para 0. Ele adquire o mutex, insere o item, libera o mutex e executa post em full, passando-o de −1 para 0 e liberando o consumidor.

O próximo wait do produtor em empty altera 0 para −1 e bloqueia. O consumidor retira o item sob a proteção do mutex e executa post em empty, passando-o de −1 para 0 e liberando o produtor. As contagens dos semáforos realizam a passagem; não é necessário um count separado para sincronização.

Com um buffer maior, vários produtores podem passar pelo semáforo de espaços livres. Sem o mutex, ambos poderiam ler o mesmo fill_ptr e escrever na mesma posição. Uma reserva não é acesso exclusivo aos índices do array.

Por que adquirir o mutex primeiro pode causar impasse

Suponha que o consumidor adquira mutex antes de executar wait em full. Com o buffer vazio, ele dorme ainda mantendo o mutex adquirido. O produtor precisa desse mutex para inserir o item cujo post liberaria o consumidor. Nenhum dos dois consegue terminar.

Uma espera em semáforo não libera nenhum mutex. Uma espera em variável de condição libera deliberadamente seu mutex associado. Portanto, a ordem nesse buffer importa: primeiro reserve, depois adquira o mutex, altere o buffer, libere o mutex e então disponibilize a permissão correspondente ao papel oposto.

A regra mais ampla é evitar bloquear enquanto mantém uma trava necessária à operação que pode desbloquear você. Essa regra explica por que o algoritmo de leitores e escritores pode ter uma organização segura diferente: seu escritor não precisa da trava do contador de leitores para liberar seu recurso.

O próprio mutex pode ser um semáforo binário inicializado em 1. Sua função continua sendo a exclusão mútua; os outros dois semáforos contam recursos.

Estruturas com muitas leituras podem permitir vários leitores ao mesmo tempo porque a leitura não altera os dados. Uma trava de leitores e escritores admite um grupo de leitores ou um escritor. Toda alteração nos dados protegidos exige acesso de escrita.

Forme o grupo de leitores

Use readers = 0, um semáforo lock inicializado em 1 para proteger esse contador e writelock inicializado em 1 para proteger o recurso compartilhado.

/* Acquire read access */
sem_wait(&lock);
readers++;
if (readers == 1)
    sem_wait(&writelock);
sem_post(&lock);

/* Release read access */
sem_wait(&lock);
readers--;
if (readers == 0)
    sem_post(&writelock);
sem_post(&lock);

Um escritor executa wait em writelock, altera os dados e então executa post em writelock. Ele não adquire a trava do contador. O primeiro leitor adquire writelock para o grupo, e o último leitor o devolve. Um semáforo é adequado a essa passagem porque a thread que executa post não precisa ser a mesma que executou wait originalmente.

Acompanhe a entrada de R1: ela aumenta readers para 1 e adquire writelock. R2 aumenta a contagem para 2 sem adquirir outra permissão. O escritor W agora bloqueia em writelock. R1 sai e reduz a contagem para 1. R2 sai, reduz a contagem para 0 e executa post, permitindo que W escreva sozinho.

O primeiro leitor pode esperar por writelock enquanto mantém lock adquirido. Isso não cria o impasse do buffer limitado: o escritor atual não precisa da trava do contador para terminar e executar post em writelock.

Justiça é uma propriedade separada

Esse projeto dá preferência aos leitores. Enquanto a contagem de leitores permanecer positiva, outro leitor poderá entrar no grupo à frente de um escritor em espera. Um fluxo contínuo de leitores com períodos de leitura sobrepostos pode manter o escritor esperando indefinidamente: inanição de escritores.

O projeto básico fornece segurança, mas não limita o tempo que um escritor espera. Maior vazão de leitores não é o mesmo que atendimento justo.

Use o modo correto

Uma trava de leitura não protege uma escrita de outros leitores. Atualizar até mesmo um contador de cache com acesso de leitura pode causar uma corrida com outro leitor. Para converter a trava nesse projeto básico, libere o acesso de leitura, adquira acesso de escrita e verifique novamente a condição. Esperar por acesso de escrita enquanto ainda é contado como leitor pode fazer a thread esperar por si mesma para sempre.

O POSIX fornece pthread_rwlock_t, pthread_rwlock_rdlock(), pthread_rwlock_wrlock() e pthread_rwlock_unlock(). O Java oferece ReentrantReadWriteLock; o C++17 oferece std::shared_mutex. Essas travas exigem mais controle do que um mutex comum. Meça a carga de trabalho: seções curtas ou escritas frequentes podem fazer um mutex simples ser tão rápido quanto ou mais rápido.

Uma violação de atomicidade ocorre quando o código depende de um grupo de acessos ser indivisível, mas outra thread pode agir entre eles. Cada acesso individual pode parecer razoável, enquanto a operação combinada falha.

Encontre o intervalo após a verificação

Considere um buffer de registro compartilhado:

/* T1 */
if (log->buf != NULL)
    write_out(log->buf);

/* T2 */
log->buf = NULL;

T1 pode verificar um ponteiro não nulo, pausar e retomar após T2 defini-lo como nulo. T1 então passa um valor nulo a write_out(). A garantia pretendida não era apenas uma verificação válida; era que o valor verificado permanecesse utilizável até a chamada.

Proteja a verificação e o uso juntos e proteja a atribuição concorrente com o mesmo mutex:

/* T1 */
lock(&m);
if (log->buf != NULL)
    write_out(log->buf);
unlock(&m);

/* T2 */
lock(&m);
log->buf = NULL;
unlock(&m);

T2 agora executa antes ou depois de toda a operação de T1. Dar a cada thread sua própria trava não ajuda: ambas poderiam manter suas travas separadas adquiridas simultaneamente. Proteger apenas T1 deixa T2 livre para agir no intervalo.

Um teste válido ainda pode levar a um saldo inválido

Comece com saldo 50. Duas threads pretendem sacar 30 cada uma somente se houver saldo suficiente. Ambas podem ler 50 e passar por balance >= 30 antes que qualquer uma aja. Se os saques forem então aplicados, o saldo pode chegar a −10. Proteger o teste e a subtração juntos permite que o primeiro saque deixe 20; a próxima thread vê 20 e recusa o saque.

Mesmo leituras e subtrações atômicas não tornam esse par uma transação. Outra thread pode agir entre a verificação atômica e a alteração atômica. Uma trava em torno de toda a decisão e alteração garante o limite necessário.

O mesmo problema aparece em count++: leitura, soma e escrita são etapas separadas. Duas threads podem ler o mesmo valor antigo e armazenar o mesmo valor incrementado, perdendo uma atualização. Uma trava em torno do incremento ou uma instrução atômica de busca e soma realiza a atualização necessária com segurança.

Use evidências sem generalizar demais

Lu e colaboradores examinaram 105 erros de concorrência corrigidos em MySQL, Apache, Mozilla e OpenOffice em um estudo de 2008. Desses, 74 eram erros sem impasse e 31 eram impasses. Violações de atomicidade e de ordem correspondiam a 97% da amostra de erros sem impasse. Essas são conclusões sobre a amostra estudada, não uma porcentagem garantida para toda base de código.

Cerca de 92% dos erros estudados podiam ser provocados controlando a ordem de no máximo quatro acessos à memória. Uma pequena tabela de intercalação pode, portanto, ser mais reveladora do que milhares de execuções comuns bem-sucedidas. O ThreadSanitizer ajuda a encontrar corridas de dados executadas, mas um erro lógico de atomicidade pode permanecer mesmo quando cada acesso individual é sincronizado. Teste a propriedade invariante de toda a operação, como “um saque bem-sucedido nunca deixa o saldo negativo”.

Uma violação de ordem significa que a operação A deve acontecer antes da operação B, mas o programa não fornece sincronização que garanta isso. A exclusão mútua sozinha não determina qual operação ocorre primeiro.

Uma thread pode executar imediatamente

Suponha que uma thread criadora armazene um registro recém-criado de uma thread trabalhadora em um ponteiro compartilhado, enquanto a trabalhadora começa usando esse ponteiro:

/* Creator */
worker = thread_create(worker_main);

/* New worker */
use(worker->state);

A trabalhadora pode executar antes de thread_create() retornar e antes de a atribuição terminar. A ordem no código-fonte da criadora não diz nada sobre quando a nova thread receberá tempo de CPU. Uma execução bem-sucedida significa apenas que a criadora venceu essa corrida por acaso.

Sinalize a prontidão após a inicialização

Acrescente ready = 0, o mutex m e a variável de condição c. A criadora mantém o mutex adquirido enquanto atribui o ponteiro e sinaliza a prontidão:

/* Creator */
lock(&m);
worker = thread_create(worker_main);
ready = 1;
signal(&c);
unlock(&m);

/* Worker, before using worker */
lock(&m);
while (ready == 0)
    wait(&c, &m);
unlock(&m);
use(worker->state);

Se a trabalhadora chegar primeiro ao mutex, ela não poderá passar pelo teste de prontidão até que a criadora tenha disponibilizado o registro. Se chegar depois, ready registra que a inicialização terminou. Mantenha o registro válido enquanto a trabalhadora o usa e sincronize quaisquer alterações posteriores.

Um semáforo inicializado em 0 oferece uma passagem mais curta: a criadora executa post após atribuir o ponteiro, e a trabalhadora executa wait antes de usá-lo. Para um resultado que só existe depois que uma thread termina, aguardar seu término antes de ler o resultado estabelece a ordem necessária. A liberação de um objeto também deve esperar até que seus usuários terminem, por exemplo aguardando o término das threads ou usando uma contagem de referências corretamente sincronizada.

Por que mudanças no tempo de execução não corrigem o problema

Acrescentar sleep(1) ou sched_yield() apenas muda a probabilidade do escalonamento desejado. Um sistema mais lento ou sobrecarregado ainda pode permitir que o consumidor prossiga cedo demais. Um mutex em torno de cada operação impede a sobreposição, mas ainda permite que o uso adquira o mutex antes da inicialização.

No estudo de Lu e colaboradores, cerca de um terço dos erros sem impasse eram violações de ordem, e cerca de 73% dos erros sem impasse não foram corrigidos apenas acrescentando ou alterando travas. Antes de escolher uma primitiva, identifique a operação que deve terminar e a operação que deve esperar. Essa dependência determina onde colocar post, signal ou a espera pelo término.

Um conjunto de threads está em impasse quando cada uma espera por algo que somente outra thread do conjunto pode fornecer. Nenhuma delas consegue continuar e realizar a ação que libera as demais. O programa pode funcionar em muitos escalonamentos até que uma ordem desfavorável revele o ciclo.

Construa a falha com duas travas

T1 adquire L1 e em seguida solicita L2. T2 adquire L2 e em seguida solicita L1. Se T1 adquirir L1 e depois T2 adquirir L2, ambas as segundas aquisições bloqueiam. Cada thread mantém exatamente o recurso de que a outra precisa.

Isso pode ficar oculto em funções comuns. Se transfer(a, b) adquire a trava de a e depois a de b, chamadas simultâneas a transfer(x, y) e transfer(y, x) podem adquirir as travas das contas em ordens opostas. O encapsulamento torna uma chamada conveniente, mas pode ocultar as travas que ela adquire.

Identifique as quatro condições

As quatro condições são necessárias. Eliminar qualquer uma delas no projeto previne impasses por recursos. A presença de travas exclusivas e aquisições aninhadas, por si só, não estabelece que uma determinada execução chegou a um ciclo.

Interprete um grafo de espera

Desenhe um nó por thread. Desenhe T → U quando T esperar por um recurso mantido por U. Com recursos de instância única, como travas exclusivas, um ciclo identifica um impasse.

Para T1 mantendo A e esperando por B, T2 mantendo B e esperando por C e T3 mantendo C e esperando por A, o grafo é T1 → T2 → T3 → T1. As três estão presas. Se T3 solicitar uma trava livre D, poderá terminar e liberar C, permitindo que T2 e depois T1 prossigam. Uma cadeia não é um ciclo.

Quando tipos de recursos têm várias instâncias intercambiáveis, um ciclo sozinho é insuficiente: uma instância adicional pode ficar disponível. Use as contagens de recursos e as requisições pendentes para avaliar esse caso.

Jantar dos filósofos e falhas relacionadas

Cinco filósofos compartilham cinco garfos dispostos em círculo. Cada um precisa dos dois garfos vizinhos. Se todos pegarem primeiro o garfo à esquerda, todos poderão esperar para sempre pelo garfo à direita. Inverter a ordem de aquisição de um filósofo rompe o ciclo. Limitar a admissão a quatro filósofos também impede que os cinco mantenham um garfo cada; pelo menos um filósofo admitido consegue obter os dois garfos.

Inanição significa que uma thread espera indefinidamente enquanto outras progridem. Bloqueio ativo significa que threads executam e reagem, mas falham repetidamente em progredir. Um conjunto em impasse está bloqueado. Uma thread pode até causar um impasse consigo mesma ao adquirir um mutex normal, não recursivo, que já mantém adquirido. Semáforos e variáveis de condição também podem criar dependências: uma thread em espera que mantém uma trava necessária à thread que a sinaliza pode fechar um ciclo sem uma segunda aquisição explícita de trava.

A prevenção altera o projeto para que uma condição necessária ao impasse não possa surgir. A ordenação de aquisição de travas costuma ser a abordagem mais clara porque ataca diretamente a dependência circular.

Defina uma ordem para todas as travas

Atribua chaves únicas às travas e sempre adquira as de chaves menores antes das de chaves maiores. Para transferências entre contas, ordene os identificadores das contas antes de adquirir as travas. Assim, tanto transfer(x, y) quanto transfer(y, x) adquirem primeiro a trava da mesma conta. Se os identificadores indicarem a mesma conta, adquira sua trava uma vez.

Um ciclo exigiria que as chaves continuassem aumentando ao redor do círculo e retornassem à chave inicial, o que é impossível. Todo caminho de aquisição deve seguir a regra. Uma única função auxiliar que inverta a ordem traz o risco de volta. O lockdep do Linux acompanha as dependências de travamento observadas e informa ordens potencialmente inseguras.

Adquira tudo ou não adquira nada

Uma forma estrita de eliminar posse e espera é conceder a uma thread seu conjunto completo de recursos em uma etapa ou não conceder nada. Ela nunca mantém um conjunto parcial enquanto espera pelo restante. Isso exige conhecer os recursos necessários antecipadamente e pode reduzir a concorrência.

Um protocolo relacionado serializa sequências de aquisição com uma trava global de prevenção:

lock(&prevention);
lock(&L1);
lock(&L2);
unlock(&prevention);
/* use L1 and L2, then release them */

Todas as threads devem terminar de adquirir seu conjunto completo sob essa trava global, e a liberação de recursos não deve exigir sua aquisição. Uma thread ainda pode manter L1 enquanto espera por L2, portanto isso não elimina literalmente a posse e espera. O protocolo impede que outras threads iniciem uma aquisição parcial concorrente. Nenhuma thread que mantenha recursos pode estar no meio de uma segunda sequência de aquisição concorrente. Os custos são manter travas adquiridas mais cedo e serializar a aquisição.

Desista e tente novamente

pthread_mutex_trylock() retorna imediatamente com EBUSY quando uma trava está indisponível. Uma thread pode adquirir L1, tentar L2 e liberar L1 se a tentativa falhar. Ela também deve desfazer outras aquisições parciais antes de tentar novamente.

Duas threads podem colidir repetidamente, recuar e tentar novamente juntas. Isso é bloqueio ativo: ambas executam, mas nenhuma termina. A espera aleatória antes de nova tentativa reduz colisões repetidas; ela não transforma o laço de tentativas em uma garantia de justiça.

Substitua uma trava por uma operação atômica

A comparação e troca (CAS) altera uma posição apenas se ela ainda corresponder a um valor esperado. Conceitualmente, um laço de nova tentativa para soma atômica lê o valor antigo, tenta substituí-lo pelo valor antigo mais o incremento e tenta novamente se outra thread o tiver alterado primeiro. Implementações reais em C usam tipos e operações atômicas tanto para a leitura quanto para a atualização.

Eliminar a aquisição de travas elimina o impasse por travas dessa operação. Um algoritmo livre de travas garante progresso para o sistema como um todo, mas uma thread pode continuar falhando em suas tentativas. Estruturas gerais livres de travas também precisam de um projeto cuidadoso do tempo de vida da memória.

A evitação verifica se uma requisição proposta deixa uma forma de todas as threads terminarem. Ela permite os padrões usuais de uso de recursos, mas adia requisições que eliminem as ordens restantes de conclusão segura.

Um estado seguro garante uma ordem possível

Uma sequência segura ordena as threads de modo que cada uma possa obter sua demanda máxima restante com os recursos livres no momento mais os liberados pelas threads anteriores. Um estado inseguro não tem essa ordem garantida. Ele não precisa já estar em impasse: as threads podem solicitar menos que seu máximo ou liberar recursos antecipadamente.

O escalonamento também pode evitar uma sobreposição perigosa ao garantir que duas tarefas conflitantes não entrem juntas em suas fases de uso de recursos. Simplesmente colocar ambas em uma CPU é insuficiente, pois elas ainda podem sofrer preempção e se intercalar enquanto mantêm recursos. A garantia necessária é a ausência de sobreposição das fases conflitantes.

Prepare as tabelas do banqueiro

Para cada tipo de recurso, acompanhe Available. Para cada thread, acompanhe Max, Allocation e Need = Max - Allocation. Compare vetores componente por componente, nunca pela soma de seus totais.

Use os totais de recursos (7, 5, 6):

As alocações somam (4, 3, 4), deixando Available = (3, 2, 2).

Acompanhe o teste de segurança

Defina Work como Available. Escolha uma thread não concluída cuja Need caiba em Work, simule sua conclusão e devolva sua Allocation a Work.

1. T1 cabe em (3, 2, 2). Devolver (2, 0, 1) resulta em Work (5, 2, 3).
2. T0 cabe. Devolver (1, 1, 0) resulta em (6, 3, 3).
3. T2 cabe. Devolver (1, 1, 2) resulta em (7, 4, 5).
4. T3 cabe. Devolver (0, 1, 1) resulta em (7, 5, 6).

Todas as threads terminam nessa simulação, portanto o estado é seguro. Work aumenta em Allocation, não em Max: os recursos extras temporariamente concedidos para a conclusão também são devolvidos, resultando em um ganho líquido igual ao que a thread mantinha originalmente.

Simule a concessão e teste novamente

Uma requisição deve caber tanto em Need da thread quanto em Available. Então subtraia-a de Available, some-a a Allocation, subtraia-a de Need e execute o teste de segurança nesse estado provisório.

Na tabela original, T2 solicitar (1, 0, 1) deixa Available em (2, 2, 1). T1 ainda pode ir primeiro, seguida por T0, T2 e T3, portanto é seguro.

Já T3 solicitar (2, 1, 1) deixa Available em (1, 1, 1). A Need restante de T3 é (2, 0, 1). Nenhuma thread cabe: T0 precisa de 4 de A, T1 precisa de 2 de B, T2 precisa de 2 de C e T3 precisa de 2 de A. Adie essa requisição apesar dos recursos livres no momento.

Toda requisição posterior precisa do mesmo teste. A evitação exige demandas máximas declaradas e um modelo de recursos conhecido, tornando-a mais adequada a sistemas especializados previsíveis do que a cargas de trabalho de aplicações gerais.

Um sistema pode permitir que um impasse se forme, detectá-lo e se recuperar. Isso aceita a perda ocasional de trabalho em troca de menos restrições às requisições comuns de recursos. A detecção só é útil quando existe uma ação de recuperação viável.

Encontre ciclos de bloqueio

Para recursos de instância única, mantenha um grafo de espera e procure um ciclo, por exemplo com uma busca em profundidade. Suponha que as arestas sejam T1 → T2, T2 → T3, T3 → T1 e T4 → T2. T1, T2 e T3 formam o ciclo. T4 está bloqueada atrás dele; a própria execução de T4 não pode liberar um recurso que rompa esse ciclo.

Com múltiplas instâncias, um ciclo é insuficiente. Use Available, Allocation e a requisição atual pendente Request de cada thread. Inicie Work com Available. Encontre repetidamente uma requisição que caiba, simule a conclusão e some a Allocation dessa thread a Work. Diferentemente da evitação, esse teste usa aquilo pelo que as threads estão esperando agora, não sua possível demanda máxima futura.

O detector padrão de recursos inicialmente separa as threads que não mantêm recursos: elas não podem contribuir com recursos mantidos para um ciclo de recursos. Entre as threads que mantêm recursos, as que permanecem não concluídas pelo teste estão em impasse segundo o modelo. Outras threads ainda podem estar impossibilitadas de progredir porque dependem desse conjunto. Manter o ciclo separado das threads bloqueadas que dependem dele ajuda a escolher uma vítima eficaz para a recuperação.

Recupere sem corromper o estado compartilhado

Um sistema pode encerrar um ou mais processos, recuperar recursos com reversão a um ponto de verificação ou reiniciar. Escolha vítimas pelo custo de recuperação, prioridade, trabalho já realizado e recursos mantidos. Após remover uma vítima, verifique novamente: vários ciclos independentes podem exigir mais de uma ação de recuperação.

Encerrar uma thread arbitrária não basta se ela deixar um mutex adquirido ou uma estrutura compartilhada parcialmente alterada. A recuperação deve liberar ou reconstruir recursos e restaurar um estado válido. Sistemas de transações podem abortar uma transação em impasse porque a reversão faz parte de seu projeto. Uma aplicação comum muitas vezes precisa de uma reinicialização controlada do processo.

Interprete tempos limite com cuidado

pthread_mutex_timedlock() pode retornar ETIMEDOUT após um prazo. Um temporizador de supervisão pode reiniciar um dispositivo que deixa de informar progresso. Ambos detectam espera excessiva; uma espera longa também pode resultar de entrada e saída lenta ou de escalonamento. Um tempo limite é uma evidência para investigar ou recuperar o sistema, não um diagnóstico exclusivo de um ciclo.

Linux e Windows em geral não encontram nem reparam ciclos entre as próprias travas de uma aplicação. O programa deve implementar a estratégia escolhida. Se a recuperação selecionar repetidamente o mesmo trabalho como vítima, esse trabalho poderá sofrer inanição mesmo que cada impasse individual seja desfeito.

Um laço de eventos espera por eventos e despacha tratadores curtos em uma thread. O programa escolhe explicitamente qual evento pronto tratar em seguida. Node.js e nginx usam projetos baseados em eventos para atender muitas conexões sem atribuir uma thread dedicada a cada conexão.

while (1) {
    events = get_events();
    /* handle each ready event, then return to the loop */
}

Tratadores síncronos no mesmo laço executam um por vez. As instruções comuns de um tratador não são interrompidas por outro tratador nesse laço. O laço ainda depende de os tratadores retornarem rapidamente.

Construa e inspecione conjuntos para select

select() aceita conjuntos de descritores a observar para leitura, escrita e condições excepcionais, além de um tempo limite. Seu argumento nfds é um a mais que o maior descritor observado. Observar os descritores 3, 5 e 9 exige, portanto, nfds = 10, não 3.

FD_ZERO(&readset);
FD_SET(3, &readset);
FD_SET(5, &readset);
FD_SET(9, &readset);
int n = select(10, &readset, NULL, NULL, NULL);
/* If n > 0, test each watched descriptor with FD_ISSET. */

Um tempo limite nulo espera pela prontidão; um tempo limite zero verifica e retorna imediatamente. select() sobrescreve os conjuntos com os descritores prontos, portanto reconstrua-os antes de cada chamada. Seu retorno positivo conta os bits definidos nos conjuntos retornados; um descritor pronto em dois conjuntos conta duas vezes. Zero significa tempo limite; −1 significa erro.

Prontidão não é transferência de dados. O programa ainda chama read() ou recv(). O fim da entrada pode aparecer como prontidão para leitura; uma leitura que retorna 0 significa que a outra ponta fechou seu lado de envio. Trate esse resultado em vez de despachar repetidamente a mesma entrada encerrada.

Mantenha os tratadores curtos e não bloqueantes

Configure os sockets com O_NONBLOCK. Quando uma operação não pode prosseguir, ela retorna −1 com errno definido como EAGAIN ou EWOULDBLOCK, permitindo que o tratador retorne ao laço. A prontidão pode mudar antes da operação, portanto o modo não bloqueante também protege contra uma espera inesperada após uma indicação de prontidão.

Uma leitura bloqueante dentro de um tratador atrasa todos os eventos na fila. Com 100 requisições enfileiradas e uma leitura bloqueante de disco de 10 ms por tratador, a última requisição espera cerca de 990 ms antes de sua própria leitura começar; o lote leva cerca de 1.000 ms. A thread passou a maior parte desse tempo esperando enquanto trabalho pronto permanecia na fila.

Escolha uma interface de prontidão

select() e poll() examinam o conjunto observado fornecido em cada chamada, portanto seu trabalho cresce com o tamanho dele. O Linux oferece epoll; FreeBSD e macOS oferecem kqueue. Observar apenas alguns descritores não torna seguro um valor alto de descritor para um fd_set de tamanho fixo.

A prontidão de rede informa a um laço quando ele pode tentar uma operação de entrada e saída. Arquivos regulares em disco são diferentes: select() e poll() os informam como prontos mesmo quando o acesso a seus dados ainda espera pelo armazenamento. Para continuar atendendo outros eventos, submeta o trabalho de forma assíncrona e trate seu resultado depois.

Submeta, faça outro trabalho e obtenha o resultado

A entrada e saída assíncrona POSIX armazena uma requisição em struct aiocb. Campos importantes são aio_fildes para o descritor de arquivo, aio_offset para a posição no arquivo, aio_buf para o destino e aio_nbytes para o comprimento solicitado.

/* cb describes a read request */
aio_read(&cb);
/* Return to other work. Later: */
int status = aio_error(&cb);
/* EINPROGRESS: still running; 0: succeeded; otherwise an error. */
/* After completion, aio_return(&cb) collects its result. */

aio_read() enfileira a requisição e retorna. A conclusão é um evento separado. Quando aio_error() indica conclusão, aio_return() fornece o resultado, como os bytes lidos após uma operação bem-sucedida. Uma requisição pode falhar, e uma leitura bem-sucedida pode retornar menos bytes que o solicitado. O registro da requisição e seu buffer devem permanecer válidos enquanto a operação estiver pendente.

Examinar repetidamente cada requisição em um laço contínuo desperdiça tempo de CPU. aio_sigevent pode configurar um sinal de conclusão ou uma chamada de retorno. O io_uring do Linux usa filas de submissão e conclusão; as portas de conclusão de entrada e saída do Windows fornecem despacho baseado em conclusão. Essas interfaces permitem que o programa aja sobre o trabalho concluído sem verificar constantemente cada requisição não concluída.

Preserve o estado durante o intervalo

Uma thread bloqueada mantém as variáveis locais de sua função na pilha. Um tratador de eventos que submete uma operação de entrada e saída e retorna deve salvar o que o tratador posterior precisa. Esse controle explícito é o gerenciamento manual da pilha; o estado salvo é uma continuação.

Suponha que um servidor leia o descritor de arquivo 12 para um cliente no socket 7. Na submissão, ele salva um registro que associa essa requisição de leitura ao socket 7 e ao estado de sua resposta. Quando a conclusão chega, o laço encontra o registro, verifica o resultado da leitura e continua enviando a resposta ao cliente correto. Registros separados impedem que várias requisições pendentes confundam seus destinos.

A continuação deve estar vinculada à operação específica, não apenas a um identificador que possa ser reutilizado depois. Mantenha a referência ao cliente válida até que a conclusão seja tratada e remova o registro quando a tarefa terminar. Esses detalhes de tempo de vida substituem suposições que uma função bloqueante de execução sequencial poderia manter em sua pilha.

Uma sintaxe legível pode ocultar uma suspensão

Chamadas de retorno, promessas e async/await automatizam grande parte desse salvamento de estado. Em JavaScript, const data = await readFile(path); suspende essa função enquanto sua operação de entrada e saída está pendente. Outro trabalho do laço pode executar, e a função é retomada mais tarde com seu estado local restaurado.

Assíncrono significa que quem chamou pode continuar antes de a operação terminar. Isso não significa que seus tratadores executem em vários núcleos de CPU ao mesmo tempo. Também não faz código que exige muita CPU após um await ceder automaticamente a execução: esse código ainda ocupa sua thread até retornar ou ser suspenso novamente.

Um laço de eventos é adequado para muitas conexões em geral ociosas com pequenas rajadas de trabalho. Um projeto baseado em threads mantém juntos o fluxo de controle e a pilha de uma tarefa. A melhor escolha depende do tempo de espera, do trabalho de CPU, da memória e de como o código evoluirá.

Compare o trabalho que cada projeto exige

Um servidor de chat com 50.000 conexões em geral ociosas pode se beneficiar de registros de eventos em vez de uma pilha de thread dedicada por conexão. Um processador de imagens que faz computação intensa por requisição precisa de trabalhadores suficientes para usar os núcleos disponíveis; um único laço ocupado não consegue paralelizar esses cálculos.

Esperas ocultas ainda importam

Um tratador pode parar sem uma chamada evidente a uma API bloqueante. Acessar uma página que foi transferida para o disco pode provocar uma leitura de disco. Durante essa falta de página, a thread do laço espera. mlock() pode manter as páginas necessárias residentes quando o sistema permite a quantidade solicitada de memória fixada. Apenas remover chamadas bloqueantes explícitas não elimina todas as fontes de atraso.

Mudanças no código podem introduzir outra espera oculta. Se uma função auxiliar que antes retornava imediatamente começar a buscar dados, quem a chama em um projeto baseado em eventos deverá dividir o trabalho em torno de uma continuação ou transferir a chamada a outro trabalhador. A pilha de uma thread bloqueante já armazena onde retomar e o estado local necessário.

Combine os pontos fortes

Um projeto híbrido mantém a prontidão de rede no laço de eventos e envia tarefas bloqueantes ou que exigem muita CPU a um conjunto de trabalhadores. As conclusões retornam ao laço para o tratamento da resposta. O Node.js usa o conjunto de threads do libuv para operações de sistema de arquivos, de modo que uma interface assíncrona pode ser implementada por threads em segundo plano.

Para usar múltiplos núcleos, um servidor pode executar um laço de eventos por núcleo em threads ou processos separados. Se esses laços compartilharem dados mutáveis, precisarão das travas usuais ou de outro protocolo de sincronização. A vantagem de dispensar travas se aplica a tratadores síncronos em um único laço, não a todas as partes de um servidor baseado em eventos.

Uma tarefa pode se intercalar durante um await

Suponha que reste uma unidade em estoque. Um tratador verifica a disponibilidade, aguarda o pagamento e então subtrai do estoque. Enquanto ele está suspenso, outro tratador pode verificar o mesmo estoque e também iniciar um pagamento. Ambas as verificações podem ter sucesso antes de qualquer subtração. Nenhum par de tratadores síncronos executa simultaneamente, mas a operação completa de verificação e atualização não é atômica.

Reserve o estoque em uma única alteração de estado sincronizada antes de ceder a execução, com um caminho de liberação caso o pagamento falhe, ou verifique novamente sob um protocolo que impeça uma segunda venda. Um mutex mantido adquirido durante uma longa espera pode criar outros problemas de progresso, portanto projete explicitamente a transição de estado e sua recuperação. Código baseado em eventos ainda exige analisar quais fatos permanecem verdadeiros após cada suspensão.