Concorrência

O panorama: palavras que você vai precisar

Vamos começar por algumas palavras, porque todo o resto é construído sobre elas. Um programa é uma receita escrita. Um processo é a receita sendo cozinhada agora. Dentro de um processo pode haver uma ou muitas threads. Uma thread é um cozinheiro seguindo uma linha da receita.

O escalonador é a surpresa desta história. Você não decide quando uma thread roda. O escalonador pode pausar uma thread no meio de uma frase e passar a vez para outra, e voltar depois. Por isso, a ordem em que os passos de duas threads se misturam não está sob o seu controle e pode mudar de uma execução para a outra.

Concorrência versus paralelismo, processos e threads

Essas duas palavras são muito confundidas. Imagine uma professora corrigindo provas de duas turmas. Ela corrige uma página da turma A, depois uma da turma B, depois A de novo. As duas pilhas estão em andamento juntas, mas ela trabalha em apenas uma página a cada momento. Isso é concorrência: várias tarefas em andamento, com os passos misturados no tempo. Agora imagine duas professoras, cada uma com uma pilha, corrigindo no mesmo instante. Isso é paralelismo: várias tarefas realmente avançando no mesmo momento físico, o que exige mais de um trabalhador, ou seja, mais de um núcleo de processador.

Com um único núcleo, o computador finge simultaneidade: dá a cada thread uma fatia de tempo curta, de novo e de novo, tão rápido que tudo parece simultâneo. Isso às vezes é chamado de pseudoparalelismo. Para trabalho que só calcula, isso não economiza tempo: quatro threads em um núcleo fazem o mesmo trabalho total que uma thread, mais o custo das trocas. A palestra de Rob Pike é a explicação famosa: concorrência é estrutura, paralelismo é execução.

O que a thread tem só para si e o que compartilha

Compartilhar memória facilita a cooperação entre threads, porque nada precisa ser copiado. Também as torna perigosas, que é o assunto das próximas seções. Uma thread pode estar em três estados. Executando significa que ela tem um núcleo agora. Pronta significa que poderia rodar, mas todos os núcleos estão ocupados, então espera o escalonador. Bloqueada significa que espera um evento (um arquivo, uma trava, uma mensagem) e não rodaria nem com um núcleo livre. Quando o evento acontece, ela vira pronta, não executando.

      escalonador escolhe
   pronta -----------------------> executando
     ^  <--- fatia de tempo acaba ---    |
     |                                   | espera um
     |        evento acontece            v evento
     +------------------------------ bloqueada

Quando o escalonador para uma thread e inicia outra no mesmo núcleo, isso é uma troca de contexto: o sistema guarda os registradores, o contador de programa e o ponteiro de pilha de quem sai e carrega os de quem entra. Esse trabalho não pertence a nenhuma tarefa, então é custo puro. Trocar entre duas threads do mesmo processo é mais barato do que entre dois processos, porque os processos também trocam o espaço de endereçamento, e isso joga fora as traduções de memória guardadas em cache.

Quem cria as threads

• Threads de kernel: criadas e escalonadas pelo sistema operacional. Podem usar vários núcleos, e uma bloqueada não para as outras. A troca custa mais.
• Threads em espaço de usuário: criadas por uma biblioteca, invisíveis para o kernel. Baratas para criar e trocar, mas o kernel enxerga uma thread só. Se uma delas faz uma chamada bloqueante, o processo inteiro para, e elas não usam vários núcleos.
• Threads verdes e goroutines: criadas e escalonadas pelo runtime da linguagem, muitas sobre poucas threads de kernel (modelo M:N). Em Go, 100.000 goroutines que só dormem funcionam bem em 8 núcleos: quando uma bloqueia em algo que o runtime conhece (sleep, canal, mutex), só essa goroutine fica estacionada e a thread do kernel continua trabalhando.

Thread t = new Thread(() -> System.out.println("A"));
t.start();   // pede à JVM uma NOVA thread, que executa a tarefa
// t.run();  // só uma chamada de método comum: continua UMA thread!
t.join();    // espera aqui até t terminar
System.out.println("B");   // sempre depois de A

Depois de start(), a ordem entre a nova thread e a thread que a criou fica por conta do escalonador e não pode ser prevista. join() cria um ponto de encontro: tudo o que vem depois de t.join() acontece depois de tudo o que t fez.

Condições de corrida e seções críticas

Duas crianças dividem um cofrinho. Ele tem 5 moedas. As duas olham dentro e veem 5. Cada uma decide colocar uma moeda, então cada uma pensa 'agora tem 6' e escreve 6 na etiqueta. O cofrinho tem de fato 7 moedas, mas a etiqueta diz 6. Uma soma foi perdida, e ninguém fez nada errado. Isso é uma condição de corrida: a resposta depende da ordem não controlada em que as threads fazem seus passos sobre dados compartilhados.

A linha de programa counter++ parece um passo só, mas são três: ler o valor, somar 1, escrever o resultado. Veja o que pode acontecer quando duas threads executam esses três passos.

