\chapter{Synchronisation migrierender Threads}
\label{Migration}
Das Tycoon-System verfügt über Mechanismen, beliebige persistente
Objekte in entfernte Objektspeicher zu verlagern~\cite{BM96}. Diese
Mechanismen sind daher auch auf Tycoon-Threads anwendbar.
Thread-Mobilität bedeutet, daß ein Thread den Adreßraum, in dem der
Thread abläuft, verlassen und in einen entfernten Adreßraum
(Objektspeicher) migrieren kann. In diesem wird die Ausführung des
Threads fortgesetzt.  Weitere Migrationsvorgänge, zum Beispiel die
Rückkehr in den ursprünglichen Adreßraum, können folgen.

Die potentielle Mobilität von Tycoon-Threads ist bei der
Implementation der Synchronisationsverfahren zu berücksichtigen. In
diesem Kapitel wird zunächst eine Übersicht über Funktionsweise und
Implementation von Thread- und Objektmobilität gegeben
(Abschnitt~\ref{Mobil}). Ein generelles, bei der Migration von
Tycoon-Objekten auftretendes Problem stellen transitive referentielle
Abhängigkeiten zwischen Tycoon-Objekten dar. In Abschnitt~\ref{Minref}
werden eine Übersicht über den Zusammenhang zwischen Migration,
referentiellen Abhängigkeiten und Synchronisationsmechanismen gegeben
sowie die Auswirkungen von Thread-Migration auf die Implementation der
Synchronisationsmechanismen beschrieben.


Wie nachfolgend beschrieben wird, kann ein Thread eigenständig
migrieren oder passiv von einem weiteren Thread in einen entfernten
Objektspeicher übertragen werden.  Threads, die in diesem Zusammenhang
an Synchronisationsvorgängen beteiligt sind, können den Zustand
weiterer, ebenfalls an diesen Synchronisationvorgängen beteiligter
Threads und Synchronisationsvariablen verändern. Die dadurch
erforderlichen Maßnahmen, die eine korrekte Funktionsweise der
Synchronisationsmechanismen bei Migration sicherstellen, werden im
Abschnitt~\ref{Zustandswechsel} behandelt.


\section{Implementation der Thread--Mobilität}
\label{Mobil}
Um eine Mobilität von Tycoon-Objekten zu erreichen, werden typsichere,
entfernte Funk\-tions\-auf\-rufe\footnote{Remote Procedure Calls (RPC).}
benutzt~\cite{Goell96}. Prinzipiell vollzieht sich die Übertragung
eines Tycoon-Objekts durch dessen Übergabe  als Argument an
eine entfernte Funktion:
\begin{enumerate}
\item Argumentwerte werden mittels Netzwerkfunktionalität zu einem
  entfernten System übertragen.
\item Die entfernte Funktion wird mit den erhaltenen Argumenten
  ausgeführt. 
\item Der Rückgabewert der entfernten Funktion wird an das aufrufende
  System zurückgesendet.
\end{enumerate}
Um eine entfernte Funktion aufrufen zu können, ist zunächst eine
Bindung an einen entfernten Dienst notwendig. Durch eine derartige
Bindung wird einem Dienstnehmer ein ausführbares Tycoon-Objekt zur
Verfügung gestellt, das eine Anbindung an eine entfernte Funktion
leistet.  Wie eine derartige Bindung an einen entfernten Dienst
realisiert wird, beschreibt der folgende Abschnitt.

\subsection{Entfernte Funktionsaufrufe}
\label{RPC}
Ein Tycoon-System, das weiteren Tycoon-Systemen Dienste als entfernte
Funktionsaufrufe zur Verfügung stellt, registriert diese Dienste durch
Aufruf der Funktion {\em register} des Moduls {\em server}. Diese
Registrierung findet bei einem im Tycoon-System implementierten
Auskunftsdienst für entfernte Dienste statt~\cite{Goell96}:
\begin{xple}
register(server  
         :ServiceType
         :Attributes
         attributFunction
         searchFunction
         rpc)
