Computer-Systeme Teil 11: Routinenwi.f4.htw-berlin.de/users/messer/LV/WI-GWI-RABS/Folien/CS-11/11-CS-Routinen-1.pdf · Computer-Systeme – WS 12/13 - Teil 11/Routinen 3 Die einzelnen

Computer-Systeme – WS 12/13 - Teil 11/Routinen 03.12.2012 1

Computer-Systeme

Teil 11: Routinen

Computer-Systeme – WS 12/13 - Teil 11/Routinen 2

Übersicht

• Stack• Subroutinen• Makros• CPU-Modi• Traps


Die einzelnen Ebenen

Wir sehen uns in diesem Teil an, wie die Compiler höhere Objekteauf der Ebene des Assemblers realisieren.


Stack I

• Ein Stack ist eine Organisation eines Speicherbereichs, um mit minimalen Aufwand beliebig komplexe arithmetische Ausdrücke bzw. Formeln einschließlich des Aufrufens von Unterprogrammen zu realisieren.

• Die push-Prozedur bringt einen Wert auf den Stack.• Die pop-Funktion holt den obersten Wert vom Stack und

liefert ihn als Wert.

• In den folgenden Beispiele möge der Stack-Pointer (SP) immer auf das oberste Element des Stacks zeigen.

• Der Stack möge von den hohen Adressen zu den niedrigenwachsen, d.h. mit voller werdenden Stack hat der SP einen immer kleineren Wert.

• Es gibt Stacks, die anders organisiert sind.


Stack II – Pseudo-Notation

Instruction push(param) SP:= SP-sizeof(param);RAM[SP]:= param;

Instruction pop(size:= sizeof(int))SP:= SP+size;return (RAM[SP-size]);

Pop() hat einen optionalen Parameter, der die Größe deszu entfernenden Bereichs in Bytes angibt.Default ist die Größe eines INTs.


Stack-Aufbau

SP ->

Durch Stackbelegter Bereich

Freier Bereich

Belegter Bereich

Richtung, inder der Stackwächst

HoheAdressen

NiedrigeAdressen

Stack-Pointer

(Stack)

Der Stack-Pointer ist einRegister, dessen Werte Adressenin einen bestimmtenSpeicherbereich sind


Stack-Operationen: push(), pop()

SP ->

(Stack)

Vorher

push(integer)

SP ->

Nachher

SP ->SP ->

(Stack)

integer

(Stack)

integer

(Stack)

Vorher Nachher

pop()


Beispiel: push(), pop() bei Operationen

Die Parameter werden mit pop() vom Stack geholt und die Ergebnissemit push() wieder auf diesen geschrieben.

SP ->

(Stack)

Vorher

Addition über Stack

SP ->

Nachher

(Stack)

integer: Ainteger: B

integer: A+B

Interner Ablauf

PROC Add:Regi st er R1= pop( ) 1. Oper andRegi st er R2= pop( ) 2. Oper andR2= R1+R2 Addi t i onpush( R2) Resul t at

[Analog zur Addition sind alleanderen Operationen gestaltet]


Bemerkung I

• Diese Architektur - Stackmaschine genannt - ist ein gedankliches Gebilde, das auf realen Architekturen per Software simuliert werden kann.

• Diese simulierende Software realisiert dann eine virtuelle Maschine durch einen Interpreter.

• Dieses Prinzip wird zur Realisierung von Java benutzt(der dann benutzte Byte-Code-Interpreter arbeitet stack-orientiert).

• Unabhängig davon ist immer ein Zugriff direkt auf alle Speicherzellen möglich.

In der Praxis gibt es keine reinen Stackmaschinen, sondern eineMischung aus Stackoperationen und direkten Zugriffen auf den Stack.


Bemerkung II

• Stacks werden in folgenden Bereichen angewendet:– Ausrechnen von Formeln– Realisieren von Subroutinen– Behandlung von Ausnahmen (Exceptions)– Behandlung von Unterbrechungen (Interrupts)

• Ganz allgemein:Stacks werden immer benutzt, wenn "geschachtelte Dinge" behandelt werden, denn diese benötigen einen kurzzeitigen Zwischenspeicher.

