\chapter{Synchronisation nebenläufiger Prozesse}
\label{SYNC}
Zunächst wird im folgenden Abschnitt eine Übersicht über die
verschiedenen Ziele der nebenläufigen Ausführung von Programmen
gegeben. Die dieser Arbeit zugrundeliegende Art der Nebenläufigkeit,
die der kooperativen Nebenläufigkeit, erfordert die Bereitstellung von
Mechanismen, die einen sicheren Zugriff auf Systemressourcen
gewährleisten.  Dieser Zugriff auf Systemressourcen, unter denen hier
sowohl physikalische Geräte wie auch Programmobjekte zu verstehen
sind, muß in geeigneter Weise synchronisiert werden.

Da Beschreibung und Analyse nebenläufiger Vorgänge seit mehreren
Jahrzehnten Bestandteil verschiedener Teildisziplinen der Informatik
sind, steht eine große Auswahl von Methoden zur Synchronisation zur
Verfügung. Eine Beschreibung und Analyse der wesentlichen Methoden
befindet sich in Abschnitt~\ref{SYNCHMECH}. Ein Überblick über die in
verschiedenen persistenten Programmiersystemen eingesetzten
Synchronisationsmethoden gibt Abschnitt~\ref{SyncPers}.


\section{Nebenläufigkeit in Rechensystemen}
Nebenläufigkeit in Rechensystemen kann ein ganzes Spektrum von
Modellen umfassen (Abbildung~\ref{isocoop}). An einem Ende dieses
Spektrums findet man die transaktionale Sichtweise, in der einzelne
Prozesse weitestgehend voneinander abgeschirmt sind. 
%Diese Art der Nebenläufigkeit findet sich in den klassischen
%Datenbanksystemen, in denen die Auswirkungen von Nebenläufigkeit beim
%Zugriff auf Datenbestände vom System verborgen werden.
Diese Art der Nebenläufigkeit findet sich in den klassischen
Datenbanksystemen, in denen die Auswirkungen von Nebenläufigkeit beim
Zugriff auf Datenbestände vom System verborgen werden.
%% vorigen Satz ändern
Die dem Programmierer zur Absicherung eines nebenläufigen Zugriffs zur
Verfügung stehenden Sprachmittel beschränken sich auf das explizite
Sperren von Datenbeständen zum Zweck der Bearbeitung sowie auf die
Formulierung von Transaktionen, bei denen die notwendige
Serialisierung von konkurrierenden Datenzugriffen vollständig in der
Verantwortung des Datenbanksystems liegt. Weiterhin besteht die
Möglichkeit der Rücknahme von Transaktionen, um im Fehlerfall einen
zurückliegenden, konsistenten Systemzustand erreichen zu können.  Ein
solches transaktionales System wird durch die ACID Eigenschaften der
Atomarität, Konsistenz, Isolation und Dauerhaftigkeit
spezifiziert~\cite{GrRe93}.  Zusammenfassend muß ein transaktionales
System über die folgenden Mechanismen verfügen:
\begin{itemize}
\item Mechanismen, die die Isolation von Prozessen voneinander
  sicherstellen. Dazu gehören das Sperren von Datenbeständen, die
  automatische Serialisierung von Datenzugriffen sowie Methoden des
  optimistischen konkurrierenden Zugriffs auf Datenbestände.
\item Mechanismen, die die Atomarität der Transaktionen sicherstellen.
  Hierunter ist die automatische Rücknahme der durch fehlerhafte oder
  abgebrochene Prozesse verursachten Änderungen zu verstehen. Die
  Auswirkungen einer Transaktion können von anderen Prozessen nur bei
  erfolgreichem Anschluß dieser Transaktion festgestellt werden.
\item Mechanismen, die die Persistenz der durchgeführten Änderungen
  sicherstellen. Fehlerhafte Sy\-stem\-zu\-stän\-de führen lediglich
  zu einer Rücknahme von Modifikationen noch nicht abgeschlossener
  Transaktionen.
\end{itemize}
\begin{figure}
\begin{center}\leavevmode
  \epsfxsize=0.8\textwidth \epsfbox{pictures/atomic-coop.eps}
\end{center}
\caption{Isolation vs. Kooperation}
\label{isocoop}
\end{figure}
Die auf der rechten Seite von Abbildung~\ref{isocoop} zu findenden
Systeme stellen die Synchronisation von Zugriffen auf gemeinsam
benutzte Datenbestände in die alleinige Verantwortung des
Programmierers. Zu kooperativen Systemen gehören insbesondere
Programmiersprachen, die die Formulierung nebenläufiger Aktivitäten
innerhalb eines Programms gestatten. Um die innerhalb eines Programms
definierten, nebenläufigen Aktivitäten von den Betriebssystemprozessen
abzugrenzen, wird im allgemeinen der Begriff {\em Thread} verwendet.
Threads besitzen, da sie voneinander verschiedene, nebenläufige
Ausführungpfade desselben Programms darstellen, einen vollständigen
Zugriff auf alle vorhandenen Programmobjekte. Im Unterschied zu
transaktionalen Systemen steht hier die Kooperation dieser Aktivitäten
im Vordergrund.  Verschiedene Threads arbeiten gemeinsam an einem
vorliegenden Problem und kommunizieren miteinander. Zur Abstimmung der
bei dieser Kooperation und Kommunikation entstehenden Konflikte beim
Zugriff auf gemeinsam zu nutzende Programmobjekte stehen in allen
solchen Systemen verschiedene Synchronisationsmechanismen zur
Verfügung.

Bezüglich der transaktionalen Eigenschaften des Tycoon-Systems sind
folgende Besonderheiten zu beachten~\cite{Korn95}:

\begin{itemize}
\item Das Tycoon-System ist ein Einbenutzersystem. Es existiert keine
  Multiprozeßeigenschaft des Systems. In einem gegebenen
  Tycoon-System wird ein Programm immer auch nur durch einen
  Betriebssystemprozeß ausgeführt.
\item Programme können durch mehrere Threads ausgeführt werden. Diese
  besitzen einen vollständigen Zugriff auf alle Programmobjekte. Eine
  durch einen Thread durchgeführte Transaktion beeinflußt alle
  weiteren vorhandenen Threads.
%\comment{Noch genauer erklären}
\item Transaktionen können durch persistente Sicherungspunkte weiter
  strukturiert werden. Im Verlauf einer Transaktion können beliebig
  viele Sicherungspunkte gesetzt werden, zu denen das System später
  zurückkehren kann. Das Ende einer Transaktion bewirkt auch die
  Aufhebung dieser Sicherungspunkte.
\end{itemize}

Eine Differenzierung von Prozessen und Threads wird in den folgenden
Abschnitten fallengelassen, da für die Betrachtung von
Synchronisationsproblemen lediglich der Sachverhalt des gemeinsamen
Zugriffs auf einzelne Ressourcen relevant ist. Welche Granularität die
daran beteiligten, aktiven Objekte haben, steht dabei im Hintergrund.



\section{Synchronisationsmechanismen}
\label{SYNCHMECH}
Ziel dieses Abschnitts ist die Vorstellung bekannter Verfahren zur
Synchronisation von Prozessen. Aus den vorgestellten Verfahren wird im
folgenden Kapitel eine Auswahl von für persistente Objektsysteme
geeigneten Verfahren getroffen.

Bei näherer Betrachtung der verfügbaren Literatur zum Thema
Synchronisation zeigt es sich, daß die Verfahren zweckmäßigerweise in
aufeinander aufbauende Gruppen unterteilt werden können. Einen ersten
Überblick über den hierarchischen Aufbau von Synchronisationsmethoden
für Systeme mit gemeinsamen Speicher gibt
Abbildung~\ref{sync-classic}.
\begin{figure}
  \begin{center}\leavevmode
    \epsfxsize=0.5\textwidth \epsfbox{pictures/sync-classic.eps}
  \end{center}
  \caption{Hierarchie der Synchronisationsmethoden}
  \label{sync-classic}
\end{figure}

\section{Basismethoden}
\label{BASIC}
Die in diesem Abschnitt vorgestellten Verfahren basieren auf
speziellen Eigenschaften der Rechnersysteme. Im einzelnen sind dieses
Verfahren, die
\begin{itemize}
\item auf bestimmten Eigenschaften des verwendeten Speichersystems
  aufbauen,
\item eine bestimmte Konfiguration des verwendeten Rechnersystems
  voraussetzen und
\item spezielle Fähigkeiten des verwendeten Prozessors oder
  zusätzlichen Schaltungsaufwand erfordern.
\end{itemize}


\subsection{Ununterbrechbarer Speicherzugriff}
\label{Speicherzugriff}
Eine grundlegende Voraussetzung für die Synchronisation von Prozessen
ist die Verfügbarkeit eines ununterbrechbaren Zugriffs auf
Speicherzellen des Rechnersystems während Schreib- und
Leseoperationen.  Dieses Verhalten wird durch den Aufbau des
Speichersystems sichergestellt~\cite{Lag87}.
%Abgesehen von
%spezialisierten Speicherbausteinen stellen praktisch alle heute
%verfügbaren Speicherarchitekturen und Zugriffsmethoden auf den
%Rechnerspeicher sicher, daß eine einzelne Speicherzelle nicht
%gleichzeitig modifiziert und gelesen werden kann~\cite{Lag87}.
Die Ununterbrechbarkeit eines Speicherzugriffs ermöglicht bereits die
Bereitstellung von Algorithmen, die den gegenseitigen Ausschluß von
konkurrierenden Prozessen beim Zugriff auf gemeinsam zu nutzende Daten
gewährleisten. Bis zu den Arbeiten von Dekker und Dijkstra nahm man
an, daß dieses Problem nicht durch einfachen Speicherausschluß zu
lösen ist~\cite{Dijk68}. Der Algorithmus von Dekker ist hier wegen
seiner Bedeutung noch einmal in  einer vereinfachten Form nach
Peterson~\cite[Seite 134--135]{JV87} in der Programmiersprache TL angegeben.

\begin{xple}
\k{let} \k{var} c1 = 0 \k{and} \k{var} c2 = 0 \k{and} \k{var} turn = 1

