\chapter{Synchronisationsmechanismen für persistente Objektsysteme}
\label{Syncprimitive}
Wie aus dem vorangegangenen Kapitel ersichtlich ist, existieren die
verschiedensten Verfahren für die Synchronisation nebenläufiger
Aktivitäten. In diesem Kapitel wird die Auswahl und Implementation
grundlegender Verfahren für das persistente Objektsystem Tycoon
beschrieben. Im folgenden Abschnitt werden die für
Synchronisationsmechanismen relevanten besonderen Eigenschaften des
Tycoon-Systems erörtert und die Anforderungen an die zu
implementierenden Mechanismen festgelegt.  Die Spezifikation der
Verfahren sowie Beispiele für ihre Benutzung ist Thema von
Abschnitt~\ref{SPEC}. Der Abschnitt~\ref{IMPL} beschreibt die
wichtigsten Aspekte der konkreten Implementation der Verfahren im
Tycoon-System.  Von der Einordnung der vorgestellten Verfahren in
existierende Standards für die Programmierung nebenläufiger
Aktivitäten handelt Abschnitt~\ref{RELATED}. Im Abschnitt~\ref{HIGHER}
werden höhere Synchronisationsmechanismen auf der Basis der in den
vorangegangenen Abschnitten behandelten Mechanismen implementiert.


\section{Anforderungen und Auswahl}
Die im  Kapitel~\ref{SYNC} vorgestellten Synchronisationsmechanismen
zeigen, wie groß das Spektrum der zur Verfügung stehenden Alternativen
zur Behandlung von Synchronisationsproblemen ist. Um zu einer
Entscheidung über die zu implementierenden Synchronisationverfahren zu
gelangen, ist  daher zunächst die Erörterung folgender Punkte notwendig:
\begin{enumerate}
\item Die für Synchronisationsmechanismen relevanten Eigenschaften des
  Tycoon-Systems sind zu untersuchen. Hierzu gehören die Auswirkungen
  des hierarchischen Aufbaus des Systems auf Synchronisationsprobleme
  sowie Eigenschaften der einzelnen Komponenten Laufzeitsystem,
  Speicherprotokoll, Objektspeicher und der Sprache~TL.
\item Es sind die für die Synchronisation in persistenten
  Objektsystemen wünschenswerten Eigenschaften der
  Synchronisationsmechanismen festzulegen.
\item Es ist zu entscheiden, auf welcher der verschiedenen Ebenen der
  Synchronisationsmechanismen die zu implementierenden Mechanismen
  angesiedelt sein sollen.
\end{enumerate}

\subsection{Eigenschaften des Tycoon-Systems}
Für das zur Verfügung stehende persistente Objektsystem Tycoon sind
die folgenden, für  Synchronisationsmechanismen wichtigen
Eigenschaften in Betracht zu ziehen:
\begin{itemize}
\item Das Tycoon-Laufzeitsystem ist als virtuelle Maschine
  implementiert (Abschnitt~\ref{RUNTIME}), die ein Einprozessorsystem
  simuliert~\cite{BM96}. Diese virtuelle Maschine steht für eine
  Vielzahl von Betriebssystemen zur Verfügung.
 
\item Betriebssystemfunktionalität, wie Hauptspeicherverwaltung und
  Ein- und Ausgabefunktionen, wird durch das Laufzeitsystem gekapselt
  und unabhängig vom eigentlichen Betriebssystem zur Verfügung
  gestellt. Ein Programmierer findet auf allen eingesetzten
  Betriebssystemen eine einheitliche Programmierschnittstelle vor.

\item Tycoon-Threads, die nebenläufige Aktivitäten ausführen, sind als
  Koroutinen implementiert, die zeitscheibengesteuert  die
  Ausführungskontrolle an weitere Koroutinen abgeben. Es existiert
  demzufolge keine zentrale Instanz im Laufzeitsystem, die präemptiv die
  Zuteilung von Rechenzeit an Threads verwaltet. Erst auf der
  Ebene der Programmiersprache TL erscheinen diese Koroutinen als
  voneinander unabhängige Threads. Eine in einigen Betriebssystemen
  bereits vorhandene Unterstützung von Threads~\cite{Sun93} wird aus
  Gründen der Portabilität nicht benutzt.
  
\item Zugriffe auf TL-Objekte erfolgen über die
  Objektspeicherschnittstelle TSP, die von dem konkret eingesetzten
  Objektspeicher abstrahiert und bereits einen atomaren Zugriff auf
  nichtzusammengesetzte TL-Objekte garantiert. Dieses Verhalten
  entspricht der Eigenschaft des unteilbaren Speicherzugriffs in
  herkömmlichen, nicht persistenten Systemen.  Laufzeitsystem, TSP und
  Objektspeicher stellen voneinander logisch und unter Umständen auch
  implementationstechnisch getrennte Schichten des Tycoon-Systems dar
  (siehe Abbildung~\ref{tycoon}).
  
  
  
\item Die Programmiersprache TL bietet durch Eigenschaften wie
  Funktionen höherer Ordnung und Polymorphismus  Möglichkeiten,
  über die viele der in Abschnitt~\ref{SYNCPROC} vorgestellten
  Programmiersprachen nicht verfügen. Ein weiterer wesentlicher
  Gesichtspunkt ist die Möglichkeit, Einfluß auf die Syntax der
  Programmiersprache TL durch  Verwendung von Syntaxerweiterungen
  nehmen zu können~\cite{Schr94}.
  
\item Tycoon-Objekte sind mobil und können zwischen verschiedenen
  Objektspeichern migrieren~\cite{BM96}.
\end{itemize}

\subsection{Anforderungen an Synchronisationsmechanismen}
Unter Berücksichtigung der oben genannten Punkten werden nachfolgend
für die zu implementierenden Synchronisationsmechanismen folgende
Anforderungen festgelegt:
\begin{itemize}
\item Da das Tycoon-Laufzeitsystem auf einer Vielzahl von sehr
  unterschiedlichen Betriebssystemen implementiert ist, sollen auch
  die Synchronisationsmechanismen mit angemessenem Aufwand auf
  weitere Systeme portierbar sein. Es dürfen daher möglichst
  wenige funktionale Abhängigkeiten vom vorliegenden Betriebssystem
  vorhanden sein. 
  
\item Die in Kapitel~\ref{SYNC} und Abschnitt~\ref{SYNCPROC}
  vorgestellten Mechanismen bieten verschiedene Ansätze zur Behandlung
  von Synchronisationsproblemen an. Wesentliche Unterschiede ergeben
  sich in dem Ausmaß der Unterstützung einer sicheren,
  programmtechnischen Lösung von Synchronisationsproblemen. Zur
  Realisierung dieser Mechanismen ist immer mindestens ein
  grundlegendes Verfahren aus Abschnitt~\ref{ERWEITERT} notwendig,
  das seinerseits wieder auf einer der in Abschnitt~\ref{BASIC}
  beschriebenen Basismethoden aufbauen muß. Um eine Weiterentwicklung
  und Erweiterbarkeit von Synchronisationsmechanismen zu
  gewährleisten, ist es sinnvoll, diesen hierarchischen Aufbau
  ebenfalls im Tycoon-System zur Verfügung zu stellen. Dieser Ansatz
  stellt eine größtmögliche Flexibilität bei der Lösung von
  Synchronisationsproblemen sicher.
  
\item Es sollten verschiedene Programmierstile, wie die
  Synchronisation mittels Nachrichtenaustausch über
  Kommunikationskanäle und über gemeinsam benutzte Variablen, möglich
  sein.
  
\item Abhängig vom vorliegenden Synchronisationsproblem, werden
  Synchronisationsmechanismen sehr oft  von den beteiligten
  Threads aufgerufen. Bei der Implementation der Mechanismen muß daher
  besonders auf eine hohe Leistungsfähigkeit geachtet werden.
  
\item Mobilität ist eine orthogonale Eigenschaft der Tycoon-Objekte
  und soll daher auch für Synchronisationsprimitive und erweiterte
  Verfahren gelten. Es ist beispielsweise denkbar, daß mehrere
  TL-Threads, die sich untereinander über bestimmte Mechanismen
  synchronisieren, gemeinsam in einen entfernten Objektspeicher
  migrieren. Die Synchronisationsbeziehungen zwischen diesen Threads
  müssen auch nach der Migration erhalten bleiben.
  
\item Die Mechanismen sollen keine Einschränkungen bezüglich der Menge
  der lösbaren Synchronisationsprobleme aufweisen.
\end{itemize}

