En ciencias de la computación, una pila de llamadas (en inglés call stack) es una estructura dinámica de datos LIFO, (una pila), que almacena la información sobre las subrutinas activas de un programa de computadora. Esta clase de pila también es conocido como una pila de ejecución, pila de control, pila de función, o pila de tiempo de ejecución, y a menudo se describe en forma corta como "la pila".
Una pila de llamadas es de uso frecuente para varios propósitos relacionados, pero la principal razón de su uso, es seguir el curso del punto al cual cada subrutina activa debe retornar el control cuando termine de ejecutar. (Las subrutinas activas son las que se han llamado pero todavía no han completado su ejecución ni retornando al lugar siguiente desde donde han sido llamadas). Si, por ejemplo, una subrutina DibujaCuadrado llama a una subrutina DibujaLinea desde cuatro lugares diferentes, el código de DibujaLinea debe tener una manera de saber a dónde retornar. Esto es típicamente hecho por un código que, para cada llamada dentro de DibujaCuadrado, pone la dirección de la instrucción después de la sentencia de llamada particular (la "dirección de retorno") en la pila de llamadas.
Puesto que la pila de llamadas se organiza como una pila, el programa que llama (a la subrutina) empuja (push) la dirección de retorno en la pila (la dirección en la que el programa continuará después de volver de la subrutina), y la subrutina llamada, cuando finaliza, retira (pop) la dirección de retorno de la pila de llamadas y transfiere el control a esa dirección. Si una subrutina llamada, llama a otra subrutina, la primera empuja (push) su dirección de retorno en la pila de llamadas, y así sucesivamente, con la información de direcciones de retorno apilándose y desapilándose como el programa dicte. Si el empujar (push) consume todo el espacio asignado para la pila de llamadas, ocurre un error llamado desbordamiento de pila. Agregando una entrada de subrutina a la pila de llamadas es a veces llamado bobinando o enrollando (winding); inversamente, la eliminación de entradas es llamado desenbobinando o desenrollando (unwinding).
Usualmente hay exactamente una pila de llamadas asociado a un programa en ejecución (o más precisamente, con cada tarea o hilo de un proceso), aunque pilas adicionales pueden ser creados para el manejo de señales o la multitarea cooperativa (como con setcontext). Puesto que hay solamente una pila en este importante contexto, puede ser referido como la pila (implícito, "de la tarea").
En lenguajes de programación de alto nivel, las características específicas de la pila de llamadas usualmente son ocultadas al programador. Ellos solo tienen acceso a la lista de funciones, y no a la memoria de la pila en sí misma. La mayoría de los lenguajes ensambladores, por una parte, requieren que los programas sean invocados con manipulación explícita de la pila. En un lenguaje de programación, los detalles reales de la pila dependen del compilador, del sistema operativo, y del conjunto de instrucciones disponible.
Según lo observado arriba, el propósito primario de una pila de llamadas es:
Una pila de llamadas puede servir para funciones adicionales, dependiendo del lenguaje, del sistema operativo, y del ambiente de la máquina. Entre ellos puede estar:
La pila de llamadas típica es usada para la dirección de retorno, variables locales, y los parámetros (conocido como el call frame). En algunos ambientes puede haber más o menos funciones asignadas a la pila de llamadas. En el lenguaje de programación Forth, por ejemplo, solamente la dirección de retorno y las variables locales son almacenadas en la pila de llamadas (que en ese ambiente es llamado la pila de retorno); los parámetros son almacenados en una pila de datos separado. La mayoría de los Forth también tiene una tercer pila para los parámetros de punto flotante.
Una pila de llamadas está compuesto de stack frames (marcos de pila) (a veces llamados registros de activación). Estos son estructuras de datos dependientes de la máquina que contienen la información de estado de la subrutina. Cada stack frame corresponde a una llamada a una subrutina que activa, es decir, que todavía no ha terminado con un retorno a quien la llamó. Por ejemplo, si una subrutina llamada DrawLine está corriendo actualmente, acabando de ser llamada por una subrutina DrawSquare, la parte superior de la pila de llamadas puede presentarse como esto (donde la pila está creciendo de abajo hacia arriba):
El stack frame en el tope de la pila (en verde) es para la rutina actualmente en ejecución (DrawLine). En el más común acercamiento para el stack frame e incluye:
La pila es a menudo accedida vía un registro llamado el puntero de pila (ver registro de pila), que también sirve para indicar al tope actual de la pila. Alternativamente, la memoria dentro del frame (marco) puede ser accedida vía un registro separado, a menudo llamado el frame pointer (puntero del frame), que típicamente apunta a un cierto lugar fijo en la estructura del frame, tal como la localización de la dirección de retorno.
Los stack frames no son todos del mismo tamaño. Diferentes subrutinas tienen diferente número de parámetros, de modo que esa parte del stack frame será diferente para diversas subrutinas, aunque usualmente es fijo a través de todas las activaciones de una subrutina particular. Similarmente, la cantidad de espacio necesario para las variables locales será diferente para diversas subrutinas. De hecho, algunos lenguajes soportan asignaciones dinámicas de memoria para las variables locales en la pila, en este caso el tamaño del área para las variables locales varía de una a otra activación de una subrutina, y no es conocida cuando es compilada la subrutina. En el último caso, el acceso vía un puntero de frame, en vez de a través del puntero de pila, es usualmente necesario puesto que los desplazamientos relativos (offsets) desde el tope de la pila a valores tales como la dirección de retorno no serían conocidas en tiempo de compilación.
En muchos sistemas un stack frame tiene un campo para contener el valor anterior del registro del puntero del frame, es decir, el valor que tenía con el programa, que llamó a la subrutina, mientras estaba ejecutándose. Por ejemplo, en el diagrama de arriba, el stack frame de DrawLine (en verde) tendría una posición de memoria manteniendo el valor del puntero del frame que DrawSquare (en azul) está utilizando. El valor es guardado al entrar en la subrutina y es restaurado pare el retorno. Tener tal campo en una localización conocida del stack frame permite que el código tenga acceso a cada frame sucesivamente por debajo el frame de la rutina actualmente en ejecución.
Los lenguajes de programación que soportan subrutinas anidadas tienen un campo en el frame de llamada que apunta al frame de llamada de la rutina externa que invocó la rutina (anidada) interna. Esto a veces llamado un display. Este apuntador proporciona a las rutinas internas (así como cualesquiera otras rutinas internas que pueda invocar) el acceso a los parámetros y las variables locales de la rutina externa (la que invoca). Algunos computadores, tales como los grandes sistemas de Burroughs, tienen "registros de display" especiales para soportar tales funciones anidadas.
Para algunos propósitos, el stack frame de una subrutina y el de la rutina que la llama pueden ser considerados como un solapado (overlap), el solapado consiste en el área donde los parámetros son pasados desde la rutina que llama a la rutina que es llamada. En algunos ambientes, la rutina que llama, empuja (push) cada argumento sobre la pila, extendiendo así su stack frame; después invoca a la subrutina (la cual usará esos parámetros). En otros ambientes, la rutina que llama tiene un área preasignada en el tope de su stack frame para mantener los argumentos que suministra a otras subrutinas que llama. Esta área a veces son llamadas el área de argumentos salientes o el callout area. Bajo este acercamiento, el tamaño del área es calculado por el compilador para ser la más grande necesaria para cualquier subrutina llamada.
La manipulación de la pila de llamadas que se necesita en el lugar donde se realiza la llamada a una subrutina es mínima (lo que es bueno puesto que pueden haber muchos lugares de donde se llama cada subrutina). Los valores para los argumentos reales son evaluados en el sitio de la llamada, puesto que son específicos para una particular llamada, y pueden ser o empujados (push) sobre la pila o colocados en los registros, según lo determinado por la convención de llamada utilizada. La instrucción de llamada real, tal como "Branch and link" es entonces típicamente ejecutada para transferir el control al código de la subrutina de destino.
En la subrutina que ha sido llamada, el primer código ejecutado es usualmente llamado el prólogo de la subrutina, puesto que hace el trabajo necesario antes de que comience el código para las sentencias de la rutina.
El prólogo comúnmente guardará la dirección de retorno, dejado en un registro por la instrucción de llamada, empujando (push) dicho valor sobre la pila de llamadas. Similarmente, los valores actuales del puntero de pila o del puntero del frame pueden ser empujados (push) a la pila. Alternativamente, algunas arquitecturas de conjunto de instrucciones, proporcionan automáticamente la funcionalidad comparable, como parte de la acción de la instrucción de llamada en sí misma, y en tal ambiente, el prólogo no necesita hacer esto.
Si están siendo usados los punteros de frame, el prólogo típicamente fijará el nuevo valor del registro del puntero de frame desde el puntero de pila. El espacio en la pila para las variables locales entonces puede ser asignado incrementalmente cambiando así al puntero de pila.
El lenguaje de programación Forth, permite el bobinado explícito de la pila de llamadas (llamada en Forth el «pila de retorno»). El lenguaje de programación del Scheme, permite el bobinado de frames especiales en la pila, a través de un «viento dinámico».
Cuando una subrutina está lista para retornar, ejecuta un epílogo que deshace los pasos del prólogo. Esto típicamente restaurará los valores de registros previamente guardados (tales como el valor del puntero del frame) tomándolos desde el frame de la pila, descargará (pop) todo el frame de la pila cambiando el valor del puntero de pila, y finalmente bifurcará a la instrucción indicada en la dirección de retorno. Bajo muchas convenciones de llamada, entre los elementos eliminados (pop) de la pila por el epílogo, incluyen los valores originales de los argumentos con que fue llamada la rutina, en este caso, usualmente no hay otras manipulaciones de la pila que necesiten ser hechas por la subrutina que llama. Sin embargo, con algunas convenciones de llamada, es la responsabilidad de la rutina que llama quitar los argumentos de la pila después del retorno.
El Retorno de la función llamada hará una remoción (pop) del frame en el tope de la pila, quizás dejando un valor de retorno.
Algunos lenguajes (como Pascal) permiten una sentencia goto global para transferir el control fuera de una función anidada y llevarlo hacia dentro de función externa previamente invocada. Esta operación requiere que la pila sea desenrolado, quitando tantos frames de pila como sea necesario para restaurar el contexto apropiado para transferir el control a la declaración de destino dentro de la función externa que la envuelve. Tales transferencias de control son generalmente usadas solo para el tratamiento de errores.
Otras lenguajes (tales como Object Pascal) proporcionan el manejo de excepciones, que también requiere desenrollar la pila. El stack frame de una función contiene una o más entradas que especifican manejadores de excepción. Cuando una excepción es lanzada, se desenrolla la pila hasta que es encontrado un manejador de excepción que esté preparado para manejar (catch) dicha excepción. El Common Lisp permite el control de lo qué sucede cuando la pila es desenrollada usando el operador especial unwind-protect.
Cuando se aplica una continuación, la pila es desenrollada y después rebobinado con la pila de la continuación. Esta no es la única manera de ejecutar continuaciones; por ejemplo, usando múltiples pilas explícitas, la aplicación de una continuación pueden simplemente activar su pila y enrollar un valor que será pasado.
Una técnica recientemente divulgada usa las pilas de llamadas en una manera diferente que otras discutidas en esta página. Se utiliza las pilas de llamadas para la reducción del juego de pruebas. Brevemente, la reducción del juego de pruebas busca reducir el número de casos de pruebas en un juego de pruebas mientras que retiene un alto porcentaje de la efectividad de la detección de falla del juego original. Dos casos de pruebas son considerados equivalentes si generan el mismo conjunto de pilas de llamadas durante la ejecución. Para más detalles, ver ().
Tomando muestras en tiempos aleatorios de la pila de llamadas puede ser muy útil para optimizar el desempeño de los programas. La razón es que si una instrucción de llamada a subrutina aparece en la pila de llamadas en una cierta fracción del tiempo de ejecución, su posible remoción pudiera ahorrar esa cantidad de tiempo. Ver análisis de desempeño y muestreo profundo.
La mezcla de los datos del flujo de control que afectan la ejecución del código (direcciones de retorno, punteros de frame guardados) y datos simples del programa (parámetros, valores de retorno) en una pila de llamadas es un riesgo de seguridad, posiblemente explotable por medio del desbordamiento de búfer (en el artículo son explicados el riesgo y el exploit).
Escribe un comentario o lo que quieras sobre Pila de retorno (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)