% Studienarbeit von Marc Weikard
%
% Universitaet Hamburg
% Fachbereich Informatik
% Arbeitsbereich DBIS
%
% Kapitel: Virtuelle Maschine


\chapter{Die virtuelle Maschine}
\label{Kap. virtuelle Maschine}

Die TVM (\s{Tycoon Virtual Machine}) stellt die Schnittstelle zum Tycoon-Laufzeitsystem dar. Sie definiert eine funktionale, kellerbasierte virtuelle Maschine mit einem bytecodierten Befehlssatz. Der unter Nutzung des unterliegenden Tycoon-Speicherprotokolls persistent gehaltene Programmcode wird durch einen im Laufzeitsystem integrierten Interpreter ausgef"uhrt.

Die konsequente Implementierung des TVM-Interpreters und des zugeh"origen Laufzeitsystems in ANSI C erm"oglicht die Portierung auf eine Reihe unterschiedlicher Systemumgebungen, unter anderem \pn{Solaris}, \pn{Windows NT}, \pn{Linux} und \pn{MacOS}.

Die Plattformunabh"angigkeit von TVM und TSP-Modell gestattet neben der Verwendung desselben Bytecodes auf allen Systemen sogar die Migration in Ausf"uhrung befindlicher leichtgewichtiger Prozesse (\e{threads}) in heterogenen Netzwerkumgebungen.


\section{Funktionsobjekte}
\label{Abs. Funktionsobjekte}

Die Programmiersprache TL unterst"utzt Funktionen h"oherer Ordnung, d.h. Funktionen k"onnen Argumente und Resultate anderer Funktionen sein. Die einfache Repr"asentation einer Funktion als Bytecode reicht nicht aus, dieses Konzept zu realisieren.

\begin{figure}[H]
\begin{center}
\leavevmode
\epsfxsize=12.5cm
\epsffile{Bilder/Funktionsobjekt.eps}
\caption{Funktionsobjekt der virtuellen Maschine}
\label{Funktionsobjekt}
\end{center}
\end{figure}

Funktionen stellen im TVM-Modell aus 3 Komponenten bestehende Objekte dar (siehe Abbildung~\ref{Funktionsobjekt}):
\begin{itemize}
\item Funktionsabschlu"s (\e{closure}). \\
Alle Funktionsabstraktionen liefern in TL gleichberechtigte Werte. Dies trifft insbesondere f"ur geschachtelte Funktionen zu, die auf Datenobjekte ihres jeweiligen Sichtbarkeitsbereichs zugreifen. Da sich der sie umgebende Kontext jedoch zu ihrer Lebenszeit "andern kann, m"ussen alle von ihnen eingegangenen globalen Bindungen fixiert werden. Der Funktionsabschlu"s ist eine Datenstruktur, in die die OIDs der referenzierten globalen Objekte 	eingetragen werden. Sie wird dynamisch erzeugt. 
\item Literalvektor. \\
Die Basisdatentypen Flie"skommazahl und Zeichenkette (\e{string}) k"onnen nicht direkt im Bytecode dargestellt werden. F"ur sie werden zur "Ubersetzungszeit eigene Objekte erzeugt, deren OIDs in den Literalvektor eingetragen werden.
\item Bytecode. \\
Der Bytecode ist eine Folge bytecodierter Instruktionen der virtuellen Maschine, die vom TVM-Interpreter abgearbeitet wird. Er wird vom Compiler-Backend aus der Zwischenrepr"asentation TML erzeugt. 
\end{itemize}


\section{Bytecode}
\label{Abs. Bytecode}