thread A            thread B            counter
lê 5                                    5
                    lê 5                5
soma 1 (6)
                    soma 1 (6)
escreve 6                               6
                    escreve 6           6   <- dois incrementos,
                                           só um contado

Esse tipo de bug se chama atualização perdida. Nada trava e nenhum erro aparece: os dados simplesmente ficam errados, e diferentes a cada execução. No mini-projeto counter-race deste repositório, 8 trabalhadores fazem 1.000.000 de incrementos no total e o contador quebrado costuma terminar entre 150.000 e 700.000 em vez de 1.000.000. O problema é o mesmo em toda linguagem, porque os três passos são os mesmos na máquina.

Quantos resultados são possíveis?

Para saber o que um trecho concorrente pode produzir, liste as formas como seus passos podem se misturar (os intercalamentos). Para duas threads que começam com counter = 0 e fazem cada uma um counter++, há apenas dois resultados. Se a leitura de uma thread vem depois da escrita da outra, o resultado é 2. Se as duas leituras acontecem antes de qualquer escrita, o resultado é 1. Nunca pode ser 0, e nunca pode passar de 2.

A seção crítica

O trecho de código que toca a coisa compartilhada é a seção crítica (ou região crítica). A cura é a exclusão mútua: enquanto uma thread está dentro, as outras esperam do lado de fora. Mantenha a seção crítica pequena, para ninguém esperar muito. Uma boa solução para o problema da seção crítica precisa satisfazer quatro condições:

1. Nunca duas threads dentro ao mesmo tempo (exclusão mútua).
2. Não pode supor nada sobre a velocidade das threads nem sobre o número de núcleos.
3. Uma thread que está fora da seção crítica não pode bloquear outra thread.
4. Nenhuma thread espera para sempre.

Uma ideia simples que quebra a terceira condição é a alternância estrita: uma variável turn diz de quem é a vez, e cada thread entra só na sua vez. Uma thread rápida fica presa atrás de uma lenta que nem tem interesse na seção crítica, porque a lenta ainda não usou a sua vez.

Duas armadilhas

• Verificar e depois agir (check-then-act): você testa uma condição (se a chave não existe) e depois age (coloca a chave), mas outra thread muda as coisas entre o teste e a ação. Mesmo que cada chamada a um mapa thread-safe seja segura sozinha, a sequência inteira não é. A seção crítica é a sequência toda, então ela precisa de uma operação atômica ou de uma trava em volta das duas chamadas.
• Data race contra condição de corrida: uma data race é uma falha de baixo nível. Condição de corrida é uma ideia maior: o resultado depende da ordem. Você pode ter condição de corrida sem data race. Duas threads que fazem setBalance(getBalance() - 100), com os dois métodos sincronizados, nunca tocam a memória juntas, mas ainda assim perdem uma atualização, porque a leitura e a escrita são seções críticas separadas.

Mutexes e travas

Pense na chave do banheiro pequeno de uma cafeteria. Só uma pessoa pode ficar com a chave, e quem a tem é a única lá dentro. As outras esperam. Quando a pessoa sai, a chave volta ao gancho e a próxima a pega. Um mutex (de mutual exclusion, exclusão mútua) é essa chave. Ele tem dois estados, trancado e destrancado. Uma thread chama lock antes da seção crítica e unlock quando sai. Se o mutex já está trancado, a thread espera.

mu.Lock()
defer mu.Unlock()   // roda quando a função termina, termine como terminar
counter++

A regra mais importante: toda trava deve ser liberada em todas as saídas, inclusive nos erros, ou todo mundo espera para sempre. Cada linguagem ajuda do seu jeito.

Uma trava é reentrante quando a thread que já a segura pode pegá-la de novo sem se bloquear. Ela lembra o dono e quantas vezes foi pega, e só fica livre quando as liberações igualam as aquisições. As travas do Java são reentrantes. Por isso um método synchronized pode chamar outro método synchronized do mesmo objeto sem congelar.

Esperar girando ou dormindo

Como uma thread deve esperar por uma trava? Um jeito é a espera ocupada (busy waiting, ou spinning): ela fica perguntando 'já está livre?' num laço, como uma criança na viagem de carro perguntando 'já chegamos?' a cada dez segundos. Gasta tempo de processador. O outro jeito é bloquear: a thread dorme e o sistema a acorda quando a trava fica livre. Dormir e acordar também custa tempo. Então girar só é boa escolha quando a espera é menor que esse custo: uma seção crítica bem curta cujo dono está rodando em outro núcleo. Uma trava que gira com uma instrução de hardware é um spinlock. Muitos mutexes reais giram um instante e depois dormem.

Qual deve ser o tamanho de uma trava?

