stack - informatica - pilas estructura de datos ejemplos
¿Cuál es la dirección del crecimiento de la pila en la mayoría de los sistemas modernos? (7)
Crece porque la memoria asignada al programa tiene los "datos permanentes", es decir, el código para el programa en sí mismo en la parte inferior, y luego el montón en el medio. Necesitas otro punto fijo desde el que hacer referencia a la pila, por lo que te deja en la cima. Esto significa que la pila crece, hasta que es potencialmente adyacente a los objetos en el montón.
Estoy preparando algunos materiales de capacitación en C y quiero que mis ejemplos se ajusten al modelo de pila típico.
¿En qué dirección crece una pila C en Linux, Windows, Mac OSX (PPC y x86), Solaris y los Unix más recientes?
El crecimiento de la pila generalmente no depende del sistema operativo en sí, sino del procesador en el que se está ejecutando. Solaris, por ejemplo, se ejecuta en x86 y SPARC. Mac OSX (como usted mencionó) se ejecuta en PPC y x86. Linux funciona en todo, desde mi gran sistema System z en el trabajo hasta un pequeño reloj de pulsera .
Si la CPU ofrece algún tipo de opción, la convención ABI / llamada utilizada por el sistema operativo especifica qué opción debe realizar si desea que su código llame al código de todos los demás.
Los procesadores y su dirección son:
- x86: abajo.
- SPARC: seleccionable. El ABI estándar usa abajo.
- PPC: abajo, creo.
- System z: en una lista enlazada, no estoy bromeando (pero aún no, al menos para zLinux).
- ARM: seleccionable, pero Thumb2 tiene codificaciones compactas solo para abajo (LDMIA = incremento después, STMDB = decremento anterior).
- 6502: abajo (pero solo 256 bytes).
- RCA 1802A: de la forma que desee, sujeto a la implementación de SCRT.
- PDP11: abajo.
- 8051: arriba.
Mostrando mi edad en esos últimos pocos, el 1802 era el chip utilizado para controlar los primeros transbordadores (sospecho que si las puertas estaban abiertas, sospecho, en función del poder de procesamiento que tenía :-) y mi segunda computadora, el COMX-35 ( siguiendo mi ZX80 ).
Detalles de PDP11 recopilados here , 8051 detalles de here .
La arquitectura SPARC utiliza un modelo de registro de ventana deslizante. Los detalles arquitectónicamente visibles también incluyen un búfer circular de ventanas de registro que son válidas y se almacenan en caché internamente, con trampas cuando se sobrepasa / subdesborda. Mira here para más detalles. Como explica el manual SPARCv8, las instrucciones GUARDAR y RESTAURAR son como las instrucciones ADD más la rotación de la ventana de registro. Usar una constante positiva en lugar del negativo habitual daría una pila ascendente.
La técnica de SCRT antes mencionada es otra: el 1802 usó algunos o son dieciséis registros de 16 bits para SCRT (técnica estándar de llamada y devolución). Uno fue el contador del programa, puede usar cualquier registro como la PC con la instrucción SEP Rn . Uno era el puntero de la pila y dos se establecieron siempre para apuntar a la dirección del código SCRT, una para la llamada y otra para el retorno. Ningún registro fue tratado de una manera especial. Tenga en cuenta que estos detalles son de memoria, es posible que no sean totalmente correctos.
Por ejemplo, si R3 era la PC, R4 era la dirección de llamada SCRT, R5 era la dirección de retorno SCRT y R2 era la "pila" (citas tal como se implementa en el software), SEP R4 configuraría R4 para ser la PC y comenzaría a funcionar el código de llamada SCRT.
Luego almacenaría R3 en la "pila" R2 (creo que R6 se usó para el almacenamiento temporal), ajustándolo hacia arriba o hacia abajo, tomará los dos bytes siguientes a R3, los cargará en R3, luego hará SEP R3 y se ejecutará en el nuevo dirección.
Para volver, sería SEP R5 que sacaría la dirección anterior de la pila R2, agregaría dos (para omitir los bytes de dirección de la llamada), la cargaría en R3 y SEP R3 para comenzar a ejecutar el código anterior.
Muy difícil de entender al principio después de todo el código basado en la pila 6502/6809 / z80, pero sigue siendo elegante en una especie de bang-tu-cara contra la pared. También una de las grandes características de venta del chip fue un conjunto completo de 16 registros de 16 bits, a pesar de que de inmediato perdiste 7 de esos (5 para SCRT, dos para DMA e interrupciones de la memoria). Ahh, el triunfo del marketing sobre la realidad :-)
System z es en realidad bastante similar, utilizando sus registros R14 y R15 para llamada / devolución.
En C ++ (adaptable a C) stack.cc :
static int
find_stack_direction ()
{
static char *addr = 0;
auto char dummy;
if (addr == 0)
{
addr = &dummy;
return find_stack_direction ();
}
else
{
return ((&dummy > addr) ? 1 : -1);
}
}
En MIPS no hay instrucciones push / pop . Todos los impulsos / pops se realizan de forma explícita mediante load / store con respecto al puntero de pila y luego ajustan manualmente el puntero $sp . Sin embargo, como todos los registros (excepto $0 ) son de propósito general, en teoría cualquier registro puede ser un puntero de pila, y la pila puede crecer en cualquier dirección que desee el programador. MIPS ABIs típicamente crecen hacia abajo.
En Intel 8051, la pila crece, probablemente porque el espacio de memoria es tan pequeño (128 bytes en la versión original) que no hay un montón y no es necesario colocar la pila encima para que se separe del montón. desde la parte inferior.
En la mayoría de los sistemas, la pila crece y mi artículo en https://gist.github.com/cpq/8598782 explica POR QUÉ crece. La razón es que es el diseño óptimo de dos regiones de memoria en crecimiento (montón y pila).
La pila crece en x86 (definida por la arquitectura, el indicador de pila de incrementos incrementales, decrementos de inserción).
La ventaja de crecer hacia abajo es que en los sistemas más antiguos la pila generalmente estaba en la parte superior de la memoria. Los programas normalmente llenaban la memoria comenzando desde abajo, por lo que este tipo de gestión de memoria minimizaba la necesidad de medir y colocar la parte inferior de la pila en algún lugar sensato.