Die Spezifikation der TVM-Byteinstruktionen lehnt sich an die von Transputern bekannten Befehlss"atze an. Alle Opcodes weisen eine feste Gr"o"se von 8 Bit auf, von denen die 4 h"oherwertigen Bit den Operator und die restlichen 4 Bit den Operanden kodieren. Da eine Restriktion auf 16 Operationen bzw. des Operandenbereichs auf 16 Werte die Verwirklichung des kompletten Befehlssatzes nicht gestattet, besitzen 3 Instruktionen eine spezielle Semantik:
\begin{itemize}
\item \s{PFIX} und \s{NFIX} f"ur die vorzeichenbehaftete Erweiterung des Operanden des Folgebefehls um 4 Bit. Durch wiederholte Ausf"uhrung lassen sich beliebige Operandengr"o"sen erreichen.
\item \s{OPR} interpretiert seinen Operanden als neuen Operator und erweitert so, insbesondere in Verbindung mit \s{PFIX/NFIX}, den Instruktionssatz.
\end{itemize}
Neben mathematischen und logischen Funktionen und Operationen zur Ablaufsteuerung existieren auch Bytecodes f"ur Objektspeicherzugriffe. Diese garantieren die Atomarit"at der punktuellen Zustands"anderungen und vereinfachen dadurch sowohl das TSP wie auch die Implementierung der h"oheren Systemebenen. Tabelle~\ref{Bytecodes} zeigt eine "Ubersicht der vorhandenen Instruktionen. 

\begin{table}
\begin{center}
\begin{tabular}{|ll|}
\hline
\s{LDL, STL}              & Laden und Modifikation von lokalen Variablen \\
\s{LDC}                   & Laden von ganzzahligen Konstanten \\
\s{LDOK, LDFALSE, LDTRUE} & Laden spezieller Konstanten \\
\s{LDG}                   & Laden von globalen Variablen \\
\s{LDLC}                  & Laden von Literalen \\
\s{LDP, STP}              & Feldzugriff und Modifikation \\
\s{LDB, STB}              & Byte-Feldzugriff und Modifikation \\
\s{ADD, SUB, MUL, DIV, MOD, NEG}   & ganzzahlige Arithmetik \\
\s{GT, GE, LT, LE}        & ganzzahlige Vergleiche \\
\s{NOT, AND, OR, XOR}     & ganzzahlige boolsche Operationen\\
\s{SHL, SHR}              & Bit-Schiebeoperationen \\
\s{C2I,I2C}               & Konvertierung von Ganzzahlen und Zeichen \\
\s{PUSHH, POPH}           & Installation/Entfernung eines Ausnahmepakets \\
\s{RAISE}                 & Ausl"osen einer Ausnahme \\
\s{J, CJ, JE}             & Unbedingte und bedingte Spr"unge \\
\s{SWITCH}                & Bedingter Sprung mit mehreren Sprungzielen \\
\s{CALL}                  & Aufruf einer Funktion \\
\s{CCALL}                 & Aufruf einer externen C-Funktion \\
\s{RET, RETURN}           & R"uckkehr aus einer Funktion \\
\s{ADJ, ADJP}             & Korrektur des Stapelzeigers \\
\s{CLOSURE}               & Erzeugen eines Funktionsabschlusses \\
\s{ARRAY}                 & Erzeugen eines ver"anderbaren Feldes \\
\s{VECTOR}                & Erzeugen eines unver"anderbaren Feldes \\
\s{NSLOTS}                & Gr"o"se eines Feldes \\
\s{MOVE, BMOVE}           & Kopieren von Feldbereichen \\
\s{PFIX, NFIX}            & Erweiterung des Befehlsoperanden \\
\s{OPR}                   & Erweiterung der Instruktionssatzes \\
\hline
\end{tabular}
\caption{Befehlssatz der virtuellen Maschine}
\label{Bytecodes}
\end{center}
\end{table}

Alle Bytecodes arbeiten auf einem Kellerspeicher, dem sie eventuell n"otige Argumente entnehmen und auf dem sie ihre Ergebnisse ablegen. Da der Kellerspeicher der Kontrolle des TSP unterliegt, m"ussen alle auf ihm befindlichen Speicherworte einem einheitlichen Markierungsschema folgen. Dies bedeutet vor allem bei mathematischen und logischen Operationen, da"s die Markierungen von den Argumenten entfernt und dem Resultat hinzugef"ugt werden m"ussen.