\end{xple}
Die Funktion {\em register} erwartet als Argument ein Server-Objekt
{\em server}, das die späteren Dienstanfragen bearbeitet. Der Typ des
zur Verfügung gestellten, entfernten Dienstes wird durch den Datentyp
{\em :ServiceType} repräsentiert. Das Argument {\em Attributes} dient
der Angabe des Datentyps der weiteren Attribute des Dienstes, die
Funktion {\em attributFunction} auf der Seite des Diensterbringers der
dynamischen Feststellung von Attributen.  Beispielsweise kann eine
derartige Funktion bei einer Anfrage zeitabhängige Attribute
berechnen. Der Rückgabewert dieser Funktion wird für die Auswahl des
gewünschten Dienstes benutzt (siehe {\em bind}).  Eine auf den
definierten Dienst abgestimmte Suchfunktion wird durch die Funktion
{\em searchFunction} spezifiziert. Diese Funktion kann auf der Seite
des Dienstnehmers benutzt werden, um einen Dienst nach einem
Verbindungsabbruch wieder aufzufinden. Durch den Wert {\em rpc} wird
die Funktionalität angegeben, die einem entfernten Dienstnehmer zur
Verfügung gestellt wird. Die in diesem Wert kodierten Funktionen
werden bei einem entfernten Aufruf durch den Server-Thread {\em
  server} ausgeführt.

Dienstnehmer erhalten durch Aufrufe der Funktion {\em bind} des Moduls
{\em client} Zugriff auf entfernte Dienste:
\begin{xple}
\k{let} rpc = client.bind(:ServiceType  :Attributes  predicate)
\end{xple}

Wiederum wird der Typ des benötigten Dienstes durch das Argument {\em
  :ServiceType} angegeben. Der gewünschte Datentyp der Dienstattribute
wird durch Angabe des Arguments {\em :Attributes} spezifiziert. Eine
Prädikatsfunktion, durch die ein Dienst auf Seite des Diensterbringers
ermittelt wird, enthält das Argument {\em predicate}. Dieser Funktion
wird während der Dienstauswahl der Rückgabewert der zuvor besprochenen
Funktion {\em attributeFunktion} übergeben. Das folgende Beispiel
beschreibt die Registrierung eines Dienstes zur Berechnung eines
ganzzahligen Werts auf der Seite des Diensterbringers und dessen
Benutzung seitens des Dienstnehmers:
\begin{xple}
  (* Spezifikation des Dienstes *)
  \k{Let} ServiceType = \k{Tuple} compute(x :Int) :Int \k{end}
  \k{Let} Attributes = String
  \k{let} attributeFunction() :Attributes = ``computeservice''
  \k{let} rpc :ServiceType = \k{tuple}
    \k{let} compute(x :Int) = \k{begin} \ldots \k{end}
  \k{end}

  (* Registrierung des Dienstes *)
  \k{let} newServer = server.new()
  server.register(newServer :ServiceType  :Attributes  attributeFunction 
                  server.searchFun  rpc)
\end{xple}
Auf der Seite des Diensterbringers steht nach Aufruf der Funktion {\em
  register} ein Dienst {\em compute} für entfernte Aufrufe zur
Verfügung. Auf der Seite des Dienstnehmers kann jetzt die Bindung an
diesen Dienst erfolgen:
\begin{xple}
  (* Spezifikation des Dienstes *)
  \k{Let} ServiceType = \k{Tuple} compute(x :Int) :Int \k{end}
  \k{Let} Attributes = String
  \k{let} predicate(s :Attributes) :Bool = string.equal(s  ``computeservice'')
  
  (* Bindung an den entfernten Dienst *)
  \k{let} computeservice = client.bind(:ServiceType  :Attributes   predicate)

  (* Benutzung des Dienstes *)
  \k{let} result = computeservice.compute(77)
\end{xple}
Durch Aufruf der Funktion {\em bind} wird ein passender Dienst über
den Auskunftsdienst ermittelt. Diese Auswahl findet über den Typ des
Dienstes ({\em Attributes}) und das angegebene Prädikat ({\em
  predicate}) statt. Zunächst werden aus der Menge der auf
