Warum wachsen Stapel normalerweise nach unten?

95

Ich weiß, dass in den Architekturen, mit denen ich persönlich vertraut bin (x86, 6502 usw.), der Stapel normalerweise nach unten wächst (dh jedes auf den Stapel geschobene Element führt zu einem dekrementierten SP, nicht zu einem inkrementierten).

Ich wundere mich über die historischen Gründe dafür. Ich weiß, dass es in einem einheitlichen Adressraum praktisch ist, den Stapel am gegenüberliegenden Ende des Datensegments zu starten (z. B.), sodass es nur dann ein Problem gibt, wenn die beiden Seiten in der Mitte kollidieren. Aber warum bekommt der Stapel traditionell den oberen Teil? Besonders wenn man bedenkt, wie das Gegenteil des "konzeptuellen" Modells ist?

(Beachten Sie, dass in der 6502-Architektur der Stapel auch nach unten wächst, obwohl er auf eine einzelne 256-Byte-Seite beschränkt ist und diese Richtungsauswahl willkürlich erscheint.)

Ben Zotto
quelle

Antworten:

52

Was die historische Begründung betrifft, kann ich nicht mit Sicherheit sagen (weil ich sie nicht entworfen habe). Meine Gedanken zu diesem Thema sind, dass frühe CPUs ihren ursprünglichen Programmzähler auf 0 gesetzt haben und es ein natürlicher Wunsch war, den Stack am anderen Ende zu starten und nach unten zu wachsen, da ihr Code natürlich nach oben wächst.

Beachten Sie außerdem, dass diese Einstellung des Programmzählers auf 0 beim Zurücksetzen nicht bei allen frühen CPUs der Fall ist . Zum Beispiel würde das Motorola 6809 den Programmzähler von Adressen abrufen, 0xfffe/fso dass Sie an einem beliebigen Ort laufen können, abhängig davon, was an dieser Adresse angegeben wurde (normalerweise, aber keineswegs auf ROM beschränkt).

Eines der ersten Dinge, die einige historische Systeme tun würden, wäre, den Speicher von oben zu scannen, bis ein Speicherort gefunden wurde, der denselben geschriebenen Wert zurückliest, damit er den tatsächlich installierten RAM kennt (z. B. einen z80 mit 64 KB Adressraum) hatte nicht unbedingt 64K oder RAM, tatsächlich wären 64K massiv gewesen in meinen frühen Tagen ). Sobald es die oberste tatsächliche Adresse gefunden hat, würde es den Stapelzeiger entsprechend setzen und könnte dann anfangen, Unterprogramme aufzurufen. Dieses Scannen wird im Allgemeinen durch den CPU-Ausführungscode im ROM als Teil des Startvorgangs durchgeführt.

In Bezug auf das Stapelwachstum wachsen nicht alle nach unten, siehe diese Antwort für Details.

paxdiablo
quelle
1
Ich mag die Strategie der Z80 RAM-Erkennungsstrategie. Es macht Sinn, dass Textsegmente nach oben wachsen - Programmierer von früher hatten etwas direkteren Kontakt mit den Auswirkungen davon als der Stapel. Danke paxdiablo. Der Zeiger auf die Menge alternativer Formen von Stapelimplementierungen ist ebenfalls sehr interessant.
Ben Zotto
Hat der frühe Speicher keine Möglichkeit, seine Größe zu benachrichtigen, und wir müssen ihn manuell berechnen?
Phuclv
1
@ LưuVĩnhPhúc, ich muss davon ausgehen, dass du eine Generation (oder zwei) hinter mir bist. Ich erinnere mich noch an die TRS-80 Modell 3-Methode, um Datum und Uhrzeit zu ermitteln und den Benutzer beim Booten danach zu fragen . Ein Speicherscanner zum Festlegen der Speicherobergrenze galt damals als Stand der Technik :-) Können Sie sich vorstellen, was passieren würde, wenn Windows bei jedem Start nach der Uhrzeit oder der Speicherkapazität fragen würde?
Paxdiablo
1
In der Zilog Z80-Dokumentation heißt es, dass das Teil gestartet wird, indem das PC-Register auf 0000h gesetzt und ausgeführt wird. Es setzt den Interrupt-Modus auf 0, deaktiviert Interrupts und setzt die I- und R-Register ebenfalls auf 0. Danach beginnt die Ausführung. Um 00:00 Uhr wird Code ausgeführt. DIESER Code muss den Stapelzeiger initialisieren, bevor er eine Unterroutine aufrufen oder Interrupts aktivieren kann. Welcher Anbieter verkauft einen Z80, der sich so verhält, wie Sie es beschreiben?
MikeB
1
Mike, sorry, ich hätte klarer sein sollen. Als ich sagte, dass die CPU den Speicher gescannt hat, meinte ich nicht, dass dies ein Merkmal der CPU selbst ist. Es wurde tatsächlich von einem Programm im ROM gesteuert. Ich werde klären.
Paxdiablo
21

Eine gute Erklärung, die ich gehört habe, war, dass einige Maschinen in der Vergangenheit nur vorzeichenlose Offsets haben konnten. Sie möchten also, dass der Stapel nach unten wächst, damit Sie Ihre Einheimischen treffen können, ohne die zusätzliche Anweisung verlieren zu müssen, um einen negativen Offset vorzutäuschen.

anq
quelle
7

Stanley Mazor (Architekt 4004 und 8080) erklärt in "Intel Microprocessors: 8008 to 8086" , wie die Stapelwachstumsrichtung für 8080 (und schließlich für 8086) gewählt wurde :

