# A fila das threads

Em um ambiente multithreading diversas threads disputam "a tapas" a atenção do processador (CPU). Certo? Podemos dizer que, em um ambiente com muito processamento a realizar, de certa forma é isso que acontece. São threads e mais threads rodando um pedacinho de código cada vez que passam pelo processador.

Um ambiente complexo como um sistema operacional executando dezenas (às vezes centenas) de programas é repleto de pequenos detalhes que podem fazer o iniciante logo desanimar quando tentar depurar um programa com mais de uma thread. De fato, eu já percebi que muitos não vão saber nem como começar a pensar sobre o problema.

Uma forma de visualizar o cenário multithread começa na fila das threads. Elas estão indo em direção ao guichê das CPUs onde vão conseguir tempo de processamento para rodar seu código. Depois que elas esgotam seu tempo elas se dirigem para o final da fila esperando por mais tempo para executar mais código.

Para simplificar este cenário vamos imaginar duas threads iniciando com o mesmo código. Esse código incrementa um contador global até ele chegar a dez, quando a função retorna e as threads terminam.

   int count = 0;
   increment() {
     while( count < 10 ) {
       count++;
       print(tid, count);
     }
   }
   main() {
     thread t1(increment);
     thread t2(increment);
   }

O tid no pseudo-código acima é sinônimo para Thread ID, o identificador único de uma thread, que costuma ser um número. Para simplificar vamos dar ao id os apelidos de t1 e t2. Esta é uma possível saída do código acima, dependendo de quantos processadores e cores possui a máquina:

   t1 1
   t1 2
   t1 3
   t1 4
   t1 5
   t1 6
   t1 7
   t1 8
   t1 9
   t1 10

Pelo jeito a primeira thread não deu chance para a outra executar. Isso acontece por causa do pequeno espaço de tempo que é necessário para realizar a tarefa de incrementar uma variável. É tão pequena a tarefa que nem foi suficiente para a primeira thread ficar sem tempo e a CPU mandar ela para o fim da fila. Por isso a segunda thread nunca chegou a incrementar o contador.

Quando uma thread quer realizar algum processamento, ela precisa entrar na fila das threads ativas, que aguardam pela CPU que irá atendê-las. Nessa fila ela pega uma senha e aguarda a sua vez. Só que cada vez que uma thread é atendida ela ganha um tempo limitado de atendimento, que na arquitetura do sistema operacional é chamado de quantum ou time slice. Se o quantum de uma thread estoura, ou a thread não tem mais nada pra fazer, ela sai do guichê de atendimento e volta a ficar inativa, ou volta para o final da fila, aguardando por mais processamento.

Uma thread pode opcionalmente ir para o final da fila por conta própria. Para isso, basta que ela chame uma função do sistema operacional pedindo para dormir. Por isso geralmente essa função é chamada de sleep na API do sistema operacional. Nessa função costuma haver um parâmetro de quanto tempo a thread deseja dormir. Se for maior que zero ela vai para a fila de threads dormindo até passar esse tempo, para depois se dirigir à fila de threads ativas, aguardar para ser processada. Se o tempo passado for exatamente zero ela vai direto para essa última fila, mas ficará sem executar do mesmo jeito, pois esta é a fila de quem está aguardando pela sua próxima fatia de tempo de processamento.

Se chamarmos a função para dormir no código da thread antes de voltar a incrementar o contador é possível que a segunda thread tenha chance de executar.

   increment() {
     while( count < 10 ) {
       count++;
       print(tid, count);
       sleep();
     }
   }

Agora cada thread, depois de incrementar uma vez o contador, volta para o final da fila. Dessa forma vemos uma thread de cada vez incrementando o mesmo contador.

   t1 1
   t2 2
   t1 2
   t2 3
   t1 4
   t2 4
   t2 6
   t2 7
   t1 5
   t1 8
   t2 8
   t2 9
   t2 10

Peraí, o mesmo contador? Isso pode gerar problemas. Se duas threads tentarem incrementar o mesmo contador ao mesmo tempo, quem garante que elas não irão incrementar o mesmo valor? Bom, se você é bom observador já deve ter reparado que na execução acima ocorreu exatamente isso, com mais de uma thread incrementando o contador com o mesmo valor.