Bytecode ist eine "au"sert kompakte Repr"asentation von Programmen. Dies schont zum einen Systemressourcen und erlaubt so den Einsatz des Tycoon-Systems auch auf verh"altnism"a"sig gering ausgestatteten Plattformen. Zum anderen wird die Bandbreite in Netzwerkumgebungen beim Versenden von in Ausf"uhrung befindlichen Prozessen nicht sehr belastet.


\section{Stapelspeicher}
\label{Abs. Stapelspeicher}

Der TVM-Stapelspeicher (\e{stack}) ist eine lineare Datenstruktur aus markierten Speicherworten (siehe Abschnitt~\ref{Abs. TSP}). Er ist in zwei Bereiche unterteilt, die von oben und unten aufeinander zuwachsen (Abbildung~\ref{Stapel}): 
\begin{enumerate}
\item Stapelspeicher f"ur Kontexte der Ausnahmebehandlung (\e{exception stack}). \\
Die Funktionsweise der Ausnahmebehandlung und die Rolle des Ausnahmestapels werden in Abschnitt~\ref{Abs. Ausnahmebehandlung} n"aher erl"autert.
\item Stapelspeicher f"ur Ausf"uhrungsrahmen (\e{frames}) von Funktionen. \\
Jede in Ausf"uhrung befindliche Funktion besitzt einen ihr zugeordenten Speicherbereich innerhalb des Stapels, ihren Ausf"uhrungsrahmen. Dieser ist in zwei Teile gegliedert, einen nicht modifizierbaren (\e{parameter frame}) und einen ver"anderbaren Bereich (\e{local frame}). Funktionsargumente, OIDs von Funktionsabschlu"s und Literalvektor und der Zustandsvektor der aufrufenden Funktion werden im \e{parameter frame} abgelegt. Der \e{local frame} speichert 	ver"anderliche Werte wie z.B. lokale Variablen. 
\end{enumerate}
M"ogliche "Uberschneidungen beider Bereiche k"onnen vom Interpreter im Voraus erkannt und durch eine dynamische Vergr"o"serung des Stapelspeichers verhindert werden.

Die Adressierung des aktuellen Rahmens, Ausnahmepaketes bzw. einzelner Speicherworte erfolgt durch Rahmen-, Ausnahme- und Stapelzeiger. 

\begin{figure}
\begin{center}
\leavevmode
\epsfxsize=12.5cm
\epsffile{Bilder/Stapel.eps}
\caption{Stapelspeicher der virtuellen Maschine}
\label{Stapel}
\end{center}
\end{figure}


\section{Ausnahmebehandlung}
\label{Abs. Ausnahmebehandlung}

Die Ausnahmebehandlung in TL bietet eine einfache M"oglichkeit, Laufzeitfehler abzufangen und gezielt zu behandeln. Dieses Konzept wird vom Tycoon-Laufzeitsystem mit Hilfe spezieller Bytecodes und eines Stapelspeichers f"ur Ausnahmekontexte direkt unterst"utzt. Ein Ausnahmekontext enth"alt alle f"ur eine Programmfortsetzung im Fehlerfall erforderlichen Informationen: den Rahmenzeiger der auszuf"uhrenden Funktion, ihren Befehlsz"ahler und Stapelzeiger.

