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. ↩