Introdução

Seja bem-vindo a Programação Paralela e Concorrente, um livro a ser usado na disciplina de mesmo nome. Essa disciplina busca ensinar aos alunos os principais conceitos e técnicas que são úteis ao trabalhar com sistemas concorrentes e paralelos.

Desde o final do século XX, a importância de aprender esses conceitos e técnicas vem crescendo, pois a indústria computacional passou a convergir para arquiteturas, tanto físicas quanto lógicas, que exibem propriedades concorrentes, paralelas e/ou distribuídas. A construção de aplicações e sistemas que satisfaçam os requisitos, cada vez mais exigentes, de performance, responsividade e tolerância a falhas depende do correto entendimento e aproveitamento dessas arquiteturas.

Hoje, qualquer que seja a área de atuação de um profissional de computação — frontend, backend, dados, segurança — ele precisará, no mínimo, estar ciente dos conceitos e técnicas vistos nesse livro, caso queira produzir software da mais alta qualidade.

No entanto, muitos profissionais hoje escolhem fazer vista grossa para essa área da computação, devido ao fato de que os bugs encontrados durante o desenvolvimento de sistemas concorrentes, paralelos e distribuídos estão entre os mais difíceis de entender, capturar e resolver. Enquanto num programa sequencial as mesmas entradas geram as mesmas saídas, em programas concorrentes e paralelos essa garantia não existe, pois a ordem que as tarefas são executadas é definida a cada execução.

Portanto, recomendo que o leitor não faça essa vista grossa, pois os profissionais capacitados para lidar com os problemas mais difíceis são justamente os mais valiosos.

Como este livro é organizado

O livro é dividido em Partes, cada uma contendo um conjunto de capítulos tratando de tópicos próximos entre si.

A Parte I, Conceitos Fundamentais, introduz o vocabulário básico de todo o livro. As partes II à V são focadas, cada uma, em 1 ou mais modelos de concorrência específicos.

A Parte II, Threads e Locks, cobre o modelo de concorrência mais comum e implementado na maioria das linguagens mainstream, e é o modelo que a maioria das pessoas tem em mente quando se fala de concorrência. Consiste em threads do SO se comunicando através do compartilhamento de memória e sincronizando entre si por meio de locks.

A Parte III, Concorrência via Mensagens, cobre dois modelos de concorrência que pertencem a família de modelos baseados em troca de mensagens (message-passing): Communicating Sequential Processes (CSP) e o modelo Actor.

A Parte IV, Programação Assíncrona, cobre um modelo de concorrência baseado numa única thread de execução, mas que é extremamente eficiente para programas que ficam a maior parte do seu tempo esperando por I/O, como servidores web e interfaces de usuário.

A Parte V, Atomics e Concorrência Lock-Free, cobre um modelo de concorrência similar ao da Parte II, por também ser baseado em threads do SO, mas trocando locks por operações atômicas implementadas no hardware.

A Parte VII, Memória Transacional, cobre dois modelos de concorrência baseados na ideia de memória transacional, só que um é implementado a nível de hardware (HTM) e outro a nível de software (STM).

A Parte VIII, Paralelismo via Memória Distribuída, cobre uma abordagem de paralelismo muito utilizada no contexto de High-Performance Computing, baseada no padrão MPI.

A Parte IX, Tópicos Avançados, contém uma variedade de capítulos cobrindo assuntos mais nichados, como a história da concorrência, modelos de concorrência não cobertos previamente, implementação de runtimes e bibliotecas concorrentes, aplicações de concorrência em domínios específicos, análise de arquiteturas concorrentes no mundo real, entre vários outros.

Dentro das Partes do livro, alguns capítulos ou seções são marcados como “Em Detalhe”. Esses apresentam um nível de aprofundamento maior sobre algum assunto, e geralmente assumem um nível de conhecimento maior nos pré-requisitos. Geralmente esses capítulos explicam mecanismos, algoritmos e provas matemáticas. Esse aprofundamento não é essencial para o entendimento do conteúdo, porém é incluído para complementar o conhecimento e dar um entendimento mais profundo para o leitor.

Outros capítulos e seções são marcados como “Interlúdio”. Esses apresentam um conteúdo que destoa daquele que é tratado na Parte e que não foi possível encaixar numa Parte específica.

O que este livro assume

Este livro assume que as Partes I (Conceitos Fundamentais) e II (Threads e Locks) serão lidas de maneira sequencial. Os capítulos dessas partes constroem o modelo mental e a terminologia básica de todo o livro. As partes restantes podem ser lidas na ordem que o leitor desejar.

Este livro assume que o leitor já possui:

• Conhecimento considerável em Programação Imperativa e Orientada a Objetos
• Conhecimento considerável em Arquitetura de Computadores
• Conhecimento básico em Programação Funcional.

Também assume-se que o leitor está fazendo ou já fez um curso de sistemas operacionais. Sistemas operacionais são a aplicação canônica para os conceitos de concorrência, e ambas as áreas se retro-alimentam. Apesar dos conceitos e técnicas de concorrência e paralelismo serem aplicáveis em outros domínios (sistemas de banco de dados, servidores de rede, High-Performance Computing, grid computing, simulação científica, computação gráfica, machine learning, etc), a concorrência como disciplina nasceu diretamente do estudo de sistemas operacionais. Além disso, todos os primitivos que serão estudados, como threads e locks, são implementados pelo kernel do sistema operacional.

Por padrão, os exemplos assumem que serão executados em algum sistema do tipo Unix (Linux, macOS, WSL, etc). Caso seja necessário que um exemplo seja executado num ambiente Windows nativo, será notado em específico.

Finalmente, o livro assume que o usuário sabe ler a documentação técnica de linguagens, bibliotecas, etc. Esse tipo de documentação, inclusive, costuma existir somente em inglês.

Como usar este livro

Este livro busca ensinar os conceitos e técnicas de maneira genérica e tecnologicamente agnóstica. Ou seja, queremos que o conhecimento seja transferível para qualquer tipo de aplicação, linguagem ou framework que o aluno venha a trabalhar.

Isso não significa que não usaremos uma linguagem ou biblioteca(s) específicas ao longo do livro. A maioria dos exemplos está escrita em C/C++ e Kotlin. Alguns capítulos usam Go, Elixir, JavaScript e Clojure, pois essas são linguagens que demonstram melhor certos modelos de concorrência.

Alguns dos exemplos desse livro são escritos nas linguagens Kotlin, Go e Elixir. Essas linguagens não são comumente ensinadas em cursos de programação. Para acelerar o aprendizado, caso você se depare com os exemplos escritos nessas linguagens e não entendeu alguma coisa, recomendo que use os artigos do site Learn X in Y minutes. Esse site apresenta tecnologias sem perder tempo explicando conceitos óbvios para pessoas que já programam:

• Learn Kotlin in Y Minutes
• Learn Go in Y Minutes
• Learn Elixir in Y Minutes

Como rodar os exemplos de código

Os exemplos de código desse livro possuem duas funcionalidades relevantes: eles são executáveis e podem omitir partes do código. No Código P-1, temos um bloco de código em C que calcula a sequência de Fibonacci para um dado índice \( n \):

#include <stdio.h>

/*
 * Retorna o elemento de índice n da sequência de
 * Fibonacci (0, 1, 1, 2, 3, 5, ...).
 */
int fibonacci(int n) {
  int a = 0, b = 1;
  for (int i = 0; i < n; i++) {
    int tmp = a + b;
    a = b, b = tmp;
  }
  return a;
}

int main() {
  int n = 4;
  printf("%d\n", fibonacci(n));
}

Passe o seu mouse (ou dedo) por cima do bloco de código, e verá que dois botões aparecerão no canto superior direito: um para Copiar e outro para Executar o código (com ícone de Play). Clique no botão de executar e veja o que o programa faz.

Ao longo do livro, veremos exemplos de código que serão gradualmente modificados. Fazemos isso para corrigir um bug ou adicionar mais funcionalidades. Geralmente, essas mudanças afetam poucas linhas. Seria desperdício de espaço se repetíssemos o código completo toda vez que fizermos uma mudança pequena. Para evitar isso, alguns exemplos de código possuem partes omitidas, que só são mostradas ao clicar num botão de olhinho para Revelar o código.

Por exemplo, suponha que queremos mudar o Código P-1 para mostrar uma saída mais detalhada. Trata-se de uma mudança apenas na main. O restante do código não é modificado, permanecendo igual ao que era antes. Portanto, omitimos o restante no Código P-2.

#include <stdio.h>

/*
 * Retorna o elemento de índice n da sequência de
 * Fibonacci (0, 1, 1, 2, 3, 5, ...).
 */
int fibonacci(int n) {
  int a = 0, b = 1;
  for (int i = 0; i < n; i++) {
    int tmp = a + b;
    a = b, b = tmp;
  }
  return a;
}
// --restante omitido--

int main() {
  int n = 14;
  printf("Elemento de índice %d da sequência de Fibonacci: %d\n", n, fibonacci(n));
}

Tente passar o mouse ou dedo em cima do bloco de código e clique no ícone de olho. O restante do código será revelado.

Sempre que um código tiver omitido algum trecho, iremos usar --restante omitido-- para indicar.

Apesar da funcionalidade de executar código no livro ser bastante útil, o ambiente que os programas são executados é bem restrito. A concorrência é mais limitada, e não podemos executar programas que leem da entrada. Portanto, eu sempre mostrarei o resultado da execução como se estivéssemos compilando e executando o programa localmente, numa máquina pessoal.

Concorrência e Paralelismo

Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once.

— Rob Pike, co-criador da linguagem Go

Essas duas palavrinhas são geralmente confundidas, até mesmo por profissionais experientes. Espero que alguns exemplos ajudem na distinção entre elas.

Estrutura x Execução

Concorrência é uma propriedade da estrutura de um programa. Um programa é concorrente quando ele é decomposto em múltiplas tarefas, e o tempo de vida (lifetime) dessas tarefas é intercalado.

A imagem abaixo mostra três tarefas que compõem um programa concorrente. Cada tarefa executa durante um tempo, e dá espaço para outra. A tarefa A é a primeira a começar, mas só termina após outras duas terem iniciado.

Paralelismo é uma propriedade da execução de um programa. Um programa é executado em paralelo quando duas ou mais tarefas que o compõem são executadas no mesmo instante de tempo.

Um programa só pode ser paralelo (isto é, executado em paralelo) se tiver um hardware que dê suporte a isso, ou seja, se o programa for executado num computador com múltiplos cores. Por exemplo, um computador com quatro cores permite executar 4 tarefas no mesmo instante de tempo.

Dessa forma, todo programa paralelo é concorrente: Não é possível executar duas “tarefas” de um programa no mesmo instante se o programa já não está estruturado em múltiplas tarefas pra começo de conversa.

Porém, o inverso não é verdade. Nem todo programa concorrente é paralelo. Um programa decomposto em múltiplas tarefas, mas executado num hardware single-core, verá que cada tarefa que o compõe irá executar na CPU por um certo intervalo de tempo, para em seguida ser trocado por outra (Um processo chamado de escalonamento). Os sistemas operacionais mais antigos, executados em hardware single-core, davam a ilusão de muitas tarefas sendo executadas ao mesmo, sendo que eles apenas escalonavam múltiplas tarefas num único processador de maneira muito rápida, imperceptível ao olho humano.

Um programa concorrente, e talvez paralelo

Considere o seguinte programa em pseudocódigo:

Seja L uma lista de itens
Seja Ts uma lista vazia

para cada item X em L:
  crie uma tarefa T
  programe T para processar o item X
  insira T em Ts

para cada tarefa T em Ts:
  inicie T
aguarde todas as tarefas em Ts finalizarem

Não vamos nos preocupar nesse momento com o que exatamente seria essa “tarefa”¹. Vamos focar na seguinte pergunta: Esse programa é concorrente, paralelo ou ambos?

Primeiro, vejamos se é concorrente:

• O programa é estruturado em várias tarefas.
• Cada tarefa é iniciada sequencialmente, mas o pseudocódigo não especifica que elas serão necessariamente executadas ou finalizadas sequencialmente².

Portanto, sim, o programa é concorrente.

Agora, veja que não temos informações suficientes para determinar se o programa é paralelo ou não, pois o pseudocódigo só nos informa a estrutura do programa, não trazendo nenhuma informação sobre o computador em que ele será executado. Como não sabemos se o programa será executado num hardware single-core ou multi-core, não podemos afirmar se ele é paralelo ou não.

1. Posteriormente veremos que uma “tarefa” pode ser implementada como um de vários tipos de unidades de execução: processos, threads, green threads, corotinas, etc. ↩

2. Veremos mais na frente como pode ser feito o escalonamento dessas tarefas. ↩

Por que concorrência e paralelismo?

Como veremos ao longo do livro, programação concorrente e paralela leva a bugs que são mais difíceis de lidar do que aqueles vistos na programação sequencial. Portanto, uma pergunta legítima é: “Por que eu iria escrever programas concorrentes e paralelos em primeiro lugar?”.

A resposta é que programas concorrentes e paralelos melhoram métricas que são importantes para uma aplicação ou sistema. Dentre essas métricas, destacamos as mais relevantes: latência, vazão e responsividade.

Latência (Latency)

Latência é o tempo passado entre uma requisição e o início da resposta correspondente. Formalmente, para uma requisição no tempo \( t_0 \) cuja resposta começa a chegar no tempo \( t_1 \), a latência \( L \) é:

\[ L = t_1 - t_0 \]

Para ver como a concorrência pode melhorar a latência, considere um servidor HTTP sem uso de concorrência:

1. No tempo \( t_0 = 0\ \text{ms} \), uma requisição \( R_1 \) chega ao servidor HTTP. Para respondê-la, o servidor precisa consultar informações no banco de dados.
2. A consulta ao banco de dados leva 8 ms.
3. No instante \( t_1 = 3\ \text{ms} \), uma outra requisição \( R_2 \) é recebida. Esta, no entanto, não requer consulta ao banco de dados. Apesar disso, o servidor está bloqueado aguardando a conclusão da consulta para \( R_1 \). A CPU está ociosa.
4. Em \( t_2 = 8\ \text{ms} \), a consulta ao banco de \( R_1 \) é concluída e o servidor emite a resposta.
5. O servidor analisa \( R_2 \), monta a resposta e a envia em \( t_3 = 10
   \text{ms} \).

Seja \( L(R) \) a latência de uma requisição \( R \). Temos que \( L(R_1) = 8\ \text{ms} \) e \( L(R_2) = 7\ \text{ms} \).

Agora, considere um servidor HTTP com uso de concorrência:

1. No tempo \( t_0 = 0\ \text{ms} \), uma requisição \( R_1 \) chega ao servidor HTTP. Para respondê-la, o servidor precisa consultar informações no banco de dados.
2. A consulta ao banco de dados leva 8 ms. O servidor cria uma tarefa que fica aguardando até receber uma resposta do banco, ficando livre para atender outras requisições.
3. No instante \( t_1 = 3\ \text{ms} \), uma outra requisição \( R_2 \) é recebida. Esta, no entanto, não requer consulta ao banco de dados. Como o processo principal do servidor está livre, ele recebe a nova requisição e cria uma nova tarefa para atendê-la.
4. Em \( t_2 = 5\ \text{ms} \), a tarefa para \( R_2 \) finaliza e o servidor envia uma resposta.
5. Em \( t_2 = 8\ \text{ms} \), a consulta ao banco de \( R_1 \) é concluída e o servidor emite a resposta.

Agora temos que \( L(R_1) = 8\ \text{ms} \) e \( L(R_2) = 5 - 3 = 2
\text{ms} \). Portanto, houve melhoria na latência de \( R_2 \), ainda que só tenhamos introduzido concorrência e não necessariamente paralelismo.

Vazão (Throughput)

Vazão é a taxa que um sistema completa trabalho, num dado intervalo de tempo. É a quantidade de operações (ou dados) processados por unidade de tempo.

Para \( N \) operações completadas num intervalo de tempo \( \Delta t \), a vazão \( V \) é:

\[ V = \frac{N}{\Delta t} \]

Considere um programa que deve redimensionar 100 imagens, onde cada redimensionamento leva 10 ms de computação na CPU, seguidos de 40 ms de I/O de disco para escrever o resultado.

Versão sequencial/serial: cada imagem leva 50 ms fim-a-fim e a próxima imagem não pode começar a ser processada até que a anterior seja completamente escrita no disco. Portanto, a vazão é de:

\[ V_{serial} = \frac{100}{100 \cdot 50\ \text{ms}} = \frac{100}{5000\ \text{ms}} = 20\ \text{imagens/s} \]

Note que durante 80% do tempo de relógio decorrido, a CPU fica ociosa.

Versão concorrente: Enquanto a imagem \( n \) está sendo escrita no disco (I/O, portanto a CPU não é utilizada), a CPU pode começar a redimensionar a imagem \( n + 1 \):

Nesse caso, a vazão é de: \[ V_{concorrente} = \frac{100}{10 + 100 * 40\ \text{ms}} = \frac{100}{4010\ \text{ms}} \approx 24.9\ \text{imagens/s} \]

representando um aumento de quase 25% sobre o inicial.

Responsividade

Responsividade é a propriedade de um sistema pela qual ele reconhece e reage a interações e mudanças, provendo feedback num intervalo de tempo adequado. Não é medida matematicamente, mas sim perceptualmente.

Considere uma aplicação desktop, como um editor de texto (Word, LibreOffice Writer, etc). A funcionalidade de “Exportar PDF” em um documento grande envolve uma série de etapas: inclusão de fontes, compressão de imagens, resolução de layout, etc. Isso custa vários segundos de computação.

Versão sequencial: A exportação roda na mesma tarefa (na mesma thread, como veremos no próximo capítulo) que processa os eventos de interação do usuário e atualiza a interface gráfica. Enquanto o PDF está sendo renderizado, a aplicação não pode processar quaisquer eventos de interação, fazendo com que:

• A janela para de atualizar a interface gráfica
• Os cliques começam a se enfileirar silenciosamente
• O cursor congela
• O sistema operacional muda a cor da janela da aplicação para cinza, indicando que ela “Não está respondendo”
• O usuário não sabe se a exportação está em processamento, travou ou deu erro, fazendo com que ele clique no botão novamente ou mate forçadamente a aplicação

Versão concorrente: A aplicação delega a renderização do PDF para uma tarefa em background e imediatamente retorna o controle para a tarefa responsável pela interface de usuário (UI). Agora, enquanto o PDF está sendo renderizado:

• A tarefa de UI instantaneamente reconhece a ação do usuário — um indicador de progresso (barra de progresso, spinner ou mensagem de status) é exibido.
• O usuário pode continuar interagindo com o documento e outros menus. A aplicação permanece viva, recebendo entrada.
• A tarefa em background continuamente reporta progresso, de forma que o usuário continuamente veja o resultado progredindo.
• Quando a renderização finaliza, a tarefa em background sinaliza para a tarefa de UI, que exibe uma notificação de “PDF salvo”.

Essa é uma demonstração de um padrão de concorrência muito comum: a concorrência desacopla uma computação custosa do ciclo de feedback exposto ao usuário.

Por que NÃO concorrência e paralelismo?

Concorrência e paralelismo não são ingredientes que você aplica em um software após ele já ter sido construído. Ambos são eixos de design que moldam toda a arquitetura de um sistema. Forçar concorrência num sistema que não foi projetado para tal é um dos esforços de engenharia mais custosos que podemos imaginar.

Nessa seção, listamos as principais desvantagens que acompanham concorrência e paralelismo.

Não-Determinismo

Conforme veremos mais à frente, todo programa concorrente cria unidades de execução (processos, threads, corotinas) cuja execução no hardware é escalonada. Esse processo de escalonamento faz com que um programa concorrente tenha uma certa quantidade de intercalações possíveis.

Por exemplo, veja o trecho de código abaixo, onde x é uma variável global:

x = x + 1

Apesar de se tratar de uma única linha de código, um compilador simples transforma essa linha de código em 3 instruções baixo-nível:

mov rax, [endereço de x] ; 0: lê x
add rax, 1               ; 1: incrementa
mov [endereço de x], rax ; 2: guarda o resultado em x

Assuma que criamos duas unidades de execução (threads, por exemplo), A e B, cada uma executando esse mesmo trecho de código, num computador single-core. Usamos A0, A1 e A2 para as instruções executadas por A e B0, B1 e B2 para as instruções executadas por B.

Como o escalonador (o programa que realiza o escalonamento dessas threads) pode interromper uma thread entre quaisquer duas instruções adjacentes, temos os seguintes possíveis escalonamentos:

Suponha que o valor inicial de x é 0. Com duas threads, cada uma incrementando uma mesma variável, o esperado é que o resultado final de x seja 2. Uma intercalação correta, que produz o resultado esperado, é A0, A1, A2, B0, B1, B2:

Uma outra intercalação possível, mas que produz um resultado diferente do esperado, é A0, B0, A1, B1, A2, B2:

Essa intercalação ilustra um bug de concorrência conhecido como lost update: Uma thread lê o valor antigo de x, e um incremento (aquele realizado por A) é perdido.

Esse exemplo ilustra talvez a maior dificuldade de sistemas concorrentes: Temos, para um mesmo código-fonte, um conjunto considerável de intercalações possíveis, e um subconjunto dessas intercalações causa erros na lógica do nosso programa. E, pior ainda, essa intercalação é não-determinística: o bug só se manifesta quando o escalonador produz certas intercalações — o que pode ocorrer uma vez em um milhão de execuções, ou apenas numa máquina com 96 cores, ou somente num certo padrão de acesso à memória.

Para controlar o impacto que esse não-determinismo pode ter sobre a corretude do programa, várias técnicas podem ser adotadas, que vão desde mecanismos de sincronização até utilizar um modelo de concorrência baseado em troca de mensagens.

Complexidade

A intercalação de um programa concorrente não é apenas não-determinística. A quantidade de intercalações possíveis escala exponencialmente conforme seu programa aumenta em tamanho ou concorrência.

Vimos que para um trecho tão simples como x = x + 1, o compilador gera 3 instruções de CPU. Com duas threads e 3 instruções, temos 20 intercalações possíveis. Dessas, apenas duas produzem o resultado esperado.

De maneira geral, se tivermos \( m \) threads, cada uma executando uma quantidade \( n_i \) de instruções, teremos

