¿Por qué la pila de llamadas tiene un tamaño máximo estático?

Después de haber trabajado con algunos lenguajes de programación, siempre me he preguntado por qué la pila de subprocesos tiene un tamaño máximo predefinido, en lugar de expandirse automáticamente según sea necesario. 

En comparación, ciertas estructuras de alto nivel muy comunes (listas, mapas, etc.) que se encuentran en la mayoría de los lenguajes de programación están diseñadas para crecer según sea necesario mientras se agregan nuevos elementos, con un tamaño limitado solo por la memoria disponible o por los límites computacionales ( por ejemplo, direccionamiento de 32 bits).

Sin embargo, no conozco ningún lenguaje de programación o entorno de tiempo de ejecución en el que el tamaño máximo de la pila no esté limitado previamente por alguna opción predeterminada o de compilación. Es por eso que demasiada recursión resultará muy rápidamente en un error / excepción de desbordamiento de pila ubicuo, incluso cuando solo se use para la pila un porcentaje mínimo de la memoria disponible para un proceso.

¿Por qué es el caso que la mayoría (si no todos) los entornos de tiempo de ejecución establecen un límite máximo para el tamaño que una pila puede crecer en tiempo de ejecución?

Es posible escribir un sistema operativo que no requiera que las pilas sean contiguas en el espacio de direcciones. Básicamente, necesitas un poco de desorden adicional en la convención de llamadas para asegurarte de que:

1. Si no hay suficiente espacio en la extensión de la pila actual para la función que está llamando, entonces cree una nueva extensión de pila y mueva el puntero de la pila para apuntar al comienzo de la misma como parte de la llamada.

2. cuando regresa de esa llamada, vuelve a transferir a la extensión de pila original. Lo más probable es que conserve el creado en (1) para su uso futuro por el mismo hilo. En principio, podría liberarlo, pero de esa manera se encuentran casos bastante ineficientes en los que salta hacia adelante y hacia atrás a través del límite en un bucle, y cada llamada requiere asignación de memoria.

3. setjmpy longjmp, o cualquier equivalente que tenga su sistema operativo para la transferencia de control no local, están en el acto y pueden regresar correctamente a la extensión de pila anterior cuando sea necesario.

Digo "convención de llamadas": para ser específicos, creo que probablemente sea mejor hacerlo en un prólogo de función que en la persona que llama, pero mi recuerdo de esto es confuso.

La razón por la que varios idiomas especifican un tamaño de pila fijo para un subproceso, es que quieren trabajar usando la pila nativa, en sistemas operativos que no lo hacen. Como dicen las respuestas de todos los demás, bajo el supuesto de que cada pila debe ser contigua en el espacio de direcciones, y no se puede mover, debe reservar un rango de direcciones específico para cada hilo. Eso significa elegir un tamaño por adelantado. Incluso si su espacio de direcciones es masivo y el tamaño que elige es realmente grande, aún debe elegirlo tan pronto como tenga dos hilos.

"Ajá", dices, "¿qué son estos supuestos sistemas operativos que usan pilas no contiguas? ¡Apuesto a que es un oscuro sistema académico que no me sirve!". Bueno, esa es otra pregunta que afortunadamente ya se hizo y respondió.

Esas estructuras de datos generalmente tienen propiedades que la pila del sistema operativo no tiene:

• Las listas vinculadas no requieren espacio de direcciones contiguas. Para que puedan agregar un pedazo de memoria desde donde quieran cuando crezcan.

• Incluso las colecciones que necesitan almacenamiento contiguo, como el vector de C ++, tienen una ventaja sobre las pilas del sistema operativo: pueden declarar inválidos todos los punteros / iteradores cada vez que crecen. Por otro lado, la pila del sistema operativo debe mantener válidos los punteros a la pila hasta que regrese la función a cuyo marco pertenece el objetivo.

