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

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 error adicional en la convención de llamadas, para asegurarte de que:

1. si no hay suficiente espacio en la extensión de pila actual para la función que está llamando, entonces crea una nueva extensión de pila y mueve el puntero de pila para que apunte al inicio como parte de la creación de llamada.

2. cuando regresas de esa llamada, te transfieres nuevamente a la extensión de la pila original. Lo más probable es que conserve el creado en (1) para uso futuro por el mismo hilo. En principio, podría soltarlo, pero de esa manera se encuentran los casos ineficientes en los que sigue saltando de un lado a otro del límite en un bucle, y cada llamada requiere asignación de memoria.

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

Digo "convención de llamada": para ser específico, creo que es mejor hacerlo en un prólogo de función en lugar de por parte de la persona que llama, pero mi memoria de esto es confusa.

La razón por la que muchos idiomas especifican un tamaño de pila fijo para un subproceso, es que quieren trabajar utilizando la pila nativa, en sistemas operativos que no hacen esto. 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 que lo use 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, todavía tiene que elegirlo tan pronto como tenga dos hilos.

"Ajá", dices, "¿cuáles son estos supuestos sistemas operativos que utilizan pilas no contiguas? ¡Apuesto a que es un sistema académico oscuro que no me sirve!". Bueno, esa es otra pregunta que, afortunadamente, ya está formulada y respondida.

Esas estructuras de datos suelen tener propiedades que la pila del sistema operativo no tiene:

• Las listas enlazadas no requieren espacio de direcciones contiguas. Para que puedan agregar un pedazo de memoria de 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 cuando crezcan. Por otro lado, la pila del sistema operativo debe mantener los punteros a la pila válidos hasta que la función a cuyo marco pertenece el objetivo retorne.

Un lenguaje de programación o tiempo de ejecución puede optar por implementar sus propias pilas que no sean contiguas o móviles para evitar las limitaciones de las OS. Golang usa esas 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 de punteros (consulte el comentario de hobb) Python sin pila, Lua y Erlang también podrían usar pilas personalizadas, pero no lo confirmé.

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

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

En Ye Olde Days de aplicaciones de un solo hilo 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 era primero, comenzando en el fondo de la memoria, el montón venía y crecía hacia arriba, y la pila comenzaba en la parte superior de la memoria y crecía hacia abajo. También había algo de memoria reservada para el sistema operativo, pero podemos ignorarlo. Los programas en esos días tenían desbordamientos de pila algo más dramáticos: la pila se estrellaría en el montón, y dependiendo de lo que se actualizó primero, trabajaría con datos erróneos o regresaría de una subrutina a una parte arbitraria de la memoria.

La gestión de la memoria cambió este modelo de alguna manera: desde la perspectiva del programa, aún tenía los tres componentes de un mapa de memoria de proceso, y en general estaban organizados de la misma manera, pero ahora cada uno de los componentes se gestionaba como un segmento independiente y la MMU. señalaría al sistema operativo si el programa intentara acceder a la memoria fuera de un segmento. Una vez que tenía memoria virtual, no era necesario o desear para dar a un programa acceso a todo su espacio de direcciones. Así que a los segmentos se les asignaron límites fijos.

  

Entonces, ¿por qué no es deseable dar a un programa acceso a su espacio de direcciones completo? Porque esa memoria constituye un "cargo de comisión" contra el canje; en cualquier momento, cualquiera o toda la memoria de un programa puede tener que escribirse para intercambiar y dejar espacio para la memoria de otro programa. Si cada programa pudiera consumir 2GB de swap, entonces tendrías que proporcionar suficiente swap para todos tus programas o arriesgarte a que dos programas necesiten más de lo que podrían obtener.

En este punto, suponiendo que haya suficiente espacio de direcciones virtuales, podría extender estos segmentos si es necesario y, de hecho, el segmento de datos (montón) crece con el tiempo: comienza con un segmento de datos pequeño , 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.