Diensterbringerseite verfügbaren Dienste diejenigen ausgewählt, deren
Typ dem über {\em bind} angegebenen Typ entspricht. Dann wird für
jeden dieser Dienste die dazugehörige Attributfunktion zur Ermittlung
der Dienstattribute ausgewertet. Mit dem Resultatwert einer solchen
Auswertung wird die von {\em bind} übergebenen Prädikatsfunktion {\em
  predicate} aufgerufen. Ergibt eine solche Auswertung den boolschen
Wert {\em true}, so wird dieser Dienst an den Dienstnehmer übermittelt.

Auf die Realisierung der konkreten Übertragung der Objektdaten wird an
dieser Stelle nicht tiefer eingegangen.  Dort, wo Details der dafür
zuständigen Mechanismen notwendig sind, folgen weitere Erläuterungen.

\subsection{Threadmigration}
Die Migration von Tycoon-Threads bedient sich der im vorherigen Abschnitt
beschriebenen, entfernten Funktionsaufrufe. Auf der Senderseite wird
eine entfernte Funktion der Empfängerseite aufgerufen, die als
Parameter den zu übertragenen Thread erhält. Auf der Empfängerseite
wird dieser Thread entgegengenommen und erneut gestartet. Die
Migration von Threads wird wie folgt implementiert~\cite{BM96}:

Die Deklaration des Typs der zu übertragenden Datenobjekte und des Typs
der entfernten Funktion zur Datenübertragung findet im Modul {\em
  gate} statt, das von allen an Migrationsvorgängen beteiligten
Tycoon-Systemen importiert werden muß:

\begin{minipage}[t]{3.4in}
\begin{xple} 

\k{Let} Parameter(Data $<:$\k{Ok}) = \k{Tuple}
  \k{var} data :optional.T(Data)
  agent :thread.T(\k{Ok})
\k{end}
\end{xple}
\end{minipage}
\begin{minipage}[t]{2.5in}
  Ein Element des Typs {\em Parameter(Data)} wird auf das entfernte
  System übertragen. Es enthält den zu übertragenden Thread {\em agent}
  sowie ein Datenelement {\em data}, das die Anbindung des
  übertragenen Threads an den Adreßraum des Zielrechners ermöglicht.
\end{minipage}

\begin{minipage}[t]{3.4in}
\begin{xple}
\k{Let} T(Data $<:$\k{Ok}) $<:$\k{Ok} = \k{Tuple}
  transfer(param :Parameter(Data)) :\k{Ok}
\k{end}
\end{xple}
\end{minipage}
\begin{minipage}[t]{2.5in}
  Der parametrisierte Typ {\em T(Data)} des entfernten
  Funktionsaufrufs zur Thread-Übertragung ist der Servicetyp des
  entfernten Dienstes (vgl.\ Abschnitt~\ref{RPC}).
\end{minipage}
\vskip 0.5cm 
Für den  Migrationsvorgang steht die Funktion
{\em migrateTo} zur Verfügung. In dieser Funktion werden durch {\em
  thread.launch} ein Hilfsthread erzeugt und der zu migrierende Thread
suspendiert. Dieser Hilfsthread überträgt durch Aufruf der durch {\em
  site} gegebenen, entfernten Funktion {\em transfer} seinen
Erzeugerthread auf das Zielsystem~\cite{BM96}:
\begin{xple}
\k{let} migrateTo(Data $<:$\k{Ok}  site :T(Data)) :Data =
  \k{begin}
    \k{let} param :Parameter(Data) = \k{tuple}
      \k{let} \k{var} data = optional.nil(:Data)
      \k{let} agent = thread.self()
    \k{end}
    thread.launch(\k{fun}(self :thread.T(\k{Ok}))
      \k{begin}
        site.transfer(param)        (* Aufruf der entfernten Funktion *)
        thread.kill(param.agent)    
      \k{end})
    (* Dieser Teil wird bereits auf dem entfernten System ausgeführt *)
    optional.value(param.data) 
  \k{end}
