¿Cómo limitan las tuberías el uso de memoria?

36

Brian Kernighan explica en este video la atracción temprana de Bell Labs por los pequeños lenguajes / programas basados ​​en limitaciones de memoria

Una máquina grande tendría 64 k-bytes, K, no M o G, y eso significaba que cualquier programa individual no podía ser muy grande, por lo que había una tendencia natural a escribir programas pequeños, y luego el mecanismo de canalización, Básicamente, la redirección de entrada y salida hizo posible vincular un programa a otro.

Pero no entiendo cómo esto podría limitar el uso de memoria teniendo en cuenta el hecho de que los datos deben almacenarse en la RAM para transmitir entre programas.

De Wikipedia :

En la mayoría de los sistemas tipo Unix, todos los procesos de una tubería se inician al mismo tiempo [énfasis mío], con sus secuencias conectadas adecuadamente y gestionadas por el planificador junto con todos los demás procesos que se ejecutan en la máquina. Un aspecto importante de esto, diferenciar las tuberías de Unix de otras implementaciones de tuberías, es el concepto de almacenamiento en búfer: por ejemplo, un programa de envío puede producir 5000 bytes por segundo, y un programa de recepción solo puede aceptar 100 bytes por segundo, pero no se pierden datos En cambio, la salida del programa de envío se mantiene en el búfer. Cuando el programa receptor está listo para leer datos, el siguiente programa en la tubería lee desde el búfer. En Linux, el tamaño del búfer es de 65536 bytes (64 KB). Un filtro de terceros de código abierto llamado bfr está disponible para proporcionar búferes más grandes si es necesario.

Esto me confunde aún más, ya que esto anula por completo el propósito de los programas pequeños (aunque serían modulares hasta cierta escala).

Lo único que puedo pensar como una solución a mi primera pregunta (las limitaciones de memoria son problemáticas dependiendo de los datos de tamaño) sería que los grandes conjuntos de datos simplemente no se computaron en ese momento y el problema real que las tuberías estaban destinadas a resolver era el cantidad de memoria requerida por los propios programas. Pero dado el texto en negrita en la cita de Wikipedia, incluso esto me confunde: como un programa no se implementa a la vez.

Todo esto tendría mucho sentido si se usaran archivos temporales, pero tengo entendido que las tuberías no escriben en el disco (a menos que se use el intercambio).

Ejemplo:

sed 'simplesubstitution' file | sort | uniq > file2

Para mí está claro que sedestá leyendo el archivo y escupiéndolo línea por línea. Pero sort, como BK afirma en el video vinculado, es un punto final, por lo que todos los datos deben leerse en la memoria (¿o no?), Luego se transmiten a uniq, lo que (en mi opinión) sería uno programa en línea a la vez. Pero entre la primera y la segunda tubería, todos los datos deben estar en la memoria, ¿no?

malan
fuente
1
unless swap is usedel intercambio siempre se usa cuando no hay suficiente RAM
edc65

Respuestas:

44

Los datos no necesitan ser almacenados en la RAM. Las tuberías bloquean a sus escritores si los lectores no están allí o no pueden mantenerse al día; bajo Linux (y la mayoría de las otras implementaciones, imagino) hay algo de almacenamiento en búfer, pero eso no es necesario. Como lo mencionaron mtraceur y JdeBP (ver la respuesta de este último), las primeras versiones de Unix almacenaron las tuberías en el disco, y así es como ayudaron a limitar el uso de la memoria: una tubería de procesamiento podría dividirse en pequeños programas, cada uno de los cuales procesaría algunos datos, dentro de los límites de las memorias intermedias del disco. Los programas pequeños requieren menos memoria, y el uso de tuberías significaba que el procesamiento podía ser serializado: el primer programa se ejecutaría, llenaría su búfer de salida, se suspendería, luego el segundo programa se programaría, procesaría el búfer, etc. Los sistemas modernos son órdenes de magnitud más grande que los primeros sistemas Unix, y puede ejecutar muchas tuberías en paralelo; pero para grandes cantidades de datos aún se vería un efecto similar (y las variantes de este tipo de técnica se utilizan para el procesamiento de "grandes datos").

En tu ejemplo

sed 'simplesubstitution' file | sort | uniq > file2

sedlee los datos filesegún sea necesario, luego los escribe mientras sortesté listo para leerlos; si sortno está listo, los bloques de escritura. Los datos realmente viven en la memoria eventualmente, pero eso es específico sorty sortestá preparado para tratar cualquier problema (usará archivos temporales si la cantidad de datos para ordenar es demasiado grande).

Puede ver el comportamiento de bloqueo ejecutando

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