A granularidade de uma trava é quanto dado ela protege. Uma trava grande é simples, mas faz todo mundo esperar todo mundo. Muitas travas pequenas deixam threads que tocam dados diferentes trabalharem juntas. O limite é a invariante, um fato que precisa ser sempre verdadeiro. Se um estoque mantém stock + reserved = total, os dois números precisam mudar dentro de uma só seção crítica, ou outra thread verá a soma quebrada no meio. Dividir em duas travas e atualizá-las uma depois da outra quebra isso. A solução é segurar as duas travas ao mesmo tempo, sempre na mesma ordem (as próximas seções explicam por quê).

Inversão de prioridade

Suponha que a thread L (prioridade baixa) segure um mutex, a thread H (prioridade alta) o peça e bloqueie, e a thread M (média) fique pronta e nem use o mutex. M roda antes de L, então L não consegue terminar e liberar a trava, e H fica presa atrás de M. Uma thread de prioridade alta passa a depender de uma média. A cura é a herança de prioridade: enquanto L segura uma trava que H quer, L roda temporariamente com a prioridade de H.

Semáforos e monitores

Imagine uma biblioteca com 3 salas de estudo. Na porta há um pote com 3 fichas. Para entrar, você pega uma ficha. Quando o pote está vazio, você espera. Quando alguém sai, devolve a ficha. Esse pote é um semáforo: um contador com duas operações que não podem ser interrompidas. down (também chamada P) pega uma unidade e, se o contador é zero, põe a thread para dormir. up (também chamada V) devolve uma unidade e acorda uma thread que dorme. Como o teste e a mudança do contador são uma ação indivisível, nenhum acordar se perde.

Um semáforo não é o mesmo que um mutex. Um mutex tem dono: só a thread que o trancou pode destrancá-lo. Um semáforo não lembra dono nenhum, então uma thread pode fazer down e outra pode fazer up. Isso torna o semáforo bom para enviar um sinal. Em Java, a thread A bloqueia em acquire() de um semáforo com 0 permissões, e a thread B depois chama release() para A continuar. Um ReentrantLock recusaria isso, já que B não é o dono.

O acordar perdido

Por que precisamos dessas ferramentas em vez de um if e um sleep? Imagine que um consumidor verifica 'a caixa está vazia' e, antes de conseguir dormir, o produtor põe um item na caixa e grita 'acorda!'. Ninguém está dormindo ainda, então o grito se perde. O consumidor então dorme e talvez nunca acorde. O teste e o ato de dormir precisam ser uma só ação atômica. O semáforo resolve guardando o sinal dentro do seu contador, e o monitor resolve fazendo o teste e o wait sob a mesma trava.

Monitores

Um monitor junta a trava e a espera, então o programador erra menos. Em Java, todo objeto é um monitor com uma trava e um conjunto de espera (uma sala de espera). Dentro de código synchronized:

• wait() libera a trava e põe a thread para dormir na sala de espera. Só quem segura a trava pode chamá-lo.
• notify() acorda uma thread que espera, escolhida de forma arbitrária. notifyAll() acorda todas. Uma thread acordada precisa ganhar a trava de novo antes de seguir.

synchronized String take() throws InterruptedException {
    while (items.isEmpty()) {   // WHILE, nunca IF
        wait();
    }
    return items.removeFirst();
}

Por que while e não if? Os monitores do Java seguem a semântica Mesa: ser notificada só deixa a thread pronta, não lhe entrega a trava na hora. Quando ela recupera a trava, outra thread pode ter levado o item. As regras também permitem um despertar espúrio, um despertar sem nenhuma notificação. Então a thread precisa checar a condição de novo depois de cada despertar. Com if, dois consumidores acordados por um só put() tentariam retirar o mesmo item, e um deles falharia.

Mais uma armadilha: o monitor de um objeto tem uma única sala de espera, mesmo que as threads esperem coisas diferentes (buffer não cheio, buffer não vazio). Com um buffer de uma posição, dois produtores e dois consumidores, um notify() pode acordar uma thread do tipo errado. Ela vê que a sua condição é falsa e volta a dormir, e o sinal se perde, então todos podem acabar dormindo. As saídas são notifyAll(), ou um Lock com um objeto Condition para cada condição.

Operações atômicas, visibilidade e modelos de memória

Um armário com cadeado é lento se você precisa entrar na fila só para somar um a um número. A máquina consegue fazer 'ler, somar, escrever' como um único movimento? Consegue. Uma operação atômica é aquela que as outras threads enxergam como ainda não começada ou já terminada, nunca pela metade. O processador oferece instruções especiais para isso, como TSL (test and set lock) e XCHG (exchange). Elas leem uma palavra de memória e escrevem nela sem que nenhum outro núcleo possa agir no meio. São a base dos mutexes e dos semáforos.

Compare-and-swap

O bloco atômico mais poderoso é o compare-and-swap (CAS): 'se o valor ainda é o que eu esperava, troque pelo novo, e me diga se trocou'. Um incremento sem trava é um laço: ler 41, calcular 42, tentar compareAndSet(41, 42). Se devolver false, alguém mudou o valor no meio, então você recomeça com uma leitura nova. Nenhuma atualização se perde, porque uma escrita baseada em um valor velho é sempre recusada.

