Simultaneidade composicional em Java ou qualquer outra linguagem de programação

Enquanto eu lia um trabalho de pesquisa sobre concorrência, chamado Software and the Concurrency Revolution ( versão html ). Me deparei com as seguintes linhas:

Infelizmente, embora os bloqueios funcionem, eles apresentam sérios problemas para o desenvolvimento moderno de software. Um problema fundamental dos bloqueios é que eles não são compostáveis . Você não pode pegar dois pedaços de código corretos baseados em bloqueio, combiná-los e saber que o resultado ainda está correto. O desenvolvimento de software moderno depende da capacidade de compor bibliotecas em programas maiores e, portanto, é uma dificuldade séria que não podemos construir componentes baseados em bloqueio sem examinar suas implementações.

1. Eu estava pensando, como o Java garante simultaneidade composível ou mesmo existe uma maneira de produzir esses cenários.

2. E como podemos sincronizar dados em uma ou mais bibliotecas? Um programador pode fazer isso a partir do seu programa ou depende da biblioteca sincronizar as coisas.

3. Se não for Java, existe alguma outra linguagem que use simultaneidade baseada em bloqueio e garanta simultaneidade composível?

Também é retirado do mesmo trabalho:

Há pelo menos três grandes problemas com métodos sincronizados. Primeiro, eles não são apropriados para tipos cujos métodos chamam funções virtuais em outros objetos (por exemplo, Vector de Java e SyncHashTable de Java), porque chamar código de terceiros enquanto mantém um bloqueio abre a possibilidade de conflito . Segundo, os métodos sincronizados podem executar muito bloqueio, adquirindo e liberando bloqueios em todas as instâncias do objeto, mesmo aquelas nunca compartilhadas entre os threads (geralmente a maioria). Terceiro, os métodos sincronizados também podem executar muito pouco bloqueio, não preservando a atomicidade quando um programa chama vários métodos em um objeto ou em objetos diferentes. Como um exemplo simples deste último, considere uma transferência bancária: account1.Credit (amount); account2.Debit (amount) ...

Nota: O artigo foi publicado em setembro de 2005

Não é a linguagem Java. É a natureza dos bloqueios (mutexes).

Existem maneiras melhores de obter simultaneidade aprimorada e, ao mesmo tempo, garantir a correção, formas que são independentes do idioma:

1. Usando objetos imutáveis, para que você não precise de bloqueios.
2. Usando promessas e estilo de passagem de continuação.
3. Usando estruturas de dados sem bloqueio.
4. Usando a memória transacional de software para compartilhar o estado com segurança.

Todas essas técnicas permitem simultaneidade aprimorada sem usar bloqueios. Nenhum deles depende especificamente da linguagem Java.

Eu estava pensando, como o Java garante simultaneidade composível ou mesmo existe uma maneira de produzir esses cenários.

Como o artigo diz, não é possível garantir a composição ao usar bloqueios junto com métodos virtuais (ou outro mecanismo semelhante, como passar funções como parâmetros). Se um trecho de código tiver acesso a métodos virtuais provenientes de outro trecho de código e ambos potencialmente usarem bloqueios, para compor com segurança (ou seja, sem o risco de um impasse) compor os dois trechos de código, será necessário inspecionar o código fonte de ambos.

E como podemos sincronizar dados em uma ou mais bibliotecas? Um programador pode fazer isso a partir do seu programa ou depende da biblioteca sincronizar as coisas.

Geralmente, cabe ao programador usar as bibliotecas para fazer a sincronização. Dessa forma, o programador sabe onde estão todos os bloqueios e pode garantir que eles não entrem em conflito.

Se não for Java, existe alguma outra linguagem que use simultaneidade baseada em bloqueio e garanta simultaneidade composível?

Novamente, o objetivo do artigo é que isso não é possível.

Mecanismos de bloqueio de baixo nível são inerentemente incontroláveis. Isso ocorre principalmente porque os bloqueios chegam ao mundo para afetar a máquina que executa as instruções.

As bibliotecas Java subsequentes adicionaram mecanismos de nível cada vez mais alto para garantir a operação multithread correta. Eles fazem isso restringindo o uso lock()e volatilea certas circunstâncias conhecidas e controláveis. Por exemplo, uma implementação de fila simultânea tem um comportamento muito localizado e permite raciocinar sobre estados antes e depois. O uso de mecanismos de nível superior significa que você precisa ler menos da especificação ou código para fazer a correção. Mas, e esse é um grande, mas você ainda precisa entender o modelo de bloqueio de qualquer subsistema e como ele interage. Além disso, as alterações no Java para simultaneidade após o Java 5 estão quase exclusivamente relacionadas às bibliotecas e não à linguagem.

O principal problema de qualquer mecanismo de bloqueio é que ele afeta o estado e opera no domínio do tempo. Nem humanos nem computadores raciocinam bem sobre estado ou tempo. É a capacidade de raciocinar sobre valor e estrutura que permitiu aos cientistas da computação criar mônadas, a primeira coisa que me vem à mente em relação à composibilidade em uma linguagem.

O mais próximo que chegamos é de processos sequenciais de comunicação . Isso ainda requer um mecanismo de alto nível, como caixas de correio e passagem de mensagens. Na minha humilde opinião, o CSP ainda não lida adequadamente com os grandes sistemas (o objetivo final do software compositável) ou com o raciocínio baseado no tempo.