\subsection{Aufbau der Mechanismen}
Die durch Syntaxerweiterungen gegebene Möglichkeit, die Sprache TL
nachträglich zu modifizieren, gestattet es, sich bei der Auswahl der
Synchronisationsmechanismen zunächst auf einen leicht
implementierbaren Satz von Synchronisationsprimitiven zu beschränken.
Wie bereits in Abschnitt~\ref{SYNCPROC} besprochen, können die dort
vorgestellten Synchronisationsmethoden auf eine Implementation durch
Semaphore zurückgeführt werden.  Die universellen Eigenschaften des
Semaphorkonzepts sowie seine leichte Implementierbarkeit lassen
Semaphore auch für persistente Objektsysteme als geeignete Kandidaten
für einen grundlegenden Synchronisationsmechanismus erscheinen.  Für
Semaphore gelten zwar die in Abschnitt~\ref{ERWEITERT} besprochenen
Nachteile wie Unübersichtlichkeit und Fehleranfälligkeit, sie sollten
jedoch wegen ihrer Allgemeinheit und Mächtigkeit dem Programmierer zur
Verfügung gestellt werden.  Für die leichte Programmierbarkeit
spezieller Anforderungen wie die gleichzeitige Manipulation von
Semaphoren erscheint es darüber hinaus sinnvoll, erweiterte
Semaphoroperationen, wie P- und V-Operationen auf mehreren Semaphoren,
zu implementieren.

Zur Programmierung von Monitoren bietet es sich an, das Konzept und
den Aufbau der Mutexe und Bedingungsvariablen (Condition variables)
der Sprache Modula-3 zu übernehmen~\cite{HKJN93}.  Diese Mechanismen
entsprechen im wesentlichen dem Monitorkonzept von Hoare
(Abschnitt~\ref{MONITOR}).  Mutexe sind leicht durch eine geringfügige
Modifikation der Semaphore, durch die Registrierung des zugeordneten
Threads, der aktuell das Mutex hält, zu implementieren.

Für alle weiteren, in Abschnitt~\ref{ERWEITERT} genannten Verfahren wie
Rendezvous und kritische Regionen werden Erweiterungen der Sprache TL
vorgesehen. Beispielhafte Syntaxerweiterungen für Rendezvous werden
in Abschnitt~\ref{HIGHER} behandelt.

\begin{figure}
  \begin{center}\leavevmode
    \epsfxsize=0.5\textwidth \epsfbox{pictures/aufbau-laufzeit-sync.eps}
  \end{center}
  \caption{Synchronisationsmethoden und Laufzeitsystem}
  \label{EINORD}
\end{figure}

\subsubsection{Einordnung in die Systemarchitektur}
Eine Voraussetzung für jede Art von Synchronisation ist die
Sicherstellung eines unteilbaren Zugriffs auf gemeinsam genutzte
Objekte. Diese Voraussetzung wird in Mehrprozessorsystemen durch
Verwendung atomarer Maschineninstruktionen, in Einprozessorsystemen
durch Unterbrechungssperren erfüllt. Im Tycoon-System erfolgt jeder
Zugriff auf persistente Objekte über das Speicherprotokoll TSP, das
unter anderem den unteilbaren Zugriff auf Objekte unterstützt. Diese
im transaktionalen Sinn zu verstehende Eigenschaft des
Speicherprotokolls ist eng mit den Eigenschaften des jeweils konkret
eingesetzten Objektspeichers verknüpft, der eine derartige
Funktionalität bereits unterstützten muß. Eine Erweiterung des TSP zur
generischen Unterstützung von Transaktionen mit interner Parallelität
wäre ein Ansatzpunkt für die Unterstützung kooperativer, nebenläufiger
Aktivitäten. Die Implementation nebenläufiger Aktivitäten ist jedoch
unabhängig von Speicherprotokoll und Objektspeicher im Laufzeitsystem
angesiedelt. Zur generischen Unterstützung von Synchronisation unter
Beibehaltung des vorhandenen, geschichteten Systemaufbaus ist es
erforderlich, die Basisfunktionalität für Synchronisationsmethoden
ebenfalls im Laufzeitsystem anzusiedeln.

Abbildung~\ref{EINORD} zeigt die Einordnung der
Synchronisationsfunktionalität in den Aufbau des
Tycoon-Laufzeitsystems. Ohne die Erläuterung des Systemaufbaus aus
Abschnitt~\ref{RUNTIME} vorwegzunehmen, ist der genannten Abbildung
die Isolation der Basisfunktionalität zur Synchronisation auf das
Modul {\em RT}, in dem die Koroutinenverwaltung des Tycoon-Systems
angesiedelt ist, zu entnehmen. 


\subsubsection{Basismethoden}
\label{Basisauswahl}
Es stellt sich die Frage, welcher Mechanismus der Basismethoden aus
Abschnitt~\ref{BASIC} zur Implementation weitergehender
Synchronisationsmethoden benutzt werden soll. Wie bereits angemerkt,
ist das Tycoon-Laufzeitsystem in seiner jetzigen Form als von
Synchronisationsmethoden des Betriebssystems unabhängige, virtuelle
Maschine konzipiert. Auch auf Mehrprozessormaschinen wird eine Instanz
des Tycoon-Systems stets als ein einzelner Benutzerprozeß ausgeführt.
Nebenläufigkeit wird vollständig vom Laufzeitsystem selbst
kontrolliert und greift auf keine der in Mehrprozessorbetriebssystemen
vorhandenen Systemaufrufe zur Kontrolle nebenläufiger Aktivitäten
zurück. Diese, die Portabilität des Tycoon-Systems garantierende
Eigenschaft, läßt die Verwendung betriebssystemspezifischer
Mechanismen oder den Einsatz atomarer Maschineninstruktionen als nicht
zweckmäßig erscheinen. Es ist daher sinnvoll, für
Basissynchronisationsmethoden den Aufbau des Laufzeitsystems als
virtuelle Maschine auszunutzen und direkt in die interne
Koroutinenverwaltung einzugreifen. Atomare Aktionen von
Tycoon-Threads, die intern im Laufzeitsystem als Koroutinen realisiert
sind, können durch eine Verhinderung eines Koroutinenwechsels
sichergestellt werden.  Ein solcher Mechanismus entspricht den in
Abschnitt~\ref{BASIC} vorgestellten Unterbrechungssperren.
Abbildung~\ref{KOROUTWECHSEL} verdeutlicht die Unterbindung eines
Koroutinenwechsels während  eines kritischen Abschnitts. Dieser
Mechanismus sollte nur zur Sicherung kurzer, kritischer Abschnitte in
den darauf aufbauenden Synchronisationsmechanismen benutzt werden, um
die Nebenläufigkeit innerhalb des Systems nicht unnötig
einzuschränken.
\begin{figure}
  \begin{center}\leavevmode
    \epsfxsize=0.5\textwidth \epsfbox{pictures/koroutinen-wechsel.eps}
  \end{center}
  \caption{Unterbindung eines Koroutinenwechsels}
  \label{KOROUTWECHSEL}
\end{figure}

\subsubsection{Zusammenfassung} 
Die Unterteilung des Tycoon-Systems in Laufzeitsystem und
Speicherprotokoll TSP sowie die Konzeption des Laufzeitsystems als
virtuelle Einprozessormaschine ermöglichen es,
Synchronisationsmechanismen unter Verwendung der Verhinderung von
Koroutinenwechseln zu entwickeln.  Der Aufbau der
Synchronisationsmethoden gestaltet sich wie folgt:
\begin{itemize}
\item  Bereitstellung eines Mechanismus, der in kritischen
  Abschnitten eine Zuteilung von Rechenzeit an weitere Koroutinen
  unterbindet. 
\item Implementation von Semaphoren und Mutexen sowie von
  Bedingungsvariablen als eigenständige Module. Diese Module werden
  mittels der Programmiersprache TL implementiert. 
\item Implementation höherer Synchronisationsmechanismen unter
  Benutzung von Syn\-tax\-erweiterungen und Funktionen höherer Ordnung.
\end{itemize}
Abbildung~\ref{synch} gibt einen Überblick über den Aufbau der
Synchronisationsmechanismen und die Einordnung in die Hierarchie der
Synchronisationsmethoden (vgl. Abschnitt~\ref{SYNCHMECH}).

\begin{figure}
  \begin{center}\leavevmode
    \epsfxsize=0.75\textwidth \epsfbox{pictures/sync-tycoon.eps}
  \end{center}
  \caption{Aufbau und Zuordnung der Synchronisationsmethoden}
  \label{synch}
\end{figure}


\section{Bibliotheken für Synchronisationsmechanismen}
\label{SPEC}
Der Aufbau der Synchronisationsprimitive gliedert sich analog zu der
in Abbildung~\ref{synch} gezeigten Darstellung. Aufbauend auf dem im
Systemmodul {\em thread} (siehe Anhang~\ref{Thread}) implementierten
Mechanismus {\em thread.atomic} zur zeitweisen Sperrung von
Koroutinenwechseln, werden in diesem Abschnitt Tycoon-Module für
Semaphore, Mutexe und Bedingungsvariablen vorgestellt. Es werden die
implementierten Funktionsaufrufe der einzelnen Module sowie einige
Bespiele für ihre Anwendung beschrieben. Die Beschreibung der
Implementation der Funktion {\em thread.atomic} folgt in
Abschnitt~\ref{RUNTIME}.