Beispiele für "geschachtelte Dinge":Klammern in Ausdrücken, Blöcke in Java


Formelberechnung I

Es soll berechnet werden: (a+b) * (c-d)

SP ->

push a

SP -> a

(1) (2)

push b

SP ->ab

add

a+bSP ->

push c

SP -> ca+b

(5)

(3) (4)

push d

SP ->c

a+b

(6)

dSP -> c-d

a+b

(7)

sub mul

SP -> (a+b)*(c-d)

(8)


Formelberechnung II

• Werte, die erst später benutzt werden, werden auf den Stackgebracht und bleiben dort, bis sie gebraucht werden.

• Werte, die sofort gebraucht werden, werden von einer Operation während der Ausführung vom Stack geholt;dann wird das Ergebnis wieder auf den Stack gebracht.

• Mit einem Stack können beliebig komplexe, geschachtelte arithmetische Ausdrücke sowie Ausdrücke zur Berechnung von Adressen ausgewertet werden, z.B. die Berechnungen der Offsets bei Array-Zugriffen.


Subroutinen I

• Es gibt immer wieder zu verwendende Code-Stücke.• Um diese nicht immer wieder neu programmieren zu

müssen, werden diese einmal im Speicher abgelegt und bei Bedarf angesprungen, ausgeführt und von dort zurück gekehrt.

• Prozedur = Procedure = Routine = Methode = Funktion = Benanntes Stück Code, das angesprungen und ausgeführt werden kann, um am Ende wieder zurückzuspringen

[die Begriffe werden später noch etwas erklärt]• Unter einer Subroutine wird hier der Oberbegriff für alle

eben genannten Begriffe benutzt.


Subroutinen II

Hauptprogramm Code derSubroutine S

....

....call S(...)........

R:.... S:....

....

....

....

....

....return

(1) (2)

(3)

(4)(5)

Schritte beim Aufruf und beider Rückkehr einer Subroutine

Die Pfeile geben den Weg an,den der PC nimmt.

Der Code beider Routinenbefindet sich im selbenAdressraum


Subroutinen III

• Subroutinen können auch geschachtelt aufgerufen werden.• Die Subroutine, die am Anfang als erstes gestartet wird, wird

Hauptprogramm genannt.

• Wenn sich Subroutinen selbst aufrufen, wird dies Rekursiongenannt:– Direkte Rekursion liegt vor, wenn sich die betreffende

Subroutine selbst aufruft.– Indirekte Rekursion liegt vor, wenn die eigene Subroutine von

einer anderen Subroutine aufgerufen wird, die sie selbst aufgerufen hat.


Subroutinen III - Schachtelungen

Hauptprogramm Code derSubroutine S

....

....call S(...)........

R:.... S:....

....call T(...)............return

(1) (2)(3)

(8)(9)

Code derSubroutine T

T:....

....

....

....

....

....return

(4)

(5)

(6)

(7)


Realisierung I

"call xyz" wird durch dieInstruktion jsr realisiertjsr = jump to subroutineEs wird die Rückkehradresseauf den Stack geschriebenund dann zur Routine gesprungen

"return" wird durch dieInstruktion rts realisiertrts = return from subroutineEs wird die Adresse vomStack geholt und dorthingesprungen

SP->SP-> Addresse

Vorher Nachher

SP-> Addresse

Nachher

SP->

Vorher

jsr-Instruktion

rts-Instruktion


Realisierung II

• Durch die Verwendung des Stacks ist eine einfache Realisierung bei geschachtelten sowie auch bei rekursiven Aufrufen von Subroutinen möglich.

• Die Instruktionen jsr und rts sind hier fiktiv. Bei jedem Prozessor heißen sie anders, haben aber im Prinzip dieselbe Bedeutung wie jsr und rts.


Stackaufbau eines Programmes I

Lokale Variablen

SP ->Zwischen-ergebnisse

belegter Bereich(Stack)

Freier Bereich

Globale Variablen(Heap)


HoheAdressen

NiedrigeAdressen

SL ->


Bemerkungen

• Im globalen Bereich (Heap) werden die mit static und die mit extern deklarierten Variablen (jedenfalls in C) abgelegt.