\[ \frac{(\sum_{i = 1}^{m} n_i)!}{\prod_{i = 1}^{m} n_i!} \]

intercalações possíveis.

Vamos ver alguns valores para ter uma noção de como isso explode. Aqui, todas as \( m \) threads executam a mesma quantidade de instruções \( n \).

Para qualquer código concorrente não-trivial, é impossível raciocinar sobre o código tentando enumerar as intercalações possíveis. Felizmente, já foram desenvolvidos outros métodos, tanto intuitivos quanto formais, de raciocinar sobre programas concorrentes de maneira eficiente.

Heisenbugs

O não-determinismo provoca o surgimento de Heisenbugs: Bugs que desaparecem ao tentar observá-los.

Inserir mensagens de logs afeta o tempo de execução e o escalonamento. Executar num debugger introduz pausas, que afetam o escalonamento. O próprio ato de instrumentar o sistema pode alterar o escalonamento que revelou o bug.

Na verdade, o programador nem precisa alterar ou instrumentar o programa para que o escalonamento possa ser mudado. Duas execuções seguidas, do mesmo código, sem depuração, podem seguir escalonamentos diferentes, simplesmente porque o sistema operacional assim o fez.

Overhead

Enquanto as outras seções detalharam dificuldades relacionadas à corretude e depuração, é importante lembrar que até mesmo programas concorrentes corretamente implementados trazem um custo. Criar, manter e coordenar diferentes tarefas sempre vem com algum custo envolvido:

• Context switches (operação realizada pelo sistema operacional ao trocar a tarefa em execução) custam milhares de ciclos de CPU.
• Mecanismos de sincronização. A utilização de locks, como mutex, envolvem o uso de operações atômicas, execução de algoritmos complexos no kernel do SO e invalidação de linhas de cache dos cores.
• Contenção e serialização. Quando duas ou mais tarefas disputam por um mesmo recurso (um mutex, um canal, um arquivo, um socket, etc), todas as tarefas envolvidas na contenção ficam paradas até que a detentora atual do recurso o libere. Na prática, a disputa por locks e outros recursos faz com que uma fração da execução do programa seja inerentemente sequencial, limitando o ganho máximo de velocidade.¹
• Cache thrashing e false sharing. Quando muitas threads disputam pelo mesmo cache, aumenta a probabilidade delas causarem o descarte de dados muito utilizados por threads irmãs.
• Consumo de memória. Threads são implementadas no kernel do sistema operacional, e toda a estrutura necessária (stack, estruturas de dados, file descriptors, sockets, etc) coloca uma pressão no uso de memória por parte do sistema operacional. Quando o quantitativo de threads é muito grande, essa pressão pode acabar forçando o SO a realizar swap, prejudicando imensamente a performance.

1. No Capítulo 2 veremos como a Lei de Amdahl formaliza isso. ↩

Conclusão

Devido a limitações físicas descobertas há mais de 20 anos¹, caso um programa precise ficar mais rápido, ele só pode fazer isso se aperfeiçoar o uso de pelo menos um dos 2 pilares das arquiteturas de hardware modernas: a hierarquia de memória e os múltiplos núcleos do processador.

Portanto, apesar da concorrência ter seus prós e contras, já se foi o tempo em que programas sequenciais garantidamente ficavam mais rápidos com a chegada da próxima geração de CPUs. Hoje, a evolução da performance e escalabilidade exige pensar em projetar sistemas cada vez mais concorrentes. Nessa disciplina, veremos justamente como fazer isso.

1. A principal dessas descobertas foi o fim da escala de Dennard, que é explicada em detalhes no capítulo História da Concorrência e Paralelismo. ↩

Suporte do SO à Concorrência

Como dito na Introdução, os estudos de concorrência e sistemas operacionais se retro-alimentam:

• As primeiras descobertas sobre concorrência surgiram durante o desenvolvimento dos primeiros sistemas operacionais.
• Um sistema operacional é o tipo de sistema mais complexo e concorrente que alguém pode chegar a trabalhar.
• Os conceitos e técnicas desenvolvidos nos estudos de concorrência têm como principal domínio de aplicação justamente os sistemas operacionais.

Além disso, todo e qualquer programa concorrente eventualmente acaba desembocando no sistema operacional. É o SO que decide qual código roda em qual núcleo e em que momento; que media o acesso aos dispositivos de I/O e que fornece os primitivos fundamentais (processos, threads, escalonamento, sincronização, interfaces de I/O) a partir dos quais qualquer código concorrente é montado.

Portanto, para começarmos falar de concorrência precisamos estabelecer conceitos que surgem justamente na área de sistemas operacionais. Nesse capítulo, vamos entender, num nível suficiente para esse livro, os seguintes conceitos:

• Processos
• Threads
• Escalonamento

Unidades Escalonáveis: Processos e Threads

Tanto processos quanto threads atuam como tarefas: construtos do sistema operacional que podem ser escalonados. Isto é, na presença de vários processos e threads, apenas uma parte deles é selecionada para executar no hardware. Ao longo do tempo, uma tarefa dá lugar (voluntariamente ou não) para outra ser executada.

A diferença entre esses construtos é no nível de isolamento entre eles, o que determina o poder e os riscos que cada um possui.

Processos

Processos são tarefas independentes cujo contexto de execução é altamente isolado.

Dois processos não podem acessar uma mesma região de memória. Cada processo tem seu próprio:

• Espaço de endereçamento virtual
• Tabela de file descriptors (arquivos, pipes, sockets, etc)
• Conjunto de signal dispositions
• Conjunto de mapeamentos de memória
• Heap e segmentos estáticos de memória (.text, .data, .bss)
• ID (Process ID ou PID)

Todos esses componentes são isolados entre dois processos distintos. Isto significa que quando um processo A escreve algo no endereço 0x7fff, ele está escrevendo numa página de memória física que um outro processo B não pode ver (imposto pela Memory Management Unit, MMU, da CPU).

Esse isolamento tem prós e contras.

• O principal pró é que se um processo crashar — ao dereferenciar um ponteiro inválido ou corromper seu heap — ele não irá afetar outros processos, devido ao isolamento.
• O principal contra é que a comunicação entre dois processos (conhecida como IPC, Inter-Process Communication) é mais trabalhosa de ser feita, tanto em termos de codificação quanto de performance.

Threads

Threads (também chamadas de threads nativas, de kernel ou do SO, para distinguir de threads de usuário) são tarefas que vivem dentro de um processo e cujo contexto de execução é pouco isolado.

Diferentemente de processos, duas threads de um mesmo processo podem acessar uma mesma região de memória. De maneira geral, todas threads em um mesmo processo compartilham:

• O mesmo espaço de endereçamento virtual
• O mesmo heap e segmentos estáticos de memória
• A mesma tabela de file descriptors
• O mesmo conjunto de signal dispositions

Isso não quer dizer que as threads compartilham tudo. Cada thread tem um estado próprio, separado das outras threads no mesmo processo. Esse estado inclui:

• Uma pilha. Permite que cada thread execute funções de maneira independente.
• Um conjunto de registradores, incluindo os registradores PC (Program Counter) e SP (Stack Pointer). Permite que cada thread execute uma sequência de instruções individual.
• Contexto de escalonamento do kernel. Permite que cada thread seja escalonada independentemente pelo SO.
• Um ID (Thread ID ou TID).

Todo processo tem pelo menos uma thread, que é a thread principal.

Prós e Contras

Esse isolamento menor entre threads apresenta prós e contras.

• O principal pró é que a comunicação entre threads é muito mais fácil de ser feita do que entre processos. Como as threads compartilham o mesmo heap e variáveis globais, a escrita de uma thread numa dessas localizações é visível para todas as outras threads do mesmo processo.
• Além disso, outro pró é que, como a criação de uma thread re-aproveita a maior parte das estruturas de dados usadas pelo processo, esse processo é consideravelmente mais barato (em termos de ciclos de CPU e memória).

No entanto, esse “poder” é justamente o que permite alguns dos maiores riscos quando falamos de threads:

• A memória compartilhada entre threads significa que duas escritas na mesma localização podem gerar bugs de concorrência, que levam o programa a ter um comportamento fora do esperado, como veremos mais pra frente.
• Para evitar esses bugs de concorrência, são introduzidos mecanismos de sincronização, que restringem o acesso a regiões de memória específicas, o que pode gerar os custos de overhead mencionados no Capítulo 1.
• A memória compartilhada também significa que se um thread corromper o heap do processo, todas as threads serão afetadas.

Simultaneous Multithreading (SMT)

Geralmente, cada thread ocupa um único núcleo do processador num dado instante. No entanto, uma tecnologia conhecida simultaneous multithreading (SMT) ou hardware multithreading permite que um único núcleo da CPU exiba para o sistema operacional duas ou mais “threads”. É por isso que em, algumas máquinas, quando o sistema operacional lista o número de threads que ele pode rodar ao mesmo tempo, esse número acaba sendo maior do que a quantidade de núcleos no processador.

Por exemplo, abaixo está o resultado do lscpu (um programa de linha de comando do Linux que retorna informações sobre as CPUs do computador) na minha máquina pessoal:

$ lscpu
Architecture:                x86_64
  CPU op-mode(s):            32-bit, 64-bit
  Address sizes:             39 bits physical, 48 bits virtual
  Byte Order:                Little Endian
CPU(s):                      16   # <-- o SO vê 16 threads/"CPUs"
  On-line CPU(s) list:       0-15
Vendor ID:                   GenuineIntel
  Model name:                13th Gen Intel(R) Core(TM) i7-13620H
    CPU family:              6
    Model:                   186
    Thread(s) per core:      2   # <-- temos duas threads por núcleo
    Core(s) per socket:      8   # <-- temos 8 núcleos físicos
    Socket(s):               1

Escalonamento

Vimos que processos e threads são as unidades básicas que um sistema operacional utiliza para organizar as tarefas que ele manda para o hardware executar. No entanto, a maioria dos computadores para usuários comuns atualmente têm de 4 a 8 núcleos. Mesmo com SMT, isso limita a quantidade de threads em paralelo nesses computadores a até 16 threads.

Se você abrir o Gerenciador de Tarefas do seu computador, você vai ver que existem muito mais processos e threads em execução do que 16. Portanto, além de criar as abstrações para representar tarefas, o sistema operacional também precisa responder a seguinte pergunta: quais tarefas serão executadas pelo hardware, num dado momento?

A resposta para essa pergunta é o escalonamento: um dos processos mais importantes que o sistema operacional realiza, e que determina a execução de todos os programas do computador.

O escalonamento é realizado por um escalonador: um processo que roda no kernel do sistema operacional e segue algum algoritmo para decidir qual será a próxima tarefa a ser executada.

O escalonamento pode ser feito de maneira preemptiva, não-preemptiva/cooperativa ou mista. Esse tipo de escalonamento tem impacto direto em como o programador escreve código.

Escalonamento Preemptivo

No escalonamento preemptivo, o escalonador pode interromper a tarefa em execução a qualquer momento para trocá-la por outra tarefa.

Vamos ver o funcionamento desse tipo de escalonamento. Para simplificar, vamos supor que estamos numa máquina com um único núcleo de CPU, sem SMT.

Um escalonador preemptivo inicialmente cria um temporizador que “apita” a cada período de tempo (por exemplo, 1 ms)¹. Esse temporizador define uma fatia/quantum de tempo, durante a qual cada tarefa irá executar na CPU.

Sempre que o temporizador apita, o escalonador força a interrupção da tarefa em execução — independente se ela quer parar ou não — salvando seu estado e trocando para a próxima tarefa.

Esse processo em que o escalonador salva o estado da tarefa interrompida e troca para a próxima tarefa é conhecido como troca de contexto (context switch), que tem um custo considerável de ciclos de CPU e de memória. Um context switch pode acontecer entre quaisquer duas instruções de uma tarefa.

Em suma, no escalonamento preemptivo o escalonador está no controle. Isso permite que ele garanta uma distribuição justa de tempo de CPU e robustez contra processos bugados ou maliciosos que tentem consumir a CPU sem parar.

Ilustração do escalonamento preemptivo com 3 tarefas. “int.” = interrupção

A maior parte dos sistemas operacionais adota o escalonamento preemptivo para processos que não são do kernel, isto é, processos a nível de usuário, para evitar que um processo mal-comportado deixe de ceder tempo de CPU para outras tarefas.

Escalonamento Cooperativo/Não-preemptivo

No escalonamento cooperativo, é a própria tarefa que escolhe quando vai interromper sua execução e liberar o controle para o escalonador.

Para indicar ao escalonador que interrompa a execução, as tarefas usam uma função (ou keyword) geralmente chamada de yield ou await. Essa função é inserida no código que o programador escreve. Veja exemplos em Python e Lua:

async def tarefa(url: str) -> str:
    print(f"Consultando {url}...")
    res = await client.get(url)  # <-- yield aqui
    return res.text

function tarefa(url)
    print("Consultando " .. url .. "...")
    local res = coroutine.yield(http_get(url)) -- yield aqui
    return res.body
end

Um padrão muito comum é que as tarefas façam o yield enquanto esperam algum resultado de I/O ficar pronto, como ao ler algo do disco, enviar uma mensagem num socket, etc.

Nesse modelo, o escalonador confia que as tarefas não irão se comportar mal. Ou seja, que elas não irão “monopolizar” a CPU ao não chamar o yield em momentos oportunos. Uma tarefa que não libera o controle irá deixar todas as outras tarefas em inanição (starvation).

Após um yield, o escalonador ainda faz um context switch, porém este é muito menos custoso de se realizar, pois como o yield funciona como uma chamada de função, ele só precisa salvar um subconjunto dos registradores do programa.²

Comparação

Escalonamento híbrido

A maioria dos sistemas operacionais e runtimes não utilizam um escalonamento que é 100% preemptivo ou 100% cooperativo, mas sim alguma forma híbrida.

Sistemas operacionais geralmente adotam o modelo preemptivo para processos e threads no user-space, mas internamente no kernel utilizam o modelo cooperativo em certos contextos.

Alguns runtimes, como os de Go e Erlang, usam um modelo cooperativo, mas com um limite de tempo ou de chamadas de função que, quando atingido, força a preempção.

1. No caso do escalonador do sistema operacional, esse temporizador é implementado no hardware do computador. ↩

2. O motivo pelo qual um context switch após um yield é mais eficiente do que um preemptivo é explicado na seção Comparando context switches e também aqui. ↩

Escalonamento no user-space

Apesar da maior parte desse capítulo ter focado em conceitos do sistema operacional, que são implementados no kernel-space, o escalonamento é um processo que pode ser implementado no user-space.

Quando feito dessa forma, o escalonador é geralmente implementado nativamente em algum runtime (é o caso de Go e Erlang) ou numa biblioteca (Python, C++). A unidade escalonada não são processos ou threads do sistema operacional, mas sim objetos no user-space que possuem um contexto de execução, lembrando threads e processos.

Algumas linguagens e bibliotecas implementam um event loop, um programa no user-space responsável por gerenciar eventos e tarefas que reagem a esses eventos. Todo event loop contém um escalonador, que obviamente é implementado no user-space.

A principal motivação para implementar escalonamento no user-space é que o custo computacional e de memória é consideravelmente menor se comparado ao escalonamento no kernel-space. Com escalonamento no user-space, um programa pode chegar a milhões de tarefas concorrentes. A razão por trás disso está na seção Comparando context switches.

Veremos ao longo do livro que escalonamento no user-space é a base do modelo de concorrência de muitos runtimes.

Unidades e Modelos de Concorrência

Os próximos capítulos desse livro são organizados ao redor de vários modelos de concorrência. Esses modelos definem uma unidade de concorrência, utilizada para representar uma “tarefa”, e as regras sobre como essas unidades interagem e são escalonadas. Esse capítulo explica o que são unidades e modelos de concorrência, e dá exemplos de cada um, que serão estudados ao longo do livro.

Unidade de Concorrência

Uma unidade de concorrência é a abstração usada para representar as tarefas concorrentes de um programa e que serão escalonadas. Essa abstração costuma ser implementada como um tipo que pode ser instanciado pelo programador. Certas unidades não se parecem com um tipo, podendo ser uma função, mas por trás dos panos elas ainda são implementadas como um objeto.

Alguns exemplos que iremos explorar nos próximos capítulos:

• Uma thread do SO é a unidade de concorrência mais primitiva de todas, escalonada pelo próprio sistema operacional.

  Implementações: threading em Python; java.lang.Thread na JVM; System.Threading.Thread em .NET; std::thread em C++; <pthread.h>/pthread_t e <threads.h>/thrd_t em C/C++; etc.

• Uma green thread (também chamada de user-space thread ou thread leve) é uma unidade de concorrência implementada e escalonada no user-space, apresentando uma semântica similar a de uma thread (memória compartilhada).

  Uma green thread pode ser executada em uma de \( N \) threads do SO possíveis, e uma thread do SO pode executar uma de \( M \) green threads possíveis, definindo assim um mapeamento \( N:M \) entre ambas as unidades de concorrência.

  Implementações: goroutines em Go; virtual threads em Java; ThreadId em Haskell; greenlet em Python; etc.

• Um processo do SO é uma unidade de concorrência escalonada pelo próprio sistema operacional, com isolamento de memória entre dois ou mais processos. A comunicação entre processos é feita usando técnicas de Inter-Process Communication (IPC), como signals, pipes e filas.

  Implementações: multiprocessing em Python, std::process e ipc-channel em Rust; <unistd.h> e <spawn.h> em C/C++; Boost.Process e Boost.Interprocess em C++; java.lang.Process na JVM; os e os/exec em Go; System.Diagnostics.Process e System.IO.Pipes em .NET; child_process e cluster em Node.js; pcntl_*, posix_*, proc_* e msg_* em PHP; Foundation.Process e Foundation.Pipe em Swift; etc.

• Um green process (também chamado de user-space process, ator ou actor)¹ é uma unidade de concorrência implementada e escalonada no user-space, apresentando uma semântica similar a de um processo do SO (memória isolada).

  Implementações: processos da BEAM, lunatic::process em WebAssembly, dart:isolate em Dart, Cloudflare Workers, etc.