Un lenguaje de programación o tiempo de ejecución puede elegir implementar sus propias pilas que no sean contiguas o móviles para evitar las limitaciones de las pilas del sistema operativo. Golang utiliza estas pilas personalizadas para admitir un gran número de co-rutinas, originalmente implementadas como memoria no contigua y ahora a través de pilas móviles gracias al seguimiento del puntero (ver el comentario de hobb). Python sin pila, Lua y Erlang también pueden usar pilas personalizadas, pero no lo he confirmado.

En los sistemas de 64 bits, puede configurar pilas relativamente grandes con un costo relativamente bajo, ya que el espacio de direcciones es abundante y la memoria física solo se asigna cuando realmente la usa.

En la práctica, es difícil (y a veces imposible) hacer crecer la pila. Para entender por qué requiere cierta comprensión de la memoria virtual.

En los días de Ye Olde de aplicaciones de un solo subproceso y memoria contigua, tres eran tres componentes de un espacio de direcciones de proceso: el código, el montón y la pila. La forma en que se distribuyeron esos tres dependía del sistema operativo, pero generalmente el código vino primero, comenzando en la parte inferior de la memoria, el montón vino después y creció hacia arriba, y la pila comenzó en la parte superior de la memoria y creció hacia abajo. También había algo de memoria reservada para el sistema operativo, pero podemos ignorar eso. Los programas en esos días tenían desbordamientos de pila algo más dramáticos: la pila se bloqueaba en el montón, y dependiendo de qué se actualizara primero, trabajaría con datos incorrectos o regresaría de una subrutina a alguna parte arbitraria de la memoria.

La gestión de la memoria cambió este modelo de alguna manera: desde la perspectiva del programa, todavía tenía los tres componentes de un mapa de memoria de proceso, y generalmente estaban organizados de la misma manera, pero ahora cada uno de los componentes se gestionaba como un segmento independiente y la MMU señalaba el SO si el programa intentó acceder a la memoria fuera de un segmento. Una vez que tenía memoria virtual, no había necesidad ni deseo de dar acceso a un programa a todo su espacio de direcciones. Entonces a los segmentos se les asignaron límites fijos.

Entonces, ¿por qué no es conveniente dar acceso a un programa a su espacio de direcciones completo? Porque esa memoria constituye un "cargo de compromiso" contra el intercambio; en cualquier momento, una parte o la totalidad de la memoria de un programa podría tener que escribirse para intercambiarse y dejar espacio para la memoria de otro programa. Si cada programa pudiera consumir potencialmente 2 GB de intercambio, entonces tendría que proporcionar suficiente intercambio para todos sus programas o arriesgarse a que dos programas necesiten más de lo que podrían obtener.

En este punto, suponiendo que haya suficiente espacio de direcciones virtuales, puede ampliar estos segmentos si es necesario, y el segmento de datos (montón) de hecho crece con el tiempo: comienza con un pequeño segmento de datos y cuando el asignador de memoria solicita más espacio cuando es necesario En este punto, con una sola pila, habría sido físicamente posible extender el segmento de la pila: el sistema operativo podría atrapar el intento de empujar algo fuera del segmento y agregar más memoria. Pero esto tampoco es particularmente deseable.

Ingrese multi-threading. En este caso, cada subproceso tiene un segmento de pila independiente, de nuevo tamaño fijo. Pero ahora los segmentos se disponen uno tras otro en el espacio de direcciones virtuales, por lo que no hay forma de expandir un segmento sin mover otro, lo que no puede hacer porque el programa potencialmente tendrá punteros a la memoria que viven en la pila. Alternativamente, podría dejar algo de espacio entre segmentos, pero ese espacio se desperdiciaría en casi todos los casos. Un mejor enfoque era poner la carga sobre el desarrollador de la aplicación: si realmente necesita pilas profundas, puede especificar eso al crear el hilo.