• Subroutinen benötigen für das Speichern von Zwischen-ergebnissen auch Variablen, die aber nur während ihrer Aktivierung vorhanden sind.

• Diese Variablen müssen beim Aufruf erzeugt sowie direkt vor der Rückkehr wieder entfernt werden.

• Da dies auch bei Rekursion erfolgen soll, müssen diese Variablen auf den Stack gebracht werden: So geschachtelt wie die Aufrufe, so geschachtelt sind diese Variablen auf dem Stackvorhanden.

• Lokale Variablen = Variablen, die nur während der Laufzeit einer Subroutine existieren

• Damit der Stack nicht in den Heap hineinläuft (dann zeigt der SP in den Bereich der globalen Variablen), gibt es für ihn eine Begrenzung (Stack-Limit: SL).


Stackaufbau eines Programmes II

• Dies gilt für– alle Programme oberhalb des

Betriebssystems unabhängig von der Programmiersprache

– Software innerhalb des Betriebssystems– das Betriebssystem selbst auf der nackten

Hardware (Kernel)

• Mit anderen Worten: es gilt für jede Software.

Stack

max.

Code

min.

SP->

Heap

SL->


Beispiel: Klasse in Java

• Lebensdauer = Zeitlicher Bereich zwischen Erzeugen eines Objektes bzw. einer Variablen und Entfernen

• Sichtbarkeit = Textueller Bereich innerhalb des Java-Programms, innerhalb dessen der Name des Objekts benutzt werden kann.

class Point {double x; // x-Koordinatedouble y; // y-Koordinate

double diffX(double xPosition) {double diff;diff= x-xPosition;return(diff);

}}

Lokale Variablen (einer Klasse)

Lokale Variable (einer Methode)


Parameter

• Wenn eine allgemeine Subroutine zum Ausgeben einer Variablen geschrieben werden soll, dann muss es möglich sein, zu verschiedenen Zeitpunkten auch verschiedene Variablen auszugeben.

• Um derartige Subroutinen schreiben zu können, werden Parameter benötigt, über die der Subroutine mitgeteilt wird, womit sie ihre Aufgabe lösen soll.

• Parameter = Wert einer Variablen aus dem Bereich der aufrufenden Subroutine, mit der die aufgerufene Subroutine arbeiten soll

• Dieses Übergabe-Verfahren wird Call-by-Value genannt, da eine Kopie des Wertes übergeben wird.


Wieder das Beispiel: Klasse in Java

• Auch hier muss das Problem der Schachtelung gelöst werden.• Parameter werden daher wie lokale Variablen gehandelt.

class Point {double x; // x-Koordinatedouble y; // y-Koordinate

double diffX(double xPosition) {double diff;diff= x-xPosition;return(diff);

}}

Parameter einer Methode


Stack-Aufbau während einer Subroutine

SP ->

Parameter belegter Bereich(Stack)

Freier Bereich


Lokale Variablen

Rückkehr-Adresse

Stack-Aufbauwährend derAusführungder Subroutine


Schrittweiser Aufbau des Stacks I

Aufrufer:

push Parameter N......push Parameter 2push Parameter 1 Lokale Variablen

SP ->

Parameter N

Aufruf: Subroutine(Parameter 1, ..., Parameter N)

...Parameter 2Parameter 1

(1) (2)

Lokale VariablenSP ->

Para

met

er

Aufrufer:

......


Schrittweiser Aufbau des Stacks II

Parameter

Subroutine:

push Lokale Var.

<- SP


(3) (4)

Lokale Variablen

SP ->

Aufrufer:

......push ....JSR Subroutine

Return-Adresse

Parameter

Return-Adresse

LokaleVariablen

Lokale Variablen

Variablen derSubroutine


Schrittweiser Aufbau des Stacks III

Parameter


(5) (6)

Lokale Variablen

SP ->

Return-Adresse

Parameter

Return-Adresse

Lokale Variablen

Subroutine:

push Lokale Var.......Berechnungen

LokaleVariablen

Ausdrücke

Subroutine:

......pop Lokale Var.

SP ->


Schrittweiser Aufbau des Stacks IV

