Como os pipelines limitam o uso da memória?

Question

Brian Kernighan explica em este vídeo a atração inicial da Bell Labs para que pequenos idiomas / programas fossem baseados em limitações de memória

A big machine would be 64 k-bytes--K, not M or G--and so that meant any individual program could not be very big, and so there was a natural tendency to write small programs, and then the pipe mechanism, basically input output redirection, made it possible to link one program to another.

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

De Wikipedia :

In most Unix-like systems, all processes of a pipeline are started at the same time [emphasis mine], with their streams appropriately connected, and managed by the scheduler together with all other processes running on the machine. An important aspect of this, setting Unix pipes apart from other pipe implementations, is the concept of buffering: for example a sending program may produce 5000 bytes per second, and a receiving program may only be able to accept 100 bytes per second, but no data is lost. Instead, the output of the sending program is held in the buffer. When the receiving program is ready to read data, then next program in the pipeline reads from the buffer. In Linux, the size of the buffer is 65536 bytes (64KB). An open source third-party filter called bfr is available to provide larger buffers if required.

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

A única coisa em que posso pensar como uma solução para minha primeira pergunta (as limitações de memória sendo problemáticas dependendo dos dados de tamanho) seria que grandes conjuntos de dados simplesmente não eram computados naquela época e os pipelines de problemas reais eram destinados a solve era a 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 de cada vez.

Tudo isso faria muito sentido se os arquivos temporários fossem usados, mas é do meu conhecimento 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 sed está lendo no arquivo e cuspindo-o linha por linha. Mas sort , como afirma BK no vídeo vinculado, é um ponto final, então todos os dados devem ser lidos na memória (ou são?), Então é passado para uniq , que (para meu mente) seria um programa de uma linha por vez. Mas entre o primeiro e o segundo pipe, todos os dados precisam estar na memória, não?

    

Answer 1

Os dados não precisam ser armazenados na RAM. Canos 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) há algum armazenamento em buffer, mas isso não é obrigatório. Como mencionado por mtraceur e JdeBP (veja a resposta deste último ), versões anteriores de pipes Unix em buffer para o disco, e foi assim que eles ajudaram a limitar o uso de memória: um pipeline de processamento poderia ser dividido em pequenos programas, cada um processando alguns dados, dentro dos limites dos buffers de disco. Programas pequenos ocupam menos memória, e o uso de pipes significa que o processamento pode ser serializado: o primeiro programa rodará, preencherá o buffer de saída, será suspenso, o segundo programa será programado, o buffer será processado 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

sed lê os dados de file , conforme necessário, e grava-os enquanto sort estiver pronto para lê-los; Se sort não estiver pronto, os blocos de gravação. Os dados, na verdade, vivem na memória, mas isso é específico para sort e sort está preparado para lidar com quaisquer problemas (ele usará arquivos temporários, pois 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 boa quantidade de dados e os canaliza para um processo que não está pronto para ler qualquer coisa nos primeiros dois minutos. Você verá uma série de write das operações, mas muito rapidamente seq irá parar e aguardar os dois minutos serem bloqueados pelo kernel (a chamada do sistema write ).

    

Answer 2

But I don't understand how this could limit memory usage considering the fact that the data has to be stored in RAM to transmit between programs.

Este é o seu erro fundamental. As primeiras versões do Unix não mantinham dados de pipe na RAM. Eles os armazenaram no disco. Os tubos tinham i-nodes; em um dispositivo de disco que foi denotado o pipe pipe . O administrador do sistema executou um programa chamado /etc/config para especificar (entre outras coisas) que volume no qual disco foi o dispositivo de tubo, que o volume foi o dispositivo raiz , e que o dispositivo de despejo .

A quantidade de dados pendentes foi restringida pelo fato de que apenas os blocos diretos do nó i do disco foram usados para armazenamento. Esse mecanismo fez o código mais simples, porque grande parte o mesmo algoritmo foi utilizado para a leitura de um tubo como foi empregado para a leitura de um arquivo regular, com alguns ajustes causados pelo fato de que os tubos não são pesquisável e o buffer é circular.

Esse mecanismo foi substituído por outros no meio até o final dos anos 80. O SCO XENIX ganhou o "High Performance Pipe System", que substituiu i-nodes por buffers in-core. O 4BSD fez pipes não nomeados em pares de socket. AT & T reimplementou canos usando o mecanismo STREAMS.

E, claro, o programa sort realizaram uma espécie limitada interna de pedaços 32KiB de entrada (ou qualquer que seja menor quantidade de memória que poderia alocar se 32KiB não estava disponível), escrevendo os resultados classificados para arquivos intermediário stmX?? em /usr/tmp/ , que então é mesclado externamente para fornecer o resultado final.

Leitura adicional

• Steve D. Pate (1996). "Comunicação entre processos". Internals 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 (1M)". Unix Programmer's Manual: 3. Instalações de Administração do Sistema . Holt, Rinehart e Winston. ISBN 0030093139. pp. 23-28.

Answer 3

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

No seu exemplo, todos os dados devem, de fato, ter sido lidos "entre" os pipes, mas ele não precisa estar residente na memória (incluindo a memória virtual). Implementações usuais de sort podem classificar conjuntos de dados que não caberão na RAM fazendo classificações parciais em tempfiles e mesclando. No entanto, é um fato que você não pode produzir uma seqüência classificada antes de ler todos os elementos. Isso é bem óbvio. Então, sim, sort só pode iniciar a saída para o segundo canal depois de ter lido (e feito o que for possível, possivelmente ordenando parcialmente os arquivos temporários) desde o primeiro. Mas não necessariamente tem que manter tudo na RAM.

No entanto, isso não tem nada a ver com o funcionamento dos pipes. 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 isso é exatamente o que pipes eram uma vez, arquivos (com gravações unidas tanto quanto a disponibilidade de memória física permitiria, como uma otimização).

Atualmente, os pipes são um buffer de kernel pequeno, de tamanho finito, para o qual os dados são copiados, pelo menos é o que ocorre conceitualmente . Se o kernel puder ajudar, as cópias serão eliminadas jogando-se truques de VM (por exemplo, canalizar a partir de um arquivo geralmente torna a mesma página disponível para o outro processo ler, portanto, é apenas uma operação de leitura, não duas cópias e nenhuma memória adicional que já é usada pelo cache de buffer é necessária. Em algumas situações você pode obter 100% de cópia zero também, ou algo muito próximo.

Se os canos são pequenos e finitos, como isso pode funcionar para qualquer quantidade desconhecida (possivelmente grande) de dados? Isso é simples: quando nada mais se encaixa, a escrita bloqueia até que haja espaço novamente.

A filosofia de muitos programas simples foi muito útil uma vez quando a memória era muito escassa. Porque, bem, você poderia trabalhar em pequenos passos, um de cada vez. Hoje em dia, as vantagens são, além de alguma flexibilidade extra, eu diria, não tão bom assim.
No entanto, os pipes são implementados de forma muito eficiente (eles tinham que ser!), Então não há nenhuma desvantagem, e é uma coisa estabelecida que está funcionando bem e que as pessoas estão acostumadas, então não há necessidade de mudar o paradigma. p>