\subsection{Semaphore}
Im Modul {\em semaphore} sind allgemeine Semaphore mit beliebigem
Anfangswert für die internen Zähler eines Semaphors implementiert. 
%Die
%genaue Beschreibung der Programmierschnittstelle ist aus
%Anhang~\ref{Modulschnitt} ersichtlich. 
Vom Modul werden der abstrakte Datentyp {\em semaphore.T} sowie die für
diesen Datentyp definierten Funktionen exportiert. Ein Element des
Typs {\em semaphore.T} wird mittels der Operation
\begin{xple}
new(count :Int) :T
\end{xple}
instantiiert. Hierbei gibt der Wert der ganzzahligen Variablen {\em
  count} die Anzahl der Threads an, die ein Semaphor akquirieren
können, ohne daß der Versuch der Akquisition zu einer Blockierung des
aufrufenden Threads führt. Diese Funktionalität kann beispielsweise zur
Verwaltung von Ressourcen benutzt werden, die einen gleichzeitigen Zugriff
von {\em count}-Threads erlauben.

Für den Zugriff auf eine Instanz des Datentyps {\em
  semaphore.T} werden vom Modul die folgenden Funktionen exportiert:
\begin{xple}
wait(sem :T) :\k{Ok}

post(sem :T) :\k{Ok}
\end{xple}
Die Funktionen {\em wait} und {\em post} entsprechen den in
Abschnitt~\ref{Semaphore} beschriebenen {\em P-} und {\em
  V}-Oper\-atio\-nen. Der Versuch, die Operation {\em wait} auf einen
Semaphor anzuwenden, führt nach $count+1$ Aufrufen dieser Funktion zur
Suspendierung des aufrufenden Threads, wenn vorher keine Erhöhung des
internen Zählers des Semaphors mittels der Funktion {\em post}
erfolgte.  Mit der Funktion {\em post} wird der interne Zähler des
Semaphors um den Wert $1$ erhöht und einer der auf das Semaphor
wartenden Threads aktiviert. Auf einen Semaphor wartende Threads werden
in einer Warteschlange verwaltet, um eine faire Zuteilung des Semaphors
zu gewährleisten. Es ist zu beachten, daß die Funktionen {\em wait}
und {\em post} für ein gegebenes Semaphor {\em sem} von verschiedenen
Threads aufgerufen werden können. Hiermit läßt sich zusätzlich zum
Schutz von kritischen Abschnitten ein Austausch von Signalen
realisieren. Das folgende Beispiel beschreibt den Schutz eines
kritischen Abschnitts sowie einen Signalaustausch:
\begin{xple}
(* Verwaltung des Zugriffs auf einen Ringpuffer des Typs :Int und der Länge N *)
\k{let} N = \ldots   (* Länge des Ringpuffers *)
\k{let} buffer = arrayOp.new(:Int N 0)
\k{let} protect = semaphore.new(1)
\k{let} full    = semaphore.new(0)
\k{let} empty   = semaphore.new(N)
\k{let} \k{var} inpointer = 0  \k{and}  \k{var} outpointer = 0
\end{xple}
\begin{minipage}[t]{2.9in}
\begin{xple}
(* Ein Element schreiben *)
\k{let} putElement(element :Int) :\k{Ok} =
  \k{begin}
    semaphore.wait(empty)
    semaphore.wait(protect)
    buffer[inpointer] := element
    inpointer := \{inpointer + 1\} \% N
    semaphore.post(protect)
    semaphore.post(full)
  \k{end}
\end{xple}
\end{minipage}
\begin{minipage}[t]{2.9in}
\begin{xple}
(* Ein Element lesen *)
\k{let} getElement() :Int =
  \k{begin}
    semaphore.wait(full)
    semaphore.wait(protect)
    \k{let} element = buffer[outpointer]
    outpointer:= \{outpointer + 1\} \% N
    semaphore.post(protect)
    semaphore.post(empty)
    element
  \k{end}
\end{xple}
\end{minipage}
\vskip 0.5cm
Im obigen Beispiel dient das Semaphor {\em protect} dem Schutz der
Integrität des Ringpuffers {\em buffer} und der Variablen {\em
  inpointer} sowie {\em outpointer}. Diese Variablen geben die
aktuelle Position für Schreib- und Lesevorgänge im Puffer an. Die
Initialisierung des Semaphors {\em protect} mit dem Wert $1$
garantiert, daß höchstens ein Thread innerhalb der Funktionen {\em
  getElement} und {\em putElement} aktiv ist. Demgegenüber dienen die
Semaphore {\em full} und {\em empty} der Signalisierung des Zustandes
des Ringpuffers. Ist die maximale Länge des Puffers erreicht, wurde
auf das Semaphor {\em empty} N--mal zugegriffen, und Threads, die die
Funktion {\em putElement} aufrufen, werden verzögert, bis durch einen
Aufruf der Funktion {\em getElement} ein Element entnommen wird. Ein
leerer Puffer führt zu einer Suspendierung eines {\em getElement}
aufrufenden Threads durch das Semaphor {\em full}. Hierdurch wird ein
Lesen aus einem leeren Puffer verhindert.

Die weiteren, im Modul {\em semaphore} enthaltenen Funktionen sind:
\begin{xple}
 tryWait(sem :T) :Bool

 waitMultipleOr(semarray :Array(T)) :T

 waitMultipleAnd(semarray :Array(T)) :\k{Ok}

 postMultiple(semarray :Array(T)) :\k{Ok}
\end{xple}
Mittels der Funktion {\em tryWait} wird versucht, einen Semaphor {\em
  sem} zu akquirieren. Gelingt dies, ist der interne Zähler des
Semaphors {\em sem} um den Wert $1$ vermindert, und die Funktion gibt
den boolschen Wert {\em true} zurück, andernfalls ist das Ergebnis der
Funktion {\em false}. Diese Funktion führt in keinem Fall zu einer
Suspendierung des aufrufenden Threads und kann zum versuchsweisen
Zugriff auf kritische Abschnitte benutzt werden. Gelingt die
Akquisition des Semaphors nicht, können beispielsweise andere
Funktionen ausgeführt werden.

Die Funktionen {\em waitMultipleOr} und {\em waitMultipleAnd} dienen
dem gleichzeitigen Zugriff auf eine Menge von Semaphoren. Die Funktion
{\em waitMultipleOr} gibt ein freies Semaphor aus der in dem Array
{\em semarray} angeführten Menge von Semaphoren zurück. Sind alle
Semaphore belegt (alle Semaphore besitzen einen internen Zählerwert
von $\leq 0$), wird der aufrufende Thread verzögert. Die Freigabe
eines oder mehrerer Semaphore führt zur erneuten Aktivierung des
Threads, wobei im Falle mehrerer freier Semaphore eine zufällige
Auswahl getroffen wird. Das beim Aufruf dieser Funktion manipulierte
Semaphor wird als Wert von {\em waitMultipleOr} zurückgegeben. Mit der
Funktion {\em waitMultipleAnd} wird die gesamte Menge der in {\em
  semarray} angegebenen Semaphore manipuliert. Diese Funktion kehrt
zurück, wenn alle Semaphore belegt werden konnten. Dadurch ist es
beispielsweise einfach möglich, eine Menge von Betriebsmitteln oder
kritischen Abschnitten gleichzeitig zu belegen. Es ist darauf
hinzuweisen, daß die Operationen {\em waitMultipleOr} und {\em
  waitMultipleAnd} auch mittels der elementaren Semaphorfunktionen
{\em wait} und {\em post} direkt programmiert werden
können~\cite{Dijk71}. Darüber hinaus muß bei der Operation {\em
  waitMultipleAnd} auf die Reihenfolge der im Array {\em semarray}
aufgeführten Semaphore geachtet werden. Alle Threads, die eine {\em
  waitMultipleAnd}-Operation auf der gleichen (Teil)-Menge von
Semaphoren ausführen, müssen die verwendeten Semaphore in gleicher
Reihenfolge angeben, da sonst eine Verklemmung entstehen
kann~\cite{Dijk71}.