int old, next;
do {
    old = value.get();          // lê
    next = old + 1;             // calcula
} while (!value.compareAndSet(old, next)); // repete se mudou

O CAS tem uma armadilha famosa, o problema ABA. Uma pilha sem trava faz pop conferindo que o topo ainda é A. A thread T1 lê top = A, A.next = B e é pausada. Enquanto isso, T2 faz pop de A, pop de B e empilha A de volta. Quando T1 acorda, o topo é A de novo, então o seu CAS funciona, mas B já foi removido, e a pilha agora aponta para um nó morto. O valor parecia igual, mas o mundo mudou. As defesas usuais são um contador de versão colado ao valor, ou nunca reutilizar um nó enquanto alguma thread ainda se refere a ele.

Visibilidade: enxergar o que os outros escreveram

Há um segundo problema, mais silencioso que as atualizações perdidas. Cada núcleo tem uma memória pequena e rápida só sua (um cache), e o compilador e o processador podem reordenar ou adiar escritas. Assim, uma thread pode não ver um valor que outra thread já escreveu. É um problema de visibilidade. Imagine uma thread trabalhadora que roda while (!stopped) { work(); }, em que stopped é um boolean comum. Outra thread faz stopped = true. A trabalhadora pode continuar lendo sua cópia antiga para sempre, e nunca parar.

Um modelo de memória é o conjunto de regras que diz quando uma escrita de uma thread tem garantia de ser vista por outra. Em Java ele é construído sobre a relação happens-before. Estas coisas a criam: liberar e depois pegar a mesma trava, escrever e depois ler um campo volatile, iniciar uma thread e esperá-la com join(). Sem esse vínculo, o programa não tem garantia nenhuma. Go tem o seu próprio modelo de memória, com o mesmo espírito.

• volatile em Java dá visibilidade: toda leitura vê a última escrita. Ele não torna count++ atômico, porque isso ainda é ler, somar, escrever. Duas threads fazendo count++ 1.000 vezes sobre um volatile int podem terminar abaixo de 2.000.
• Em Rust, o Ordering não muda se a operação é atômica. Ele diz que garantias de ordem a operação dá às outras leituras e escritas, de Relaxed (nada além da própria operação) até SeqCst (uma única ordem global). Um contador lido só depois de juntar todas as threads pode usar Relaxed, porque o join já dá visibilidade.

Deadlock, livelock e inanição

Dois carros chegam a uma ponte estreita por lados opostos. Nenhum consegue avançar, e nenhum quer dar ré. Esperam para sempre. Um deadlock é exatamente isso: um grupo de threads, cada uma esperando algo que outra do grupo segura, então nenhuma consegue se mover jamais. O programa está vivo, não usa processador e não faz nada, e não levanta erro nenhum.

As quatro condições

Um deadlock de recursos precisa de quatro condições ao mesmo tempo (são as condições de Coffman). Remova qualquer uma e o deadlock é impossível.

Enxergando um deadlock

Um grafo de alocação de recursos desenha threads e recursos como pontos. Uma seta de um recurso para uma thread significa 'está com'. Uma seta de uma thread para um recurso significa 'quer'. Quando cada recurso tem uma só unidade, um ciclo no grafo significa deadlock.

   quer           com
P1 ------> R2 ---------> P2
 ^                        |
 |         com            | quer
 +-------- R1 <-----------+

Um thread dump do Java mostra a mesma coisa em texto. Para cada thread, lista as travas que ela segura (locked) e a que ela espera (waiting to lock). Siga a cadeia: philosopher-0 segura 0a e espera 0b, philosopher-1 segura 0b e espera 0c, philosopher-2 segura 0c e espera 0a. A cadeia volta à primeira thread, então há uma espera circular, e as três threads do ciclo nunca mais vão se mover.

Quatro estratégias

• Ignorar (o algoritmo do avestruz): fingir que deadlocks não acontecem. É uma escolha de engenharia real quando eles são raros e corrigi-los é caro.
• Detectar e recuperar: deixar os pedidos serem atendidos, procurar de tempos em tempos um ciclo e então se recuperar tirando um recurso, voltando atrás ou matando um processo. Bancos de dados fazem isso com transações.
• Evitar: conhecer o máximo que cada processo pode pedir e atender um pedido só se o estado resultante ainda for seguro. É o algoritmo do banqueiro.
• Prevenir: tornar uma das quatro condições estruturalmente impossível, como na tabela acima.

Um estado é seguro quando existe alguma ordem em que todo processo consegue terminar, mesmo que cada um peça o seu máximo. Exemplo com 12 unidades de um recurso. P1 tem 4 e pode precisar de até 10, P2 tem 3 e pode precisar de até 5, P3 tem 2 e pode precisar de até 8. Unidades em uso: 9, então 3 estão livres. As necessidades restantes são 6, 2 e 6. P2 consegue terminar com suas 2 unidades, devolvendo 3, e então 6 ficam livres. P1 termina, depois P3. O estado é seguro. Agora P1 pede mais 2: sobraria 1 unidade, as necessidades seriam 4, 2 e 6, e ninguém teria certeza de terminar. O banqueiro recusa o pedido por enquanto.

