Concorrência ou paralelismo: Threads, Processes, Fibers e Actors

Quanto mais processamento é necessário para resolver um problema, mais nos deparamos com projetos que envolvem questões de paralelismo, concorrência e distribuição de tarefas. Quais seriam as opções que existem e quais as características de cada uma delas?

Como já sabemos, o problema em escrever código para ser rodado paralelamente é grande quando temos acesso a dados compartilhados (shared memory) e existe uma ou mais escritas ocorrendo no mesmo dado.

A abordagem dos monitores do Java (wait/notify) e das pthreads do C estão ligadas a objetos que sinalizam quando podemos e quando não devemos escrever nessa memória compartilhada e, apesar de extremamente poderosa, vem se mostrando difícil de ser trabalhada e mantida pelos desenvolvedores. Tudo isto está conectado com a questão de concorrência preemptiva, onde um escalonador agenda e executa as threads/processos, inclusive em mais de um processador simultaneamente.

Existem duas outras alternativas que ganham força hoje em dia: os atores e processos de linguagens como Erlang e Scala, e as fibers do ruby 1.9.

Em linguagens como Erlang, onde as “variavéis” são imutáveis, não existem efeitos colaterais ao se executar uma função, portanto podemos dizer que a “memória compartilhada” não sofre dos males das outras linguagens, já que não há estado que possa ser alterado. Muitos dizem que o grande problema das linguagens atuais é justo o estado.

Qual a grande vantagem da imutabilidade fazer parte de uma lingaugem? Duas invocações poderiamm ser paralelizadas pelo interpretador/compilador, como o exemplo de pseudo código Java abaixo mostra:

String geraCorpo(Movimentacao[] movimentacoes) {
  String conteudo = "";
  for (Movimentacao m : movimentacoes) {
    conteudo += m.geraConteudo();
  }
  return conteudo;
}

String geraRodape(Informacao[] informacoes) {
  String rodape = "";
  for(Informacao info : informacoes) {
    rodape += info.geraConteudo();
  }
  return rodape;
}

String processaRelatorio (Movimentacao[] movimentacoes, 
         Informacao[] informacoes ) {
  return geraCorpo(movimentacoes) + geraRodape(informacoes)
}

Repare que quando invocarmos o processaRelatorio as duas outras funções seriam executadas sequencialmente, mas um compilador/interpretador inteligente poderia executar as duas invocações em paralelo e concatenar o resultados assim que ambos estiverem disponíveis. Ele poderia ir mais além, invocando partes de cada laço em paralelo em processadores diferentes. Isso se tivessemos a garantia de que não haveria efeitos colaterais ao invocarmos cada uma dessas funções, garantia a qual não se da para fazer com o Java.

Funções que não causam efeitos colaterais permitem otimizações impressionantes por parte do interpretador/compilador e são uma ótima alternativa para fazer uso de todos os cores que temos disponibilizados (número que só cresce) evitando o desperdício.

Por outro lado, existem partes do sistema que podem ser manualmente agendados para executarem concorrentemente e – as vezes – até mesmo em paralelo (sendo que as duas coisas são diferentes).

Em sites de verificação de rotas de vôo, diversas requisições para diferentes sites podem ser executadas simultaneamente com uma tarefa extra que que concatena todos os resultados. Para que essa tarefa final receba as respostas, precisamos trocar mensagens entre aqueles que processam as diversas requisições e a tarefa que concatena as informações. Alguém responsável por pegar informação de um site seria aquele que recebe o identificador do site que será pesquisado (por exemplo tam, gol etc), os critérios de pesquisa, e quem é responsável pela tarefa final, de concatenar os resultados.

Dada as 3 informações, esse alguém executa uma requisição que é blocante, isto é, segura a sua thread até obter a resposta, executa transformações (parseia) a mesma, e termina notificando o responsável da finalização do processo, como o pseudo-código abaixo:

class Agente {
  def recebe(site, pesquisa, callback) {
    resposta = http.request(site + "?search_for=" + pesquisa)
    resultado = parseia(resposta)
    callback.recebe (resultado)
  }
}

