¿Cómo se almacenan y recuperan las variables de la pila de programas?

Disculpas de antemano por la ingenuidad de esta pregunta. Soy un artista de 50 años que intenta comprender correctamente las computadoras por primera vez. Entonces aquí va.

He estado tratando de entender cómo un compilador maneja los tipos de datos y las variables (en un sentido muy general, sé que hay mucho). Me falta algo en mi comprensión de la relación entre el almacenamiento en "la pila" y los tipos de valor, y el almacenamiento en "el montón" y los tipos de referencia (las comillas están destinadas a significar que entiendo que estos términos son abstracciones y no tomarse demasiado literalmente en un contexto tan simplificado como la forma en que estoy formulando esta pregunta). De todos modos, mi idea simplista es que tipos como los booleanos y los enteros van a "la pila" porque pueden, porque son entidades conocidas en términos de espacio de almacenamiento, y su alcance se controla fácilmente en consecuencia.

Pero lo que no entiendo es cómo una aplicación lee las variables en la pila; si declaro y asigno xcomo un entero, digamos x = 3, y el almacenamiento está reservado en la pila y luego su valor de 3se almacena allí, y luego en la misma función que declaro y asigno ycomo, por ejemplo 4, y luego sigo que luego uso xen otra expresión, (digamos z = 5 + x) cómo puede leer el programa xpara evaluar zcuándo está debajoyen la pila? Claramente me estoy perdiendo algo. ¿Es que la ubicación en la pila es solo acerca de la duración / alcance de la variable, y que toda la pila es realmente accesible para el programa todo el tiempo? Si es así, ¿eso implica que hay algún otro índice que contiene las direcciones solo de las variables en la pila para permitir que se recuperen los valores? Pero luego pensé que el punto principal de la pila era que los valores se almacenaban en el mismo lugar que la dirección variable. En mi mente débil, parece que si existe este otro índice, ¿estamos hablando de algo más como un montón? Claramente estoy muy confundido, y solo espero que haya una respuesta simple a mi pregunta simplista.

Gracias por leer hasta aquí.

Almacenar variables locales en una pila es un detalle de implementación, básicamente una optimización. Puedes pensarlo de esta manera. Al ingresar una función, el espacio para todas las variables locales se asigna en alguna parte. Luego puede acceder a todas las variables, ya que de alguna manera conoce su ubicación (esto es parte del proceso de asignación). Al salir de una función, el espacio se desasigna (libera).

La pila es una forma de implementar este proceso: puede considerarlo como una especie de "montón rápido" que tiene un tamaño limitado y, por lo tanto, solo es apropiado para pequeñas variables. Como optimización adicional, todas las variables locales se almacenan en un bloque. Como cada variable local tiene un tamaño conocido, usted conoce el desplazamiento de cada variable en el bloque, y así es como accede a ella. Esto contrasta con las variables asignadas en el montón, cuyas direcciones se almacenan en otras variables.

Puede pensar en la pila como muy similar a la estructura de datos clásica de la pila, con una diferencia crucial: se le permite acceder a elementos debajo de la parte superior de la pila. De hecho, puede acceder al elemento desde la parte superior. Así es como puede acceder a todas sus variables locales presionando y haciendo estallar. El único empuje que se realiza es al ingresar a la función, y el único estallido al salir de la función.$k$

Finalmente, permítanme mencionar que, en la práctica, algunas de las variables locales se almacenan en registros. Esto se debe a que el acceso a los registros es más rápido que el acceso a la pila. Esta es otra forma de implementar un espacio para variables locales. Una vez más, sabemos exactamente dónde se almacena una variable (esta vez no a través de desplazamiento, sino a través del nombre de un registro), y este tipo de almacenamiento solo es apropiado para datos pequeños.

Tener yen la pila no impide físicamente el xacceso, lo que, como señaló, hace que las pilas de computadoras sean diferentes de otras pilas.