• Uma corotina é uma unidade de concorrência implementada e escalonada no user-space, e sempre escalonada de maneira cooperativa (daí o nome).

  Uma corotina é uma generalização de uma rotina/função: enquanto uma rotina/função tradicional tem um ponto de entrada e um ponto de saída, uma corotina pode ter vários. Como são escalonadas cooperativamente, o próprio programador decide quando suspender uma corotina, usando uma função ou keyword geralmente chamada yield/await.

  Podemos dividir corotinas entre stackful e stackless.

  • Uma corotina stackful é uma corotina que possui uma pilha de chamadas (call stack) completa. O runtime aloca memória (entre 4 KB-1MB) para construir a pilha, e gerencia ela ao longo da vida da corotina. Isso permite que a corotina seja suspensa em qualquer profundidade na cadeia de chamadas de funções, e não apenas a partir da função mais externa. Uma corotina stackful é equivalente a uma green thread cooperativa.

    Implementações: coroutine.* em Lua (a implementação mais famosa), goroutines em Go (quando cooperativas), virtual threads em Java, <ucontext.h> em C/C++.

  • Uma corotina stackless é uma corotina que não carrega sua própria pilha de chamadas. Invés disso, o compilador transforma a corotina num struct, que funciona como uma máquina de estados. Cada chamada de yield/await é transformada numa transição de estado.

    Apenas as variáveis locais que persistem entre pontos de suspensão (isto é, que são usadas em ambos os lados de um yield/await) são salvas em memória, mais especificamente num pequeno frame do heap (entre 512 e 1024 bytes).

    Por não possuir uma pilha de chamadas, uma corotina stackless só pode ser suspensa no nível mais alto do seu próprio corpo, nunca de dentro de uma chamada de função aninhada. Para mais detalhes de como corotinas stackless funcionam por baixo dos panos, veja Em Detalhe: Corotinas.

    Corotinas stackless são a principal forma de implementar a sintaxe async/await no modelo de programação assíncrono.

    Implementações: asyncio/coroutine em Python, corotinas em C++20, async/await em várias linguagens (C#, Rust, JavaScript, Dart, Swift, Python, Zig), generators em várias linguagens (Python, JavaScript, PHP), Amp e ReactPHP em PHP.

• Uma fiber é uma unidade de concorrência, geralmente equivalente a uma corotina stackful.

  Implementações: Swoole\Coroutine e \Fiber em PHP, Fiber em Ruby, Boost.Fiber em C++, funções de fibers (ConvertThreadToFiber, CreateFiber, SwitchToFiber, etc) expostas na API Win32 em C/C++ (<windows.h>), node-fibers em Node.js, etc.

1. O nome “Ator” deriva do modelo de concorrência chamado “modelo de Ator”, que é muito associado com green processes, em especial por causa da implementação mais famosa desse, presente na BEAM. No entanto, nem todas implementações do modelo de Ator implementam Atores com green processes. Dois exemplos disso são Ractors (implementação da linguagem Ruby) e Akka/Pekko (uma biblioteca e runtime que implementa o modelo de Ator na JVM), pois os Atores de ambas as implementações não tem um isolamento de memória no heap, nem possuem um garbage-collector por ator. O isolamento é feito por convenção ou por restrição da API pública, mas ele não existe a nível de memória. ↩

Modelos de Concorrência

Um modelo de concorrência é uma combinação de três coisas:

1. Uma unidade de concorrência (representando tarefas)
2. A forma como essas tarefas serão escalonadas
3. As regras de como duas ou mais tarefas podem coordenar entre si

Uma linguagem de programação pode tranquilamente oferecer mais de um modelo para o programador, que poderá escolher um ou mais modelos para resolver algum problema.

Vamos ver dois modelos de concorrência para ilustrar essa definição. Essas descrições estão longe de serem detalhadas, pois o detalhamento virá nos capítulos dos respectivos modelos.

Threads e Locks

Esse modelo é composto de:

1. Unidade de Concorrência: Threads do SO
2. Escalonamento: Preemptivo e realizado no kernel-space.
3. Coordenação: Memória compartilhada + Locks

As threads se comunicam através de memória compartilhada e, para controlar o acesso a essa memória, realizam sincronização por meio de locks (Mutex, por exemplo).

Concorrência Lock-Free

Esse modelo é composto de:

1. Unidade de Concorrência: Threads do SO
2. Escalonamento: Preemptivo e realizado no kernel-space.
3. Coordenação: Memória compartilhada + Atomics

Nesse caso, é praticamente o mesmo modelo que o anterior. No entanto, ao invés de sincronizarem o acesso à memória por meio de locks, são utilizadas operações atômicas (também chamadas de atomics).

As próximas Partes do livro irão focar em cada modelo de concorrência relevante, aprendendo o jeito correto de raciocinar e programar em cada modelo, e vendo quando usar (ou não) cada um deles.

Criando Threads

Vamos ao modelo de concorrência mais fundamental: threads do SO como unidade de concorrência, memória compartilhada como comunicação, locks como sincronização.

Threads são um construto do sistema operacional: vivem no kernel-space. Mas para usá-las, a linguagem de programação precisa oferecer um tipo que represente essas threads no user-space. Cada linguagem faz isso de um jeito: C expõe a API POSIX direto, C++ embrulha em classes com semântica de ownership, Java e Kotlin usam objetos gerenciados pelo garbage collector, e Python carrega junto uma restrição peculiar (o GIL) que muda o que threads conseguem fazer na prática.

Nos próximos sub-capítulos, vamos criar threads em cada uma dessas linguagens.

Pthreads (POSIX Threads)

O padrão POSIX (Portable Operating System Interface) é uma coleção de interfaces de programação (APIs) que um sistema operacional deve implementar para ser considerado POSIX-compliant. Essas APIs são acessíveis por meio da linguagem de programação C¹.

Esse padrão foi criado para que quando um programador escrevesse código que utilizasse as funcionalidades comuns de um sistema operacional (system calls, gerenciamento de processos e threads, utilitários de sistema, shells, etc), esse código funcionasse em qualquer sistema operacional POSIX-compliant.

Um dos componentes da POSIX é a API para criar e gerenciar threads do SO, chamada de Pthreads. Essa API é acessível em C via <pthread.h>.

Criando uma única thread com pthread_t e pthread_create

Criar uma thread é simples:

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

void *greet(void *arg) {
  char *name = (char *)arg;
  printf("Hello from %s!\n", name);
  return NULL;
}

int main() {
  pthread_t my_thread;
  pthread_create(&my_thread, NULL, greet, "thread");
}

Vamos entender o código por partes:

1. Primeiro, para podermos usar as funções da API Pthreads, incluímos o header da biblioteca fazendo #include <pthread.h>.

2. Toda thread precisa executar algum código, e isso é feito por meio de uma função. Quando a thread inicia, ela executa uma função que o programador especifica. Nesse caso, a função greet será executada pela nossa thread.

   Nós chamaremos essas funções que são executadas pelas threads de “funções iniciais”.

   O primeiro e único argumento de greet é arg, cujo tipo é void *. Esse tipo é usado em C para representar um “ponteiro genérico”. Isto é, um ponteiro que pode estar apontando para um valor de qualquer tipo. Porém, não podemos usar um ponteiro desse tipo, apenas passar ele entre funções. O motivo pelo qual não podemos usar um void * (ponteiro para void) é porque void é um tipo que não possui valores. Portanto, não faz sentido tentar acessar/dereferenciar o valor apontado.

   Para podermos usar esse ponteiro, precisamos converter ele para um ponteiro para algum tipo válido. É o que fazemos em char *name = (char *)arg;. Nós convertemos um ponteiro para void num ponteiro para char, e salvamos ele numa variável name. Depois, imprimos name na saída padrão e retornamos NULL para indicar que essa função não retorna nada de útil.

   Toda função inicial tem a mesma assinatura: recebe um void * e retorna um void *.

3. Começamos o código da main declarando uma variável my_thread cujo tipo é pthread_t. Esse tipo representa uma thread, mas por enquanto ela ainda não foi criada pelo sistema operacional.

   Para pedir que o SO crie a thread, chamamos pthread_create. Precisamos passar:

   1. um ponteiro para uma pthread_t
   2. um ponteiro para uma pthread_attr_t, um tipo que armazena os atributos da nossa thread. Quando passamos NULL, a thread receberá os atributos padrões.
   3. um ponteiro para a função inicial que será executada. Nesse caso, passamos a função que criamos, greet. Note que em C, &greet é equivalente a greet, pois o nome de uma função automaticamente decai para um ponteiro para ela mesma.
   4. Um valor que será convertido num void * e passado como o argumento arg de greet. Note que passamos a string literal "thread", que é do tipo char[7]. Arrays em C decaem para um ponteiro do mesmo tipo, então o tipo decai de char[7] para char *, que é implicitamente convertido para um void *.

Vamos executar o programa e vê-lo em ação. Para isso, compilamos o programa usando a flag -pthread do compilador, que inclui o binário que implementa a biblioteca:

$ cc main.c -o main -pthread
$ ./main
$

Epa! O que aconteceu?! O esperado era que o programa printasse Hello from thread! na saída padrão.

Aguardando uma thread concluir com pthread_join

O motivo de nada ter sido printado é que o nosso programa principal criou uma nova thread e chegou ao seu fim. O programa principal não ficou esperando até a thread ser de fato executada e encerrada.

Felizmente, podemos forçar que nosso programa principal (ou thread principal, pois lembre-se que todo programa inicia com pelo menos uma thread, a principal) fique aguardando a conclusão da sua irmã, usando a função pthread_join. É o que fazemos no Código 4-2.

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

void *greet(void *arg) {
  char *name = (char *)arg;
  printf("Hello from %s!\n", name);
  return NULL;
}
// --restante omitido--

int main() {
  pthread_t my_thread;
  pthread_create(&my_thread, NULL, greet, "thread");
  pthread_join(my_thread, NULL);
}

$ cc main.c -o main -pthread
$ ./main
Hello from thread!

Agora sim! pthread_join trabalha com dois parâmetros:

1. O primeiro é a variável que representa a thread que você deseja esperar.

2. O segundo é um void ** (um ponteiro para um ponteiro para void) que, após a thread sendo esperada finalizar, é atualizado para apontar para o valor retornado pela função inicial que acabou de ser executada (Lembre-se que o tipo do valor retornado por funções iniciais é sempre void *).

   Como passamos NULL, estamos indicando que não queremos salvar esse valor. Depois veremos exemplos onde é útil para o programa obter o resultado retornado pela thread.

Criando múltiplas threads

Esse não seria um livro de concorrência se criássemos apenas uma thread! O Código 4-3 cria 10 threads num loop, cada uma executando greet com um argumento diferente.

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

void *greet(void *arg) {
  char *name = (char *)arg;
  printf("Hello from %s!\n", name);
  return NULL;
}
// --restante omitido--

int main() {
  int n = 10;
  pthread_t threads[n];
  char names[n][32];

  for (int i = 0; i < n; i++) {
    snprintf(names[i], sizeof(names[i]), "thread %d", i);
    pthread_create(&threads[i], NULL, greet, names[i]);
  }

  for (int i = 0; i < n; i++) {
    pthread_join(threads[i], NULL);
  }
}

Vamos compilar e executar o programa. Para demonstrar o não-determinismo, iremos executar o programa 3 vezes.

$ cc main.c -o main -pthread
$ ./main
Hello from thread 0!
Hello from thread 2!
Hello from thread 1!
Hello from thread 4!
Hello from thread 3!
Hello from thread 5!
Hello from thread 7!
Hello from thread 6!
Hello from thread 9!
Hello from thread 8!
$ ./main
Hello from thread 0!
Hello from thread 1!
Hello from thread 4!
Hello from thread 3!
Hello from thread 2!
Hello from thread 7!
Hello from thread 8!
Hello from thread 9!
Hello from thread 5!
Hello from thread 6!
$ ./main
Hello from thread 0!
Hello from thread 1!
Hello from thread 2!
Hello from thread 3!
Hello from thread 4!
Hello from thread 5!
Hello from thread 6!
Hello from thread 7!
Hello from thread 8!
Hello from thread 9!

Vamos prestar atenção em cada execução:

1. Na primeira execução, vemos que a ordem que as mensagens aparecem não vai linearmente de 0 até 9, apesar de nós termos criado as threads (e feito o join delas) nessa ordem.

   Logo após o Hello da thread 0, vem o Hello da thread 2! O Hello da thread 1 vem atrás do da thread 2.

2. Na segunda execução, vemos uma nova ordem de mensagens, totalmente diferente da primeira.

3. Na terceira execução, algo interessante acontece. Demos a sorte da ordem das mensagens terem seguido linearmente de 0 a 9! Mesmo após duas execuções não-lineares!

   Isso é um exemplo simples de como, muitas vezes, programas concorrentes podem “enganar” o programador, dando a falsa impressão de que alguma ordem está sendo seguida quando, na verdade, é apenas uma intercalação possível (e talvez mais provável) ocorrendo, em meio a tantas outras.

Retornando valores de uma thread

Muitas vezes, quando uma thread A cria outra thread B, a thread B realiza algum trabalho e deve retornar um valor para A. Esse tipo de colaboração entre threads é muito comum nos seguintes casos:

• Uma thread pai precisa coletar e combinar resultados gerados por \( N \) threads filhas.
• Uma thread precisa retornar um erro/status para outra thread.
• Threads colaboram usando o padrão de fan-out/fan-in, que estudaremos mais à frente.

O mecanismo: return + pthread_join

Vamos criar um programa simples, que não precisaria de threads normalmente, mas que é simples o suficiente para mostrarmos como o mecanismo para retornar valores de uma thread funciona.

O Código 4-4 cria uma thread que calcula \( 7^2 \), e retorna o resultado para a thread principal.

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

void *square(void *arg) {
  int input = *(int *)arg;
  int *result = malloc(sizeof(int));
  *result = input * input;
  return result;
}

int main() {
  int val = 7;
  pthread_t tid;
  pthread_create(&tid, NULL, square, &val);

  int *answer;
  pthread_join(tid, (void **)&answer);
  printf("7² = %d\n", *answer);
  free(answer);
}

Vamos entender o código:

1. Uma thread é criada e inicializada com a função inicial square. Como de praxe, toda função inicial precisa receber um void * e retornar um void *.

2. Dentro da função square, convertemos o ponteiro genérico void * em int *, dereferenciamos/acessamos o valor que ele está apontando e guardamos na variável local input.

3. Alocamos memória para um inteiro com malloc(sizeof(int)) e guardamos o ponteiro retornado em result.

   O motivo pelo qual precisamos alocar memória no heap para guardar o resultado é que a função inicial de uma thread só retorna void *. Se simplesmente usássemos uma variável local para guardar o resultado, precisaríamos retornar um ponteiro para ela. Porém, em C, retornar ponteiros para variáveis locais é considerado undefined behavior, pois a memória do stack alocada para a função não sobrevive após o retorno da função².

   Mas ponteiros que apontam para variáveis no heap permanecem válidos mesmo após o retorno da função em que eles foram criados, então não há problema em utilizar esses ponteiros como valor de retorno de uma função.

4. Calculamos o quadrado do argumento via input * input e armazenamos dentro do endereço de memória apontado por result.

5. Retornamos o ponteiro result da função inicial. Note que, apesar de result ser do tipo int * (ponteiro para int), ele decai automaticamente para um void * pois esse é o tipo de retorno de square e ponteiros para qualquer tipo podem decair para void *.

6. A thread principal cria um ponteiro para int answer, que irá armazenar o valor retornado pela thread. Ao chamar pthread_join, um ponteiro para esse ponteiro (&answer) é passado e convertido para void **.

   Dessa forma, após a thread finalizar, a implementação de pthread_join pode fazer algo como *(&answer) = result, onde result é o ponteiro retornado por square.

7. Após a thread finalizar, seus recursos serem liberados e pthread_join retornar, a expressão *answer retorna o valor 49. Em seguida, esse valor é exibido na tela e a memória apontada por answer é liberada.

Retornando structs

Como a função inicial de uma thread sempre retorna um void *, podemos alocar memória para qualquer tipo, inclusive um struct complexo. É o que o Código 4-5 faz.

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

struct stats {
  int min, max, sum;
};

void *compute_stats(void *arg) {
  int *nums = arg;
  int count = nums[0];
  int *data = &nums[1];

  struct stats *s = malloc(sizeof(struct stats));
  s->min = s->max = s->sum = data[0];

  for (int i = 1; i < count; i++) {
    if (data[i] < s->min) s->min = data[i];
    if (data[i] > s->max) s->max = data[i];
    s->sum += data[i];
  }

  return s;
}

int main() {
  int nums[] = {5, 3, 17, 8, 1, 12};
  pthread_t tid;

  pthread_create(&tid, NULL, compute_stats, nums);

  struct stats *s;
  pthread_join(tid, (void **)&s);

  printf("min=%d max=%d sum=%d\n", s->min, s->max, s->sum);
  free(s);
}

Vamos entender o código:

1. Declaramos um struct stats que irá armazenar estatísticas sobre uma sequência de ints.
2. Declaramos a função inicial compute_stats. O parâmetro arg é convertido num int * que será usado como uma array. Por convenção, o primeiro elemento guarda a quantidade de elementos count, e do segundo elemento para frente é a sequência de números em si. Para facilitar, criamos um novo ponteiro data apontando para o começo dos dados.
3. Alocamos memória para um valor do tipo stats e armazenamos o endereço de memória retornado no ponteiro s. Em seguida, um simples laço for é usado para calcular as estatísticas. Retornamos o valor do ponteiro s.
4. O main é trivial. Os dados são inicializados, a thread é criada e um ponteiro stats * é declarado. Ele será inicializado com o valor retornado pela thread.

Usando pthread_exit em chamadas de função aninhadas

Só podemos usar return para retornar valores de uma thread se ele for utilizado dentro da função inicial (top-level) da thread. Caso essa função inicial chame uma função A, que por sua vez chama outra função B, como faríamos para terminar a thread e enviar um resultado dentro de B?

A resposta é a função pthread_exit, que pode ser chamada em qualquer ponto na pilha de chamadas de uma thread. Um exemplo de uso dessa função está no código abaixo.

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

static void check_positive(int n, int *result) {
    if (n < 0) {
        *result = -1;
        pthread_exit(result);
    }
}

void *double_it(void *arg) {
    int n = *(int *)arg;
    int *result = malloc(sizeof(*result));

    check_positive(n, result);

    *result = n * 2;
    return result;
}

int main() {
    int inputs[] = {5, -3, 10};
    pthread_t tids[3];

    for (int i = 0; i < 3; i++)
        pthread_create(&tids[i], NULL, double_it, &inputs[i]);

    for (int i = 0; i < 3; i++) {
        int *r;
        pthread_join(tids[i], (void **)&r);
        if (*r == -1)
            printf("input %d: rejected\n", inputs[i]);
        else
            printf("input %d: result = %d\n", inputs[i], *r);
        free(r);
    }
}

(Avançado) Threads joinable vs detached

Toda pthread tem um atributo chamado join state. A depender desse atributo, uma thread pode ser classificada em:

• Joinable: após terminar sua execução, a thread espera outra thread chamar pthread_join nela. Esse é o padrão.
• Detached: a thread nunca será passada como argumento de pthread_join, e o sistema automaticamente fará a limpeza dos seus recursos quando ela terminar de executar.

Esse atributo é relevante pois, mesmo após terminar sua execução, uma joinable thread ainda consome recursos, principalmente memória, até que ela seja passada como argumento de pthread_join.

Cada thread joinable que terminou sua execução e está aguardando ser passada de argumento pra pthread_join está associada a três recursos principais: o valor de retorno da sua função inicial, um stack de chamadas (não pode ser desalocado, pois o valor de retorno pode depender dele) e os metadados usados pela implementação da biblioteca <pthread.h>. Esses recursos totalizam pouco mais de 8 MB por thread.

pthread_join não faz apenas uma thread esperar outra terminar de executar. Quando a thread passada para o join finaliza, pthread_join limpa todos os recursos associados com a thread finalizada.

Isso nos leva ao principal bug de memória em programas baseados em <pthread.h>: o programador esquecer de chamar pthread_join em threads joinable, provocando vazamento de recursos (resource leak), como memória. Como de praxe na linguagem C, o gerenciamento de memória é uma responsabilidade exclusiva do programador. C não oferece APIs ou runtimes que facilitem essa responsabilidade.

Um programa com resource leak

Vamos demonstrar um bug de resource leak com um programa. O Código 4-6 irá criar threads joinable num loop while. Essas threads irão executar uma função que não faz praticamente nada, fazendo com que elas terminem de executar quase que imediatamente. Para causar o resource leak, o programa não irá chamar pthread_join nelas. Chegará um momento em que a tentativa de criar novas threads usando pthread_create irá falhar, pois toda a memória virtual disponível para o programa já terá sido consumida pelas threads já criadas, encerrando o loop.

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

void *do_nothing(void *arg) {
    return NULL;
}

int main(void) {
    pthread_t tid;
    int i = 0;

    while (pthread_create(&tid, NULL, do_nothing, NULL) == 0) {
        i++;
    }

    printf("created %d threads before failure\n", i);
    return 0;
}

Antes de executar, precisamos limitar a memória virtual do processo para até ~2 GB via ulimit. Caso deixássemos sem limite, o OOM Killer (Out-of-Memory Killer, um processo do kernel-space que mata processos quando a memória livre chega perto de zero) entraria em ação, matando o processo e impedindo que o último printf fosse executado.

$ ulimit -Sv 2000000
$ cc main.c -o main -pthread
$ ./main
created 243 threads before failure

O programa conseguiu criar 243 threads antes de falhar devido a falta de recursos. Todos os 2 GB de memória virtual foram consumidos pois as threads criadas nunca foram passadas para pthread_join. Mesmo após terminarem de executar, elas continuaram consumindo memória.

Esse número de 243 faz sentido: 2 GB é equivalente a 2048 MB. 2048 MB / 8 MB = 256 threads, na teoria. O restante da memória foi consumido por outros atores (o próprio processo pai, a thread principal, bibliotecas, entre outras alocações).

A versão com threads detached e sem leaks

Vamos ver agora como esse programa se comporta se criarmos threads detached ao invés de joinable, implementado no Código 4-7.

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

void *do_nothing(void *arg) {
    return NULL;
}
// --restante omitido--

int main(void) {
    pthread_t tid;
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);

    for (int i = 0; i < 100000; i++) {
        pthread_create(&tid, &attr, do_nothing, NULL);
    }
    pthread_attr_destroy(&attr);
    printf("100k threads created and self-cleaning\n");

    // Pequeno sleep (0.5 s) para que as threads detached tenham tempo de
    // finalizar e liberar seus recursos.
    usleep(500000);

    return 0;
}

$ cc main.c -o main -pthread
$ ./main
100k threads created and self-cleaning

Para definir uma thread como detached, podemos chamar pthread_detach numa thread joinable ou, de maneira mais eficiente, criamos ela como detached desde o princípio, usando os atributos da thread.

Criamos uma variável do tipo pthread_attr_t para guardar os atributos das threads. Configuramos ela como detached usando pthread_attr_setdetachstate.

Enquanto tínhamos criado no máximo 243 threads joinable simultâneas no Código 4-6, o Código 4-7 conseguiu criar 100.000 threads detached sem problema. Isso faz sentido: como os recursos das threads detached são liberados quando elas finalizam, e a função do_nothing termina quase que imediatamente, podemos criar um número imenso dessas threads sem se preocupar com esgotamento dos recursos.

Note que chamar pthread_join numa thread detached é considerado Undefined Behavior pela especificação POSIX.

Uma observação

Apesar de threads detached terem seus benefícios, elas são geralmente consideradas um anti-padrão ou code smell, sendo preferível o uso de outros construtos (thread pools, executors, etc).

A motivação para isso é abordada no capítulo Anti-padrões de Concorrência.

1. C também possui uma outra API para criar threads, introduzida no padrão C11 e acessível via <threads.h>. Esta, no entanto, possui uma superfície de API muito menor, não oferecendo suporte para cancelamento e tipos avançados de locks, sendo preterida para programas não-triviais. ↩

2. Em C, variáveis locais de uma função são alocadas no stack do programa (mais especificamente, no frame do stack referente àquela função). ↩

C++ (std::thread e std::jthread)

C++ oferece threads na biblioteca padrão desde o C++11, via <thread>. O tipo std::thread funciona de maneira parecida com pthread_t, mas sem a manipulação de ponteiros genéricos (void *) e casts manuais. Os argumentos são passados com seus tipos reais.

Criando uma thread

O construtor de std::thread recebe um callable (função, lambda ou functor) e os argumentos que serão passados para ele. A construção do objeto já cria e inicia a thread (não tem uma etapa separada de “start”). t.join() bloqueia até a thread t finalizar.

#include <iostream>
#include <thread>

void greet(const std::string &name) {
    std::cout << "Hello from " << name << "!\n";
}

int main() {
    std::thread t(greet, "thread");
    t.join();
}

Retornando valores com std::ref

std::thread não possui um mecanismo de retornar valores de uma thread de forma direta. Uma alternativa é passar uma referência para uma variável de saída:

#include <iostream>
#include <thread>

void square(int input, int &result) {
    result = input * input;
}

int main() {
    int answer;
    std::thread t(square, 7, std::ref(answer));
    t.join();
    std::cout << "7² = " << answer << "\n";
}

Note o std::ref(answer). Se trocarmos por apenas answer, o programa continua compilando e rodando, mas answer fica com lixo de memória na main.

O construtor de std::thread faz decay-copy (o processo de primeiro aplicar decay ao tipo do valor e depois copiá-lo) de todos os argumentos antes de repassar para a thread¹. Sem o std::ref, a thread recebe uma cópia de answer e escreve nessa cópia. A variável original na main nunca é tocada. É uma proteção contra dangling references (a variável original pode sair de escopo antes da thread ler), mas significa que quando você quer a referência, tem que pedir explicitamente e ser responsável por garantir que o objeto referido irá viver por tempo suficiente até a thread terminar.

O destrutor de std::thread

Em Pthreads, esquecer de chamar pthread_join numa thread joinable causa resource leak silencioso: o programa continua rodando, mas a memória vai sendo consumida aos poucos. C++ tomou uma decisão diferente:

#include <thread>

int main() {
    std::thread t([] {});
} /* -> t sai de escopo ao final do bloco
  -> destrutor é chamado
  -> destrutor detecta que t ainda é joinable
  -> destrutor chama std::terminate e mata o processo
*/