Hoy, con un espacio de direcciones virtuales de 64 bits, podríamos crear pilas efectivamente infinitas para números de hilos efectivamente infinitos. Pero, de nuevo, eso no es particularmente deseable: en casi todos los casos, una pila demasiado baja indica un error con su código. Proporcionarle una pila de 1 GB simplemente difiere el descubrimiento de ese error.

La pila que tiene un tamaño máximo fijo no es ubicua.

También es difícil acertar: las profundidades de la pila siguen una Distribución de la Ley de Potencia, lo que significa que no importa cuán pequeño sea el tamaño de la pila, todavía habrá una fracción significativa de funciones con pilas aún más pequeñas (por lo tanto, desperdicia espacio), y no importa cuán grande lo haga, todavía habrá funciones con pilas aún más grandes (por lo que forzará un error de desbordamiento de pila para funciones que no tienen error). En otras palabras: sea cual sea el tamaño que elija, siempre será demasiado pequeño y demasiado grande al mismo tiempo.

Puede solucionar el primer problema permitiendo que las pilas comiencen pequeñas y crezcan dinámicamente, pero aún tiene el segundo problema. Y si dejas que la pila crezca dinámicamente de todos modos, ¿por qué ponerle un límite arbitrario?

Hay sistemas donde las pilas pueden crecer dinámicamente y no tienen un tamaño máximo: Erlang, Go, Smalltalk y Scheme, por ejemplo. Hay muchas maneras de implementar algo así:

• pilas móviles: cuando la pila contigua ya no puede crecer porque hay algo más en el camino, muévala a otra ubicación en la memoria, con más espacio libre
• pilas no contiguas: en lugar de asignar la pila completa en un único espacio de memoria contiguo, asígnelo en múltiples espacios de memoria
• pilas asignadas al montón: en lugar de tener áreas de memoria separadas para la pila y el montón, simplemente asigne la pila en el montón; Como se dio cuenta, las estructuras de datos asignadas en el montón no suelen tener problemas para crecer y reducirse según sea necesario.
• no use pilas en absoluto: esa también es una opción, por ejemplo, en lugar de realizar un seguimiento del estado de la función en una pila, haga que la función pase una continuación a la persona que llama

Tan pronto como tenga construcciones potentes de flujo de control no local, la idea de una sola pila contigua desaparece de todos modos: las excepciones y continuaciones reanudables, por ejemplo, "bifurcarán" la pila, por lo que en realidad terminará con una red de pilas (por ejemplo, implementado con una pila de espagueti). Además, los sistemas con pilas modificables de primera clase, como Smalltalk, requieren pilas de espagueti o algo similar.

El sistema operativo tiene que dar un bloque contiguo cuando se solicita una pila. La única forma de hacerlo es si se especifica un tamaño máximo.

Por ejemplo, supongamos que la memoria se ve así durante la solicitud (las X representan usadas, las Os no utilizadas):

XOOOXOOXOOOOOX

Si se solicita un tamaño de pila de 6, la respuesta del sistema operativo responderá que no, incluso si hay más de 6 disponibles. Si se solicita una pila de tamaño 3, la respuesta del sistema operativo será una de las áreas de 3 ranuras vacías (Os) en una fila.

Además, se puede ver la dificultad de permitir el crecimiento cuando se ocupa el siguiente espacio contiguo.

Los otros objetos que se mencionan (Listas, etc.) no van a la pila, terminan en el montón en áreas no contiguas o fragmentadas, por lo que cuando crecen, solo toman espacio, no requieren contiguos como están. gestionado de manera diferente.

La mayoría de los sistemas establecen un valor razonable para el tamaño de la pila, puede anularlo cuando se construye el hilo si se requiere un tamaño más grande.

En Linux, esto es puramente un límite de recursos que existe para matar los procesos fuera de control antes de que consuman cantidades dañinas del recurso. En mi sistema Debian, el siguiente código

#include <sys/resource.h>
#include <stdio.h>