Cuando se compila un programa, las posiciones de las variables en la pila también están predeterminadas (dentro del contexto de una función). En su ejemplo, si la pila contiene una xcon un y"encima de", entonces el programa sabe de antemano que xserá de 1 punto por debajo de la parte superior de la pila, mientras que dentro de la función. Dado que el hardware de la computadora puede solicitar explícitamente 1 elemento debajo de la parte superior de la pila, la computadora puede obtener xaunque ytambién exista.

¿Es que la ubicación en la pila es solo acerca de la duración / alcance de la variable, y que toda la pila es realmente accesible para el programa todo el tiempo?

Si. Cuando sale de una función, el puntero de la pila vuelve a su posición anterior, borrando de manera efectiva xy y, pero técnicamente seguirán allí hasta que la memoria se use para otra cosa. Además, si su función llama a otra función, xy yseguirá estando allí y se puede acceder yendo demasiado lejos en la pila intencionalmente.

Para proporcionar un ejemplo concreto de cómo un compilador gestiona la pila y cómo se accede a los valores en la pila, podemos ver representaciones visuales, además del código generado por GCCun entorno Linux con i386 como la arquitectura de destino.

1. Marcos de pila

Como sabe, la pila es una ubicación en el espacio de direcciones de un proceso en ejecución que utilizan las funciones o procedimientos , en el sentido de que el espacio se asigna en la pila para las variables declaradas localmente, así como los argumentos pasados ​​a la función ( el espacio para variables declaradas fuera de cualquier función (es decir, variables globales) se asigna en una región diferente en la memoria virtual). El espacio asignado para todos los datos de una función se refiere a un marco de pila . Aquí hay una representación visual de múltiples cuadros de pila (de Computer Systems: A Programmer's Perspective ):

2. Gestión de marcos de pila y ubicación variable

Para que los valores escritos en la pila dentro de un marco de pila particular sean administrados por el compilador y leídos por el programa, debe haber algún método para calcular las posiciones de estos valores y recuperar su dirección de memoria. Los registros en la CPU referidos como el puntero de la pila y el puntero base ayudan con esto.

El puntero base, ebppor convención, contiene la dirección de memoria del fondo, o base, de la pila. Las posiciones de todos los valores dentro del marco de la pila se pueden calcular utilizando la dirección en el puntero base como referencia. Esto se muestra en la imagen de arriba: %ebp + 4es la dirección de memoria almacenada en el puntero base más 4, por ejemplo.

3. Código generado por el compilador

Pero lo que no entiendo es cómo una aplicación lee las variables en la pila; si declaro y asigno x como un entero, digamos x = 3, y el almacenamiento está reservado en la pila y luego se almacena su valor de 3 allí, y luego en la misma función declaro y asigno y como, por ejemplo, 4, y luego sigo que luego uso x en otra expresión, (por ejemplo z = 5 + x), ¿cómo puede el programa leer x para evaluar z cuando está debajo de y en la pila?

Usemos un programa de ejemplo simple escrito en C para ver cómo funciona esto:

int main(void)
{
        int x = 3;
        int y = 4;
        int z = 5 + x;

        return 0;
}

Examinemos el texto de ensamblaje producido por GCC para este texto fuente C (lo limpié un poco por claridad):

main:
    pushl   %ebp              # save previous frame's base address on stack
    movl    %esp, %ebp        # use current address of stack pointer as new frame base address
    subl    $16, %esp         # allocate 16 bytes of space on stack for function data
    movl    $3, -12(%ebp)     # variable x at address %ebp - 12
    movl    $4, -8(%ebp)      # variable y at address %ebp - 8
    movl    -12(%ebp), %eax   # write x to register %eax
    addl    $5, %eax          # x + 5 = 9
    movl    %eax, -4(%ebp)    # write 9 to address %ebp - 4 - this is z
    movl    $0, %eax
    leave

Lo que observamos es que las variables X, Y y Z se encuentran en direcciones %ebp - 12, %ebp -8y %ebp - 4, respectivamente. En otras palabras, las ubicaciones de las variables dentro del marco de la pila main()se calculan utilizando la dirección de memoria guardada en el registro de la CPU %ebp.

4. Los datos en la memoria más allá del puntero de la pila están fuera de alcance

Claramente me estoy perdiendo algo. ¿Es que la ubicación en la pila es solo acerca de la duración / alcance de la variable, y que toda la pila es realmente accesible para el programa todo el tiempo? Si es así, ¿eso implica que hay algún otro índice que contiene las direcciones solo de las variables en la pila para permitir que se recuperen los valores? Pero luego pensé que el punto principal de la pila era que los valores se almacenaban en el mismo lugar que la dirección variable.

La pila es una región en la memoria virtual, cuyo uso es administrado por el compilador. El compilador genera código de tal manera que los valores más allá del puntero de la pila (valores más allá de la parte superior de la pila) nunca se referencian. Cuando se llama a una función, la posición del puntero de la pila cambia para crear espacio en la pila que se considera que no está "fuera de límites", por así decirlo.

A medida que se llaman y devuelven funciones, el puntero de la pila se reduce y se incrementa. Los datos escritos en la pila no desaparecen una vez que están fuera del alcance, pero el compilador no genera instrucciones que hagan referencia a estos datos porque no hay forma de que el compilador calcule las direcciones de estos datos usando %ebpo %esp.

5. Resumen

El compilador genera el código que puede ejecutar directamente la CPU. El compilador gestiona la pila, los marcos de la pila para las funciones y los registros de la CPU. Una estrategia utilizada por GCC para rastrear las ubicaciones de las variables en los cuadros de la pila en el código destinado a ejecutarse en la arquitectura i386 es usar la dirección de memoria en el puntero base del cuadro de la pila %ebp, como referencia y escribir valores de variables en ubicaciones en los cuadros de la pila. en desplazamientos a la dirección en %ebp.

Hay dos registros especiales: ESP (puntero de pila) y EBP (puntero base). Cuando se invoca un procedimiento, las dos primeras operaciones suelen ser

push        ebp  
mov         ebp,esp 

La primera operación guarda el valor del EBP en la pila, y la segunda operación carga el valor del puntero de la pila en el puntero base (para acceder a las variables locales). Entonces, EBP apunta a la misma ubicación que ESP.

Assembler traduce nombres de variables en compensaciones EBP. Por ejemplo, si tiene dos variables locales x,yy tiene algo como

  x = 1;
  y = 2;
  return x + y;

entonces se puede traducir en algo como

   push        ebp  
   mov         ebp,esp
   mov  DWORD PTR [ ebp + 6],  1   ;x = 1
   mov  DWORD PTR [ ebp + 14], 2   ;y = 2
   mov  eax, [ ebp + 6 ]
   add  [ ebp + 14 ], eax          ; x + y 
   mov  eax, [ ebp + 14 ] 
   ...  

Los valores de compensación 6 y 14 se calculan en tiempo de compilación.

Así es más o menos cómo funciona. Consulte un libro de compilación para más detalles.

Está confundido porque no se accede a las variables locales almacenadas en la pila con la regla de acceso de la pila: Primero en entrar, Último en salir, o simplemente FILO .

La cuestión es que la regla FILO se aplica a las secuencias de llamadas de función y los marcos de pila , en lugar de a las variables locales.

¿Qué es un marco de pila?

Cuando ingresa una función, se le da cierta cantidad de memoria en la pila, llamada marco de pila. Las variables locales de la función se almacenan en el marco de la pila. Puede imaginar que el tamaño del marco de la pila varía de una función a otra, ya que cada función tiene diferentes números y tamaños de variables locales.

Cómo se almacenan las variables locales en el marco de la pila no tiene nada que ver con FILO. (Incluso el orden de aparición de sus variables locales en su código fuente no garantiza que las variables locales se almacenen en ese orden). Como dedujo correctamente en su pregunta, "hay algún otro índice que contiene las direcciones solo de las variables en la pila para permitir que se recuperen los valores ". Las direcciones de las variables locales generalmente se calculan con una dirección base , como la dirección de límite del marco de la pila y los valores de compensación específicos de cada variable local.

Entonces, ¿cuándo aparece este comportamiento FILO?

Ahora, ¿qué pasa si llamas a otra función? La función de llamada debe tener su propio marco de pila, y es este marco de pila el que se empuja en la pila . Es decir, el marco de pila de la función de llamada se coloca encima del marco de pila de la función de llamada. Y si esta función de llamada llama a otra función, entonces su marco de pila será empujado, nuevamente, en la parte superior de la pila.

¿Qué sucede si una función regresa? Cuando una función destinatario de la llamada vuelve a la función de la persona que llama, marco de pila de la función destinatario de la llamada se extraen a partir de la pila, liberando espacio para uso futuro.

Entonces de tu pregunta:

¿Es que la ubicación en la pila es solo acerca de la duración / alcance de la variable, y que toda la pila es realmente accesible para el programa todo el tiempo?

tiene bastante razón aquí porque los valores de las variables locales en el marco de la pila no se borran realmente cuando la función regresa. El valor simplemente permanece allí, aunque la ubicación de la memoria donde se almacena no pertenece al marco de la pila de ninguna función. El valor se borra cuando alguna otra función gana su marco de pila que incluye la ubicación y escribe sobre algún otro valor en esa ubicación de memoria.

Entonces, ¿qué diferencia la pila del montón?

La pila y el montón son iguales en el sentido de que ambos son nombres que se refieren a algún espacio en la memoria. Dado que podemos acceder a cualquier ubicación en la memoria con su dirección, puede acceder a cualquier ubicación en la pila o el montón.

La diferencia viene de la promesa que hace el sistema informático sobre cómo los va a usar. Como dijiste, el montón es para el tipo de referencia. Dado que los valores en el montón no tienen relación con ningún marco de pila específico, el alcance del valor no está vinculado a ninguna función. Sin embargo, una variable local tiene un alcance dentro de una función, y aunque puede acceder a cualquier valor de variable local que se encuentre fuera del marco de la pila de la función actual, el sistema intentará asegurarse de que este tipo de comportamiento no ocurra, utilizando apilar marcos. Esto nos da una especie de ilusión de que la variable local está limitada a una función específica.

Hay muchas formas de implementar variables locales mediante un sistema de tiempo de ejecución de lenguaje. El uso de una pila es una solución eficiente común, utilizada en muchos casos prácticos.

Intuitivamente, un puntero de pila spse mantiene en tiempo de ejecución (en una dirección fija o en un registro, realmente importa). Suponga que cada "inserción" incrementa el puntero de la pila.

En el momento de la compilación, el compilador determina la dirección de cada variable como sp - Kdónde Kes una constante que solo depende del alcance de la variable (por lo tanto, se puede calcular en tiempo de compilación).

Tenga en cuenta que estamos usando la palabra "apilar" aquí en un sentido laxo. A esta pila no solo se accede a través de operaciones push / pop / top, sino que también se accede mediante sp - K.

Por ejemplo, considere este pseudocódigo:

procedure f(int x, int y) {
  print(x,y);    // (1)
  if (...) {
    int z=x+y; // (2)
    print(x,y,z);  // (3)
  }
  print(x,y); // (4)
  return;
}

Cuando se llama al procedimiento, x,yse pueden pasar argumentos en la pila. Por simplicidad, suponga que la convención es la que llama xprimero, luego y.

Luego, el compilador en el punto (1) puede encontrar xat sp - 2y yat sp - 1.

En el punto (2), se introduce una nueva variable. El compilador genera código que suma x+y, es decir, lo que señala sp - 2y sp - 1, y empuja el resultado de la suma en la pila.

En el punto (3), zse imprime. El compilador sabe que es la última variable en alcance, por lo que es señalado por sp - 1. Esto ya no es y, ya que spcambió. Aún así, para imprimir yel compilador sabe que puede encontrarlo, en este ámbito, en sp - 2. Del mismo modo, xahora se encuentra en sp - 3.

En el punto (4), salimos del alcance. zaparece, y ynuevamente se encuentra en la dirección sp - 1, y xestá en sp - 2.

Cuando volvemos, fo la persona que llama aparece x,yde la pila.

Entonces, la computación Kpara el compilador es una cuestión de contar cuántas variables están en el alcance, aproximadamente. En el mundo real, esto es en realidad más complejo ya que no todas las variables tienen el mismo tamaño, por lo que el cálculo de Kes ligeramente más complejo. A veces, la pila también contiene la dirección de retorno, por flo Kque también debe "omitirla". Pero estos son tecnicismos.

Tenga en cuenta que, en algunos lenguajes de programación, las cosas pueden volverse aún más complejas si se deben manejar características más complejas. Por ejemplo, los procedimientos anidados requieren un análisis muy cuidadoso, ya que Kahora tiene que "omitir" muchas direcciones de retorno, especialmente si el procedimiento anidado es recursivo. Las funciones de cierre / lambdas / anónimas también requieren cierta atención para manejar las variables "capturadas". Aún así, el ejemplo anterior debería ilustrar la idea básica.

La idea más fácil es pensar en las variables como nombres fijos para las direcciones en la memoria. De hecho, algunos ensambladores muestran el código de la máquina de esa manera ("almacenar el valor 5 en la dirección i", donde ihay un nombre de variable).

Algunas de estas direcciones son "absolutas", como las variables globales, algunas son "relativas", como las variables locales. Las variables (es decir, las direcciones) en las funciones son relativas a algún lugar en la "pila" que es diferente para cada invocación de función; de esa manera, el mismo nombre puede referirse a diferentes objetos reales, y las llamadas circulares a la misma función son invocaciones independientes que funcionan en la memoria independiente.

Los elementos de datos que pueden ir a la pila se colocan en la pila. ¡Sí! Es un espacio premium. Además, una vez que empujamos xa la pila y luego empujamos ya la pila, idealmente no podemos acceder xhasta que yesté allí. Necesitamos hacer estallar ypara acceder x. Los tienes correctos.

La pila no es de variables, sino de frames

Donde te equivocaste es sobre la pila en sí. En la pila, no son los elementos de datos los que se envían directamente. Más bien, en la pila stack-framese empuja algo llamado . Este marco de pila contiene los elementos de datos. Si bien no puede acceder a los marcos en lo profundo de la pila, puede acceder al marco superior y a todos los elementos de datos contenidos en él.

Digamos que tenemos nuestros elementos de datos agrupados en dos marcos de pila frame-xy frame-y. Los empujamos uno tras otro. Ahora, siempre y cuando se frame-yencuentre encima frame-x, idealmente no puede acceder a ningún elemento de datos dentro frame-x. Solo frame-yes visible. PERO dado que frame-yes visible, puede acceder a todos los elementos de datos incluidos en él. La totalidad del marco es visible exponiendo todos los elementos de datos contenidos dentro.

Fin de la respuesta Más (despotricar) sobre estos marcos

Durante la compilación, se hace una lista de todas las funciones del programa. Luego, para cada función se hace una lista de elementos de datos apilables . Luego, para cada función stack-frame-templatese hace a. Esta plantilla es una estructura de datos que contiene todas las variables elegidas, el espacio para los datos de entrada de la función, los datos de salida, etc. Ahora, durante el tiempo de ejecución, siempre que una función se llama, una copia de esta templatese pone en la pila - junto con toda la entrada y variables intermedias . Cuando esta función llama a alguna otra función, se coloca una nueva copia de esa función stack-frameen la pila. Ahora, mientras esa función se esté ejecutando, los elementos de datos de esta función se conservarán. Una vez que finaliza esa función, se abre su marco de pila. Ahoraeste marco de pila está activo y esta función puede acceder a todas sus variables.

Tenga en cuenta que la estructura y composición de un marco de pila varía de un lenguaje de programación a otro. Incluso dentro de un lenguaje puede haber diferencias sutiles en diferentes implementaciones.

Gracias por considerar CS. Soy programador hoy en día tomando clases de piano :)