$ c++ main.cpp -o main -std=c++20 -pthread
$ ./main
terminate called without an active exception
Aborted

O destrutor de std::thread invoca std::terminate() e derruba o processo inteiro. A filosofia é que um leak silencioso é pior do que um crash. Pelo menos o crash aparece no primeiro teste.

std::jthread

O C++20 introduziu std::jthread (joining thread), cujo destrutor faz join() automaticamente. Mesma ideia do std::unique_ptr com delete:

#include <iostream>
#include <thread>

int main() {
    std::jthread t([] {
        std::cout << "Hello from jthread!\n";
    });
    // t sai de escopo -> join() automático
}

Se t sair de escopo por qualquer motivo (return antecipado, exceção, final do bloco), o destrutor cuida do join().

Múltiplas threads

#include <iostream>
#include <thread>
#include <vector>
#include <format>

int main() {
    const int n = 10;
    std::vector<std::jthread> threads;
    threads.reserve(n);

    for (int i = 0; i < n; i++) {
        threads.emplace_back([i] {
            std::cout << std::format("Hello from thread {}!\n", i);
        });
    }
}

A lambda captura i por valor ([i]). Cada thread recebe uma cópia do valor de i no momento da criação. Se trocarmos para captura por referência ([&i]), todas as threads enxergam a mesma variável i, e o resultado depende de quando cada thread lê i, potencialmente depois de i já ter sido incrementado pelo loop. O compilador aceita as duas formas sem reclamar.

$ c++ main.cpp -o main -std=c++20 -pthread
$ ./main
Hello from thread 0!
Hello from thread 3!
Hello from thread 1!
Hello from thread 2!
Hello from thread 5!
Hello from thread 4!
Hello from thread 7!
Hello from thread 6!
Hello from thread 8!
Hello from thread 9!
$ ./main
Hello from thread 1!
Hello from thread 0!
Hello from thread 2!
Hello from thread 4!
Hello from thread 3!
Hello from thread 5!
Hello from thread 6!
Hello from thread 8!
Hello from thread 7!
Hello from thread 9!

Como usamos jthread, não precisamos do join() manual: o destrutor dos objetos cuida disso quando o vector sai de escopo.

1. O construtor de std::thread invoca internamente std::invoke(decay_copy(f), decay_copy(args)...). Isso explica também por que, ao passar um const char * como argumento, a thread recebe uma cópia do ponteiro (o que geralmente é o comportamento desejado). ↩

Java (java.lang.Thread)

Em Java, threads são objetos da classe java.lang.Thread. O garbage collector cuida da memória e a tipagem forte cuida dos argumentos. Em compensação, Java traz suas próprias pegadinhas.

Criando uma thread

public class Main {
    public static void main(String[] args) throws InterruptedException {
        Thread t = new Thread(() -> {
            System.out.println("Hello from thread!");
        });
        t.start();
        t.join();
    }
}

O construtor de Thread recebe um Runnable (uma interface funcional com um único método run()). Aqui usamos uma lambda, mas qualquer classe que implementa Runnable serve. Instanciar o objeto Thread não cria a thread do SO; isso só acontece no start(). Essa separação permite configurar nome, prioridade e modo daemon antes de iniciar.

A restrição de effectively final

Vamos criar 10 threads:

public class Main {
    public static void main(String[] args) throws InterruptedException {
        int n = 10;
        Thread[] threads = new Thread[n];

        for (int i = 0; i < n; i++) {
            final int id = i;
            threads[i] = new Thread(() -> {
                System.out.println("Hello from thread " + id + "!");
            });
            threads[i].start();
        }

        for (Thread t : threads) {
            t.join();
        }
    }
}

O final int id = i está ali porque lambdas em Java só capturam variáveis locais que são effectively final, cujo valor não muda após a inicialização. A variável de loop i muda a cada iteração, então usá-la direto na lambda causa:

error: local variables referenced from a lambda expression
       must be final or effectively final

O compilador barra antes de rodar. Pode parecer restritivo, mas essa restrição evita toda uma classe de bugs: se o programador quer que a lambda use o valor de i, ele é forçado a criar uma cópia explícita.

$ javac Main.java && java Main
Hello from thread 0!
Hello from thread 2!
Hello from thread 1!
Hello from thread 4!
Hello from thread 5!
Hello from thread 3!
Hello from thread 6!
Hello from thread 8!
Hello from thread 7!
Hello from thread 9!

run() vs start()

Vamos ver o que acontece quando chamamos run() ao invés de start():

public class Main {
    public static void main(String[] args) throws InterruptedException {
        Thread t = new Thread(() -> {
            System.out.println(Thread.currentThread().getName());
        });

        System.out.println("--- com run() ---");
        t.run();

        System.out.println("--- com start() ---");
        Thread t2 = new Thread(() -> {
            System.out.println(Thread.currentThread().getName());
        });
        t2.start();
        t2.join();
    }
}

$ javac Main.java && java Main
--- com run() ---
main
--- com start() ---
Thread-1

Com run(), quem executou o código foi a thread main. Nenhuma thread nova foi criada. O programa roda sequencialmente e produz a saída “correta”, mas sem concorrência nenhuma.

Threads daemon

Quando uma thread é criada, é possível configurá-la como uma thread daemon. A JVM só encerra quando todas as threads não-daemon terminam. Se uma thread não-daemon ainda estiver executando quando a main retornar, o processo fica bloqueado aguardando a finalização:

public class Main {
    public static void main(String[] args) {
        Thread t = new Thread(() -> {
            try { Thread.sleep(5000); } catch (InterruptedException e) {}
            System.out.println("Thread finalizou!");
        });
        t.start();
        System.out.println("main retornou");
    }
}

$ javac Main.java && java Main
main retornou
Thread finalizou!

A main terminou, mas o programa continuou rodando por mais 5 segundos até a thread terminar. Marcando a thread como daemon com t.setDaemon(true) antes do start(), a JVM não espera:

public class Main {
    public static void main(String[] args) {
        Thread t = new Thread(() -> {
            try { Thread.sleep(5000); } catch (InterruptedException e) {}
            System.out.println("Thread finalizou!");
        });
        t.setDaemon(true);
        t.start();
        System.out.println("main retornou");
    }
}

$ javac Main.java && java Main
main retornou

A mensagem Thread finalizou! nunca apareceu. A JVM encerrou junto com a main, matando a thread daemon no meio do sleep.

Retornando valores

Runnable não retorna valores. Um truque comum é usar um array de um elemento como recipiente:

public class Main {
    public static void main(String[] args) throws InterruptedException {
        int[] answer = {0};
        Thread t = new Thread(() -> {
            answer[0] = 7 * 7;
        });
        t.start();
        t.join();
        System.out.println("7² = " + answer[0]);
    }
}

Por que não uma variável int direto? Pela mesma restrição de effectively final: a lambda não pode modificar uma variável local primitiva. O array contorna isso porque a referência ao array não muda (satisfaz a restrição), mas o conteúdo pode ser alterado¹.

1. Java oferece Callable<V> (como Runnable mas com retorno) e Future<V> (que representa o resultado pendente) para lidar com retorno de threads de maneira mais robusta. ↩

Kotlin (kotlin.concurrent.thread)

Por baixo dos panos, Kotlin usa a mesma java.lang.Thread da JVM. O que muda é a ergonomia: a função thread() do pacote kotlin.concurrent cria, configura e inicia a thread numa chamada só.

import kotlin.concurrent.thread

fun main() {
    val t = thread {
        println("Hello from thread!")
    }
    t.join()
}

thread() recebe uma lambda, cria a java.lang.Thread, chama start() e retorna o objeto. Como é a mesma JVM, a mesma regra se aplica: o programa não encerra enquanto threads não-daemon estiverem rodando. Para marcar como daemon, basta isDaemon = true.

Captura de variáveis

Em Java, lambdas só capturam variáveis effectively final. Kotlin não tem essa restrição: lambdas capturam qualquer variável do escopo externo, inclusive var:

import kotlin.concurrent.thread

fun main() {
    var counter = 0
    val t = thread { counter++ }
    t.join()
    println("counter = $counter")
}

Com uma thread só, funciona. Mas com várias threads incrementando counter ao mesmo tempo, seria uma race condition. E o compilador não dá nenhum sinal de alerta. Não tem erro de compilação, não tem warning, não tem nenhuma indicação de que algo pode dar errado. Essa liberdade coloca a responsabilidade inteira nas costas do programador.

Múltiplas threads

import kotlin.concurrent.thread

fun main() {
    val threads = (0 until 10).map { i ->
        thread { println("Hello from thread $i!") }
    }
    threads.forEach { it.join() }
}

$ kotlinc main.kt -include-runtime -d main.jar && java -jar main.jar
Hello from thread 1!
Hello from thread 0!
Hello from thread 3!
Hello from thread 2!
Hello from thread 5!
Hello from thread 4!
Hello from thread 6!
Hello from thread 7!
Hello from thread 9!
Hello from thread 8!

O (0 until 10).map { ... } cria as 10 threads e coleta numa lista. forEach faz o join de cada uma.

Retornando valores

Como a lambda pode capturar e modificar variáveis do escopo externo, retornar um valor de uma thread é direto:

import kotlin.concurrent.thread

fun main() {
    var answer = 0
    val t = thread { answer = 7 * 7 }
    t.join()
    println("7² = $answer")
}

A lambda modifica answer direto, e após o join() o valor está lá¹.

1. Na prática, boa parte do código Kotlin concorrente usa coroutines (kotlinx.coroutines) ao invés de threads diretamente. Threads do SO continuam sendo o mecanismo subjacente, mas coroutines adicionam structured concurrency e cancelamento cooperativo. ↩

Resolvendo problemas com threads

No capítulo anterior, aprendemos a criar threads em várias linguagens. Mas os exemplos eram todos triviais: threads que imprimem mensagens ou calculam valores simples. Agora vamos usar threads para resolver problemas de verdade.

Os exemplos deste capítulo têm uma propriedade em comum: as threads não compartilham estado mutável entre si. Cada uma trabalha sobre sua própria fatia de dados, e os resultados são combinados apenas depois que todas terminam. Isso é proposital. Queremos primeiro ver threads funcionando corretamente, antes de explorar o que pode dar errado.

Exemplo 1: Soma paralela de um array

Vamos começar com um problema simples: somar todos os elementos de um array grande. A versão sequencial é trivial:

#include <stdio.h>

#define N 1000

int main(void) {
    int numbers[N];
    for (int i = 0; i < N; i++)
        numbers[i] = i + 1;

    long total = 0;
    for (int i = 0; i < N; i++)
        total += numbers[i];

    printf("total = %ld\n", total);
}

O resultado é \( \frac{1000 \cdot 1001}{2} = 500500 \).

Paralelizando com threads

A ideia é simples: dividimos o array em fatias (slices) disjuntas e damos cada fatia pra uma thread diferente. Cada thread calcula a soma parcial da sua fatia. Ao final, a thread principal coleta os resultados via pthread_join e soma tudo.

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

#define N_THREADS 5
#define N_ELEMS   1000

typedef struct {
    const int *data;
    size_t     len;
} Slice;

void *partial_sum(void *arg) {
    Slice *s = arg;
    long sum = 0;
    for (size_t i = 0; i < s->len; i++)
        sum += s->data[i];
    return (void *)sum;
}

int main(void) {
    int numbers[N_ELEMS];
    for (int i = 0; i < N_ELEMS; i++)
        numbers[i] = i + 1;

    size_t chunk = N_ELEMS / N_THREADS;

    pthread_t tids[N_THREADS];
    Slice     slices[N_THREADS];

    for (int t = 0; t < N_THREADS; t++) {
        slices[t].data = numbers + t * chunk;
        slices[t].len  = (t == N_THREADS - 1)
                       ? N_ELEMS - t * chunk
                       : chunk;
        pthread_create(&tids[t], NULL, partial_sum, &slices[t]);
    }

    long total = 0;
    for (int t = 0; t < N_THREADS; t++) {
        void *res;
        pthread_join(tids[t], &res);
        total += (long)res;
    }

    printf("total = %ld\n", total);
}

O struct Slice armazena um ponteiro para o início de uma fatia do array e o comprimento dessa fatia. Com isso, cada thread sabe exatamente quais elementos deve somar, sem acessar dados de outras threads.

A função partial_sum recebe uma Slice, calcula a soma dos elementos e retorna o resultado. O retorno é feito convertendo um long para void *, truque que funciona pois em plataformas de 64 bits, void * e long têm o mesmo tamanho (8 bytes)¹.

No main, dividimos o array de 1000 elementos em 5 fatias de 200 cada. A última fatia recebe os elementos restantes caso a divisão não seja exata. Criamos 5 threads, cada uma recebendo sua Slice, e depois coletamos os resultados com pthread_join.

O que faz esse exemplo funcionar sem nenhuma sincronização: as threads operam sobre regiões disjuntas da memória. Cada thread lê apenas a sua fatia (que é const) e escreve numa variável local sum. A única comunicação acontece no join, quando a thread principal coleta os resultados.

1. Converter entre long e void * é uma prática comum em código baseado em Pthreads, mas tecnicamente é um comportamento definido pela implementação (não pelo padrão C). Em plataformas de 64 bits (Linux x86-64, ARM64), isso funciona pois ambos os tipos têm 8 bytes. Para código portável, a alternativa é alocar memória no heap e retornar um ponteiro, como fizemos no capítulo anterior. ↩

Exemplo 2: Buscando o máximo em paralelo

A mesma ideia de dividir um array em fatias, dar cada fatia para uma thread e juntar os resultados no final funciona para qualquer operação que possa ser decomposta em partes independentes. Aqui, aplicamos ela para encontrar o valor máximo.

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

#define N_THREADS 4
#define N_ELEMS   16

typedef struct {
    const int *data;
    size_t     len;
} Slice;

void *partial_max(void *arg) {
    Slice *s = arg;
    int max = INT_MIN;
    for (size_t i = 0; i < s->len; i++) {
        if (s->data[i] > max)
            max = s->data[i];
    }
    return (void *)(long)max;
}

int main(void) {
    int data[] = {3, 41, 15, 92, 65, 35, 89, 79,
                  32, 38, 46, 26, 53, 58, 97, 23};

    size_t chunk = N_ELEMS / N_THREADS;
    pthread_t tids[N_THREADS];
    Slice     slices[N_THREADS];

    for (int t = 0; t < N_THREADS; t++) {
        slices[t].data = data + t * chunk;
        slices[t].len  = (t == N_THREADS - 1)
                       ? N_ELEMS - t * chunk
                       : chunk;
        pthread_create(&tids[t], NULL, partial_max, &slices[t]);
    }

    int global_max = INT_MIN;
    for (int t = 0; t < N_THREADS; t++) {
        void *res;
        pthread_join(tids[t], &res);
        int local_max = (int)(long)res;
        if (local_max > global_max)
            global_max = local_max;
    }

    printf("max = %d\n", global_max);
}

A estrutura é a mesma do exemplo anterior: Slice, divisão em fatias, coleta via pthread_join. O que muda é a operação: cada thread calcula o máximo local da sua fatia, e a thread principal compara os 4 máximos locais para encontrar o global.

Tanto a soma quanto o máximo são operações associativas: não importa como dividimos os elementos entre as threads, o resultado final é o mesmo¹.

1. Esse padrão é um caso particular de Map-Reduce ou fan-out/fan-in: a fase “map” aplica uma função a cada fatia (soma parcial, máximo parcial, etc.), e a fase “reduce” combina os resultados num único valor. ↩

Exemplo 3: Download concorrente

Até agora, os exemplos eram CPU-bound: dividíamos dados entre threads para processar mais rápido. Esse é diferente. O gargalo aqui é I/O, e a concorrência melhora a vazão: várias operações lentas acontecem ao mesmo tempo, como discutido no Capítulo 1.

Para simular downloads sem depender de rede, cada thread “baixa” um arquivo dormindo por um tempo proporcional ao “tamanho” do arquivo:

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

typedef struct {
    const char *filename;
    int         size_kb;
} Download;

void *download_file(void *arg) {
    Download *d = arg;
    printf("[start] %s (%d KB)\n", d->filename, d->size_kb);

    usleep(d->size_kb * 100);

    printf("[done]  %s\n", d->filename);
    return NULL;
}

int main(void) {
    Download files[] = {
        {"relatorio.pdf",  4200},
        {"foto.jpg",       1800},
        {"dados.csv",      3500},
        {"backup.tar.gz",  7200},
        {"config.json",      50},
    };
    int n = sizeof(files) / sizeof(files[0]);

    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);

    // Versão sequencial: baixa um de cada vez
    for (int i = 0; i < n; i++)
        download_file(&files[i]);

    clock_gettime(CLOCK_MONOTONIC, &t1);
    long seq_ms = (t1.tv_sec - t0.tv_sec) * 1000
                + (t1.tv_nsec - t0.tv_nsec) / 1000000;

    printf("\nSequencial: %ld ms\n\n", seq_ms);

    // Versão concorrente: baixa todos ao mesmo tempo
    clock_gettime(CLOCK_MONOTONIC, &t0);

    pthread_t tids[n];
    for (int i = 0; i < n; i++)
        pthread_create(&tids[i], NULL, download_file, &files[i]);
    for (int i = 0; i < n; i++)
        pthread_join(tids[i], NULL);

    clock_gettime(CLOCK_MONOTONIC, &t1);
    long par_ms = (t1.tv_sec - t0.tv_sec) * 1000
                + (t1.tv_nsec - t0.tv_nsec) / 1000000;

    printf("\nConcorrente: %ld ms\n", par_ms);
}

O programa roda o mesmo conjunto de downloads duas vezes: primeiro sequencialmente, depois com uma thread por arquivo.

[start] relatorio.pdf (4200 KB)
[done]  relatorio.pdf
[start] foto.jpg (1800 KB)
[done]  foto.jpg
[start] dados.csv (3500 KB)
[done]  dados.csv
[start] backup.tar.gz (7200 KB)
[done]  backup.tar.gz
[start] config.json (50 KB)
[done]  config.json

Sequencial: 1677 ms

[start] relatorio.pdf (4200 KB)
[start] foto.jpg (1800 KB)
[start] dados.csv (3500 KB)
[start] backup.tar.gz (7200 KB)
[start] config.json (50 KB)
[done]  config.json
[done]  foto.jpg
[done]  dados.csv
[done]  relatorio.pdf
[done]  backup.tar.gz

Concorrente: 722 ms

Na versão sequencial, cada download precisa terminar antes do próximo começar, e o tempo total é a soma dos tempos individuais. Na versão concorrente, todos começam praticamente ao mesmo tempo, e o tempo total fica limitado pelo download mais lento (backup.tar.gz, 722 ms).

Esse exemplo é estruturalmente diferente dos dois anteriores: não tem fase de combinação. Cada thread faz seu trabalho e termina. O join existe apenas para garantir que o programa não encerre antes de todas as threads finalizarem.

O padrão: dividir, processar, combinar

Os três exemplos anteriores seguem o mesmo padrão, apesar de resolverem problemas diferentes:

1. Dividir o trabalho em partes independentes.
2. Processar cada parte numa thread separada.
3. Combinar os resultados após todas as threads terminarem (via join).

No download concorrente, a fase de combinação nem existe (cada thread é autossuficiente). Na soma e no máximo, a combinação é trivial: uma adição ou uma comparação.

Esses exemplos funcionam sem nenhum mecanismo de sincronização porque as threads não precisam se comunicar entre si durante a execução. Cada uma opera sobre sua própria fatia de dados, e a única troca de informação acontece no join, quando a thread principal coleta os resultados.

Mas nem todo problema se decompõe dessa forma.

E quando as threads precisam compartilhar dados?

Nos exemplos anteriores, fomos cuidadosos em garantir que cada thread trabalhasse sobre dados exclusivamente seus. Mas e se duas threads precisarem acessar e modificar a mesma variável?

O Código 5-5 cria 10 threads que incrementam um contador compartilhado, cada uma 100.000 vezes:

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

int counter = 0;

void *increment(void *arg) {
    for (int i = 0; i < 100000; i++)
        counter++;
    return NULL;
}

int main(void) {
    pthread_t tids[10];

    for (int i = 0; i < 10; i++)
        pthread_create(&tids[i], NULL, increment, NULL);
    for (int i = 0; i < 10; i++)
        pthread_join(tids[i], NULL);

    printf("counter = %d (esperado: 1000000)\n", counter);
}

O resultado esperado é \( 10 \times 100000 = 1000000 \). Porém:

$ ./main
counter = 474032 (esperado: 1000000)
$ ./main
counter = 538691 (esperado: 1000000)
$ ./main
counter = 623107 (esperado: 1000000)

O valor muda a cada execução e é quase sempre menor que 1.000.000. Esse é o bug de lost update que analisamos no Capítulo 1: quando múltiplas threads leem, modificam e escrevem a mesma variável sem sincronização, incrementos são perdidos. Lá, vimos as intercalações possíveis de x = x + 1 executado por duas threads. Aqui, o mesmo problema aparece em escala. Com 10 threads e 100.000 incrementos cada, a quantidade de intercalações que causam perdas é astronômica.

“Mas é só somar no final”

Uma objeção justa a esse exemplo: o contador é artificial. Se cada thread mantivesse a própria soma numa variável local e a thread principal juntasse tudo no join, o problema sumia, e a gente cairia de volta no padrão dividir, processar, combinar do resto do capítulo. E é verdade. Todo agregado que só precisa do valor final (uma soma, um máximo, uma contagem) se resolve assim, sem thread nenhuma tocar o estado da outra.

O compartilhamento vira inevitável quando o estado precisa ser lido enquanto as threads ainda estão rodando, não depois. Aí não tem “somar no final”: o final é tarde demais.

Volte ao download concorrente. Suponha que, além de baixar, a gente queira uma barra de progresso: quantos arquivos já terminaram e quantos KB já foram baixados no total, atualizados de tempos em tempos enquanto os downloads acontecem. Duas variáveis compartilhadas, arquivos_prontos e kb_baixados, que cada thread de download atualiza ao avançar, e a thread principal lê num laço pra imprimir o placar:

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

typedef struct {
    const char *filename;
    int         size_kb;
} Download;

int arquivos_prontos = 0;
int kb_baixados       = 0;
int total_arquivos    = 0;

