Sind Stacks der einzig sinnvolle Weg, um Programme zu strukturieren?

74

Die meisten Architekturen, die ich gesehen habe, basieren auf einem Aufrufstapel, um den Kontext vor Funktionsaufrufen zu speichern / wiederherzustellen. Es ist ein so verbreitetes Paradigma, dass Push- und Pop-Operationen in den meisten Prozessoren integriert sind. Gibt es Systeme, die ohne Stack funktionieren? Wenn ja, wie funktionieren sie und wofür werden sie verwendet?

ConditionRacer
quelle
5
Angesichts der Tatsache, wie sich Funktionen in C-ähnlichen Sprachen verhalten sollen (dh Sie können Aufrufe so tief verschachteln, wie Sie möchten, und in umgekehrter Reihenfolge zurückkehren), ist mir nicht klar, wie man Funktionsaufrufe implementieren könnte , ohne dass dies unglaublich wäre ineffizient. Sie könnten zB den Programmierer zwingen, einen Continuation-Passing-Stil oder eine andere bizarre Form der Programmierung zu verwenden, aber aus irgendeinem Grund scheint niemand wirklich sehr viel mit CPS auf der niedrigen Ebene zu arbeiten.
Kevin
5
GLSL funktioniert ohne Stapel (wie auch andere Sprachen in dieser speziellen Klammer). Rekursive Aufrufe werden einfach nicht zugelassen.
Leushenko
3
Möglicherweise möchten Sie auch Registerfenster untersuchen , die von einigen RISC-Architekturen verwendet werden.
Mark Booth
2
@ Kevin: "Frühe FORTRAN-Compiler unterstützten keine Rekursion in Subroutinen. Frühe Computerarchitekturen unterstützten kein Konzept eines Stacks, und wenn sie Subroutinenaufrufe direkt unterstützten, wurde der Rücksprungort oft an einem festen Ort neben dem Subroutinencode gespeichert, was auch der Fall ist nicht zulassen, dass eine Subroutine erneut aufgerufen wird, bevor ein vorheriger Aufruf der Subroutine zurückgekehrt ist. Obwohl in Fortran 77 nicht angegeben, unterstützten viele F77-Compiler die Rekursion als Option, während sie in Fortran 90 zum Standard wurde. " en.wikipedia.org/wiki/Fortran#FORTRAN_II
Mooing Duck
3
Der P8X32A-Mikrocontroller ("Propeller") kennt in seiner Standard-Assemblersprache (PASM) kein Stack-Konzept. Die Anweisungen, die für das Springen verantwortlich sind, modifizieren sich auch selbst, um zu bestimmen, wohin zurückgekehrt werden soll - was beliebig gewählt werden kann. Interessanterweise weist die "Spin" -Sprache (eine interpretierte Hochsprache, die auf demselben Chip ausgeführt wird) eine traditionelle Stapelsemantik auf.
Wossname

Antworten:

50

Eine (etwas) beliebte Alternative zu einem Call-Stack sind Fortsetzungen .

Die Parrot-VM basiert beispielsweise auf Fortsetzungen. Es ist vollständig stapelfrei: Daten werden in Registern gespeichert (wie Dalvik oder LuaVM, Parrot ist registergestützt), und der Kontrollfluss wird mit Fortsetzungen dargestellt (im Gegensatz zu Dalvik oder LuaVM, die über einen Aufrufstapel verfügen).

Eine weitere beliebte Datenstruktur, die in der Regel von Smalltalk- und Lisp-VMs verwendet wird, ist der Spaghetti-Stack, der einem Netzwerk von Stacks ähnelt.

Wie @rwong hervorhob, ist der Continuation-Passing-Stil eine Alternative zu einem Call-Stack. Programme, die im Continuation-Passing-Stil geschrieben (oder in diesen transformiert) wurden, kehren nie zurück, sodass kein Stapel erforderlich ist.

