Concorrência e o ToonTalk

Antes que eu tente explicar a computação concorrente no ToonTalk e por que é difícil estender linguagens seqüenciais para que sejam concorrentes, explicarei a relação entre concorrência, paralelismo e computação distribuída. Os processos paralelos são aqueles que estão rodando dentro do mesmo sistema computacional. O sistema tipicamente tem mais de um processador. Os processos distribuídos são aqueles que rodam tipicamente em diferentes sistemas computacionais conectados via rede. A distinção entre paralelo e distribuído é importante porque a computação distribuída está tipicamente a caminho do limite organizacional ou de segurança. Portanto apenas a computação distribuída precisa se preocupar com segurança, alocação de recursos, recuperação de falhas de hardware e coisas semelhantes. Em discussões em que a distinção não é importante, eu faço referência a processos concorrentes, isto é, processos que podem ser tanto paralelos quanto distribuídos.

O ToonTalk é uma linguagem de programação concorrente plena. Isto porque todas as subcomputações são expressas como processos novos, independentes. Se um robô precisa que outros robôs realizem alguma subcomputação, ele deve ser treinado para carregar um caminhão com aqueles outros robôs. A nova casa construída pela equipe no caminhão é um novo processo. Diferentemente de linguagens convencionais (C, Java, Logo, Lisp, Fortran, Cobol, Perl, Basic etc.), não há um modo de expressar uma chamada de subrotina no ToonTalk. Uma chamada para um procedimento transfere o controle para o procedimento de tal forma que o programa principal, após a chamada do procedimento, tem de esperar até que o procedimento termine. Quando o procedimento termina, ele retorna (algumas vezes retornando um valor). O programa principal pode então reiniciar onde estava quando o procedimento foi chamado. Pode-se obter o comportamento equivalente no ToonTalk treinando um robô para carregar um caminhão com robôs e uma caixa com um pombo nela. O robô deve colocar o ninho do pombo nesta caixa e não fazer nada mais. Aquele robô ou outros membros da equipe devem ser programados para procurar por algo no ninho. Conseqüentemente, este processo será suspenso até que os robôs que foram colocados no caminhão dêem algo ao pombo. Os robôs aguardando no ninho verão o que foi entregue e retomarão a computação. Em outras palavras, uma chamada de subrotina ou de procedimento no ToonTalk é apenas um padrão muito especial do uso de caminhões, pombos e robôs. O ToonTalk apenas fornece ao programador a capacidade mais geral de expressar a geração de novos processos.

A ausência de subrotinas no ToonTalk o torna muito mais adequado para ter um número muito maior de processos do que as linguagens de programação convencionais. A razão para isso é que todos implementam chamadas de subrotina utilizando uma estrutura de dados chamada de pilha. As pilhas são um meio muito efetivo de implementar chamadas de procedimentos, inclusive chamadas recursivas. O problema é que cada processo (mesmo se suspenso) precisa de sua própria pilha. Isto torna os processos algo custoso. Um processo no ToonTalk só precisa de 2 indicadores: para o programa (a equipe de robôs) e para os dados (a caixa). Não há pilha; não há nada mais. Eu testei o ToonTalk com dezenas de milhares de casas (isto é, processos). Em contraste, quando utilizei Java, o sistema parou de funcionar quando eu tinha apenas algumas centenas de processos.

As linguagens convencionais têm estado compartilhado. As mesmas variáveis, estruturas de dados e objetos podem ser acessados a partir de diferentes processos (processos que compartilham dados são freqüentemente chamados "threads"). O estado compartilhado é necessário nestas linguagens de forma que os "threads" trabalhem em conjunto. Este compartilhamento entre processos independentes concorrentes é, entretanto, muito perigosa. Ela leva à concorrência entre processos ("race conditions"). Considere uma variável, A, que se supõe que represente o saldo atual de uma conta de poupança. (A poderia ser uma variável global ou um exemplo de variável de um objeto – ambos os tipos de variáveis têm esse problema.) Uma subrotina foi escrita para sacar X de A depois de verificar se X é menor ou igual a A. Ela o faz atualizando A para A-X. Em outras palavras, a rotina permite uma retirada apenas se houver fundos suficientes na conta. Agora nos permita introduzir a concorrência. Suponha que há uma conta com dez reais e um processo gostaria de retirar 9 reais e outro processo quer retirar 8 reais. Com azar ambas as retiradas podem ocorrer. E ainda pior, o saldo pode ser 1 real, 2 reais ou -7 reais depois do processamento das duas retiradas. Como? Considere este cenário:

O processo 1 verifica que X é menor que A e calcula A-X igual a 1, mas antes de atribuir 1 para A, o processo 2 se inicia e vê que A ainda é dez, e portanto processa a retirada inteira e ajusta A para 2. O processo 1 é retomado onde parou e ajusta A para 1.

Então como as linguagens convencionais lidam com concorrência entre processos? Elas introduzem novas idéias de programação: bloqueios ou regiões críticas. Por exemplo, o procedimento de retirada poderia obter um bloqueio em A de forma que nenhum outro processo pudesse acessá-lo. Poderia então, com segurança, compará-lo a X, calcular A- X e ajustar A ao resultado. Não apenas isso acrescenta complexidade à tarefa de fazer programas, mas pode levar a novos problemas: especialmente "deadlock". Suponha que o processo 1 bloqueie A e então necessita encontrar o valor de B que é bloqueado pelo processo 2. Então o processo 1 é suspenso e espera que o processo 2 libere B. Mas o que acontece se o processo 2 precisa então acessar o valor de A? A está bloqueado, então o processo 2 também é suspenso. Isso é freqüentemente chamado de espera circular. Você poderia pensar que seria simples programar de forma tal que se evitasse esta espécie de dependência mútua. Mas o ciclo de dependência pode envolver centenas de processos.

Então por que o ToonTalk não sofre desses problemas? A razão é que o ToonTalk não tem estado compartilhado. Uma caixa só pode existir em um lugar. E os robôs na mesma casa fazem turnos - eles nunca trabalham na mesma caixa ao mesmo tempo. A ausência de estados compartilhados é a forma pela qual o ToonTalk evita concorrência ou deadlock. Mas isso não limita a expressividade da linguagem? Poderia, se não fosse pelos pombos. O fato de que cópias do mesmo pombo voam para o mesmo ninho proporciona um meio para comunicação muitos-para-um que pode ser usado em vez do estado compartilhado. Como exemplo, considere o exemplo do ToonTalk da conta bancária. Múltiplos processos podem retirar dinheiro da mesma conta. Cada processo tem uma cópia de um pombo cujo ninho está na caixa que está representando a conta bancária. Os robôs em casas diferentes podem dar aos pombos solicitações de retiradas da conta, dando aos pombos, caixas contendo a quantia de dinheiro a ser retirada. Nós não sabemos qual caixa terminará no topo do ninho – mas todas elas serão empilhadas no ninho (Em outras palavras, as solicitações são enfileiradas no ninho). Os robôs trabalhando na conta verão uma caixa aparecer no ninho para uma solicitação de retirada. Eles irão processar a solicitação antes de começar a nova solicitação. Não há problema, mesmo se o cálculo do novo saldo exigir um novo subcálculo. O robô carregará o caminhão com robôs e uma caixa para calcular o novo saldo. E então ele colocará o ninho que receberá o resultado no local onde o saldo atual está mantido. A próxima solicitação não será processada até que o subcálculo dê ao pombo o novo saldo e o ninho apropriado seja coberto.

Em resumo, tentativas de adicionar concorrência às linguagens com subrotinas e estado compartilhado conduzem à complexidade, implementações custosas de processos e erros que são muito difíceis de localizar. O ToonTalk, em contraste, foi projetado desde o início para ser concorrente. No ToonTalk não há a necessidade de introduzir bloqueios ou regiões críticas, os processos custam muito pouco e concorrências e deadlocks são evitados.