E então alguém responsável por concatenar os resultados:

class TarefaFinal {
  final = []
  def recebe(resultado_parcial) {
    final.add resultado_parcial
  }
  def aguarda_ate_o_fim {
    // aguarda ate o fim de todos os parciais
    // e entao retorna o resultado total
  }
}

A tarefa mãe seria quem dispara diversos agentes que farão as pesquisas e o agente final, que colherá os resultados, ainda com pseudo-código:

class Pesquisador {
  def busca(opcoes) {
    concatenador = new TarefaFinal
    sites = {'www.tam.com.br', 'www.voegol.com.br',
                 'www.aerolinhascaelum.com.br'}
    for site in sites {
      new Agente().envia (site, opcoes, concatenador)
    }
    return concatenador.aguarda_ate_o_fim
  }
}

Em Java, por exemplo, utilizariamos uma thread para cada agente, para que cada requisição blocante não impedisse a execução das outras em paralelo. Com isso, podemos utilizar todos os processadores de uma máquina, mas o peso de gerenciar muitas threads em Java é algo que queremos evitar.

Outra solução, ainda em Java, é utilizar a api de NIO, permitindo executar tarefas de entrada e saída sem que a thread atual aguarde o resultado final. Por um lado essa alternativa aumentaria a possibilidade de atendermos muito mais requisições, porém há um custo aí de ficar perguntando se o resultado “já está pronto”. É um trade-off entre performance e escalabilidade. Essa abordagem pode ser feita de maneira um pouco mais elegante e transparente através de bibliotecas de dataflow concurrency.

A solução que algumas linguagens apresentam é chamada de processos. Esses processos serão executados concorrentemente, e, como o código é escrito visando minimizar efeitos colaterais, em grande parte ele poderá ser executado em paralelo. Esses processos são mais leves pois não implicam em um overhead de informações devido a troca do estado de memória e de pilha de execução quanto a implementação de threads em Java.

Ainda mais impressionante é a capacidade de executar cada um desses processos em máquinas diferentes da atual. Se o código do agente é facilmente serializável, ou que permita um rápido bootstrap em diversas máquinas remotas, fica muito barato rodar esses processos em diversas máquinas, inclusive efetuando concatenações parciais, até obter o resultado final, se aproximando das idéias do Map Reduce, descrito pelo google em 2004.

Por fim, existe a opção de co-rotinas que voltam a ser abordadas, nesse caso no mundo Ruby, através de Fibers.

O uso de Fibers permite escrever um código onde N processos mantem a comunicação entre si, dizendo uns aos outros quando é o momento de deixar de executar para dar espaço para execução do outro processo. Muitos se lembrarão do método Thread.yield() de Java, que tem um comportamento definido parecido com o mencionado. Mas ele não garante que a thread atual para e deixa outro processo rodar.

Por outro lado, fibers garantem que aquele processo pare momentaneamente para deixar aquele que o invocou continuar sua execução. A grande vantagem está em poder separar, com isso, o código que controla diversos processos (fibers) e o código que executa cada processamento. A desvantagem está em que os processos estão rodando concorrentemente, não em paralelo.

Hoje em dia, outro assunto que está sendo muito discutido é a questão da memória transacional. Uma maneira que, resumidamente, permite criar transações em cima de suas variáveis de memória para que, em casos onde imutabilidade de dados compartilhados não é possível, haja um controle automático.

Mas essa abordagem apresenta certas dificuldades e detalhes importantes de serem estudados, como as dificuldades de se fazer operações de IO durante uma transação dessas – o problema de “como efetuar o rollback do lançamento de um foguete?”. Quem implenta uma possível solução para isso é o haskell, através dos monads.

Só enxergaremos melhor as todas as vantagens e desvantagens de cada uma dessas opções aqui citadas quando elas quando elas forem parte do dia a dia de muitos programadores, um futuro não tão distante.

Agradeço ao Rafael Ferreira e ao Renato Lucindo pelas discussões e revisões.

