O que vários encadeamentos podem fazer que um único encadeamento não possa? [fechadas]

Em primeiro lugar, os threads não podem acelerar a execução do código. Eles não fazem o computador rodar mais rápido. Tudo o que eles podem fazer é aumentar a eficiência do computador usando o tempo que seria desperdiçado. Em certos tipos de processamento, essa otimização pode aumentar a eficiência e diminuir o tempo de execução.

A resposta simples é sim. Você pode escrever qualquer código para ser executado em um único segmento. Prova: Um sistema de processador único pode executar apenas instruções linearmente. Ter várias linhas de execução é feito pelas interrupções de processamento do sistema operacional, salvando o estado do thread atual e iniciando outro.

A resposta complexa é ... mais complexa! A razão pela qual os programas multithread podem ser mais eficientes que os lineares é devido a um "problema" de hardware. A CPU pode executar cálculos mais rapidamente do que a memória e o armazenamento de dados em disco rígido. Assim, uma instrução "add", por exemplo, executa muito mais rapidamente que uma "busca". Caches e busca de instrução de programa dedicada (não tenho certeza do termo exato aqui) podem combater isso até certo ponto, mas a questão da velocidade permanece.

Threading é uma forma de combater essa incompatibilidade usando a CPU para instruções de limite de CPU enquanto as instruções de IO estão sendo concluídas. Um plano de execução de encadeamento típico provavelmente seria: Busque dados, processe dados, grave dados. Suponha que buscar e escrever demore 3 ciclos e o processamento leve um, para fins ilustrativos. Você pode ver que enquanto o computador está lendo ou escrevendo, ele está fazendo nada por 2 ciclos cada um? Claramente está sendo preguiçoso, e precisamos quebrar nosso chicote de otimização!

Podemos reescrever o processo usando o threading para usar esse tempo perdido:

1. # 1 busca
2. sem operação
3. # 2 buscar
4. # 1 pronto, processe-o
5. escreva # 1
6. # 1 busca
7. # 2 pronto, processe
8. escreva # 2
9. buscar # 2

E assim por diante. Obviamente, este é um exemplo um pouco inventado, mas você pode ver como essa técnica pode utilizar o tempo que seria gasto esperando por IO.

Observe que a segmentação conforme mostrado acima só pode aumentar a eficiência em processos altamente vinculados de E / S. Se um programa estiver calculando principalmente as coisas, não haverá muitos "buracos" nos quais poderíamos trabalhar mais. Além disso, há uma sobrecarga de várias instruções ao alternar entre threads. Se você executar muitos threads, a CPU passará a maior parte do tempo trocando e não trabalhando muito no problema. Isso é chamado de surra .

Tudo isso é bom para um processador de núcleo único, mas a maioria dos processadores modernos tem dois ou mais núcleos. Os threads ainda servem ao mesmo propósito - para maximizar o uso da CPU, mas desta vez temos a capacidade de executar duas instruções separadas ao mesmo tempo. Isso pode diminuir o tempo de execução por um fator de quantos núcleos estão disponíveis, porque o computador é realmente multitarefa, não comutação de contexto.

Com vários núcleos, os encadeamentos fornecem um método de dividir o trabalho entre os dois núcleos. O acima ainda se aplica para cada núcleo individual; Um programa que executa uma eficiência máxima com dois encadeamentos em um núcleo provavelmente executará com eficiência máxima com cerca de quatro encadeamentos em dois núcleos. (A eficiência é medida aqui por execuções mínimas de instrução NOP).

Os problemas com a execução de threads em vários núcleos (em oposição a um único núcleo) geralmente são resolvidos pelo hardware. A CPU terá certeza de que ela bloqueia os locais de memória apropriados antes de ler / gravar nela. (Eu li que ele usa um sinalizador especial na memória para isso, mas isso pode ser feito de várias maneiras). Como um programador com linguagens de alto nível, você não precisa se preocupar com nada mais em dois núcleos como você teria que com um.

