Como a segurança do encadeamento pode ser fornecida por uma linguagem de programação semelhante à maneira como a segurança da memória é fornecida pelo Java e C #?

Java e C # fornecem segurança de memória, verificando os limites da matriz e as desreferências de ponteiros.

Quais mecanismos podem ser implementados em uma linguagem de programação para evitar a possibilidade de condições de corrida e impasses?

As corridas ocorrem quando você tem o aliasing simultâneo de um objeto e, pelo menos, um dos aliases está mudando.

Portanto, para evitar corridas, você precisa tornar uma ou mais dessas condições falsas.

Várias abordagens abordam vários aspectos. A programação funcional enfatiza a imutabilidade, que remove a mutabilidade. O bloqueio / atômica remove a simultaneidade. Os tipos afins removem o alias (o Rust remove o alias mutável). Os modelos de ator geralmente removem o alias.

Você pode restringir os objetos com aliases, para que seja mais fácil garantir que as condições acima sejam evitadas. É aí que entram os canais e / ou os estilos de passagem de mensagens. Você não pode usar o alias da memória arbitrária, apenas o final de um canal ou fila que está organizado para ser livre de corridas. Geralmente, evitando a simultaneidade, ou seja, bloqueios ou atômica.

A desvantagem desses vários mecanismos é que eles restringem os programas que você pode escrever. Quanto mais brusca a restrição, menos programas. Portanto, nenhum alias ou mutabilidade funciona e são fáceis de raciocinar, mas são muito limitantes.

É por isso que Rust está causando tanta agitação. É uma linguagem de engenharia (contra a acadêmica) que suporta alias e mutabilidade, mas faz com que o compilador verifique se eles não ocorrem simultaneamente. Embora não seja o ideal, ele permite que uma classe maior de programas seja gravada com segurança do que muitos de seus antecessores.

Java e C # fornecem segurança de memória, verificando os limites da matriz e as desreferências de ponteiros.

É importante pensar primeiro em como o C # e o Java fazem isso. Eles fazem isso convertendo o que é comportamento indefinido em C ou C ++ em comportamento definido: travar o programa . Desreferências nulas e exceções de índice de matriz nunca devem ser capturadas em um programa C # ou Java correto; eles não devem acontecer em primeiro lugar porque o programa não deve ter esse bug.

Mas acho que não é o que você quer dizer com sua pergunta! Poderíamos facilmente escrever um tempo de execução "deadlock safe" que verifica periodicamente se há n threads esperando um pelo outro e terminar o programa se isso acontecer, mas não acho que isso o satisfaria.

Quais mecanismos podem ser implementados em uma linguagem de programação para evitar a possibilidade de condições de corrida e impasses?

O próximo problema que enfrentamos com sua pergunta é que "condições de corrida", ao contrário de impasses, são difíceis de detectar. Lembre-se, o que buscamos na segurança das linhas não é eliminar as corridas . O que queremos é tornar o programa correto, independentemente de quem vencer a corrida ! O problema com as condições de corrida não é que dois threads estejam sendo executados em uma ordem indefinida e não sabemos quem vai terminar primeiro. O problema com as condições de corrida é que os desenvolvedores esquecem que algumas ordens de acabamento de threads são possíveis e não respondem a essa possibilidade.

Portanto, sua pergunta se resume basicamente a "existe uma maneira de uma linguagem de programação garantir que meu programa esteja correto?" e a resposta a essa pergunta é, na prática, não.

Até agora, apenas critiquei sua pergunta. Deixe-me tentar mudar de marcha aqui e abordar o espírito da sua pergunta. Existem escolhas que os designers de linguagem poderiam fazer que mitigassem a situação horrível em que estamos com o multithreading?

A situação é realmente horrível! Obter o código multithread correto, principalmente em arquiteturas de modelo de memória fraca, é muito, muito difícil. É instrutivo pensar sobre por que é difícil:

• Vários threads de controle em um processo são difíceis de raciocinar. Uma discussão é difícil o suficiente!
• As abstrações tornam-se extremamente vazadas em um mundo multithread. No mundo de thread único, garantimos que os programas se comportam como se fossem executados em ordem, mesmo que não sejam realmente executados em ordem. No mundo multithread, esse não é mais o caso; as otimizações que seriam invisíveis em um único encadeamento tornam-se visíveis e agora o desenvolvedor precisa entender essas possíveis otimizações.
• Mas piora. A especificação C # diz que NÃO é necessário que uma implementação tenha uma ordem consistente de leituras e gravações que possa ser acordada por todos os threads . A noção de que existem "raças", e que há um vencedor claro, na verdade não é verdadeira! Considere uma situação em que há duas gravações e duas leituras para algumas variáveis ​​em muitos threads. Em um mundo sensato, podemos pensar "bem, não podemos saber quem vai vencer as corridas, mas pelo menos haverá uma corrida e alguém vencerá". Nós não estamos nesse mundo sensível. O C # permite que vários threads discordem sobre a ordem na qual as leituras e gravações ocorrem; não há necessariamente um mundo consistente que todos estejam observando.

Portanto, existe uma maneira óbvia de os designers de idiomas melhorarem as coisas. Abandone as vitórias de desempenho dos processadores modernos . Faça com que todos os programas, mesmo os multiencadeados, tenham um modelo de memória extremamente forte. Isso tornará os programas multithread muitas vezes mais lentos, o que funciona diretamente contra o motivo de ter programas multithread em primeiro lugar: para melhorar o desempenho.

Mesmo deixando de lado o modelo de memória, há outras razões pelas quais o multithreading é difícil:

• Prevenir impasses requer análise de todo o programa; você precisa conhecer a ordem global na qual os bloqueios podem ser removidos e impor essa ordem em todo o programa, mesmo que o programa seja composto de componentes gravados em diferentes momentos por diferentes organizações.
• A ferramenta principal que lhe damos para domar o multithreading é o bloqueio, mas os bloqueios não podem ser compostos .

Esse último ponto traz mais explicações. Por "composível", quero dizer o seguinte:

Suponha que desejamos calcular um int dado um duplo. Escrevemos uma implementação correta da computação:

int F(double x) { correct implementation here }

Suponha que desejamos calcular uma string, dada uma int:

string G(int y) { correct implementation here }

Agora, se quisermos calcular uma string dada uma duplicação:

double d = whatever;
string r = G(F(d));

G e F podem ser compostos em uma solução correta para o problema mais complexo.

Mas os bloqueios não têm essa propriedade devido a conflitos. Um método correto M1 que retira bloqueios na ordem L1, L2 e um método correto M2 que retira bloqueios na ordem L2, L1, não podem ser utilizados no mesmo programa sem criar um programa incorreto. Os bloqueios fazem com que você não possa dizer "todo método individual está correto, portanto tudo está correto".

Então, o que podemos fazer, como designers de linguagem?

Primeiro, não vá lá. Múltiplos threads de controle em um programa são uma péssima idéia, e compartilhar memória entre threads é uma má idéia; portanto, não a coloque no idioma ou no tempo de execução.

Aparentemente, isso não é para iniciantes.

Vamos voltar nossa atenção para a pergunta mais fundamental: por que temos vários threads em primeiro lugar? Há duas razões principais, e elas são confundidas com a mesma coisa frequentemente, embora sejam muito diferentes. Eles são conflitantes porque ambos são sobre gerenciamento de latência.

• Criamos threads, incorretamente, para gerenciar a latência de E / S. Precisa escrever um arquivo grande, acessar um banco de dados remoto, qualquer que seja, criar um thread de trabalho em vez de bloquear o thread da interface do usuário.

Péssima ideia. Em vez disso, use assincronia de thread único por meio de corotinas. C # faz isso lindamente. Java, não tão bem. Mas esta é a principal maneira pela qual a atual safra de designers de idiomas está ajudando a resolver o problema de segmentação. O awaitoperador em C # (inspirado nos fluxos de trabalho assíncronos em F # e em outras técnicas anteriores) está sendo incorporado em cada vez mais idiomas.

• Criamos threads, adequadamente, para saturar CPUs ociosas com trabalho computacionalmente pesado. Basicamente, estamos usando threads como processos leves.