\subsection{Mutexe und Bedingungsvariable}
Die Module {\em mutex} und {\em condition} vervollständigen die für
das Tycoon-System implementierten Basissynchronisationsmechanismen.
Diese Module dienen ebenfalls dem Schutz von kritischen Abschnitten
sowie dem Signalisieren von Bedingungen. Mutexe bieten eine den
binären Semaphoren ähnelnde Funktionalität, weisen aber im Gegensatz
zu diesen einige Einschränkungen bezüglich ihrer Verwendung auf. Ein
Mutex ist ein einfacher Mechanismus zur Sperrung von kritischen
Abschnitten.  Ein Mutex befindet sich immer in einem von zwei
möglichen Zuständen, es ist entweder gesperrt oder frei. Ein
gesperrtes Mutex kann nur von dem Thread, der das Mutex gesperrt hat,
wieder freigegeben werden.  Diese Eigenschaft verhindert die
versehentliche Freigabe eines kritischen Abschnitts durch von der
beabsichtigten Programmlogik eigentlich nicht berechtigte Threads,
verhindert aber eine Kommunikation zwischen Threads analog zu dem im
vorangegangenen Abschnitt beschriebenen Beispiel des
Ringpuffers.  Weiterhin ist es bei der Realisierung kritischer
Abschnitte durch Mutexe nur durch zusätzliche Mechanismen möglich, daß
sich mehrere Threads in einem solchen Abschnitt befinden. Ein Mutex
stellt die einfachste Möglichkeit dar, kritische Abschnitte zu
realisieren. Das Modul {\em mutex} ist wie folgt aufgebaut: Ein
Element des Typs {\em mutex.T} wird mittels der Operationen
\begin{xple}
new() :T

newLocked():T
\end{xple}
erzeugt. Die Funktion {\em new} gibt eine freies, nicht gesperrtes
Mutex zurück, ein Aufruf der Funktion {\em newLocked} liefert ein
bereits gesperrtes Mutex.  

Die Zugriffsfunktionen für ein Element des Typs {\em mutex.T} bestehen
aus den Aufrufen
\begin{xple}
 lock(mutex :T) :\k{Ok}

 unlock(mutex :T) :\k{Ok}

 tryLock(mutex :T) :Bool
\end{xple}
Der Aufruf der Funktion {\em lock} führt zu einer Suspendierung des
aufrufenden Threads, falls das Mutex schon gesperrt wurde. Die
Funktion {\em unlock} gibt ein gesperrtes Mutex wieder frei und führt
zu einer Aktivierung eines eventuell wartenden Threads. Wird die
Funktion {\em unlock} nicht von dem Thread aufgerufen, der das Mutex
gesperrt hat, wird der Ausnahmefehler {\em mutex.error} generiert.
Auch im Modul {\em mutex} werden wartende Threads in einer
Warteschlange verwaltet, um eine faire Zuteilung der Mutexe zu
gewährleisten. Ein Aufruf der Funktion {\em tryLock} führt zur
Sperrung des angegebenen (freien) Mutex, aber bei bereits gesperrtem
Mutex nicht zur Suspendierung des aufrufenden Threads. Bei einem
erfolgreichen Sperren des Mutex wird der boolsche Wert {\em true}
zurückgegeben, andernfalls ergibt die Auswertung von {\em tryLock} den
Wert {\em false}.

Zur Lösung von Programmierproblemen, die die Freigabe eines kritischen
Abschnitts bis zu Eintritt eines spezifizierten Ereignisses erfordern,
sind die Funktionen im Modul {\em condition} vorgesehen. Diese
Funktionalität entspricht der in Abschnitt~\ref{MONITOR} beschriebenen
Funktionalität der Modula-3--Monitore und wird in der folgenden
Beschreibung der einzelnen Funktionsaufrufe näher erläutert.
\begin{xple}
new() :T
\end{xple}
Die Funktion {\em new} erzeugt eine neue Bedingungsvariable des Typs
{\em condition.T}. Auf einer solchen Variablen sind die folgenden
Funktionen implementiert:
\begin{xple}
  wait(m :mutex.T  cond :T) :\k{Ok}
 
  timedWait(m: mutex.T  cond :T  timeout :time.T) :\k{Ok}

  signal(cond :T) :\k{Ok}

  broadcast(cond :T) :\k{Ok}
\end{xple}
Die Benutzung einer gegebenen Bedingungsvariablen erfolgt immer
zusammen mit dem der Bedingungsvariablen logisch zugeordneten Mutex.
Zur Ausführung der Operation {\em wait(mu\-tex condition)} ist es
erforderlich, daß der aufrufende Thread das Mutex {\em mutex} bereits
gesperrt hat. Der Aufruf dieser Funktion entsperrt das Mutex und
blockiert den Thread auf der der Bedingungsvariablen zugeordneten
Warteschlange. Dies führt zur Freigabe des durch das Mutex geschützten
kritischen Abschnitts, ein weiterer Thread kann nach Akquisition des
Mutex in den kritischen Abschnitt eintreten.

Die Angabe eines maximalen Wartezeitraums bis zum Eintreten einer
Bedingung ermöglicht der Aufruf der Funktion {\em timedWait}. Wird die
Bedingung nicht bis zum Erreichen des angegebenen Zeitpunkts
signalisiert, kehrt die Funktion {\em timedWait} nach erneutem Sperren
des verwendeten Mutex zurück.

Die Erfüllung der mit einer Bedingungsvariablen verknüpften Bedingung
wird durch die Funktion {\em signal} angezeigt. Der Aufruf dieser
Funktion bewirkt eine Deblockierung eines auf die jeweilige
Bedingungsvariablen wartenden Threads. Sind keine wartenden Threads
vorhanden, erfolgt keine weitere Aktion. Die Funktion {\em broadcast}
startet alle auf eine Bedingungsvariable wartenden Threads. Die
Abbildungen~\ref{lock} sowie~\ref{barrier} illustrieren die beiden
folgenden Programmbeispiele zur Verwendung von Mutexen und
Bedingungsvariablen.

Die Sperrung eines kritischen Abschnitts unter Verwendung von Mutexen
zeigt folgendes Programmfragment (vgl.\ Abbildung~\ref{lock}):
\begin{xple}
\k{let} lock = mutex.new()

mutex.lock(lock)
 (* kritischer Abschnitt *)
mutex.unlock(lock)
\end{xple}
\begin{figure}
\begin{center}\leavevmode
  \epsfxsize=0.25\textwidth \epsfbox{pictures/lock.eps}
\end{center}
\caption{Sperrung kritischer Abschnitte}
\label{lock}
\end{figure}

Das folgende, etwas anspruchsvollere Beispiel zeigt das Warten mehrerer
Threads aufeinander (vgl.\ Abbildung~\ref{barrier}):
\begin{xple}
\k{let} lock = mutex.new()
\k{let} cond = condition.new()
\k{let} \k{var} barrierCount = 0

\k{let} barrier(n :Int) =
 \k{begin}
   mutex.lock(lock)
     barrierCount := barrierCount + 1
     \k{if} barrierCount == n \k{then}
       condition.broadcast(cond)
       barrierCount := 0
     \k{else}
       \k{while} barrierCount $<$ n \k{do}
         condition.wait(lock  cond)
       \k{end}
     \k{end}
    mutex.unlock(lock)
  \k{end}

\k{let} doA() = \ldots
\k{let} doB() = \ldots

\k{let} funcA(n :Int  f :\k{Fun}():\k{Ok}) =
 \k{begin}
   \ldots  f() \ldots
   barrier(n)
   \ldots
 \k{end}

\k{let} threadA = thread.fork(\k{fun}(self :thread.T(\k{Ok})) funcA(2 doA))
\k{let} threadB = thread.fork(\k{fun}(self :thread.T(\k{Ok})) funcA(2 doB))
\end{xple}

Jeder der {\em N} Threads ruft zu
einem bestimmten Zeitpunkt die im obigen Programmfragment angegebene
Funktion {\em barrier} mit dem Argument {\em N} auf. Der Aufruf dieser
Funktion bewirkt eine Blockierung aller {\em barrier } aufrufenden
$N-1$ Threads. Alle Threads warten an der Barriere {\em barrier}
aufeinander, bis beim {\em N}--ten Thread schließlich die Ausführung der
Funktion {\em broadcast} zur Wiederaktivierung aller auf die
Bedingungsvariable {\em cond} wartenden Threads führt (Funktion {\em
  barrier}). 

\begin{figure}
\begin{center}\leavevmode
  \epsfxsize=0.25\textwidth \epsfbox{pictures/barrier.eps}
\end{center}
\caption{Synchronisation an einer Barriere}
\label{barrier}
\end{figure} 

Ein analoges Beispiel zeigt das Warten eines Threads auf $N$ weitere
Threads: 
\begin{xple}
\k{let} lock  = mutex.new()
\k{let} cond  = condition.new()
\k{let} \k{var} N = 0

(* Initialisierung der gemeinsam benutzten Variablen N *)
\k{let} initWait(n :Int) =
  \k{begin}
    mutex.lock(lock)
      $N := n$
    mutex.unlock(lock)
  \k{end}

(* Auf das Eintreffen von N Threads warten *)
\k{let} waitForAll() =
  \k{begin}
    mutex.lock(lock)
      \k{while} $N > 0$ \k{do}
        condition.wait(lock  cond)
      \k{end}
    mutex.unlock(lock)
  \k{end}