TL; DR: Os segmentos podem dividir o trabalho para permitir que o computador processe várias tarefas de forma assíncrona. Isso permite que o computador seja executado com eficiência máxima, utilizando todo o tempo de processamento disponível, em vez de bloquear quando um processo está aguardando um recurso.

What can multiple threads do that a single thread cannot?

Nada.

Esboço de prova simples:

• [Conjectura de Turing para a Igreja] ⇒ Tudo o que pode ser calculado pode ser calculado por uma Máquina Universal de Turing.
• Uma máquina universal de Turing é de encadeamento único.
• Portanto, tudo o que pode ser calculado pode ser calculado por um único thread.

Note, no entanto, que há uma grande suposição escondida lá: a linguagem usada dentro do segmento único é Turing-complete.

Então, a questão mais interessante seria: "A adição de apenas multi-threading a uma linguagem não Turing-completa pode torná-lo completo?" E eu acredito, a resposta é "sim".

Vamos usar o Total Functional Languages. [Para aqueles que não estão familiarizados: assim como a programação funcional está programando com funções, a programação totalmente funcional está programando com funções totais.]

O Total Functional Languages obviamente não é Turing-complete: você não pode escrever um loop infinito em um TFPL (na verdade, isso é basicamente a definição de "total"), mas você pode em uma máquina de Turing, existe pelo menos um programa que não pode ser escrito em um TFPL, mas pode em um UTM, portanto, os TFPLs são menos computacionalmente poderosos que os UTMs.

No entanto, assim que você adicionar threading a um TFPL, você obtém loops infinitos: faça cada iteração do loop em um novo thread. Cada thread individual sempre retorna um resultado, portanto, é Total, mas cada thread também gera um thread new que executa a iteração next , ad infinitum.

Eu acho que esta linguagem seria Turing-completa.

No mínimo, responde à pergunta original:

What can multiple threads do that a single thread cannot?

Se você tem uma linguagem que não pode fazer loops infinitos, o então multi-threading permite fazer loops infinitos.

Note, claro, que gerar um encadeamento é um efeito colateral e, portanto, nossa linguagem estendida não é apenas não mais Total, nem é mais Funcional.

Em teoria, tudo que um programa multithread faz pode ser feito com um programa single-threaded também, apenas mais lento.

Na prática, a diferença de velocidade pode ser tão grande que não há como usar um programa single-threaded para a tarefa. Por exemplo. Se você tiver uma tarefa de processamento de dados em lote em execução todas as noites e levar mais de 24 horas para concluir em um único thread, não terá outra opção além de torná-la multithread. (Na prática, o limite é provavelmente ainda menor: muitas vezes essas tarefas de atualização devem ser concluídas pela manhã, antes que os usuários comecem a usar o sistema novamente. Além disso, outras tarefas podem depender deles, que também devem terminar durante a mesma noite. o tempo de execução disponível pode ser tão baixo quanto algumas horas / minutos.)

Fazer o trabalho de computação em vários segmentos é uma forma de processamento distribuído; você está distribuindo o trabalho por vários threads. Outro exemplo de processamento distribuído (usando vários computadores em vez de múltiplos threads) é o protetor de tela SETI: calculando que muitos dados de medição em um único processador levariam muito tempo e os pesquisadores prefeririam ver os resultados antes da aposentadoria ;-) No entanto, eles não têm orçamento para alugar um supercomputador por tanto tempo, então distribuem o trabalho em milhões de PCs domésticos, para torná-lo barato.

Although threads seem to be a small step from sequential computation, in fact, they represent a huge step. They discard the most essential and appealing properties of sequential computation: understandability, predictability, and determinism. Threads, as a model of computation, are wildly nondeterministic, and the job of the programmer becomes one of pruning that nondeterminism.

-- The Problem with Threads (www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf).

Embora existam algumas vantagens de desempenho que podem ser obtidas com o uso de encadeamentos em que você pode distribuir o trabalho entre vários núcleos, eles geralmente têm um ótimo preço.