Ordenação de travas

A prevenção mais usada em código real ataca a espera circular. Dê a cada trava uma posição e pegue sempre nessa ordem. Numa transferência bancária, trave primeiro a conta de menor id, seja qual for a ordem dos argumentos. Duas transferências entre as mesmas duas contas travam então na mesma ordem e não conseguem formar um círculo. A ordem precisa vir de uma propriedade fixa (como um id), não da posição numa chamada. E precisa ser respeitada por todo o código: um único caminho que a quebre, muitas vezes escondido num callback chamado com uma trava na mão, pode tornar um ciclo possível de novo. É mais um motivo para não chamar código de fora segurando uma trava.

Livelock e inanição

Duas pessoas se encontram num corredor. As duas dão um passo para a esquerda, depois as duas para a direita, depois para a esquerda de novo. Ninguém está preso, as duas estão ocupadas, e ninguém passa. Isso é um livelock: as threads continuam rodando mas não progridem, porque cada uma reage à outra de um modo que desfaz o próprio passo. Muitas vezes vem de uma cura de deadlock: pegar a primeira trava, tentar a segunda com tryLock() e, se falhar, soltar a primeira e recomeçar imediatamente. Duas threads simétricas podem repetir isso em sincronia para sempre. Uma espera aleatória antes de tentar de novo (backoff aleatório) torna isso improvável, e uma ordem global de travas torna o recuo desnecessário.

Inanição (starvation) é quando uma thread nunca consegue o recurso ou o processador de que precisa, mesmo que o recurso seja liberado várias e várias vezes, porque a política de escolha sempre prefere outras. Diferente do deadlock, o sistema como um todo continua funcionando. A cura é uma política justa: primeiro a chegar, primeiro a ser atendido, ou aumentar a prioridade de quem espera há muito tempo.

Problemas clássicos: produtor-consumidor, leitores-escritores, jantar dos filósofos

Alguns quebra-cabeças aparecem tanto que todo cientista da computação os aprende. Depois de conhecer os três abaixo, você vai reconhecê-los escondidos dentro de programas reais.

Produtor-consumidor

Uma pizzaria: o cozinheiro (produtor) põe pizzas numa prateleira com espaço para N pizzas, e o entregador (consumidor) as retira. Se a prateleira está cheia, o cozinheiro precisa esperar. Se está vazia, o entregador precisa esperar. A prateleira de tamanho fixo é um buffer limitado, e o limite faz o lado mais rápido esperar pelo mais lento.

A solução clássica usa três semáforos. empty conta as vagas livres, full conta os itens e mutex protege a própria prateleira. Para um buffer de 8 posições que começa vazio:

# produtor                 # consumidor
down(empty)                 down(full)
down(mutex)                 down(mutex)
coloca item no buffer       retira item do buffer
up(mutex)                   up(mutex)
up(full)                    up(empty)

Em Java você não precisa construí-lo: ArrayBlockingQueue é um buffer limitado pronto. put() bloqueia enquanto está cheio e take() bloqueia enquanto está vazio, e toda a sincronização fica dentro da classe. É o jeito recomendado.

Leitores-escritores

Um mural compartilhado: vários alunos podem lê-lo juntos, mas quando o professor escreve nele, ninguém mais pode ler nem escrever. Vários leitores ao mesmo tempo é normal; um escritor precisa do mural sozinho. Com preferência para leitores, um novo leitor pode entrar sempre que outros leitores já estão lendo, mesmo que um escritor esteja esperando. Se os leitores continuam chegando antes de o último sair, o escritor espera para sempre: ele sofre inanição. Versões que fazem os novos leitores esperarem atrás de um escritor aguardando corrigem isso, ao preço de menos compartilhamento entre leitores.

Jantar dos filósofos

Cinco filósofos sentam a uma mesa redonda com cinco garfos, um entre cada par. Para comer, cada um precisa dos dois garfos ao seu lado. Um garfo é uma trava.

            P0
       f0        f1
    P4              P1
       f4        f2
         P3  f3  P2

A regra ingênua é 'pegue o garfo da esquerda, depois o da direita'. Se os cinco pegam o garfo da esquerda no mesmo instante, cada um segura um garfo e espera o do vizinho: P0 espera P1, P1 espera P2, e assim por diante até P4 esperar P0. Um círculo de espera, logo um deadlock. As quatro condições estão presentes. Há duas correções famosas:

O semáforo do garçom não protege uma seção crítica. Ele limita quantas threads estão numa região ao mesmo tempo. O seu valor inicial carrega toda a garantia: com 5 permissões ele não restringe nada e o deadlock volta, e com 1 permissão o deadlock some, mas some também todo o paralelismo.

Troca de mensagens e canais