Esto produce una buena cantidad de datos y los canaliza a un proceso que no está listo para leer nada durante los primeros dos minutos. Verá que se realizan varias writeoperaciones, pero muy rápidamente seqse detendrá y esperará a que transcurran los dos minutos, bloqueado por el núcleo (la writellamada del sistema espera).

Stephen Kitt
fuente
13
Esta respuesta podría beneficiarse de una explicación adicional de por qué dividir los programas en muchos pequeños ahorra el uso de la memoria: un programa tenía que poder ajustarse en la memoria para ejecutarse, pero solo el programa que se ejecuta actualmente . Todos los demás programas se cambiaron al disco a principios de Unix, y solo un programa se cambió a la RAM real a la vez. Entonces, la CPU ejecutaría un programa, que escribiría en una tubería (que en ese entonces estaba en el disco ), intercambiaría ese programa e intercambiaría el que leía de la tubería. Forma elegante de convertir una línea de ensamblaje lógicamente paralela en una ejecución serializada incremental.
mtraceur
66
@malan: Se pueden iniciar múltiples procesos y pueden estar en un estado ejecutable al mismo tiempo. Pero, como máximo, un proceso puede ejecutarse en cada CPU física en un momento dado, y es el trabajo del planificador de procesos del núcleo asignar "segmentos" de tiempo de CPU a cada proceso ejecutable. En los sistemas modernos, un proceso que es ejecutable pero que actualmente no está programado como un intervalo de tiempo de CPU generalmente permanece residente en la memoria mientras espera su próximo segmento, pero el núcleo puede localizar la memoria de cualquier proceso en el disco y volver a la memoria nuevamente como lo encuentra conveniente (Agitando algunos detalles aquí.)
Daniel Pryden
55
Los procesos a ambos lados de una tubería pueden comportarse de manera efectiva como co-rutinas: un lado escribe hasta que llena el búfer y los bloques de escritura, momento en el cual el proceso no puede hacer nada con el resto de su segmento de tiempo y entra en un IO modo de espera. Luego, el sistema operativo le da el resto del segmento de tiempo (u otro segmento de tiempo próximo) al lado de lectura, que lee hasta que no quede nada en el búfer y los siguientes bloques de lectura, momento en el cual el proceso del lector no puede hacer nada con el resto de su intervalo de tiempo y vuelve al sistema operativo. Los datos pasan por la tubería por valor de un búfer a la vez.
Daniel Pryden
66
@malan Los programas se inician "al mismo tiempo" conceptualmente en todos los sistemas Unix, solo en sistemas multiprocesadores modernos con suficiente RAM para mantenerlos, lo que significa que están literalmente todos en RAM al mismo tiempo, mientras que en un sistema que puede No los guardes en la RAM al mismo tiempo, algunos se cambian al disco. También tenga en cuenta que "memoria" en muchos contextos significa memoria virtual, que es la suma del espacio RAM y el espacio de intercambio en el disco. Wikipedia se está centrando en el concepto más que en los detalles de implementación, especialmente porque la antigüedad de Unix hizo las cosas ahora es menos relevante.
mtraceur
2
@malan Además, la contradicción que está viendo proviene de los dos significados diferentes de "memoria" (RAM vs RAM + intercambio). Estaba hablando solo de RAM de hardware, y en ese contexto solo el código que la CPU ejecuta actualmente debe encajar en la RAM (que era lo que estaba afectando las decisiones de las que habla Kernighan), mientras que en el contexto de todos los programas que se ejecutan lógicamente por el sistema operativo en un momento dado (en el nivel abstracto proporcionado en la división superior del tiempo), un programa solo necesita ajustarse dentro de toda la memoria virtual disponible para el sistema operativo, que incluye espacio de intercambio en el disco.
mtraceur
34

Pero no entiendo cómo esto podría limitar el uso de memoria teniendo en cuenta el hecho de que los datos deben almacenarse en la RAM para transmitir entre programas.

Este es tu error fundamental. Las primeras versiones de Unix no contenían datos de tubería en RAM. Los almacenaron en disco. Las tuberías tenían nodos i; en un dispositivo de disco que se designó como dispositivo de tubería . El administrador del sistema ejecutó un programa llamado /etc/configpara especificar (entre otras cosas) qué volumen en qué disco era el dispositivo de tubería, qué volumen era el dispositivo raíz y cuál era el dispositivo de volcado .

La cantidad de datos pendientes estaba limitada por el hecho de que solo los bloques directos del i-node en el disco se usaban para el almacenamiento. Este mecanismo simplificó el código, porque se empleó el mismo algoritmo para leer desde una tubería que para la lectura de un archivo normal, con algunos ajustes causados ​​por el hecho de que las tuberías no son buscables y el búfer es circular.