(* Alle wartenden Threads wieder aktivieren *)
\k{let} barrier() =
  \k{begin}
    mutex.lock(lock)
      $N := N - 1$
      \k{if} N == 0 \k{then}
        condition.broadcast(cond)
      \k{else} 
        \k{while} $N > 0$ \k{do}
          condition.wait(lock  cond)
        \k{end}
      \k{end}
    mutex.unlock(lock)
  \k{end}
\end{xple}
Von einem Thread {\em A} werden {\em N} weitere Threads gestartet.  Vor
dem Starten weiterer Threads initialisiert Thread {\em A} den gemeinsam
benutzten Zähler {\em N} durch die Funktion {\em initWait}. Thread {\em A}
wartet daraufhin durch Aufruf der Funktion {\em waitForAll} auf die
Erfüllung der Bedingung {\em cond} durch alle durch ihn initiierten Threads.
Die durch Thread {\em A} gestarteten, untergeordneten
Threads warten durch Aufruf der Funktion {\em barrier}
aufeinander. Der {\em N}--te, {\em barrier} aufrufende Thread aktiviert
alle durch den Thread {\em A} gestarteten Threads, sowie den Thread
{\em A} selbst.


Ein Beispiel für die Verwendung der Funktion {\em timedWait} zeigt
der folgende Programmausschnitt. Ein Thread, dessen maximaler,
akzeptabler Zeitraum bis zum Eintreten des Ereignisses {\em cond} drei
Sekunden betragen soll, initialisiert die Variable {\em timeout} und
ruft die Funktion {\em timedWait} mit diesem Parameter auf. Zuvor wird
in einer Programmschleife die mit der Bedingungsvariable {\em cond}
verknüpfte Bedingung geprüft. Ist diese  erfüllt, wird mit
der Ausführung weiterer Aktionen fortgefahren und der Schleifenkörper
verlassen. Andernfalls wird die Überschreitung des gewählten
Zeitpunkts getestet. Im Fall einer Überschreitung des angegebenen
Zeitpunkts wird eine Ausnahmebedingung erzeugt:
\begin{xple}
\k{let} m = mutex.new()  \k{and}  cond = condition.new()

 mutex.lock(m)
   (* Das Timeoutintervall beträgt drei Sekunden *)
   \k{let} timeout = time.add(time.now()  time.create(0 0 3 0))
   \k{loop}
     \k{if} {\em $<$ Bedingung erfüllt $>$} \k{then}
       (* Weitere Aktionen des Programms *)
       \k{exit}
     \k{end}
     \k{if} time.greaterEqual(time.now()  timeout) \k{then}
       \k{raise} condition.timeout \k{end}
     \k{end}
     condition.timedWait(m  cond  timeout)        
   \k{end}
 mutex.unlock(m)
\end{xple}
  
Die angeführten Beispiele zeigen die korrekte Verwendung des
Condition-Mechanismus, da, wie in Abschnitt~\ref{MONITOR} bereits
angemerkt, die Erfüllung einer Bedingung nach Wiederaktivierung eines
Threads durch die Funktion {\em signal} nicht gewährleistet ist.
Beispielsweise kann jeder Thread, der das Mutex {\em lock} im obigen
Programmfragment akquiriert, den durch das Mutex geschützten Wert
ändern. Dieses macht ein erneutes Testen der mit einer Bedingungsvariablen
verknüpften Bedingung notwendig.


\section{Implementation im Tycoon-System}
\label{IMPL}
Zur Implementation atomarer Aktionen im Tycoon-System wird in
Abschnitt~\ref{Basisauswahl} die Benutzung eines Mechanismus zur
Verhinderung von Koroutinenwechsel vorgeschlagen. Um einen Ansatz für
die Implementation eines derartigen Mechanismus zu finden, ist es
notwendig, das im Tycoon-System realisierte Laufzeitsystem näher zu
betrachten. Der Aufbau und die Arbeitsweise des Laufzeitsystems werden
daher im folgenden Abschnitt erläutert. Daran anschließend werden die
zur Sicherstellung des Basismechanismus notwendigen Eingriffe in das
Laufzeitsystem beschrieben. Die Bereitstellung eines
Timeout-Mechanismus für den im Modul {\em condition} vorhandenen
Funktionsaufruf {\em timedWait} erfordert ebenfalls unterstützende
Maßnahmen im Laufzeitsystem. Zur Modifikation des Laufzeitsystems
ist die Benutzung der für die Implementation des Laufzeitsystems
verwendeten Programmiersprache C notwendig. Die für die Erweiterung
des Laufzeitsystems verwendeten Datenstrukturen müssen wie Objekte der
Programmiersprache TL die Eigenschaft der Persistenz besitzen. Dies
wird durch die im nächsten Abschnitt beschriebenen Maßnahmen erreicht.
Zur Implementation der auf dem Basismechanismus aufbauenden Module
{\em semaphore}, {\em mutex} und {\em condition} wird ausschließlich
die Programmiersprache TL verwendet. Dieser Einsatz von TL sichert
automatisch die Persistenz aller verwendeten Programmobjekte.

Der folgende  Abschnitt gibt einen Überblick über das im Tycoon-System
implementierte Laufzeitsystems.

\subsection{Das Laufzeitsystem}
\label{RUNTIME}
Das Tycoon-Laufzeitsystem ist fast vollständig\footnote{Zur
  Realisierung eines Koroutinenwechsels für das Betriebssystem SunOS 4
  war der Einsatz einer Maschinenanweisung zur Simulation der Funktion
  {\em setjump} erforderlich~\cite{BM96}.} in der standardisierten
Programmiersprache Ansi-C ge\-schrie\-ben. Dieser Sachverhalt sowie
der modulare Aufbau des Laufzeitsystems gewährleisten die
Portierbarkeit auf weitere Betriebssysteme. Das Tycoon-Laufzeitsystem
gliedert sich in die folgenden drei Komponenten~\cite{BM96}:
\begin{figure}
\begin{center}\leavevmode
  \epsfxsize=0.35\textwidth \epsfbox{pictures/rt.eps}
\end{center}
\caption{Schematischer Aufbau des Laufzeitsystems}
\label{rtsarch}
\end{figure}

\begin{description}
\item[RT (``RunTime''-Support):] Mit dieser Komponente wird den
  weiteren Teilen des Laufzeitsystems eine genormte Schnittstelle für
  betriebssystemspezifische Operationen zur Verfügung gestellt. Diese
  Operationen umfassen unter anderem die Dateiverwaltung und sonstige
  Ein- und Ausgabefunktionen sowie Zugriffsfunktionen zur
  Speicherverwaltung des Betriebssystems. Weiterhin ist in dieser
  Komponente die gesamte Koroutinenverwaltung implementiert. Ein
  weiterer wichtiger Teil des {\em RT} ist die Unterkomponente {\em
    rtsession}. In diesem Modul werden flüchtige Variablen des
  Laufzeitsystems registriert, die eine Sitzung im Tycoonsystem
  überdauern sollen. Diese registrierten Variablen werden vor einer
  Stabilisierung des Objektspeichers in Objektspeicherstrukturen
  übertragen und sind somit persistent. Bei einem Neustart des
  Systems oder der Rücknahme einer Transaktion werden diese
  persistenten Variablen in die entsprechenden C-Strukturen
  zurückübertragen und stehen zur weiteren Benutzung durch das
  Laufzeitsystem zur Verfügung.
  
\item[TM (``Tycoon Machine''):] Die Tycoon Maschine stellt den
  Hauptteil des Laufzeitsystems dar. Hier ist der Bytecodeinterpreter,
  der den vom Tycoon-Übersetzer erzeugten Bytecode direkt abarbeitet,
  angesiedelt.  Weitere Funktionen dieser Komponente sind die
  Transaktionsverwaltung sowie die Verwaltung persistenter
  Sicherungspunkte.

\item[TL (``Tycoon Language''-Extensions):] Dieser Teil des
  Laufzeitsystems enthält eine Reihe von Funktionen, die ihrerseits von
  verschiedenen Tycoon--Modulen benutzt werden. Es handelt sich hierbei um
  Hilfsfunktionen, deren Aufgaben auf der Ebene der Programmiersprache
  TL nicht oder nur mit großem Aufwand realisiert werden
  können. Hierunter sind Funktionen zur Threadsteuerung, typunsichere
  Operationen auf TL--Objekten, Hilfsfunktionen für C--Callbacks und
  Funktionen zur Symbolverwaltung für dynamisches Linken von
  TL-Objekten zu finden.
\end{description}


In Abbildung~\ref{rtsarch} sind die Abhängigkeiten der einzelnen
Laufzeitsystemkomponenten dargestellt. Die Komponente {\em TL} benutzt
 Funktionen aus den Komponenten {\em TM} und {\em RT}. In der
 Komponente {\em TM} werden unter anderem die von {\em RT}
 bereitgestellten Funktionen zur Koroutinenumschaltung benutzt. Nur die
 Komponente {\em RT} greift  auf Funktionen des
 unterliegenden Betriebssystems zurück. 
 