Introduzca multihilo. En este caso, cada hilo tiene un segmento de pila independiente, de nuevo de tamaño fijo. Pero ahora los segmentos se colocan 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 se puede hacer porque el programa potencialmente tendrá punteros a la memoria que se encuentra en la pila. Alternativamente, podría dejar algo de espacio entre los segmentos, pero ese espacio se desperdiciaría en casi todos los casos. Un mejor enfoque fue poner la carga en el desarrollador de la aplicación: si realmente necesitas pilas profundas, podrías especificar eso al crear el subproceso.

Hoy, con un espacio de direcciones virtuales de 64 bits, podríamos crear pilas infinitas para un número infinito de hilos. Pero, de nuevo, eso no es particularmente deseable: en casi todos los casos, un desbordamiento de pila indica un error en su código. Al 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 hacerlo bien: las profundidades de la pila siguen una Distribución de la Ley de Poder, lo que significa que no importa lo pequeño que sea el tamaño de la pila, todavía habrá una fracción significativa de funciones con pilas incluso más pequeñas (así que, se pierde) espacio), y sin importar qué tan grande sea, aún habrá funciones con pilas incluso más grandes (por lo que forzará un error de desbordamiento de pila para funciones que no tienen error). En otras palabras: cualquiera que sea el tamaño que elijas, siempre será demasiado pequeño y demasiado grande al mismo tiempo.

Puedes solucionar el primer problema permitiendo que las pilas empiecen poco a poco y crezcan dinámicamente, pero aún así tienes el segundo problema. Y si permites 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 formas de implementar algo así:

• pilas móviles: cuando la pila contigua ya no puede crecer porque hay otra cosa en el camino, muévela a otra ubicación en la memoria, con más espacio libre
• pilas no contiguas: en lugar de asignar la pila completa en un solo espacio de memoria contiguo, asignarlo 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 asigna la pila en el montón; Como se ha dado cuenta, las estructuras de datos asignadas en el montón tienden a no 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 mantener un seguimiento del estado de la función en una pila, haga que la función pase una continuación al destinatario

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

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

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

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.

También, uno puede ver la dificultad de permitir el crecimiento cuando la siguiente ranura contigua está ocupada.

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 ya que se gestionan de forma diferente.

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

En Linux, esto es puramente un límite de recursos que existe para eliminar 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 motivos para creer que el programa realmente necesita cantidades inusuales de memoria de pila, el proceso se eliminará cuando exceda un tamaño de pila de ocho mebibytes.

Debido a este límite, un proceso fuera de control (recursión infinita involuntaria) se anula mucho antes de que comience a consumir cantidades tan grandes de memoria que el sistema se ve obligado a iniciar el intercambio. Esto puede hacer la diferencia entre un proceso estrellado y un servidor estrellado. Sin embargo, no limita los programas con una necesidad legítima de una pila grande, solo necesitan establecer el límite flexible en un valor apropiado.

Técnicamente, las pilas crecen dinámicamente: cuando el límite suave se establece en ocho mebibyte, eso no significa que esta cantidad de memoria haya sido asignada todavía. Esto sería un desperdicio ya que la mayoría de los programas nunca se acercan a sus límites flexibles respectivos. Más bien, el kernel detectará los accesos debajo de la pila, y simplemente los mapeará en las páginas de memoria según sea necesario. Por lo tanto, la única limitación real del tamaño de 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 de pila de máximo es estático porque es la definición de "maximum" . Cualquier tipo de máximo en cualquier cosa es una cifra límite fija, acordada. Si se comporta como un objetivo que se mueve espontáneamente, no es un máximo.

Las pilas en los sistemas operativos de memoria virtual, de hecho, 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, incluso.

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

Una de las razones es que la mayoría de los algoritmos no requieren una cantidad tremenda 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 que la recursión fuera de control es el uso degenerado de la pila, tal vez provocado por un caso de prueba inesperado. Por ejemplo, supongamos que un analizador para un operador binario e infijo funciona recurriendo en el operando derecho: primer operando de análisis, operador de exploración, análisis de 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 caso de prueba enorme de esta forma requerirá una pila enorme. Abortar el programa cuando alcance un límite de pila razonable lo detectará.

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

Los hilos necesitan un tamaño máximo de pila por una razón similar a esta. 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.