Multi-threading sem bloqueio é para verdadeiros especialistas em threading

Eu estava lendo uma resposta que Jon Skeet deu a uma pergunta e nela ele mencionou o seguinte:

No que me diz respeito, o multi-threading sem bloqueio é para verdadeiros especialistas em threading, dos quais não sou um.

Não é a primeira vez que ouço isso, mas encontro muito poucas pessoas falando sobre como você realmente faz isso se estiver interessado em aprender como escrever código multi-threading sem bloqueio.

Portanto, minha pergunta é além de aprender tudo que puder sobre threading, etc, onde você começa a tentar aprender a escrever código multi-threading sem bloqueio e quais são alguns bons recursos.

Felicidades

As implementações "livres de bloqueio" atuais seguem o mesmo padrão na maioria das vezes:

• * leia algum estado e faça uma cópia dele **
• * modificar cópia **
• fazer uma operação interligada
• tente novamente se falhar

_{(* opcional: depende da estrutura de dados / algoritmo)}

O último bit é assustadoramente semelhante a um spinlock. Na verdade, é um spinlock básico . :)
Concordo com @nobugz sobre isso: o custo das operações intertravadas usadas no multi-threading sem bloqueio é dominado pelas tarefas de cache e coerência de memória que ele deve realizar .

O que você ganha, entretanto, com uma estrutura de dados "livre de bloqueio" é que seus "bloqueios" são muito refinados . Isso diminui a chance de que dois threads simultâneos acessem o mesmo "bloqueio" (local da memória).

O truque na maioria das vezes é que você não tem bloqueios dedicados - em vez disso, você trata, por exemplo, todos os elementos em uma matriz ou todos os nós em uma lista vinculada como um "bloqueio de rotação". Você lê, modifica e tenta atualizar se não houve atualização desde sua última leitura. Se houver, você tenta novamente.
Isso torna seu "bloqueio" (oh, desculpe, não bloqueio :) muito refinado, sem introduzir memória adicional ou requisitos de recursos.
Torná-lo mais refinado diminui a probabilidade de esperas. Torná-lo o mais refinado possível sem introduzir requisitos de recursos adicionais parece ótimo, não é?

A maior parte da diversão, entretanto, pode vir de garantir o pedido correto de carregamento / armazenamento .
Contrariamente às intuições de alguém, as CPUs são livres para reordenar leituras / gravações de memória - elas são muito inteligentes, a propósito: você terá dificuldade em observar isso a partir de um único thread. No entanto, você terá problemas quando começar a fazer multi-threading em vários núcleos. Suas intuições irão falhar: só porque uma instrução está no início do seu código, isso não significa que realmente acontecerá antes. CPUs podem processar instruções fora de ordem: e eles gostam especialmente de fazer isso com instruções com acessos à memória, para ocultar a latência da memória principal e fazer melhor uso de seu cache.

Agora, é certo contra a intuição que uma sequência de código não flui "de cima para baixo", ao invés disso, ela funciona como se não houvesse sequência alguma - e pode ser chamada de "playground do diabo". Acredito ser inviável dar uma resposta exata sobre quais reordenamentos de carga / loja ocorrerão. Em vez disso, sempre se fala em termos de mays e mights e latas e se preparar para o pior. "Oh, a CPU pode reordenar esta leitura para vir antes da gravação, então é melhor colocar uma barreira de memória aqui, neste local."

Questões são complicadas pelo fato de que mesmo esses mays e mights podem ser diferentes entre arquiteturas de CPU. Ele pode ser o caso, por exemplo, que algo que é garantido que não aconteceria em um arquitetura poderia acontecer em outro.

Para obter o multithread "livre de bloqueio" certo, você precisa entender os modelos de memória.
Conseguir o modelo de memória e as garantias corretos não é trivial, no entanto, como demonstrado por esta história, em que a Intel e a AMD fizeram algumas correções na documentação para MFENCEcausar confusão entre os desenvolvedores de JVM . No final das contas, a documentação na qual os desenvolvedores confiaram desde o início não era tão precisa em primeiro lugar.

Os bloqueios no .NET resultam em uma barreira de memória implícita, então você está seguro ao usá-los (na maioria das vezes, isto é ... veja por exemplo esta grandeza de Joe Duffy - Brad Abrams - Vance Morrison em inicialização preguiçosa, bloqueios, voláteis e memória barreiras. :) (Certifique-se de seguir os links dessa página.)