Uma das desvantagens de usar encadeamentos não mencionados aqui é a perda de compartimentalização de recursos obtida com espaços de processo de encadeamento único. Por exemplo, digamos que você se depara com o caso de um segfault. Em alguns casos, é possível recuperar-se disso em uma aplicação de processo múltiplo em que você simplesmente deixa a criança defeituosa morrer e reaparecer uma nova. Esse é o caso do backend de pré-inicialização do Apache. Quando uma instância do httpd sobe de barriga, o pior caso é que a solicitação HTTP específica pode ser descartada para esse processo, mas o Apache gera um novo filho e, muitas vezes, a solicitação se for apenas reenviada e atendida. O resultado final é que o Apache como um todo não é retirado com o thread defeituoso.

Outra consideração neste cenário é o vazamento de memória. Existem alguns casos em que você pode facilmente lidar com um travamento de thread (no UNIX, a recuperação de alguns sinais específicos - mesmo o segfault / fpviolation - é possível), mas mesmo nesse caso, você pode ter vazado toda a memória alocada por esse thread (malloc, novo, etc.) Então, enquanto você processa pode viver, ele vaza mais e mais memória ao longo do tempo com cada falha / recuperação. Novamente, existem maneiras de minimizar isso, como o uso de pools de memória pelo Apache. Mas isso ainda não protege contra a memória que pode ter sido alocada por bibliotecas de terceiros que o thread pode estar usando.

E, como algumas pessoas apontaram, entender as primitivas de sincronização talvez seja a coisa mais difícil de acertar. Esse problema por si só - apenas acertar a lógica geral para todo o seu código - pode ser uma enorme dor de cabeça. Deadlocks misteriosos são propensos a acontecer nos momentos mais estranhos, e às vezes nem mesmo até o seu programa estar em execução na produção, o que torna a depuração ainda mais difícil. Adicione a isso o fato de que os primitivos de sincronização variam muito com a plataforma (Windows vs. POSIX), e a depuração pode ser mais difícil, assim como a possibilidade de condições de corrida a qualquer momento (inicialização / inicialização, tempo de execução e desligamento), programar com threads realmente tem pouca piedade para iniciantes. E mesmo para os especialistas, ainda há pouca piedade só porque o conhecimento do encadeamento em si não minimiza a complexidade em geral. Cada linha de código encadeado, por vezes, parece exponencialmente composto a complexidade geral do programa, bem como aumentar a probabilidade de um impasse oculto ou condição de corrida estranha a qualquer momento. Também pode ser muito difícil escrever casos de teste para descobrir essas coisas.

É por isso que alguns projetos como o Apache e o PostgreSQL são, na maioria das vezes, baseados em processos. O PostgreSQL executa cada thread de backend em um processo separado. É claro que isso ainda não alivia o problema das condições de sincronização e corrida, mas adiciona um pouco de proteção e de certa forma simplifica as coisas.

Vários processos, cada um executando um único thread de execução, pode ser muito melhor do que vários threads em execução em um único processo. E com o advento de grande parte do novo código peer-to-peer, como AMQP (RabbitMQ, Qpid, etc.) e ZeroMQ, é muito mais fácil dividir threads em diferentes espaços de processo e até mesmo máquinas e redes, simplificando bastante as coisas. Mas ainda assim, não é uma bala de prata. Ainda há complexidade para lidar. Você apenas move algumas de suas variáveis do espaço de processo para a rede.

O resultado é que a decisão de entrar no domínio dos tópicos não é leve. Uma vez que você pisa nesse território, quase instantaneamente tudo se torna mais complexo e novas raças de problemas entram em sua vida. Pode ser divertido e legal, mas é como a energia nuclear - quando as coisas dão errado, elas podem ir mal e rapidamente. Lembro-me de ter participado de uma aula de treinamento de criticalidade há muitos anos e eles mostraram fotos de alguns cientistas de Los Alamos que brincavam com o plutônio nos laboratórios da Segunda Guerra Mundial. Muitos tomaram poucas ou nenhumas precauções contra o evento de uma exposição, e num piscar de olhos - num único clarão brilhante e indolor, tudo estaria acabado para eles. Dias depois eles estavam mortos. Richard Feynman mais tarde se referiu a isso como " fazendo cócegas na cauda do dragão ." Isso é o tipo de brincadeira com tópicos pode ser como (pelo menos para mim de qualquer maneira). Parece bastante inofensivo a princípio, e no momento em que você morde, você está coçando a cabeça com a rapidez com que as coisas azedaram. Mas pelo menos threads não te matam.