Em vez de dividir uma geladeira e brigar pelos ovos, dê a cada cozinheiro a sua própria bancada e deixe que eles passem pratos uns aos outros. Ninguém toca na mesma coisa, então ninguém precisa de trava. Isso é troca de mensagens. O lema de Go diz bem: 'não se comunique compartilhando memória; compartilhe memória comunicando'. As tarefas não acessam a mesma variável. Elas enviam e recebem valores, e a sincronização faz parte da comunicação.

Em Go o meio de enviar é um canal: um tubo entre goroutines. A convenção é que quem recebe um valor passa a ser o único a usá-lo. Os canais vêm em dois tipos.

Com um canal sem buffer, emissor e receptor precisam se encontrar: quem chega primeiro espera o outro. Esse encontro se chama rendezvous e também sincroniza as duas goroutines. Com um canal com buffer de capacidade 3, três envios passam sem receptor, porque os valores esperam na fila interna. O quarto envio bloqueia até um recebimento liberar uma vaga.

canal de capacidade 3, ninguém recebendo:

envia 1  -> [1][ ][ ]   ok
envia 2  -> [1][2][ ]   ok
envia 3  -> [1][2][3]   ok
envia 4  -> [1][2][3]   BLOQUEIA até um recebimento

ch := make(chan int)   // sem buffer
ch <- 1                // bloqueia: ninguém está recebendo ainda
go func() { <-ch }()   // nunca chega aqui!

Esse exemplo mostra uma regra: num canal sem buffer, o receptor precisa existir antes de o envio poder terminar. Quando todas as goroutines do programa estão bloqueadas, o runtime do Go percebe e encerra o programa com um erro.

Fechando um canal

close(ch) diz 'não virão mais valores', e é trabalho do emissor. Os valores que já estão no canal ainda são entregues. Um laço for v := range ch termina quando o canal está fechado e vazio. Sem close, o laço esperaria para sempre mais um valor.

Um dono, nenhuma trava

Eis um jeito de consertar a corrida do contador sem trava. Uma goroutine é dona da variável count. Oito trabalhadores enviam o valor 1 por um canal 1.000 vezes cada, e a dona soma o que recebe. As atualizações são aplicadas uma por vez, na ordem em que chegam. A variável nunca é lida e escrita no mesmo momento, então a resposta é sempre exatamente 8.000. O canal faz o papel de fila de pedidos.

Rust: enviar move a posse

Em Rust, tx.send(data) move o valor para o receptor. A thread que enviou perde o acesso, e se a linha seguinte tentar data.push(1), o compilador se recusa a compilar o programa. Assim, duas threads nunca alteram o mesmo dado enviado, e não há data race, sem cópia e sem trava.

Modelo de atores e a BEAM

Imagine uma empresa em que cada funcionário tem a sua mesa, o seu caderno e uma caixa de correio. Ninguém lê o caderno de outra pessoa. Se você quer algo, deixa uma carta na caixa de correio dela, e ela lê suas cartas uma de cada vez. Esse é o modelo de atores. Um ator mantém um estado só seu, conversa apenas por mensagens assíncronas e trata as mensagens da sua caixa de correio uma de cada vez. Como nenhum outro ator enxerga o seu estado, não há memória compartilhada para proteger com travas.

O lar mais conhecido dos atores é a BEAM, a máquina virtual do Erlang e do Elixir. Um processo da BEAM não é um processo do sistema operacional. Ele é criado e escalonado pela própria BEAM, tem pilha, heap e coletor de lixo próprios, começa com muito pouca memória e não compartilha dados com os outros. Um sistema pode manter centenas de milhares deles, por exemplo um por conexão aberta.

Como um Agent executa a leitura, o cálculo e a escrita dentro de um único processo, um incremento não pode se intercalar com outro. Oito tarefas que chamam cada uma Agent.update(counter, &(&1 + 1)) 1.000 vezes terminam sempre com exatamente 8.000.

call e cast

• GenServer.call: quem chama espera a resposta. Isso naturalmente reduz o ritmo de quem está pedindo.
• GenServer.cast: a mensagem apenas é colocada na caixa de correio, e quem enviou nunca fica sabendo quando, ou se, ela foi tratada.

Um ator trata uma mensagem por vez, então a sua velocidade máxima é 1 dividido pelo tempo de tratamento. Se um GenServer precisa de 1 ms por mensagem, ele dá conta de no máximo 1.000 mensagens por segundo. Se mil produtores enviam 5.000 por segundo com cast, as 4.000 a mais a cada segundo se acumulam na caixa de correio. Ninguém desacelera os produtores (não há backpressure), então a memória cresce e as respostas ficam cada vez mais atrasadas. As saídas: usar call para os produtores esperarem, dividir o trabalho entre vários processos, ou descartar parte da carga.

Escalonamento justo e let it crash

E se um processo executa um cálculo interminável sem nenhum receive? A BEAM faz escalonamento preemptivo sem interrupções de relógio: ela conta o trabalho de cada processo em reduções (pequenas unidades de trabalho). Quando um processo gasta o seu orçamento, vai para o fim da fila e outro assume o escalonador. Um processo que só calcula não consegue monopolizar um núcleo, e os outros continuam rápidos.