Como um bônus adicional, você será apresentado ao modelo de memória .NET em uma missão paralela . :)

Também há um "oldie but goldie" de Vance Morrison: O que todo desenvolvedor deve saber sobre aplicativos multithread .

... e claro, como @Eric mencionou, Joe Duffy é uma leitura definitiva sobre o assunto.

Um bom STM pode chegar o mais próximo possível de um bloqueio de baixa granularidade e provavelmente fornecerá um desempenho próximo ou equivalente a uma implementação feita à mão. Um deles é o STM.NET dos projetos DevLabs da MS.

Se você não é um fanático apenas por .NET, Doug Lea fez um ótimo trabalho na JSR-166 .
Cliff Click tem uma abordagem interessante sobre tabelas de hash que não dependem de lock-striping - como fazem as tabelas de hash simultâneas Java e .NET - e parecem escalar bem para 750 CPUs.

Se você não tem medo de se aventurar no território do Linux, o artigo a seguir fornece mais informações sobre os aspectos internos das arquiteturas de memória atuais e como o compartilhamento de linha de cache pode destruir o desempenho: O que todo programador deve saber sobre memória .

@Ben fez muitos comentários sobre o MPI: Concordo sinceramente que o MPI pode brilhar em algumas áreas. Uma solução baseada em MPI pode ser mais fácil de raciocinar, mais fácil de implementar e menos sujeita a erros do que uma implementação de bloqueio incompleta que tenta ser inteligente. (No entanto, é - subjetivamente - também verdadeiro para uma solução baseada em STM.) Eu também apostaria que é anos-luz mais fácil escrever corretamente um aplicativo distribuído decente em, por exemplo, Erlang, como muitos exemplos bem-sucedidos sugerem.

MPI, no entanto, tem seus próprios custos e seus próprios problemas quando está sendo executado em um sistema único com vários núcleos . Por exemplo, em Erlang, existem problemas a serem resolvidos em torno da sincronização da programação do processo e das filas de mensagens .
Além disso, em seu núcleo, os sistemas MPI geralmente implementam um tipo de programação N: M cooperativa para "processos leves". Isso, por exemplo, significa que há uma mudança de contexto inevitável entre processos leves. É verdade que não é uma "troca de contexto clássica", mas principalmente uma operação de espaço do usuário e pode ser feita rapidamente - no entanto, eu sinceramente duvido que possa ser trazida para os 20-200 ciclos que uma operação interligada leva . A troca de contexto do modo de usuário é certamente mais lentamesmo na biblioteca Intel McRT. A programação N: M com processos leves não é nova. Os LWPs estiveram lá em Solaris por um longo tempo. Eles foram abandonados. Havia fibras no NT. Eles são principalmente uma relíquia agora. Houve "ativações" no NetBSD. Eles foram abandonados. O Linux teve sua própria opinião sobre o assunto de segmentação N: M. Parece estar meio morto agora.
De vez em quando, surgem novos concorrentes: por exemplo, McRT da Intel ou, mais recentemente , Programação em modo de usuário junto com ConCRT da Microsoft.
No nível mais baixo, eles fazem o que um agendador N: M MPI faz. Erlang - ou qualquer sistema MPI - pode se beneficiar muito em sistemas SMP explorando o novo UMS .

Acho que a pergunta do OP não é sobre os méritos e argumentos subjetivos a favor / contra qualquer solução, mas se eu tivesse que responder a isso, acho que depende da tarefa: para construir estruturas de dados básicas de baixo nível e alto desempenho que rodam em um sistema único com muitos núcleos , técnicas low-lock / "lock-free" ou um STM produzirá os melhores resultados em termos de desempenho e provavelmente venceria uma solução MPI a qualquer momento em termos de desempenho, mesmo se as rugas acima forem corrigidas por exemplo, em Erlang.
Para construir qualquer coisa moderadamente mais complexa que seja executada em um único sistema, eu talvez escolheria o bloqueio de granulação grossa clássico ou, se o desempenho for uma grande preocupação, um STM.
Para construir um sistema distribuído, um sistema MPI provavelmente seria uma escolha natural.
Observe que também existem implementações MPI para .NET (embora pareçam não estar tão ativas).

Livro de Joe Duffy:

http://www.bluebytesoftware.com/books/winconc/winconc_book_resources.html

Ele também escreve um blog sobre esses tópicos.