Primeiro, um único aplicativo encadeado nunca tirará proveito de uma CPU multi-core ou hyper-threading. Mas, mesmo em um único núcleo, um único thread de processamento multi-threading tem vantagens.

Considere a alternativa e se isso faz você feliz. Suponha que você tenha várias tarefas que precisam ser executadas simultaneamente. Por exemplo, você tem que manter a comunicação com dois sistemas diferentes. Como você faz isso sem multi-threading? Você provavelmente criaria seu próprio agendador e deixaria que ele chamasse as diferentes tarefas que precisam ser executadas. Isso significa que você precisa dividir suas tarefas em partes. Você provavelmente precisará encontrar algumas restrições em tempo real para garantir que suas peças não ocupem muito tempo. Caso contrário, o temporizador expirará em outras tarefas. Isso dificulta a divisão de tarefas. Quanto mais tarefas você precisar gerenciar, mais divisão precisará fazer e mais complexo será o seu agendador para atender a todas as restrições.

Quando você tem vários segmentos, a vida pode se tornar mais fácil. Um agendador preventivo pode interromper um thread a qualquer momento, manter seu estado e reinicializar outro. Ele será reiniciado quando o seu segmento chegar a sua vez. Vantagens: a complexidade de escrever um agendador já foi feita para você e você não precisa dividir suas tarefas. Além disso, o agendador é capaz de gerenciar processos / threads dos quais você nem mesmo está ciente. E também, quando um encadeamento não precisa fazer nada (ele está esperando por algum evento), ele não ocupará ciclos de CPU. Isso não é tão fácil de realizar quando você está criando seu agendador single-threaded down. (colocar alguma coisa para dormir não é tão difícil, mas como isso acorda?)

A desvantagem do desenvolvimento multi-thread é que você precisa entender sobre problemas de simultaneidade, estratégias de bloqueio e assim por diante. O desenvolvimento de código multi-thread sem erros pode ser bastante difícil. E a depuração pode ser ainda mais difícil.

is there something that exists that can only be accomplished by using multiple threads?

Sim. Você não pode executar código em várias CPUs ou núcleos de CPU com um único thread.

Sem várias CPUs / núcleos, os threads ainda podem simplificar o código que é executado conceitualmente em paralelo, como a manipulação de clientes em um servidor - mas você pode fazer a mesma coisa sem threads.

Tópicos não são apenas sobre velocidade, mas sobre simultaneidade.

Se você não tiver um aplicativo em lote como @Peter sugerido, mas em vez disso, um kit de ferramentas GUI como o WPF como você poderia interagir com os usuários e a lógica de negócios com apenas um thread?

Além disso, suponha que você esteja criando um servidor da Web. Como você serviria mais de um usuário simultaneamente com apenas um thread (supondo que não haja outros processos)?

Existem muitos cenários em que apenas um thread simples não é suficiente. É por isso que avanços recentes como o processador Intel MIC com mais de 50 núcleos e centenas de threads estão ocorrendo.

Sim, programação paralela e concorrente é difícil. Mas necessário.

O Multi-Threading pode permitir que a interface GUI ainda seja responsiva durante operações de processamento longas. Sem multi-threading, o usuário ficaria parado assistindo a um formulário bloqueado enquanto um longo processo está sendo executado.

O código multiencadeado pode travar a lógica do programa e acessar dados obsoletos de maneiras que segmentos únicos não podem.

Threads podem pegar um bug obscuro de algo que um programador médio pode depurar e movê-lo para o reino onde as histórias são contadas sobre a sorte necessária para pegar o mesmo bug com a calça abaixada quando um programador de alerta estava procurando no momento certo.

aplicativos que lidam com o bloqueio de E / S que também precisam permanecer responsivos a outras entradas (a GUI ou outras conexões) não podem ser transformados em singlethreaded