\end{xple}
Zu beachten ist die Beendigung des {\em migrateTo } aufrufenden
Threads auf dem Ursprungssystem durch den Aufruf von {\em
  thread.kill}. Dies führt zur Beendigung des Threads im Sendersystem
und zum Abbau der dem Thread zugeordneten, flüchtigen Datenstrukturen
des Laufzeitsystems.

Der Aufruf der Funktion {\em optional.value(param.data)} gibt einen
Wert des entfernten Systems an den übertragenen Thread zurück.
Dadurch wird die Öffnung des Adreßraums des entfernten Systems für den
übertragenen Thread erreicht. Der Wert {\em param.data} wird durch die
im folgenden erläuterte Technik des dynamischen Bindens von
Tycoon-Objekten ermittelt:

Zunächst lautet die Implementation der auf dem Zielsystem
ausgeführten, entfernten Funktion {\em transfer}  wie folgt:
\begin{xple}
\k{let} data() = \k{begin} (* Rückgabe eines Werts des Zielsystems *) \k{end}
\k{let} rpc = \k{tuple}
  \k{let} transfer(param :Parameter(Data)) =
    \k{begin}
      param.data := optional.new(data())
      thread.run(param.agent)
    \k{end}
  \k{end}
%server.register(\ldots rpc)
\end{xple}
Die Funktion {\em transfer} startet den vom Sendersystem übertragenen
Thread erneut. Der durch die Auswertung der Funktion {\em data()}
erhaltene Wert des Zielsystems wird von der Funktion {\em migrateTo}
als Ergebniswert zurückgegeben. Da diese Auswertung der Funktion {\em
  data()} auf dem Zielsystem stattfindet und den Wert eines Objekts
des Zielsystems zurückgibt, erhält der übertragene Thread Zugriff auf
Objekte des Zielsystems: Der Adreßbereich des übertragenen Threads ist
um Objekte des Zielsystems erweitert worden.

Die konkrete Migration eines Threads vollzieht sich dann in zwei Schritten.
Zuerst wird die Ziel\-adres\-se des entfernten Systems festgelegt. Dann
erfolgt der eigentliche Migrationsvorgang durch Aufruf der Funktion
{\em migrateTo}:
\begin{xple}
\k{let} site = client.bind(\ldots)
\k{let} data = migrateTo(site)
\end{xple}

Auf der Seite des Dienstnehmers, des Senders des Threads, wird
zunächst durch Aufruf der Funktion {\em bind} die Zieladresse für die
Migration durch Binden an einen Dienst des Zielrechners festgelegt.
Die Funktionalität dieses Dienstes besteht, wie beschrieben, in der
Entgegennahme und dem Starten des übertragenen, passiven
(suspendierten) Thread-Objekts.

Es ist darauf hinzuweisen, daß die Implementation von Thread-Migration
lediglich die direkte Übertragung eines Threads unterstützt. Befinden
sich weitere Threads im transitiven oder direkten Sichtbarkeitsbereich
des migrierenden Threads (siehe Abschnitt~\ref{Minref}), so liegt die
Verantwortung für die korrekte Übertragung dieser Threads bei dem
Programmierer des zu migrierenden Threads.  Insbesondere ist ein
Benutzer der Mechanismen zur Thread-Migration für die Suspendierung
referenzierter Threads zum Abbau flüchtiger Datenstrukturen des
Laufzeitsystems vor der Übertragung und für die erneute Aktivierung
dieser Threads auf dem Zielsystem selbst verantwortlich.  Das Beispiel
in Abbildung~\ref{Agentmig} (Seite~\pageref{Agentmig}) zeigt, wie eine
Migration mehrerer, zum migrierenden Thread lokaler Threads, zu
implementieren ist:

\begin{figure}
\begin{xple}
(* Implementation der Threadübertragung *)
\k{let} agent(site :ServiceType) =
  \k{begin}
    (* Deklarationen *)
    \k{let} funcA(self :thread.T(\k{Ok})) = 
      \k{begin}
        \ldots   (* Arbeitsteil der Funktion funcA *)
      \k{end}

    \k{let} funcB(self :thread.T(\k{Ok})) = 
      \k{begin}
        \ldots   (* Arbeitsteil der Funktion funcB *)
      \k{end}

    (* Starten lokaler Threads *)
    \k{let} threadA = thread.fork(funcA)
    \k{let} threadB = thread.fork(funcB)

    (* Weitere Kodeabschnitte von {\em agent} *)
    \ldots
    (* Suspendierung der lokalen Threads vor der Migration *)
    thread.suspend(threadA)
    thread.suspend(threadB)
    
    (* Durchführung der Migration *)
    \k{let} data = migrateTo(site) 

    (* Die weiteren Abschnitte werden bereits auf dem entfernten System ausgeführt *)
    thread.run(threadA)    (* Neuaktivierung der lokalen Threads *)
    thread.run(threadB) 

    (* Weitere Kodeabschnitte *)
  \k{end}
     
(* Festlegung der Zieladresse *)
\k{let} site = client.bind(\ldots)

(* Starten des Threads für die Funktion {\em agent} *)
thread.fork(\k{fun}(self :thread.T(\k{Ok})) agent(site))
\end{xple}
\caption{Migration mehrerer Threads}
\label{Agentmig}
\end{figure}
Alle Threads, die mit auf das entfernte System migrieren sollen, sind
von dem die Migration durchführenden Thread vor der Übertragung zu
suspendieren.  Die Aktivierung des migrierenden Hauptthreads ({\em
  agent}) wird auf der Empfängerseite durch die Funktion {\em
  transfer} gewährleistet. Alle weiteren Threads sind durch die
Funktion {\em agent} auf der Empfängerseite erneut zu aktivieren. Ein
Beenden der lokalen Threads durch {\em thread.kill} ist nicht
notwendig, da diese aufgrund ihrer lokalen Sichtbarkeit nicht außerhalb
von {\em agent} referenzierbar sind. 
\newpage
\section{Die Minimierung transitiver referentieller Abhängigkeiten}
\label{Minref}
Ein wichtiger Begriff im Zusammenhang mit der Mobilität von
Tycoon-Objekten ist der mit diesen Objekten verbundene, transitive
Sichtbarkeitsbereich.  Hierunter ist die Menge der durch ein Objekt
transitiv erreichbaren Objekte zu verstehen. Ein Tycoon-Objekt hat im
allgemeinen Referenzen auf weitere Tycoon-Objekte. Im linken Teil  der
Abbildung~\ref{deepcopy} sind Referenzen zwischen einigen
Tycoon-Objekten verzeichnet.  Beispielsweise besteht die Menge der
durch das Objekt {\em info} transitiv erreichbaren Objekte aus {\em
  database}, {\em count}, {\em print} und {\em int}. Das Objekt {\em
  statistic} gehört dagegen nicht zur Menge der von {\em info}
erreichbaren Objekte. Da bei einem Migrationsvorgang die referentielle
Integrität zwischen Tycoon-Objekten erhalten bleiben muß, werden auch
alle von dem zu übertragenen Objekt referenzierten Objekte übertragen.
Dieser Kopiervorgang ({\em Tiefenkopie, deep copy}) überträgt alle
durch eine Objekt transitiv erreichbaren, weiteren Objekte in den
entfernten Objektspeicher.  Ein Nachteil dieses Verfahrens besteht in
dem Umfang der zu übertragenen Datenmengen. Werden zum Beispiel durch
einen zu übertragenen Thread eine umfangreiche Datenbank und mehrere
Module des Tycoon-System referenziert, müssen diese Objekte ebenfalls
übertragen werden. Dies führt zu erheblichen Datenmengen, die den
Nutzen von Migrationsvorgängen erheblich reduzieren. Im ungünstigsten
Fall kann ein Migrationsvorgang zur Übertragung des gesamten
Objektspeicherinhalts führen.

\begin{figure}
\begin{center}\leavevmode
  \epsfxsize=0.8\textwidth \epsfbox{pictures/deepcopy.ps}