void *download_file(void *arg) {
    Download *d = arg;

    // "baixa" em pedaços de 100 KB, atualizando o progresso a cada pedaço
    int restante = d->size_kb;
    while (restante > 0) {
        int pedaco = restante < 100 ? restante : 100;
        usleep(pedaco * 100);
        kb_baixados += pedaco;
        restante -= pedaco;
    }

    arquivos_prontos++;
    return NULL;
}

int main(void) {
    Download files[] = {
        {"relatorio.pdf",  4200},
        {"foto.jpg",       1800},
        {"dados.csv",      3500},
        {"backup.tar.gz",  7200},
        {"config.json",      50},
    };
    total_arquivos = sizeof(files) / sizeof(files[0]);

    int total_kb = 0;
    for (int i = 0; i < total_arquivos; i++)
        total_kb += files[i].size_kb;

    pthread_t tids[total_arquivos];
    for (int i = 0; i < total_arquivos; i++)
        pthread_create(&tids[i], NULL, download_file, &files[i]);

    // enquanto os downloads rolam, a main lê o progresso e imprime
    while (arquivos_prontos < total_arquivos) {
        printf("progresso: %d/%d arquivos, %d/%d KB\n",
               arquivos_prontos, total_arquivos, kb_baixados, total_kb);
        usleep(200000);
    }

    for (int i = 0; i < total_arquivos; i++)
        pthread_join(tids[i], NULL);

    printf("progresso: %d/%d arquivos, %d/%d KB\n",
           arquivos_prontos, total_arquivos, kb_baixados, total_kb);
    printf("pronto.\n");
}

Aqui não dá pra “juntar no final”. A barra de progresso só faz sentido durante a execução, e é justamente durante a execução que várias threads estão somando em kb_baixados ao mesmo tempo. É o mesmo x = x + 1 do contador, só que agora com um motivo palpável pra existir: a informação é útil no meio do caminho, não no fim. E o kb_baixados termina quase sempre abaixo dos 16.750 KB esperados, pela mesmíssima razão de antes.

O contador era o exemplo mínimo do problema; o placar é onde ele te pega num programa que você teria escrito de qualquer jeito. Nos dois casos falta a mesma coisa: um jeito de garantir que aquele incremento aconteça inteiro antes de outra thread mexer na variável.

Exercícios

Os exercícios abaixo usam só o que apareceu até aqui: criar threads com pthread_create, esperar com pthread_join, passar dados via struct e devolver resultado convertendo pra void *. Nada de mutex ainda, isso é o próximo capítulo.

Dividir, processar, combinar é um dos formatos que dá pra montar sem sincronização, e boa parte dos exercícios cai nele, mas não é o único. Alguns aqui não têm fase de combinação nenhuma (cada thread termina sozinha, como no download do Exemplo 3), e outros processam fatias sem reduzir a um valor só. O que amarra todos é a mesma condição: enquanto não existe lock, as threads só podem tocar regiões disjuntas da memória. Os exercícios difíceis esbarram de propósito nesse limite, pra você sentir onde ele está, não consertar (ainda).

Salvo indicação, compile com cc main.c -o main -pthread.

Fáceis

5.1 Modifique a soma paralela pra usar 8 threads em vez de 5, sobre um array de 10.000 elementos preenchido com i + 1. Confira que o total continua 50005000.

5.2 No exemplo da soma, o array tem 1000 elementos e são 5 threads, divisão exata. Troque N_ELEMS pra 1003 sem mexer em mais nada e rode. O resultado ainda fica certo? Explique, olhando pra linha que calcula slices[t].len, por que a última fatia é tratada diferente das outras.

5.3 Escreva um programa que cria 4 threads, cada uma recebendo via struct um número inteiro n (1, 2, 3, 4). Cada thread calcula n * n e devolve o resultado. A main coleta os quatro quadrados com pthread_join e imprime a soma deles (esperado: 1 + 4 + 9 + 16 = 30).

5.4 Pegue a busca do máximo e adapte pra encontrar o mínimo de um array de 16 inteiros. O que muda além do nome da função?

5.5 Escreva um programa que dobra cada elemento de um array de 1000 inteiros, em paralelo, escrevendo o resultado no próprio array (v[i] *= 2). Divida em fatias, uma por thread, e note que aqui não existe fase de combinação: cada thread escreve na sua fatia e acabou, o join só garante que tudo terminou antes da main imprimir. Compare com a soma paralela e diga o que sumiu.

Médios

5.6 Generalize a soma paralela pra funcionar com um número de threads que não divide o tamanho do array de forma exata (por exemplo, 1000 elementos e 3 threads). Garanta que nenhum elemento fique de fora nem seja somado duas vezes. Verifique com 1000 elementos e 3, 7 e 11 threads que o total é sempre 500500.

Dica: distribua os elementos que sobram (N_ELEMS % N_THREADS) entre as primeiras fatias, uma a mais em cada, em vez de jogar todos na última.

5.7 Escreva um programa que conta, em paralelo, quantos números primos existem num array de inteiros. Divida o array em fatias, cada thread conta os primos da sua fatia e devolve a contagem parcial, e a main soma as parciais. Teste com o array {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} (resposta: 6 primos).

5.8 Simule o envio de 6 notificações independentes, cada uma com um tempo de “envio” diferente (use usleep com valores como 300, 120, 250, 80, 400 e 150 ms, um por notificação, passados via struct). Rode primeiro sequencialmente, depois com uma thread por notificação, e meça o tempo de relógio das duas versões com clock_gettime, como no download concorrente. Não há nada pra combinar: cada thread dispara sua notificação e termina. Explique por que o tempo da versão concorrente fica perto da notificação mais lenta (400 ms), e não da soma de todas.

5.9 No download concorrente, a versão concorrente cria uma thread por arquivo. Suponha que você tenha 100 arquivos pra baixar, mas queira usar no máximo 5 threads. Descreva (em prosa ou pseudocódigo, não precisa compilar) como você organizaria o trabalho pra que cada thread processe uma fatia da lista de arquivos, uma depois da outra, respeitando o limite de 5 threads.

Difíceis

5.10 Rode o contador sem sincronização cinco vezes e anote os resultados. Agora reduza o número de incrementos por thread de 100.000 pra 10, mantendo as 10 threads, e rode mais cinco vezes. Com que frequência o resultado dá certo (100) em cada caso? Explique por que diminuir o trabalho dentro do laço muda a probabilidade de você observar o bug, mesmo o bug estando presente nos dois programas.

5.11 Considere este programa, que tenta acumular resultados num array compartilhado em vez de devolver pelo join:

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

#define N 4

int resultados[N];

typedef struct {
    int  id;
    int  valor;
} Tarefa;

void *worker(void *arg) {
    Tarefa *t = arg;
    resultados[t->id] = t->valor * 10;
    return NULL;
}

int main(void) {
    pthread_t tids[N];
    Tarefa tarefas[N];

    for (int i = 0; i < N; i++) {
        tarefas[i].id    = i;
        tarefas[i].valor = i + 1;
        pthread_create(&tids[i], NULL, worker, &tarefas[i]);
    }
    for (int i = 0; i < N; i++)
        pthread_join(tids[i], NULL);

    for (int i = 0; i < N; i++)
        printf("resultados[%d] = %d\n", i, resultados[i]);
}

Este programa não tem o bug do contador, mesmo com 4 threads escrevendo no mesmo array resultados sem sincronização nenhuma, e mesmo o array sendo estado compartilhado. Explique por quê. O que é diferente entre este caso e o counter++? Que propriedade das escritas de cada thread torna a ausência de sincronização segura aqui?

Dica: olhe em qual posição de memória cada thread escreve.

5.12 Agora quebre o programa de propósito. Modifique o worker do exercício anterior pra que todas as threads escrevam na mesma posição resultados[0] += t->valor (em vez de resultados[t->id] = ...). Rode várias vezes. O valor final de resultados[0] deveria ser 1 + 2 + 3 + 4 = 10. Ele é sempre 10? Relacione o que você observa com o bug do contador, e explique por que a mudança de resultados[t->id] pra resultados[0] reintroduziu o problema que o exercício 5.11 não tinha.

Mutual Exclusion

Sabemos criar threads, e sabemos que quando elas compartilham uma variável e a modificam sem coordenação, incrementos se perdem e o contador soma menos do que deveria. Vimos isso acontecer: dez threads incrementando counter cem mil vezes cada, e o resultado final saindo 474032 em vez de 1000000.

Este capítulo é sobre a solução mais fundamental pra esse tipo de problema: garantir que, do início ao fim daquele counter++, nenhuma outra thread meta a mão na variável. A ideia se chama exclusão mútua (mutual exclusion), e é a base de quase todo o restante desta parte do livro.

Vamos começar enunciando o problema com precisão, entender o que “sincronizar” duas threads realmente significa, e então construir a ferramenta que resolve o problema na prática: o lock, e sua encarnação mais comum, o mutex.

O Problema da Exclusão Mútua

Volte pro counter++. Aquela linha vira três instruções: lê counter num registrador, incrementa o registrador, escreve de volta. O bug aparece quando uma thread é interrompida entre a leitura e a escrita, e outra thread lê o mesmo valor antigo antes da primeira salvar o resultado. As duas escrevem por cima uma da outra, e um incremento evapora.

O trecho de código que precisa rodar sem essa interferência (aqui, a sequência lê-incrementa-escreve) é o que queremos proteger. E “proteger” significa uma coisa específica: no máximo uma thread pode estar dentro dele por vez.

Vale insistir nesse ponto, porque é onde muita gente entende errado. Exclusão mútua não é sobre duas threads executarem “ao mesmo tempo” no sentido físico. Num computador single-core, duas threads nunca executam de verdade simultaneamente, e o bug do contador acontece do mesmo jeito, porque o escalonador interrompe uma thread no meio das três instruções. O que importa é a ocupação do trecho: uma thread que foi interrompida no meio do counter++ ainda está “dentro” dele, mesmo parada, sem executar nada. Exclusão mútua exige que, enquanto uma thread ocupa o trecho, nenhuma outra entre, esteja ela rodando ou preemptada.

O protocolo de entrada e saída

Pra impor essa ocupação exclusiva, cada thread precisa pedir permissão antes de entrar no trecho protegido e avisar quando sair. A estrutura geral fica assim:

enquanto (true) {
    // ... código que não mexe no recurso compartilhado ...

    protocolo_de_entrada()      // pede permissão pra entrar

    // trecho protegido: no máximo uma thread aqui dentro

    protocolo_de_saida()        // libera pra próxima

    // ... resto ...
}

A pergunta central é: o que colocar em protocolo_de_entrada e protocolo_de_saida pra que a coisa funcione? Uma resposta correta para essa pergunta precisa satisfazer três propriedades. Elas foram formuladas por Dijkstra nos anos 60, e valem para qualquer mecanismo, seja um mutex, um semáforo, ou um algoritmo feito na unha só com variáveis compartilhadas.

Exclusão mútua. No máximo uma thread ocupa o trecho protegido por vez. É a propriedade que dá nome a tudo, e é o que faltava no contador. Sem ela, o counter++ de duas threads se intercala e incrementos se perdem.

Progresso. Se ninguém está no trecho protegido e uma ou mais threads querem entrar, a decisão de qual entra não pode ser adiada pra sempre. Ou seja, o protocolo não pode travar num impasse quando o recurso está livre. Uma “solução” que simplesmente proíbe todo mundo de entrar satisfaz a exclusão mútua de forma trivial, e é inútil justamente por violar o progresso.

Espera limitada. Existe um limite pra quantas vezes outras threads conseguem entrar depois que uma thread pediu pra entrar e antes dela conseguir. Sem isso, uma thread azarada pode ficar eternamente vendo as outras passarem na frente. Esse problema tem nome próprio, starvation, e um mecanismo pode garantir exclusão mútua e progresso e ainda assim deixar uma thread morrer de fome.

Por que não fazer na unha

Uma reação natural é tentar resolver isso sozinho, com uma variável de flag:

int ocupado = 0;

void entrar(void) {
    while (ocupado) { }   // espera enquanto está ocupado
    ocupado = 1;          // marca como ocupado
}

void sair(void) {
    ocupado = 0;
}

Parece razoável, e está errado. while (ocupado) e ocupado = 1 são duas operações separadas. Duas threads podem, ambas, ver ocupado == 0, sair as duas do while, e as duas marcarem ocupado = 1 e entrarem juntas no trecho. O protocolo de entrada tem, ele mesmo, exatamente a race que estamos tentando eliminar. Aninhar a proteção não resolve, só empurra o problema um nível pra baixo.

Existem algoritmos corretos feitos só com leituras e escritas comuns, como o algoritmo de Peterson e o de Dekker, mas eles são engenhosos, limitados a duas threads na forma clássica, e frágeis diante do reordenamento de instruções que o hardware faz. Na prática, ninguém protege seção crítica assim. O que se usa é uma primitiva que resolve o entrar/sair de forma atômica, com apoio do hardware e do sistema operacional. Essa primitiva é o lock.

O que é sincronização

O termo sincronização aparece o tempo todo em concorrência, e costuma ser usado de forma vaga. Vale fixar o que ele significa: sincronizar é impor alguma restrição sobre a ordem relativa em que as ações de threads diferentes acontecem.

Threads sem sincronização são independentes. O escalonador intercala as instruções delas de qualquer jeito, e nenhuma ordem entre threads diferentes é garantida. Sincronizar é justamente abrir mão dessa liberdade em pontos específicos, dizendo “isto aqui não pode acontecer antes daquilo”. Toda vez que você força uma ordem, está sincronizando, e está, de propósito, tornando o programa um pouco mais sequencial num ponto pra torná-lo correto.

Os problemas de sincronização se dividem em duas famílias, e é útil separá-las desde já porque elas pedem ferramentas diferentes.

Exclusão mútua é a família deste capítulo. A restrição é “estas ações não podem se sobrepor”: enquanto uma thread está no counter++, nenhuma outra pode estar. Não importa quem vai primeiro, importa que não seja ao mesmo tempo. A ferramenta é o lock.

Coordenação é a outra família, e a restrição tem outra natureza: “esta ação só pode acontecer depois que aquela condição for verdadeira”. Uma thread que consome itens de uma fila precisa esperar até que exista algum item pra consumir. Uma thread que junta resultados precisa esperar até que todas as outras terminem. Aqui o problema não é impedir sobreposição, é fazer uma thread esperar por um acontecimento de outra. As ferramentas são outras (variáveis de condição, barreiras, semáforos usados como sinal), e são o assunto de um capítulo mais à frente.

A distinção não é meramente acadêmica. Usar a ferramenta errada é uma fonte comum de bugs: gente usando lock pra tentar fazer uma thread esperar por um evento acaba com busy-waiting desperdiçando CPU, e gente usando primitivas de coordenação pra proteger dados acaba sem a exclusão que precisava. Por ora, ficamos na primeira família. O lock resolve exclusão mútua, e é pra ele que vamos agora.

O que é um Lock

Um lock (ou “tranca”) é um objeto com duas operações: adquirir (acquire/lock) e liberar (release/unlock). A regra é simples: no máximo uma thread pode ter o lock adquirido por vez. Se uma thread tenta adquirir um lock que já está com outra, ela bloqueia, ou seja, para de executar e fica esperando, até que a dona atual libere.

Com isso, o protocolo de entrada e saída da seção anterior vira duas chamadas:

adquirir(lock)      // protocolo de entrada
// trecho protegido
liberar(lock)       // protocolo de saída

Quem chega primeiro e adquire o lock entra no trecho. Qualquer outra que chegar enquanto isso fica bloqueada no adquirir. Quando a primeira chama liberar, uma das que estavam esperando é acordada, adquire o lock, e entra. Uma de cada vez, que é exatamente a exclusão mútua que queríamos.

O que faz o adquirir ser atômico

Na seção anterior vimos que tentar fazer isso na unha com uma flag ocupado não funciona, porque while (ocupado) e ocupado = 1 são duas operações e outra thread pode se meter entre elas. O lock resolve isso porque o adquirir usa uma instrução do próprio processador que faz “testar e marcar” de forma indivisível.

O exemplo clássico é o test-and-set: uma instrução que, num único passo que o hardware garante não ser interrompível, lê o valor atual de uma posição de memória e escreve 1 nela, devolvendo o valor que estava lá antes. Em pseudocódigo, o efeito é:

// tudo isto acontece como uma operação atômica, indivisível:
int test_and_set(int *alvo) {
    int antigo = *alvo;
    *alvo = 1;
    return antigo;
}

A diferença pro entrar quebrado da flag é que aqui não tem janela entre o teste e a marcação. Duas threads não conseguem, ambas, ver 0 e marcar 1: a primeira que executar o test_and_set recebe 0 de volta (e entra), e a segunda recebe 1 (e sabe que precisa esperar). O hardware serializa as duas execuções da instrução. Processadores modernos oferecem primitivas assim (xchg, cmpxchg no x86, ou pares como ldrex/strex no ARM), e é sobre elas que os locks são construídos.

Bloquear é diferente de girar

Tem uma decisão embutida no “fica esperando” do adquirir. O que a thread faz enquanto o lock está ocupado? Duas respostas possíveis:

• Girar (spin): ficar num loop testando o lock repetidamente, queimando CPU até ele liberar.
• Dormir: avisar o sistema operacional “me tire de execução até este lock liberar”, cedendo o core pra outra thread rodar.

A escolha entre girar e dormir tem consequências grandes de performance, e cada uma tem seu lugar. Girar desperdiça CPU enquanto espera, mas evita o custo de tirar e recolocar a thread em execução; vale a pena quando a espera é curtíssima. Dormir tem o custo fixo de envolver o sistema operacional, mas libera o core pra trabalho útil; vale a pena quando a espera pode ser longa. O lock que gira é o spinlock, e o lock que dorme, o tipo mais usado no dia a dia, é o mutex.

Mutex

O mutex (de mutual exclusion) é a encarnação mais comum do lock. É o que você vai usar em 90% dos casos em que precisa proteger uma seção crítica. Em vez de mais teoria, vamos direto consertar o contador. O Código 6-1 é o mesmo de sempre, com um mutex protegendo o counter++:

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

int counter = 0;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void *increment(void *arg) {
    for (int i = 0; i < 100000; i++) {
        pthread_mutex_lock(&lock);
        counter++;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main(void) {
    pthread_t tids[10];
    for (int i = 0; i < 10; i++)
        pthread_create(&tids[i], NULL, increment, NULL);
    for (int i = 0; i < 10; i++)
        pthread_join(tids[i], NULL);
    printf("counter = %d\n", counter);
}

$ cc main.c -o main -pthread
$ ./main
counter = 1000000
$ ./main
counter = 1000000
$ ./main
counter = 1000000

1000000, três vezes seguidas, e vai continuar dando 1000000 em qualquer execução. Deixou de ser uma questão de sorte com o escalonamento: não importa como as dez threads se intercalam, o resultado é o mesmo. O não-determinismo continua ali (a ordem em que as threads pegam o lock ainda varia a cada execução), mas ele deixou de afetar a corretude. É isso que a sincronização compra: você abre mão do controle sobre a ordem, mas garante que qualquer ordem produz o resultado certo.

A API da Pthreads

Foram três mudanças em relação ao código quebrado.

Declaramos o mutex com pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER. Esse PTHREAD_MUTEX_INITIALIZER é uma macro que dá ao mutex o estado inicial correto (destravado). Pra mutexes globais ou estáticos, é a forma mais simples de inicializar. Existe também pthread_mutex_init, usada quando o mutex é alocado dinamicamente ou precisa de atributos especiais.

Antes do counter++, chamamos pthread_mutex_lock(&lock). Se o mutex está livre, a thread o adquire e segue. Se está com outra thread, essa chamada bloqueia: a thread é retirada de execução pelo sistema operacional e só volta quando o mutex for liberado. Ela não fica queimando CPU num loop, o que é a diferença entre um mutex e um spinlock.

Depois do counter++, chamamos pthread_mutex_unlock(&lock), liberando o mutex pra próxima thread. Esse par lock/unlock delimita a seção crítica. Tudo que está entre eles roda com exclusão mútua garantida.

O trecho protegido aqui é minúsculo, só um incremento, e é assim que deve ser. O mutex serializa tudo que está dentro dele, então quanto mais código você põe entre o lock e o unlock, mais tempo as outras threads passam bloqueadas esperando. A regra é segurar o mutex pelo menor tempo possível: proteja o acesso ao dado compartilhado, e nada mais.

Esquecer o unlock

O erro mais clássico com mutex é adquirir e esquecer de liberar, ou liberar só em alguns caminhos do código. Considere:

pthread_mutex_lock(&lock);
if (algo_deu_errado) {
    return -1;              // saiu com o mutex ainda travado!
}
counter++;
pthread_mutex_unlock(&lock);

Se algo_deu_errado for verdadeiro, a função retorna sem chamar unlock. O mutex fica travado pra sempre, e a próxima thread que tentar pthread_mutex_lock vai bloquear eternamente. Todo caminho de saída da seção crítica (returns, breaks, gotos de erro) precisa liberar o mutex. Em C isso é responsabilidade sua e é fácil escorregar. Linguagens com destrutores ou blocos protegidos resolvem isso de forma mais segura, como veremos no Kotlin logo abaixo.

Mutex em Kotlin: synchronized

Lá em Criando Threads ficou uma promessa por cumprir: um var counter capturado por várias threads em Kotlin daria uma race, e o compilador não avisaria nada. A correção é a palavra-chave synchronized.

Na JVM, o mecanismo embutido de exclusão mútua é justamente essa palavra-chave. Todo objeto em Kotlin (e Java) tem um lock associado, chamado de monitor, e um bloco synchronized(obj) adquire o monitor de obj na entrada e o libera na saída. O contador protegido fica assim:

import kotlin.concurrent.thread

var counter = 0
val lock = Any()

fun main() {
    val threads = (0 until 10).map {
        thread {
            repeat(100_000) {
                synchronized(lock) {
                    counter++
                }
            }
        }
    }
    threads.forEach { it.join() }
    println("counter = $counter")
}

$ kotlinc main.kt -include-runtime -d main.jar && java -jar main.jar
counter = 1000000

O val lock = Any() cria um objeto qualquer só pra servir de lock. Poderia ser qualquer objeto; o que importa é que todas as threads sincronizem no mesmo objeto, senão cada uma adquire um monitor diferente e a exclusão mútua não acontece.

A vantagem do synchronized sobre o par lock/unlock manual é que ele libera o monitor automaticamente ao sair do bloco, por qualquer caminho, inclusive se uma exceção for lançada lá dentro. O problema do “esquecer o unlock” simplesmente não existe: não tem unlock pra esquecer. O fim do bloco { } é o unlock.

Quando o dado compartilhado vive dentro de um objeto, dá pra ir além e marcar métodos inteiros com @Synchronized:

class Contador {
    private var valor = 0
    @Synchronized fun incrementa() { valor++ }
    @Synchronized fun valor(): Int = valor
}

Um método @Synchronized sincroniza no próprio objeto (this). Enquanto uma thread executa incrementa(), nenhuma outra consegue executar incrementa() nem valor() na mesma instância, porque ambos disputam o mesmo monitor. Isso mantém a proteção junto do dado que ela protege, que é um jeito mais organizado de pensar do que espalhar lock/unlock pelo código.

Uma ressalva importante, porém: @Synchronized torna cada método atômico, mas não uma sequência de chamadas a esses métodos. Proteger cada acesso individual não é a mesma coisa que proteger a lógica que combina vários acessos. Um objeto com todos os métodos @Synchronized ainda pode ser usado de forma incorreta se o código que o chama assume que o estado não muda entre uma chamada e a próxima.

Exercícios

O que você tem em mãos até aqui: o problema da exclusão mútua e as três propriedades de Dijkstra (exclusão mútua, progresso, espera limitada), a ideia de lock, o test_and_set atômico por baixo dele, a escolha entre girar e dormir, e o mutex na prática (pthread_mutex_t em C, synchronized e @Synchronized em Kotlin). Ainda não entramos em deadlock, semáforos ou variáveis de condição, então nenhum exercício aqui precisa disso.

Compile o C com cc main.c -o main -pthread. Pro Kotlin, kotlinc main.kt -include-runtime -d main.jar && java -jar main.jar.

Fáceis

6.1 Pegue o contador com mutex e mude pra 20 threads incrementando 50.000 vezes cada. O resultado esperado é 1000000. Confirme que ele sai igual em toda execução.

6.2 No mesmo contador, comente as chamadas pthread_mutex_lock e pthread_mutex_unlock (deixando só o counter++ dentro do laço) e rode três vezes. Anote os três valores. Agora descomente e rode mais três. Descreva a diferença que você vê entre os dois conjuntos de resultados.

6.3 Explique, com suas palavras, por que a solução “na unha” com uma flag ocupado (a do capítulo do problema da exclusão mútua) viola a exclusão mútua. Aponte exatamente as duas operações que uma segunda thread consegue enfiar no meio.

Médios

6.4 Escreva um programa em C com um mutex protegendo duas variáveis globais, soma e contagem, que várias threads atualizam juntas: cada thread, num laço, faz soma += valor; contagem++. Ao final, a main imprime a média soma / contagem. Garanta que as duas variáveis são atualizadas dentro da mesma seção crítica, e explique o que poderia dar errado se cada uma tivesse o seu próprio mutex.

6.5 O Mutex segura o lock em volta de um único counter++. Escreva uma versão em que cada thread, em vez de travar e destravar 100.000 vezes, calcula a soma parcial numa variável local e trava o mutex uma única vez pra somar sua parcial no counter global. Compare mentalmente quantas vezes o mutex é adquirido nas duas versões, e explique por que a segunda tende a ser bem mais rápida sem deixar de estar correta.

6.6 Traduza o exercício 6.4 pra Kotlin usando synchronized(lock). Depois reescreva encapsulando soma e contagem numa classe com métodos @Synchronized. A versão com a classe protege corretamente a operação “atualizar as duas de uma vez”? Justifique, lembrando da ressalva sobre sequências de chamadas a métodos @Synchronized no final do capítulo do Mutex.

6.7 As três propriedades de Dijkstra são exclusão mútua, progresso e espera limitada. Para cada uma das “soluções” abaixo, diga qual propriedade ela viola:

1. Um protocolo que nunca deixa nenhuma thread entrar na seção crítica.
2. Um lock justo na média, mas em que uma thread específica sempre perde a disputa pras outras e pode esperar indefinidamente.
3. A flag ocupado feita na unha, que deixa duas threads entrarem juntas.

Difíceis

6.8 Considere este trecho, que adquire o mutex e sai da função por um caminho de erro:

pthread_mutex_lock(&lock);
resultado = processa(dado);
if (resultado < 0)
    return resultado;          // sai daqui
counter += resultado;
pthread_mutex_unlock(&lock);

Descreva o que acontece com a próxima thread que chamar pthread_mutex_lock(&lock) quando processa devolve um valor negativo. Depois reescreva o trecho pra que o mutex seja liberado em todos os caminhos de saída, sem mudar a lógica.

6.9 Implemente um lock rudimentar usando a função atômica embutida do GCC/Clang __sync_lock_test_and_set(&flag, 1), que faz o test-and-set descrito no capítulo do lock de forma indivisível (devolve o valor antigo de flag e escreve 1). Seu adquirir deve girar enquanto o valor devolvido for 1, e seu liberar deve zerar a flag com __sync_lock_release(&flag). Proteja o contador com ele e verifique que o resultado dá 1000000.

Dica: while (__sync_lock_test_and_set(&flag, 1)) { } é o laço de espera. Esse é literalmente um spinlock: ele gira em vez de dormir.

6.10 O lock que você escreveu no 6.9 gira (queima CPU) enquanto espera; o pthread_mutex_t dorme (cede o core). Para cada cenário abaixo, diga qual dos dois é a escolha melhor e por quê, usando o trade-off girar-vs-dormir do capítulo do lock:

1. A seção crítica é um counter++, e há mais threads do que cores.
2. A seção crítica é um counter++, cada thread roda no seu próprio core, e a disputa pelo lock é curtíssima.
3. A seção crítica faz uma leitura de disco que leva dezenas de milissegundos.

Acesso Concorrente e Seus Problemas

Você já sabe proteger uma seção crítica: envolve o acesso compartilhado num mutex, ou num bloco synchronized, e a exclusão mútua garante que o contador soma 1000000 toda vez. Mas até agora tratamos os bugs que o lock previne de forma meio informal, chamando tudo de “as threads pisaram umas nas outras”.

Este capítulo dá nomes precisos a esses bugs, e separa conceitos que vivem sendo confundidos, mesmo por programadores experientes. Data race e race condition não são a mesma coisa, apesar de quase todo mundo usar os dois termos como sinônimos. Um pode existir sem o outro, e a diferença muda o jeito de raciocinar sobre o problema e sobre a correção. Por baixo dos dois está a noção de seção crítica, que já usamos na prática e que agora vale definir com cuidado.

Saber usar o mutex é metade do trabalho. A outra metade é reconhecer, no seu próprio código, quais acessos são perigosos e por quê, e é disso que trata este capítulo.

Data Race

Um data race acontece quando duas threads acessam a mesma posição de memória sem nenhuma ordem imposta entre os acessos, e pelo menos um deles é uma escrita. As três condições precisam valer juntas. Duas leituras não são um data race, porque ler não muda nada. E se algum mecanismo de sincronização garante que um acesso acontece antes do outro, também não tem race, porque existe uma ordem.

Repare que a definição não fala em “ao mesmo tempo”. Isso é proposital, e é um ponto onde muita gente tropeça. Um data race não precisa de dois cores rodando de verdade em paralelo. Num computador single-core, só uma thread executa por vez, mas o escalonador interrompe uma thread no meio do counter++ (lembre-se que ele vira três instruções) e passa a vez pra outra. A thread interrompida leu o valor antigo, a outra escreve por cima, e quando a primeira volta ela sobrescreve com o resultado do valor velho. As duas threads não tocaram a memória no mesmo instante físico, e mesmo assim o acesso de uma se intercalou com o da outra sem ordem nenhuma garantindo quem vem antes. Isso basta. Paralelismo real deixa o data race mais provável e mais frequente, mas não é ele que cria o problema. O problema é a ausência de ordem, e ela existe em qualquer sistema concorrente, com um core ou com noventa e seis.

A versão sem mutex do contador tinha as três condições: várias threads escrevendo em counter, várias lendo, e nenhum lock no meio. Vamos pegar aquela versão quebrada e apontar uma ferramenta pra ela. O compilador tem um detector de data races embutido, o ThreadSanitizer, ligado com a flag -fsanitize=thread:

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

int counter = 0;

void *increment(void *arg) {
    for (int i = 0; i < 100000; i++)
        counter++;
    return NULL;
}

int main(void) {
    pthread_t tids[10];

    for (int i = 0; i < 10; i++)
        pthread_create(&tids[i], NULL, increment, NULL);
    for (int i = 0; i < 10; i++)
        pthread_join(tids[i], NULL);

    printf("counter = %d\n", counter);
}

$ cc main.c -o main -pthread -fsanitize=thread -g
$ ./main
==================
WARNING: ThreadSanitizer: data race (pid=154701)
  Read of size 4 at 0x58acd8fc7064 by thread T2:
    #0 increment main.c:8 (main+0x11f9)

  Previous write of size 4 at 0x58acd8fc7064 by thread T1:
    #0 increment main.c:8 (main+0x1211)

  Location is global 'counter' of size 4 at 0x58acd8fc7064 (main+0x4064)

  Thread T2 (tid=154704, running) created by main thread at:
    #0 pthread_create <null> (libtsan.so.2+0x5fb47)
    #1 main main.c:16 (main+0x128e)

  Thread T1 (tid=154703, running) created by main thread at:
    #0 pthread_create <null> (libtsan.so.2+0x5fb47)
    #1 main main.c:16 (main+0x128e)

SUMMARY: ThreadSanitizer: data race main.c:8 in increment
==================
counter = 809976
ThreadSanitizer: reported 2 warnings

A ferramenta aponta o dedo direto pra linha 8, counter++, e diz exatamente o que aconteceu: a thread T2 leu counter, e a thread T1 já tinha escrito naquela mesma posição, sem nada garantindo a ordem entre as duas. Ela ainda mostra onde cada thread foi criada. Isso é bem diferente de olhar pra saída 809976 e ficar adivinhando o que deu errado. O data race é um defeito estrutural do programa, e o ThreadSanitizer o encontra mesmo numa execução que, por sorte, tivesse dado o resultado certo.

Data race é comportamento indefinido

Em C e C++, um data race não é só “um bug que às vezes dá resultado errado”. O modelo de memória dessas linguagens diz que um programa com data race tem comportamento indefinido (undefined behavior). Isso é mais forte do que parece. Não é que counter vai receber um valor errado. É que o compilador tem permissão pra assumir que data races não acontecem, e otimizar o código com base nessa suposição.

Considere um loop que lê uma flag compartilhada:

int done = 0;

void *worker(void *arg) {
    while (!done) {
        // faz trabalho
    }
    return NULL;
}

Como nada dentro do while modifica done, o compilador pode concluir que done nunca muda durante o loop, carregar o valor uma vez num registrador, e transformar o teste num if (!done) while (true) {}. Se outra thread setar done = 1 mais tarde, a thread do worker nunca vai perceber. Ela fica presa num loop infinito que, olhando só pra esse código-fonte, não deveria existir. O compilador não introduziu um bug: ele executou uma otimização perfeitamente válida, porque a suposição de que não existem data races é uma premissa da linguagem.

É por isso que “funcionou na minha máquina” não significa nada num programa com data race. O mesmo código-fonte, compilado com -O2 em vez de -O0, ou por outro compilador, ou pra outra arquitetura, pode se comportar de forma completamente diferente, porque comportamento indefinido não tem obrigação de ser consistente¹.

Como remover o data race

O ThreadSanitizer não reclamou do resultado errado. Reclamou da falta de coordenação entre os acessos. Qualquer coisa que estabeleça uma ordem entre a escrita de uma thread e a leitura de outra tira as três condições do data race. O mutex que usamos pra proteger o counter++ faz exatamente isso: enquanto uma thread segura o lock, nenhuma outra lê nem escreve counter, e a ordem entre os acessos deixa de ser arbitrária. Uma operação atômica também resolve, trocando a leitura, o incremento e a escrita por uma única instrução indivisível.

O que importa entender aqui é a natureza do defeito. O data race é uma propriedade dos acessos à memória: existe, ou não existe, independente de qual intercalação o escalonador escolheu naquela execução. Ele pode estar num programa que passou em todos os testes. E, como vimos, num programa que ainda por cima imprimiu o número certo.

1. Na JVM (Java, Kotlin) o modelo de memória é mais brando: um data race não é comportamento indefinido, e o programa continua sendo uma máquina de estados bem-definida. Mas continua quebrado de outro jeito. Sem sincronização, uma thread pode simplesmente nunca enxergar a escrita feita por outra, porque o valor ficou num cache de core ou num registrador. É o problema de visibilidade, e a solução (campos volatile, blocos synchronized, AtomicInteger) também passa por estabelecer uma ordem entre os acessos. ↩

Race Condition

Uma race condition é quando a corretude do programa depende da ordem ou do tempo em que as threads são escalonadas. Se existe uma intercalação que leva o programa a um estado errado, tem uma race condition, mesmo que essa intercalação seja rara.

Isso soa parecido com data race, e por isso os dois termos vivem sendo trocados. Mas eles falam de coisas diferentes. Data race é sobre acessos à memória sem coordenação. Race condition é sobre a lógica do programa depender de tempo. A confusão é natural, porque no contador sem sincronização os dois estavam presentes ao mesmo tempo. Só que dá pra ter um sem o outro. E o caso mais instrutivo é o de uma race condition que não tem nenhum data race.

Uma race condition sem data race

Imagine uma conta bancária cujo saldo é lido e escrito sempre de forma protegida. Vamos usar Kotlin, porque a JVM deixa o exemplo limpo: cada operação individual é sincronizada, então não tem data race nenhum sobre o saldo.

class Conta(private var total: Int) {
    @Synchronized fun saldo(): Int = total
    @Synchronized fun debita(valor: Int) { total -= valor }
}

fun sacar(conta: Conta, valor: Int) {
    if (conta.saldo() >= valor) {   // checa
        conta.debita(valor)         // age
    }
}

Tanto saldo() quanto debita() são @Synchronized. Nenhuma thread lê o saldo enquanto outra está no meio de uma escrita. Um detector de data race passa esse código sem uma reclamação sequer, porque não existe acesso desprotegido à memória.

E mesmo assim sacar está errado. O problema está entre as duas linhas. A função checa o saldo, e só depois debita, e nada garante que o saldo continua o mesmo entre uma coisa e outra. Suponha uma conta com saldo 100, e duas threads tentando sacar 100 cada, ao mesmo tempo:

As duas threads leram 100, as duas passaram no teste, e as duas debitaram. A conta terminou com saldo -100, sacando 200 de uma conta que tinha 100. Cada operação foi atômica. A sequência checa-então-age não foi, e é aí que a ordem de escalonamento decide se o programa está correto ou não.

Esse padrão tem nome, check-then-act, e é uma das formas mais comuns de race condition. Proteger cada acesso individualmente não resolve, porque o problema não está em nenhum acesso isolado. Está no fato de que a decisão tomada no passo 3 já estava velha no passo 5. O que precisa ser indivisível é o par checa-e-age inteiro, não cada metade.

Data race e race condition são independentes

Já temos os dois lados. O contador sem sincronização era data race e race condition. O saque é race condition sem data race. Falta o terceiro caso, e ele também existe: dá pra ter um data race que, na prática, não corrompe a lógica do programa, como um contador de estatísticas aproximado onde perder alguns incrementos não muda nenhuma decisão. Continua sendo comportamento indefinido em C, continua sendo uma prática ruim, mas não é uma race condition no sentido de levar o programa a um estado logicamente errado.

O que fica: eliminar data races é necessário, mas não é suficiente. Um programa pode estar livre de data races, com todos os acessos devidamente protegidos, e ainda assim produzir um saldo negativo porque a lógica dele depende de uma ordem que o escalonador não garante.

Critical Section

Nos dois problemas anteriores, existia sempre um trecho de código que não podia ter duas threads dentro dele ao mesmo tempo. No contador, era o counter++. No saque, era o par checa-então-debita. Esse trecho tem um nome: seção crítica (critical section). É a parte do código que acessa um recurso compartilhado e que precisa rodar sem interferência de outras threads pra manter o programa correto.

O termo é de Dijkstra, dos anos 60, e já apareceu aqui de forma prática. Quando protegemos o counter++ com um mutex, a seção crítica era exatamente o trecho entre o lock e o unlock. As três propriedades que uma solução de exclusão mútua precisa satisfazer, exclusão mútua, progresso e espera limitada, foram enunciadas em torno justamente desse conceito de seção crítica, e estão no capítulo sobre o problema da exclusão mútua. O que falta aqui não é repetir aquilo, é desenvolver a habilidade de reconhecer uma seção crítica no seu próprio código, antes de sair aplicando mutex em tudo.

A janela de leitura-modificação-escrita

O caso mais comum de seção crítica é a sequência read-modify-write: uma thread lê um estado compartilhado, calcula algo a partir dele, e escreve o resultado de volta. O counter++ é o exemplo mínimo. Uma única linha, mas três instruções: lê counter num registrador, incrementa o registrador, escreve de volta.

O perigo mora na janela entre a leitura e a escrita. Enquanto uma thread está com o valor no registrador, incrementando, o counter na memória ainda tem o valor antigo. Se outra thread ler counter nesse intervalo, ela lê o valor desatualizado, e as duas acabam gravando o mesmo resultado. É por isso que a sequência inteira precisa se comportar como uma operação indivisível, do começo da leitura até o fim da escrita. Exclusão mútua sobre essa janela é o que transforma o 809976 de volta em 1000000.

O saque do capítulo sobre race condition é a mesma janela, só que mais espalhada: lê o saldo (if conta.saldo() >= valor), decide (passou no teste), escreve (conta.debita(valor)). Entre a leitura e a escrita, o saldo pode ter mudado. Que a leitura e a escrita estejam em linhas diferentes, ou até em funções diferentes, não muda a natureza do problema.

Reconhecendo seções críticas no seu código

O padrão a procurar é sempre o mesmo: uma decisão ou um cálculo baseado num estado compartilhado, seguido de uma modificação desse estado, com a suposição implícita de que o estado não mudou no meio do caminho. Sempre que você vir esse formato, tem uma seção crítica ali, e ela precisa rodar de forma atômica em relação às outras threads.

Reconhecer essas janelas é o que separa quem protege o programa certo de quem sai espalhando lock aleatoriamente (o que, além de não garantir corretude, ainda mata a performance, porque cada lock desnecessário serializa threads que poderiam rodar em paralelo). O olho pra identificar seções críticas vem com prática, e é uma habilidade que vale mais do que decorar qual primitiva usar: a primitiva você escolhe depois de saber o que precisa proteger, nunca antes.

Exercícios

Este capítulo te deu vocabulário preciso: data race (acesso concorrente à mesma memória, sem ordem, com ao menos uma escrita), race condition (corretude depende da ordem de escalonamento), a diferença entre os dois, o padrão check-then-act, a noção de seção crítica, e o ThreadSanitizer como detector de data races. Os exercícios giram em torno de reconhecer e classificar esses defeitos, que é a habilidade que o capítulo quis construir.

Compile o C com cc main.c -o main -pthread. Para o ThreadSanitizer, adicione -fsanitize=thread -g.

Fáceis

7.1 Para cada situação, diga se há data race, race condition, os dois, ou nenhum:

1. Duas threads leem a mesma variável global e nenhuma escreve.
2. Dez threads fazem counter++ na mesma global, sem lock.
3. Uma thread escreve num arquivo e outra, sem coordenação, lê o mesmo arquivo.
4. Cada thread escreve numa posição diferente de um array (v[id] = ...), sem lock.

7.2 Rode o contador sob o ThreadSanitizer e leia a saída. Aponte, na mensagem do TSan, a linha do código-fonte que ele acusa, e diga qual thread fez a leitura e qual fez a escrita conflitante.

7.3 No exemplo do saque (race condition sem data race), diga qual é a seção crítica: o menor trecho de código que precisaria rodar de forma indivisível pra sacar ficar correto.

Médios

7.4 Pegue a versão quebrada do contador e proteja o counter++ com um mutex (você já sabe fazer isso do capítulo anterior). Rode de novo sob o ThreadSanitizer. O TSan ainda acusa data race? Explique o que a proteção mudou em relação às três condições que definem um data race.

7.5 O programa abaixo mantém um “máximo visto até agora” compartilhado. Encontre a seção crítica e explique por que, mesmo cada novo > maximo sendo uma leitura simples, o programa pode terminar com um maximo menor do que o maior valor processado:

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

int maximo = 0;

int valores[][4] = {
    {10, 55, 23, 80},
    {70, 12, 91, 34},
    {45, 88, 19, 60},
};

void *processa(void *arg) {
    int *linha = arg;
    for (int i = 0; i < 4; i++) {
        int novo = linha[i];
        if (novo > maximo)      // checa
            maximo = novo;      // age
    }
    return NULL;
}

int main(void) {
    pthread_t tids[3];
    for (int i = 0; i < 3; i++)
        pthread_create(&tids[i], NULL, processa, valores[i]);
    for (int i = 0; i < 3; i++)
        pthread_join(tids[i], NULL);
    printf("maximo = %d (esperado: 91)\n", maximo);
}

Dica: é o mesmo formato check-then-act do saque, com if (novo > maximo) no lugar do if (saldo >= valor).

7.6 Escreva você mesmo um exemplo, em Kotlin, de uma race condition sem data race: cada acesso individual ao estado é @Synchronized, mas a lógica que combina dois acessos ainda está errada. Não repita o saque do capítulo; invente outra situação check-then-act (por exemplo, reservar o último ingresso de um estoque, ou incrementar um id só se ele ainda não existe).

Difíceis

7.7 O capítulo afirma que data race e race condition são independentes, e dá os três casos. Construa, em código, um exemplo de cada:

1. Data race e race condition ao mesmo tempo.
2. Race condition sem data race.
3. Data race sem race condition (um em que perder alguns acessos não muda nenhuma decisão do programa).

Para o caso 3, argumente por que ele continua sendo comportamento indefinido em C, apesar de “não estragar” o resultado que interessa.

7.8 No trecho de flag do capítulo do data race:

int done = 0;

void *worker(void *arg) {
    while (!done) {
        // faz trabalho
    }
    return NULL;
}

com outra thread fazendo done = 1 mais tarde, o worker pode nunca perceber a mudança. Compile um programa com esse padrão em -O0 e depois em -O2 e veja se o comportamento muda. Explique, com base no que o capítulo diz sobre comportamento indefinido e otimização, por que o compilador tem permissão pra transformar o laço em algo que nunca relê done.

Dica: você vai precisar de uma segunda thread que dorme um pouco (usleep) e depois seta done = 1. Rode com timeout pra não travar o terminal caso o laço vire infinito.

7.9 Reforce o programa do exercício 7.5 até ele ficar correto usando um mutex, e depois rode-o sob o ThreadSanitizer pra confirmar que o data race sumiu. Em seguida, responda: proteger cada if (novo > maximo) com seu próprio par lock/unlock, mas liberando o lock entre a checagem e a atribuição, resolve o problema? Justifique ligando com o que o capítulo diz sobre check-then-act precisar ser indivisível inteiro, não em metades.

Patologias de Locks

O lock resolve a exclusão mútua, mas abre a porta pra uma classe nova de problemas. O contador sem sincronização dava resultado errado; os problemas deste capítulo são de outra natureza: o programa para de fazer progresso, ou faz uma thread esperar pra sempre. Nenhum deles corrompe dados. Eles travam ou emperram a execução.

Vale conectar os três com as propriedades que uma solução de exclusão mútua precisa garantir. Deadlock e livelock são falhas de progresso: em ambos, as threads deixam de avançar, num caso porque estão todas bloqueadas esperando umas às outras, no outro porque estão todas ocupadas reagindo umas às outras sem chegar a lugar nenhum. Starvation é uma falha de espera limitada: o programa como um todo progride, mas uma thread específica fica indefinidamente sem a sua vez.

Os três vêm de usar locks, e os três têm solução. A diferença entre saber usar um mutex e saber escrever código concorrente correto está, em boa parte, em reconhecer e evitar essas três patologias.

Deadlock

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

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

pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER;

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

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

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

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

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

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

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

As quatro condições de Coffman

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

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

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

Quebrando a espera circular: ordem global de locks

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

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

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

pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER;

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

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

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

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

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

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

Starvation

Vamos medir um mutex sob disputa. O experimento coloca duas threads idênticas brigando pelo mesmo lock sem parar, cada uma contando quantas vezes conseguiu adquiri-lo em dois segundos. Nenhuma tem prioridade, nenhuma segura o lock por mais tempo que a outra: o código das duas é exatamente o mesmo. Vejamos os números primeiro:

$ ./main
thread 0: 23700713 aquisicoes
thread 1: 23120329 aquisicoes
pior rajada: 95700 aquisicoes seguidas sem uma das threads entrar

As duas primeiras linhas parecem tranquilizadoras. Cerca de 23 milhões de aquisições pra cada uma, praticamente empatado, que é o que você esperaria de duas threads iguais. Se olhasse só pro total, concluiria que o mutex trata as duas com perfeita justiça.

A terceira linha conta outra história. Em algum momento da execução, uma das threads adquiriu o lock quase 96 mil vezes seguidas antes da outra conseguir a sua vez uma única vez. Durante essa rajada, a thread preterida estava viva, pronta, chamando pthread_mutex_lock, e simplesmente não entrava. O total é justo na média, mas a distribuição tem picos em que uma thread fica de fora por dezenas de milhares de rodadas seguidas. E como as duas threads são iguais, não dá pra culpar nenhuma característica de uma delas: a rajada é uma propriedade do mutex, não das threads.

Esse é o fenômeno da starvation (inanição): uma thread não consegue progredir porque outra está sempre à sua frente na disputa por um recurso. Repare que não é deadlock. No deadlock, ninguém avança; aqui o programa como um todo voa, executando mais de 46 milhões de aquisições em dois segundos. O que falha é a garantia de que cada thread terá a sua vez em tempo razoável, aquela terceira propriedade do problema da exclusão mútua, a espera limitada.

Por que o mutex faz isso

O programa que gerou os números acima está no Código 8-3. Cada thread guarda quantas aquisições no total já tinham acontecido da última vez que ela entrou, e assim mede o maior intervalo em que ficou de fora:

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

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
int rodando = 1;                          // sempre acessado com o lock
long total[2] = {0, 0}, max_gap = 0;

void *worker(void *arg) {
    int eu = *(int *)arg;
    long last = -1;
    for (;;) {
        pthread_mutex_lock(&lock);
        if (!rodando) { pthread_mutex_unlock(&lock); break; }
        long agora = total[0] + total[1];
        if (last >= 0) {                  // pula a primeira aquisição
            long g = agora - last;        // aquisições desde a última minha
            if (g > max_gap) max_gap = g;
        }
        last = agora;
        total[eu]++;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

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

    struct timespec ts = {2, 0};
    nanosleep(&ts, NULL);
    pthread_mutex_lock(&lock);
    rodando = 0;
    pthread_mutex_unlock(&lock);

    pthread_join(t[0], NULL);
    pthread_join(t[1], NULL);
    printf("thread 0: %ld aquisicoes\n", total[0]);
    printf("thread 1: %ld aquisicoes\n", total[1]);
    printf("pior rajada: %ld aquisicoes seguidas sem uma das threads entrar\n", max_gap);
}

Rode você mesmo e o número da pior rajada vai variar bastante de uma execução pra outra, de algumas dezenas de milhares a mais de cem mil. Essa própria variabilidade é parte do problema: o pior caso não tem teto previsível.

A variável rodando é lida e escrita sempre com o mutex segurado, tanto pelas threads quanto pela main que a zera pra encerrar o teste. Isso não é firula: se a main escrevesse rodando = 0 fora do lock enquanto as threads leem dentro, teríamos exatamente o data race que estudamos, com todo o comportamento indefinido que ele traz. O flag de parada compartilhado precisa da mesma proteção que qualquer outro dado compartilhado.

A causa da rajada está em como um mutex acorda quem espera. Quando uma thread libera o lock e imediatamente tenta pegá-lo de novo, ela já está executando, com seus dados quentes no cache do core. A outra thread, que estava bloqueada esperando, precisa ser acordada pelo sistema operacional, recolocada em execução, e migrada de volta pro core. Nesse meio tempo, quem acabou de soltar já pegou de novo. O mutex do glibc não promete justiça: ele entrega o lock a quem estiver em melhor posição pra pegá-lo, e quem acabou de rodar está sempre em melhor posição que quem está dormindo. Enquanto uma das duas mantém o embalo, ela fura a fila repetidamente, comportamento que tem nome: barging.

Mutexes justos

A solução é usar um lock que garanta ordem de chegada, um mutex justo (fair). Um mutex justo mantém uma fila de quem está esperando e entrega o lock na ordem em que as threads chegaram, custe o que custar em performance. E custa: forçar a ordem de chegada significa acordar a próxima da fila mesmo quando seria mais rápido deixar a thread atual pegar de novo, o que derruba o número total de aquisições por segundo. Justiça se compra com throughput, e a API padrão da Pthreads nem oferece essa opção diretamente, sinal de que o padrão da indústria é abrir mão da justiça por velocidade.¹

Na maioria dos programas essa escolha é acertada, porque nenhuma thread realmente depende de pegar o lock dentro de uma janela de tempo específica: 96 mil aquisições de atraso, num loop que faz 23 milhões, somem no ruído. O barging vira problema de verdade quando alguma thread tem um prazo a cumprir, um pedido de rede pra responder, um quadro de vídeo pra renderizar, e é justamente aí, quando o pior caso importa mais que a média, que a starvation deixa de ser curiosidade e vira bug.

1. Linguagens de mais alto nível costumam expor a escolha. Na JVM, por exemplo, ReentrantLock(true) pede explicitamente a política justa, enquanto o lock padrão não promete nada sobre ordem de chegada. ↩

Livelock

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

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

De onde o livelock aparece

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

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

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

pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER;

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

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

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

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

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

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

Por que ele quase nunca gira pra sempre

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

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

Quebrando a simetria

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

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

pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER;

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

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

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

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

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

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

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

Outros Locks e Semáforos

O mutex resolve a exclusão mútua e é o que você vai usar na esmagadora maioria dos casos. Mas ele é um ponto num espaço de escolhas, e às vezes o ponto errado. Cada primitiva deste capítulo muda um eixo do mutex, mantendo o resto.

O spinlock muda como a thread espera: em vez de dormir quando o lock está ocupado, ela fica girando. O semáforo muda quantas threads entram: em vez de uma só, ele deixa passar até um número que você escolhe, e com isso escapa da exclusão mútua pura e vira também uma ferramenta de coordenação. O read-write lock muda quem conflita com quem: várias threads que só leem podem entrar juntas, e a exclusão vale só quando alguém escreve.

Nenhum deles substitui o mutex como padrão. Cada um ganha do mutex numa situação específica e perde feio fora dela, e a parte que importa é reconhecer qual situação é qual.

Spinlock

Já sabemos o que é um spinlock: o lock que, em vez de dormir esperando, fica girando num loop testando o lock até ele liberar. A pergunta que ficou em aberto é quando isso vale a pena. A resposta é um número, então vamos medir.

O experimento é o mesmo dos dois lados: threads incrementando um contador compartilhado dois milhões de vezes cada, com uma seção crítica curtíssima (um counter++). Uma rodada protege o contador com um mutex, a outra com um spinlock, e cronometramos as duas. Com só duas threads:

mutex     2 threads: 0.181s
spinlock  2 threads: 0.076s

O spinlock terminou em menos da metade do tempo. Com só duas threads e uma seção crítica de um incremento, o lock quase nunca está ocupado quando a outra thread chega, e quando está, é por pouquíssimo tempo. Dormir e ser acordado, nesse cenário, é puro desperdício: o custo de envolver o sistema operacional pra tirar e recolocar a thread em execução é maior que a espera em si. O spinlock corta esse custo: gira umas poucas voltas e pega o lock, sem nunca chamar o sistema operacional para dormir.

Quando o spinlock desanda

Agora o mesmo programa, sem mexer em nada além do número de threads. Primeiro com uma thread por core (a máquina do teste tem 16), depois com quatro vezes mais threads que cores:

mutex    16 threads: 1.724s
spinlock 16 threads: 5.401s

mutex    64 threads: 5.623s
spinlock 64 threads: 94.340s

Com 16 threads o spinlock já perdeu, gastando três vezes o tempo do mutex. Com 64, ele não é só mais lento: é catástrofe, dezessete vezes pior. O mesmo lock que ganhava por mais de 2x virou perda por 17x, sem mudar uma linha de código, só o número de threads.

Duas coisas apodrecem ao mesmo tempo. A primeira é a disputa: com dezesseis threads girando na mesma posição de memória, cada core que quer testar o lock precisa puxar aquela linha de cache pra si, invalidando a cópia dos outros. O lock vira um ping-pong de coerência de cache entre os cores, e as threads gastam mais tempo brigando pela linha do que fazendo trabalho.

A segunda é pior e é a razão de fundo pra evitar spinlock fora de nichos. Quando há mais threads que cores, o sistema operacional preempta threads no meio da execução pra dar vez às outras. Se ele preempta uma thread enquanto ela segura o spinlock, todas as outras que querem o lock ficam girando, queimando CPU a plena carga, esperando um lock cuja dona nem está executando pra poder liberar. Elas giram uma fatia de tempo inteira à toa, até o escalonador finalmente rodar a dona de novo e ela soltar. Um mutex não sofre disso: quem não consegue o lock dorme, o core fica livre pra rodar a thread que segura o lock, ela termina e libera mais rápido.

A API da Pthreads

O tipo é o pthread_spinlock_t, e as operações espelham as do mutex, com spin no lugar de mutex:

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

long counter = 0;
pthread_spinlock_t lock;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_spin_lock(&lock);
        counter++;
        pthread_spin_unlock(&lock);
    }
    return NULL;
}

int main(void) {
    pthread_spin_init(&lock, 0);          // 0: compartilhado só entre threads deste processo
    pthread_t t[2];
    pthread_create(&t[0], NULL, increment, NULL);
    pthread_create(&t[1], NULL, increment, NULL);
    pthread_join(t[0], NULL);
    pthread_join(t[1], NULL);
    pthread_spin_destroy(&lock);
    printf("counter = %ld\n", counter);
}

$ cc main.c -o main -pthread
$ ./main
counter = 2000000

A diferença pro mutex é só de tipo e nome de função. Não existe inicializador estático análogo ao PTHREAD_MUTEX_INITIALIZER, então o spinlock é sempre montado em runtime com pthread_spin_init, e o primeiro argumento diz se ele é compartilhado entre processos ou só entre threads do mesmo processo. O pthread_spin_destroy no fim libera os recursos dele.

Repare que o spinlock não oferece nada análogo ao contraste que separava dormir de girar: ele só sabe girar. É por isso que ele é uma ferramenta de nicho, e não o padrão. O lugar dele é dentro do próprio sistema operacional e de estruturas de dados de baixíssima latência, onde as seções críticas são medidas em nanossegundos e o código roda com a preempção sob controle. Fora desse nicho, o mutex é a escolha certa, e o custo de dormir que ele paga se paga de volta na primeira vez que uma thread é preemptada segurando o lock.

Semáforos

Um mutex deixa uma thread por vez na seção crítica. E se o recurso protegido comportasse três ao mesmo tempo, ou dez? Um pool com três conexões de banco pode atender três threads simultâneas; a quarta precisa esperar uma das três liberar. Um mutex não sabe expressar isso, porque ele só conta até um: ocupado ou livre.

O semáforo é essa generalização. Ele guarda um contador inteiro não-negativo e oferece duas operações sobre ele. Uma decrementa o contador; se ele já está em zero, a thread bloqueia até que dê pra decrementar. A outra incrementa o contador, possivelmente acordando alguma thread que esperava. Dijkstra, que inventou a primitiva, chamou as duas de P (a que decrementa e pode esperar) e V (a que incrementa e libera). O contador representa quantas unidades do recurso ainda estão disponíveis.

Com o contador inicializado em um, você tem de volta o mutex: a primeira thread decrementa pra zero e entra, qualquer outra encontra zero e espera, a primeira incrementa de volta pra um ao sair. Esse caso é o semáforo binário. Inicializado em N, ele vira um semáforo contador que deixa N threads passarem antes de começar a bloquear.

Um estacionamento com N vagas

O Código 9-2 modela um estacionamento de três vagas com oito carros chegando ao mesmo tempo. O semáforo vagas começa em três, e cada carro faz P pra entrar e V pra sair:

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

sem_t vagas;

void *carro(void *arg) {
    int id = *(int *)arg;
    sem_wait(&vagas);          // P: pega uma vaga, ou espera se não tem
    printf("carro %d estacionou\n", id);
    usleep(100000);            // fica um tempo estacionado
    printf("carro %d saiu\n", id);
    sem_post(&vagas);          // V: libera a vaga
    return NULL;
}

int main(void) {
    sem_init(&vagas, 0, 3);    // 3 vagas; o 0 do meio: compartilhado só entre threads
    pthread_t t[8]; int id[8];
    for (int i = 0; i < 8; i++) { id[i] = i; pthread_create(&t[i], NULL, carro, &id[i]); }
    for (int i = 0; i < 8; i++) pthread_join(t[i], NULL);
    sem_destroy(&vagas);
    return 0;
}

$ cc main.c -o main -pthread
$ ./main
carro 0 estacionou
carro 2 estacionou
carro 1 estacionou
carro 2 saiu
carro 0 saiu
carro 1 saiu
carro 3 estacionou
carro 5 estacionou
carro 4 estacionou
...

Em nenhum momento existem mais de três carros estacionados ao mesmo tempo. Assim que um sai e faz sem_post, o contador sobe pra um, e uma das threads paradas no sem_wait acorda, decrementa de volta pra zero, e entra. A sem_wait é o P e a sem_post é o V; o sem_init recebe o valor inicial do contador no terceiro argumento, e o segundo argumento, aqui 0, diz que o semáforo é compartilhado só entre threads do mesmo processo.

Semáforo binário não é mutex

É tentador olhar pro semáforo binário e concluir que ele é só um mutex com outro nome. A diferença está em quem pode liberar. Um mutex tem dono: a thread que adquire é a única que pode liberar, e várias implementações checam isso e recusam um unlock vindo de outra thread. O semáforo não tem dono. Qualquer thread pode chamar sem_post, inclusive uma que nunca chamou sem_wait.

Essa ausência de dono é exatamente o que torna o semáforo uma ferramenta de coordenação, e não só de exclusão. Uma thread pode ficar bloqueada num sem_wait esperando um sinal, e uma outra thread, quando um evento acontece, faz sem_post pra liberá-la. Um faz o papel de “espere até isto ficar pronto”, o outro de “pronto, pode ir”. Não é uma thread protegendo seus próprios dados; é uma thread avisando a outra. O mutex não consegue fazer isso, porque o unlock vindo de quem não é o dono não é permitido.

O preço dessa flexibilidade é que semáforo é fácil de errar. Um sem_post a mais e o contador passa do teto que você imaginava, deixando entrar mais threads que o recurso suporta. Um sem_post a menos e uma vaga some pra sempre, até o programa travar por falta de vagas que existem mas ninguém devolveu. O mutex, ao amarrar liberar a quem adquiriu, elimina essa classe de erro inteira. Por isso, quando o que você quer é mesmo exclusão mútua simples, o mutex é mais seguro; o semáforo brilha quando o problema é contar recursos ou sinalizar entre threads.

Read-Write Lock

Imagine uma tabela de configuração que centenas de threads consultam o tempo todo e que muda de vez em quando. Proteger ela com um mutex funciona, mas paga um preço escondido. Duas threads que só querem ler a tabela não interferem uma na outra: ler não muda nada, e duas leituras simultâneas dão o mesmo resultado que duas leituras em sequência. Mesmo assim, o mutex serializa as duas, porque ele não faz distinção entre ler e escrever. Cada leitura espera a anterior terminar, e o paralelismo que existia de graça é jogado fora.

O read-write lock faz essa distinção. Ele tem dois modos de aquisição. Várias threads podem segurar o lock em modo de leitura ao mesmo tempo, sem se bloquearem. Mas o modo de escrita é exclusivo: enquanto uma thread escreve, nenhuma outra lê nem escreve. A regra é a do mundo real: quantos leitores você quiser, mas um escritor sozinho.

Medindo o ganho

O experimento tem oito threads batendo numa estrutura compartilhada, cada operação fazendo um trabalho de alguns microssegundos com o lock na mão. O que varia é a proporção de escritas. Comparamos o mesmo programa protegido por um mutex e por um rwlock:

== 0% escritas ==
mutex : 0.256s
rwlock: 0.030s

== 1% escritas ==
mutex : 0.257s
rwlock: 0.135s

== 10% escritas ==
mutex : 0.278s
rwlock: 0.576s

== 50% escritas ==
mutex : 0.282s
rwlock: 0.601s

Com leitura pura, o rwlock termina em um oitavo do tempo do mutex, quase o fator oito que você esperaria de oito threads que agora rodam em paralelo em vez de enfileiradas. Com 1% de escritas o ganho encolhe, mas ainda é quase o dobro. E aí a coisa vira: em 10% de escritas o rwlock já é mais lento que o mutex, e em 50% ele perde feio.

A virada tem duas causas. A óbvia é que toda escrita é exclusiva, então quanto mais escritas, mais o rwlock se comporta como o mutex de qualquer jeito, sem paralelismo nenhum para compensar. A menos óbvia é que o rwlock é mais caro por operação: para deixar vários leitores entrarem juntos, ele precisa contar quantos estão dentro, e esse contador é ele próprio um dado compartilhado que precisa ser atualizado de forma atômica a cada rdlock e unlock. Quando as leituras são curtas e frequentes, essa contabilidade extra come o ganho do paralelismo. O rwlock só vale a pena quando as leituras dominam de verdade e seguram o lock por tempo suficiente pra que rodar várias em paralelo compense o custo de contá-las.

A API da Pthreads

O tipo é pthread_rwlock_t, e a aquisição se desdobra em duas funções conforme a intenção:

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

pthread_rwlock_t lock = PTHREAD_RWLOCK_INITIALIZER;
int config = 42;

void *leitor(void *arg) {
    pthread_rwlock_rdlock(&lock);         // modo leitura: compartilhado
    printf("leitor viu config = %d\n", config);
    pthread_rwlock_unlock(&lock);
    return NULL;
}

void *escritor(void *arg) {
    pthread_rwlock_wrlock(&lock);         // modo escrita: exclusivo
    config = 99;
    printf("escritor mudou config\n");
    pthread_rwlock_unlock(&lock);
    return NULL;
}

int main(void) {
    pthread_t l[3], w;
    for (int i = 0; i < 3; i++) pthread_create(&l[i], NULL, leitor, NULL);
    pthread_create(&w, NULL, escritor, NULL);
    for (int i = 0; i < 3; i++) pthread_join(l[i], NULL);
    pthread_join(w, NULL);
    return 0;
}

O rdlock pega o lock em modo leitura e o wrlock em modo escrita; o mesmo pthread_rwlock_unlock libera os dois. Um único inicializador estático, PTHREAD_RWLOCK_INITIALIZER, serve pros dois modos, do mesmo jeito que o PTHREAD_MUTEX_INITIALIZER servia pro mutex.

O escritor que nunca escreve

Deixar vários leitores entrarem juntos abre uma armadilha. Se leitores chegam sem parar e o lock sempre tem pelo menos um deles dentro, um escritor esperando o modo exclusivo pode nunca conseguir a vez. Sempre tem um leitor lá dentro, sempre chega outro antes do último sair, e o escritor fica na fila indefinidamente. É a starvation de novo, agora não por barging do mutex, mas embutida na regra de quem pode entrar: a preferência por leitores mata o escritor de fome.

As implementações lidam com isso escolhendo uma política. Algumas dão preferência a escritores: assim que um escritor chega e pede o lock, novos leitores param de ser admitidos e ficam esperando ele passar, mesmo que o lock ainda esteja em modo leitura. Isso protege o escritor, ao custo de segurar leitores que poderiam ter entrado. A Pthreads não fixa a política no padrão e deixa em aberto pra implementação, o que significa que um código que depende de uma preferência específica não é portável. Antes de escolher um rwlock, vale saber qual das duas starvations você prefere arriscar, porque não dá pra fugir das duas ao mesmo tempo.

Problemas Clássicos

Há um punhado de problemas que aparecem em todo livro de concorrência, e não por tradição. Cada um isola uma dificuldade específica de coordenar threads, com um enredo simples o bastante pra caber numa frase e geral o bastante pra reaparecer, disfarçado, em código de verdade. Quem resolve o produtor-consumidor sabe conectar qualquer fila entre um lado que gera trabalho e outro que consome. Quem resolve os filósofos jantando sabe evitar deadlock quando várias threads disputam vários recursos.

Os quatro deste capítulo vêm da época em que a caixa de ferramentas era o semáforo, antes das primitivas mais confortáveis que veremos adiante, e é com semáforo e mutex que vamos resolver todos eles. Isso não é limitação: é justamente o que torna os problemas instrutivos, porque força a construir a coordenação na mão, vendo cada peça no lugar. As soluções que você vai escrever aqui são as mesmas que Dijkstra e seus contemporâneos escreveram, e várias delas são o que roda por baixo das abstrações prontas de hoje.

Producer-Consumer

Um lado gera itens de trabalho, o outro os processa, e entre eles há um buffer de tamanho fixo. Um servidor web coloca requisições numa fila e um pool de threads as atende. Um decodificador de vídeo enche um buffer de quadros que a placa de vídeo esvazia. O padrão é sempre o mesmo, e traz junto sempre os mesmos dois riscos: o produtor não pode escrever num buffer cheio, e o consumidor não pode ler de um buffer vazio. Se qualquer um dos dois ignorar isso, o programa corrompe dados ou lê lixo.

Contar quantas threads podem prosseguir é exatamente o que um semáforo faz, e aqui a gente precisa de dois. Um conta quantas posições livres o buffer ainda tem; o produtor faz P nele antes de escrever, e bloqueia se o buffer está cheio. O outro conta quantos itens prontos existem; o consumidor faz P nele antes de ler, e bloqueia se o buffer está vazio. Cada sem_post de um lado é o que eventualmente libera o outro.

Dois semáforos e um mutex

Se houvesse um só produtor e um só consumidor, os dois semáforos bastariam. Mas com vários produtores, dois deles podem passar pelo semáforo de posições livres ao mesmo tempo, e aí os dois vão escrever na mesma posição do buffer e avançar o mesmo índice, um por cima do outro. O semáforo garante que existe espaço; ele não garante que dois produtores não vão brigar pelo mesmo espaço. Essa briga pelo índice é uma seção crítica comum, e quem resolve seção crítica é o mutex.

Daí a divisão de trabalho que é o coração da solução: os semáforos coordenam (quantos podem entrar), o mutex protege (a manipulação dos índices). O Código 10-1 tem dois produtores e dois consumidores sobre um buffer de quatro posições:

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

#define TAM 4                 // tamanho do buffer
#define NP 2                  // produtores
#define NC 2                  // consumidores
#define POR_PROD 5            // itens que cada produtor gera
#define POR_CONS 5            // itens que cada consumidor consome

int buffer[TAM];
int in = 0, out = 0;

sem_t vazias;                 // posições livres
sem_t cheias;                 // itens prontos
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void *produtor(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < POR_PROD; i++) {
        int item = id * 100 + i;
        sem_wait(&vazias);            // espera uma posição livre
        pthread_mutex_lock(&mutex);   // protege os índices
        buffer[in] = item;
        in = (in + 1) % TAM;
        pthread_mutex_unlock(&mutex);
        sem_post(&cheias);            // agora tem mais um item pronto
    }
    return NULL;
}

