Como os pipelines limitam o uso de memória?

36

Brian Kernighan explica neste vídeo a atração inicial do Bell Labs por pequenos idiomas / programas baseados em limitações de memória

Uma máquina grande seria de 64 k bytes - K, não M ou G - e isso significava que qualquer programa individual não podia ser muito grande; portanto, havia uma tendência natural de escrever pequenos programas e, em seguida, o mecanismo de pipe, basicamente, o redirecionamento de saída de entrada tornou possível vincular um programa a outro.

Mas não entendo como isso pode limitar o uso da memória, considerando o fato de que os dados precisam ser armazenados na RAM para serem transmitidos entre os programas.

Da Wikipedia :

Na maioria dos sistemas tipo Unix, todos os processos de um pipeline são iniciados ao mesmo tempo [grifo meu], com seus fluxos conectados adequadamente e gerenciados pelo planejador, juntamente com todos os outros processos em execução na máquina. Um aspecto importante disso, diferenciando os tubos Unix de outras implementações de tubos, é o conceito de buffer: por exemplo, um programa de envio pode produzir 5000 bytes por segundo, e um programa de recebimento pode aceitar apenas 100 bytes por segundo, mas não dados são perdidos. Em vez disso, a saída do programa de envio é mantida no buffer. Quando o programa receptor estiver pronto para ler os dados, o próximo programa no pipeline lerá a partir do buffer. No Linux, o tamanho do buffer é 65536 bytes (64 KB). Um filtro de terceiros de código aberto chamado bfr está disponível para fornecer buffers maiores, se necessário.

Isso me confunde ainda mais, pois isso derrota completamente o objetivo de pequenos programas (embora eles sejam modulares até uma certa escala).

A única coisa que consigo pensar em uma solução para minha primeira pergunta (as limitações de memória são problemáticas dependendo dos dados de tamanho) seria que grandes conjuntos de dados simplesmente não eram computados na época e os pipelines de problemas reais deveriam solucionar o problema. quantidade de memória requerida pelos próprios programas. Mas, dado o texto em negrito na citação da Wikipedia, até isso me confunde: como um programa não é implementado por vez.

Tudo isso faria muito sentido se os arquivos temporários fossem usados, mas entendo que os pipes não gravam no disco (a menos que a troca seja usada).

Exemplo:

sed 'simplesubstitution' file | sort | uniq > file2

Está claro para mim que sedestá lendo o arquivo e cuspindo linha por linha. Mas sort, como BK afirma no vídeo vinculado, é um ponto final, então todos os dados precisam ser lidos na memória (ou não?), E depois são passados ​​para o uniqque (na minha opinião) seria um programa em linha de cada vez. Mas entre o primeiro e o segundo canal, todos os dados precisam estar na memória, não?

malan
fonte
1
unless swap is usedswap é sempre utilizado quando não há memória RAM suficiente
edc65

Respostas:

44

Os dados não precisam ser armazenados na RAM. Tubos bloqueiam seus escritores se os leitores não estiverem lá ou não puderem acompanhar; no Linux (e na maioria das outras implementações, imagino), existem alguns tipos de buffer, mas isso não é necessário. Como mencionado por mtraceur e JdeBP (veja a resposta deste), versões anteriores dos pipes em buffer do Unix para o disco, e foi assim que eles ajudaram a limitar o uso da memória: um pipeline de processamento poderia ser dividido em pequenos programas, cada um dos quais processaria alguns dados, dentro dos limites dos buffers de disco. Pequenos programas consomem menos memória e o uso de pipes significava que o processamento poderia ser serializado: o primeiro programa seria executado, preencheria seu buffer de saída, seria suspenso; o segundo programa seria agendado, processaria o buffer, etc. Sistemas modernos são pedidos de magnitude maior que os primeiros sistemas Unix e pode executar muitos pipes em paralelo; mas para grandes quantidades de dados você ainda veria um efeito semelhante (e variantes desse tipo de técnica são usadas para o processamento de "big data").

No seu exemplo,

sed 'simplesubstitution' file | sort | uniq > file2

sedlê os dados fileconforme necessário e os escreve enquanto sortestiver pronto para lê-los; se sortnão estiver pronto, os blocos de gravação. Os dados realmente ficam na memória eventualmente, mas isso é específico sorte sortestá preparado para lidar com qualquer problema (ele usará arquivos temporários e a quantidade de dados para classificar é muito grande).

Você pode ver o comportamento de bloqueio executando

strace seq 1000000 -1 1 | (sleep 120; sort -n)