Beantworten Sie Ihre Frage aus einer anderen Perspektive: Es ist möglich, einen Aufrufstapel ohne einen separaten Stapel zu haben, indem Sie die Stapelrahmen auf dem Heap zuweisen. Einige Lisp- und Scheme-Implementierungen tun dies.

Jörg W. Mittag
quelle
4
Dies hängt von Ihrer Definition eines Stapels ab. Ich bin mir nicht sicher, ob eine verknüpfte Liste (oder ein Array von Zeigern auf oder ...) von Stapelrahmen so viel "kein Stapel" ist wie "eine andere Darstellung eines Stapels". Programme in CPS-Sprachen (in der Praxis) tendieren dazu, effektiv verknüpfte Listen von Fortsetzungen zu erstellen, die den Stapeln sehr ähnlich sind für die Effizienz).
Jonathan Cast
6
" Programme, die im Continuation-Passing-Stil geschrieben (oder in diesen umgewandelt) wurden, kehren nie zurück " ... klingt bedrohlich.
Rob Penridge
5
@ RobPenridge: Es ist ein bisschen kryptisch, da stimme ich zu. CPS bedeutet, dass Funktionen, anstatt zurückzukehren, als zusätzliches Argument eine andere Funktion verwenden, die nach Abschluss ihrer Arbeit aufgerufen werden soll. Wenn Sie also eine Funktion aufrufen und nach dem Aufrufen der Funktion eine andere Arbeit ausführen müssen, anstatt auf die Rückkehr der Funktion zu warten und dann mit Ihrer Arbeit fortzufahren, wickeln Sie die verbleibende Arbeit ab ("die Fortsetzung"). ) in eine Funktion und übergeben Sie diese Funktion als zusätzliches Argument. Die von Ihnen aufgerufene Funktion ruft dann diese Funktion auf, anstatt zurückzukehren, und so weiter und so fort. Keine Funktion kehrt zurück, nur
Jörg W Mittag
3
… Ruft die nächste Funktion auf. Daher benötigen Sie keinen Aufrufstapel, da Sie den Bindungsstatus einer zuvor aufgerufenen Funktion niemals wiederherstellen müssen. Anstatt den vergangenen Zustand mit sich herumzutragen, damit Sie zu ihm zurückkehren können, tragen Sie den zukünftigen Zustand mit sich herum , wenn Sie so wollen.
Jörg W Mittag
1
@jcast: Das definierende Merkmal eines Stacks ist IMO, dass Sie nur auf das oberste Element zugreifen können. Eine Liste von Fortsetzungen, OTOH, gibt Ihnen Zugriff auf alle Fortsetzungen und nicht nur auf den obersten Stackframe. Wenn Sie beispielsweise wiederaufnehmbare Ausnahmen im Smalltalk-Stil haben, müssen Sie in der Lage sein, den Stapel zu durchlaufen, ohne ihn zu öffnen. Und wenn Fortsetzungen in der Sprache vorhanden sind und trotzdem die bekannte Idee eines Aufrufstapels beibehalten werden soll, entstehen Spaghetti-Stapel, bei denen Fortsetzungen den Stapel "aufteilen".
Jörg W Mittag
36

Früher hatten Prozessoren keine Stapelanweisungen, und Programmiersprachen unterstützten keine Rekursion. Im Laufe der Zeit unterstützen immer mehr Sprachen die Rekursion und die Hardware-Suite mit Funktionen zur Stapelrahmenzuweisung. Diese Unterstützung war im Laufe der Jahre bei verschiedenen Prozessoren sehr unterschiedlich. Einige Prozessoren verwendeten Stapelrahmen- und / oder Stapelzeigerregister; Einige übernommene Befehle, die die Zuweisung von Stapelrahmen in einem einzigen Befehl ausführen würden.

Ein entscheidender Vorteil des Stacks ist die Cache-Lokalität, da Prozessoren erst mit Caches auf einer Ebene und dann mit Caches auf mehreren Ebenen aufwarten. Die Spitze des Stapels befindet sich fast immer im Cache. Wann immer Sie etwas tun können, das eine hohe Cache-Trefferrate aufweist, sind Sie mit modernen Prozessoren auf dem richtigen Weg. Der auf den Stack angewendete Cache bedeutet, dass sich lokale Variablen, Parameter usw. fast immer im Cache befinden und das höchste Leistungsniveau aufweisen.