Parameter


(7) (8)

Lokale Variablen

SP ->

Lokale Variablen

Subroutine:

......RTS

Aufrufer:

......pop Parameter

SP ->


Schrittweiser Aufbau des Stacks V

Aufrufer

......push Parameter N......push Parameter 2push Parameter 1JSR Subroutinepop Parameter......

Subroutine

push Lokale Variablen....Berechnungen....pop Lokale VariablenRTS


Erläuterungen

• Nach dem vorgestellten Schema arbeiten die meisten Aufrufe von Subroutinen.

• Bei einer Subroutine ohne Parameter entfällt das "push Parameter" und "pop Parameter".

• Bei einer Subroutine ohne lokale Variablen entfällt das "push Lokale Variablen" und "pop Lokale Variablen".

• Wenn die Subroutine selbst einen Wert als Ergebniszurückliefern soll, wie z. B. sin(x), dann wird der Platz für das Resultat vom Aufrufer als besonderer Parameter gleich zum Anfang auf den Stack gebracht, so dass nach dem Aufruf das Resultat als oberstes Element auf dem Stacksteht (siehe Formelberechnung durch Stack).


Begriffe

• Statt Routine bzw. Subroutine wird beim objektorientierten Ansatz von Methoden gesprochen.

• Funktion = Routine, die einen Wert an den Aufrufer liefert• Prozedur = Routine, die keinen Rückgabewert hat

(Java, C und C++: void)

• Activation Record = Teil des Stacks, der alle temporären Daten eines Subroutinenaufrufs beinhaltet (Parameter, Rückkehradresse, lokale Variablen)


Kopf und Körper einer Subroutine

• Kopf = Head = Schnittstelle der Subroutine nach außen(Name, Parameter, Resultat samt Typdeklaration)Der Kopf wird auch Signaturgenannt.

• Körper = Body = Code einer Subroutine ohne Kopf, d.h. der Teil nach dem Anlegen der lokalen Variablen bis zum Entfernen der lokalen Variablen und Rückkehr.

float sin(float winkel)

{ int i, j, k; i= 10; .... return Value; }

Name Parameter

Kopf

Körper

Lokale Variablen

Zu lieferndesResultat

Resultat

Beispiel für eine Funktion


Makro

• Makro = Stück Code, der bei jedem Aufruf an die Stelle des Aufrufs hineinkopiert wird und den Aufruf ersetzt

• Ein Makro hat auch einen Kopf und einen Körper. Der Kopf definiert den Namen und die Parameter, der Körper das, was beim Aufruf hineinkopiert werden soll.

• Der Aufruf selbst wird entfernt und stattdessen der Körper samt ersetzten Parametern eingesetzt.

#define TEST (a==b)

if TEST { a= 0; b=1;}

if (a==b) { a= 0; b=1;}

Expansion

Definition desMacros TEST

Name Körper

Beispiel eines Makro in der Sprache C

Aufruf desMacros TEST


CPU-Arbeitsmodi I

• Im Status-Register der CPU befindet sich ein Bit zum Vermerken des Arbeitsmodus der CPU:– User-Mode: Normaler, eingeschränkter Modus– Kernel-Mode: nur vom Betriebssystem benutzter Modus ohne

jede Einschränkung

• Manchmal sind es mehrere Bits, so dass es mehr als 2 Modi der CPU gibt, z.B. bei den Intel-Prozessoren IA32.

• Die Einschränkung im User-Mode betrifft die Ausführung folgender Instruktionsgruppen:– I/O-Instruktionen (falls vorhanden)– Administrationsinstruktionen (Reset, Stop etc.)– Setzen des Status-Registers


CPU-Arbeitsmodi II - Zusammenfassung

• Status Register (SR):– Flags, die das Resultat des letzten Befehls beschreiben, z. B. ob

das Resultat kleiner als 0 war etc.– Modus-Bit, das definiert, in welchem Modus sich die CPU

befindet

• Supervisor-Mode = Privilegierter Mode = Kernel Mode• User Mode = Nicht-Privilegierter Mode


CPU-Status

• Unter bestimmten Umständen muss der gesamte CPU-Inhalt in den Speicher gerettet und später wieder hergestellt werden.