void *consumidor(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < POR_CONS; i++) {
        sem_wait(&cheias);            // espera um item pronto
        pthread_mutex_lock(&mutex);
        int item = buffer[out];
        out = (out + 1) % TAM;
        pthread_mutex_unlock(&mutex);
        sem_post(&vazias);            // liberou uma posição
        printf("consumidor %d pegou %d\n", id, item);
    }
    return NULL;
}

int main(void) {
    sem_init(&vazias, 0, TAM);        // começa com TAM posições livres
    sem_init(&cheias, 0, 0);          // e zero itens prontos
    pthread_t p[NP], c[NC];
    int pid[NP], cid[NC];
    for (int i = 0; i < NP; i++) { pid[i]=i; pthread_create(&p[i],NULL,produtor,&pid[i]); }
    for (int i = 0; i < NC; i++) { cid[i]=i; pthread_create(&c[i],NULL,consumidor,&cid[i]); }
    for (int i = 0; i < NP; i++) pthread_join(p[i],NULL);
    for (int i = 0; i < NC; i++) pthread_join(c[i],NULL);
    printf("pronto\n");
    return 0;
}

$ cc main.c -o main -pthread
$ ./main
consumidor 0 pegou 0
consumidor 1 pegou 1
consumidor 1 pegou 3
consumidor 1 pegou 4
consumidor 1 pegou 100
consumidor 0 pegou 2
consumidor 1 pegou 101
consumidor 0 pegou 102
consumidor 0 pegou 103
consumidor 0 pegou 104
pronto