Kurz gesagt, die Verwendung des Stacks hat sich sowohl in der Hardware als auch in der Software entwickelt. Es gibt andere Modelle (z. B. wurde Datenflussberechnung über einen längeren Zeitraum versucht), die Lokalität des Stapels macht es jedoch sehr gut. Außerdem ist prozeduraler Code genau das, was Prozessoren für die Leistung benötigen: Eine Anweisung gibt an, was nach der anderen zu tun ist. Wenn die Anweisungen nicht in linearer Reihenfolge vorliegen, verlangsamt sich der Prozessor, zumindest bis jetzt, enorm, da wir nicht herausgefunden haben, wie der Direktzugriff so schnell wie der sequentielle Zugriff erfolgen kann. (Übrigens gibt es auf jeder Speicherebene ähnliche Probleme, vom Cache über den Hauptspeicher bis hin zur Disc ...)

Zwischen der nachgewiesenen Leistung von sequentiellen Zugriffsanweisungen und dem vorteilhaften Caching-Verhalten des Aufrufstapels haben wir zumindest derzeit ein gewinnendes Leistungsmodell.

(Wir könnten auch die Veränderbarkeit von Datenstrukturen in die Werke werfen ...)

Dies bedeutet nicht, dass andere Programmiermodelle nicht funktionieren, insbesondere wenn sie in die sequentiellen Anweisungen und das Call-Stack-Modell der heutigen Hardware übersetzt werden können. Es gibt jedoch einen deutlichen Vorteil für Modelle, die unterstützen, wo sich die Hardware befindet. Die Dinge bleiben jedoch nicht immer gleich, sodass wir in Zukunft Änderungen sehen können, da verschiedene Speicher- und Transistortechnologien mehr Parallelität ermöglichen. Es ist immer eine Scherze zwischen Programmiersprachen und Hardware-Fähigkeiten, also werden wir sehen!

Erik Eidt
quelle
9
Tatsächlich haben GPUs überhaupt noch keine Stapel. Es ist dir verboten, in GLSL / SPIR-V / OpenCL zu rekursieren (nicht sicher in Bezug auf HLSL, aber ich sehe wahrscheinlich keinen Grund, warum es anders wäre). Die Art und Weise, wie sie Funktionsaufruf- "Stapel" behandeln, ist die Verwendung einer absurd großen Anzahl von Registern.
LinearZoetrope
@Jsor: Das ist zu einem großen Teil ein Implementierungsdetail, wie aus der SPARC-Architektur hervorgeht. Wie Ihre GPUs verfügt SPARC über einen riesigen Registersatz, ist jedoch insofern einzigartig, als es ein Schiebefenster hat, das beim Umlauf die sehr alten Register auf einen Stapel im RAM überträgt. Es ist also wirklich ein Hybrid zwischen den beiden Modellen. Und SPARC hat nicht genau angegeben, wie viele physische Register vorhanden sind, wie groß das Registerfenster ist, sodass bei jedem Funktionsaufruf überall auf dieser Skala von "sehr vielen Registern" bis "gerade genug für ein Fenster" unterschiedliche Implementierungen möglich sind verschütten direkt zu stapeln "
MSalters
Eine Kehrseite des Call-Stack-Modells ist, dass Array und / oder Adressüberlauf sehr sorgfältig überwacht werden müssen, da selbstmodifizierende Programme als Exploit möglich sind, wenn beliebige Bits des Heaps ausführbar sind.
BenPen
14