• CPU-Status = Inhalt der CPU, d.h.– Alle Daten- und Adressregister, auch SP– Status-Register (SR)– Program Counter (PC)

• Um den alten Zustand wieder herzustellen, müssen diese Werte wieder in die Register geschrieben werden, jedoch kann das Modus-Bit nur dann verändert werden, wenn die CPU vorher im Supervisor/Kernel-Modus ist.


Exceptions

• Exception = Ausnahmesituation einer Instruktion mit anschließendem Abbruch der Ausführung

• Beispiele für Exceptions:– Division durch 0– Word-Zugriff auf den Speicher mit ungerader Adresse– RAM signalisiert Speicherfehler– Zugriff auf nicht vorhandenem Speicher


Ablauf bei Exceptions

1. Abbruch der aktuellen Instruktion2. Wechsel in den Kernel-Modus (Setzen des Modus-Bits)3. Bestimmen des Trap-Handlers4. Retten des alten Status-Registers5. Retten des aktuellen PC-Wertes6. Sprung zum Trap-Handler (Setzen des PC)

7. Retten des restlichen CPU-Status auf den Stack8. Beginn der Behandlung

Wenn die CPU eine Exception festgestellt hat:

Die ersten 6 Schritte werden automatisch durch die CPU als Abschlussder aktuellen Instruktion durchgeführt.


Stackaufbau nach Exception

Lokale Variablen

SP ->

Zwischen-ergebnisse

Parameter NParameter N...

Parameter 2Parameter 1

<- LB

Return-Address

Vor Exception

Lokale Variablen

SP ->

Zwischen-ergebnisse

Parameter N...


<- LB

Status-Register

Exception-Handlerläuft


Begriffe

• Trap = Exception = Ausnahmesituation• Trap-Handler = Routine, die als Reaktion einer Exception

aufgerufen wird

• Es gibt eine Tabelle mit den Adressen der Trap-Handler, die ein Array ist

• Die Traps/Exceptions haben Nummern, die als Indices in diese Tabelle benutzt werden.


Bestimmung des Trap-Handlers

Exception-Nummer

Adresse F1

Tabelle steht aneiner speziellendafür vorgesehenenStelle

Adresse F2Adresse F3Adresse F4

.....Adresse FN

Indizieren

Handler F4

Handler F3

Handler F2

.....

Routinenim Kernel


Abschluss des Trap-Handlers

• Ausgabe einer Fehlermeldung mit Fortführung des Programms

• Abbruch des Programms• Reparatur des Problems und Rückkehr zu abgebrochenen

Instruktion

Je nach Schwere kann der Trap-Handler unterschiedliche Dinge tun:

Im Falle einer Rückkehr zum Programm muss der Trap-Handlerden alten CPU-Status anhand der Werte auf dem Stackwiederherstellen.


Syscall – System Call

• Syscall = System Call = Systemaufruf = Aufruf einer Routine im Kernel

• Ein Syscall ist ein Unterprogramm-Aufruf mit Wechsel des CPU-Modus.

• Zum Beginn wird der CPU-Status gerettet.• Bei der Rückkehr aus der Kernelroutine wird bis auf den

Return-Code der CPU-Status wieder hergestellt.• Der Return-Code besagt dem Aufrufer, ob alles in Ordnung

war bzw. wenn ein Wert zu liefern ist, welcher Wert dies ist. Dafür wird meistens ein bestimmtes Register reserviert (das nicht wiederhergestellt wird).


Trap-Instruktion

• Zentral beim Syscall steht die Trap-Instruktion, die sehr ähnlich zum Unterprogrammaufruf ist.

• Die Rückkehr zum Aufrufer erfolgt durch die RTT-Instruktion(Return-from-Trap).

• Die Trap-Instruktion rettet das SR-Register sowie den aktuellen PC-Wert auf den Stack, bestimmt anhand einer Tabelle mit Sprungadressen, wohin gesprungen werden soll, und springt dorthin.

• Die RTT-Instruktion holt den geretteten PC-Wert vom Stackund schreibt ihn in den PC (Sprung zurück); dasselbe erfolgt mit dem SR-Wert, wobei hier der neue CPU-Modus durch den wieder hergestellten SR-Wert bestimmt wird.