Os dez itens saem: os do produtor 0 (0 a 4) e os do produtor 1 (100 a 104), cada um consumido uma única vez, sem nenhum sumir nem aparecer duplicado. A ordem de quem pega o quê muda a cada execução, porque o escalonador decide quando cada thread roda, mas as duas invariantes se mantêm sempre: nunca um produtor escreve num buffer cheio, nunca um consumidor lê de um vazio.

Repare como as três primitivas se encaixam. Tira o semáforo vazias e um produtor rápido passa por cima de itens que ninguém consumiu ainda. Tira o cheias e um consumidor lê posições que nunca foram escritas. Tira o mutex e dois produtores corrompem o índice in. Cada uma cobre um buraco que as outras duas não cobrem, e é essa complementaridade que faz a solução funcionar.

A questão do término

Uma sutileza fácil de passar batido: como o programa sabe parar? Aqui, cada produtor gera um número fixo de itens e cada consumidor consome um número fixo, com as contas batendo (dois produtores de cinco, dois consumidores de cinco). Cada thread sabe exatamente quantas voltas dar e termina sozinha.

Em sistemas de verdade, quem produz e quem consome raramente sabe o total de antemão. O consumidor fica num loop infinito esperando trabalho que pode nunca mais vir, e desligar isso com elegância, sem deixar consumidor preso pra sempre num sem_wait, é um problema à parte, com soluções próprias como enviar um valor especial que sinaliza “acabou”. O núcleo da coordenação, os dois semáforos contra o buffer e o mutex sobre os índices, é o que não muda.

Readers-Writers

Você já usou um read-write lock pronto: vários leitores juntos, um escritor sozinho. Agora vamos construir um, com as peças que já temos na mão. O exercício vale porque mostra que o rwlock não é mágica de sistema operacional: é um mutex, um semáforo e um contador arranjados de um jeito esperto, e ver o arranjo explica de onde vem a starvation que o capítulo do rwlock mencionou.

A ideia central é assimétrica. Um escritor precisa de exclusão total, então basta um semáforo binário, escrita, que ele adquire antes de escrever e libera depois. Leitores são o caso interessante: muitos podem entrar juntos, mas coletivamente eles precisam manter os escritores de fora enquanto pelo menos um estiver lendo. A sacada é fazer o primeiro leitor a chegar trancar o semáforo de escrita, e o último a sair destrancar. Os leitores do meio nem tocam nesse semáforo, e é por isso que entram todos juntos.

Para saber quem é o primeiro e quem é o último, os leitores mantêm um contador, readcount. Incrementar e testar esse contador é uma seção crítica (dois leitores não podem, ambos, achar que são o primeiro), então ele mesmo é protegido por um mutex. O Código 10-2 monta tudo isso:

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

int readcount = 0;                                 // quantos leitores estão dentro
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;   // protege o readcount
sem_t escrita;                                     // 1 = livre pra escrever

int dado = 0;

void *leitor(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < 2; i++) {
        pthread_mutex_lock(&mtx);
        readcount++;
        if (readcount == 1) sem_wait(&escrita);    // o primeiro leitor tranca a escrita
        pthread_mutex_unlock(&mtx);

        printf("leitor %d leu %d\n", id, dado);    // vários podem estar aqui juntos
        usleep(50000);

        pthread_mutex_lock(&mtx);
        readcount--;
        if (readcount == 0) sem_post(&escrita);    // o último leitor destranca
        pthread_mutex_unlock(&mtx);
    }
    return NULL;
}

void *escritor(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < 2; i++) {
        sem_wait(&escrita);                        // exclusivo: espera nenhum leitor
        dado++;
        printf("escritor %d escreveu %d\n", id, dado);
        usleep(50000);
        sem_post(&escrita);
    }
    return NULL;
}

int main(void) {
    sem_init(&escrita, 0, 1);
    pthread_t l[3], w[2]; int lid[3]={0,1,2}, wid[2]={0,1};
    for (int i=0;i<3;i++) pthread_create(&l[i],NULL,leitor,&lid[i]);
    for (int i=0;i<2;i++) pthread_create(&w[i],NULL,escritor,&wid[i]);
    for (int i=0;i<3;i++) pthread_join(l[i],NULL);
    for (int i=0;i<2;i++) pthread_join(w[i],NULL);
    printf("fim\n");
    return 0;
}

$ cc main.c -o main -pthread
$ ./main
leitor 0 leu 0
leitor 1 leu 0
leitor 2 leu 0
leitor 2 leu 0
leitor 0 leu 0
leitor 1 leu 0
escritor 0 escreveu 1
escritor 0 escreveu 2
escritor 1 escreveu 3
escritor 1 escreveu 4
fim

Olhe a ordem da saída. Os seis “leu” aconteceram primeiro, todos vendo dado = 0, com vários leitores dentro ao mesmo tempo. Só depois que o último leitor saiu é que os escritores conseguiram entrar. Não foi coincidência: enquanto chegava leitor, o readcount nunca voltava a zero, o sem_post(&escrita) nunca era chamado, e os escritores ficavam presos no sem_wait. Com leitores chegando sem parar, um escritor poderia esperar pra sempre.

Essa é a starvation de escritor de que falamos ao ver a API do rwlock, agora visível na construção: a preferência por leitores não é uma decisão que alguém tomou por cima, é uma consequência direta de como as peças foram encaixadas. Esta é a solução original de Courtois, e ela favorece leitores por construção. Dar preferência a escritores, ou alternar de forma justa, exige mais contadores e mais semáforos, arranjados pra barrar novos leitores assim que um escritor manifesta interesse.¹

1. A solução com preferência a escritores usa um segundo semáforo pra segurar leitores na entrada quando há escritor esperando, mais um contador de escritores análogo ao readcount. É o mesmo tipo de raciocínio, só que aplicado aos dois lados. ↩

Dining Philosophers

Cinco filósofos sentam numa mesa redonda. Entre cada par de vizinhos há um garfo, cinco garfos no total, e no centro há um prato de espaguete que exige dois garfos pra comer. Cada filósofo alterna entre pensar e comer. Pra comer, ele pega o garfo da esquerda, depois o da direita, come, e devolve os dois. O problema, formulado por Dijkstra, é achar um jeito de todos comerem sem que ninguém fique preso.

A solução ingênua é escrever exatamente o enunciado: pega o garfo da esquerda, pega o da direita, come. Cada garfo é um mutex, porque um garfo só serve a um filósofo por vez.

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

#define N 5
pthread_mutex_t garfo[N];

void *filosofo(void *arg) {
    int id = *(int *)arg;
    int esq = id, dir = (id + 1) % N;
    for (;;) {
        pthread_mutex_lock(&garfo[esq]);      // pega o garfo da esquerda
        printf("filosofo %d pegou garfo esquerdo\n", id);
        usleep(100000);                        // hesita um instante
        pthread_mutex_lock(&garfo[dir]);      // quer o da direita
        printf("filosofo %d comeu\n", id);
        pthread_mutex_unlock(&garfo[dir]);
        pthread_mutex_unlock(&garfo[esq]);
    }
    return NULL;
}

int main(void) {
    setbuf(stdout, NULL);                      // mostra a saída antes do travamento
    pthread_t t[N]; int id[N];
    for (int i = 0; i < N; i++) pthread_mutex_init(&garfo[i], NULL);
    for (int i = 0; i < N; i++) { id[i]=i; pthread_create(&t[i],NULL,filosofo,&id[i]); }
    for (int i = 0; i < N; i++) pthread_join(t[i],NULL);
    return 0;
}

O usleep entre pegar um garfo e o outro cumpre o mesmo papel de sempre: dá tempo pra todos pegarem o primeiro garfo antes de qualquer um tentar o segundo. Rodando:

$ cc main.c -o main -pthread
$ ./main
filosofo 0 pegou garfo esquerdo
filosofo 1 pegou garfo esquerdo
filosofo 2 pegou garfo esquerdo
filosofo 4 pegou garfo esquerdo
filosofo 3 pegou garfo esquerdo
^C
$

Nenhum “comeu” aparece. Os cinco pegaram o garfo da esquerda, e agora cada um quer o garfo da direita, que é o garfo esquerdo do vizinho, que o vizinho está segurando e não vai soltar porque ele também está esperando o dele. É um deadlock, e das quatro condições que o produzem, a que salta aos olhos aqui é a espera circular: o filósofo 0 espera o 1, que espera o 2, e assim por diante até fechar o anel.

Duas saídas

A primeira saída já conhecemos do deadlock: quebrar a espera circular impondo uma ordem global na aquisição. Se, em vez de “cada um pega o seu garfo esquerdo primeiro”, a regra for “todos pegam primeiro o garfo de menor número”, o anel não se fecha. O filósofo 4, que pegaria o garfo 4 e depois o 0, passa a pegar o 0 e depois o 4, e essa única inversão basta pra romper o ciclo.

A segunda saída é mais interessante porque usa a ferramenta deste capítulo e ataca o problema por outro ângulo: em vez de mudar a ordem, limitar quantos tentam comer ao mesmo tempo. O deadlock só é possível porque os cinco tentam sentar pra comer de uma vez. Se no máximo quatro tentarem, sempre sobra um garfo pra alguém completar o par, comer, e liberar os seus. Basta um porteiro que admita no máximo quatro filósofos à mesa, e um porteiro que conta é um semáforo:

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

#define N 5
pthread_mutex_t garfo[N];
sem_t garcom;                          // admite no máximo N-1 à mesa
int refeicoes[N] = {0};

void *filosofo(void *arg) {
    int id = *(int *)arg;
    int esq = id, dir = (id + 1) % N;
    for (int r = 0; r < 3; r++) {      // cada um come três vezes
        sem_wait(&garcom);             // pede lugar ao garçom
        pthread_mutex_lock(&garfo[esq]);
        pthread_mutex_lock(&garfo[dir]);
        refeicoes[id]++;
        printf("filosofo %d comeu (%d)\n", id, refeicoes[id]);
        pthread_mutex_unlock(&garfo[dir]);
        pthread_mutex_unlock(&garfo[esq]);
        sem_post(&garcom);             // levanta da mesa
    }
    return NULL;
}

int main(void) {
    setbuf(stdout, NULL);
    sem_init(&garcom, 0, N - 1);       // no máximo 4 sentados de uma vez
    pthread_t t[N]; int id[N];
    for (int i = 0; i < N; i++) pthread_mutex_init(&garfo[i], NULL);
    for (int i = 0; i < N; i++) { id[i]=i; pthread_create(&t[i],NULL,filosofo,&id[i]); }
    for (int i = 0; i < N; i++) pthread_join(t[i],NULL);
    printf("todos comeram\n");
    return 0;
}

$ cc main.c -o main -pthread
$ ./main
filosofo 0 comeu (1)
filosofo 0 comeu (2)
filosofo 0 comeu (3)
filosofo 1 comeu (1)
filosofo 1 comeu (2)
...
todos comeram

Cada filósofo come as três vezes e o programa termina. Nesta execução o filósofo 0 pegou os dois garfos e emendou as três refeições antes de soltar, porque o loop é rápido e ele estava com os garfos quentes na mão; noutra execução a ordem sai diferente. O que não muda é o essencial: o garçom nunca deixa os cinco disputarem ao mesmo tempo, então nunca se forma o anel de espera. Comparado com a ordem global, o garçom tem a vantagem de ser local: você não precisa reescrever a regra de aquisição de cada filósofo, só interpor uma permissão na entrada. É a mesma ideia do estacionamento com vagas, aplicada a uma disputa que sem o limite viraria deadlock.

Sleeping Barber

Uma barbearia tem um barbeiro, uma cadeira de corte e algumas cadeiras de espera. Sem cliente, o barbeiro dorme. Quando um cliente chega, se o barbeiro está dormindo, ele o acorda e é atendido; se o barbeiro está ocupado, o cliente senta pra esperar, desde que haja cadeira livre; se não há, ele vai embora. O desafio é que o barbeiro dormir e ser acordado é precisamente uma comunicação entre threads: uma dorme, outra a desperta.

Esse é o uso do semáforo que separa ele de um mutex. Lá no capítulo de semáforos, o ponto era que semáforo não tem dono: qualquer thread pode fazer sem_post, não só quem fez sem_wait. Aqui isso deixa de ser curiosidade e vira o mecanismo central. O barbeiro bloqueia num semáforo clientes, que começa em zero, e é outra thread, o cliente, que faz sem_post nele. O barbeiro dorme; o cliente o acorda. Um mutex não faz isso, porque o barbeiro não poderia liberar um lock que o cliente adquiriu.

O barbeiro, os clientes e dois semáforos

A conversa acontece em dois sentidos, então há dois semáforos. clientes é o cliente avisando o barbeiro “cheguei”; barbeiro é o barbeiro avisando o cliente “pode vir”. Além deles, um mutex protege a contagem de quem está esperando, porque decidir se há cadeira livre é um teste-e-ação sobre um contador compartilhado, e dois clientes chegando juntos não podem, ambos, achar que pegaram a última cadeira.

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

#define CADEIRAS 3

sem_t clientes;                // clientes esperando; o barbeiro dorme aqui
sem_t barbeiro;                // o barbeiro sinaliza que vai atender
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
int esperando = 0;             // clientes na sala de espera
int fechado = 0;               // a barbearia fechou

void *o_barbeiro(void *arg) {
    for (;;) {
        sem_wait(&clientes);                       // dorme se não tem ninguém
        pthread_mutex_lock(&mtx);
        if (fechado && esperando == 0) { pthread_mutex_unlock(&mtx); break; }
        esperando--;
        pthread_mutex_unlock(&mtx);
        sem_post(&barbeiro);                       // chama o próximo
        printf("barbeiro cortando cabelo\n");
        usleep(30000);
    }
    printf("barbeiro foi pra casa\n");
    return NULL;
}

void *cliente(void *arg) {
    int id = *(int *)arg;
    pthread_mutex_lock(&mtx);
    if (esperando < CADEIRAS) {
        esperando++;
        printf("cliente %d senta pra esperar (%d na fila)\n", id, esperando);
        pthread_mutex_unlock(&mtx);
        sem_post(&clientes);                       // acorda o barbeiro
        sem_wait(&barbeiro);                       // espera ser chamado
    } else {
        printf("cliente %d foi embora, sala cheia\n", id);
        pthread_mutex_unlock(&mtx);
    }
    return NULL;
}

int main(void) {
    setbuf(stdout, NULL);
    sem_init(&clientes, 0, 0);
    sem_init(&barbeiro, 0, 0);
    pthread_t b, c[6]; int id[6];
    pthread_create(&b, NULL, o_barbeiro, NULL);
    for (int i = 0; i < 6; i++) { id[i]=i; pthread_create(&c[i],NULL,cliente,&id[i]); usleep(10000); }
    for (int i = 0; i < 6; i++) pthread_join(c[i],NULL);
    pthread_mutex_lock(&mtx); fechado = 1; pthread_mutex_unlock(&mtx);
    sem_post(&clientes);                           // acorda o barbeiro pra ele fechar
    pthread_join(b, NULL);
    return 0;
}

$ cc main.c -o main -pthread
$ ./main
cliente 0 senta pra esperar (1 na fila)
barbeiro cortando cabelo
cliente 1 senta pra esperar (1 na fila)
cliente 2 senta pra esperar (2 na fila)
barbeiro cortando cabelo
cliente 3 senta pra esperar (2 na fila)
cliente 4 senta pra esperar (3 na fila)
cliente 5 foi embora, sala cheia
barbeiro cortando cabelo
barbeiro cortando cabelo
barbeiro cortando cabelo
barbeiro foi pra casa

O cliente 5 chega com a sala já cheia e vai embora sem esperar, exatamente o comportamento que o enunciado pede. Os outros cinco são atendidos, cada um acordando o barbeiro com um sem_post(&clientes) e esperando a vez com um sem_wait(&barbeiro). A dança de dormir e acordar, que num mutex seria impossível, aqui é só um semáforo que uma thread espera e outra libera.

O fechado no fim resolve o mesmo problema de término do produtor-consumidor por outro caminho: sem ele, o barbeiro ficaria pra sempre dormindo no sem_wait, esperando um cliente que não vem mais. A main, depois que todos os clientes foram atendidos, marca a barbearia como fechada e faz um último sem_post para acordar o barbeiro uma vez mais, só pra ele ver que o expediente acabou e ir pra casa.

História da Concorrência e Paralelismo

Eu considero que, para qualquer assunto que você deseja entender melhor, é essencial conhecer o contexto e a história que o cercam. Com os temas desse livro — concorrência e paralelismo — não seria diferente.

Dentre os destaques desse capítulo, veremos:

• Como as descobertas sobre concorrência surgiram durante os estudos sobre sistemas operacionais
• Como durante décadas os programadores se beneficiaram do “almoço grátis” proporcionado pelo aumento da velocidade de clock das CPUs, e como uma limitação física fundamental acabou com isso.
• Como a indústria reagiu ao fim do almoço grátis, construindo arquiteturas multi-core

Dijkstra, o sistema operacional THE e o surgimento dos semáforos

Tony Hoare e o surgimento da concorrência por troca de mensagens

A Escala de Dennard