\begin{figure}
\begin{center}\leavevmode
  \epsfxsize=0.5\textwidth \epsfbox{pictures/ring.eps}
\end{center}
\caption{Anordnung der aktiven Koroutinen}
\label{COROUT}
\end{figure}

Threads werden im Tycoon-System durch Koroutinen simuliert. Die
grundlegende Verwaltung der Koroutinen ist in Abbbildung~\ref{COROUT}
illustriert. Die sich im Tycoon-System befindenden, aktiven Koroutinen
sind in einer doppelt verketteten Ringstruktur angeordnet. Die
Umschaltung zwischen diesen Koroutinen findet zyklisch und abhängig
von einem Zeitgeber während der Abarbeitung des Bytecodes in der
Komponente {\em TM} statt. Zu diesem Zweck wird durch eine
Zeitgeberroutine die Tycoon-Systemvariable {\em rtcorout\_fSwitch}
gesetzt. An ausgesuchten Punkten des Tycoon-Bytecodeinterpreters wird
diese Systemvariable ausgewertet.  Abhängig vom ihrem Wert findet dann
durch Aufruf der Transferfunktion {\em rtcorout\_transfer} die
Umschaltung zur nächsten Koroutine des Rings statt. Dieses
nicht präemptive Verhalten stellt die Ununterbrechbarkeit der
Tycoon--Bytecodebefehle durch die Auswahl geeigneter Umschaltpunkte
sicher.
 
In einem Tycoon--System sind immer mindestens zwei Threads aktiv:
Dies sind der sogenannte Superthread und der Hauptthread der
Tycoon-Sitzung.  Bestimmte Funktionen des Laufzeitsystems können nur
durch den Superthread ausgeführt werden.  Hierzu gehören alle
Funktionen, die mit der Transaktionsverwaltung gekoppelt sind. Während
der Stabilisierung des Objektspeichers können beispielsweise keine
Threads außer dem angesprochenen Superthread aktiv sein, da der
derzeitige Zustand dieser Threads im Objektspeicher durch die
Stabilisierung persistent gemacht wird. Der Superthread ist der
einzige nichtpersistente Thread im Tycoon-System. Bei jedem Start des
Systems wird ein neuer Superthread erzeugt, der alle zuvor aktiven
Threads wieder aktiviert.
 
Im einzelnen  wird die Koroutinenverwaltung in der Komponente {\em RT}
prinzipiell mittels folgender Funktionen verwirklicht.  Weitere, die
Koroutinenverwaltung betreffende Hilfsfunktionen werden detailliert in
\cite{Breil95} beschrieben.
\begin{description}
\item[rtcorout\_new:] Es wird eine neue Koroutine unter Verwendung der
  C-Bibliotheksfunktion {\em set\-jmp} erzeugt~\cite{SV90}. Zu diesem
  Zweck wird durch eine weitere Funktion des {\em RT} ein
  Speicherbereich für die Prozessorregister und den Stackbereich der
  Koroutine bereitgestellt. Zu diesen Prozessorregistern zählt ein
  Zeiger, der die aktuelle Position des auszuführenden Maschinencodes
  angibt. Dieser Zeiger wird dann durch die Adresse der Funktion {\em
    tmexec\_runGC}, in der der eigentliche Bytekodeinterpreter kodiert
  ist, ersetzt. Durch diese Vorgehensweise wird eine Stackumgebung
  erzeugt, die bei einer nachfolgenden Aktivierung der Koroutine zu
  der Ausführung einer weiteren Instanz des Bytekodeinterpreters
  führt.
\item[rtcorout\_transfer:] Diese Funktion führt zu einer Umschaltung
  zu einer weiteren Koroutine. Mittels der C-Bibliotheksfunktion {\em
    setjmp} werden die für die Ausführung relevanten Prozessorregister
  der aktuellen Koroutine gesichert. Die Funktion {\em longjmp}
  restauriert die durch ihre Parameter gegebene Prozessorumgebung und
  setzt die weitere Programmausführung gemäß dieser Umgebung fort.
\item[timerHandler:] Diese Routine dient zum zyklischen Aktivieren der
  Koroutinenumschaltung.
\end{description}

Die Schnittstelle zur Abbildung der persistenten Strukturen von
Tycoon-Threads auf Koroutinen wird durch die folgenden Funktionen
gewährleistet:
\begin{description}
\item[tmthread\_newGC:] Es wird eine neue Objektidentifikation {\em
    (OID)} für einen neu anzulegenden, persistenten Thread vom
  Objektspeicher angefordert. Diese Anforderung wird durch den Aufruf
  der entsprechenden Funktionen des Speicherprotokolls TSP erfüllt.
  Weiterhin werden durch zusätzliche Aufrufe des TSP persistente
  Speicherbereiche für den Stackbereich des Threads erzeugt.

\item[tmthread\_runGC:] Ein neu erzeugter oder bereits vorhandener
  Thread wird für die Aus\-füh\-rung durch die {\em TM}
  vorbereitet. Dies umfaßt die Erzeugung einer neuen Koroutine
  durch Aufruf der Funktion {\em rtcorout\_new} sowie die
  Initialisierung der flüchtigen Strukturen des
  Koroutinenrings mit den aus der persistenten Threadstruktur
  entnommenen Daten für Stackbereich und {\em TM}-Maschinenregister.

\item[tmthread\_stopGC:] Diese Routine wird bei einer Suspendierung
  oder Beendigung eines Threads abgearbeitet. Die aktuellen Werte der
  Register der {\em TM} werden wieder in die persistente Datenstruktur des
  Threads übertragen. Der der aktiven Koroutine zugeordnete,
  nichtpersistente Speicherbereich für die Ringstruktur der Koroutine
  wird abgebaut und an das Betriebssystem zurückgegeben.
\end{description}

\begin{figure}
\begin{center}\leavevmode
  \epsfxsize=0.5\textwidth \epsfbox{pictures/thread-states.eps}
\end{center}
\caption{Zustandsübergänge der Tycoon-Threads}
\label{tstates}
\end{figure}
Die Ausführungszustände und möglichen Zustandsübergänge der
Tycoon-Threads sind aus Abbildung~\ref{tstates} ersichtlich.
Übergänge zwischen den einzelnen Zuständen werden mittels der
entsprechenden Funktionen aus dem Modul {\em thread} (siehe
Anhang~\ref{Thread}) programmiert oder ergeben sich während der
Ausführung eines Threads.  Ein neu erzeugter Thread befindet sich im
Zustand {\em suspended} (Funktion {\em thread.new}) oder im Zustand
{\em running} ({\em thread.fork}). Beendete Threads befinden sich 
entweder im Zustand {\em terminated} oder, als Folge nicht
abgefangener Ausnahmebedingungen, im Zustand {\em exception}. In den
Zustand {\em blocking} gelangt ein Thread durch Aufruf der Funktion
{\em thread.join}. Diese Funktion führt zur Blockierung des
aufrufenden Threads, bis der als Parameter der Funktion {\em
  thread.join} angegebene Thread seine Ausführung beendet. Nur
Threads, die sich im Zustand {\em running} befinden, sind als Elemente
von Datenstrukturen des Laufzeitsystems erreichbar.  Alle Threads, die
sich in einem der anderen Zustände befinden, sind nur über die {\em
  OID}, die eine Referenz zur persistenten Datenstruktur der Threads
im Objektspeicher darstellt, erreichbar. Es existiert keine Struktur,
in der nicht aktive Threads verzeichnet sind.


\subsection{Interner Aufbau der Synchronisationsmechanismen}
\label{INTERN}
Zur Sicherstellung der atomaren Ausführung einer Befehlssequenz wird
in den internen Mechanismus des Laufzeitsystems zur
Koroutinenumschaltung eingegriffen. Zur Implementation eines
Timeoutmechanismus für die Funktion {\em timedWait} des Moduls {\em
  Condition} sind ebenfalls Erweiterungen des Laufzeitsystems
erforderlich. Alle weiteren Mechanismen zur Synchronisation sind
vollständig in der Sprache TL verfaßt. In den folgenden drei
Unterabschnitten sind Details der jeweiligen Implementation
beschrieben.

\subsubsection{Atomare Aktionen}
\label{ATOMIC}
Um eine Umschaltung zur nächsten Koroutine nach Ablauf des
vorgegebenen Zeitintervalls zu verhindern, wurde eine weitere
Variable des C-Laufzeitsystems, {\em tmthread\_nCritical}, eingeführt.
Zur Einleitung und Beendigung eines ununterbrechbaren Abschnitts
während der Ausführung eines Threads sind zwei Funktionen des
Laufzeitsystems vorgesehen:
\begin{description}
\item[tlthread\_beginCritical:] Der Wert der Variablen
  {\em tmthread\_nCritical} wird inkrementiert. 
