¿Por qué las pilas normalmente crecen hacia abajo?

95

Sé que en las arquitecturas con las que estoy familiarizado (x86, 6502, etc.), la pila normalmente crece hacia abajo (es decir, cada elemento que se introduce en la pila da como resultado un SP decrementado, no uno incrementado).

Me pregunto cuál es la razón histórica de esto. Sé que en un espacio de direcciones unificado, es conveniente comenzar la pila en el extremo opuesto del segmento de datos (digamos), por lo que solo hay un problema si los dos lados chocan en el medio. Pero, ¿por qué la pila obtiene tradicionalmente la parte superior? ¿Especialmente dado que esto es lo opuesto al modelo "conceptual"?

(Y tenga en cuenta que en la arquitectura 6502, la pila también crece hacia abajo, aunque está limitada a una sola página de 256 bytes, y esta elección de dirección parece arbitraria).

Ben Zotto
fuente

Respuestas:

52

En cuanto al fundamento histórico, no puedo decirlo con certeza (porque yo no los diseñé). Mi opinión al respecto es que las primeras CPU tenían su contador de programa original establecido en 0 y era un deseo natural comenzar la pila en el otro extremo y crecer hacia abajo, ya que su código crece naturalmente hacia arriba.

Además, tenga en cuenta que esta configuración del contador de programa en 0 en el reinicio no es el caso para todas las CPU anteriores. Por ejemplo, el Motorola 6809 obtendría el contador de programa de las direcciones 0xfffe/fpara que pudiera comenzar a ejecutar en una ubicación arbitraria, dependiendo de lo que se proporcionó en esa dirección (generalmente, pero de ninguna manera limitado a, ROM).

Una de las primeras cosas que harían algunos sistemas históricos sería escanear la memoria desde la parte superior hasta encontrar una ubicación que leyera el mismo valor escrito, de modo que supiera la RAM real instalada (por ejemplo, un z80 con espacio de direcciones de 64K no necesariamente tenía 64K o RAM, de hecho 64K habría sido masivo en mis primeros días). Una vez que encontrara la dirección real superior, configuraría el puntero de la pila de manera adecuada y podría comenzar a llamar a las subrutinas. Este escaneo generalmente lo realiza la CPU que ejecuta el código en la ROM como parte del inicio.

Con respecto al crecimiento de las pilas, no todas crecen hacia abajo, consulte esta respuesta para obtener más detalles.

paxdiablo
fuente
1
Me gusta la historia de la estrategia de detección de RAM Z80. Tiene algún sentido que los segmentos de texto se distribuyan hacia arriba: los programadores de antaño tenían un contacto algo más directo para lidiar con las implicaciones de eso que la pila. Gracias paxdiablo. El puntero al conjunto de formas alternativas de implementaciones de pila también es muy interesante.
Ben Zotto
¿No tiene la memoria de los primeros días una forma de notificar su tamaño y tenemos que calcularlo manualmente?
phuclv
1
@ LưuVĩnhPhúc, debo asumir que estás una generación (o dos) detrás de mí. Todavía recuerdo que el método TRS-80 modelo 3 para obtener la fecha y la hora era pedirlo al usuario en el momento del arranque. Tener un escáner de memoria para establecer el límite superior de la memoria se consideraba de vanguardia en su día :-) ¿Se imagina lo que sucedería si Windows preguntara la hora, o cuánta memoria tenía, cada vez que arrancaba?
paxdiablo
1
De hecho, la documentación de Zilog Z80 dice que la pieza se inicia configurando el registro de la PC en 0000h y ejecutándose. Establece el modo de interrupción en 0, deshabilita las interrupciones y también establece los registros I y R en 0. Después de eso, comienza a ejecutarse. A las 0000h, comienza a ejecutar código. ESE código tiene que inicializar el puntero de la pila antes de que pueda llamar a una subrutina o habilitar interrupciones. ¿Qué proveedor vende un Z80 que se comporta como usted lo describe?
MikeB
1
Mike, lo siento, debería haber sido más claro. Cuando dije que la CPU escaneaba la memoria, no quise decir que fuera una característica de la CPU en sí. En realidad, se controlaba desde un programa en ROM. Te lo aclaro.
paxdiablo
21

Una buena explicación que escuché fue que algunas máquinas en el pasado solo podían tener compensaciones sin firmar, por lo que querría que la pila creciera hacia abajo para poder golpear a sus locales sin tener que perder la instrucción adicional para simular una compensación negativa.

anq
fuente
7

Stanley Mazor (arquitecto de 4004 y 8080) explica cómo se eligió la dirección de crecimiento de la pila para 8080 (y eventualmente para 8086) en "Microprocesadores Intel: 8008 a 8086" :