TRAP und RTT I

SP ->

SP -> PC

SR

(1) (2)

Trap-Instruktion

PC

SR

SP ->

SP ->RTT-Instruktion


TRAP und RTT II - Ablauf

TRAP-Instruktion RTT-Instruktion

CPU-Mode:= KernelPush Status-RegisterPush Programm CounterPC:= Spezielle AdresseSetzen des Kernel-Mode im SR

Pop Programm CounterPop Status-RegisterCPU-Mode:= SR-Wert

Das Aufrufen eines Trap-Handlers sieht genauso wie dieBehandlung einer Exception aus; dasselbe gilt auch für dieRückkehr.

Eine Exception/Trap ist eine Reaktion auf einen Fehler,während bei der Trap-Instruktion um einen gewollten Aufrufhandelt.


TRAP und RTT III – Sicht des Programmierers

User-Mode Kernel-Mode

...Parameter setzenTRAPParameter beseitigen...

Push Register...Ausführen der Funktion...Pop RegisterRTT

Prolog

Epilog


Noch einmal: Aufruf einer Routine

Aufrufer Routine

...Parameter setzenJSRParameter beseitigen...

push Registerpush Local Variables...Ausführen der Funktion...pop Local Variablespop RegisterRTS

Prolog

Epilog

Dies kann im sowohl im User-Modus als auch im Kernel-Modus ablaufen.


Trap-Call I – ohne Wechsel des Stacks

Lokale Variablen

SP ->

Zwischen-ergebnisse

Parameter NParameter N...


Return-Address

Aufrufervor trap

trap

Lokale Variablen

SP ->

Zwischen-ergebnisse

Parameter N...


Status-Register


Trap-Call II – Bestimmung des Trap-Handlers

trap Parameter

Adresse F1

Tabelle steht aneiner speziellendafür vorgesehenenStelle

Adresse F2Adresse F3Adresse F4

.....Adresse FN

Indizieren

Adressen derRoutinen, die dieSyscalls realisieren

Syscall F4

Syscall F3

Syscall F2

.....

Routinenim Kernel

Tabellen und Routinen im Kernel


Hinweis zum Stackwechsel

• In der vorgestellten Version wird nur mit einem Stackgearbeitet, d.h. nach dem Trap wird derselbe Stack im Kernel-Mode benutzt.

• Viele Maschinen arbeiten nicht so: Sie besitzen zwei Stackpointer, einer für den User-Mode und einen für den Kernel-Mode. Bei diesen Maschinen findet noch ein Wechsel des Stacks statt:– Kernel-SP (KSP)= Stackpointer für den Kernel-Modus– User-SP (USP)= Stackpointer für den User-Modus


Call und Trap - Stacklayout

(2) Lokaler Kontext

TemporäreVariablen

Parameter 1

Parameter n

...Parameter 2

LokaleVariablen

<-SP

Nach Call

Return

LB undRegister

Nach Exception/Trap/Syscall

TemporäreVariablen

Parameter 1

Parameter n

...Parameter 2

LokaleVariablen

Return

Register(SP+...)

SR-Register

(1)(1)

(2) (2)

(1) Rückkehr-Information<-SP


Call und Trap – Zusammenfassung

• Ein Call ist ein programmierter, parametrisierbarer Sprung mit Rückkehrinformation ohne Modus-Wechsel.

• Ein Trap ist ein programmierter, parametrisierbarer Sprung mit Rückkehrinformation und Wechsel in den Kernelmode.

• Mit Traps werden Syscalls realisiert. Traps werden innerhalb des Kernels nicht verwendet.

• Exceptions sind Abbrüche in der Instruktionsausführung und werden wie Traps behandelt.


Nach dieser Anstrengung etwas Entspannung....

Documents

Computer-Systeme Teil 11: Routinenwi.f4.htw-berlin.de/users/messer/LV/WI-GWI-RABS/Folien/CS-11/11-CS-Routinen-1.pdf · Computer-Systeme – WS 12/13 - Teil 11/Routinen 3 Die einzelnen