Como os processos não compartilham nada, um processo que falha morre sozinho. Links e monitores avisam os processos interessados, e um supervisor reinicia o filho segundo a sua estratégia. Com one_for_one, só o filho que morreu é reiniciado. A filosofia se chama let it crash (deixe quebrar): separe o código que faz o trabalho do código que trata falhas, e volte a um estado inicial confiável em vez de tentar consertar um quebrado.

A medição mantém 10.000 conexões ociosas, cada uma esperando 30 segundos. Os três modelos passam com folga, com latência mediana abaixo de um milissegundo, porque nenhum deles gasta uma thread do sistema operacional numa conexão que espera. Os números não dizem nada sobre cálculo pesado dentro de um handler, e dependem do que um handler real mantém vivo.

Async, promises e o event loop

O garçom de um restaurante não fica parado ao lado da sua mesa esperando a sopa cozinhar. Ele anota o pedido, vai atender outras mesas e volta quando a cozinha toca o sino. Um garçom consegue cuidar de muitas mesas porque a maior parte do tempo é espera. Um servidor Node.js ou Bun funciona assim. Ele usa uma thread e chamadas de E/S que não bloqueiam. O event loop pergunta ao sistema operacional quais operações ficaram prontas e executa o callback de cada uma, uma por vez. Uma conexão ociosa não segura thread nenhuma, então milhares delas custam pouca memória.

Promises e async/await

Uma promise representa um resultado que existirá no futuro, como o recibo de um bolo que ainda está no forno. Ela nasce pendente e se resolve uma só vez: ou cumprida com um valor, ou rejeitada com um erro. Depois disso o seu estado nunca muda. Funções declaradas async sempre devolvem uma promise, e await pausa só aquela função até a promise se resolver, deixando a thread livre para outros eventos. O código parece sequencial, mas é a mesma cadeia que você escreveria com then.

async function sequential() {
	await sleep(300);
	await sleep(200);
	await sleep(100);          // total cerca de 600 ms
}
async function together() {
	await Promise.all([sleep(300), sleep(200), sleep(100)]); // cerca de 300 ms
}

Com um await por linha, cada espera começa só depois de a anterior terminar, então os tempos se somam. Quando você cria todas as promises primeiro e espera com Promise.all, as esperas se sobrepõem, e o total é o tempo da mais lenta.

As duas filas

O loop tem dois tipos de fila. Macrotarefas são timers e callbacks de E/S. Microtarefas são continuações de promises (o then e a parte depois de um await). Depois de cada trecho de código síncrono, o loop esvazia toda a fila de microtarefas, e só então pega a próxima macrotarefa. Por isso uma promise já resolvida sempre passa na frente de um setTimeout(..., 0).

console.log("A");
setTimeout(() => console.log("B"), 0);        // macrotarefa
Promise.resolve().then(() => console.log("C")); // microtarefa
(async () => { console.log("D"); await null; console.log("E"); })();
console.log("F");
// imprime: A D F C E B

O grande limite: um callback lento bloqueia todo mundo

Cada callback roda até o fim antes de o próximo evento ser tratado. Esperar E/S não segura a thread, mas uma computação síncrona segura. Se um handler calcula por 2 segundos e três requisições chegam no mesmo instante, elas são atendidas uma depois da outra: cerca de 2, 4 e 6 segundos. Em geral, n handlers de t segundos de trabalho de processador levam n vezes t. O event loop dá concorrência para E/S, não paralelismo para cálculo. Para trabalho que mantém o processador ocupado, mande-o para outra thread, como uma worker thread, que conversa com a thread principal por mensagens.

Uma thread só ainda pode ter corrida

Entre dois await o código roda sem interrupção, mas a cada `await` outras tarefas podem rodar. Veja: const current = balance; await audit(); balance = current - amount;. Se withdraw(80) é chamada duas vezes com saldo 100, as duas leem 100, as duas esperam, as duas escrevem 20. O saldo final é 20, não -60. É uma corrida de check-then-act sem nenhuma thread paralela. A solução é não deixar nenhum await entre a leitura e a escrita, ou colocar as operações numa fila para rodarem uma por vez.

A mesma ideia numa janela: Swing

Um programa Java Swing usa o mesmo modelo. Uma única thread, a event dispatch thread (EDT), retira eventos de uma fila e executa os handlers um depois do outro. Toda leitura ou alteração de um componente da janela precisa acontecer nela, então os componentes não precisam de travas. Se o handler de um botão baixa um arquivo por 10 segundos, a janela congela por 10 segundos: não se redesenha nem responde a cliques. O trabalho longo vai para uma thread em segundo plano. O SwingWorker faz isso: doInBackground roda fora da EDT e done roda de volta nela, onde atualizar componentes é seguro.

Pools de threads e backpressure