Jeder Programmblock,  f"ur den eine Ausnahmebehandlung vorgesehen ist, wird von zwei Byteinstruktionen gekapselt:
\begin{itemize}
\item \s{PUSHH} legt zu Beginn des kritischen Abschnitts einen Ausnahmekontext auf dem Stapelspeicher ab.
\item \s{POPH} entfernt den Kontext bei fehlerfreier Programmausf"uhrung vom Stapel.
\end{itemize}
Wird innerhalb des Blocks eine benutzerdefinierte Ausnahme durch den \s{RAISE}-Opcode ausgel"ost, so werden der oberste Ausnahmekontext vom Stapelspeicher genommen, ung"ultig gewordene Ausf"uhrungsrahmen entfernt und die Programmausf"uhrung an der im Kontext definierten Stelle fortgesetzt. Auch geschachtelte Ausnahmebehandlungen k"onnen durch diesen einfachen Mechanismus gehandhabt werden.


\section{Parallele leichtgewichtige Prozesse}
\label{Abs. parallele Prozesse}

Im Gegensatz zu einem Proze"s, der den Ausf"uhrungsrahmen einer kompletten Applikation definiert, sind leichtgewichtige Prozesse (\e{leight-weight processes}), im folgenden Threads genannt, Ausf"uhrungskontexte einzelner Funktionen. Ein Thread ben"otigt zur Ausf"uhrung lediglich einen eigenen Stapelspeicher und einen kompletten Registersatz (\s{IP, FP, EP, SP}), alle weiteren Ressourcen werden mit seinem Erzeugerproze"s geteilt. Die Konstruktion, Destruktion und der Kontextwechsel von Threads sind daher im Vergleich zu Prozessen mit weit geringeren Kosten verbunden. Hinsichtlich Synchronisation und Kommunikation existieren den Prozessen "aquivalente Mechanismen. 

Das Tycoon-Laufzeitsystem unterst"utzt die quasi parallele Ausf"uhrung (\e{multitasking}) mehrerer persistenter Threads. Betriebssystemfunktionen wurden f"ur die Implementierung nicht genutzt, da diese sich von Plattform zu Plattform unterscheiden oder teilweise noch nicht einmal vorhanden sind (beispielsweise \pn{MacOS}). Verwendet werden stattdessen Coroutinen, die in C einfach zu realisieren und auch in anderen Programmiersprachen, z.B. Modula-2, nicht unbekannt sind. Coroutinen st"utzen sich auf eine kooperative Form des Multitasking, d.h. eine gerade laufende Funktion mu"s von sich aus den Wechsel des Ausf"uhrungskontextes veranlassen. Dieser im ersten Augenblick ersichtliche Nachteil gegen"uber pr"aemptivem Multitasking, das Kontextwechsel implizit durchf"uhrt und nicht auf die Unterst"utzung der beteiligten (leichtgewichtigen) Prozesse angewiesen ist, relativiert sich jedoch bei genauerer Betrachtung des im Laufzeitsystem implementierten Verfahrens.

Parallele Ausf"uhrungskontexte sind auf Ebene des Bytecodes vollkommen transparent. Es existieren im TVM-Befehlssatz keine speziellen Operationen, die zur Abgabe der Programmsteuerung an einen konkurrierenden Thread f"uhren. Die entsprechenden Mechanismen sind direkt in den Interpreter eingebunden. Ihre Aktivierung erfolgt nach Ablauf einer vom Proze"smanager (\e{scheduler}) des Laufzeitsystems zugeteilten Zeitscheibe mit der n"achsten auszuf"uhrenden Byteinstruktionen zur Kontrollflu"ssteuerung (u.a. Sprungbefehl, Funktionsaufruf). Da jeder Bytecode den Kontrollflu"s betreffende Instruktionen enth"alt, die in kurzen Abst"anden ausgef"uhrt werden, k"onnen andere Threads nicht blockiert werden. Dieses einfache und doch leistungsf"ahige Konzept wird nur beim Aufruf externer C-Funktionen durchbrochen, da diese nicht der Kontrolle des Proze"smanagers unterstehen.      

 
\section{Persistente Threads}
\label{Abs. persistente Threads}