El puntero de la pila se eligió para funcionar "cuesta abajo" (con la pila avanzando hacia la memoria inferior) para simplificar la indexación en la pila desde el programa del usuario (indexación positiva) y para simplificar la visualización del contenido de la pila desde un panel frontal.

roolebo
fuente
6

Una posible razón podría ser que simplifica la alineación. Si coloca una variable local en la pila que debe colocarse en un límite de 4 bytes, simplemente puede restar el tamaño del objeto del puntero de la pila y luego poner a cero los dos bits inferiores para obtener una dirección alineada correctamente. Si la pila crece hacia arriba, asegurar la alineación se vuelve un poco más complicado.

jalf
fuente
1
Las computadoras no restan; añaden el cumplido de 2. Todo lo que se hace restando se hace realmente sumando. Considere, las computadoras tienen sumadores, no resta.
jww
1
@jww - esa es una distinción sin diferencia. ¡Bien podría haber dicho que las computadoras no suman, solo restan! Para los propósitos de esta respuesta, realmente no importa, pero la mayoría de las ALU usarán un circuito que admita tanto la suma como la resta con el mismo rendimiento. Es decir, si bien A - Bpodría implementarse conceptualmente como A + (-B)(es decir, un paso de negación separado para B), no lo es en la práctica.
BeeOnRope
@jww Tu nitpick es incorrecto para las primeras computadoras: tomó algún tiempo para que el complemento a dos ganara, y hasta que lo hizo, había computadoras que usaban el complemento y el signo y la magnitud de uno y tal vez otras cosas en su lugar. Con esas implementaciones, bien puede haber una ventaja en sumar frente a restar. Por lo tanto, en ausencia de información adicional, es incorrecto descartar esto como un posible factor que influye en las opciones del esquema de direccionamiento, como la dirección de la pila.
mtraceur
4

IIRC la pila crece hacia abajo porque el montón crece hacia arriba. Podría haber sido al revés.

Cristiano v
fuente
5
Un montón de crecimiento ascendente permite una reasignación eficiente en algunos casos, pero un montón de crecimiento descendente prácticamente nunca lo hace.
Peter Cordes
@PeterCordes ¿por qué?
Yashas
3
@Yashas: porque realloc(3)necesita más espacio después de un objeto para simplemente extender el mapeo sin copiar. La reasignación repetida del mismo objeto es posible cuando le sigue una cantidad arbitraria de espacio no utilizado.
Peter Cordes
2

Creo que es puramente una decisión de diseño. No todos crecen hacia abajo: consulte este hilo SO para obtener una buena discusión sobre la dirección del crecimiento de la pila en diferentes arquitecturas.

Kaleb Brasee
fuente
1

Creo que la convención comenzó con el IBM 704 y su infame "registro de decremento". El habla moderna lo llamaría un campo de compensación de la instrucción, pero el punto es que bajaron , no subieron .

luser droog
fuente
1

Solo 2c más:

Más allá de todas las razones históricas mencionadas, estoy bastante seguro de que no hay ninguna razón válida en los procesadores modernos. Todos los procesadores pueden tomar compensaciones firmadas, y maximizar la distancia de pila / pila es bastante discutible desde que comenzamos a trabajar con múltiples subprocesos.

Personalmente, considero que esto es un error de diseño de seguridad. Si, digamos, los diseñadores de la arquitectura x64 hubieran invertido la dirección del crecimiento de la pila, la mayoría de los desbordamientos del búfer de pila se habrían eliminado, lo cual es un gran problema. (ya que las cuerdas crecen hacia arriba).

Ofek Shilon
fuente
0

No estoy seguro, pero hice algo de programación para VAX / VMS en el pasado. Me parece recordar una parte de la memoria (¿el montón?) Subiendo y bajando la pila. Cuando los dos se conocieron, entonces te quedaste sin memoria.

Martín
fuente
1
Esto es cierto, pero entonces ¿por qué el montón crece hacia arriba y no al revés?
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
0

Una ventaja del crecimiento de la pila descendente en un sistema integrado mínimo es que una sola porción de RAM se puede mapear de forma redundante tanto en la página O como en la página 1, lo que permite que se asignen cero variables de página a partir de 0x000 y que la pila crezca hacia abajo desde 0x1FF, maximizando la cantidad que tendría que crecer antes de sobrescribir las variables.

Uno de los objetivos de diseño originales del 6502 era que podía combinarse con, por ejemplo, un 6530, lo que da como resultado un sistema de microcontrolador de dos chips con 1 KB de ROM de programa, temporizador, E / S y 64 bytes de RAM compartidos. entre las variables de pila y página cero. En comparación, el sistema integrado mínimo de esa época basado en un 8080 o 6800 sería de cuatro o cinco chips.

Milán
fuente