O truque para acertar os programas de baixo bloqueio é entender em um nível profundo precisamente quais são as regras do modelo de memória em sua combinação particular de hardware, sistema operacional e ambiente de tempo de execução.

Pessoalmente, não sou nem de perto inteligente o suficiente para fazer a programação correta de low-lock além do InterlockedIncrement, mas se você for, ótimo, vá em frente. Apenas certifique-se de deixar muita documentação no código para que as pessoas que não são tão inteligentes quanto você não quebrem acidentalmente uma das invariáveis ​​do seu modelo de memória e introduzam um bug impossível de encontrar.

Atualmente, não existe "threading sem bloqueio". Era um playground interessante para a academia e afins, no final do século passado, quando o hardware do computador era lento e caro. O algoritmo de Dekker sempre foi meu favorito, o hardware moderno o colocou no pasto. Não funciona mais.

Dois desenvolvimentos acabaram com isso: a disparidade crescente entre a velocidade da RAM e da CPU. E a capacidade dos fabricantes de chips de colocar mais de um núcleo de CPU em um chip.

O problema de velocidade da RAM exigia que os projetistas do chip colocassem um buffer no chip da CPU. O buffer armazena código e dados, rapidamente acessíveis pelo núcleo da CPU. E pode ser lido e gravado de / para a RAM em um ritmo muito mais lento. Esse buffer é chamado de cache da CPU, a maioria das CPUs tem pelo menos dois deles. O cache de primeiro nível é pequeno e rápido, o segundo é grande e mais lento. Enquanto a CPU puder ler dados e instruções do cache de primeiro nível, ela será executada rapidamente. Uma falha de cache é muito cara, ela coloca a CPU em hibernação por até 10 ciclos se os dados não estiverem no primeiro cache, até 200 ciclos se não estiver no segundo cache e precisam ser lidos RAM.

Cada núcleo da CPU tem seu próprio cache, eles armazenam sua própria "visão" da RAM. Quando a CPU grava dados, a gravação é feita no cache que é então, lentamente, descarregada na RAM. Inevitável, cada núcleo agora terá uma visão diferente do conteúdo da RAM. Em outras palavras, uma CPU não sabe o que outra CPU escreveu até que o ciclo de gravação de RAM seja concluído e a CPU atualize sua própria visualização.

Isso é dramaticamente incompatível com threading. Você sempre se preocupa muito com o estado de outro encadeamento quando deve ler dados que foram escritos por outro encadeamento. Para garantir isso, você precisa programar explicitamente uma chamada barreira de memória. É uma primitiva de CPU de baixo nível que garante que todos os caches da CPU estejam em um estado consistente e tenham uma visão atualizada da RAM. Todas as gravações pendentes devem ser liberadas para a RAM e os caches precisam ser atualizados.

Isso está disponível no .NET, o método Thread.MemoryBarrier () implementa um. Dado que isso representa 90% do trabalho que a instrução de bloqueio faz (e 95 +% do tempo de execução), você simplesmente não está à frente, evitando as ferramentas que o .NET oferece e tentando implementar as suas próprias.

Google para bloquear estruturas de dados livres e memória transacional de software .

Vou concordar com John Skeet neste; threading sem bloqueio é o playground do diabo, e é melhor deixá-lo para as pessoas que sabem que sabem o que precisam saber.

Quando se trata de multi-threading, você precisa saber exatamente o que está fazendo. Quero dizer, explorar todos os cenários / casos possíveis que podem ocorrer quando você está trabalhando em um ambiente multi-thread. Multithreading livre de bloqueio não é uma biblioteca ou uma classe que incorporamos, é um conhecimento / experiência que ganhamos durante nossa jornada nos threads.

Mesmo que o encadeamento sem bloqueio possa ser difícil no .NET, geralmente você pode fazer melhorias significativas ao usar um bloqueio, estudando exatamente o que precisa ser bloqueado e minimizando a seção bloqueada ... isso também é conhecido como minimizar a granularidade do bloqueio .

Por exemplo, basta dizer que você precisa tornar um tópico de coleção seguro. Não lance um bloqueio cegamente em torno de um método iterando sobre a coleção se ele executar alguma tarefa que consome muita CPU em cada item. Talvez você só precise bloquear a criação de uma cópia superficial da coleção. A iteração da cópia pode funcionar sem bloqueio. É claro que isso depende muito das especificações do seu código, mas consegui corrigir um problema de comboio de bloqueio com essa abordagem.