Um restaurante não contrata um cozinheiro novo para cada prato e o demite depois do prato. Ele mantém uma equipe fixa na cozinha e uma fila de pedidos. Um pool de threads faz o mesmo: um número limitado de threads retira tarefas de uma fila e é reutilizado. Criar uma thread custa tempo e memória, e threads demais brigam pelo processador e esgotam recursos. Num pool o custo de criação é pago uma vez, e a concorrência tem um teto conhecido.

Em Java, Executors.newFixedThreadPool(4) cria um pool com exatamente 4 threads e uma fila de tarefas sem limite de tamanho. Envie dez tarefas longas: 4 rodam, 6 esperam na fila por ordem de chegada. submit não bloqueia, ele enfileira a tarefa e devolve um Future (um ticket para o resultado).

Quanto tempo vai levar?

Uma thread bloqueada em E/S não faz nada, mas continua ocupada. Com n tarefas que esperam t segundos cada, num pool de k threads, o tempo total é cerca de ceil(n / k) vezes t. Doze tarefas que dormem 1 segundo cada em 4 threads precisam de 3 segundos.

Desligando um pool

Um ExecutorService mantém suas threads vivas, então você precisa pará-lo. shutdown é o jeito educado: nada novo é aceito, e o que já foi enviado é concluído. shutdownNow é o jeito imediato: envia interrupt às threads ativas e devolve as tarefas que nunca começaram. A interrupção é cooperativa, então uma tarefa que a ignora continua rodando.

Backpressure

Agora o grande perigo. Um pool de 10 threads consegue terminar 100 tarefas por segundo. Por muito tempo, os produtores enviam 150 por segundo. Com uma fila sem limite, nada os detém. As 50 tarefas a mais a cada segundo se acumulam na fila e comem memória, e a espera de cada nova tarefa cresce sem limite. No fim, o programa fica sem memória. Uma fila sem limite esconde a sobrecarga.

Backpressure (contrapressão) é fazer o sinal 'estou cheio' chegar ao produtor. Um cano de água é uma boa imagem: se a pia está cheia, a torneira precisa diminuir. Há dois jeitos. Uma fila limitada que bloqueia o produtor quando está cheia (como o buffer bloqueante do quebra-cabeça produtor-consumidor). Ou descarte de carga (load shedding): recusar de propósito o trabalho extra, para continuar respondendo bem ao que você aceita.

produtores (150/s)    fila              trabalhadores (100/s)
   ===========>  [limitada: 100] ===========>  10 threads
                      |
               cheia? -> bloqueia o produtor
                         ou rejeita a tarefa

Um pool pode entrar em deadlock sozinho

Duas tarefas externas são enviadas a um pool de 2 threads. Cada tarefa externa envia uma tarefa interna ao mesmo pool e chama get() no seu Future para esperá-la. As duas tarefas externas seguram uma thread e esperam. As tarefas internas ficam na fila e nenhuma thread está livre para rodá-las. Uma espera circular entre as threads e a fila: um deadlock por esgotamento do pool. As curas: não bloquear dentro de tarefas (compor os resultados de forma assíncrona), ou usar pools separados para tarefas externas e internas.

Juntando tudo

Você conheceu muitas ferramentas. Como elas se encaixam? Comece pelo problema. Tarefas concorrentes compartilham algo, ou esperam por algo. Se compartilham dados, você os protege ou para de compartilhá-los.

Erros comuns

• Achar que counter++ é um passo só. São ler, somar, escrever.
• Achar que volatile torna count++ seguro. Ele dá só visibilidade.
• Achar que uma coleção thread-safe torna segura uma sequência de chamadas (check-then-act).
• Chamar run() em vez de start().
• Usar if em vez de while em volta de wait().
• Pegar o mutex antes do semáforo contador no produtor-consumidor.
• Travar em ordens diferentes em lugares diferentes.
• Chamar código desconhecido (um callback) segurando uma trava.
• Filas sem limite, que escondem a sobrecarga até a memória acabar.
• Rodar cálculo pesado no event loop.
• Confiar num teste que passou muitas vezes, ou num detector de corrida que não imprimiu nada.

Uma receita curta

1. Dá para evitar compartilhar? Dê ao dado um só dono e envie mensagens.
2. Se precisa compartilhar, encontre a seção crítica inteira: todos os passos que precisam acontecer como um só.
3. Proteja-a com a ferramenta mais simples: uma trava, ou um atômico se for uma variável só.
4. Se pega várias travas, defina uma ordem global.
5. Limite as filas e o número de threads, para a sobrecarga aparecer cedo.
6. Use um detector de corrida e pense no momento de cada passo, porque só testes não provam que um programa concorrente está correto.

Os mini-projetos deste repositório deixam você ver tudo isso rodando: a corrida do contador (a atualização perdida e suas quatro correções), o jantar dos filósofos (deadlock e duas curas) e as dez mil conexões (event loop, goroutines e processos da BEAM). Para ir além, o livro gratuito The Little Book of Semaphores e o jogo The Deadlock Empire são ótimas formas de praticar.