Os designers de idiomas podem ajudar criando recursos de idiomas que funcionam bem com paralelismo. Pense em como o LINQ se estende tão naturalmente ao PLINQ, por exemplo. Se você é uma pessoa sensata e limita suas operações TPL a operações ligadas à CPU que são altamente paralelas e não compartilham memória, você pode obter grandes vitórias aqui.

O que mais podemos fazer?

• Faça o compilador detectar os erros mais complicados e transformá-los em avisos ou erros.

O C # não permite que você espere em um bloqueio, porque essa é uma receita para conflitos. O C # não permite que você bloqueie um tipo de valor, porque isso é sempre a coisa errada a fazer; você trava na caixa, não no valor. O C # avisa se você alias um volátil, porque o alias não impõe semântica de aquisição / lançamento. Existem muitas outras maneiras pelas quais o compilador pode detectar problemas comuns e evitá-los.

• Projete recursos de qualidade, onde a maneira mais natural de fazê-lo também é a maneira mais correta.

C # e Java cometeram um grande erro de design, permitindo o uso de qualquer objeto de referência como monitor. Isso incentiva todos os tipos de práticas ruins que tornam mais difícil rastrear impasses e mais difíceis de impedi-los estaticamente. E desperdiça bytes em cada cabeçalho de objeto. Os monitores devem ser derivados de uma classe de monitores.

• Uma grande quantidade de tempo e esforço da Microsoft Research foi feita para tentar adicionar memória transacional de software a uma linguagem semelhante a C #, e eles nunca tiveram um desempenho bom o suficiente para incorporá-la ao idioma principal.

STM é uma ideia bonita, e eu brinquei com implementações de brinquedos em Haskell; permite que você componha de maneira muito mais elegante soluções corretas com peças corretas do que as soluções baseadas em bloqueio. No entanto, não sei o suficiente sobre os detalhes para dizer por que não foi possível fazê-lo funcionar em escala; pergunte a Joe Duffy da próxima vez que você o vir.

• Outra resposta já mencionou imutabilidade. Se você tiver imutabilidade combinada com corotinas eficientes, poderá criar recursos como o modelo do ator diretamente no seu idioma; pense Erlang, por exemplo.

Tem havido muita pesquisa em linguagens baseadas em cálculo de processo e eu não entendo muito bem esse espaço; tente ler alguns artigos sobre o assunto e veja se tem alguma ideia.

• Facilite a gravação de bons analisadores por terceiros

Depois de trabalhar na Microsoft em Roslyn, trabalhei na Coverity, e uma das coisas que fiz foi obter o front end do analisador usando Roslyn. Com uma análise lexical, sintática e semântica precisa fornecida pela Microsoft, poderíamos nos concentrar no trabalho árduo de detectar detectores que encontravam problemas comuns de multithreading.

• Aumente o nível de abstração

Uma razão fundamental pela qual temos corridas e impasses e tudo isso é porque estamos escrevendo programas que dizem o que fazer , e acontece que somos todos péssimos em escrever programas imperativos; o computador faz o que você diz e pedimos para fazer as coisas erradas. Muitas linguagens de programação modernas são cada vez mais sobre programação declarativa: diga quais resultados você deseja e deixe o compilador descobrir a maneira eficiente, segura e correta de alcançar esse resultado. Mais uma vez, pense no LINQ; queremos que você diga from c in customers select c.FirstName, o que expressa uma intenção . Deixe o compilador descobrir como escrever o código.

• Use computadores para resolver problemas do computador.

Algoritmos de aprendizado de máquina são muito melhores em algumas tarefas do que algoritmos codificados manualmente, embora, é claro, existam muitas vantagens, incluindo correção, tempo necessário para treinar, preconceitos introduzidos por um mau treinamento etc. Mas é provável que muitas tarefas que atualmente codificamos "manualmente" sejam em breve passíveis de soluções geradas por máquina. Se os humanos não estão escrevendo o código, eles não estão escrevendo bugs.

Desculpe que foi um pouco divagar lá; esse é um tópico enorme e difícil e nenhum consenso claro surgiu na comunidade de PL nos 20 anos que acompanho o progresso nesse espaço problemático.