\end{center}
\caption{Übertragung eines Objekts durch Tiefenkopie}
\label{deepcopy}
\end{figure}

Die Implementation der Objektübertragung und Thread-Migration führt
zur Mitübertragung aller durch ein Objekt transitiv erreichbarer
Objekte. Insbesondere werden auch alle transitiv erreichbaren Threads
übertragen. Wie in Abschnitt~\ref{Mobil} angemerkt, werden diese
Threads durch die Funktion zur Thread-Migration ({\em migrateTo})
nicht berücksichtigt. Der Benutzer dieser Funktion ist für die
Verwaltung dieser Threads  verantwortlich.

Durch Synchronisationsmechanismen ist eine weitere Verschärfung der
mit der Tiefenkopie verbundenen Probleme möglich. Threads, die
untereinander keine Referenzen besitzen, können durch
Synchronisationsmechanismen Referenzen aufeinander erhalten. Dieses
Problem tritt immer dann auf, wenn Threads, die Referenzen auf eine
Variable eines Synchronisationsmechanismus besitzen, einen
Migrationsvorgang einleiten. Ein einfaches Beispiel macht die
Problematik deutlich:
\begin{xple}
\k{let} m = mutex.new()
\k{let} funcA(self :thread.T(\k{Ok})) = \k{begin} 
  mutex.lock(m) 
  \ldots 
  mutex.unlock(m) 
  \k{let} site = \ldots
  \k{let} data = migrateTo(site)
\k{end}

\k{let} funcB(self :thread.T(\k{Ok})) = 
  \k{begin} 
     mutex.lock(m) 
    \ldots 
     mutex.unlock(m) 
  \k{end}

\k{let} threadA = thread.fork(funcA) 
\k{let} threadB = thread.fork(funcB)
\end{xple}
Auf Synchronisationsmechanismen wartende Threads werden in einer
Warteschlange innerhalb der Synchronisationsvariablen gespeichert. Ein
Migrationsvorgang führt dann zur Mitübertragung dieser Threads. Im
obigen Beispiel führt daher der Migrationsvorgang von {\em threadA}
zur Mitübertragung von {\em threadB} und aller von {\em threadB}
transitiv erreichbaren Objekte, wenn {\em threadB} sich zum Zeitpunkt
der Migration auf der Warteschlange des Mutex {\em m} befindet.
Derartige Referenzen können unter anderem auch durch Benutzung von
Tycoon-Modulen entstehen, deren interne Datenstrukturen durch
Synchronisationsmechanismen abgesichert sind.  Ein Verfahren zur
Minimierung dieser transitiven Referenzen wird im folgenden
beschrieben.

%\subsection{Ubiquitäre Ressourcen}
%\label{Ubiq}
Um eine Übertragung von Tycoon-Objekten in entfernte Objektspeicher
ohne die Mit\-über\-tra\-gung großer Mengen transitiv referenzierter
Objekte zu ermöglichen, bietet das Tycoon-System ein Verfahren zur
Minimierung derartiger Referenzen an. Ein wesentlicher Gesichtspunkt
bei diesen Verfahren besteht in der Beobachtung, daß typische
Tycoon-Systeme zueinander ähnlich aufgebaut sind. So existiert eine
große Menge von Modulen, deren Existenz in jedem Tycoon-System
vorausgesetzt werden kann. Derartige Module werden als allgegenwärtig
({\em ubiquitär}) bezeichnet. Das Tycoon-Modul {\em atomic} gestattet
die Kennzeichnung derartiger ubiquitärer Module~\cite{Pour96}. 
Diese Kennzeichnung ist jedoch nicht auf Module beschränkt, sondern
ermöglicht die Deklaration beliebiger Tycoon-Objekte als ubiquitäre
Ressourcen.  Die konkrete Übertragung von Objekten zwischen
Tycoon-Systemen ist so implementiert, daß ubiquitäre Ressourcen nicht
mit\-über\-tra\-gen werden.  Statt dessen wird der Objektgraph eines
zu übertragenen Objekts, der die Menge aller durch ein Tycoon-Objekt
transitiv erreichbaren Objekte enthält, bei als ubiquitär
gekennzeichneten Objekten abgeschnitten und durch eine symbolische
Referenz ersetzt.  Nach der Über\-tra\-gung wird dieser Objektgraph
durch einen  Bindevorgang~\cite{Pour96} wieder
vervollständigt, symbolische Referenzen ubiquitärer Objekte werden
durch die entsprechenden Objektgraphen auf dem Empfängersystem
ersetzt.
\begin{figure}
\begin{center}\leavevmode
  \epsfxsize=0.8\textwidth \epsfbox{pictures/dynlink.ps}
