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 primeiro a começar, mas só termina após outras duas terem iniciado.
Paralelismo é uma propridade 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õem irá executar na CPU por um certo intervalo de tempo, para em seguida ser trocado por outra (Um processo chamado de escalonamento). Os sistemas operaciionais 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 items
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”1. 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 se que elas serão necessariamente executadas ou finalizadas sequencialmente2.
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.
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 ínicio 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:
- 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.
- A consulta ao banco de dados leva 8 ms.
- 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.
- Em \( t_2 = 8\ \text{ms} \), a consulta ao banco de \( R_1 \) é concluída e o servidor emite a resposta.
- 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:
- 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.
- 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.
- 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.
- Em \( t_2 = 5\ \text{ms} \), a tarefa para \( R_2 \) finaliza e o servidor envia uma resposta.
- 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 image 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 usá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 a 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:
| # | Pos 1 | Pos 2 | Pos 3 | Pos 4 | Pos 5 | Pos 6 |
|---|---|---|---|---|---|---|
| 1 | A0 | A1 | A2 | B0 | B1 | B2 |
| 2 | A0 | A1 | B0 | A2 | B1 | B2 |
| 3 | A0 | A1 | B0 | B1 | A2 | B2 |
| 4 | A0 | A1 | B0 | B1 | B2 | A2 |
| 5 | A0 | B0 | A1 | A2 | B1 | B2 |
| 6 | A0 | B0 | A1 | B1 | A2 | B2 |
| 7 | A0 | B0 | A1 | B1 | B2 | A2 |
| 8 | A0 | B0 | B1 | A1 | A2 | B2 |
| 9 | A0 | B0 | B1 | A1 | B2 | A2 |
| 10 | A0 | B0 | B1 | B2 | A1 | A2 |
| 11 | B0 | A0 | A1 | A2 | B1 | B2 |
| 12 | B0 | A0 | A1 | B1 | A2 | B2 |
| 13 | B0 | A0 | A1 | B1 | B2 | A2 |
| 14 | B0 | A0 | B1 | A1 | A2 | B2 |
| 15 | B0 | A0 | B1 | A1 | B2 | A2 |
| 16 | B0 | A0 | B1 | B2 | A1 | A2 |
| 17 | B0 | B1 | A0 | A1 | A2 | B2 |
| 18 | B0 | B1 | A0 | A1 | B2 | A2 |
| 19 | B0 | B1 | A0 | B2 | A1 | A2 |
| 20 | B0 | B1 | B2 | A0 | A1 | A2 |
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:
| Passo | Instrução | rax (A) | rax (B) | x |
|---|---|---|---|---|
| 1 | A0 | 0 | — | 0 |
| 2 | A1 | 1 | — | 0 |
| 3 | A2 | 1 | — | 1 |
| 4 | B0 | — | 1 | 1 |
| 5 | B1 | — | 2 | 1 |
| 6 | B2 | — | 2 | 2 ✓ |
Uma outra intercalação possível, mas que produz um resultado diferente do
esperado, é A0, B0, A1, B1, A2, B2:
| Passo | Instrução | rax (A) | rax (B) | x |
|---|---|---|---|---|
| 1 | A0 | 0 | — | 0 |
| 2 | B0 | — | 0 | 0 |
| 3 | A1 | 1 | — | 0 |
| 4 | B1 | — | 1 | 0 |
| 5 | A2 | 1 | — | 1 |
| 6 | B2 | — | 1 | 1 ✗ |
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ível, 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 \).
| \( m \) | \( n \) | Intercalações |
|---|---|---|
| 2 | 3 | 20 |
| 3 | 3 | 1.680 |
| 4 | 3 | 369.600 |
| 2 | 5 | 252 |
| 3 | 5 | 756.756 |
| 2 | 10 | 184.756 |
| 3 | 10 | \( \approx 5.6 \times 10^{12} \) |
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 desenvolvidas outras 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.3
- 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.
Conclusão
Devido a limitações físicas descobertas a mais de 20 anos4, 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.
-
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. ↩
-
Veremos mais na frente como pode ser feito o escalonamento dessas tarefas. ↩
-
No Capítulo 2 veremos como a Lei de Ahmdal formaliza isso. ↩
-
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. ↩