Der Stapelzeiger wurde so gewählt, dass er "bergab" läuft (wobei der Stapel in Richtung des unteren Speichers vorrückt), um die Indizierung in den Stapel aus dem Benutzerprogramm zu vereinfachen (positive Indizierung) und die Anzeige des Inhalts des Stapels von einer Frontplatte aus zu vereinfachen.

Roolebo
quelle
6

Ein möglicher Grund könnte sein, dass dies die Ausrichtung vereinfacht. Wenn Sie eine lokale Variable auf dem Stapel platzieren, die an einer 4-Byte-Grenze platziert werden muss, können Sie einfach die Größe des Objekts vom Stapelzeiger subtrahieren und dann die beiden unteren Bits auf Null setzen, um eine richtig ausgerichtete Adresse zu erhalten. Wenn der Stapel nach oben wächst, wird die Ausrichtung etwas schwieriger.

jalf
quelle
1
Computer subtrahieren nicht; Sie fügen in 2 Kompliment hinzu. Alles, was durch Subtrahieren gemacht wird, wird wirklich durch Addieren gemacht. Bedenken Sie, Computer haben Addierer, keine Subtrahierer.
JWW
1
@jww - das ist eine Unterscheidung ohne Unterschied. Ich könnte gut behaupten, Computer fügen nicht hinzu, sie subtrahieren nur! Für die Zwecke dieser Antwort spielt es keine Rolle - aber die meisten ALUs verwenden eine Schaltung , die sowohl Addition als auch Subtraktion mit derselben Leistung unterstützt. Das heißt, obwohl A - Bdies konzeptionell als A + (-B)(dh als separater Negationsschritt für B) implementiert werden könnte , ist dies in der Praxis nicht der Fall .
BeeOnRope
@jww Dein Nitpick ist falsch für frühe Computer - es hat einige Zeit gedauert, bis das Zweierkomplement gewonnen hat, und bis es das tat, gab es Computer, die das eigene Komplement und Vorzeichen und die Größe und vielleicht auch andere Dinge verwendeten. Bei diesen Implementierungen kann das Addieren gegenüber dem Subtrahieren durchaus von Vorteil gewesen sein. In Ermangelung zusätzlicher Informationen ist es daher falsch, dies als möglichen Faktor auszuschließen, der die Auswahl des Adressierungsschemas wie die Stapelrichtung beeinflusst.
mtraceur
4

IIRC wächst der Stapel nach unten, weil der Haufen nach oben wächst. Es hätte auch umgekehrt sein können.

Christian V.
quelle
5
Ein nach oben wachsender Heap ermöglicht in einigen Fällen eine effiziente Neuzuweisung, ein nach unten wachsender Heap jedoch so gut wie nie.
Peter Cordes
@ PeterCordes warum?
Yashas
3
@Yashas: weil nach einem Objekt realloc(3)mehr Platz benötigt wird, um das Mapping ohne Kopieren zu erweitern. Eine wiederholte Neuzuweisung desselben Objekts ist möglich, wenn eine beliebige Menge nicht genutzten Speicherplatzes folgt.
Peter Cordes
2

Ich glaube, es ist eine reine Designentscheidung. Nicht alle wachsen nach unten - in diesem SO-Thread finden Sie eine gute Diskussion über die Richtung des Stapelwachstums auf verschiedenen Architekturen.

Kaleb Brasee
quelle
1

Ich glaube, die Konvention begann mit der IBM 704 und ihrem berüchtigten "Dekrementregister". Die moderne Sprache würde es ein Versatzfeld der Anweisung nennen, aber der Punkt ist, dass sie nach unten und nicht nach oben gingen .

luser droog
quelle
1

Nur noch 2c:

Über alle erwähnten historischen Gründe hinaus bin ich mir ziemlich sicher, dass es keinen Grund gibt, der in modernen Prozessoren gültig ist. Alle Prozessoren können vorzeichenbehaftete Offsets verwenden, und die Maximierung des Heap / Stack-Abstands ist ziemlich umstritten, seit wir uns mit mehreren Threads befasst haben.

Ich persönlich halte dies für einen Sicherheitsfehler. Wenn beispielsweise die Designer der x64-Architektur die Stapelwachstumsrichtung umgekehrt hätten, wären die meisten Überläufe des Stapelpuffers beseitigt worden - was eine große Sache ist. (da die Saiten nach oben wachsen).

Ofek Shilon
quelle
0

Ich bin mir nicht sicher, aber ich habe damals einige Programmierungen für VAX / VMS durchgeführt. Ich scheine mich zu erinnern, wie ein Teil des Speichers (der Haufen ??) hoch und der Stapel runter ging. Als sich die beiden trafen, war dir das Gedächtnis ausgegangen.

Martin
quelle
1
Das ist wahr, aber warum wächst der Haufen dann nach oben und nicht umgekehrt?
Ciro Santilli 22 冠状 病 六四 事件 22
0

Ein Vorteil des absteigenden Stapelwachstums in einem minimalen eingebetteten System besteht darin, dass ein einzelner RAM-Block redundant sowohl auf Seite O als auch auf Seite 1 abgebildet werden kann, sodass ab 0x000 keine Seitenvariablen zugewiesen werden können und der Stapel von 0x1FF abwärts wächst, wodurch das maximiert wird Menge, die es wachsen müsste, bevor Variablen überschrieben werden.

Eines der ursprünglichen Entwurfsziele des 6502 war, dass er beispielsweise mit einem 6530 kombiniert werden konnte, was zu einem Zwei-Chip-Mikrocontrollersystem mit 1 KB Programm-ROM, Timer, E / A und 64 Byte gemeinsam genutztem RAM führte zwischen Stapel- und Seitennullvariablen. Im Vergleich dazu wäre das minimale eingebettete System dieser Zeit, das auf einem 8080 oder 6800 basiert, vier oder fünf Chips.

Mailand
quelle