Isso produz uma quantidade razoável de dados e os direciona para um processo que não está pronto para ler nada nos primeiros dois minutos. Você verá várias writeoperações passarem, mas muito rapidamente seqparará e esperará os dois minutos decorridos, bloqueados pelo kernel (a writechamada do sistema aguarda).

Stephen Kitt
fonte
13
Essa resposta pode se beneficiar da explicação adicional de por que a divisão de programas em muitos pequenos economiza o uso de memória: Um programa precisava ser capaz de caber na memória para executar, mas apenas o programa em execução no momento . Todos os outros programas foram trocados para o disco no início do Unix, com apenas um programa trocado na RAM real de cada vez. Portanto, a CPU executava um programa, que gravava em um canal (que na época estava em disco ), trocava esse programa e aquele que lia do canal. Maneira elegante de transformar uma linha de montagem logicamente paralela em execução serial incremental.
Mtraceur
6
@malan: Vários processos podem ser iniciados e podem estar em um estado executável ao mesmo tempo. Porém, no máximo, um processo pode estar sendo executado em cada CPU física a qualquer momento, e é tarefa do agendador de processos do kernel alocar "fatias" de tempo da CPU para cada processo executável. Nos sistemas modernos, um processo que pode ser executado, mas não está agendado atualmente, uma divisão do tempo da CPU geralmente permanece residente na memória enquanto aguarda sua próxima fatia, mas o kernel tem permissão para paginar a memória de qualquer processo em disco e voltar à memória novamente como acha conveniente. (Handwaving alguns detalhes aqui.)
Daniel Pryden
5
Os processos em ambos os lados de um tubo podem se comportar efetivamente como co-rotinas: um lado grava até preencher o buffer e os blocos de gravação; nesse ponto, o processo não pode fazer nada com o resto de sua divisão temporal e entra em um Modo de espera de E / S. Em seguida, o sistema operacional fornece o restante da divisão do tempo (ou outra divisão do tempo futura) para o lado da leitura, que lê até que não haja mais nada no buffer e nos próximos blocos de leitura. Nesse momento, o processo do leitor não pode fazer nada com o restante do tempo. sua divisão do tempo e retorna ao sistema operacional. Os dados passam pelo canal, um buffer de cada vez.
Daniel Pryden
6
@malan Os programas são iniciados "ao mesmo tempo" conceitualmente em todos os sistemas Unix, apenas em sistemas modernos de multiprocessadores com memória RAM suficiente para mantê-los, o que significa que eles estão literalmente todos na memória RAM ao mesmo tempo, enquanto em um sistema que pode mantêm todos na RAM ao mesmo tempo, alguns são trocados para o disco. Observe também que "memória" em muitos contextos significa memória virtual, que é a soma do espaço RAM e do espaço de troca no disco. A Wikipedia está se concentrando mais no conceito do que nos detalhes da implementação, principalmente porque a idade do Unix é menos relevante agora.
Mtraceur
2
@malan Além disso, a contradição que você está vendo vem dos dois significados diferentes de "memória" (RAM vs RAM + swap). Eu estava falando apenas de RAM de hardware e, nesse contexto, apenas o código atualmente sendo executado pela CPU precisa caber na RAM (que foi o que estava afetando as decisões sobre as quais Kernighan está falando), enquanto no contexto de todos os programas sendo executados logicamente pelo sistema operacional em um determinado momento (no nível abstrato fornecido em cima da fatia do tempo), um programa só precisa caber em toda a memória virtual disponível para o sistema operacional, o que inclui espaço de troca no disco.
mtraceur
34

Mas não entendo como isso pode limitar o uso da memória, considerando o fato de que os dados precisam ser armazenados na RAM para serem transmitidos entre os programas.

Este é o seu erro fundamental. As versões anteriores do Unix não mantinham dados de pipe na RAM. Eles os armazenaram em disco. Pipes tinham i-nós; em um dispositivo de disco indicado como dispositivo de tubo . O administrador do sistema executou um programa chamado /etc/configpara especificar (entre outras coisas) qual volume em que disco era o dispositivo de pipe, qual volume era o dispositivo raiz e qual o dispositivo de despejo .

A quantidade de dados pendentes foi restringida pelo fato de que apenas os blocos diretos do nó i no disco foram usados ​​para armazenamento. Esse mecanismo tornou o código mais simples, porque o mesmo algoritmo foi empregado para a leitura de um canal e para a leitura de um arquivo regular, com alguns ajustes causados ​​pelo fato de que os canais não são procuráveis ​​e o buffer é circular.