TL; DR

  • Aufrufliste als Funktionsaufrufmechanismus:
    1. Wird in der Regel durch Hardware simuliert, ist jedoch für den Hardwareaufbau nicht von grundlegender Bedeutung
    2. Ist von grundlegender Bedeutung für die imperative Programmierung
    3. Ist nicht grundlegend für die funktionale Programmierung
  • Stapel als Abstraktion von "last-in, first-out" (LIFO) ist für die Informatik, Algorithmen und sogar einige nichttechnische Bereiche von grundlegender Bedeutung.
  • Einige Beispiele für die Programmorganisation, die keine Aufrufstapel verwenden:
    • Continuation-Passing-Stil (CPS)
    • Zustandsmaschine - eine riesige Schleife, in die alles eingearbeitet ist. (Angeblich von der Saab Gripen-Firmware-Architektur inspiriert, einer Mitteilung von Henry Spencer zugeschrieben und von John Carmack reproduziert.) (Anmerkung 1)
    • Datenflussarchitektur - ein Netzwerk von Akteuren, die durch Warteschlangen verbunden sind (FIFO). Die Warteschlangen werden manchmal als Kanäle bezeichnet.

Der Rest dieser Antwort ist eine zufällige Ansammlung von Gedanken und Anekdoten und daher etwas unorganisiert.


Der Stapel, den Sie (als Funktionsaufrufmechanismus) beschrieben haben, ist spezifisch für die imperative Programmierung.

Unterhalb der erforderlichen Programmierung finden Sie den Maschinencode. Maschinencode kann den Aufrufstapel durch Ausführen einer kleinen Folge von Anweisungen emulieren.

Unterhalb des Maschinencodes finden Sie die Hardware, die für die Ausführung der Software verantwortlich ist. Während der moderne Mikroprozessor zu komplex ist, um hier beschrieben zu werden, kann man sich vorstellen, dass ein sehr einfacher Entwurf existiert, der langsam ist, aber immer noch denselben Maschinencode ausführen kann. Solch ein einfaches Design nutzt die Grundelemente der digitalen Logik:

  1. Kombinierte Logik, dh eine Verbindung von logischen Gattern (und / oder nicht ...) Beachten Sie, dass "kombinierte Logik" Rückkopplungen ausschließt.
  2. Speicher, dh Flip-Flops, Latches, Register, SRAM, DRAM usw.
  3. Eine Zustandsmaschine, die aus einer kombinatorischen Logik und einem Speicher besteht, der gerade ausreicht, um einen "Controller" zu implementieren, der den Rest der Hardware verwaltet.

Die folgenden Diskussionen enthielten zahlreiche Beispiele für alternative Arten der Strukturierung von Imperativprogrammen.

Die Struktur eines solchen Programms sieht folgendermaßen aus:

void main(void)
{
    do
    {
        // validate inputs for task 1
        // execute task 1, inlined, 
        // must complete in a deterministically short amount of time
        // and limited to a statically allocated amount of memory
        // ...
        // validate inputs for task 2
        // execute task 2, inlined
        // ...
        // validate inputs for task N
        // execute task N, inlined
    }
    while (true);
    // if this line is reached, tell the programmers to prepare
    // themselves to appear before an accident investigation board.
    return 0; 
}

Dieser Stil ist für Mikrocontroller geeignet, dh für diejenigen, die die Software als Ergänzung zu den Funktionen der Hardware betrachten.


