LIFO oder Stack

Die Bezeichnung LIFO steht für 'Last In, First Out' und bezeichnet einen Puffer, bei dem die zuletzt gespeicherten Werte zuerst wieder gelesen werden. Dieses Verhalten gleicht einem Stapel, darum wird ein LIFO-Puffer meist auch als Stack bezeichnet. Der Stack hat eine zentrale Rolle in der Programmierung von Mikrocomputern und soll entsprechend ausführlich beschrieben werden.

Der Stack wird in einem reservierten Teil des Speichers angelegt. In der Initialisierungsphase eines Programms wird ein Zeiger (das ist eine Variable, die die Adresse einer Speicherzelle des Stacks enthält) auf den Beginn des Stacks gesetzt. Bei jedem Schreibvorgang wird der zu speichernde Wert in die Speicherzelle, auf die der Zeiger weist, geschrieben und der Zeiger auf die nächste Adresse gesetzt. Beim Lesen wird zuerst der Zeiger auf die vorhergehende Adresse gesetzt und der Wert der adressierten Speicherzelle zurückgegeben. Durch diesen Mechanismus wird immer der zuletzt gespeicherte Wert gelesen. Dieses Verhalten kann man dazu nutzen, vorübergehend irgendwelche Werte zu speichern.

Da der Stack eine sehr große Rolle als Zwischenspeicher und beim Unterprogrammaufruf spielt, gibt es fast in jedem Mikroprozessor entsprechend spezialisierte Befehle, die den Stack verwalten. Der Zeiger wird als 'Stack pointer' bezeichnet und ist als eigenes Register in der CPU vorhanden. Der folgende Programmausschnitt soll die Anwendung des Stacks zum Zwischenspeichern von Werten zeigen. Der Programmteil überprüft, ob der Inhalt des Registers HL kleiner als $24 ist. Da der Mikroprozessor Z80 keinen 16-Bit-Vergleichsbefehl hat, wird der Vergleich mit einer 16-Bit-Subtraktion durchgeführt. Bei der Subtraktion wird jedoch das Register HL verändert. Um den alten Wert von HL nach dem Vergleich weiterverwenden zu können, wird der Inhalt von HL vor der Subtraktion auf dem Stack zwischengespeichert und nach der Subtraktion wieder vom Stack gelesen.

            LD      DE,$0024    ;Vergleichswert
            PUSH    HL          ;HL sichern
            XOR     A           ;carry flag rücksetzen
            SBC     HL,DE       ;Subtraktion
            POP     HL          ;HL restaurieren
            JR      C,LABEL1    ;Sprung falls HL < DE

Folgende Abbildung zeigt die Vorgänge auf dem Stack. Der Stackpointer zeigt auf den ersten freien Platz im Stack. Mit dem Befehl 'PUSH HL' wird der Inhalt von HL auf den Stack geschrieben und der Stackpointer dekrementiert, so dass er auf den nächsten freien Platz zeigt. Der Befehl 'POP HL' inkrementiert den Stack pointer und liest den Wert am Stack in das Register HL ein. Damit ist der Stackpointer wieder an derselben Stelle wie zu Beginn der Programmsequenz, und HL ist unverändert.

Benützung des Stacks

Man sieht aus diesem Beispiel, dass in einem Programm immer gleich viele PUSH- und POP-Befehle vorhanden sein müssen, damit der Stack nicht voll wird. In der Tat gehört die falsche Verwendung von Stackbefehlen zu den häufigsten Programmierfehlern auf Assemblerebene. Solche Fehler wirken sich im Allgemeinen fatal auf das Programm aus, da nicht nur Variablen falsch zugewiesen werden, sondern auch bei Unterprogrammaufrufen (Unterprogramme verwenden auch den Stack, siehe unten) falsche Rücksprungadressen erhalten werden, was zu einem sicheren Absturz des Programms führt.