\item[tlthread\_endCritical:] Der Wert der Variablen
  {\em tmthread\_nCritical} wird dekrementiert.
\end{description}
Der Wert von {\em tmthread\_nCritical} wird in den im
Bytecodeinterpreter vorhandenen Umschaltpunkten für Koroutinen
ausgewertet. Liegt ein Wert ungleich Null vor, findet keine Umschaltung
zur nächsten Koroutine statt. Durch Inkrementieren und Dekrementieren
der Variablen {\em tmthread\_nCritical} sind geschachtelte, atomare
Aktionen eines Threads möglich.  Die Anwesenheit eines Threads in
einem ununterbrechbaren Abschnitt muß dauerhaft festgehalten werden, da
während der Ausführung alle Operationen des Systems ausgeführt werden
können. Dazu gehören auch alle Operationen zur Stabilisierung des
Objektspeichers. Diese Forderung wird durch Registrierung von {\em
  tmthread\_nCritical} als Sitzungsvariable, die unmittelbar vor der
Objektspeicherstabilisierung in eine persistente Struktur übertragen
wird, erfüllt.

Die Schnittstelle zur Benutzung der Funktionen {\em
  tlthread\_beginCritical} und {\em tlthread\_endCriti\-cal} ist im
Modul {\em thread} als Funktionsaufruf {\em thread.atomic}
implementiert. Das folgende Beispiel zeigt die Benutzung dieser
Funktion:
\begin{xple}
\k{let} \k{var} shared = 0

(* Funktion, die atomar auszuführen ist *)
\k{let} incAtomic(\k{var} x :Int) = 
  \k{begin}
    x := x + 1
    x
  \k{end}

(* Atomares Inkrementieren eines Werts *)
\k{let} result = thread.atomic(\k{fun}() incAtomic(shared))
\end{xple}

Die Funktion {\em thread.atomic} erwartet als Parameter eine
parameterlose Funktion. Diese Funktion wird durch den oben
beschriebenen Mechanismus ununterbrechbar ausgeführt. Um beliebige
Funktionen mittels {\em thread.atomic} ausführen zu können, bietet es
sich an, wie im obigen Beispiel auf Funktionen höherer
Ordnung zurückzugreifen.

Die zur Sicherstellung atomarer Abschnitte verwendete Funktion {\em
  thread.atomic} wird wie folgt implementiert:
\begin{xple}
\k{let} atomic(R $<:$\k{Ok}  action() :R) :R =
  \k{begin}
    beginCritical()
    \k{try}
      \k{let} result = action()
      endCritical()
      result
    \k{else}
      endCritical()
      \k{reraise}
    \k{end}
  \k{end}
\end{xple}
Die Funktionen {\em beginCritical} sowie {\em endCritical} beinhalten
lediglich direkte Aufrufe des Laufzeitsystems zum Inkrementieren und
Dekrementieren der Variablen {\em tmthread\_nCritical}. Die als
Argument übergebene Funktion {\em action} wird dann im Schutz dieser
Aufrufe atomar ausgewertet. Zu beachten ist darüber hinaus die
Propagierung eventuell auftretender Ausnahmebedingungen bei der
Ausführung der Funktion {\em action} durch Klammerung der
Auswertungssequenz mit {\em try} und {\em reraise}.

Die vorliegende Implementation von {\em thread.atomic} erfordert
weitere Vorkehrungen im Laufzeitsystem. Diese beinhalten unter anderem
die Aufhebung der Umschaltsperren bei zeitweiser oder endgültiger
Beendigung eines Threads, hervorgerufen durch Ausnahmebedingungen oder
expliziten Aufruf der Funktionen {\em suspend} und {\em kill}.


\subsubsection{Timeouts}
Um die Implementation von zeitabhängigen Wartefunktionen zur
Threadsteuerung zu er\-mög\-li\-chen, ist die Erweiterung des
Laufzeitsystems um einen Timeoutmechanismus erforderlich. Ein
derartiger Mechanismus wird unter anderem für die im Modul {\em
  condition} enthaltene Funktion {\em timedWait} benötigt. Die
genannte Funktionalität wird durch Programmierung einer
zeitgesteuerten Warteschlangenverwaltung auf der Ebene {\em RT} des
Laufzeitsystems ermöglicht.

Threads, die für ein gegebenes Zeitintervall verzögert werden sollen,
werden in einer speziellen Warteschlange eingetragen. Die Ordnung in
der Warteschlange ist durch Registrierung der zeitlichen Differenz zum
nächsten Warteschlangeneintrag gewährleistet. Ist beispielsweise die
Verzögerung eines Threads {\em T1} um $7.4 sec$ und die eines weiteren
Threads {\em T2} um $9.4 sec$ notwendig, so werden für diese Threads
in der Warteschlange die Zeiten $\Delta T1=7.4 sec$ und
$\Delta T2=2.0 sec$ als Zeitintervalle bis zur Aktivierung
festgehalten. Durch diese Anordnung ist für die Aktivierung lediglich
die Betrachtung des ersten Warteschlangeneintrags notwendig.  Einträge
werden bei Vorhandensein aktiver Threads in der Zeitgeberroutine zur
Koroutinenumschaltung überprüft. Im Fall des Ablaufs des
Zeitintervalls des ersten Warteschlangeneintrags wird der Thread durch
die Funktion {\em thread.run } des {\em RT} erneut gestartet.
Bei Abwesenheit aktiver Threads wird mittels eines
betriebssysteminternen, zeitabhängigen Unterbrechungsmechanismus die
exakte Wartezeit bis zur notwendigen Aktivierung des ersten
Warteschlangeneintrags programmiert. Diese Vorgehensweise ist
notwendig, um eine Portierbarkeit dieses Mechanismus zu gewährleisten,
da in vielen Betriebssystemen nur eine begrenzte Anzahl von Zeitgebern
je Betriebssystemprozeß verfügbar ist.

Die Einführung zeitabhängiger Warteschlangen führt zum Auftreten
asynchroner Vorgänge im Laufzeitsystem. Das bei Ablauf einer Wartezeit
notwendige, nebenläufige Einfügen von Threads  in den
Ring der aktiven Threads wird daher durch Sperrmechanismen während des
Zugriffs auf interne Strukturen des Laufzeitsystems synchronisiert.

Die Implementation des obigen Mechanismus erfolgt in der
Programmiersprache ANSI-C. Um die Persistenz der dabei verwendeten
Datenstrukturen zu erreichen, wird die Zeitgeberwarteschlange analog
zu dem in Abschnitt~\ref{RUNTIME} genannten Verfahren vor der
Objektspeicherstabilisierung in persistente Datenstrukturen
übertragen. Da in der oben genannten Warteschlange durch
Speicherrückgewinnung änderbare Objektidentifikatoren in flüchtigen
C-Datenstrukturen gespeichert sind, ist die Implementation einer
Enumeratorfunktion notwendig~\cite{MMS95a}.
%\comment{Veränderbare OIDs vorher schon erwähnt}


\subsubsection{Die Module zur Synchronisation}
Durch den im Abschnitt~\ref{ATOMIC} beschriebenen Mechanismus {\em
  atomic} zur Verwirklichung ununterbrechbarer Anweisungsfolgen ist es
möglich, die Synchronisationsmechanismen für Semaphore, Mutexe und
Bedingungsvariablen vollständig in der Sprache TL zu verfassen. Dadurch
besitzen alle vorgestellten Synchronisationsmechanismen automatisch die
Eigenschaft der Persistenz. Die  Implementation ist bei allen
Mechanismen  prinzipiell ähnlich aufgebaut. 
Ein Element des Typs {\em sync.T}, wobei hier {\em sync} als Synonym
für alle angesprochenen Mechanismen steht, ist als TL-Tupel der Form
\begin{xple}
 \k{Let} T $<:$\k{Ok} = \k{Tuple}
\begin{tabular}{lll}
    \ldots & & (* Zähler für Statistiken *) \\
    \ldots & & (* Semaphorzähler *) \\
    \k{var} owner & :thread.T(\k{Ok}) & (* 'Halter' des Elements *) \\
    waitqueue & :queue.T(thread.T(\k{Ok})) & (* Liste der wartenden Threads *)
  \end{tabular}
  \k{end}
\end{xple}
aufgebaut. Für jedes Element des Typs {\em sync.T} wird im Falle der
Akquisition der Halter der Synchronisationsvariable in der
veränderlichen Variable {\em owner} festgehalten. Diese Variable wird
derzeit bei Freigabeoperationen nur für Synchronisationsvariablen des
Typs {\em mutex.T} ausgewertet, um die Berechtigung für diese
Operation festzustellen. In der Variablen {\em waitqueue} ist die
Liste aller auf die Synchronisationsvariable wartenden Threads
festgehalten. Alle Modifikationen, die an einem Element des Typs {\em
  sync.T} vorgenommen werden, sind durch die Operation {\em thread.atomic}