a adição de métodos de verificação na biblioteca IO para ver o quanto pode ser lido sem bloquear pode ajudar, mas muitas bibliotecas não dão nenhuma garantia total sobre isso

Muitas boas respostas, mas não tenho certeza de qualquer frase, assim como eu faria - Talvez isso ofereça uma maneira diferente de analisá-la:

Tópicos são apenas uma simplificação de programação como Objetos ou Atores ou para loops (Sim, qualquer coisa que você implementa com loops que você pode implementar com / goto).

Sem threads, você simplesmente implementa um mecanismo de estado. Eu tive que fazer isso muitas vezes (a primeira vez que fiz isso eu nunca tinha ouvido falar disso - apenas fiz uma grande instrução switch controlada por uma variável "State"). As máquinas de estado ainda são bastante comuns, mas podem ser irritantes. Com linhas, uma grande parte do clichê desaparece.

Eles também facilitam a quebra de sua execução em tempo de execução em partes amigáveis com multi-CPU (assim como os atores, eu acredito).

O Java fornece encadeamentos "verdes" em sistemas nos quais o sistema operacional não oferece suporte a nenhum encadeamento. Neste caso, é mais fácil ver que eles são claramente nada mais do que uma abstração de programação.

Sistemas operacionais usam o conceito de fatiamento de tempo, em que cada segmento chega à hora de executar e, em seguida, fica com preempção. Uma abordagem como essa pode substituir o threading como está agora, mas escrever seus próprios planejadores em cada aplicativo seria um exagero. Além disso, você teria que trabalhar com dispositivos de E / S e assim por diante. E exigiria algum suporte do lado do hardware, para que você pudesse disparar interrupções para executar seu agendador. Basicamente, você estaria escrevendo um novo sistema operacional todas as vezes.

No geral, o encadeamento pode melhorar o desempenho nos casos em que os encadeamentos aguardam E / S ou estão em repouso. Ele também permite criar interfaces que sejam responsivas e permitir a interrupção de processos enquanto você executa tarefas longas. E também, o encadeamento aprimora as coisas em CPUs multicore verdadeiras.

Primeiro, os threads podem fazer duas ou mais coisas ao mesmo tempo (se você tiver mais de um núcleo). Embora você também possa fazer isso com vários processos, algumas tarefas simplesmente não são distribuídas em vários processos muito bem.

Além disso, algumas tarefas têm espaços que você não pode evitar facilmente. Por exemplo, é difícil ler dados de um arquivo no disco e também fazer com que o processo faça outra coisa ao mesmo tempo. Se sua tarefa necessariamente exigir muitos dados de leitura do disco, seu processo gastará muito tempo aguardando o disco, não importa o que você faça.

Em segundo lugar, os segmentos podem permitir que você evite ter que otimizar grandes quantidades de seu código que não sejam essenciais para o desempenho. Se você tiver apenas um único thread, cada parte do código é crítica para o desempenho. Se bloquear, você está afundado - nenhuma tarefa que seria executada por esse processo pode fazer avançar o progresso. Com os encadeamentos, um bloco afetará apenas esse encadeamento, e outros encadeamentos poderão surgir e funcionar em tarefas que precisam ser executadas por esse processo.

Um bom exemplo é o código de tratamento de erros executado com pouca frequência. Digamos que uma tarefa encontre um erro muito pouco freqüente e o código para lidar com esse erro precise ser exibido na memória. Se o disco estiver ocupado e o processo tiver apenas um único encadeamento, nenhum progresso de encaminhamento poderá ser feito até que o código para manipular esse erro possa ser carregado na memória. Isso pode causar uma resposta em rajada.

Outro exemplo é se você raramente precisa fazer uma pesquisa de banco de dados. Se você esperar que o banco de dados responda, seu código sofrerá um grande atraso. Mas você não quer se dar ao trabalho de tornar todo esse código assíncrono, porque é tão raro precisar fazer essas pesquisas. Com um fio para fazer este trabalho, você obtém o melhor dos dois mundos. Um thread para fazer este trabalho faz com que seja um desempenho não crítico, como deveria ser.