Para forçar isso acontecer mais rápido e de maneira mais gritante podemos fazer a thread ir para o final da fila antes de incrementarmos e após pegarmos o valor atual do contador. Note que nesses testes a saída muda completamente dependendo de quantos processadores sua máquina tem. O resultado às vezes pode ser bem bizarro do que o visto nesse artigo. 1

   increment() {
     while( count < 10 ) {
       int c = count;
       sleep();
       c++;
       print(tid, c);
       count = c;
     }
   }

O código acima pode gerar a seguinte saída:

   t1 1
   t2 1
   t1 2
   t2 2
   t1 3
   t2 3
   t1 4
   t2 4
   t1 5
   t2 5
   t2 6
   t1 6
   t2 7
   t1 7
   t1 8
   t2 8
   t2 9
   t1 9
   t2 10
   t1 10

Explicando mais uma vez com mais detalhes: quando uma thread guarda o valor do contador na variável local e volta para o final da fila, ela deixa de armazenar o contador atualizado para apenas **depois** que todas as outras threads passarem na sua frente. Só que as outras threads também pegam o mesmo valor do contador, pois ele ainda não foi alterado. Quando chega a hora da segunda passada no guichê das CPUs, todas as threads incrementaram o mesmo valor do contador. Se houvesse apenas um processador em uma máquina o fluxo de execução do ponto de vista do processamento único para duas threads ficaria mais ou menos o seguinte (zzz é quando uma thread dorme):

   t1 c = count (0)
   t1 zzz
   t2 c = count (0)
   t2 zzz
   t1 c++ (1)
   t2 c++ (1)
   t1 print c (1)
   t2 print c (1)
   t1 count = c (1)
   t2 count = c (1)
   t1 c = count (1)
   t1 zzz
   t2 c = count (1)
   t2 zzz
   ...

O exemplo acima forçou essa situação, mas é preciso lembrar que isso pode acontecer mesmo sem a thread dormir. É possível que o tempo da thread se esgote e ela pare de ser atendida justo na hora que iria salvar a variável c no contador global. Dessa forma, ela vai para o final da fila à força e, quando voltar a ser atendida, uma outra thread já terá lido o valor anterior para ela própria incrementar.

O que gostaríamos que acontecesse para corrigir o problema é forçar a segunda thread a esperar antes que a primeira termine todo o processo de incrementar e salvar no contador global, o que resolveria o nosso problema (o wait no exemplo abaixo é uma thread aguardando e não fazendo nada):

   t1 c = count (0)
   t1 zzz
   t2 wait
   t1 c++ (1)
   t2 wait
   t1 print c (1)
   t2 wait
   t1 count = c (1)
   t2 wait
   t1 ready
   t2 c = count (1)
   t1 wait
   t2 c++ (2)
   t1 wait
   t2 print c (2)
   t1 wait
   t2 count = c (2)
   t2 ready
   t1 c = count (2)
   t2 wait
   ...

Esse wait do fluxo, ou seja, deixar a próxima thread aguardando a que chegou primeiro incrementar, pode ser obtido se utilizarmos um mecanismo de acesso exclusivo fornecido pelo sistema operacional. Uma outra história para contar, que chamarei de "A sala da fila das threads".

1 Eu mesmo em meus testes não pude usar sleep passando zero como o tempo para dormir porque meu número de processadores não permite que eu faça esse experimento, já que sempre vão existir processadores dispostos a reprocessar a thread que acabou de ir para o final de sua fila.

# Deixe o programador programar

Seis meses se passaram desde que defini o cronograma para um projeto importante (mas não urgente) que deveria ser entregue cinco meses atrás. O tempo em dias que estimei na época não havia mudado nada, mas uma série de desventuras (tarefas brotando do chão e umas férias bem merecidas) fizeram com que quase nenhuma linha de código tivesse sido produzida para aquele projeto. No entanto, tenho a consciência tranquila, já que estou em uma de minhas fases mais produtivas e inovadoras.