11 Comentários

  1. William 25/09/2009 at 05:33 #

    Otimo post Guilherme!

    Este futuro ao qual você se refere nao esta longe realmente!

    Linguagens como Scala e Clojure , alem de diversas implementações de estrategias para concorrencia /paralelismo como Hadoop(MapReduce em Java), Terracotta são adotadas rapidamente por diversas empresas.

    A questão exata é saber os prós e contras de cada e aplicar tudo na medida certa!

    Muito bom post!

  2. Henrique Abreu 25/09/2009 at 10:05 #

    Bom post, mas tem uns erros no tipo de retorno das funções no 1º código:
    void geraCorpo … void geraRodape … void processaRelatorio
    return geraCorpo + geraRodape ?

    Abraço,

  3. Leandro Silva 25/09/2009 at 10:46 #

    Muito bom, Guilherme!

    Uma alternativa para concorrência Java baseada em troca de mensagens é a biblioteca Jetlang:

    http://code.google.com/p/jetlang

    Para ser franco, acho ela um tanto ruidosa. Quando fiz alguns estudos sobre concorrência e paralelismo tempos atrás, conheci a GParallelizer (em Groovy) que você citou, e fiquei bem inspirado a fazer algo bem próximo disso em Java. Tive algum sucesso no design da API, mas a implementação ainda está um tanto pobre.

    Mais uma vez, ótimo post!

  4. Guilherme Silveira 25/09/2009 at 13:02 #

    Henrique, muito obrigado, as alterações já foram feitas.
    Leandro, William, obrigado por adicionarem mais valor as informações do post

    Abraço

  5. Savio 25/09/2009 at 14:47 #

    Bom post.

    Obviamente o objetivo não era ser abrangente, mas achei que pecaram em não citar I/O Assíncrona. Esse conceito é muito importante porque livra a mente do programador de achar que tudo se resolve com threads. Na prática quase nunca thread é a solução ideal. Quase nunca precisamos de concorrência _real_, i.e., execução simultânea em cores/processadores diferentes. O que normalmente precisamos é orquestrar tarefas, e permitir mais de um fluxo de execução. Isso não implica em concorrência real.

  6. Paulo Silveira 25/09/2009 at 15:10 #

    Ola Savio! Quase no fim do artigo ha sim citação sobre a API não blocante e assincrona do Java: o java.nio!

  7. Savio 25/09/2009 at 18:04 #

    Essa API do java na verdade é um non-blocking IO por polling, certo?

    Uma outra forma de async IO talvez mais interessante é por callbacks e eventos.

    Frameworks como Twisted (python), Boost.ASIO (c++) e a API aio_* do Linux 2.6 fazem async IOs muito mais robustas e flexíveis.

    Pra que fazer polling se eu posso receber uma mensagem quando minha tarefa estiver pronta? 🙂

    Att.

  8. Paulo Silveira 25/09/2009 at 18:19 #

    Ola Savio!

    O Selector do java.nio vai fazer isso pra voce, e voce pode esperar algo por callback pelo PooledExecutor se quiser. Mas nao sei comparar com esses frameworks que voce postou, ja ta bem longe do meu conhecimento. Dizem que o java.nio é bem flexivel tambem comparado com as outras linguagens, e que a proposta do nio2 vai mais longe ainda.

    Paulo

  9. Savio 25/09/2009 at 18:40 #

    Perfeitamente.

    Com callbacks, thread pools e selectors o lance fica flexível mesmo. Já cobre a maioria esmagadora dos casos.

    Obrigado pela explicação. 🙂

  10. Guilherme Garnier 30/09/2009 at 14:18 #

    Excelente post Guilherme. Só mais um errinho: o nome do método no primeiro exemplo é processaRelatorio, e não processa_relatorio.

  11. Paulo Silveira 13/10/2009 at 04:10 #

    @Guilherme Garnier, metodo modificado!

    Pra quem esta interessado em STM:
    http://kskky.info/wiki/STM.NETInFramework4

Deixe uma resposta