int main() {
    struct rlimit limits;
    getrlimit(RLIMIT_STACK, &limits);
    printf("   soft limit = 0x%016lx\n", limits.rlim_cur);
    printf("   hard limit = 0x%016lx\n", limits.rlim_max);
    printf("RLIM_INFINITY = 0x%016lx\n", RLIM_INFINITY);
}

produce la salida

   soft limit = 0x0000000000800000
   hard limit = 0xffffffffffffffff
RLIM_INFINITY = 0xffffffffffffffff

Tenga en cuenta que el límite rígido se establece en RLIM_INFINITY: El proceso puede aumentar su límite flexible a cualquier cantidad. Sin embargo, mientras el programador no tenga ninguna razón para creer que el programa realmente necesita cantidades inusuales de memoria de pila, el proceso se anulará cuando exceda un tamaño de pila de ocho mebibytes.

Debido a este límite, un proceso desbocado (recursión infinita no deseada) se elimina mucho tiempo antes de que comience a consumir cantidades tan grandes de memoria que el sistema se ve obligado a comenzar a intercambiar. Esto puede marcar la diferencia entre un proceso bloqueado y un servidor bloqueado. Sin embargo, no limita los programas con una necesidad legítima de una pila grande, solo necesitan establecer el límite flexible en algún valor apropiado.

Técnicamente, las pilas crecen dinámicamente: cuando el límite flexible se establece en ocho mebibyte, eso no significa que esta cantidad de memoria se haya asignado todavía. Esto sería un desperdicio ya que la mayoría de los programas nunca se acercan a sus respectivos límites blandos. Por el contrario, el kernel detectará los accesos debajo de la pila y solo se asignará en las páginas de memoria según sea necesario. Por lo tanto, la única limitación real en el tamaño de la pila es la memoria disponible en sistemas de 64 bits (la fragmentación del espacio de direcciones es bastante teórica con un tamaño de espacio de direcciones de 16 zebibytes).

El tamaño máximo de la pila es estático porque esa es la definición de "máximo" . Cualquier tipo de máximo en cualquier cosa es una cifra límite fija y acordada. Si se comporta como un objetivo en movimiento espontáneo, no es un máximo.

De hecho, las pilas en los sistemas operativos de memoria virtual crecen dinámicamente, hasta el máximo .

Hablando de eso, no tiene que ser estático. Más bien, puede ser configurable, incluso por proceso o por subproceso.

Si la pregunta es "¿por qué es que hay un tamaño máximo de pila" (una impuesta artificialmente, por lo general mucho menos que la memoria disponible)?

Una razón es que la mayoría de los algoritmos no requieren una gran cantidad de espacio de pila. Una pila grande es una indicación de una posible recursión fuera de control . Es bueno detener la recursión fuera de control antes de que asigne toda la memoria disponible. Un problema que parece una recursión desbocada es el uso de pila degenerado, tal vez provocado por un caso de prueba inesperado. Por ejemplo, supongamos que un analizador para un operador binario infijo funciona recurriendo al operando correcto: analizar el primer operando, explorar el operador, analizar el resto de la expresión. Esto significa que la profundidad de la pila es proporcional a la longitud de la expresión: a op b op c op d .... Un gran caso de prueba de esta forma requerirá una gran pila. Anular el programa cuando alcanza un límite de pila razonable lo atrapará.

Otra razón para un tamaño de pila máximo fijo es que el espacio virtual para esa pila puede reservarse a través de un tipo especial de mapeo y, por lo tanto, garantizarse. Garantizado significa que el espacio no se asignará a otra asignación con la que la pila colisionará antes de alcanzar el límite. Se requiere el parámetro de tamaño de pila máximo para solicitar esta asignación.

Los subprocesos necesitan un tamaño de pila máximo por un motivo similar a este. Sus pilas se crean dinámicamente y no se pueden mover si chocan con algo; el espacio virtual debe reservarse por adelantado, y se requiere un tamaño para esa asignación.