Então eis que surge na porta do templo sagrado (a sala de desenvolvimento) um dos mortais que costuma acreditar que "dirige" seus funcionários. Vira-se para mim e "define" que esse projeto não poderá passar desse mês. E todas aquelas tarefas urgentes que estavam furando a fila de prioridades, como a última da semana passada, devem ser postergadas. É lógico que nada disso foi surpresa, visto que outros discursos desse tipo e outras tarefas urgentes já haviam aparecido no decorrer desses seis meses; mas, enfim, esse foi o primeiro deadline oficialmente definido.

Por isso mesmo, com uma preocupação constante em minha cabeça, decido desestressar um pouco e ter um almoço bem alargado (quatro horas) em um outro bairro, em outro ambiente, com uns velhos amigos para jogar alguma conversa fora. Nada como a vida fluindo devagar para fazer esquecer detalhes menos essenciais, como trabalho e estresse no trabalho. Sou obrigado nessa hora a parafrasear o sócio mais espirituoso de nossa empresa, que coincidentemente estava presente no almoço: "mas, afinal de contas, quem foi que definiu que a vida tem que ter trabalho e estresse?".

Eu assino embaixo.

Porém, terminado o almoço, volto a pensar em como resolverei o impasse do cronograma do tal projeto superimportante, quando, ao passar pela entrada do metrô, colocam na minha mão justamente um desses panfletos de rua com mensagens subliminares. E nele estava, acreditem, leitores, a solução para todos os meus problemas!

Se você está com algum PROBLEMA DE DIFÍCIL SOLUÇÃO e precisa de AJUDA URGENTE, peça esta ajuda a Santo Expedito que é o Santo dos Negócios que precisam de Pronta Solução e cuja invocação nunca é tardia. (Abaixo segue a oração ao Santo).

É lógico que toda essa história fantasiosa pode ser pura ficção com um pingo sequer de realidade, e no fundo almocei foi mesmo é com meus amigos imaginários. No entanto, é capaz que esse não seja um cenário incomum em muitas empresas de tecnologia por aí afora, que insistem em fazer duas coisas que, aliadas, podem gerar qualquer coisa, menos um projeto bem feito e testado:

• Pedir que seus funcionários elaborem um cronograma de um projeto complexo (um mês ou mais de trabalho).
• Pedir que seus funcionários espremam o tempo definido para o projeto de alguma forma mágica.

O problema é que, na área de informática, apesar de ciência esotérica e cheia de mistérios, não existem santos, não existem milagres e não existe mágica que gere um código de qualidade se não for despendido para ele uma soma considerável de tempo e trabalho. E não estou falando de nenhum luxo. É o tempo justo, mesmo.

Por isso que há eras meu amigo Strauss e o conhecido Joel falam sobre as necessidades básicas de um programador e criticam o resto. As necessidades básicas, na minha opinião, se resumem em três regras de ouro:

1. Dê condições para o programador pensar

2. Dê condições para o programador trabalhar

3. Dê condições para o programador programar

Fora isso, o resto é perfumaria, perda de tempo e enchimento de saco. Os bons programadores não querem ser gerenciados: querem programar. Só isso. Deixe-os com seus problemas e vá tomar conta de algo que não atrapalhe suas vidas. Já estará fazendo um imenso avanço na produtividade de sua empresa.

# A sala da fila das threads

Quando falei sobre a fila das threads, e como cada thread espera pacientemente em uma fila até chegar sua vez de ser atendida no guichê das CPUs, também vimos como é fácil fazer caquinhas em um programa que roda paralelamente duas threads ou mais.

Também falei que iríamos resolver esse problema, afinal de contas, temos que salvar todos aqueles programas que usam dezenas de threads trabalhando ao mesmo tempo para contar números de um até dez.

A boa notícia é que o salvamento é mais simples do que parece: coloque todas as suas threads em uma sala trancada e deixe apenas uma chave. As threads terão que brigar para sair da sala e, depois que a vencedora sair, as outras terão que ficar esperando ela voltar.

Confuso? Se estiver, ainda bem. Isso quer dizer que estamos novamente em um daqueles artigos com "pseudo-parábolas", a maneira mais ilustrada de explicar as coisas.