\end{center}
\caption{Rebinden ubiquitärer Objekte}
\label{rebind}
\end{figure}
Abbildung~\ref{rebind} zeigt eine derartige Übertragung: Das
Tycoon-Objekt {\em info} ist einen anderen Objektspeicher zu
übertragen. Die Objekte {\em print} und {\em database} sind als
ubiquitär gekennzeichnet. Dadurch ist lediglich die Übertragung des
Objekts {\em info} notwendig. Nach der Übertragung wird durch
dynamisches Rebinden der Objektgraph von {\em info} wieder
vervollständigt.


Eine unerwünschte, indirekte Übertragung von Threads durch in
ubiquitären Objekten benutzte Synchronisationsmechanismen ist aus den
oben genannten Gründen ausgeschlossen.  Es ist jedoch anzumerken, daß
durch die Migration von Threads, die mit ubiquitären Objekten in
Synchronisationsbeziehungen stehen, weitere Probleme durch
Deaktivierung und Neuaktivierung dieser Threads entstehen können
(siehe folgenden Abschnitt).

Bei der Programmierung migrierender Threads ist immer zu beachten, daß
zusätzliche transitive Referenzen durch Synchronisationsvorgänge mit
nicht ubiquitären Objekten enstehen können.

\section{Zustandswechsel migrierender Threads}
\label{Zustandswechsel}
Migrierende Tycoon-Threads sind für die Migration weiterer Threads aus
ihrem Sichtbarkeitsbereich verantwortlich. Aktive Threads müssen von
dem den Migrationsvorgang vollziehenden Thread vor der Migration
deaktiviert werden. Nach dem Migrationsvorgang sind derartige Threads
erneut zu aktivieren. Hierbei ist zu beachten, daß eine einfache
Suspendierung und erneute Aktivierung aller zu migrierenden Threads
nicht ausreichend ist. Alle von einem Thread während des
Migrationsvorgangs verwalteten Threads können sich zum Zeitpunkt der
Übertragung in allen Threadzuständen befinden (vgl.
Abbildung~\ref{tstates}, Seite~\pageref{tstates}). Der Zustand eines
Threads wird jedoch bei Migrationsvorgängen geändert:
\begin{itemize}
\item Insbesondere werden Threads auch aufgrund von Migrationsvorgängen
  suspendiert und beendet. Die Beendigung zu übertragender
  Threads auf dem Ursprungssystem kann daher zu Verklemmungen führen,
  wenn diese Threads Synchronisationsvariablen akquiriert haben, auf
  die weitere Threads warten. Diese Situation kann beispielsweise
  entstehen, wenn zu migrierende Threads Synchronisationsmechanismen
  ubiquitärer Ressourcen halten.
\item Bei einem Migrationsvorgang wird der aktiv migrierende Thread
  auf der Empfängerseite neu gestartet.  Alle weiteren, migrierenden
  Threads müssen nach der Migration auf das entfernte System von dem
  aktiv migrierenden Thread erneut gestartet werden.  Dieses erneute
  Aktivieren muß von einer Aktivierung nach Zuteilung einer
  Synchronisationsvariablen unterschieden werden. Erfolgt diese
  Unterscheidung nicht, so werden blockierte
  Synchronisationsmechanismen durch diese inkorrekte Aktivierung
  wartender Threads fälschlicherweise als verfügbar betrachtet.