rwong
quelle
@Peteris: Stacks sind LIFO-Datenstrukturen.
Christopher Creutzig
1
Interessant. Ich hätte es umgekehrt gedacht. Beispielsweise ist FORTRAN eine zwingende Programmiersprache, und in früheren Versionen wurde kein Aufrufstapel verwendet. Die Rekursion ist jedoch für die funktionale Programmierung von grundlegender Bedeutung, und ich denke nicht, dass sie im allgemeinen Fall ohne Verwendung eines Stacks implementiert werden kann.
TED
@TED ​​- In einer funktionalen Sprachimplementierung gibt es eine Stapel- (oder normalerweise eine Baum-) Datenstruktur, die ausstehende Berechnungen darstellt, die Sie jedoch nicht unbedingt mit Anweisungen ausführen, die die stapelorientierten Adressierungsmodi des Computers oder sogar die Aufruf- / Rückgabeanweisungen verwenden (verschachtelt / rekursiv - möglicherweise nur als Teil einer Zustandsmaschinenschleife).
Davidbak
@davidbak - IIRC, ein rekursiver Algorithmus muss ziemlich rekursiv sein, um den Stack loszuwerden. Es gibt wahrscheinlich einige andere Fälle, in denen Sie es optimieren könnten, aber im Allgemeinen müssen Sie einen Stack haben . Tatsächlich wurde mir gesagt, dass es einen mathematischen Beweis dafür gibt, dass dies irgendwo herumschwirrt. Diese Antwort behauptet, es sei das Church-Turing-Theorem (ich glaube, basierend auf der Tatsache, dass Turing-Maschinen einen Stapel verwenden?)
TED
1
@TED ​​- Ich stimme dir zu. Ich glaube, die Fehlkommunikation hier ist, dass ich den Beitrag des OP gelesen habe, um über die Systemarchitektur zu sprechen , die für mich Maschinenarchitektur bedeutete . Ich denke, andere, die hier geantwortet haben, haben das gleiche Verständnis. Diejenigen von uns, die verstanden haben, dass dies der Kontext ist, haben mit der Antwort geantwortet, dass Sie auf der Ebene der Maschinenbefehle / Adressierungsmodi keinen Stapel benötigen. Aber ich kann sehen, dass die Frage auch so interpretiert werden kann, dass lediglich ein Sprachsystem im Allgemeinen einen Aufrufstapel benötigt. Diese Antwort ist auch nein, aber aus verschiedenen Gründen.
Davidbak
11

Nein, nicht unbedingt.

Lesen Sie Appels Garbage Collection- Altpapier kann schneller sein als die Stapelzuweisung . Es verwendet Continuation-Passing-Stil und zeigt eine stapellose Implementierung.

Beachten Sie auch, dass alte Computerarchitekturen (z. B. IBM / 360 ) kein Hardware-Stack-Register hatten. Aber das O und Compiler reservierten ein Register für den Stapelzeiger durch Konvention (bezogen auf Aufrufkonventionen ) , so dass sie einen Software haben könnten Call - Stack .

Im Prinzip kann ein C-Compiler und -Optimierer des gesamten Programms den Fall erkennen (was bei eingebetteten Systemen häufig vorkommt), dass der Aufrufgraph statisch bekannt ist und keine Rekursion (oder Funktionszeiger) aufweist. In einem solchen System konnte jede Funktion ihre Absenderadresse an einem festen statischen Ort aufbewahren (und so funktionierte Fortran77 in den 1970er Jahren).

Heutzutage haben Prozessoren auch Aufrufstapel (und Anweisungen zum Aufrufen und Zurückgeben von Maschinen), die sich der CPU-Caches bewusst sind .

Basile Starynkevitch
quelle
1
Ziemlich sicher, dass FORTRAN die Verwendung statischer Rückgabeorte eingestellt hat, als FORTRAN-66 herauskam und Unterstützung für SUBROUTINEund benötigte FUNCTION. Sie sind jedoch korrekt für frühere Versionen (FORTRAN-IV und möglicherweise WATFIV).
TMN
Und COBOL natürlich. Und ein hervorragender Punkt zu IBM / 360: Es wurde ziemlich häufig verwendet, obwohl die Adressierungsmodi des Hardware-Stacks fehlten. (R14, ich glaube es war?) Und es hatte Compiler für Stack-basierte Sprachen, zB PL / I, Ada, Algol, C.
Davidbak
Tatsächlich habe ich das 360 im College studiert und fand es zuerst verwirrend.
JDługosz
1
@ JDługosz Der beste Weg für moderne Studenten der Computerarchitektur, die 360 ​​zu betrachten, ist eine sehr einfache RISC-Maschine ... wenn auch mit mehr als einem Befehlsformat ... und ein paar Anomalien wie TRund TRT.
Davidbak
Wie wäre es mit "Null und gepackt hinzufügen", um ein Register zu verschieben? Aber "Branch and Link" statt Stack für Absenderadresse hat ein Comeback gemacht.
JDługosz
10