Os SOs modernos possuem inúmeras maneiras de controlar e monitorar o acesso a recursos do sistema. Neste breve artigo irei falar apenas de um: o critical section, ou, em tradução livre, "seção crítica". O "seção" desse nome diz respeito a uma seção do programa, ou seja, um pedaço de código mesmo. Um pedaço de código crítico.

Resumidamente, um critical section é um recurso que apenas uma thread por vez pode obter. Para que outra thread tenha acesso ao mesmo critical section, a primeira thread que o obteve deve soltá-lo. Enquanto ela não solta, as outras threads ficam paradas, esperando pela chave, na sala trancada.

Do ponto de vista do programador o critical secton é apenas uma estrutura que é usada na chamada de quatro funções básicas: para inicializar o recurso, para entrar na seção crítica, para sair da seção crítica e para liberar o recurso, quando aquele critical section não será usado mais.

Falando assim, parece simples. Bom, na verdade é simples, mesmo. Tudo que você precisa para corrigir o programa do artigo anterior é criar um critical section e fazer com que as threads obtenham-no antes de mexer com o contador compartilhado.

   #include <windows.h>
   #include <stdio.h>
   
   #define MAX_COUNTER 10
   
   int g_counter = 0;
   CRITICAL_SECTION g_cs;
   
   DWORD WINAPI Increment()
   {
     DWORD tid 
       = GetCurrentThreadId();
   
     while( g_counter < MAX_COUNTER )
     {
       // esse é o começo de nossa 
       // seção crítica
       // só uma thread entra
       // por vez por aqui
       EnterCriticalSection(&g_cs);
   
       int temp = g_counter;
       temp = temp + 1;
       Sleep(0); // indo para 
                 // o final da fila
       g_counter = temp;
   
       // esse é o fim de nossa 
       // seção crítica
       // a partir dessa chamada 
       // outra thread pode 
       // entrar pelo começo
       LeaveCriticalSection(&g_cs);
   
       printf("Counter: %d"
         "\t\tThread: %d\n", 
         temp, 
         tid);
     }
   
     return 0;
   }
   
   int main()
   {
     HANDLE threads[3];
     DWORD tids[3];
   
     // precisamos inicializar 
     // nosso recurso de 
     // seção crítica
     InitializeCriticalSection(&g_cs);
   
     for( int i = 0; i < 3; ++i )
     {
       threads[i] 
         = CreateThread(NULL, 
         0, 
         IncrementGlobalCounter, 
         0, 
         0, 
         &tids[i]);
       printf("Thread %i: %d\n", 
         i, 
         tids[i]);
     }
   
     // aguarda as threads
     WaitForMultipleObjects(3, 
       threads, 
       TRUE, 
       INFINITE);
   
     // agora precisamos liberar o 
     // recurso de seção crítica
     DeleteCriticalSection(&g_cs);
   }

Para finalizar, algo para pensar: se uma thread só consegue um critical section depois que outra thread soltá-lo, o que acontece se essa outra thread estiver esperando por outro critical section que uma thread que aguarda estiver segurando?

Acabamos de ilustrar um procedimento muito simples para cagar completamente no código e gerar um travamento que pode demorar de horas a semanas para ser detectado e resolvido. É o conhecido deadlock. Se você não entendeu ainda, imagine que, para voltar à sala das threads, a primeira thread que saiu precisa de duas chaves; só que ela só pegou a primeira, e a segunda está dentro da sala. Para pegar a segunda chave, ela precisa entrar na sala, só que a sala está trancada pelas duas chaves!

Deadlocks são sempre indesejáveis, e é por isso que existem diversas técnicas para tentar evitá-los. A mais conhecida é sempre obter os critical sections na mesma ordem. Dessa forma a obtenção de recursos é hierarquizada, o que impede que dois CSs estejam no mesmo nível de obtenção, evitando que duas threads distintas os obtenham.

Espero que tenha ficado claro nossa breve explanação de como podemos controlar programas multithreading. Espero, pois a próxima tarefa é entender outros conceitos mais abstratos e virtuais, como funções virtuais e classes abstratas.