\end{itemize}
Die Probleme, die sich aus der Beendigung von Threads ergeben, die
Synchronisationsmechanismen ubiquitärer Ressourcen halten, kann
derzeit nur durch eine explizite Berücksichtigung bei der
Programmierung von Thread-Migration gelöst werden. Es ist zu
verhindern, daß sich ein zu migrierender Thread in einem internen,
kritischen Abschnitt eines ubiquitären Objekts befindet, da nach einem
Migrationsvorgang eine neue, automatische Akquisition des kritischen
Abschnitts nicht gewährleistet werden kann.

%Allerdings ist anzumerken, daß diese Problematik lediglich Module
%betrifft, in denen modulinterne Zustandswechsel vorkommen, die durch
%Synchronisationsmechanismen zu schützen sind.

Eine mögliche Lösung für obiges Problem ist die Einführung von
Netzwerkreferenzen für Tycoon-Objekte. Bei einem Migrationsvorgang
werden Referenzen auf immobile (ubiquitäre) Objekte durch
Netzwerkreferenzen auf dieses Objekt ersetzt. Derartige Referenzen
ermöglichen einen transparenten Zugriff auf nicht migrationsfähige
Objekte aus entfernten Objektspeichern.  Diese Technik wird
beispielsweise in der Programmiersprache Obliq
eingesetzt~\cite{Card94}.

%Eine weitere Möglichkeit besteht in dem Einsatz von
%Sicherungspunkten. Derartige Sicherungspunkte 

Der Zustand eines Threads muß nach Abschluß eines Migrationsvorgangs
dem Zustand im ursprünglichen System entsprechen.  Um dies zu
erreichen ist die Einführung zusätzlicher Hilfszustände für Threads
notwendig. Die in der Abbildung~\ref{tstates} angeführten Zustände
werden um die Zustände {\em mig\_blocking}, {\em mig\_running} und
{\em mig\_suspended} erweitert.  Abbildung~\ref{newtstates} zeigt die
neuen Zustandsübergänge für Threads im Tycoon-System.
\begin{figure}
\begin{center}\leavevmode
  \epsfxsize=0.6\textwidth \epsfbox{pictures/newthread-states.eps}
\end{center}
\caption{Zustandsübergänge unter Berücksichtung von Migration}
\label{newtstates}
\end{figure}
Das Modul {\em thread} wird um zusätzliche Funktionen zur Steuerung
migrierender Threads erweitert. Im einzelnen werden die Funktionen
\begin{xple}
migrate(t :thread.T(\k{Ok})) :\k{Ok}

activate(t :thread.T(\k{Ok})) :\k{Ok}
\end{xple}
neu eingeführt. Die Funktion {\em migrate} überführt den angegebenen
Thread abhängig von seinem ursprünglichen Zustand in einen neuen
Zustand. Falls der Thread vor Ausführung von {\em migrate} im Zustand
{\em running} ist, wird der Thread deaktiviert und in den Zustand {\em
  mig\_running} überführt. Dieser  entspricht effektiv dem
alten Zustand {\em suspended}, alle flüchtigen Datenstrukturen des
Laufzeitsystems sind abgebaut. Jedoch führen nachfolgende Aufrufe der
Funktion {\em suspend} zur Überführung in den Zustand {\em
  mig\_suspended}. Analog wirken sich Aufrufe der in
Abbildung~\ref{newtstates} angegebenen Funktionen auf die weiteren,
neuen Zustände aus.  In keinem Fall wird ein Thread erneut aktiviert,
mit der Ausnahme der Aktivierung mittels {\em activate} durch den die
Migration veranlassenden Hauptthread. Dadurch bleibt der im
Sendersystem vorhandene Zustand eines Threads auch nach Migration
erhalten. 
%Dadurch wird eine nicht zulässige Aktivierung  auf
%Synchronisationsmechanismen wartender Threads verhindert.









% Local Variables:
% TeX-master: "da"
% TeX-parse-self: t
% TeX-auto-save: t
% End:
% LocalWords:  register server ServiceType Attributes attributFunction rpc
% LocalWords:  searchFunktion