Sie haben bis jetzt einige gute Antworten; Lassen Sie mich Ihnen ein unpraktisches, aber sehr lehrreiches Beispiel dafür geben, wie Sie eine Sprache ohne den Begriff Stapel oder "Kontrollfluss" überhaupt entwerfen können. Hier ist ein Programm, das Fakultäten ermittelt:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = f(3)

Wir setzen dieses Programm in eine Zeichenfolge und bewerten das Programm durch Textsubstitution. Wenn wir also auswerten f(3), führen wir eine Suche durch und ersetzen sie durch 3 für i, wie folgt:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = if 3 == 0 then 1 else 3 * f(3 - 1)

Toll. Jetzt führen wir eine weitere Textsubstitution durch: Wir stellen fest, dass die Bedingung des "if" falsch ist, und ersetzen eine weitere Zeichenfolge, wodurch das Programm erzeugt wird:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(3 - 1)

Jetzt ersetzen wir alle Unterausdrücke mit Konstanten durch einen anderen String:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(2)

Und Sie sehen, wie das geht; Ich werde nicht weiter darauf eingehen. Wir könnten so lange eine Reihe von Saitensubstitutionen durchführen, bis wir let x = 6fertig sind.

Wir verwenden den Stack traditionell für lokale Variablen und Fortsetzungsinformationen. Denken Sie daran, ein Stapel sagt Ihnen nicht, woher Sie gekommen sind, sondern wohin Sie mit diesem Rückgabewert als Nächstes gehen.

Im Zeichenfolgensubstitutionsmodell der Programmierung befinden sich keine "lokalen Variablen" auf dem Stapel. Die formalen Parameter werden durch ihre Werte ersetzt, wenn die Funktion auf ihr Argument angewendet wird, anstatt in eine Nachschlagetabelle auf dem Stapel abgelegt zu werden. Und es gibt kein "irgendwohin als nächstes", weil die Programmbewertung einfach einfache Regeln für die String-Ersetzung anwendet, um ein anderes, aber gleichwertiges Programm zu erstellen.

Natürlich ist das Ersetzen von Strings nicht der richtige Weg. Aber Programmiersprachen, die "Gleichheitsdenken" unterstützen (wie Haskell), verwenden logischerweise diese Technik.

Eric Lippert
quelle
3
Retina ist ein Beispiel für eine Regex-basierte Programmiersprache, die Zeichenfolgenoperationen zur Berechnung verwendet.
Andrew Piliser
2
@ AndrewPiliser Entworfen und implementiert von diesem coolen Typen .
Katze
3

Seit der Veröffentlichung von " Über die Kriterien für die Zerlegung von Systemen in Module" durch Parnas im Jahr 1972 wurde vernünftigerweise akzeptiert, dass in Software versteckte Informationen eine gute Sache sind. Dies folgt auf eine lange Debatte in den 60er Jahren über strukturelle Zersetzung und modulare Programmierung.

Modularität

Ein notwendiges Ergebnis von Black-Box-Beziehungen zwischen Modulen, die von verschiedenen Gruppen in einem Multithread-System implementiert werden, erfordert einen Mechanismus, der einen Wiedereintritt ermöglicht, und ein Mittel zum Verfolgen des dynamischen Aufrufgraphen des Systems. Der kontrollierte Ausführungsfluss muss in mehrere Module hinein und aus diesen heraus gehen.

Dynamisches Scoping

Sobald das lexikalische Scoping nicht ausreicht, um das dynamische Verhalten zu verfolgen, ist eine gewisse Laufzeitbuchhaltung erforderlich, um den Unterschied zu verfolgen.

Wenn ein Thread (per Definition) nur einen einzigen aktuellen Befehlszeiger hat, ist ein LIFO-Stack geeignet, um jeden Aufruf zu verfolgen.