Antes de tudo, agradeço a todos os membros que responderam a essa pergunta, especialmente a Robert Harvey, cuja resposta parece muito próxima da minha.

Eu pesquisei sobre conceitos de simultaneidade por dois anos e, de acordo com minhas descobertas, nenhuma linguagem fornece uma garantia de que suas construções de simultaneidade sejam compostas. Código de execução perfeitamente bom usando estruturas de dados imutáveis ​​e o STM também pode produzir resultados inesperados porque, sob o capô, o STM usa bloqueios. O STM é muito bom para operações atômicas, mas se falarmos sobre composibilidade de contrastes de simultaneidade entre módulos, há uma chance (muito pequena) de que o STM possa não funcionar como esperado.

Ainda assim, podemos minimizar a incerteza usando o seguinte (técnicas / métodos / construções):

1. Evitando bloqueios e sincronização
2. Usando STM
3. Usando estruturas de dados persistentes (imutáveis)
4. Evitando compartilhar estado
5. Funções puras
6. Estilo de programação assíncrona
7. Evitando a alternância frequente de contexto
8. O paradigma multiencadeamento e a natureza de seu ambiente desempenham papel importante

Talvez a objeção mais fundamental seja [...] que os programas baseados em bloqueio não sejam compostos: fragmentos corretos podem falhar quando combinados. - Tim Harris et al., "Transações de memória compostas", Seção 2: Histórico, pág.2

Atualizar

Graças a Jules, estou corrigido. O STM usa várias implementações e a maioria delas é livre de bloqueios. Mas ainda acredito que o STM é uma boa solução aqui, mas não a perfeita, e tem desvantagens:

Cada leitura (ou gravação) de um local de memória de dentro de uma transação é realizada por uma chamada para uma rotina STM para leitura (ou gravação) de dados. Com código sequencial, esses acessos são executados por uma única instrução da CPU. As rotinas de leitura e gravação do STM são significativamente mais caras que as instruções correspondentes da CPU, pois geralmente precisam manter os dados da contabilidade sobre cada acesso. A maioria dos STMs verifica se há conflitos com outras transações simultâneas, registra o acesso e, no caso de uma gravação, registra o valor atual (ou antigo) dos dados, além de ler ou gravar o local da memória acessada. Algumas dessas operações usam instruções caras de sincronização e acessam metadados compartilhados, o que aumenta ainda mais seus custos. Tudo isso reduz o desempenho de thread único quando comparado ao código seqüencial. - Por que o STM pode ser mais do que um brinquedo de pesquisa - página 1

Veja também estes documentos:

• http://dl.acm.org/citation.cfm?id=1454466
• http://dl.acm.org/citation.cfm?id=1924440

Esses documentos têm alguns anos. As coisas podem ter mudado / melhorado, mas não todas.

Ouvi dizer por pesquisadores respeitados que qualquer mecanismo de sincronização útil pode ser usado para criar um impasse. Memória transacional (seja hardware ou software) não é diferente. Por exemplo, considere esta abordagem para escrever uma barreira de encadeamento:

transaction {
    counter++;
}

while (true) {
    transaction {
        if (counter == num_threads)
            break;
    }
}

(Nota: o exemplo é retirado de um artigo de Yannis Smaragdakis no PACT 2009)

Se ignorarmos o fato de que essa não é uma boa maneira de sincronizar um grande número de threads, parece estar correto. Mas não é compostável. A decisão de colocar a lógica em duas transações é essencial. Se chamássemos isso de outra transação, de modo que tudo achatasse em uma transação, provavelmente nunca concluiríamos.

O mesmo se aplica aos canais de passagem de mensagens: os ciclos de comunicação podem causar conflitos. A sincronização ad-hoc com atômicos C ++ pode levar a conflitos. RCU, bloqueios de sequência, bloqueios de leitores / gravadores, variáveis ​​de condição e semáforos podem ser usados ​​para criar bloqueios.

Isso não quer dizer que transações ou canais (ou bloqueios ou RCU) sejam ruins. Em vez disso, é para dizer que algumas coisas simplesmente não parecem possíveis. Mecanismos de controle de simultaneidade escaláveis, compostáveis ​​e sem patologia provavelmente não são possíveis.

A melhor maneira de evitar problemas não é procurar um mecanismo de bala de prata, mas usar rigorosamente bons padrões. No mundo da computação paralela, um bom ponto de partida é a Programação Paralela Estruturada: Padrões para Computação Eficiente , de Arch Robison, James Reinders e Michael McCool. Para programação simultânea, existem alguns bons padrões (consulte o comentário de @ gardenhead), mas é improvável que os programadores de C ++ e Java os usem. Um padrão que mais pessoas poderiam começar a usar as maneiras corretas é substituir as sincronizações ad-hoc nos programas por uma fila de múltiplos consumidores multiprodutor. E a TM é definitivamente melhor do que bloqueios, pois aumenta o nível de abstração, para que os programadores se concentrem no que precisa ser atômico , nãocomo implementar um protocolo de bloqueio inteligente para garantir a atomicidade. Felizmente, à medida que a TM de hardware melhorar e os idiomas adicionarem mais suporte à TM, chegaremos a um ponto em que a TM substitui os bloqueios no caso comum.