Este mecanismo fue reemplazado por otros a mediados o finales de la década de 1980. SCO XENIX ganó el "Sistema de tuberías de alto rendimiento", que reemplazó a los nodos i con memorias intermedias en el núcleo. 4BSD convirtió tuberías sin nombre en pares de enchufes. AT&T reimplementó tuberías con el mecanismo STREAMS.

Y, por supuesto, el sortprograma realizó un tipo interno limitado de trozos de entrada de 32 KB (o cualquier cantidad de memoria menor que pudiera asignar si 32 KB no estuviera disponible), escribiendo los resultados ordenados en stmX??archivos intermedios en los /usr/tmp/que luego se fusionan externamente para proporcionar el resultado final salida.

Otras lecturas

  • Steve D. Pate (1996). "Comunicación entre procesos". UNIX Internals: un enfoque práctico . Addison-Wesley. ISBN 9780201877212.
  • Maurice J. Bach (1987). "Llamadas del sistema para el sistema de archivos". El diseño del sistema operativo Unix . Prentice Hall. ISBN 0132017571.
  • Steven V. Earhart (1986). " config(1M)". Manual del programador de Unix: 3. Instalaciones de administración del sistema . Holt, Rinehart y Winston. ISBN 0030093139. pp. 23–28.
JdeBP
fuente
1

Estás parcialmente en lo correcto, pero solo por accidente .

En su ejemplo, todos los datos deben haberse leído "entre" las tuberías, pero no es necesario que residan en la memoria (incluida la memoria virtual). Las implementaciones habituales de sortpueden ordenar conjuntos de datos que no caben en la RAM haciendo ordenamientos parciales a archivos temporales y fusionándolos. Sin embargo, es un hecho dado que no puede generar una secuencia ordenada antes de haber leído todos y cada uno de los elementos. Eso es bastante obvio. Entonces, sí, sortsolo puede comenzar a salir a la segunda tubería después de haber leído (y hecho lo que sea, posiblemente clasificando parcialmente los archivos temporales) todo desde el primero. Pero no necesariamente tiene que mantenerlo todo en RAM.

Sin embargo, esto no tiene nada que ver con el funcionamiento de las tuberías. Las tuberías se pueden nombrar (tradicionalmente todas se nombraron), lo que significa nada más y nada menos que tener una ubicación en el sistema de archivos, como los archivos. Y eso es exactamente lo que alguna vez fueron las tuberías, los archivos (con escrituras fusionadas tanto como lo permitiera la disponibilidad de memoria física, como una optimización).

Hoy en día, las tuberías son un pequeño búfer de núcleo de tamaño finito en el que se copian los datos, al menos eso es lo que conceptualmente sucede . Si el núcleo puede ayudarlo, las copias se eluyen jugando trucos de VM (por ejemplo, la canalización de un archivo generalmente solo hace que la misma página esté disponible para que el otro proceso la lea, por lo que finalmente es solo una operación de lectura, no dos copias, y no De todos modos, se necesita memoria adicional de la que ya utiliza el caché del búfer. En algunas situaciones, también puede obtener una copia cero al 100% o algo muy cercano.

Si las tuberías son pequeñas y de tamaño finito, ¿cómo puede funcionar esto para una cantidad de datos desconocida (posiblemente grande)? Eso es simple: cuando nada más encaja, los bloques de escritura hasta que haya espacio nuevamente.

La filosofía de muchos programas simples fue más útil alguna vez cuando la memoria era muy escasa. Porque, bueno, podrías trabajar en pequeños pasos, uno a la vez. Hoy en día, las ventajas son, aparte de cierta flexibilidad adicional, me atrevo a decir que ya no son tan geniales.
Sin embargo, las tuberías se implementan de manera muy eficiente (¡tenían que serlo!), Por lo que tampoco hay desventaja, y es una cosa establecida que funciona bien y a la que las personas están acostumbradas, por lo que no hay necesidad de cambiar el paradigma.

Damon
fuente
Cuando dice 'se nombraron tuberías' (JdeBP parece decir que hubo un 'dispositivo de tubería'), eso significa que había un límite en la cantidad de tuberías que se podían usar en un momento dado (es decir, había un límite para ¿Cuántas veces podrías usar |en un comando)?
malan
2
Nunca he visto un límite así, y no creo que en teoría haya uno. En la práctica, cualquier cosa que tenga un nombre de archivo necesita un inodo, y el número de inodos es, por supuesto, finito. Como son el número de páginas físicas en un sistema, si nada más. Los sistemas modernos garantizan 4k escrituras atómicas, por lo que cada tubería debe tener al menos una página completa de 4k, lo que pone un límite estricto en la cantidad de tuberías que puede tener. Pero considere tener un par de gigabytes de RAM ... prácticamente, ese es un límite que nunca encontrará. Intenta escribir algunos millones de tuberías en una terminal ... :)
Damon