Ausnahmen

Während das Fortsetzungsmodell keine explizite Datenstruktur für den Stapel verwaltet, gibt es dennoch den verschachtelten Aufruf von Modulen, die irgendwo verwaltet werden müssen!

Selbst deklarative Sprachen behalten entweder den Evaluierungsverlauf bei oder reduzieren den Ausführungsplan aus Leistungsgründen und halten den Fortschritt auf andere Weise aufrecht.

Die von rwong identifizierte Endlosschleifenstruktur ist in Anwendungen mit hoher Zuverlässigkeit und statischer Planung üblich, die viele übliche Programmierstrukturen nicht zulassen, jedoch erfordern, dass die gesamte Anwendung als White Box ohne signifikante versteckte Informationen betrachtet wird.

Mehrere gleichzeitige Endlosschleifen erfordern keine Struktur zum Speichern von Rücksprungadressen, da sie keine Funktionen aufrufen, was die Frage zur Diskussion stellt. Wenn sie mit gemeinsam genutzten Variablen kommunizieren, können diese leicht zu älteren analogen Absenderadressen im Fortran-Stil ausarten.

Pekka
quelle
1
Sie malen sie in einer Ecke von „unter der Annahme , jedes Multi-Threaded - System“. Gekoppelte Finite-State-Maschinen haben möglicherweise mehrere Threads in ihrer Implementierung, erfordern jedoch keinen LIFO-Stack. Es gibt keine Einschränkung bei FSMs, dass Sie zu einem früheren Zustand zurückkehren, geschweige denn in der LIFO-Reihenfolge. Das ist also ein echtes Multithread-System, für das es nicht gilt. Wenn Sie sich auf eine Definition von Multithreading als "parallel unabhängige Funktionsaufrufstapel" beschränken, erhalten Sie eine zirkuläre Definition.
MSalters
Ich lese die Frage nicht so. OP ist mit Funktionsaufrufen vertraut, fragt aber nach anderen Systemen.
MSalters
@MSalters Aktualisiert, um gleichzeitige Endlosschleifen einzubeziehen. Das Modell ist gültig, schränkt jedoch die Skalierbarkeit ein. Ich würde vorschlagen, dass sogar gemäßigte Zustandsautomaten Funktionsaufrufe enthalten, um die Wiederverwendung von Code zu ermöglichen.
Pekka
2

Alle alten Mainframes (IBM System / 360) hatten überhaupt keine Vorstellung von einem Stack. Auf dem 260 wurden beispielsweise Parameter an einer festen Stelle im Speicher erstellt, und wenn ein Unterprogramm aufgerufen wurde, wurde es mit einem R1Verweis auf den Parameterblock und R14der Rücksprungadresse aufgerufen . Wenn die aufgerufene Routine eine andere Unterroutine aufrufen möchte, muss sie an R14einem bekannten Ort gespeichert werden, bevor dieser Aufruf erfolgt.

Dies ist viel zuverlässiger als ein Stapel, da alles an festen Speicherorten gespeichert werden kann, die zur Kompilierungszeit eingerichtet wurden, und es kann zu 100% garantiert werden, dass die Prozesse niemals den Stapel verlieren. Es gibt keine der "Allocate 1MB und Daumen drücken", die wir heutzutage tun müssen.

Rekursive Unterprogrammaufrufe wurden in PL / I durch Angabe des Schlüsselworts zugelassen RECURSIVE. Sie bedeuteten, dass der von der Unterroutine verwendete Speicher eher dynamisch als statisch zugewiesen wurde. Aber rekursive Aufrufe waren damals genauso selten wie heute.

Der stapellose Betrieb erleichtert auch das massive Multithreading erheblich, weshalb häufig versucht wird, moderne Sprachen stalklos zu machen. Es gibt zum Beispiel keinen Grund, warum ein C ++ - Compiler nicht so modifiziert werden könnte, dass er dynamisch zugewiesenen Speicher anstelle von Stapeln verwendet.

Martin Kochanski
quelle