geschützt und werden atomar durchgeführt. Als Beispiele sei hier der
prinzipielle Ablauf der Operationen des Wartens und Freigebens eines
Semaphors angeführt. Die Funktionen {\em semaphore.wait} sowie {\em
  semaphore.post} können unter dem Schutz der Operation {\em
  thread.atomic} wie folgt implementiert werden: 
\vskip 0.5cm
\begin{minipage}[t]{2.5in}
\begin{xple}
(* Warten auf ein Semaphor *)
\k{let} wait(sem :T) =  
 \k{begin}
   \k{let} self = thread.self()
   thread.atomic(\k{fun}() \k{begin}
     $sem.count := sem.count - 1$
     \k{if} $sem.count < 0$ \k{then}
         queue.push(sem.waitqueue  self)
         thread.suspend(self)
     \k{end}
   \k{end})
 \k{end}
\end{xple}
\end{minipage}
\begin{minipage}[t]{3.0in}
\begin{xple}
(* Freigabe eines Semaphors *)
\k{let} post(sem :T) :\k{Ok} =
   \k{begin}
     thread.atomic(\k{fun}() \k{begin}
       $sem.count := sem.count + 1$
       \k{if} sem.count $\leq 0$ \k{then}
            thread.run(queue.pop(sem.waitqueue))
       \k{end}
     \k{end})
   \k{end} 
\end{xple}
\end{minipage}
\vskip 0.5cm

Die in der Funktion {\em wait} erforderliche Freigabe der durch {\em
  thread.atomic} erzwungenen Umschaltsperre für Koroutinen ist durch
die Implementation der Funktion {\em thread.suspend} sichergestellt
(Abschnitt~\ref{ATOMIC}). Es ist zu beachten, daß der in der Funktion
{\em post} vorhandene Aufruf {\em thread.run}  zu einem
Aufbau der für das Laufzeitsystem erforderlichen, flüchtigen
Datenstruktur sowie des zu aktivierenden Threads führt. Weiterhin wird
der zu startende Thread in die Ringstruktur der aktiven Threads
eingefügt. Die Aktivierung des Threads findet nach Beendigung der
durch {\em thread.atomic} bedingten Umschaltsperre im Rahmen der
normalen Rechenzeitzuteilung statt.




\subsection{Tycoon-Threads und Standards}
\label{RELATED}
%Zu Begin dieser Arbeit werden neben der Betrachtung grundsätzlicher
%Synchronisationsmechanismen bereits vorhandener Standards für die
%Programmierung nebenläufiger Aktivitäten untersucht.  
Für die Programmierung nebenläufiger Aktivitäten existieren eine Reihe
weitverbreiteter Programmierschnittstellen. Die für das Tycoon-System
implementierten Synchronisationsmechanismen wurden auch in Hinblick
auf derartige Standards entworfen. Im folgenden wird die Einordnung
der Funktionen zur Threadsteuerung und Synchronisation in diese
Standards beschrieben.
 
Als Ausgangspunkt werden die für das Unix-Betriebssystem Solaris
spezifizierte Threadbibliothek~\cite{Sun93} sowie die Spezifikation
nach Posix für eine standardisierte Multithreadschnittstelle
herangezogen~\cite{POSIX}.  Der Standard nach Posix deckt die
folgenden Punkte zur Programmierung von Threads ab:
\begin{description}
\item [Threadeigenschaften:] Hierunter fällt eine Reihe von Funktionen
  zum Setzen und Abfragen threadspezifischer Parameter wie Stackgröße
  und Prioritätssteuerung. Weiterhin sind  Methoden des
  Threadschedulings wie Zeitscheibensteuerung und präemptives
  Scheduling einstellbar.
\item[Threadsteuerung:] \sloppy{Hierunter fallen Funktionen zur Erzeugung und
  Beseitigung von Threads, Funktionen zur Kontrollübermittlung wie
  {\em join} und {\em exit} sowie Aufrufe zum Vergleich von Threads.}

\item[Eigenschaften der Synchronisationsmechanismen:] Mit den
  Funktionen dieser Gruppe sind Prioritätsparameter (Übernahme der
  Prioritätsparameter der die Synchronisationsmechanismen benutzenden
  Threads) und die Speicherabbildung von Synchronisationsmechanismen
  (zum Prozeß lokaler Speicher oder von mehreren Prozessen gemeinsam
  benutzter Speicher) steuerbar.
\item[Benutzung der Synchronisationsmechanismen:] \sloppy{In dieser Gruppe
  sind Funktionen zum Zugriff auf Synchronisationsmechanismen wie
  Mutexe und Bedingungsvariablen spezifiziert.}
\end{description}
%\comment{Scheduling == Rechenzeitzuteilung ??}
Der verabschiedete Posix-Standard beinhaltet eine minimale, aber
vollständige Menge von Syn\-chronisations- und
Threadsteuerungsmechanismen. Als Mechanismen zur Synchronisation von
Threads sind lediglich Mutexe und Bedingungsvariablen spezifiziert. Die
Mechanismen zur Threadsteuerung bilden die in vielen Betriebssystemen
vorhandenen Steuerungsmechanismen für die Rechenzeiteinteilung von
Threads und Systemprozessen ab. Ein Beispiel hierfür ist die
Möglichkeit, Prozesse und Threads als Echtzeitprozesse mit garantiertem
Rechenzeitkontingent und berechenbaren Antwortzeiten bei der Reaktion
auf Ereignisse  ablaufen zu lassen~\cite{Deit90}.


Die für die genannten Unix-\-Betriebs\-systeme spezifizierten
Mechanismen sind eng an den Posixstandard angelehnt. Darüber
hinaus werden zusätzliche Synchronisationsmechanismen wie Semaphore
und Leser- und Schreibersperren angeboten. 

Grundsätzlich muß für eine Implementation von Funktionen des genannten
Standards bereits eine Entsprechung von Funktionalitäten im Zielsystem
vorhanden sein.  Die in dieser Arbeit realisierten
Synchronisationsmechanismen stellen zusammen mit den vorhandenen
Aufrufen zur Threadsteuerung eine im Rahmen des Tycoonsystems sinnvolle
Untermenge des Posixstandards dar.  Nicht vom Posixstandard
übernommene Funktionalitäten wie Prioritätssteuerung und
Interprozeßkommunikation sind im Tycoon-System nicht vorhanden. Eine
Übersicht über äquivalente Funktionen des Posixstandards
Posix.1c/D10~\cite{POSIX} und den Tycoonmodulen {\em thread}, {\em
  mutex} und {\em condition} gibt die folgende Tabelle:
\newpage
\begin{tabular}{|l|l|p{2.5in}|} \hline
\multicolumn{1}{|c|}{Posix-Threads} & 
\multicolumn{1}{c|}{Tycoon-Threads} & 
\multicolumn{1}{c|}{Bemerkungen} \\ \hline\hline
\multicolumn{3}{|c|}{Funktionen zur Threadsteuerung} \\ \hline
pthread\_create & thread.fork & auch thread.new \\
pthread\_self & thread.self &  \\ 
pthread\_equal & pid1 == pid2 & Vergleich mittels
Ver\-gleichs\-funktionen der Sprache TL bei Threads mit gleicher Signatur \\
pthread\_exit & thread.kill & \\
pthread\_join & thread.join & \\ \hline
\multicolumn{3}{|c|}{Funktionen zur Mutexsteuerung} \\ \hline
pthread\_mutex\_init & mutex.new & \\
pthread\_mutex\_destroy & \multicolumn{1}{|c|}{--} & 
nicht notwendig\footnotemark  \\
pthread\_mutex\_lock & mutex.lock & \\
pthread\_mutex\_trylock & mutex.tryLock & \\ \hline
\multicolumn{3}{|c|}{Funktionen für Bedingungsvariablen} \\ \hline
pthread\_cond\_init & condition.new & \\
pthread\_cond\_destroy & \multicolumn{1}{|c|}{--} & 
nicht notwendig\footnotemark[2] \\
pthread\_cond\_signal & condition.signal & \\
pthread\_cond\_broadcast & condition.broadcast & \\
pthread\_cond\_wait & condition.wait & \\
pthread\_cond\_timedwait & condition.timedWait & \\ \hline
\end{tabular}

\footnotetext{Nicht mehr
referenzierbare Objekte werden durch Speicherrückgewinnung entfernt.}


\include{Konzepte} 


% Local Variables:
% TeX-master: "da"
% TeX-parse-self: t
% TeX-auto-save: t
% End:
% LocalWords:  bez WaitEntryT nil Posts setSyncs Objektid queue runningState
% LocalWords:  run multithreaded