Ein Merkmal des Tycoon-Systems ist seine erweiterte orthogonale Persistenz, die nicht nur bei Daten und Programmen, sondern auch bei Threads zur Anwendung kommt. Der Ausf"uhrungskontext eines Threads, d.h. sein Stapelspeicher, Registersatz, Befehlsz"ahler und die OID der aktuellen Funktion, mu"s daher persistent im Objektspeicher gehalten werden. Der Interpreter operiert aus Geschwindigkeitsgr"unden auf im Hauptspeicher liegenden Kopien der Kontexte. Ein Abgleich mit dem Objektspeicher wird immer bei Kontextwechseln und vor Aufruf der Freispeicherverwaltung durchgef"uhrt. Es stehen hierzu Funktionen zur Verf"ugung, die das Auslesen bzw. Schreiben des Ausf"uhrungszustandes in den Objektspeicher erlauben.  

\newpage

\section{Migration}
\label{Abs. Migration}

Die plattformunabh"angige Repr"asentation von Daten und Programmen bildet zusammen mit der auf allen Plattformen verf"ugbaren gleichen Grundfunktionalit"at des Tycoon Laufzeitsystems die Basis f"ur die Systemgrenzen "uberschreitende Migration von Threads. Die Realisierung dieses innovativen Konzeptes erfolgt im wesentlichen auf hochsprachlicher Ebene und "uber externe Bibliotheken. Es erfordert keine gesonderte Unterst"utzung durch den Interpreter, z.B. in Form spezieller Bytecodes. Eine ausf"uhrliche Beschreibung findet sich in \cite{MMS95}.   


\section{C-Calls}
\label{Abs. CCalls}

TL bietet mit seiner Aufrufschnittstelle f"ur C-Funktionen eine einfache M"oglichkeit der Koppelung an externe Diensterbringer. Die hochsprachlichen Konstrukte werden direkt auf einen einfachen, portablen und effizienten Mechanismus des Laufzeitsystems abgebildet, der den Zugriff auf statisch und dynamisch gebundene Bibliotheken steuert.

Der Aufruf einer externen C-Funktion wird durch die Byteinstruktion \s{CCALL} implementiert, die 3 Argumente erwartet:
\begin{itemize}
\item Beschreibung der Argumente und des Ergebnistyps,
\item Name der Funktion, 
\item Name der Bibliothek. 
\end{itemize}
W"ahrend die ersten beiden Parameter bereits zur "Ubersetzungszeit bekannt sind, wird der Bibliotheksname erst zur Laufzeit ermittelt. Die Unabh"angigkeit des Bytecodes vom verwendeten Bindungsmechanismus wird auf diese Weise garantiert. Auf Plattformen, die keine dynamische Bindung unterst"utzen, m"ussen alle externen Bibliotheken statisch an das Laufzeitsystem gebunden werden.

Die automatische Konvertierung von Argumenten zwischen der TVM und externen Funktionen ist auf unstrukturierte Werte wie Ganzzahlen und Zeichenketten beschr"ankt. Strukturierte Werte m"ussen in TL oder C-Funktionen gekapselt werden (\e{wrapper functions}). Diese "ubernehmen die Konstruktion zusammengesetzter Werte aus den Basisdatentypen bzw. deren Zerlegung.


\section{Callbacks}
\label{Abs. Callbacks}

Im Zusammenspiel mit externen Bibliotheken (z.B. grafischen Benutzerschnittstellen) ist es h"aufig notwendig, Funktionalit"at des Tycoon-Systems von au"sen zug"anglich zu machen. Die TVM stellt hierzu einen Mechanismus (\e{callback}) bereit, der Funktionsobjekte mit dynamisch erzeugtem Code zur Parameterkonvertierung kapselt und als C-Funktionszeiger exportiert.

Callbacks erfordern den direkten Eingriff in die Ablaufsteuerung des Interpreters. Vor Ausf"uhrung einer exportierten Funktion m"ussen ein entsprechender Funktionsrahmen aufgebaut und der aktuelle Ausf"uhrungskontext des Interpreters manipuliert werden.



