Einleitung
Eine wichtige Aufgabe bei der Steuerung verteilter Systeme besteht darin, die Konsistenz der gespeicherten Objekte zu erhalten, insbesondere wenn Benutzer zeitgleich auf dieselben Objekte zugreifen. Die Konsistenzerhaltung betrifft dabei zwei Bereiche: Zum einen dürfen mögliche Fehler, wie zum Beispiel der Ausfall eines Rechners oder einer Leitung, nicht zu einem inkonsistenten Zustand der Objekte führen. Zum anderen dürfen auch nebenläufige Berechnungen unterschiedlicher Benutzer keine störenden Auswirkungen aufeinander haben. Transaktionskonzepte haben sich ausgehend von Datenbank-Anwendungen als Mittel der Fehlerbehandlung und der Nebenläufigkeitskontrolle durchgesetzt. In diesen Konzepten finden die Berechnungen einzelner Benutzer jeweils innerhalb von Transaktionen statt, für die systemseitig bestimmte Eigenschaften zugesichert werden. Das klassische Transaktionskonzept hat dabei zum Ziel, jede Transaktion soweit zu isolieren, daß sie andere Transaktionen und auch deren Abbrüche nicht bemerkt. Die Isolation basiert auf dem Konsistenzkriterium der Serialisierbarkeit, welches fordert, daß nebenläufige Transaktionen stets denselben Effekt haben müssen, den sie auch bei serieller Ausführung hätten.
Auch wenn klassische Transaktionen ein ausreichendes Konzept
darstellen, um viele Datenbankanwendungen wie zum Beispiel
Buchungssysteme zu realisieren, zeigt sich schnell, daß sie aufgrund
der geforderten Isolation von Berechnungen ungeeignet für eine
Unterstützung von komplexeren Abläufen sind: In vielen Bereichen gibt
es Beziehungen zwischen den Berechnungen der einzelnen Anwender.
Beispielsweise betraut ein Anwender einen anderen mit der Durchführung
einer Teilaufgabe oder mehrere Benutzer führen eine gemeinsame Aufgabe
durch und treffen zu diesem Zweck auch gemeinsam Entscheidungen.
Diese Beziehungen implizieren in der Regel einen Informationsfluß
zwischen den Partnern, da oft Zwischenergebnisse ausgetauscht werden
müssen. Zwischen Transaktionen findet dieser Informationsfluß dadurch
statt, daß eine Transaktion Objektzustände liest, die eine andere
Transaktion geschrieben hat. Eine Transaktionsverwaltung muß also in
der Lage sein, diese Beziehungen zu modellieren und in bestimmten
Situationen Informationsfluß zwischen laufenden Transaktionen zu
erlauben. Die Zielsetzung des klassischen Transaktionskonzepts liegt
aber im direkten Gegensatz dazu, weil hier mit der Isolation von
Transaktionen jede Art von Informationsfluß zwischen laufenden
Transaktionen verhindert werden soll.
Daher wurden erweiterte Transaktionskonzepte entwickelt, die Beziehungen zwischen einzelnen Transaktionen modellieren können. Diese Konzepte haben in der Regel sowohl die Mechanismen zur Fehlerbehandlung als auch die zur Nebenläufigkeitskontrolle danach ausgerichtet, eine bestimmte Art von Beziehungen zwischen Transaktionen zu modellieren. Die Anforderungen, die die Modellierung von Beziehungen an ein Transaktionskonzept stellt, betreffen meist nur die Nebenläufigkeitskontrolle, während die Anforderungen an die Fehlerbehandlung unabhängig von den jeweiligen Beziehungen zwischen den Transaktionen sind. Die starke Verflechtung der Mechanismen zur Fehlerbehandlung und zur Nebenläufigkeitskontrolle bei den erweiterten Transaktionskonzepten führt aber dazu, daß sich der Benutzer bei der Wahl eines Transaktionskonzepts zur Unterstützung von bestimmten Beziehungen auch auf vorgegebene Mechanismen zur Fehlerbehandlung festlegt. Diese Mechanismen stellen im Vergleich zu klassischen Transaktionen oft weitergehende Anforderungen an die Applikationen oder schränken deren zulässiges Verhalten stark ein.
Das in [Nett 1991] eingeführte Konzept der dynamischen Aktionen wählt statt dessen einen flexibleren Ansatz: Im Gegensatz zu den Transaktionskonzepten sind hier Fehlerbehandlung und Nebenläufigkeitskontrolle orthogonal zueinander und es kann daher eine korrekte Fehlerbehandlung sichergestellt werden, ohne bestimmte Eigenschaften der Nebenläufigkeitskontrolle wie beispielsweise eine Isolation der dynamischen Aktionen fordern zu müssen. Im Gegensatz zu den erweiterten Transaktionskonzepten führt die zur Unterstützung komplexerer Anwendungen notwendige Aufgabe der Isolation nicht dazu, daß für eine korrekte Fehlerbehandlung zusätzliche Anforderungen an die Applikation entstehen. Die Orthogonalität macht es somit möglich, bei sichergestellter Fehlerbehandlung durch unterschiedliche Konzepte zur Nebenläufigkeitskontrolle beliebige Arten von Beziehungen zwischen dynamischen Aktionen zu modellieren.
In dieser Arbeit wird ein Konzept auf Basis der dynamischen Aktionen vorgestellt, das die wichtigsten Arten von Beziehungen zwischen den Berechnungen unterschiedlicher Benutzer modellieren kann. Dabei treten in der praktischen Anwendung oft unterschiedliche Beziehungstypen innerhalb einer Anwendung auf, die sich fast alle zwei Hauptprinzipien zuordnen lassen: dem Kooperationsprinzip und dem Auftragsprinzip.
Oft wird eine Aufgabe nicht von einem einzelnen Anwender gelöst, sondern an der Lösung sind mehrere Anwender beteiligt. Die Anwender teilen beispielsweise die Aufgabe in einzelne Abschnitte auf, die der jeweilige Anwender bearbeitet, und anschließend wird aus den Abschnitten gemeinsam die Gesamtlösung erstellt.
Ein Beispiel für das Kooperationsprinzip ist das Erstellen eines Textes durch zwei Autoren, wobei Autor A Einleitung und Schluß und Autor B den Mittelteil schreibt. Nachdem Autor A die Einleitung geschrieben hat, soll Autor B sie lesen können, um seinen Mittelteil darauf abzustimmen; das gleiche gilt auch umgekehrt, wenn Autor A zur Erstellung des Schlusses den Mittelteil von Autor B kennen muß. Nachdem alle Teile des Textes geschrieben wurden, sollen beide Autoren, nachdem sie jeweils den gesamten Text gelesen und gegebenenfalls überarbeitet haben, den Text als endgültige Fassung akzeptieren.
Wie dieses Beispiel verdeutlicht, bedeutet das Kooperationsprinzip folgendes: Zwischen den Berechnungen kooperierender Benutzer findet mehrfach Informationsfluß in beliebige Richtungen statt, allerdings gibt es auch Zeiten, in denen kein Informationsfluß möglich sein soll. Autor B soll im obigen Beispiel die Einleitung nicht während ihres gesamten Entstehens sehen, sondern nur dann, wenn der Autor A sie gezielt zur Verfügung stellt. Betrachtet man größere Systeme, wird außerdem deutlich, daß es möglich sein muß, den Informationsfluß auf den Kreis der Kooperationspartner zu beschränken. Falls die späteren Leser des Textes auch Zugriff auf den Objektspeicher haben, muß das System sie daran hindern, Zwischenversionen zu lesen, die nur für den Informationsfluß zwischen den Autoren gedacht sind. Die Leser dürfen den Text erst lesen, nachdem dieser am Ende von beiden Autoren akzeptiert wurde.
Eine weitere sehr häufig auftretende Beziehung unter Anwendern ist die zwischen Auftraggeber und Auftragnehmer. Dabei beauftragt ein Benutzer einen anderen mit der Lösung einer Teilaufgabe, die dieser eigenständig lösen kann. Der Auftraggeber benutzt anschließend die Ergebnisse des Auftragnehmers, um seine eigene Aufgabe zu erledigen.
Im Beispiel der Texterstellung ist die Einschaltung eines Übersetzungsbüros eine Anwendung des Auftragsprinzips: Der Autor schreibt einen Text in Deutsch, übergibt ihn dem Übersetzungbüro und bekommt einen englischen Text zurück. Der Autor kann anschließend alleine entscheiden, ob er den übersetzten Text benutzt oder verwirft und beispielsweise eine Übersetzung bei einem anderen Büro in Auftrag gibt.
Im Gegensatz zum Kooperationsprinzip ist beim Auftragsprinzip die Beziehung zwischen den Partnern nicht gleichberechtigt: Der Auftragnehmer bekommt eine Aufgabe, die er zu erfüllen hat. Dabei benötigt er keine weiteren Informationen über den Kontext dieser Aufgabe und hat auch keine Möglichkeit der Einflußnahme auf den Auftraggeber. Nachdem der Auftragnehmer die Ergebnisse an den Auftraggeber zurückgegeben hat, liegt die Kontrolle über diese Ergebnisse alleine beim Auftraggeber. Es findet also beim Erteilen des Auftrags einmal ein Informationsfluß von Auftraggeber zum Auftragnehmer statt und bei Beendigung des Auftrags erfolgt ein Informationsfluß in die Gegenrichtung.
Eine andere wichtige Eigenschaft des Auftragsprinzips besteht darin, daß grundsätzlich die Existenz des Auftragnehmers vor fremden Anwendern verborgen werden soll. Im Übersetzungsbeispiel ist es beispielsweise nur wichtig, daß der Autor einen englischen Text abliefert. Ob er den Text selbst in Englisch schreibt oder einen Übersetzer beauftragt, ist für den späteren Leser unerheblich. Insbesondere darf niemand außer dem Autor den vom Übersetzungsbüro zurückgegebenen englischen Text sehen, da der Autor schließlich noch Änderungen am Text machen oder ihn ganz verwerfen könnte und nur die vom Autor endgültig akzeptierte Version für die Allgemeinheit gedacht ist. Selbst wenn das Übersetzungsbüro seine Tätigkeit abbricht und den Auftrag unerledigt zurückgibt, muß dieses nicht unbedingt das Scheitern des Auftraggebers nach sich ziehen, da der Autor seine Aufgabe immer noch erfüllen könnte, indem er alternativ ein anderes Büro beauftragt. Der Abbruch des Auftragnehmers hätte dann keinen Effekt auf das Gesamtergebnis.
Es existieren bereits erweiterte Transaktionskonzepte, die entweder das Kooperations- oder das Auftragsprinzip durchsetzen. Die Konzepte zur Realisierung des Kooperationsprinzips basieren meistens auf den offen geschachtelten Transaktionen, während das Auftragsprinzip meistens durch Konzepte realisiert wird, die auf geschlossen geschachtelten Transaktionen basieren. In der Praxis kommen allerdings oft beide Prinzipien kombiniert vor. Im Texterstellungsbeispiel zum Kooperationsprinzip könnte beispielsweise Autor B seinen Text durch das Übersetzungbüro in das Englische übersetzen lassen. Außerdem könnten im Übersetzungsbüro mehrere Mitarbeiter kooperativ an der Übersetzung arbeiten. Die existierenden erweiterten Transaktionskonzepte eignen sich aufgrund der engen Verflechtung von Fehlerbehandlung und Nebenläufigkeitskontrolle nicht als Basis für ein Konzept, das beide Prinzipien integriert.
Da beide Prinzipien sich auf die Nebenläufigkeitskontrolle beziehen, bieten dynamische Aktionen durch die Orthogonalität von Fehlerbehandlung und Nebenläufigkeitskontrolle einen sinnvollen Rahmen für die Entwicklung eines Konzepts, welches diese beiden Prinzipien integriert: Die existierenden Mechanismen zur Fehlerbehandlung können ohne Änderung genutzt werden, so daß sich die Integration auf den Bereich der Nebenläufigkeitskontrolle beschränkt. Dynamische Aktionen unterstützen bereits Nebenläufigkeitskonzepte zur Realisierung des Auftragsprinzip durch Schachtelung (siehe [Nett 1991], [Nett, Weiler 1994]) und des Kooperationsprinzips (siehe [Mock 1994]), die zu einem Integrationskonzept kombiniert werden können. Eine direkte Kombination der Konzepte ist aber nicht möglich, da beide Prinzipien teilweise entgegengesetzte Anforderungen an die Nebenläufigkeitskontrolle stellen. Statt dessen werden Mechanismen benötigt, die abhängig von der Anwendungssemantik in bestimmten Situationen das Auftrags- oder das Kooperationsprinzip durchsetzen. Die Entwicklung eines Integrationskonzepts, das diese Anforderungen erfüllt, ist Gegenstand dieser Arbeit.
In dieser Arbeit wird auf der Basis von dynamischen Aktionen das Konzept der geschachtelten dynamischen Aktionen für kooperative Anwendungen zur Kombination von Auftrags- und Kooperationsprinzip entwickelt. Es integriert die geschachtelten dynamischen Aktionen und die dynamischen Aktionen für kooperative Anwendungen. Das Integrationskonzept wird auch unter dem Gesichtspunkt entwickelt, eine möglichst gute Verträglichkeit mit den zugrundeliegenden Konzepten zu bieten. Diese Verträglichkeit wird nachgewiesen, indem das Integrationskonzept in ein formales Modell eingebettet wird, welches bereits für die dynamischen Aktionen für kooperative Anwendungen entwickelt wurde. Neben der Verträglichkeit werden so auch weitere Eigenschaften des Integrationskonzepts formal bewiesen.
Als wichtiger Bestandteil des Integrationskonzepts wird in dieser Arbeit der Mechanismus der Objektkontrolle eingeführt. Mit diesem Mechanismus können dynamische Aktionen die Sichtbarkeit von Objektänderungen individuell für einzelne Objekte steuern und dadurch Zugriffe durch andere dynamische Aktionen auf die Objekte kontrollieren. Die Objektkontrolle stellt somit ein adäquates Mittel dar, um sowohl das Auftrags- als auch das Kooperationsprinzip zu unterstützen. Sie bietet den Applikationen die Möglichkeit, in konkreten Situationen abhängig von ihrer Semantik festzulegen, welches der beiden Prinzipien durchgesetzt werden soll.
Zur Realisierung des Integrationskonzepts wird das kooperative Sperrverfahren für geschachtelte dynamische Aktionen entwickelt. Analog zur Erstellung des Konzepts werden hier das geschachtelte Sperrverfahren und das flache kooperative Sperrverfahren, die jeweils eines der beiden zugrundeliegenden Konzepte realisieren, unter Berücksichtigung einer bestmöglichen Verträglichkeit integriert.
Das kooperative Sperrverfahren wird durch eine Systemkomponente zur Sperrenverwaltung durchgesetzt, welche anhand von Regeln überprüft, ob die Anforderung oder Freigabe einer Sperre durch eine dynamische Aktion zulässig ist. In dieser Arbeit werden die für eine solche Überprüfung benötigten Algorithmen und Datenstrukturen detailiert beschrieben.
Schließlich wird die Systemkomponente zur Sperrenverwaltung zum Nachweis der tatsächlichen Einsetzbarkeit des Sperrverfahrens implementiert. Neben der beschriebenen Einbindung in das existierende verteilte Aktionssystem für dynamische Aktionen erfolgt zur Demonstration des kooperativen Sperrverfahrens eine Implementierung als eigenständige Komponente zur Nebenläufigkeitskontrolle mit interaktiver Nutzerschnittstelle.
Zunächst werden in Kapitel 2 die am weitesten verbreiteten Konzepte zur Realisierung von Auftrags- und Kooperationsprinzip beschrieben und diskutiert. Außerdem erfolgt in diesem Kapitel eine Einführung in die dynamischen Aktionen, wobei insbesondere die beiden Nebenläufigkeitskonzepte zur Realisierung des Auftrags- bzw. des Kooperationsprinzips genauer beschrieben werden. In Kapitel 3 werden das Integrationskonzept und das zugehörige kooperative Sperrverfahren entwickelt. Die Einbettung in ein formales Modell und der formale Nachweis der Verträglichkeit mit den zugrundeliegenden Konzepten folgt in Kapitel 4. Kapitel 5 beschreibt die Algorithmen und Datenstrukturen zur Durchsetzung des Sperrverfahrens und Kapitel 6 die Implementierung der Sperrenverwaltung. Die Arbeit schließt in Kapitel 7 mit einer Zusammenfassung und einem Ausblick.