Vamos ver como a programação simultânea e paralela no .Net funciona, usando o problema dos filósofos gastronômicos como exemplo. Esse plano, da sincronização de threads / processos, ao modelo de atores (nas seguintes partes). O artigo pode ser útil para um primeiro conhecido ou para atualizar seu conhecimento.
Por que ser capaz de fazer isso? Os transistores atingem seu tamanho mínimo, a lei de Moore baseia-se na limitação da velocidade da luz e, portanto, é observado crescimento em quantidade, mais transistores podem ser feitos. Ao mesmo tempo, a quantidade de dados está aumentando e os usuários esperam uma reação imediata dos sistemas. Em tal situação, a programação "normal", quando temos um thread em execução, não é mais eficaz. É necessário resolver de alguma forma o problema da execução simultânea ou competitiva. Além disso, esse problema existe em diferentes níveis: no nível dos fluxos, no nível dos processos, no nível das máquinas na rede (sistemas distribuídos). O .NET possui tecnologias testadas pelo tempo, de alta qualidade, para solucionar rápida e efetivamente esses problemas.
Desafio
Edsger Dijkstra colocou esse problema para seus alunos desde 1965. A redação estabelecida é essa. Há um número (geralmente cinco) de filósofos e tantos garfos. Eles estão sentados à mesa redonda, com garfos no meio. Os filósofos podem comer de seus pratos com comida sem fim, pensar ou esperar. Para comer o filósofo, você precisa pegar dois garfos (o último divide o garfo com o primeiro). Para tirar e colocar um garfo - duas ações separadas. Todos os filósofos estão calados. A tarefa é encontrar um algoritmo que todos pensem e fiquem cansados, mesmo após 54 anos.
Primeiro, vamos tentar resolver esse problema usando espaço compartilhado. Os garfos estão sobre a mesa e os filósofos os pegam quando estão e os colocam de volta. Há problemas com a sincronização, quando exatamente para tirar os plugues? O que fazer se não houver plug? e outros, mas primeiro, vamos lançar os filósofos.
Para iniciar threads, use o pool de threads através do método Task.Run :
var cancelTokenSource = new CancellationTokenSource(); Action<int> create = (i) => RunPhilosopher(i, cancelTokenSource.Token); for (int i = 0; i < philosophersAmount; i++) { int icopy = i;
Conjunto de threads criado para otimizar a criação e exclusão de threads. Esse pool tem uma fila de tarefas e o CLR cria ou exclui threads, dependendo do número dessas tarefas. Um pool para todos os AppDomains. Esse pool deve ser usado quase sempre, porque você não precisa se preocupar em criar, excluir segmentos, suas filas etc. É possível sem um pool, mas é necessário usar o Thread diretamente, é aconselhável nos casos em que você precise alterar a prioridade de um segmento, quando tivermos uma operação longa, em Primeiro plano de um segmento, etc.
E a classe System.Threading.Tasks.Task facilita o trabalho com esse pool de threads (ou mesmo sem ele). É uma operação assíncrona. Grosso modo, esse é o mesmo Thread , mas com todos os tipos de conveniências: a capacidade de iniciar tarefas após um bloco de outras tarefas, devolvê-las de funções, é conveniente interrompê-las e muito mais. etc. Eles são necessários para suportar construções assíncronas / aguardadas (padrão assíncrono baseado em tarefas, açúcar sintático para aguardar a operação de E / S). Vamos falar sobre isso novamente.
CancelationTokenSource é necessário aqui para que o próprio encadeamento possa ser encerrado pelo sinal do encadeamento de chamada.
Problemas de sincronização
Filósofos bloqueados
Ok, podemos criar threads, vamos tentar almoçar:
Aqui, primeiro tentamos pegar os garfos esquerdo e depois direito, e se funcionar, então comemos e os colocamos de volta. Tomar um garfo é atômico, ou seja, dois fluxos não podem receber um ao mesmo tempo (incorretamente: o primeiro lê que o plugue está livre, o segundo também, o primeiro leva, o segundo leva). Para fazer isso, Interlocked.CompareExchange , que deve ser implementado usando uma instrução de processador ( TSL , XCHG ), que bloqueia um pedaço de memória para leitura e gravação seqüencial atômica. E o SpinWait é equivalente a uma construção while(true) com apenas um pouco de "mágica" - o thread ocupa o processador ( Thread.SpinWait ), mas às vezes transfere o controle para outro thread ( Thread.Yeild ) ou adormece ( Thread.Sleep ).
Mas essa solução não funciona, porque os fluxos logo serão bloqueados (para mim em um segundo): todos os filósofos pegam o garfo esquerdo, mas não o direito. A matriz de garfos possui valores: 1 2 3 4 5.
Na figura, bloqueando threads (deadlock). Verde indica execução, vermelho indica sincronização e cinza indica suspensão. Os diamantes indicam a hora de início da tarefa.
A fome dos filósofos
Embora não seja necessário pensar em muita comida, você deve forçar alguém a desistir da filosofia. Vamos tentar simular a situação dos fluxos de jejum em nosso problema. A fome ocorre quando o fluxo funciona, mas sem trabalho significativo, em outras palavras, é o mesmo impasse, só que agora o fluxo não dorme, mas procura ativamente algo para comer, mas não há comida. Para evitar o bloqueio frequente, colocaremos o plugue de volta se não pudermos usar outro.
Nesse código, é importante que dois em cada quatro filósofos se esqueçam de colocar o garfo esquerdo. E acontece que eles comem mais comida, enquanto outros começam a passar fome, embora os fluxos tenham a mesma prioridade. Aqui eles realmente não passam fome, porque maus filósofos às vezes recolhem seus garfos. Acontece que os bons comem cerca de 5 vezes menos que os ruins. Portanto, um pequeno erro no código leva a uma queda no desempenho. Aqui vale a pena notar que uma situação rara é possível quando todos os filósofos tomam o garfo esquerdo, não há direito, eles colocam o esquerdo, esperam, tomam o esquerdo novamente, etc. Esta situação também é fome, mais como um impasse. Eu não pude repetir. Abaixo está uma foto de uma situação em que dois maus filósofos pegaram os garfos e dois bons filósofos estão passando fome.
Aqui você pode ver que os tópicos são ativados algumas vezes e tentam obter um recurso. Dois dos quatro núcleos não fazem nada (o gráfico verde na parte superior).
A morte do filósofo
Bem, outro problema que pode interromper o glorioso jantar dos filósofos é se um deles de repente morre com garfos nas mãos (e eles o enterram assim). Os vizinhos serão deixados sem almoço. Você pode NullReferenceException código de exemplo para esse caso, por exemplo, uma NullReferenceException lançada depois que o filósofo pegar os garfos. E, a propósito, a exceção não será processada e o código de chamada simplesmente não a capturará (para isso, AppDomain.CurrentDomain.UnhandledException , etc.). Portanto, os manipuladores de erro são necessários nos próprios threads e com a finalização correta.
Garçom
Bem, como resolvemos esse problema com impasses, fome e morte? Permitiremos que apenas um filósofo garfo, adicione exclusão mútua de fluxos para esse local. Como fazer isso? Suponha que um garçom esteja ao lado dos filósofos que dá permissão a um filósofo para pegar garfos. Como fazemos esse garçom e como os filósofos fazem perguntas interessantes.
A maneira mais simples é quando os filósofos simplesmente pedem constantemente ao garçom acesso aos garfos. I.e. agora os filósofos não esperam um plugue por perto, mas esperam ou perguntam a um garçom. Primeiro, usamos apenas o Espaço do Usuário para isso, pois não usamos interrupções para chamar nenhum procedimento do kernel (sobre eles abaixo).
Soluções de espaço do usuário
Aqui faremos o mesmo que costumávamos fazer com um garfo e dois filósofos, giraríamos em um ciclo e esperamos. Mas agora serão todos os filósofos e como se apenas um garfo, ou seja, podemos dizer que haverá apenas aquele filósofo que pegou esse "garfo de ouro" do garçom. Para isso, usamos o SpinLock.
private static SpinLock spinLock = new SpinLock();
SpinLock é um bloqueador, com, grosso modo, o mesmo while(true) { if (!lock) break; } while(true) { if (!lock) break; } , mas com ainda mais "mágica" do que no SpinWait (que é usado lá). Agora ele sabe contar os que estão esperando, fazê-los dormir um pouco e muito mais. etc. Em geral, faz todo o possível para otimizar. Mas devemos lembrar que esse ainda é o mesmo ciclo ativo que consome recursos do processador e mantém um encadeamento que pode levar à fome se um dos filósofos se tornar uma prioridade sobre os outros, mas não tiver um garfo de ouro (problema de inversão de prioridade). Portanto, nós o usamos apenas para alterações muito curtas na memória compartilhada, sem chamadas de terceiros, bloqueios aninhados, etc. surpresas.
Figura para o SpinLock . As correntes estão constantemente "lutando" pelo garfo de ouro. Falhas acontecem - na figura, a área selecionada. Os núcleos não são totalmente usados: apenas cerca de 2/3 desses quatro threads.
Outra solução aqui seria usar apenas Interlocked.CompareExchange com a mesma expectativa ativa, conforme mostrado no código acima (em filósofos famintos), mas isso, como já mencionado, teoricamente poderia levar ao bloqueio.
Sobre o Interlocked , vale a pena dizer que não existem apenas o CompareExchange , mas também outros métodos para leitura e gravação atômica. E, repetindo as alterações caso outro encadeamento consiga fazer suas alterações (leia 1, leia 2, escreva 2, escreva 1 é ruim), ele pode ser usado para alterações complexas de um valor (padrão Interlocked Anything).
Soluções em modo kernel
Para evitar a perda de recursos em um loop, vamos ver como você pode bloquear um fluxo. Em outras palavras, continuando nosso exemplo, veremos como o garçom coloca o filósofo para dormir e o acorda somente quando necessário. Primeiro, vamos ver como fazer isso no modo kernel do sistema operacional. Todas as estruturas existentes costumam ser mais lentas do que aquelas no espaço do usuário. Várias vezes mais lento, por exemplo, o AutoResetEvent pode ser 53 vezes mais lento que o SpinLock [Richter]. Porém, com a ajuda deles, você pode sincronizar processos por todo o sistema, gerenciados ou não.
A principal construção aqui é o semáforo proposto por Dijkstroy mais de meio século atrás. Um semáforo é, em termos simples, um número inteiro positivo controlado por um sistema e duas operações nele - aumentam e diminuem. Se a redução não funcionar, zero, o encadeamento de chamada será bloqueado. Quando o número é aumentado por algum outro encadeamento / processo ativo, os encadeamentos são ignorados e o semáforo diminui novamente pelo número de passados. Você pode imaginar trens em um gargalo com um semáforo. O .NET oferece vários designs com recursos semelhantes: AutoResetEvent , ManualResetEvent , Mutex e o próprio Semaphore . Usaremos AutoResetEvent , essa é a mais simples dessas construções: apenas dois valores são 0 e 1 (falso, verdadeiro). Seu método WaitOne() bloqueia o segmento de chamada se o valor for 0 e, se 1, reduz para 0 e ignora. E o método Set() aumenta para 1 e pula uma espera, que novamente diminui para 0. Ele age como uma catraca no metrô.
Vamos complicar a solução e usaremos a trava para cada filósofo, e não para todos de uma vez. I.e. agora pode haver vários filósofos ao mesmo tempo, e não um. Mais uma vez, bloqueamos o acesso à mesa para pegar garfos corretamente, evitando corridas (condições da corrida).
Para entender o que está acontecendo aqui, considere o caso em que o filósofo falhou em pegar os garfos, então suas ações serão assim. Ele está esperando pelo acesso à mesa. Tendo recebido, ele tenta pegar os garfos. Não deu certo. Ele dá acesso à mesa (exclusão mútua). E passa seu "torniquete" ( AutoResetEvent ) (a princípio eles estão abertos). Entra no ciclo novamente, porque ele não tem garfos. Tenta pegá-los e para na catraca dele. Um vizinho mais afortunado à direita ou à esquerda, depois de terminar de comer, destranca nosso filósofo, "abrindo sua catraca". Nosso filósofo passa (e ele fecha atrás) pela segunda vez. Tenta pela terceira vez pegar os garfos. Boa sorte E passa a catraca para jantar.
Quando há erros aleatórios nesse código (eles sempre existem), por exemplo, um vizinho é especificado incorretamente ou o mesmo objeto AutoResetEvent é AutoResetEvent para todos ( Enumerable.Repeat ), então os filósofos aguardam os desenvolvedores, porque encontrar erros nesse código é uma tarefa bastante difícil. Outro problema com esta solução é que ela não garante que nenhum filósofo passe fome.
Soluções híbridas
Examinamos duas abordagens para sincronização quando permanecemos no modo de usuário e giramos em um loop e quando bloqueamos um thread no kernel. O primeiro método é bom para bloqueios curtos, o segundo para os longos. Freqüentemente, você primeiro precisa esperar brevemente que uma variável seja alterada no loop e depois bloquear o thread quando a espera for longa. Essa abordagem é implementada no chamado projetos híbridos. Existem as mesmas construções que eram para o modo kernel, mas agora com um loop no modo usuário: SemaphorSlim , ManualResetEventSlim , etc. A construção mais popular aqui é o Monitor , porque C # tem uma sintaxe de lock conhecida. Monitor é o mesmo semáforo com um valor máximo de 1 (mutex), mas com suporte para espera em um loop, recursão, padrão de variável de condição (sobre isso abaixo), etc. Vamos olhar para uma solução com ele.
Aqui novamente trancamos a mesa inteira para acessar os garfos, mas agora desbloqueamos todos os fluxos de uma só vez, e não os vizinhos quando alguém termina de comer. I.e. primeiro, alguém come e bloqueia os vizinhos, e quando ele termina, mas quer comer imediatamente novamente, ele entra na fechadura e acorda os vizinhos, porque o tempo de espera é mais curto.
Portanto, evitamos os impasses e a fome de algum filósofo. Usamos um loop para uma breve espera e bloqueamos o fluxo por um longo. Desbloquear tudo de uma vez funciona mais lentamente do que se apenas o vizinho fosse desbloqueado, como na solução com AutoResetEvent , mas a diferença não deve ser grande, porque os threads devem permanecer no modo de usuário primeiro.
O lock sintaxe tem surpresas desagradáveis. Eles recomendam o uso do Monitor diretamente [Richter] [Eric Lippert]. Uma delas é que o lock sempre sai do Monitor , mesmo se houver uma exceção, e outro segmento pode alterar o estado da memória compartilhada. Nesses casos, geralmente é melhor ir para o impasse ou concluir de alguma forma com segurança o programa. Outra surpresa é que o Monitor usa blocos de sincronização ( SyncBlock ), que estão em todos os objetos. Portanto, se você selecionar o objeto errado, poderá obter facilmente um impasse (por exemplo, se você bloquear a cadeia interna). Sempre usamos um objeto oculto para isso.
O padrão Variável de condição permite implementar de forma mais concisa a expectativa de uma condição complexa. No .NET, ele está incompleto, na minha opinião, porque em teoria, deve haver várias filas em várias variáveis (como em Posix Threads), e não em um bloqueio. Então alguém poderia fazê-los para todos os filósofos. Mas, mesmo nesta forma, permite reduzir o código.
Muitos filósofos ou async / await
Ok, agora podemos efetivamente bloquear threads. Mas, e se tivermos muitos filósofos? 100? 10000? Por exemplo, recebemos 100.000 solicitações para um servidor web. A criação de um fluxo para cada solicitação será uma sobrecarga, porque tantos threads não serão executados em paralelo. Somente quantos núcleos lógicos serão executados (eu tenho 4). E todos os outros simplesmente usarão recursos. Uma solução para esse problema é o padrão assíncrono / espera. Sua idéia é que uma função não mantenha um fluxo, se você precisar esperar que continue. E quando ela faz isso, algo acontece, ela retoma sua execução (mas não necessariamente no mesmo encadeamento!). No nosso caso, esperaremos pelo plugue.
SemaphoreSlim tem um método WaitAsync() para isso. Aqui está uma implementação usando esse padrão.
async / await , Task . , , Task. , , . , , , , . . async / await .
. 100 4 , 8 . Monitor 4 , . 4 2. async / await 100, 6.8 . , 6 . Monitor .
Conclusão
, .NET . , , , . . , , , TPL Dataflow, Reactive , Software Transaction .
Fontes