Esse mecanismo foi substituído por outros no meio até o final dos anos 80. O SCO XENIX ganhou o "Sistema de tubulação de alto desempenho", que substituiu os nós i por buffers internos. O 4BSD transformou tubos sem nome em pares de soquetes. A AT&T reimplementou os tubos usando o mecanismo STREAMS.

E, é claro, o sortprograma executou um tipo interno limitado de blocos de entrada de 32KiB (ou qualquer quantidade menor de memória que ele pudesse alocar se 32KiB não estivesse disponível), gravando os resultados classificados em stmX??arquivos intermediários nos /usr/tmp/quais ele se mesclava externamente para fornecer o resultado final. saída.

Leitura adicional

  • Steve D. Pate (1996). "Comunicação entre processos". Internos do UNIX: Uma Abordagem Prática . Addison-Wesley. ISBN 9780201877212.
  • Maurice J. Bach (1987). "Chamadas do sistema para o sistema de arquivos". O design do sistema operacional Unix . Prentice-Hall. ISBN 0132017571.
  • Steven V. Earhart (1986). " config(1 milhão)". Manual do Programador Unix: 3. Recursos de administração do sistema . Holt, Rinehart e Winston. ISBN 0030093139. pp. 23–28.
JdeBP
fonte
1

Você está parcialmente correto, mas apenas por acidente .

No seu exemplo, todos os dados devem realmente ter sido lidos "entre" os canais, mas não precisam residir na memória (incluindo memória virtual). As implementações usuais de sortpodem classificar conjuntos de dados que não cabem na RAM, fazendo classificações parciais em arquivos temporários e mesclando. No entanto, é certo que você não pode gerar uma sequência classificada antes de ler cada elemento. Isso é bastante óbvio. Portanto, sim, sortsó é possível começar a enviar para o segundo canal depois de ler (e fazer o que for, possivelmente classificando parcialmente os arquivos temporários) tudo do primeiro. Mas não precisa necessariamente manter tudo na RAM.

No entanto, isso não tem nada a ver com o funcionamento dos tubos. Pipes podem ser nomeados (tradicionalmente todos eles foram nomeados), o que significa nada mais e nada menos do que eles têm um local no sistema de arquivos, como arquivos. E é exatamente isso que os tubos eram uma vez, arquivos (com gravações coalescentes, tanto quanto a disponibilidade de memória física permitiria, como uma otimização).

Atualmente, os pipes são um buffer de núcleo pequeno e de tamanho finito no qual os dados são copiados, pelo menos é o que acontece conceitualmente . Se o kernel pode ajudá-lo, as cópias são eliminadas por meio de truques de VM (por exemplo, a canalização de um arquivo geralmente apenas disponibiliza a mesma página para o outro processo ler, então, finalmente, é apenas uma operação de leitura, não duas cópias, e não é necessária uma memória adicional do que a que já é usada pelo cache do buffer. Em algumas situações, você também pode obter 100% de cópia zero ou algo muito próximo.

Se os tubos são pequenos e de tamanho finito, como isso pode funcionar para uma quantidade desconhecida (possivelmente grande) de dados? Isso é simples: quando nada mais se encaixa, a gravação é bloqueada até que haja espaço novamente.

A filosofia de muitos programas simples era mais útil uma vez quando a memória era muito escassa. Porque, bem, você poderia trabalhar em pequenas etapas, uma de cada vez. Hoje em dia, as vantagens são, além de uma flexibilidade extra, ouso dizer, que não são tão boas assim.
No entanto, os tubos são implementados com muita eficiência (eles precisavam ser!), Então também não há desvantagem, e é algo estabelecido que está funcionando bem e com o qual as pessoas estão acostumadas, portanto, não há necessidade de mudar o paradigma.

Damon
fonte
Quando você diz 'pipes foram nomeados' (o JdeBP parece dizer que havia um 'dispositivo de pipe'), isso significa que havia um limite para o número de tubos que poderiam ser usados ​​em um determinado momento (ou seja, havia um limite para quantas vezes você poderia usar |em um comando)?
malan
2
Eu nunca vi esse limite e não acho que, em teoria , tenha existido um. Na prática, qualquer coisa que tenha um nome de arquivo precisa de um inode, e o número de inodes é, obviamente, finito. Assim como o número de páginas físicas em um sistema, se nada mais. Os sistemas modernos garantem gravações atômicas de 4k, portanto, cada canal deve possuir pelo menos uma página completa de 4k, o que impõe um limite rígido ao número de canais que você pode ter. Mas considere ter alguns gigabytes de RAM ... praticamente, esse é um limite que você nunca encontrará. Experimente e digite alguns milhões de tubos em um terminal ... :)
Damon