\k{let} funcA(self :thread.T(\k{Ok})) = 
  \k{begin}
    (* Eingangsprotokoll *)
    c1 := 1
    turn := 2
    \k{while} \{c2 == 1\} \k{and} \{turn == 2\} \k{do} \k{end}
    (* kritischer Abschnitt *)
    c1 := 0
  \k{end}

\k{let} funcB((self :thread.T(\k{Ok})) = 
  \k{begin}
    (* Eingangsprotokoll *)
    c2 := 1
    turn := 1
    \k{while} \{c1 == 1\} \k{and} \{turn == 1\} \k{do} \k{end}
    (* kritischer Abschnitt *)
    c2 := 0
  \k{end}

(* Erzeugung der Threads *)
\k{let} tA = thread.fork(funcA)  \k{and}  tB = thread.fork(funcB)
\end{xple}

Jeder Thread, der versucht in den kritischen Abschnitt zu gelangen muß
zunächst das Eingangsprotokoll durchlaufen: Die Variable {\em c1} wird
auf $1$ gesetzt, wenn der Thread {\em tA} in den kritischen Abschnitt
eintreten möchte; ebenso wird {\em c2} auf $1$ gesetzt, wenn Thread
{\em tB} in den kritischen Abschnitt eintreten möchte. Die Variable
{\em turn} dient der Verhinderung von Verklemmungen, in ihr wird der
nächste Thread vermerkt, der in den kritischen Abschnitt eintreten
darf. Versuchen beide Threads gleichzeitig das Eingangsprotokoll
auszuführen, so ermöglicht derjenige Thread, der die Variable {\em
  turn} als letztes ändert, dem jeweils anderen Thread den Eintritt in
den kritischen Abschnitt.

Eine Analyse der Methode von Dekker~\cite{JV87} zeigt jedoch, daß der von
ihm entwickelte Algorithmus verschiedene, gravierende Nachteile
aufweist:
\begin{itemize}
\item Alle Prozesse, die an dem zu lösenden Ausschlußproblem beteiligt
  sind, müssen von vornherein bekannt sein.
  
\item Der Algorithmus benutzt die Technik des aktiven Wartens, das
  heißt, ein Prozeß verbraucht auch im Wartezustand Rechenzeit.
  
\item Der Algorithmus ist relativ kompliziert und die Rechenzeit des
  Algorithmus steigt bei der Beteiligung von mehr als zwei Prozessen
  stark an.
\end{itemize}
Trotz dieser Nachteile erbringt der Algorithmus von Dekker den
Nachweis, daß der gegenseitige Speicherausschluß, der durch den Aufbau
des Speichersystems gegeben ist, die Lösung von
Synchronisationsproblemen zuläßt.

\subsection{Unterbrechungssperren}
Eine einfache Möglichkeit zur Synchronisation stellt das Verbot von
Unterbrechungen laufender Prozesse dar. Unterbrechungen werden in
Rechnersystemen auf vielfältige Art benutzt. Beispiele hierfür sind
Ein- und Ausgabeanforderungen durch externe Geräte oder zyklische
Unterbrechungen durch externe Zeitgeber. Typischerweise werden in
Betriebssystemen, die die nebenläufige Abarbeitung von Programmen
erlauben, Prozeßumschaltungen als Folge abgelaufener
Rechenzeitkontingente durchgeführt. Kritische Abschnitte 
%\comment{muß noch definiert werden } 
können dann dadurch realisiert werden, daß
für die Dauer eines solchen Abschnitts jede Unterbrechung untersagt
wird. Diese Methode weist jedoch eine Reihe von Problemen auf:
\begin{itemize}
\item Sperren für Unterbrechungsanforderungen werden für kritische
  Abschnitte im Betriebssystem selbst benötigt und sind im allgemeinen
  auch nur durch privilegierte Maschineninstruktionen realisierbar,
  die auf der Ebene von Benutzerprozessen nicht zugelassen sind.
\item Die gesamte Funktionsweise des Systems kann durch lang
  andauernde oder nicht wieder aufgehobene Sperren von
  Unterbrechungsanforderungen negativ beeinflußt werden.
\item Unterbrechungssperren sind für Mehrprozessorsysteme nicht ohne
  weiteres realisierbar.
\end{itemize}
%%Lehmanns Kommentar: Es fehlt eine Aussage darüber, wer oder was
%%gesperrt wird.

\subsection{Atomare Prozessorinstruktionen}
Wie in Abschnitt~\ref{Speicherzugriff}  besprochen, bietet der
ununterbrechbare Speicherzugriff bereits die Möglichkeit,
Synchronisationsprobleme zu behandeln. Um die programmiertechnische
Behandlung von Synchronisationsproblemen zu vereinfachen, bieten viele
Rechnerprozessoren spezielle Instruktionen zur Synchronisation an.
Diese  zeichnen sich im wesentlichen durch drei
Eigenschaften gegenüber anderen Prozessorbefehlen aus:
\begin{itemize}
\item Es handelt sich um sogenannte
  Read-Modify-Write-Instruktionen~\cite{Nau84}. Dies bedeutet, daß die
  Instruktionen den adressierten Speicherbereich lesen, den gelesenen
  Wert modifizieren und den modifizierten Wert zurück in den
  adressierten Speicherbereich übertragen.
\item Die Abarbeitung einer solchen Instruktion, also die Modifikation
  der angesprochenen Speicherzelle, ist nicht
  unterbrechbar. Unterbrechungsanforderungen werden bis zum Ende der
  Abarbeitung verzögert.
\item Auch Zugriffe durch diese Instruktionen auf den gemeinsamen
  Speicher in Multiprozessorumgebungen sich nicht unterbrechbar.
\end{itemize}

{\sloppy Beispiele für solche Befehle stellen die Befehle {\em TEST-AND-SET}, 
{\em EXCHANGE}\ und {\em COMPARE-AND-SWAP} dar. Die Wirkung dieser Befehle
wird im folgenden besprochen.

}


\subparagraph{TEST-AND-SET:}
\label{TAS}
Dieser Befehl entspricht in seiner Wirkung dem Auslesen einer
Speicherzelle und dem Setzen eines prozessorinternen Zustandsbits in
Abhängigkeit des Werts der Speicherzelle. Anschließend wird der Wert
der angesprochenen Speicherzelle auf einen definierten Wert gesetzt.
Dieser Wert kann bei einigen Prozessoren als Befehlsoperand übergeben
werden. TEST-AND-SET ist als Befehl {\em TAS} zum Beispiel auf Motorola
680xx/880xx-Prozessoren~\cite{Nau84} implementiert.  Das folgende
Programmfragment verdeutlicht die Wirkung des Befehls {\em TAS}:
\begin{xple}
\k{let} testAndSet(\k{var} value :Bool) :Bool =
  \k{begin}
     \k{let} local = value
     value := true
     local
  \k{end}
\end{xple}

Eine Anwendung dieses Befehls zur Realisierung des gegenseitigen
Ausschlusses kann dann wie folgt realisiert werden:

\begin{minipage}[t]{3in}
\begin{xple}
\k{let} \k{var} busy = false

\k{let} funcA() = 
  \k{begin}
    \k{while} testAndSet(busy)  \k{do} \k{end}
    (* kritischer Abschnitt A *)
    busy := false
  \k{end}
\end{xple}
\end{minipage}
\begin{minipage}[t]{3in}
\begin{xple}


\k{let} funcB() = 
  \k{begin}
    \k{while} testAndSet(busy)  \k{do} \k{end}
    (* kritischer Abschnitt B *)
    busy := false
  \k{end}
\end{xple}
\end{minipage}

Es ist anzumerken, daß der Einsatz von TEST-AND-SET Operationen zu
einem unfairen Verhalten bezüglich der Möglichkeit des Eintritts
beteiligter Prozesse in kritische Abschnitte führen kann.  Faires
Verhalten liegt dann vor, wenn garaniert ist, daß ein Ereignis, das
stattfinden kann auch stattfindet.  Hierbei wird jedoch keine Aussage
darüber getroffen, wann dies der Fall ist (vgl.~\cite{JV87}). Im
vorigen Beispiel besteht dagegen die Möglichkeit, daß ein Prozeß nie
in den kritischen Abschnitt eintreten kann, wenn andere Prozesse
ständig früher die Bedingung für den Eintritt vorfinden ({\em busy ==
  false}).

\subparagraph{EXCHANGE:}
\label{EXCHANGE}
Dieser Befehl stellt eine Verallgemeinerung der
TEST-AND-SET Instruk\-tion dar. Die Inhalte zweier Speicherzellen werden
atomar ausgetauscht:
\begin{xple}
\k{let} exchange(\k{var} x :Int  \k{var} y :Int) =
  \k{begin}
    \k{let} \k{var} temp = x
    x := y
    y := temp
  \k{end}
\end{xple}

Kritische Abschnitte können dann wie folgt implementiert werden:
\begin{xple}
\k{let} \k{var} busy = 1

\k{let} funcA() =
  \k{begin}
    \k{let} \k{var} localA = 0
    \k{loop}
      exchange(busy localA)
      \k{if} localA == 1 \k{then} \k{exit} 
    \k{end}
    (* kritischer Abschnitt *)
    exchange(busy localA)
  \k{end}

\k{let} funcB() =
  \k{begin}
    \k{let} \k{var} localB = 0
    \k{loop}
      exchange(busy localB)
      \k{if} localB == 1 \k{then} \k{exit} 
    \k{end}
    (* kritischer Abschnitt *)
    exchange(busy localB)
  \k{end}
\end{xple}

EXCHANGE ist für Intel-x86-Prozessoren als Befehl {\em XCHG}
implementiert~\cite{Sybex87}. Für Sparc-Prozessoren ist die
EXCHANGE-Instruktion als Befehl {\em SWAP} neben einer ganzen Reihe
anderer atomarer Instruktionen wie {\em LDSTUB, LDSTUBA} und {\em
  SWAPA} implementiert~\cite{Cat91}.\footnote{Bei den genannten
  Befehlen wird der Inhalt eines Prozessorregisters mit dem Inhalt
  einer Speicherzelle vertauscht.}


\subparagraph{COMPARE-AND-SWAP:}
\label{COMPARE-AND-SWAP}
Eine weitere, unteilbare Maschineninstruktion stellt COM\-PARE-AND-SWAP
dar. Im Unterschied zur einfachen EXCHANGE-Anweisung ist bei dieser
Anweisung ein Austausch der adressierten Speicherzellen abhängig von
deren Inhalt. Folgendes Beispiel verdeutlicht die Wirkung von
COMPARE-AND-SWAP~\cite{GrRe93}:
\begin{xple}
\k{let} compareAndSwap(\k{var} cell, old, new :word.T) :Bool =
  \k{begin}
    \k{if} cell == old \k{then}
      cell := new
      true
    \k{else}
      old := cell
      false
    \k{end}
  \k{end}
\end{xple}

Die COMPARE-AND-SWAP-Anweisung bietet im Gegensatz zu den bisher
besprochenen Instruktionen die Möglichkeit, kritische Operationen auf
Maschinenworten zu programmieren, ohne auf zusätzliche Hilfsvariablen
für die Synchronisation des kritischen Abschnitts zurückgreifen zu
müssen.  
%\comment{Beispiel von Queueops. mit CS ??}
%% Lehmann: Voriger Satz trivial ??

\subparagraph{Weitere maschinennahe Instruktionen:} Neben den bisher
besprochenen, atomaren Instruktionen bieten verschiedene Prozessoren
eine noch weitergehende Unterstützung zur Lösung von
Synchronisationsproblemen an. Beispiele hierfür sind atomare
Additionsbefehle und Befehle zur direkten Manipulation von
Warteschlangen auf VAX/11 Maschinen (ADAWI und
INSQHI/REMQHI)~\cite{Dec80}.
% und die Implementation von
%Semaphoroperationen auf IBM 360/370 Maschinen~\cite{Ibm79}.

Einen allgemeineren Mechanismus zur Nachbildung verschiedener, atomarer
Instruktionen beschreibt Moore für den Mikroprozessor
PPC601~\cite{Mo93}. Durch die Maschineninstruktion LOAD-AND-RESERVE
wird eine Speicherzelle gelesen und als reserviert gekennzeichnet.
Eine Schreiboperation auf diese Speicherzelle wird in internen
Prozessorregistern vermerkt. Die atomare Operation STORE-CONDITIONAL
wertet den Inhalt dieser Register aus und führt eine Schreiboperation
nur dann durch, wenn der angesprochene Wert zwischenzeitlich nicht
geändert wurde. Bei erfolgreicher Schreiboperation wird die
Reservierung der Speicherstelle zurückgenommen. Diese Instruktion kann
mit zusätzlichen Verzweigungsoperationen kombiniert werden, um
Sequenzen von Operationen zu programmieren, die die oben
beschriebenen, atomaren Anweisungen nachbilden.

\subsection{Zusammenfassung}
Zur Lösung von Synchronisationsproblemen bietet sich eine ganze Reihe
von Möglichkeiten auf niedrigem Abstraktionsniveau an. Dekkers
Algorithmus erbringt den Nachweis, daß bereits die Eigenschaft des
nichtunterbrechbaren Schreib- und Lesezugriffs auf den Hauptspeicher
des Rechnersystems zur Synchronisation von nebenläufigen Prozessen
ausreichend ist. Diese Lösung eignet sich sowohl für
Einprozessorrechner wie auch für
Multiprozessormaschinen~\cite{Dijk71}. Eine spezielle Lösung für
Einprozessorsysteme stellt das Verbot von Unterbrechungen dar, das
jedoch abhängig vom zur Verfügung stehenden Betriebsystem nicht immer
realisierbar ist.  Wie aus dem folgenden Abschnitt ersichtlich wird,
eignen sich die angesprochenen Maschineninstruktionen für die
Implementation von Synchronisationsmethoden auf höherer Ebene. Ihr
direkter Einsatz für Synchronisationsprobleme ist jedoch mit einer
Reihe von Nachteilen verbunden. Zum einen kann durch das aktive Warten
Rechenzeit gebunden werden, zum anderen besteht die Möglichkeit, daß
ein Prozeß nie in einen kritischen Abschnitt eintreten kann: Andere
Prozesse können ständig vor diesem Prozeß die erfüllte Bedingung für
einen Eintritt in den kritischen Abschnitt vorfinden. Die einzelnen
Instruktionen sind darüber hinaus abhängig von der verwendeten
Prozessortechnik.

%Ihr direkter Einsatz für Synchronisationsprobleme ist jedoch mit den
%Nachteilen des aktiven Wartens und der Gefahr der unfairen Behandlung
%einzelner Prozesse verbunden. Die einzelnen Instruktionen sind darüber
%hinaus abhängig von der verwendeten Prozessortechnik.
% Je
%nach Mächtigkeit dieser Befehle ist jedoch ihr direkter Einsatz für
%Synchronisationsprobleme mit den Nachteilen des aktiven Wartens und
%der Gefahr der unfairen Behandlung einzelner Prozesse verbunden. Die
%einzelnen Instruktionen sind darüber hinaus abhängig von der
%verwendeten Prozessortechnik.

\section{Erweiterte Methoden}
\label{ERWEITERT}
Die Nachteile der bereits angesprochenen, maschinennahen
Synchronisationsanweisungen führen zur Entwicklung weiterer
Synchronisationsmechanismen. Die im folgenden besprochenen Mechanismen
sind weiterhin auf einem eher niedersprachlichen Niveau angesiedelt,
abstrahieren aber schon von den direkten, maschinenabhängigen, atomaren
Instruktionen. Nach der nahezu direkten Umsetzung atomarer
Maschinenbefehle in erweiterte Konstrukte werden Verfahren entwickelt,
die den Nachteil des aktiven Wartens auf Ereignisse vermeiden. Dies
wird in den meisten der nachfolgend beschriebenen Verfahren durch eine
Kombination von maschinennahen Befehlen sowie der Benutzung von
Warteoperationen des eigentlichen Betriebssystems erreicht.
Maschinennahe Befehle werden bei diesen Verfahren nur noch zum Schutz
von kritischen Abschnitten im Betriebssystem selbst verwendet, ihre
Anwendung bleibt den Benutzerprozessen verborgen.

\subsection{LOCK und UNLOCK}
Eines der ersten Synchronisationsverfahren, das allerdings noch den
Nachteil des aktiven Wartens aufweist, stellte Denning 1971
vor~\cite{Den71}. Bei diesem Verfahren werden den kritischen
Abschnitten sogenannte Sperrbits zugeordnet, die durch die atomaren
Instruktionen LOCK und UNLOCK gesetzt bzw. zurückgesetzt werden.
Möchte ein Prozeß in einen kritischen Abschnitt eintreten, wird dies
durch die Operation LOCK angemeldet. Ist der Abschnitt bereits durch
einen anderen Prozeß gesperrt, muß der Prozeß aktiv auf die Freigabe
des Abschnitts durch die Operation UNLOCK warten.  Diese Operationen
können unmittelbar durch einen atomaren Maschinenbefehl wie zum
Beispiel TEST-AND-SET implementiert werden.
\begin{xple}
(* Ein freies Lockbit ist mit false zu initialisieren *)
\k{let} lock(\k{var} l :Bool) = 
  \k{begin}
    \k{while} testAndSet(l) \k{do} \k{end}
  \k{end}

\k{let} unlock(\k{var} l :Bool) = 
  \k{begin}
    l := false
  \k{end}
\end{xple}

\subsection{Semaphore}
\label{Semaphore}
Einen wesentlichen Fortschritt in der Entwicklung von Methoden zur
Synchronisation erzielte Dijkstra mit der Einführung des Konzepts der
Semaphore im Jahr 1965~\cite{Dijk68}. In diesem Artikel wird ein
Verfahren für die kooperative Zusammenarbeit von Prozessen
dargestellt.  Zwei oder mehrere Prozesse kommunizieren hierbei über
den Austausch von Signalen so, daß die Prozesse sich gegenseitig über
die Möglichkeit der Fortführung einer Aktivität informieren. Dieser
Signalaustausch erfolgt mittels spezieller Variablen, über
Semaphore.

Ein Semaphor entspricht dabei einer ganzzahligen Variablen {\em sem}, auf
der zwei atomare Operationen {\em P} und {\em V} definiert sind. 
%In Dijkstras Artikel von 1968 angegebenen Operationen benutzen die
%Notation // Anweisung //, um die Atomarität einer Anweisungsfolge zu
%beschreiben:
In Dijkstras Artikel von 1968 werden diese Operationen wie folgt
definiert~\cite[Seite 67--68]{Dijk68}:
\begin{quote}
  ``The V-Operation is an operation with one argument, which must be
  the identifikation of a semaphore. Its function is to increase the
  value of its argument by $1$; this increase is to be regarded as an
  indivisible operation.''
  
  `` The P-Operation is an operation with one argument, which must be
  the identifikation of a semaphore. Its function is to decrease the
  value of its argument by $1$ as soon as the resulting value would be
  non-negative. The completion of the P-operation---i.e.\ the decision
  that this is the appropriate moment to effectuate the decrease and
  the subsequent decrease itself---is to be regarded as an indivisible
  operation.''
\end{quote}
%\begin{quote}
%{\em P(sem)}: // as soon as $sem - 1 \geq 0$ then $sem := sem - 1$ //

%{\em V(sem)}: // $sem := sem + 1$ //
%\end{quote}
Trifft die Bedingung $sem > 0$ während einer P-Operation nicht zu, so
muß der ausführende Prozeß so lange warten, bis diese Bedingung erfüllt
ist. Semaphore, die mit dem Wert $1$ initialisiert sind, werden binäre
Semaphore genannt. 

Die Änderungen des Werts von $sem$ in beiden Operationen werden
atomar durchgeführt. Versuchen zwei Prozesse gleichzeitig, eine
P-Operation auf einem binären Semaphor durchzuführen, und ist das
Semaphor frei, so wird einer der beiden Prozesse so lange verzögert,
bis $sem$ durch eine V-Operation wieder einen Wert $sem > 0$ annimmt.
Der Wert von $sem$ wird sodann in der P-Operation um den Wert $1$
vermindert, und der wartende Prozeß kann in den kritischen Abschnitt
eintreten. Analog wird während einer V-Operation der Wert des
Semaphors $sem$ atomar um $1$ erhöht. Warten mehrere Prozesse auf die
Freigabe des Semaphors, so ist die Reihenfolge der Zuteilung des
Semaphors bei Freigabe (der V-Operation) unspezifiziert. Das folgende
Programmfragment verdeutlicht die Anwendung der Se\-ma\-phor\-operationen:
\begin{xple}
  \k{let} \k{var} sem = 1

  \k{let} activity(n :Int) :\k{Ok} =
    \k{begin}
      \k{while} true \k{do} \k{begin}
        P(sem)
        (* kritischer Abschnitt von Aktivität n *)
        V(sem)
        (* restliche Tätigkeiten von Aktivität n *)
      \k{end}
    \k{end}

  (* Erzeugung von N Threads, die im wechselseitigen Ausschluß in ihren
     kritischen Abschnitt eintreten *)
  \k{for} i = 1 \k{upto} N \k{do}
    thread.fork(\k{fun}(self :thread.T(\k{Ok})) activity(n))
  \k{end}
\end{xple}
Die beschriebenen, binären Semaphore gestatten genau einem Prozeß die
Anwesenheit in einem durch ein Semaphor geschützten Abschnitt.  Zur
Lösung umfangreicherer Probleme eignen sich allgemeine Semaphore. Sie
unterscheiden sich von der ursprünglichen Definition in dem
Sachverhalt, daß der Initialwert des Semaphors einen beliebigen Wert
annehmen kann. Ein Beispiel für die Anwendung des Semaphorkonzepts
zur Implementation einer kooperativen Zusammenarbeit mehrerer Prozesse
ist das Erzeuger-Verbraucher-Problem~\cite{Stall92} .

Eine Implementation der allgemeinen Semaphore mittels der atomaren
Maschineninstruktion TEST-AND-SET gibt z.B. Stallings
an~\cite{Stall92}. Auch diese Lösung verwendet die Technik des aktiven
Wartens. Jedoch werden durch den Einsatz von TEST-AND-SET
nur sehr kurze Programmabschnitte, in denen die internen
Datenstrukturen eines Semaphors manipuliert werden, geschützt.
%die durch
%aktives Warten geschützten Abschnitte sind die hier jedoch nur zum Schutz der Semaphor-Datenstruktur
%benötigt wird und deshalb dementsprechend kurz ist. 
% vorigen Satz noch ändern
Durch die Verwendung der TEST-AND-SET-Instruktion ist diese
Implementation auch für Mehrprozessorsysteme mit gemeinsamem Speicher
geeignet. Eine Implementation mit Unterbrechungssperren für die Dauer
der Manipulation des Semaphors findet sich in der gleichen Quelle.
Implementationen unter Verwendung anderer atomarer
Maschineninstruktionen wie z.B. COMPARE-AND-SWAP geben Gray und Reuter
an~\cite{GrRe93}.  Zusammenfassend ergeben sich folgende Eigenschaften
des Semaphorkonzepts:
\begin{itemize}
\item Allgemeines Konzept zur Lösung von Synchronisationsproblemen und
  zur Implementation kooperativer Aktivitäten.
\item  Aktives Warten wird auf den kurzen Abschnitt der Manipulation
  der eigentlichen Semaphorvariablen beschränkt.
\item Semaphore verhalten sich fair, wenn zur Implementation der
  wartenden Prozesse Warteschlangenoperationen verwendet werden.
\end{itemize}
Zahlreiche Autoren weisen aber darüber hinaus auf mögliche Probleme
bei der Verwendung von Semaphoren hin:

\begin{itemize}
\item Mit Semaphoren realisierte Programme sind oft nicht leicht zu
  lesen und zu warten, die Anzahl der Semaphoroperationen ist oft
  groß und die Semaphoroperationen sind unstrukturiert über den
  Programmtext verteilt~\cite{AHV85}.  
%  Ein anschauliches Beispiel hierfür ist die Lösung des Problems des
%  Anforderns von {\em m} aus {\em n} gegebenen Betriebsmitteln
%  aus~\cite{Fr86} in Anhang~\ref{M-aus-N}.
\item Es ist oft sehr schwierig, für ein gegebenes
  Synchronisationsproblem eine Lösung anzugeben, die gleichzeitig
  korrekt und effizient ist~\cite{AHV85}.
\end{itemize}
Diese Probleme führten zur Entwicklung von Synchronisationsmethoden
die auf einem höherem Abstraktionsniveau als Semaphore angesiedelt
sind.  Diese werden in Abschnitt~\ref{SYNCPROC} besprochen.

\subsubsection{Erweiterte Semaphoroperationen}
\label{Semerweitert}
Zur Lösung von Problemen, deren Bearbeitung mit allgemeinen Semaphoren
sehr schwierig ist oder für die eine Lösung bisher gar nicht angegeben
werden konnte, werden zahlreiche Erweiterungen vorgeschlagen. Einige
Varianten sind:

\subparagraph{Semaphor-Arrays:} Diese unterscheiden sich von den
allgemeinen Semaphoren lediglich dadurch, daß Arrayelemente als
Argumente für Semaphoroperationen zugelassen sind.

\subparagraph{Gleichzeitige Semaphoroperationen} Bei den
gleichzeitigen Semaphoroperationen sind gleichzeitige P- und
V-Operationen auf mehreren Semaphoren zugelassen:

\begin{quote}
$P(sem_{0}, sem_{1}, \ldots ,sem_{n})$

$V(sem_{0}, sem_{1}, \ldots ,sem_{n})$
\end{quote}

Ein Prozeß kann bei einer multiplen P-Operation erst dann fortfahren,
wenn alle dabei angesprochenen Semaphore $sem_{i}$ durch entsprechende
V-Operationen wieder freigegeben werden. Gleichzeitige
Semaphoroperationen stehen z.B. als Betriebssystemaufruf in allen
UNIX-Implementationen zur Verfügung~\cite{SV90}.
%Freisleben weist
%darauf hin, daß mit diesen Operationen zwar die einfache Formulierung
%bestimmter Synchronisationsprobleme möglich ist, dem aber
%gravierende Schwierigkeiten bei der Implementierung auf Mehrprozessormaschinen
%gegeüberstehen. 

\subparagraph{Leser-Schreiber-Semaphoren:} Gray und Reuter geben eine
Erweiterung der Se\-ma\-phor\-ope\-ra\-tionen für das in Datenbanken
oft auftretende Leser-Schreiber-Problem an~\cite{GrRe93}. Bei diesem
Synchronisationsproblem tritt der Fall ein, daß ein Datum häufig
gleichzeitig von vielen Prozessen gelesen wird, aber nur selten in
seinem Wert verändert wird. Ein exklusives Sperren des mit dem Zugriff
verbundenen, kritischen Abschnitts mittels binärer Semaphore führt
demnach zu folgenden Ineffizienzen:
\begin{itemize}
\item  Es ist nur einem Prozeß erlaubt, gleichzeitig im kritischen
  Abschnitt aktiv zu sein. Das gleichzeitige Lesen eines Datums ist
  somit nicht möglich. 
\item Semaphoroperationen (P-Operation) auf belegten Semaphoren führen
  zur Suspendierung der aufrufenden Prozesse. Dies bedeutet, daß
  lesende Prozesse grundlos verzögert werden.
\end{itemize}
Die Erweiterung der allgemeinen Semaphore zu
Leser-Schreiber-Semaphoren wird durch die Ein\-führung zusätzlicher
Modi bei den Semaphoroperationen erreicht:
\begin{itemize}
\item Semaphore können exklusiv angefordert werden. Dies entspricht
  der bisherigen P-Operation. Kein anderer Prozeß kann in den
  kritischen Abschnitt eintreten.
\item Semaphore können als Lese-Semaphore angefordert werden. Weitere
  Anforderungen  als Lese-Semaphor können sofort
  durchgeführt werden. Prozesse, die einen schreibenden Zugriff auf ein
  Datum im kritischen Abschnitt benötigen, müssen warten, bis alle
  Lesevorgänge beendet sind und  das Semaphor wieder freigegeben ist.
\end{itemize}

\subsection{Zählen von Ereignissen}
Einen Synchronisationsmechanismus, der auf dem Zählen von durch
Prozesse ausgelösten Ereignissen basiert, stellen die von Reed und
Kanodia beschriebenen {\em Eventcounts} und {\em Sequencer}
dar~\cite{ReKa79}. Im Unterschied zu einer Kommunikation zwischen
Prozessen über gemeinsam genutzte, z.B.\ durch  Semaphore geschützte
Variablen, findet bei diesem Mechanismus der Austausch von Ereignissen
direkt über sogenannte Ereigniszähler ({\em Eventcounts}) statt. Der
Fortschritt eines Prozesses bei einer Berechnung wird über diese
Ereigniszähler angezeigt.  Ein Ereigniszähler ist eine mit Null
initialisierte, ganzzahlige Variable, auf der die folgenden drei
Operationen definiert sind\footnote{Die Notation // \ldots //
  kennzeichnet die atomare Ausführung einer Anweisungsfolge.}:
\begin{center}
\begin{tabular}{lll}
  $Advance(E)$ & : & // $E:=E + 1$ // \\

  $x:= Read(E)$ & : & $x:=E$  \\

  $Await(E, v)$ & : & Der aufrufende Prozeß wird blockiert, bis $E \ge
  v$ gilt. \\
\end{tabular}
\end{center}
Die Operation {\em Advance} erhöht den Wert des Ereigniszählers {\em
  E} atomar um den Wert $1$. Zur Beobachtung des derzeitigen Werts von
{\em E} dienen die Operationen {\em Read} und {\em Await}. Während
über {\em Read} lediglich der aktuelle Wert des Ereigniszählers
ausgelesen wird, ist es mit der Operation {\em Await} möglich, auf
einen bestimmten Wert der Variablen {\em E} zu warten. Zur Steuerung
der Reihenfolge der Abarbeitung von Ereignissen dienen Folgezähler
({\em Sequencer}). Ein Folgezähler ist eine ganzzahlige Variable, auf
der die Operation
\begin{center}
\begin{tabular}{lll}
  $x:=Ticket(S)$ & : & // $x := S$ ; $S:=S + 1$ // \\
\end{tabular}
\end{center}
definiert ist. Diese Operation liefert den alten Wert der Variablen
{\em S} und inkrementiert daraufhin diese Variable. Die gesamte
Anweisungfolge läuft atomar ab. Durch eine Ticket-Anweisung wird dem
aufrufenden Prozeß ein garantiert eindeutiger Wert zugewiesen, der
benutzt werden kann, um den geordneten Eintritt von Prozessen in
kritische Abschnitte zu gewährleisten.  Die Simulation der
Semaphoroperationen verdeutlicht dies~\cite{Fr86}:
\begin{xple}
  \k{Let} Sem $<:$\k{Ok}= \k{Tuple}
    \k{var} init   :Int
    \k{var} event  :Int
    \k{var} ticket :Int
  \k{end}

 (* Initialisierung eines binären Semaphors *)
  \k{let} sem :Sem = \k{tuple} \k{let} \k{var} init = 1  \k{and}  \k{var} event = 0  \k{and} \k{var} ticket = 0 \k{end}

  \k{let} wait(sem :Sem) :\k{Ok} =
    \k{begin}
      \k{let} t = Ticket(sem.ticket)
      Await(sem.event   t - sem.init + 1)
    \k{end}

  \k{let} signal(sem :Sem) :\k{Ok} =
    \k{begin}
      Advance(sem.event)
    \k{end}
\end{xple}
Die in der Definition des Semaphors enthaltene Variable {\em init}
gibt dessen Initialisierungswert an. Für binäre Semaphore ist hier der
Wert $1$ zu wählen. Ein die Prozedur {\em wait} aufrufender Prozeß
erhält durch das atomare Ticket ({\em sem.ticket}) einen eindeutigen
Wert zugewiesen. Hierdurch wird die Reihenfolge der Zuteilung des
Semaphors an die die Prozedur {\em wait} aufrufenden Prozesse
festgelegt. Der Ausdruck $sem.event-(t-sem.init+1)$ beschreibt die
Anzahl der Prozesse, die weiterhin die Prozedur {\em wait} aufgerufen
können, ohne durch die Operation {\em Await} blockiert zu werden.  Die
in der Prozedur {\em signal} aufgerufene Operation {\em Advance}
erhöht die Anzahl der Freigabeereignisse atomar um $1$ und gibt damit
das Semaphor frei.

%Eventcounts und Sequencer sind durch die mögliche Simulation der
%Semaphoroperationen gleichmächtig zu diesen. Weiterhin beschreiben
Reed und Kanodia merken an, daß Ereignis- und Folgezähler gegenüber
Semaphoroperationen als grundlegendere Operationen anzusehen sind:
\begin{quote}
  ``Eventcounts and sequencers can be viewed as primitives at a lower
  level than semaphores. We can build semaphores out of eventcounts
  and sequenceres, and in addition, can build some more powerful
  operations on these semaphores''~\cite[Seite 119]{ReKa79}.
\end{quote}
%Durch Eventcounts und Sequencer können weitergehende
%Semaphoroperationen simuliert werden:
Dieses belegen Reed und Kanodia durch den Einsatz ihrer Mechanismen
zur Implementation von Leser-Schreiber-Sperren sowie zur
Implementation von gleichzeitigen Operationen auf mehreren
(simulierten) Semaphoren~\cite{ReKa79} (vgl.\
Abschnitt~\ref{Semerweitert}). 

Die Autoren weisen außerdem darauf hin, daß durch die monoton
anwachsenden Werte der Ereignis- und Folgezähler Schwierigkeiten bei
der Implementation der Mechanismen auftreten. Dies gilt insbesondere
auf Systemen mit kleinen Wortgrößen, in denen die Zähler durch mehrere
Maschinenworte realisiert sind, deren Werte nicht mehr durch atomare
Schreiboperationen geändert werden können. Als Lösung geben Reed und
Kanodia einen Algorithmus zur Implementation ihrer Mechanismen an, der
lediglich die atomare Manipulation einzelner Bits von Maschinenworten
voraussetzt~\cite{ReKa79}.


\subsection{Zusammenfassung}
Dijkstras Semaphoroperationen stellen einen allgemeinen Mechanismus
zur Syn\-chro\-ni\-sa\-tion und Kommunikation nebenläufiger
Aktivitäten in Systemen mit gemeinsamem Speicher dar. Es existieren
zahlreiche Erweiterungen dieses Konzepts, die jedoch lediglich dazu
dienen, die Behandlung spezieller Problemfälle zu vereinfachen.
Zahlreiche Autoren weisen auf die oftmals schwer zu verstehenden
Lösungen von Synchronisationsproblemen durch
Se\-ma\-phor\-ope\-ra\-tionen hin.  Weiterhin kann die Trennung der
Anforderungs- und Freigabeoperationen leicht zur Ursache von
Programmierfehlern werden.  Die weiteren, in diesem Kapitel
betrachteten Synchronisationmechanismen ermöglichen ebenfalls die
einfachere Lösung mancher Synchronisationsprobleme, können jedoch
zusätzliche Probleme bei ihrer Implementation verursachen.  Semaphore
und die verwandten Synchronisationsverfahren sind daher eher als
maschinenunabhängige, elementare Verfahren zu betrachten, die
Bausteine für strukturierte Mechanismen zur Synchronisation
darstellen.



\section{Synchronisation in Programmiersprachen}
\label{SYNCPROC}
Die direkt in Programmiersprachen eingebundenen
Synchronisationsmethoden versuchen den wesentlichen Nachteil der
erweiterten Synchronisationsmethoden zu vermeiden: fehlende
Strukturierungsmöglichkeiten durch den direkten Einsatz von Semaphoren
und äquivalenten, erweiterten Methoden, die zu Fehleranfälligkeit,
erschwerter Wartbarkeit und mangelnder Durchsichtigkeit der mit diesen
Mechanismen erstellten Programmen führen.
%% vorigen Satz überprüfen!!
Hochsprachliche Synchronisationsmethoden dienen dazu,
\begin{itemize}
\item den strukturierten und sicheren nebenläufigen Zugriff von
  Prozessen auf gemeinsam genutzte Ressourcen zu ermöglichen,
\item Synchronisationsvorgänge durch strukturierte Anweisungen zu
  lokalisieren sowie
\item vom Modell der direkten Speichersynchronisation über gemeinsam
  genutzte Variablen zu abstrahieren und  durch Konzepte wie
  z.B.\ den Nachrichtenaustausch über Kommunikationskanäle und die
  explizite Formulierung von Synchronisationsbedingungen zu erweitern.
\end{itemize}
Die hochsprachlichen Synchronisationsmechanismen gliedern sich
demzufolge in:
\begin{itemize}
\item Verfahren, die wie die erweiterten Methoden auf der direkten
  Manipulation von gemeinsamen Variablen beruhen, jedoch strukturierte
  Konstrukte zur Synchronisation benutzen.
\item Verfahren, die Synchronisation gänzlich ohne gemeinsame
  Variablen erreichen und statt dessen über spezielle Kanäle
  miteinander kommunizieren.
\item Methoden, die die Formulierung von Synchronisationbedingungen
  vom eigentlichen Programmtext trennen und die Generierung des
  eigentlichen, nebenläufigen Programms in die Verantwortung von
  generischen Werkzeugen, wie z.B. spezielle Compiler oder
  Programmgeneratoren, legen.
\item Verfahren, die eine Mischung der genannten Methoden benutzen.
\end{itemize}


\subsection{Kritische Regionen}
\label{REGIONS}
Kritische Regionen und bedingte kritische Regionen wurden 1972 von
Hoare~\cite{Hoar72} und Brinch~Hansen~\cite{Hansen72} eingeführt.
Diese Konstrukte gehörten zu den ersten Synchronisationsmechanismen,
die eine strukturierte Notation für die nebenläufige Benutzung von
Ressourcen zur Verfügung stellten. Bei diesen Konstrukten werden die
von Prozessen gemeinsam zu nutzenden Ressourcen bei ihrer Deklaration
durch Schlüsselwörter gekennzeichnet.  Der eigentliche Zugriff auf
diese Ressourcen kann dann später nur innerhalb gekennzeichneter
Programmabschnitte, den eigentlichen kritischen Regionen, erfolgen.
Die Vorteile dieser Notation, die Kennzeichnung nebenläufig genutzter
Objekte, liegen in den durch einen Compiler automatisch eingefügten
Synchronisationsoperationen und der Überprüfung der korrekten
Benutzung gemeinsamer Ressourcen. Eine mögliche Notation einfacher
kritischer Regionen in TL-Syntax lautet wie folgt:
\begin{xple}
(* Deklaration *)
\k{let} \k{shared} person :Person= \k{tuple} 
  \k{let} \k{var} name = ``Hoare''
  \k{let} \k{var} age  = 30
  \k{let} \k{var} spec = \ldots
\k{end}

(* Benutzung *)
\k{region} person \k{do}
  person.spec  = f(person.age)
\k{end}
\end{xple}
Die Benutzung der gemeinsam genutzten Variablen {\em person} ist nur
innerhalb einer mit {\em region~\ldots~end} gekennzeichneten
kritischen Region zulässig. Die Implementation kritischer Regionen
kann durch das Einfügen von Semaphoranweisungen durch den Compiler
erreicht werden. Aus
\begin{xple}
\k{region} person \k{do} S \k{end}
\end{xple}
wird für jede kritische Region mit demselben Bezeichner {\em person} die
Anweisungsfolge 
\begin{xple}
  P($sem_{person}$)
    S
  V($sem_{person}$)
\end{xple}
erzeugt.  Die einfachen kritischen Regionen stellen die atomare
Modifikation bzw.\ Benutzung von Programmressourcen sicher. Um eine
Kommunikation zwischen Prozessen mittels kritischer Regionen zu
ermöglichen, wurde eine Erweiterung  kritischer Regionen, bedingte
kritische Regionen von Hoare und Brinch~Hansen vorgeschlagen. Diese
Erweiterung besteht aus der Möglichkeit, die Ausführung einer
kritischen Region mit einer Bedingung zu verknüpfen. Erst wenn diese
Bedingung erfüllt ist, wird die Ausführung eines Prozesses innerhalb
der kritischen Region fortgesetzt. Bei Nichterfüllung der Bedingung
wird die kritische Region freigegeben, andere Prozesse können dann in
diese eintreten.  Nach Verlassen der kritischen Region wird die
Bedingung erneut geprüft und entsprechend dem Ergebnis der Prüfung
fortgefahren:
\begin{xple}
(* Deklaration siehe letztes  Programmbeispiel *)

(* Benutzung mit Bedingung *)
\k{region} person \k{when} person.age $>=$ 18 \k{do}
  person.spec  := \ldots
\k{end}
\end{xple}
Des weiteren besteht die Möglichkeit, innerhalb einer kritischen Region
auf das Eintreten eines  Ereignisses zu warten:
\begin{xple}
(* Deklaration siehe oben *)

(* Benutzung mit Warten innerhalb der kritischen.\ Region *)
\k{region} person \k{do}
  \ldots
  \k{await}(person.spec == default)
  \ldots
\k{end}
\end{xple}
Solange die Bedingung innerhalb der kritischen Region nicht erfüllt
ist, werden der darin ausführende Prozeß verzögert und die kritische
Region freigegeben. Sobald die Bedingung erfüllt ist und sich kein
anderer Prozeß innerhalb der kritischen Region befindet, wird die
Ausführung des wartenden Prozesses fortgesetzt.  Die Implementation
bedingter kritischer Regionen ist insofern problematisch, als daß die
Bedingungen für den Eintritt in eine kritische Region bzw.\ das
Fortsetzen eines Prozesses nach einer {\bf await}-Anweisung nach jedem
Verlassen der kritischen Region durch einen anderen Prozeß erneut
geprüft werden müssen.  Dieses stellt, verglichen mit der
Programmierung desselben Kommunikationsproblems durch Semaphore, einen
nicht unerheblichen zusätzlichen Aufwand dar~\cite{Hoar85}.
Brinch~Hansen bezeichnet diese Form des Wartens auf Ereignisse als
kontrolliertes aktives Warten (``controlled form of busy
waiting'')~\cite{Hansen72}. 

%% Lit.angabe für TooL
\subsection{Monitore}
\label{MONITOR}
Die Zusammenfassung komplexer Datenstrukturen mit den auf ihnen
operierenden Funktionen sind in verschiedenen Ausprägungen in vielen
Programmiersprachen vorhanden.  Das Modulkonzept des Tycoon-Systems
sowie die Klassenkonzepte von Programmiersprachen wie z.B.\ Ada, C++,
Modula-3, Smalltalk oder der auf der Basis des Tycoon-Systems
entwickelten, objektorientierten Sprache TooL sind Beispiele hierfür.
Gemeinsam ist diesen Konzepten unter anderem die Kontrolle des
Zugriffs auf die eigentlichen Datenobjekte durch Abkapselung der
verschiedenen Datenstrukturen voneinander. Der Zugriff auf
Datenobjekte ist nur durch die zu den Datenobjekten selbst gehörenden,
bei ihrer Deklaration angegebenen Zugriffsfunktionen möglich. Eine
Entsprechung dieses Konzepts bezüglich der Synchronisationsanforderungen
liegt bei den sogenannten Monitoren vor~\cite{Hoar74}.  In der
Datenstruktur eines Monitors sind die spezifizierten, zum Monitor
gehörenden Komponenten zusätzlich vor konkurrierendem Zugriff durch
nebenläufige Prozesse geschützt. Es ist zu einem Zeitpunkt lediglich
einer Zugriffsfunktion gestattet, im Monitor aktiv zu sein. Andere
Prozesse, die ebenfalls Zugriffsfunktionen des Monitors aufrufen
wollen, werden verzögert, bis der derzeitige Prozeß den Monitor
verlassen hat. Zusätzlich zu diesen Einschränkungen besteht, analog zu
den kritischen Regionen, die Möglichkeit, während der Ausführung einer
Zugriffsfunktion auf die Erfüllung angegebener Ereignisse zu warten.
Hierdurch wird bis zum Eintreten dieser Ereignisse die
Ausführungskontrolle an andere Prozesse abgegeben. Ein Beispiel für
die Deklaration und Benutzung eines Monitors ist die Simulation eines
binären Semaphors~\cite{Hoar85}. Die hier verwendete Notation stellt
bereits eine geringfügige Erweiterung des ursprünglichen
Monitorkonzepts dar (siehe unten):
\begin{xple}
(* Deklaration *)
\k{monitor} Singleresource;
\k{var} free :Boolean;
\k{procedure} *acquire;
  \k{when} free \k{do} free := false;      (* wait(free) *)
\k{procedure} *release;
  \k{begin}  free := true; \k{end};        (* signal(free) *)
\k{begin}
  free := true;
  \ldots
\k{end}

(* Benutzung *)
\k{instance} semaphore :Singleresource;
semaphore.acquire;
\ldots
semaphore.release;
\end{xple} 
Der Aufruf der Monitorprozedur {\em acquire} im obigen Beispiel
bewirkt die Verzögerung des aufrufenden Prozesses, falls die
Auswertung der Variablen {\em free} nicht den Wert {\em true} ergibt.
Eine anderer wartender Prozeß kann nun in den Monitor eintreten.  Die
Rolle der Variable {\em free} entspricht der einer von Hoare für das
Warten innerhalb von Monitoren vorgeschlagenen Bedingungsvariablen
(Condition variable).  Auf einer Bedingungsvariablen {\em cond} sind
die folgenden drei Operationen definiert:
%% Lit.angabe Hoare ??
\begin{center}
\begin{tabular}{lcp{4.5in}}
wait(cond) & : & Der aufrufende Prozeß gibt die kritische Region frei und
wartet auf das Eintreffen der Bedingung {\em cond}. \\
signal(cond) & : & Der aufrufende Prozeß signalisiert das Eintreffen der
Bedingung {\em cond}. Ein auf diese Bedingung wartender Prozeß kann nach
Verlassen der kritischen Region durch den {\em signal(cond)} aufrufenden
Prozeß weitergeführt werden. \\ 
queue(cond) & : & Sind auf die Bedingung {\em cond} wartende Prozesse
vorhanden, so ergibt diese Funktion den boolschen Wert {\em true}. \\
\end{tabular}
\end{center}
%% Schlüsselwörter kursiv??
Bedingungsvariablen ermöglichen also die Anwesenheit mehrerer Prozesse
in einem Monitor. Bis auf einen ausführenden Prozeß sind allerdings
alle anderen Prozesse durch das Warten auf den Eintritt einer
Bedingung blockiert.

Eine auf Semaphoren basierende Implementation von Monitoren gibt Hoare
an~\cite{Hoar74}.  Eine vereinfachte Implementation des
Monitorkonzepts findet sich in der objektorientierten
Programmiersprache Modula-3~\cite{Nels91}. Da Modula-3 bereits über
alle Mechanismen zur Definition von Modulen verfügt, wurden zur
Realisierung von Monitoren lediglich Bedingungsvariablen sowie eine
Form der binären Semaphore, sogenannte Mutexe, hinzugefügt.  Zur
eigentlichen Sprache gehört hier lediglich das geordnete Akquirieren
und Freigeben der Mutexe durch das Sprachelement {\em LOCK}. Die
Verwendung dieses Schlüsselwortes stellt die ausschließliche Benutzung
eines Mutex durch den aktuell im Programmabschnitt ablaufenden Prozeß
sicher. Eine anderweitige Manipulation, wie beispielsweise die
explizite Freigabe eines Mutex durch einen anderen Prozeß, ist nicht
ohne weiteres möglich. Als Beispiel für die Benutzung von Mutexen und
Bedingungsvariablen ist folgendes Programmfragment in der
Programmiersprache Modula-3 angegeben:
\begin{xple}
  (* Deklaration *)
  \k{VAR} m := \k{NEW}(\k{MUTEX});
  \k{VAR} c := \k{NEW}(Thread.Condition);
   
  (* Prozeß A: evtl. Warten auf Eintritt der Bedingung $B_{1}$ *)
  \k{BEGIN}
  \k{LOCK}(m) \k{DO}
    \k{WHILE} \k{NOT}($B_{1}$) \k{DO}
       Thread.Wait(m, c);
       $S_{1}$;         (* Bearbeitung geschützter Ressourcen *)
    \k{END};
  \k{END};

  (* Prozeß B: Erfüllung der Bedingung c und ihrer Signalisierung *)
  \k{BEGIN}
  \k{LOCK}(m) \k{DO}
     $S_{2}$;                     (* Erfüllung der Bedingung $B_{1}$ *)
     Thread.Signal(c);  (* Signalisieren der Bedingung $B_{1}$ *)
    \k{END};
  \k{END};
\end{xple}
%% Schlüsselwörter kursiv ??
Die Benutzung von Bedingungsvariablen ist nur im Zusammenhang mit
Mutexen zum Schutz von kritischen Abschnitten sinnvoll. Die
Bedingungsvariablen ermöglichen, analog zum Monitorkonzept, die
Aufhebung des durch einen Mutex erzwungenen, gegenseitigen Ausschlusses
von Prozessen.  Durch Aufruf der Funktion {\em Thread.Wait(m,c)} im
obigen Beispiel werden der Mutex {\em m} freigegeben und der aufrufende
Prozeß suspendiert (Prozeß {\em A}).  Nach Erfüllung der Bedingung
$B_{1}$ (Prozeß {\em B}) wird dieser Sachverhalt durch Aufruf der
Funktion {\em Thread.signal(c)} signalisiert. Dieser Aufruf führt zur
erneuten Aktivierung von Prozeß {\em A}. Nach Freigabe des Mutex {\em
  m} durch Prozeß {\em B} wird dieser Mutex von Prozeß {\em A} erneut
akquiriert.  Wurde keinem anderen Prozeß dieser Mutex zugeteilt, kann
Prozeß {\em A} in seinem kritischen Abschnitt fortfahren.  Bei der
Modula-3--Implementation der Bedingungsvariablen ist zu beachten, daß
im Gegensatz zu denen bei Hoare beschriebenen Monitoren die Erfüllung
einer Bedingung beim Signalisieren derselben durch {\em Thread.Signal}
nicht garantiert ist.  Andere Prozesse können bereits vor dem auf die
Bedingung wartenden Prozeß im kritischen Abschnitt (nach Akquirierung
des den Abschnitt schützenden Mutex) aktiv geworden
sein~\cite{Birell87}. Aus diesem Grund ist der erneute Test der
Bedingung ($B_{1}$, s.o.) nach Verlassen der Funktion {\em
  Thread.Wait} notwendig.

Monitore sind in verschiedenen Ausprägungen unter anderem in den
Sprachen Concurrent Pascal, Pascal-Plus, Modula-2 sowie, wie bereits
besprochen, in Modula-3 implementiert~\cite{Hansen75} \cite{WEBE79}
\cite{Wirt85} \cite{Nels91}.
%\comment{Hier noch Vorteile und Nachteile von Monitoren}

\subsection{Kommunikationskanäle und Rendezvous}
\label{KommRend}
%Bei den bisher besprochenen Synchronisationsmechanismen kommunizieren
%Prozesse über gemeinsam benutzte Variablen und  
%Die bisher besprochenen Synchronisationsmechanismen beruhen auf dem
%Konzept der Speichersynchronisation.
Bei den bisher besprochenen Synchronisationsmechanismen kommunizieren
mehrere nebenläufige Prozesse über die durch
Synchronisationsmechanismen kontrollierte Modifikation von Variablen.
Diese Art der Kommunikation und Synchronisation setzt das
Vorhandensein eines gemeinsamen Speichers voraus. Hoare präsentierte 1978
ein allgemeines mathematisches Modell zur Beschreibung
kommunizierender, konkurrierender Prozesse, das unter anderem von
Randbedingungen wie dem Vorhandensein eines gemeinsamen Speichers
abstrahiert~\cite{Hoar78}.  CSP\footnote{Communicating Sequential
  Processes.}
%% Begriff CSP erl.
\begin{itemize}
\item leistet die Formalisierung des Begriffs des {\em sequentiellen
    Prozesses} sowie die Einführung des Prozeßkonzepts als
  mathematische Abstraktion der Interaktion zwischen einem System und
  dessen Umgebung;
\item erlaubt die Beschreibung und programmtechnische Behandlung
  nichtdeterministischer Vorgänge;
%benutzt Nichtdeterminismus  als allgemeines Beschreibungsmittel für
%  Prozeßinteraktion. 
%\comment{Beispiel}
\item gibt eine mathematische Beschreibung der Kommunikation von
  Prozessen als Spezialfall von Prozeßinteraktion.
\end{itemize}
Die Programmiersprache CSP nutzt die von Dijkstra eingeführten
Sprachmittel der parallelen Komposition, den sogenannten bewachten
Befehlen (Guarded Commands), sowie der nichtdeterministischen Auswahl
zwischen Alternativen~\cite{Dijk75}. Die parallele Komposition von
Prozessen beschreibt die Zusammenfassung nebenläufiger Prozesse zu
einem Prozeß, dessen Verhalten sich aus dem Verhalten der einzelnen
Unterprozesse ergibt.  Die Notation
\begin{xple}
 X \k{::} \k{[} P \k{$\|$} Q \k{$\|$} R \k{]}
\end{xple}
bezeichnet einen Prozeß X, der sich entsprechend dem nebenläufigen
Verhalten der Unterprozesse P, Q und R verhält.

Ein bewachter Befehl besteht aus einem boolschen Ausdruck, dem Wächter
(Guard), sowie einer Liste von Programmanweisungen. Diese Liste wird
nur dann ausgeführt, wenn die Auswertung des Wächters den boolschen
Wert {\em true} ergibt. Mehrere bewachte Anweisungen können zu einer
Liste kombiniert werden. Ergibt die Auswertung mehrerer Wächter den
boolschen Wert {\em true}, so wird die Entscheidung, welche der den
Wächtern zugeordneten Anweisungsfolgen bearbeitet wird,
nichtdeterministisch getroffen. Hoare benutzte für dieses Konstrukt
die folgende Notation:
\begin{xple}
 X \k{::} \k{[} g1 $\rightarrow$ P $\Box$ g2 $\rightarrow$ Q $\Box$ g3 $\rightarrow$ R \k{]}
\end{xple}
Diese Anweisungsfolge beschreibt einen Prozeß {\em X}, der sich wie
die Prozesse {\em P}, {\em Q} oder {\em R} verhält, wenn einer der
Wächter {\em g1}, {\em g2} oder {\em g3} zum boolschen Wert {\em true}
evaluiert. Ist dies bei mehr als einem Wächter der Fall, so wird die
Auswahl zwischen den auf die Wächter folgenden Prozesse
nichtdeterministisch durchgeführt.  Ergibt keine Auswertung eines
Wächters den Wert {\em true}, so kann der gesamte Prozeß {\em X} nicht
weiter ausgeführt werden.

Zur Kommunikation zwischen Prozessen dienen Ein- und Ausgabeanweisungen,
die jeweils einen Wert an einen bezeichneten Prozeß übermitteln bzw.\
einen Wert von einem Prozeß empfangen. Der Nachrichtenaustausch findet
erst dann statt, wenn beide beteiligten Prozesse eine passende
Kommunikationsanforderung absetzen.  Diese Form des
Nachrichtenaustausches wird auch als {\em Rendezvous} bezeichnet. Die
Anweisungsfolgen 
\begin{xple}
\begin{tabular}{ll}
 X \k{::} \k{$\ast$[} a?x $\rightarrow$ P $\Box$ b?x $\rightarrow$ Q \k{]} &
 Y \k{::} \k{$\ast$[} c!y \ldots \k{]}
\end{tabular}
\end{xple}
beschreiben einen Prozeß {\em X}, der Werte von den Prozessen {\em a}
oder {\em b} liest und sich dann wie die Prozesse {\em P} und {\em Q}
verhält. Der Prozeß {\em Y} gibt dagegen einen Wert an den Prozeß {\em
  c} aus. In diesem Beispiel werden Ein- und Ausgabeanweisungen als
Wächter benutzt. Diese Anweisungen ergeben jeweils den boolschen Wert
{\em false}, wenn die durch sie adressierten, schreibenden und lesenden
Prozesse beendet sind. Das Zeichen {\bf $\ast$} beschreibt die
wiederholte Ausführung der jeweiligen Anweisungsfolgen.  Im
ursprünglichen Entwurf der Sprache CSP war eine Kommunikation nur
durch direkte Aufzählung der beteiligten Prozesse möglich. Dies hat
den Nachteil, daß alle Prozesse von vornherein bekannt sein müssen.
In einer späteren, erweiterten Fassung von CSP werden benannte
Kommunikationskanäle eingeführt, die eine indirekte Adressierung von
Prozessen gestatten~\cite{Hoar85}. In diesem Fall entsprechen die
obigen Variablen {\em a}, {\em b} und {\em c} solchen
Kommunikationkanälen.

Eine Synchronisation nebenläufiger Prozesse wird in CSP allein durch
die Kommunikation über benannte Kanäle erreicht. Ein gemeinsamer
Speicher, dessen nebenläufige Benutzung durch andere
Synchronisationsmechanismen, wie z.B.\ Semaphore, abgesichert wird,
ist nicht notwendig. Hierdurch sind diese Mechanismen für verteilte
Systeme geeignet, die im allgemeinen über keinen gemeinsamen Speicher
verfügen.

Bewachte Befehle mit nichtdeterministischer Auswahl und das Konzept
des Nachrichtenaustausches über Rendezvous wurden in zahlreiche
weitere Sprachen übernommen. Hier ist im speziellen die Sprache Occam
zu nennen, die eine sehr direkte Umsetzung der Konzepte von CSP
darstellt~\cite{STEIN88}. Diese Sprache ist zur Programmierung
spezieller Mikroprozessoren, den sogenannten Transputern, entwickelt
worden, die bereits eine maschinelle Unterstützung zur Realisierung
nebenläufiger Prozesse und die Kommunikation über physikalische Kanäle
bieten~\cite{INMO85}. Das Konzept der Rendezvous, zusammen mit der
nichtdeterministischen Auswahl, finden in den {\em select}-Anweisungen
der Sprachen Synchronous C++~\cite{Abel93} und Ada ihre
Entsprechung~\cite{BULIWE87}.  Darüber hinaus stellt Ada weitere
Synchronisationmechanismen wie Monitore und Semaphore zur Verfügung.
Rendezvous sowie nichtdeterministische Auswahl sind ebenfalls in der
experimentellen Sprache Orca zu finden~\cite{BAL95}.
Implementationstechniken zur Realisierung verteilter Rendezvous werden
detailliert von Atkinson beschrieben~\cite{ATMONA88}.

\subsection{Weitere Mechanismen}
\label{Weitere}
In den bisher besprochenen Verfahren zur Synchronisation werden die
eigentlichen Synchronisationsanweisungen teilweise explizit benutzt,
wie zum Beispiel die {\em LOCK}-Anweisung in Modula-3 oder das {\em AWAIT}
der Pascal-Plus Monitore, aber auch implizit von Compilern oder
Laufzeitsystemen erzeugt. Der automatische, gegenseitige Ausschluß bei
kritischen Regionen, Monitoren oder die Synchronisation durch die
Kommunikationsmechanismen von CSP sind Beispiele hierfür. Gemeinsam
ist diesen Verfahren die Verteilung von Anweisungen für die
Synchronisation über den gesamten Programmtext. Ein alternativer
Ansatz hierzu ist die Spezifikation von Synchronisationsbedingungen,
die von den eigentlichen Programmanweisungen getrennt sind. Die
Realisierung der konkreten Synchronisationsanweisungen wird dann
vollständig durch Compiler bzw. Laufzeitsysteme übernommen.
\subparagraph{Pfadausdrücke:} Die von Campell und Habermann
vorgeschlagenen Pfadausdrücke beschreiben Synchronisationsanweisungen
und Ausführungsreihenfolgen in einer regulären Ausdrücken ähnlichen
Form.  Synchronisationsbedingungen werden getrennt vom sonstigen
Programmtext formuliert~\cite{Ha75}. Das (sequentielle) Verhalten der
Programme wird durch Prozedur- und Typendeklarationen beschrieben, die
eine mit Monitoren verwandte Struktur aufweisen. Im einzelnen können
mit Pfadausdrücken folgende Arten der Prozedurausführung spezifiziert
werden:
\begin{center}
\begin{tabular}{lcp{4.5in}}
 {\bf path} {\em P1} {\bf end} & : & Die Prozedur {\em P1} kann
 wiederholt ausgeführt werden. Es ist jedoch zu einem bestimmten
 Zeitpunkt nur einem Prozeß möglich, innerhalb von {\em P1} aktiv zu
 sein. Diese entspricht dem Verhalten einer kritischen Region oder
 eines Monitors. \\ \\ 

\{{\em P1}\} & : &  Die Prozedur {\em P1} kann nebenläufig durch
mehrere Prozesse ausgeführt werden. Es können jedoch nur dann weitere
Prozesse {\em P1} ausführen, solange ein anderer Prozeß noch in {\em
  P1} aktiv ist. \\ \\ 

{\em P1} ; {\em P2} ; {\em P3} & : &  Diese Notation beschreibt die
sequentielle Ausführungsreihenfolge der genannten Prozeduren {\em P1},
{\em P2} und {\em P3}. Die Prozeduren können durch verschiedene
Prozesse  ausgeführt werden, die Reihenfolge der Ausführung findet
jedoch wie angegeben statt. Beispielsweise wird ein Prozeß, der mit
der Ausführung der Prozedur {\em P3} beginnen möchte verzögert, bis
die Prozeduren {\em  P1} und {\em P2} bearbeitet wurden. \\ \\

{\em P1}, {\em P2}, {\em P3} & : & Bei dieser Selektionsanweisung kann
genau eine der Prozeduren ausgeführt werden. Die Auswahl, welche der
Prozeduren ausgeführt wird, findet nichtdeterministisch statt. \\
\end{tabular}
\end{center}
Der Name einer Prozedur darf in einem Pfadausdruck nur einmal
erscheinen, sonst können die Ausdrücke beliebig verschachtelt sein.
Das folgende Beispiel zeigt die Synchronisation von Leser-
Schreibervorgängen durch Pfadausdrücke~\cite[Seite 122--123]{Fr86}.
\begin{xple}
\k{path} requestwrite \k{end};
\k{path} \{read\} , write \k{end};
\end{xple}
\begin{minipage}[t]{3in}
\begin{xple}
\k{procedure} read:
\k{begin}
  (* Lesevorgang *)
\k{end};
\end{xple}
\end{minipage}
\begin{minipage}[t]{3in}
\begin{xple}
\k{procedure} write:
\k{begin}
  (* Schreibvorgang *)
\k{end};
\end{xple}
\end{minipage}
\begin{xple}
\k{procedure} requestwrite:
\k{begin} write \k{end};
\end{xple}
Ein Schreibvorgang wird durch Ausführung der Prozedur {\em
  requestwrite} eingeleitet, weitere Schreibvorgänge werden bis zur
Beendigung der Prozedur {\em write} verzögert.  Ebenfalls werden
gleichzeitige Leseversuche bis zur Beendigung der Prozedur {\em write}
verzögert. Da die Prozedur {\em write} vor der Prozedur {\em
  requestwrite} beendet wird, erhalten wartende Leser Vorrang vor
wartenden Schreibern. Hat ein Prozeß mit dem Lesevorgang begonnen,
können weitere Prozesse Lesevorgänge einleiten.



Ein Beispiel für einen komplexen Pfadausdruck ist:
\begin{xple}
\k{path} P1, (P2; P3; \{P4; P5\}), P6 \k{end};
\end{xple}
Hierdurch wird die wiederholte Ausführung der notierten Prozeduren
beschrieben. Zunächst kann entweder {\em P1} oder {\em P2} oder {\em
  P6} ausgeführt werden. Bei der Auswahl von {\em P2} wird zunächst
{\em P2}, dann {\em P3} sequentiell bearbeitet. Die folgende
Ausführung des Ausdrucks \{{\em P4}; {\em P5}\} kann von mehreren
Prozessen parallel durchgeführt werden. Jedoch muß ein Prozeß, der
{\em P5} aufruft, warten, bis die Bearbeitung von {\em P4} beendet
ist.

Pfadausdrücke erinnern durch die Art ihrer Notation und
Kombinierbarkeit an reguläre Ausdrücke. Wie bei diesen ist es nicht
möglich, z.B.\ Informationen über den Zustand der durch einen
Pfadausdruck beschriebenen Abläufe zu erhalten. So ist es in einem
Pfadausdruck nicht möglich, die Anzahl der auf die Ausführung einer
Prozedur wartenden Prozesse zu erhalten bzw. zu benutzen.
Synchronisationsprobleme, die diese Art von Informationen benötigen,
lassen sich nur durch Verwendung weiterer Synchronisationsmechanismen
oder durch Erweiterungen der Pfadausdrücke lösen~\cite{Fr86}. Eine
Anwendung von Pfadausdrücken für die Kommunikation von Prozessen in
verteilten Rechnersystemen finden sich bei McLaughry~\cite{McL95}.
Eine Implementation von Pfadausdrücken mittels Semaphoren gibt
Habermann an~\cite{Ha75}.

%\subparagraph{Automatische Parallelisierung} 
%Zusätzlich zu den Methoden der expliziten Formulierung nebenläufiger
%Prozesse und Synchronisationsbedingungen in Programmiersprachen wurden
%Verfahren zur automatischen Parallelisierung sequentieller Programme
%entwickelt.  Ein Hauptziel  hierbei ist die bessere Ausnutzung
%paralleler Rechnerarchitekturen durch schon bestehende
%Softwarebestände~\cite{Pe87}. Eine Parallelisierung auf der Ebene
%einzelner Programmanweisungen leisten  Datenflußmaschinen zusammen mit
%eigens für ihre Programmierung entworfenen Sprachen~\cite{Pe87}.

\subsection{Zusammenfassung}
In allen Sprachen, die die nebenläufige Ausführung von
Programmabschnitten erlauben, finden sich verschiedenartige
Mechanismen zur Prozeßsynchronisation. Wesentliche Unterschiede
bestehen in der Möglichkeit bzw.\ Notwendigkeit,
Synchronisationsanweisungen explizit zu formulieren oder diese Arbeit
einem Werkzeug, wie z.B.\ einem Compiler, zu überlassen. Unterschiede
bestehen weiterhin in der Effizienz möglicher Implementationen.
Pfadausdrücke unterliegen bezüglich der Menge der lösbaren Probleme
den gleichen Einschränkungen wie die regulären Ausdrücke.



\section{Synchronisation in persistenten Objektsystemen}
\label{SyncPers}
%% 
Für Synchronisationsmechanismen in persistenten Objektsystemen sind
eine Reihe verschiedener An\-sätze vorhanden. Für alle gilt die
Feststellung, daß die in herkömmlichen, relationalen Datenbanksystemen
verfolgte Strategie zur Herstellung von Datenkonsistenz, der
Verwendung atomarer Transaktionen nach dem ACID-Modell, für typische
Aufgabenstellungen persistenter Objektsysteme nur ungenügend geeignet
ist. Im Gegensatz zu solchen Systemen steht in persistenten
Objektsystemen die Formulierung von Operationen auf sehr komplexen
Objektstrukturen mittels der vorhandenen Sprachmittel im Vordergrund.
Ein weiterer Faktor ist das Vorhandensein lang andauernder,
kooperativer Aktivitäten, zu denen die in herkömmlichen
Datenbanksystemen vorgesehenen, für sehr kurz andauernde Transaktionen
ausgelegten Mechanismen, nicht passen.

Im einzelnen gliedern sich die in persistenten Objektsystemen
verwirklichten Mechanismen zur Sicherstellung von Datenkonsistenz in
Methoden zur Spezifikation erweiterter, kooperativer
Transaktionsmechanismen und Mechanismen, die, wie die in dieser Arbeit
betrachteten Mechanismen, eine explizite, nichttransaktionale
Kontrolle über nebenläufige Zugriffe auf Datenobjekte gestatten.

Zu den erweiterten, transaktionalen Ansätzen zählen Methoden, die die
strikte Forderung nach Isolation nach dem ACID-Modell lockern und
Zugriff auf in laufenden Transaktionen benutzte Objekte
gestatten~\cite{GrRe93}.  Ein Beispiel hierfür sind die sogenannten
Transaktionsgruppen~\cite{Mun93}. In solchen Transaktionsgruppen
werden Transaktionen in einem Baum angeordnet, dessen Elemente aus
Knoten und Blättern bestehen.  Die zu einem Knoten gehörenden Blätter
stellen hierbei kooperative Transaktionen dar, die gegenseitig auf in
ihnen bearbeitete Objekte zugreifen können.  Transaktionsgruppen
werden durch Spezifikation zu Pfadausdrücken ähnlichen Mustern
spezifiziert, die die gewünschte Reihenfolge von Transaktionen
beschreiben~\cite{Ha75}. Weiterhin werden durch derartige Muster auch
Operationen beschrieben, die sich gegenseitig ausschließen. Im System
ist dadurch eine Menge kooperativer Transaktionen vorhanden. Die
Rücknahme einer einzelnen Transaktion betrifft nur einen
möglicherweise sehr kleinen Teil der durchgeführten Änderungen und
nicht das gesamte System. Eine Implementation von Transaktionsmustern
liegt in der Sprache DPS-Algol vor, einer Erweiterung der persistenten
Sprache PS-Algol~\cite{Mun93}~\cite{ABCCM83a}.

\begin{sloppypar}
Eine Erweiterung von PS-Algol um Sprachkonstrukte zur Formulierung
ne\-ben\-läu\-fi\-ger Threads ist in der Sprache DPS-Algol
verwirklicht~\cite{Kra87}. In dieser Sprache stehen durch Threads
implementierte, kooperative Aktivitäten im Vordergrund.  Threads
synchronisieren Zugriffe auf Datenobjekte mittels bedingter kritischer
Regionen (siehe Abschnitt~\ref{REGIONS}).  Transaktionale Vorgänge im
System werden durch kritische Regionen und Funktionen höherer Ordnung
verwirklicht.
\end{sloppypar}



Ein System, das wie das Tycoon-System über persistente Threads
verfügt, ist das Napier88-System der Universität
St.~Andrews~\cite{Nap95}. Nebenläufige Zugriffe auf Datenobjekte
können in Napier88 durch Semaphore koordiniert werden~\cite{Nap96}.
Weiterhin werden Mittel zur Spezifikation der Sichtbarkeit von
Transaktionen nach dem CACS-Modell\footnote{Communicating Actions
  Control System.} bereitgestellt~\cite{StMo92}.
%% CACS noch beschreiben ???


% Local Variables:
% TeX-master: "da"
% TeX-parse-self: t
% TeX-auto-save: t
% End:
