1 · Der Beginn der „Modern Computer-Era“ ist um das Jahr 1945 herum anzusiedeln. Typisch für die Zeit waren (nach heutigen Maßstäben gerechnet) große und teure Computer,

- 1 -

- 2 -

1 Einführung in

Verteilte Systeme

Für den Begriff des Verteilten Systems kann man in der Literatur eine ganze Reiheunterschiedlicher Interpretationen finden. Das Verständnis davon, was man sich untereinem Verteilten System vorzustellen hat, ist historisch gewachsen und unterliegt nochheute einem beständigen Wandel. In [Tan92] findet sich auf Seite 364 der Hinweis,man habe es immer dann mit einem Verteilten System zu tun, falls „multiple intercon-nected CPU´s work together“. Dem gegenüber ist auf Seite 382 die Rede von einemVerteilten System als „collection of machines that do not have shared memory“.

Im folgenden sollen Verteilte Systeme in ihrer allgemeinsten Form betrachtet wer-den. Darunter fallen alle Arten von Client-/Server-Systemen sowie Multiprozessorsy-steme, d.h. Systeme, welche aus Knoten bestehen, die selbst Uniprozessor oder Multi-prozessor sein können. [Spa94] entnimmt man folgende Definitionen (S.86):

Ein Verteiltes System ist ein System mit räumlich verteilten Komponenten, die kei-nen gemeinsamen Speicher benutzen und einer dezentralen Administration unter-stellt sind. Zur Ausführung gemeinsamer Ziele ist eine Kooperation der Kompo-nenten möglich. Werden von diesen Komponenten Dienste angeboten und angebo-tene Dienste genutzt, so entsteht ein Client/Server-System, im Falle einer zusätzli-chen zentralen Dienstvermittlung ein Tradingsystem.

Die Einordnung Verteilter Systeme in den Kontext des OSI-Referenzmodells ist dabeinicht unproblematisch. Generell kann jedoch gesagt werden, daß Verteilte Systeme imwesentlichen Aspekte der oberen Schichten des Referenzmodells betreffen. Im Gegen-satz zu einer Grundlagenvorlesung aus dem Bereich „Datenkommunikation“, welchesich im wesentlichen mit den unteren OSI-Schichten befaßt, werden daher im folgen-den verstärkt Konzepte der oberen drei Schichten behandelt.

Verteilte Systeme 1. Einführung in Verteilte Systeme

- 3 -

1.1 Historie Verteilter Systeme

Der Beginn der „Modern Computer-Era“ ist um das Jahr 1945 herum anzusiedeln.Typisch für die Zeit waren (nach heutigen Maßstäben gerechnet) große und teureComputer, aufgebaut in der klassischen von Neumann-Architektur. In einem Unter-nehmen waren nur wenige Computer vorhanden, die vollständig voneinander unab-hängig arbeiteten (zentraler Ansatz). Aus dieser Zeit stammt eine Grundregel, welcheals Grosch’s Gesetz bekannt geworden ist. Sie besagt, daß sich die Rechenleistungeiner CPU proportional zum Quadrat ihres Preises verhält. Investiert man also dasdoppelte in einen Rechner, so kann man nach Grosch’s Gesetz das vierfache an Lei-stung erwarten. Mit der Entwicklung der Mikroprozessortechnologie verlor das Gesetzvon Grosch seine Gültigkeit!

Abb. 1.1:Leistungsexplosion bei Datennetzen gemäß [Gei95]

Ein genereller Trend zur Abkehr von dem zentralen Ansatz ist seit Mitte der achtzi-ger Jahre zu erkennen. Ausgelöst wurde er im wesentlichen durch vier Entwicklung-stendenzen:

1. Im Bereich der Halbleiterchips kam es zu einer Leistungsexplosion. Die Rechen-leistung von Mikroprozessoren hat sich im letzten Jahrzehnt ca. alle zwei Jahreverdoppelt, die Kapazität von Halbleiterspeichern alle drei Jahre vervierfacht.Stetig wachsende Leistung bei schrumpfenden Preisen und Abmessungen bildetedie Grundlage dafür, daß immer mehr Rechner immer komplexere Software aus-führen konnten.

2. Die Bereitstellung schneller, lokaler Datennetze bildet die ökonomische Voraus-setzung dafür, Personal Computer und Workstations zu verbinden. Die Einfüh-rung der Ethernet-Technik in den siebziger Jahren kann als Wegbereiter für ver-teilte Softwaresysteme gesehen werden, siehe auch Abb. 1.1.

3. In den letzten drei Jahrzehnten sind auch erhebliche Fortschritte im Bereich derSoftwaretechnik zu verzeichnen gewesen. Die Akzeptanz von programmier-sprachlichen Konzepten wie Prozedur, Modul und Schnittstelle schuf die Voraus-


- 4 -

setzungen für die grundlegenden Mechanismen Verteilter Systeme. Konsequen-zen waren der RPC (Remote Procedure Call) und die objektorientierte Modellie-rung Verteilter Systeme.

4. Die Abkehr von streng hierarchisch aufgebauten Organisationsformen in Unter-nehmen führt ganz allgemein zu einer Dezentralisierung und schafft flache Füh-rungsstrukturen.

Diese vier Aspekte ermöglichen nicht nur die Entwicklung Verteilter Systeme, sie pro-vozieren sie geradezu.

1.2 Vorteile Verteilter Systeme

Warum nutzt man die oben angeführten Entwicklungstendenzen, um zentrale Sy-steme durch verteilte zu ersetzen? Es gibt eine ganze Reihe von Gründen, welche fürVerteilte Systeme sprechen, vgl. auch [PSW95]:m Verteilte Systeme ermöglichen die stetige Anpassung der Größe eines Systems. Den

neu hinzugekommenen Anforderungen an das Computersystem eines expandieren-den Unternehmens kann durch Erweiterungen bestehender Komponenten zeitgemäßentsprochen werden.

m Bestehende Lösungen sind integrierbar. Existierende Systeme können von neu hin-zugekommenen Systemkomponenten genutzt werden, ohne daß ein System gleicherFunktionalität neu entwickelt werden muß.

m Eine sukzessive Systemerweiterung minimiert das Risiko der Überlastung einzelnerSystemkomponenten, indem stets auf die gleichmäßige Auslastung sowohl beste-hender als auch neu hinzukommender Module geachtet wird.

m Die überschaubare, organisatorische Verwaltung der Kapazität eines Verteilten Sy-stems bedingt kosteneffektive Realisierungen. Das System ist flexibel und anpaß-bar.

m Der Eigentümer einer Ressource hat die Möglichkeit, das Management dieser Kom-ponente selbst zu übernehmen. In jedem Fall steht es ihm frei bei Bedarf einzugrei-fen, um seine eigenen Interessen wahrzunehmen.

m Die einzelnen Bestandteile eines Verteilten Systems sind weitestgehend autonom.Im Falle eines Fehlers oder sogar Ausfalls einer Systemkomponente können die üb-rigen Einheiten im Idealfall unbeeinflußt weiterarbeiten und ggf. den Störfall über-brücken.

Neben diesen (und vielen weiteren) Vorteilen eines Verteilten Systems kann man sichauch über Nachteile streiten, die u.a. in folgenden Punkten zum Ausdruck kommen:m Für den Zeitraum des Übergangs zu Verteilten Systemen droht ein Softwaredefizit.

Die Realisierung eines Verteilten Systems erfordert komplexere Softwarelösungenals die eines zentralen Systems. In [Tan92] wird der „radikale Unterschied“ in derSW-Bereitstellung für zentrale und Verteilte Systeme betont. Danach ist man bei


- 5 -

Verteilten Systemen erst am Anfang der Konzeptentwicklung.

m Die hinzugekommenen Netzwerkkomponenten können vollkommen neuartige Feh-ler verursachen.

m Aus der Sicht des Datenschutzes sind Verteilte Systeme bedenklich. Vernetzte Da-ten ermöglichen generell einfacher den Zugriff, als dies bei separater Datenhaltungder Fall ist.

1.3 Klassifikation Verteilter Systeme

Die Klassifikation Verteilter Systeme erfolgt entsprechend ihrer Hard- und Soft-ware. Zunächst zur Hardware. Wichtig ist, wie die einzelnen Komponenten einesVerteilten Systems miteinander verbunden sind und wie sie kommunizieren. Dazu gibtes verschiedene Klassifikationsschemata.

Ein bekanntes Beispiel ist sicherlich die Unterscheidung von sequentiellen („sin-gle“) und parallelen („multiple“) Instruktions- und Datenströmen nach Flynn (1971),welche zu insgesamt vier Rechnerklassen führt: Zum einen sind dies klassische vonNeumann-Rechner, hier bezeichnet mit der Abkürzung SISD (Single Instruction SingleData). Des weiteren benennt man parallele und verteilte Architekturen mit MIMD(Multiple Instruction Multiple Data). Mischformen, wie etwa Vektorrechner, gehöreneiner der Klassen SIMD oder -seltener- MISD an.

Bei MIMD-Architekturen ist es darüber hinaus üblich, zwischen Systemen, bei de-nen die Prozessoren auf einen gemeinsamen Speicher zugreifen, und solchen, bei de-nen jedem Prozessor ein eigener privater Speicher zur Verfügung steht, zu unterschei-den. Man trennt also „ shared memory“ -Systeme von „non shared memory“-Systemen. Betrachtet man Verteilte Systeme, so liegt dabei im Sinne der anfangs ge-mäß [Spa94] gegebenen Definition der Fall des „non shared memory“ vor.

Um nun Rechnerarchitekturen weiter abzugrenzen, unterscheidet man lose gekop-pelte und fest gekoppelte Systeme. In letzterem Fall ist die Verzögerung bei derÜbertragung einer Nachricht von einer CPU zu einer anderen als niedrig einzustufen.Dementsprechend ist die Übertragungsrate hoch. In einem lose gekoppelten System istdas Gegenteil der Fall. Die Übertragungsrate ist niedrig, große Verzögerungszeitensind möglich. Ein Beispiel für ein lose gekoppeltes System wären zwei über Modemund Telefonnetz gekoppelte Rechner. Fest gekoppelte Systeme sind in der Regel mitshared memory ausgestattet. Man bezeichnet sie mithin als Multiprozessorsysteme. Sieeignen sich eher als System zur parallelen Abarbeitung eines einzelnen Problems. Beider Bearbeitung mehrerer unabhängiger Probleme bietet sich die Verwendung einesMulticomputers mit non shared memory an, welcher durch ein „echtes“ Verteiltes Sy-stem repräsentiert werden kann.

Jede dieser Kategorien kann aufgrund des Aufbaus des verwendeten Verbindungs-netzwerks weiter unterteilt werden in busbasiert bzw. switchbasiert. Unter einem Busversteht man ein einzelnes Netzwerk, ein Kabel oder ein anderes Medium, das alleRechner verbindet. Switchbasierte Systeme verfügen nicht über ein solches „Rück-


- 6 -

grat“. Es bestehen einzelne Verbindungen zwischen den Rechnern. Daher muß in je-dem Knoten für eine aufzubauende Verbindung eine Routingentscheidung getroffenwerden. Für letztere Architektur entscheidet man sich immer dann, wenn abzusehenist, daß der zu erwartende rege Datenverkehr das Bussystem schnell überlasten würde.Aber auch switchbasierte Systeme stoßen schnell an ihre Grenzen. Bei einem Kreuz-schienenverteiler werden n2 Switches benötigt, in Omega-Netzwerken aus 2x2-Switches immerhin noch n⋅log2(n) Switches. Neben den dadurch entstehenden hohenKosten für die große Anzahl Switches tritt als weiteres Problem die hohe Verzöge-rungszeit beim Durchlaufen der einzelnen Switch auf. Dies betrifft vor allem Multi-prozessorsysteme. Bei Multicomputern ist mit deutlich geringerem Verkehrsaufkom-men zu rechnen, da der lokale Speicher entlastend wirkt. Um die Kosten niedrig zuhalten, werden hier nicht alle Prozessoren über Switche direkt verbunden, sondernkönnen nur mittelbar über andere Prozessoren Nachrichten austauschen. Vielfach ver-wendete Topologien sind einfache zweidimensionale Gitter und Hypercube.

Abb. 1.2: Bus- und switchbasierte Systeme

mit und ohne gemeinsamen Speicher

Bisher wurden für die Klassifikation ausschließlich Hardwaremerkmale herangezo-gen. Unterschieden wurden letztlich vier Varianten: Bus- bzw. Switchbasierte, loseoder eng gekoppelte Systeme. Bedeutender noch ist jedoch die Software und dabeiinsbesondere das zum Einsatz kommende Betriebssystem. Analog zur Hardware unter-scheidet man lose gekoppelte von fest gekoppelter Software.

Lose gekoppelte Software gestattet es Rechnern und Benutzern eines Verteilten Sy-stems, im wesentlichen unabhängig voneinander zu arbeiten und nur in einem be-grenzten Umfang - im Bedarfsfall - zu interagieren. Ein Beispiel wären PC-Arbeitsplätze mit jeweils eigener CPU, eigenem Speicher und Betriebssystem, abergemeinsam genutztem Laserdrucker. Fest gekoppelte Software realisiert ein Programmauf verschiedenen Rechnern gleichzeitig.


- 7 -

Tabelle 1.1: Kategorien verteilter Systeme

SoftwareHardware

lose gekoppelt fest gekoppelt

eng gekoppelt(Bus- und Switchbasiert) � ì

(Multiprozessorbetriebssy-stem)

lose gekoppelt(Bus- und Switchbasiert) ó

(Netzbetriebssystem)

ö(Verteiltes Betriebssystem)

Kategorie ó in Tabelle 1.1 ist die in Unternehmen gebräuchlichste Form der Hard-ware- und Softwarekombination, z.B. realisiert durch eine Anzahl über ein LAN ver-bundener Workstations. Sie wird auch als Netzbetriebssystem bezeichnet. Jeder Nutzerhat dabei eine eigene Workstation mit eigenem Betriebssystem. I.d.R. wird dabei lo-kales Arbeiten bevorzugt, explizite entfernte Aufrufe (z.B. rlogin oder rcp) sindjedoch möglich. Die Kommunikation erfolgt in diesem Fall über den Zugriff auf ge-meinsame Dateien.

Kategorie ö, das sog. Verteilte Betriebssystem, schafft für den Nutzer die Illusion,daß das gesamte Netzwerk eher ein Time-Sharing-System ist, als daß es eine An-sammlung einzelner Maschinen darstellt. Die Kommunikation erfolgt bei einem sol-chen System über Nachrichten.

Letztlich ist darüber hinaus nur noch Kategorie ì sinnvoll: Die Systeme dieser Ka-tegorie dienen häufig speziellen Zwecken, wie z.B. Datenbanksysteme. Charakteri-stisch ist dabei eine einzelne Prozeß-Queue im gemeinsamen Speicher. Die Kommuni-kation zwischen den einzelnen Komponenten eines solchen Systems erfolgt über dengemeinsamen Speicher. Diese Kategorie wird auch als Multiprozessorbetriebssystembezeichnet.

1.4 Eigenschaften Verteilter Systeme

Nachdem im vorangegangenen Abschnitt geklärt worden ist, auf welche Weise sichverteilte Systeme unterscheiden, soll im folgenden auf die Gemeinsamkeiten der unter-schiedlichen Ausprägungen Verteilter Systeme eingegangen werden. Dabei gibt es fol-gende Charakteristiken:

1. Ein erster Aspekt ist die Entferntheit. Komponenten eines Verteilten Systems sindimmer auch räumlich voneinander getrennt. Wechselwirkungen treten entwederlokal oder entfernt auf.

2. Die Komponenten eines Verteilten Systems können parallel arbeiten, woraus einGeschwindigkeitszuwachs gegenüber sequentieller Vorgehensweise resultiert.Das System ist in der Lage, Nebenläufigkeit zu realisieren.


- 8 -

3. Es ist nicht praktikabel, ausschließlich globale Systemzustände zu betrachten.Lokale Zustandsbetrachtungen müssen zusätzlich durchgeführt werden.

4. Komponenten arbeiten unabhängig und können auch unabhängig voneinanderausfallen. Verteilte Systeme unterliegen somit dem partiellen Systemausfall.

5. Das System arbeitet asynchron. Kommunikations- und Verarbeitungsprozessewerden nicht durch eine globale Systemuhr gesteuert. Änderungen und Prozessewerden demzufolge nicht notwendigerweise synchronisiert.

6. Im Verteilten System dürfen Management- und Steuerfunktionen auf verschiede-ne autonome Komponenten, sogenannte Autoritäten, verteilt werden. Dabei darfkeine einzelne Autorität eine übergeordnete Gesamtkontrolle ausführen. Dies si-chert ein gewisses Maß an Autonomie.

7. Ein Verteiltes System kann durch Zusammenschluß von bereits existierenden Sy-stemen entstehen. Demzufolge ist eine kontextbezogene Namensverwaltung er-forderlich, welche die eindeutige Interpretation der Namen über die Grenzen ei-nes administrativen oder technologischen Bereichs hinaus ermöglicht. Manspricht in diesem Zusammenhang von föderativer Namensverwaltung.

8. Um die Leistungsfähigkeit des Verteilten Systems zu erhöhen, können Program-me und Daten zwischen verschiedenen Orten bewegt werden, dieses Konzeptwird als Migration bezeichnet. Dabei sind zusätzliche Mechanismen einzubezie-hen, welche die Lage von Programmen und Daten protokollieren.

9. Ein Verteiltes System muß in der Lage sein, dynamische Umstrukturierungenvorzunehmen. Diese dynamischen Rekonfiguration ist beispielsweise dann erfor-derlich, wenn zur Laufzeit neue Bindungen hinzugefügt werden müssen.

10. Rechnerarchitekturen können unterschiedliche Topologien und Mechanismenbenutzen, insbesondere, falls es sich um Produkte verschiedener Hersteller han-delt. Diese Charakteristik wird als Heterogenität bezeichnet.

11. Ein Verteiltes System unterliegt der Evolution. Es wird in seiner Lebenszeitzahlreiche Änderungen durchlaufen.

12. Quellen von Informationen, Verarbeitungseinheiten und Nutzer können physi-kalisch mobil sein. Programme und Daten können zwischen Knoten bewegt wer-den, um die Mobilität des Systems zu erhalten oder die Leistungsfähigkeit zusteigern.

Um diese Charakteristiken zu erreichen, müssen bestimmte Anforderungen erfüllt sein,um Verteilte Systeme geeignet modellieren und implementieren zu können, vgl[PSW95]:

m Offenheit, d.h. Portabilität eines Systems,m Integrierbarkeit, zur Behandlung der Heterogenität,m Flexibilität, um die Evolution des Systems zu unterstützen,m Modularität, welche eine wichtige Grundvoraussetzung für die Flexibilität dar-

stellt,m Föderation, um den Zusammenschluß autonomer Einheiten zu ermöglichen,


- 9 -

m Verwaltbarkeit,m Sicherstellung von Dienstqualitäten,m Sicherheit undm Transparenz.Transparenz ist eine zentrale Anforderung, die daraus resultiert, den Umgang mit

verteilten Anwendungen so weit wie möglich zu erleichtern. Sie umfaßt das Verbergenvon Implementierungsdetails und die Verteilungstransparenz. Letztere verbirgt ihrer-seits die Komplexität Verteilter Systeme. Dabei werden interne Vorgänge durch soge-nannte Transparenzfunktionen vor dem Betrachter verborgen. Der Nutzer wird dadurchentlastet.

Es gibt viele Ausprägungen der Verteilungstransparenz. Exemplarisch sollen hiereinige genannt werden.m Die Zugriffstransparenz verbirgt die speziellen Zugriffsmechanismen für einen

lokalen oder entfernten Dienst- bzw. Ressourcenaufruf.

m Die Ortstransparenz verbirgt die Systemtopologie als solche.

m Dem gegenüber hält die Migrationstransparenz Bewegung und Auslagerung vonFunktionen und Anwendungen transparent.

m Unter Replikationstransparenz versteht man Vorkehrungen für das - vom Benut-zer unbemerkte - Anlegen redundanter Kopien von Datenbeständen des Netzes.Letztes födert den sicheren und schnellen Zugriff auf die Daten.

m Abarbeitungstransparenz verbirgt, ob die Abarbeitung eines Aufrufs parallel odersequentiell erfolgt.

m Wird bei Ausfall einer angesprochenen Netzkomponente ohne Zutun des Nutzersein Ersatz gefunden und angesprochen, so spricht man von Ausfalltransparenz.

m Bleibt auch die Zuordnung von Ressourcen zu Anwendungsprozessen verkapselt, soliegt Ressourcentransparenz vor.

m Die Verbundstransparenz versteckt Grenzen zwischen administrativen und tech-nologischen Bereichen.

m Gruppentransparenz verbirgt das Benutzen von Gruppen.

Anwendung

Verteilungsplattform

4

3

2

1

Betriebssystem

Abb. 1.3: Einordnung der Verteilungsplattform in die Softwarearchitektur


- 10 -

Zur Überbrückung von Verteilung bedarf es einer geeigneten Softwareinfrastruktur.Diese heißt nach [Gei95] Verteilungsplattform oder auch synonym Middleware,Verteilungsinfrastruktur und gemäß der in Abschnitt 1.3 eingeführten KlassifikationNetzbetriebssystem. Die Verteilungsplattform unterstützt die Interaktion zwischenden auf potentiell heterogenen Systemen ablaufenden Anwendungskomponenten. DieVerteilungsplattform wird dem lokalen Betriebssystem hinzugefügt oder übernimmtselbst die Aufgaben des Betriebssystems. Auf diese Weise wird die Verteilung transpa-rent gehalten. Anwendungen werden von komplexen Details interner Vorgänge abge-schirmt.

Einer Verteilungsplattform können viele individuelle Systeme zugrundeliegen, aufdenen sie aufsetzt. Gleichzeitig kann eine Vielzahl von Anwendungen auf die Vertei-lungsplattform zugreifen.

- 11 -

2 Kommunikation

in Verteilten Systemen

In den folgenden drei Kapiteln soll die Zwei-Parteien-Kommunikation betrachtetwerden, d.h. die Kommunikation zwischen zwei Komponenten eines Verteilten Sy-stems. Vorausgesetzt wird dabei die Kenntnis des OSI-Referenzmodells mit seinensieben Schichten. Insbesondere Wissen über die drei oberen, anwendungsorientiertenSchichten sind für das Verständnis im folgenden hilfreich.

2.1 Das Client/Server-Modell

Am Anfang unserer Überlegungen soll die These stehen, daß das OSI-Modell nichtzur Modellierung Verteilter Systeme geeignet ist. Warum ist dies der Fall? Der Ver-waltungsaufwand der sieben Schichten ist zu hoch, denn bei der Übertragung einerNachricht wird sieben mal ein Datenkopf angehängt bzw. wieder entfernt. Dies kostetZeit, bei LANs in Relation zur Übertragung sogar sehr viel Zeit. Die Folge dieser Er-kenntnis ist, daß Verteilte Systeme auf ein eigenes Grundmodell zurückgreifen: dasClient/Server-Modell (C/S-Modell).

Abb. 2.1: Das Client/Server-Modell

Die Idee des C/S-Modells besteht darin, ein Betriebssystem als Menge kooperieren-der Prozesse - sogenannter Server - zu strukturieren. Diese stellen den Nutzern -sogenannten Clients - Dienste bereit. Auf einem Rechner kann ein Client oder ein Ser-

Verteilte Systeme 2. Kommunikation in Verteilten Systemen

- 12 -

ver, eine Menge von Clients oder Servern oder beides laufen. Das C/S-Modell basiertauf einem einfachen, verbindungslosen Anfrage/Antwortprotokoll: Der Client sendeteine Anfrage und erhält seine Antwort von dem Server, vgl. Abb. 2.1. Diese einfacheMethode ist sehr effizient. Der Protokollstapel wird klein gehalten. Bei identischenRechnern besitzt er nur drei Protokollschichten:

M

5 Anfrage/Antwortschicht

M

2 Verbindungsschicht

1 Bitübertragungsschicht

Abb. 2.2: Der Protokollstapel des Client/Server-Modells

Die Schichten 1 und 2 werden immer durch Hardware realisiert, z.B. durch entspre-chende Ethernet- oder Token-Ring-Bausteine. Die Schichten 3 und 4 werden nicht be-nötigt, da keine Verbindungen aufgebaut werden und kein Routing notwendig ist. DieMenge der erlaubten Anfragen und Antworten legt das Anfrage/Antwortprotokoll inSchicht 5 fest. Da keine unterschiedliche Datenrepräsentation verwendet wird, entfälltdie Funktionalität der Schicht 6. Die Anwendung selbst ist im C/S-Modell bzw. in derVerteilungsplattform nicht vorhanden.

Legt man diese einfache Struktur zugrunde, so ist es lediglich notwendig, daß dieVerteilungsplattform zwei Systemaufrufe anbietet. Ein Aufruf der Art send(a,&mp)

verschickt die Nachricht, die durch mp referenziert wird, an einen Prozeß, der durch aidentifiziert wird. Der Aufrufer wird dabei so lange blockiert, bis die Nachricht voll-ständig verschickt ist. Demgegenüber wird der Aufrufer von receive(a,&mp) blok-kiert, bis eine Nachricht für ihn angekommen ist. Die Nachricht wird in den durch mpangegebenen Puffer kopiert. Der Parameter a gibt die Adresse an, die vom Empfängerabgehört wird.

Es existieren viele Varianten dieser Routinen. Im folgenden soll eine einfache Im-plementierung für einen Fileserver gemäß [Tan92] vorgestellt werden. Der Client undder Server haben eine Reihe von Definitionen gemeinsam, die in der Datei header.haus Abb. 2.3 zusammengefaßt sind. Dabei handelt es sich im wesentlichen um die De-finition erlaubter, entfernter Operationen auf den durch den Server verwalteten Datei-en, damit in Verbindung stehende Fehlercodes und vor allem die Definition des Nach-richtenformats. Alle Anfragen von einem Client an einen Server sowie alle Antwortenbenutzen dieses Format. In einem realen System gibt es i.d.R. kein festes Nachrichten-format!

Die Hauptschleife des ereignisorientierten Serverprogramms ist in Abb. 2.4 angege-ben. Man erkennt, wie einfach die Implementierung vorgenommen werden kann. ZuBeginn des Schleifenkörpers wird die Bibliotheksroutine receive(⋅) aufgerufen, um


- 13 -

ankommende Anfragen zu erhalten. Der Prozeß wird blockiert. Erst wenn eine Anfrageeintrifft, veranlaßt der Betriebssystemkern die Aufhebung der Blockade. Abhängigvom Inhalt des opcode-Feldes wird anschließend eine Prozedur aufgerufen, welchedie gewünschte Funktionalität realisiert.

#define MAX_PATH 255 /* max. Länge des Dateinamens */#define BUF_SIZE 1024 /* auf einmal übertragbare Datenmenge */#define FILE_SERVER 243 /* Netzwerkadresse des Datei-Servers */

/* erlaubte Operationen zur Verwaltung */

#define CREATE 1#define READ 2#define WRITE 3#define DELETE 4

/* Fehlercodes */

#define Ok 0#define E_BAD_OPCODE -1 /* unbekannte Operation */

/* Nachrichtenformat */

struct message {long source; /* Identität des Senders */long dest; /* Identität des Empfängers */long opcode; /* Code einer erlaubten Operation */long count; /* Anzahl der übertragenen Bytes */long offset; /* Position des Lesens bzw. Schreibens */long extra1; /* Zusatzfeld */long extra2; /* Zusatzfeld */long result; /* Ergebnisstatus der Operation */char name[MAX_PATH]; /* Dateiname */char data[BUF_SIZE]; /* Datenpuffer, wird nur benutzt

bei READ und WRITE */};

Abb. 2.3: Listing header.h

#include <header.h>

void main(void) /* Es handelt sich um einen Prozeduraufruf. Es werden weder Parameter übergeben noch erwartet. */

struct message m1,m2; /* eintreffende und ausgehende Nachrichten */int r; /* Ergebniscode */

initialize(); /* wird spaeter fuer dyn. Binden gebraucht */while (true) { /* permanente Schleife */

receive (FILE_SERVER,&m1);/* für FILE_SERVER ankommende Nachricht wird in Puffer m1 kopiert. Blockierung, bisNachricht angekommen und kopiert ist. */

switch (m1.opcode){ /* Fallunterscheidung für Operation von m1 */case CREATE: r=do_create(&m1,&m2); break;case READ: r=do_read(&m1,&m2); break;case WRITE: r=do_write(&m1,&m2); break;case DELETE: r=do_delete(&m1,&m2); break;default: r=E_BAD_OPCODE;

}m2.result=r; /* Ergebniscode wird der ausgehenden

Nachricht zugewiesen */send(m1.source,&m2); /* sende Antwort; Blockierung des Servers,

bis die Nachricht verschickt ist */}

}

Abb. 2.4: Listing server.c


- 14 -

#include <header.h> /* gleiche Definition wie beim Server */

int copy(char *src, char *dst){

struct message m1; /* Nachrichtenpuffer */long position=0; /* aktuelle Dateiposition */long client=110; /* Adresse des Client */initialize (); /* bereite Ausführung vor */

do {/* lies einen Datenblock aus der Quelldatei */m1.opcode=READ; /* als Operation wird Lesen definiert */m1.offset=position; /* setzen der aktuellen Dateiposition */m1.count=BUF_SIZE; /* def., wieviele Bytes auf einmal

gelesen werden sollen */strcpy(m1.name,src);/* kopiere Dateinamen in Nachricht m1 */send(FILE_SERVER,&m1); /* sende Nachricht an Dateiserver */receive(client,&m1);/* warte blockiert auf die Antwort */

/* schreibe die empfangenen Daten in die Zieldatei */m1.opcode=READ; /* Operation ist Lesen */m1.offset=position; /* aktuelle Dateiposition */m1.count=BUF_SIZE; /* wieviele Bytes sollen gelesen werden */strcpy(m1.name,src);/* kopiere Dateinamen in Nachricht */send(FILE_SERVER,&m1);receive(client,&m1);position+=m1.result /* m1.result ist Anzahl geschriebener Bytes */

} while (m1.result>0); /* wiederhole, bis alle Pakete übertragen, oder Fehler aufgetreten sind */

return (m1.result); /* gebe OK oder Fehlercode zurück */}

Abb. 2.5: Listing client.c

Exemplarisch ist in Abb. 2.5 eine Client-Prozedur angegeben, die mit Hilfe desServers eine Datei kopiert. Der Funktion copy werden dabei Zeiger src und dst auf dieDateinamen übergeben. Die Bestandteile der Datei werden paketweise vom Servereingelesen und anschließend wieder an diesen zurückgesendet.

Abb. 2.6: Blockierende Kommunikationsprimitive


- 15 -

Zur Abstraktion des Programms soll überlegt werden, wann der Server blockiert ist.Dies geschieht zunächst beim Aufruf von receive. Der Prozeß wartet auf eine An-frage. Mit dem send nach Bearbeitung der Anfrage erfolgt eine weitere Blockierungfür die Dauer der Übertragung. Den genauen Ablauf mit den entsprechenden Blockie-rungsphasen auf Client- und Serverseite entnimmt man Abb. 2.6.

AdressierungIn diesem Beispiel war dem Client die Adresse des Servers dadurch bekannt, daß sie

als Konstante in der Datei header.h enthalten war. Von einer solchen Voraussetzungkann nicht immer ausgegangen werden. Es ergibt sich ein Adressierungsproblem.

Im Sinne einer föderativen Namensverwaltung sollte bei der Adressierung unter-schieden werden zwischen Prozeß und Zielrechner. Als Alternative zu der absolutenAngabe einer Adresse ist es daher sinnvoll den Namen in zwei Teile aufzuspalten.Zum Beispiel stünde 4@243 oder 243,4 für Prozeß Nummer 4 auf Rechner Nummer243. Der Ablauf der Kommunikation ist bei diesem Verfahren besonders einfach. Erbesteht nur aus zwei Schritten:1. Der Anfrage an den Server und

2. dessen Antwort an den Client.

Der Nachteil dieser machine.process-Adressierung und ihrer zahlreichen Variati-onsmöglichkeiten besteht darin, daß der Nutzer wissen muß, auf welchem Rechner derServer plaziert ist, d.h. es ist keine Ortstransparenz der Server mehr vorhanden. Damitist ein wesentliches Ziel bei der Entwicklung Verteilter Systeme verlorengegangen.

Abb. 2.7: Varianten der Adreßfindung

Ein anderer Ansatz sieht ein spezielles Lokalisierungspaket vor, das der Sender an


- 16 -

alle anderen Rechner schickt. Das Lokalisierungspaket enthält die Adresse des Ziel-prozesses oder eine Bezeichnung des gesuchten Prozesses (Dienstes). Insbesondere fürLANs, welche echtes Broadcast bereitstellen, wäre ein „Lokalisierung-durch-Broadcast“-Verfahren denkbar. Dieses Vorgehen sichert zwar die Ortstransparenz,verursacht durch den Broadcastaufruf jedoch zusätzliche Netzlast. Der Ablauf wird aufvier Schritte ausgedehnt:1. Broadcasten des Lokalisierungspakets,

2. „Ich bin hier“-Antwort des Servers,

3. Anfrage an den Server,

4. Antwort des Servers.

Eine Weiterentwicklung auf diesem Gebiet ist die Einführung eines Name-Serversoder Traders. Diese Begriffe unterscheiden sich leicht, da ein Trader i.d.R. etwaskomfortabler ist. Das Prinzip sieht in beiden Fällen folgenden Ablauf vor:1. Zunächst erfolgt eine Anfrage des Clients an den Name-Server nach der Adresse

des gewünschten Servers. Ein Trader wird alternativ nach einem bestimmten Prozeßoder Dienst gefragt.

2. Der Name-Sever (Trader) übermittelt die Adresse an den Client.

3. Mit Hilfe dieser Adresse kann der Client nun die ursprünglich gewünschte Anfragestellen.

4. Der adressierte Server antwortet auf die Anfrage.

Bei Vorhandensein eines Traders kann dem Client auch bei unvollständigen Angabenein Dienst vermittelt werden. Die Dienstvermittlung erfordert jedoch zahlreiche neueMechanismen, siehe [Spa94].

BlockierungBei Kommunikationsprimitiven unterscheidet man zwischen blockierenden (syn-

chronen) und nichtblockierenden (asynchronen) Primitiven. Der Systementwicklerwählt zwischen diesen beiden Arten.

Bei blockierenden Primitiven wird der Prozeß während der Sendung einer Nach-richt blockiert, d.h. Anweisungen werden erst dann weiter abgearbeitet, wenn dieNachricht vollständig abgesendet ist. Analog endet die Blockierung beim Empfangenerst, nachdem die Nachricht angekommen und kopiert ist. Die in Abb. 2.3 bis Abb. 2.5vorgestellte Implementierung basierte auf der Verwendung von blockierenden Primiti-ven. Bei nichtblockierenden Primitiven wird die zu sendende Nachricht zunächst nurin einen Puffer des Betriebssystemkerns kopiert. Direkt im Anschluß daran, also nochvor der eigentlichen Sendung, erfolgt die Entblockierung. Der sendende Prozeß kannparallel zur Nachrichtenübertragung mit seiner Ausführung fortfahren. Dieser Ge-schwindigkeitsvorteil wird jedoch dadurch erkauft, daß der Sender nicht weiß, wanndie Übertragung beendet ist und wann er den Puffer wieder nutzen kann. Darüber hin-aus kann er den einmal beschriebenen Puffer auch nicht mehr verändern.


- 17 -

Die Definitionen synchroner und asynchroner Primitive unterscheiden sich jenach Autor. An einigen Stellen wird immer dann von synchronen Primitiven gespro-chen, wenn der Sender blockiert ist, bis der Empfänger den Erhalt der Nachricht bestä-tigt hat.

PufferungAuch bezüglich der Pufferung gibt es zwei Möglichkeiten, Primitive zu realisieren.

Bisher wurde immer von ungepufferten Primitiven ausgegangen. recei-ve(addr,&mp) informiert den Kern seiner Maschine, daß der aufrufende Prozeß dieAdresse addr abhören will und bereit ist, Nachrichten von dort zu empfangen. EinenPuffer stellt er an der Adresse &mp bereit. Wann kann es bei diesem Vorgehen zu Pro-blemen kommen? Schickt der Client erst ein send und der Aufruf von receivedurch den Server erfolgt zu einem späteren Zeitpunkt, so weiß der Kern bei einer an-kommenden Nachricht nicht, ob einer seiner Prozesse die Adresse dieser Nachrichtbenutzen wird und wohin er ggf. die Nachricht kopieren soll. Der Client kann in die-sem Fall einen Verlust des Aufrufes nicht aussschließen. Eine mögliche Implementie-rung könnte daher ein wiederholtes send nach Ablauf eines Timers im Client vorse-hen.

Nutzen mehrere Clients die gleiche Adresse, so können weitere Probleme auftreten.Nachdem der Server eine Nachricht von einem der Clients angenommen hat, hört ersolange nicht mehr seine Adresse ab, bis er seinen Auftrag erledigt hat und den näch-sten receive-Aufruf ausführt. Falls die Erledigung eines Auftrags länger dauert,können andere Clients eine Reihe von Versuchen unternehmen, an den Server zu sen-den. Dabei können manche von ihnen bereits aufgegeben haben, je nachdem wievieleVersuche sie unternehmen bzw. wie „ungeduldig“ sie sind.

Abb. 2.8: a) Ungepufferte und b) gepufferte Primitive

Eine alternative Implementierung, welche die genannten Probleme zu umgehen ver-


- 18 -

sucht, sind die puffernden Primitive. Ein empfangender Kern speichert die eintreffen-den Nachrichten für einen bestimmten Zeitraum zwischen. Wird kein passendes re-

ceive aufgerufen, so werden die Nachrichten nach einem Timeout gelöscht. Es müs-sen Puffer vom Kern bereitgestellt und verwaltet werden. Eine konzeptionell einfacheLösung sieht die Definition einer Datenstruktur Mailbox vor. Ein Prozeß, welcherNachrichten empfangen will, fordert den Kern auf, eine Mailbox für ihn zu erzeugenund gibt die Adresse an, mit der in eintreffenden Netzwerkpaketen nachgesehen wer-den soll. Bei einem receive wird eine Nachricht aus der Mailbox geholt. Ist dieMailbox leer, so wird der Prozeß blockiert. Probleme treten dann nur bei voller Mail-box auf. In diesem Fall werden Aufrufe wie im ungepufferten Fall verworfen.

ZuverlässigkeitFür eine Weiterklassifizierung der Primitive nach dem Grad ihrer Zuverlässigkeit

bietet sich eine Einteilung in drei grobe Klassen an.1. Primitive, welche nach dem „Prinzip der Deutschen Bundespost“ vorgehen: Ab-

schicken, der Rest ist egal.

2. Primitive, bei denen der empfangende Kern eine individuelle Bestätigung an denSender zurückschicken muß.

3. Primitive, welche die Bestätigung im piggy-backing übertragen. Dabei macht mansich das Wissen zunutze, daß der Server i.d.R. auf eine Anfrage in einem eng ge-steckten Zeitrahmen antworten wird, siehe auch Abb. 2.9.

Eine Kombination der beiden letztgenannten Möglichkeiten sieht vor, daß vom piggy-backing auf individuelle Bestätigungen übergegangen wird, falls der gesteckteZeitrahmen überschritten wird.

Abb. 2.9: Bestätigung mittels piggy-backing

Insgesamt ergeben sich vier Entwurfsmöglichkeiten: Adressierung, Blockierung,Pufferung und Zuverlässigkeit. Diese können in ihren verschiedenen Ausprägungenkombiniert werden.

Bei der Kombination sollte jedoch beachtet werden, daß es mehr und weniger sinn-volle Möglichkeiten gibt. Die Verwendung von blockierenden und ungepufferten Pri-mitiven ist ebenso sinnvoll wie die Verwendung von nichtblockierenden, gepuffertenPrimitiven. Es ist jedoch nicht sinnvoll, ungepufferte und nichtblockierende oder ge-pufferte und blockierende Primitive zu verwenden, da im ersten Fall (ungepuffert,nichtblockierend) das entstehende Fehlerrisiko zu hoch ist und im zweiten Fall (gepuf-fert, blockierend) eine nicht notwendige, zu lange Übertragungszeit entsteht.


- 19 -

2.2 Der Remote Procedure Call

Das Client/Server-Modell bietet einen brauchbaren Weg, ein verteiltes Betriebssy-stem zu strukturieren. Trotzdem hat es eine extreme Schwachstelle: Das Basisparadig-ma, auf dem alle Kommunikation aufbaut, ist die Ein- und Ausgabe von Daten; sendund receive organisieren jedoch den Austausch von Daten. Um das Ziel, verteilteBerechnungen für den Benutzer genau so aussehen zu lassen wie zentrale Berechnun-gen, zu erreichen, sind komfortablere Mechanismen notwendig.Ein Vorschlag von Birell und Nelson aus dem Jahr 1984 besteht darin, daß ein Pro-gramm ein Unterprogramm aufrufen können soll, welches sich auf einem anderenRechner befindet. Diese Methode ist als entfernter Unterprogrammaufruf (remoteprocedure call, RPC) bekannt. Ruft ein Prozeß auf Rechner A ein Unterprogrammauf Rechner B auf, so wird der aufrufende Prozeß auf A ausgesetzt (suspendiert) unddie Ausführung des aufgerufenen Unterprogramms findet auf Rechner B statt. Dabeiwerden Parameter ausgetauscht. Für den Programmierer bleibt dieser Nachrichtenaus-tausch jedoch unsichtbar.

Das Konzept bringt eine Vielzahl an Problemen mit sich, welche einzeln gelöstwerden müssen.

Um die Komplexität der Konzepte zu reduzieren, soll im folgenden 3-stufig vorge-gangen werden. Zunächst wird das klassische Konzept des lokalen Unterprogrammauf-rufs wiederholt, im zweiten Schritt wird der entfernte Prozeduraufruf in seiner einfach-sten, grundlegenden Form vorgestellt und schließlich werden im dritten Schritt Beson-derheiten des RPCs diskutiert und Erweiterungen vorgenommen.

Konventionelle lokale ProzeduraufrufeEs wird zunächst ein konventioneller Unterprogrammaufruf count=read(fd,

buf,nbytes); betrachtet: In einem traditionellen System wird read aus einer Bi-bliothek entnommen und durch den Binder in das ausführbare Programm eingebunden.Die Routine read ist i.d.R. ein in Assembler geschriebenes Unterprogramm, das nurseine Parameter in Register kopiert und den Systemaufruf READ ausführt, d.h. derKern wird mit dem Lesen der Daten beauftragt wodurch im Kern eine Ausnahmebe-handlung ausgelöst wird. Die Routine read kann somit als Schnittstelle zwischen Be-triebssystem und Benutzerprogramm verstanden werden.

Vor dem Aufruf von read im Hauptprogramm enthält der Stack die lokalen Varia-blen, siehe Abb. 2.10 a). Für den Aufruf werden die Parameter i.d.R. in umgekehrterReihenfolge auf dem Stack abgelegt, siehe Abb. 2.10 b). Zusätzlich findet noch dieRücksprungadresse Platz.


- 20 -

lokale Variablen desHauptprogramms

bytes

buf

fd

Rücksprungadresse

lokale Variablen vonread

sp


sp

sp


a) b) c)

Abb. 2.10: Stack bei einem lokalen Prozeduraufruf

Im Anschluß daran wird das Unterprogramm ausgeführt und der Ergebniswert in einRegister übertragen. Die Rücksprungadresse wird vom Stack entfernt und die Kon-trolle geht wieder an den Aufrufer. Dieser nimmt auch die Parameter vom Stack. DerStack hat dann wieder den ursprünglichen Zustand, siehe Abb. 2.10 c). Bei Unterpro-grammaufrufen unterscheidet man zwischen Wert- (call-by-value) und Referenzpara-metern (call-by-reference), je nachdem, ob es sich um einen Datenwert oder einen Zei-ger auf ein Datum handelt.

Der entfernte ProzeduraufrufIst read nun ein entferntes Unterprogramm, so ist für diesen Fall eine „andere Versi-

on“ von read, ein sogenannter Client-Stub in der Bibliothek enthalten. Der Aufruf er-folgt analog zu obigem Fall, und es wird wiederum eine Ausnahmebehandlung ausge-löst. Anders als beim Original werden die Parameter nicht in Register kopiert, und derKern wird nicht damit beauftragt, die gewünschten Daten zu lesen. Statt dessen werdendie Parameter in eine Nachricht verpackt und der Kern durch das send-Primitiv be-auftragt, die Nachricht an den Server zu schicken. Im Anschluß daran ruft der Client-Stub ein receive auf und blockiert sich so lange, bis eine Antwort eintrifft.

Trifft die Nachricht beim Server ein, so übergibt der Kern diese an den sogenanntenServer-Stub, der an den aktuellen Server gebunden ist. I.a. hat der Server-Stub geradeein receive aufgerufen und wartet auf ankommende Nachrichten. Der Server-Stubpackt dann die in der Nachricht enthaltenen Parameter aus und ruft das Unterpro-gramm lokal auf. Parameter und Rücksprungadresse werden wie gewohnt abgelegt. Esfolgt die Ausführung und die Rückgabe der Ergebnisse an den Server-Stub. Erhält derServer-Stub die Kontrolle zurück, so verpackt er die Ergebnisse, d.h. den Puffer, erneutin eine Nachricht, die er mittels send an den Client schickt. Zum Abschluß ruft erwieder receive auf und ist damit bereit, die nächste Nachricht zu empfangen.

Erreicht die Antwort des Servers den Client, wird sie in einen entsprechenden Puffer


- 21 -

kopiert und der Client-Stub wird entblockiert. Dieser prüft die Nachricht und packt sieaus. Dann schiebt er sie auf den Stack. Wenn der Aufrufer von read die Kontrollezurückerhält, so ist ihm nur bekannt, daß die Daten vorliegen, nicht aber, daß ein Auf-ruf entfernt ausgeführt wurde. Diese Transparenz zeichnet den RPC aus.

Auf diese Art können entfernte Dienste durch einfache, d.h. lokale UP-Aufrufe aus-geführt werden. Dies erfolgt ohne explizite Anwendung der Kommunikationsprimitive.Alle Details sind durch zwei Bibliotheksroutinen verborgen (den Client- und den Ser-ver-Stub), analog zum Verbergen von Ausnahmebehandlungen durch traditionelle Bi-bliotheken.

Zusammenstellung der einzelnen Schritte:

�Der Client ruft ein Unterprogramm im Client-Stub auf.

óDer Client-Stub erzeugt eine Nachricht und übergibt sie an den Kern.

ìDer Kern sendet die Nachricht an den entfernten Kern.

öDer entfernte Kern übergibt die empfangene Nachricht dem Server-Stub.

úDer Server-Stub packt die Parameter aus und ruft ein Unterprogramm im Server auf.

÷Der Server führt das Unterprogramm aus und übergibt dem Server-Stub die Ergeb-nisse.

øDer Server-Stub verpackt die Ergebnisse in einer Nachricht und übergibt sie seinemKern.

íDer entfernte Kern sendet die Nachricht an den Kern des Client.

ûDer Client-Kern übergibt die Nachricht an den Client-Stub.

çDer Client-Stub packt die Ergebnisse aus und übergibt sie dem Client.

Hierbei wird der entfernte Prozeduraufruf auf die lokalen Aufrufe � und ú zurückge-führt.

Abb. 2.11: Ablauf eines Remote Procedure Calls

Erweiterungen des entfernten ProzeduraufrufsDer Client besitzt die Aufgabe, Parameter entgegenzunehmen, sie in eine Nachricht


- 22 -

zu verpacken und diese an den Server-Stub zu senden. Hierbei tritt eine ganze Reihevon Problemen auf, welche im folgenden vorgestellt werden.

Für die Parameterübergabe ist zunächst das Verpacken der Nachricht, das soge-nannte (parameter) marshalling notwendig. Ein Aufruf der Art n=sum(4,7) wirddabei in eine Nachricht der Form

sum

4

7

übersetzt.Neben den Parametern 4 und 7 fügt der Client-Stub auch den Namen „sum“ (bzw. einesynonyme Nummer) des aufzurufenden Unterprogramms in die Nachricht ein, damitder Server weiß, welches Unterprogramm von ihm ausgeführt werden soll. Solange dieC/S-Rechner identisch sind und Parameter nur skalaren Typs ausgeführt werden, ar-beitet dieses Modell gut. Probleme gibt es bei heterogenen Rechnertypen mit unter-schiedlichen Zeichencodierungen oder Zahlendarstellungen. Ein störendes Problem istbeispielsweise, daß in einigen Rechnern die Bytes von rechts nach links numeriertwerden, während in anderen Rechnern die umgekehrte Reihenfolge verwendet wird.Die Folge ist, daß z.B. die Bytes zur Darstellung eines großen Integerwerts, in unter-schiedlichen Reihenfolgen gespeichert werden. In dem Buch „Gullivers Reisen“ istvon zwei Politikern die Rede, welche einen Krieg darüber begannen, an welchem Endeein Ei aufzuschlagen sei. In Anlehnung an die dort verwendeten Bezeichnungen nenntman das INTEL-Format, bei dem die Bytes von rechts nach links numeriert werdenauch little endian. Das SPARC-Format, bei dem umgekehrt verfahren wird, kanndemnach mit big endian bezeichnet werden.

Abb. 2.12: Der String CLIENT und der Integerwert 5 in INTEL- und SPARC-Format

Da ein Unterprogramm mit n Parametern aus (n+1) Feldern besteht, kann durch dieIdentifizierung des (n+1)ten Feldes abgeleitet werden, welches Format verwendetwird. Aus den Typinformationen für die Parameter können ggf. notwendige Konvertie-rungen abgeleitet werden.

Um die Darstellung einheitlich zu gestalten, fordert man häufig eine kanonischeDarstellung, die von allen Sendern beim Einpacken ihrer Nachrichten eingehalten wer-den muß. Ein Verfahren, bei dem beispielsweise stets little endian verlangt wird kann

a) little endian

Adresse 10 9 8 7 6 5 4 3 2 1Inhalt T N E I L C 0 0 0 5

b) big endian

Adresse 1 2 3 4 5 6 7 8 9 10Inhalt T N E I L C 0 0 0 5


- 23 -

sich jedoch als störend und ineffizient herausstellen, falls zwei big endian Rechnermiteinander kommunizieren. Es muß zweimal konvertiert werden, obwohl dies nichtnotwendig wäre. Alternativ benutzt der Client sein internes Format und gibt im erstenByte an, um welche Darstellung es sich dabei handelt. Der Server kann dann überprü-fen, ob eine Übereinstimmung mit seinem internen Format vorliegt und leitet, fallsnotwendig, eine Konvertierung in die Wege.

2.2.1 Dynamisches Binden

In einem Verteilten System ist es möglich, daß sich aufgrund bestimmter Ereignissedie Adresse eines Servers bzw. seiner Schnittstelle ändert. Dies hätte zur Folge, daßzahlreiche Programme neu geschrieben und übersetzt werden müßten. Statt dessen be-nutzt man den Mechanismus des dynamischen Bindens.Ausgangspunkt hierfür ist eine formale Spezifikation des Servers, z.B. in folgenderForm:

#include<header.h>specification of file_server, version 3.1;

long read (in char name[MAX_PATH], out char buf[BUF_SIZE],in long bytes, in long position);

long write (in char name...);int create(...);int delete(...);

end;

Abb. 2.13: Formale Spezifikation eines Servers

Diese Spezifikation enthältm den Namen des Servers (im Beispiel, Abb. 2.13, ist dies ein file-server),m die Versionsnummer (3.1),m eine Liste von Unterprogrammen (read, write, ...), die der Server anbietet.

Für alle Unterprogramme wurden die Typen der Parameter angegeben. Diese Typenbeziehen sich auf den Server, d.h.m ein in-Parameter (wie z.B. name) wird vom Client an den Server gesendet. name

teilt dem Server mit, welche Datei gelesen, geschrieben o.ä. werden soll, bytesund position bedeuten, wieviel Bytes von welcher Position an gelesen werdensollen.

m ein out-Parameter wird vom Server an den Client gesendet, z.B. verweist buf aufdie Adresse, an die der Server die Daten ablegt, die der Client angefordert hat.

m außerdem gibt es in/out-Parameter, die vom Client an den Server gesendet wer-den, dort modifiziert und schließlich an den Client zurückgesendet werden.

Dem Client-Stub ist bekannt, welche Parameter er an den Server senden muß, demServer-Stub ist bekannt, welche er zurücksenden muß.

Die formale Spezifikation wird in einem sog. Stub-Generator eingegeben, der dar-aus sowohl Client- als auch Server-Stub erzeugt. Beide Stubs werden anschließend inentsprechenden Bibliotheken abgelegt. Ruft der Client ein Unterprogramm auf, so wirddas dazugehörige Client-Stub-Unterprogramm dazugebunden. Dies geschieht zur


- 24 -

Laufzeit mit der aktuellen Adresse des zuständigen Servers und anderen Parametern;es sind allerdings auch Variationen dieses Verfahrens möglich. Der Server-Stub wirdanalog bei der Übersetzung des Server-Codes hinzugebunden. Zu Beginn einer Server-ausführung erfolgt (beim dynamic binding) der Aufruf von initialize () - dieser bewirktdas Exportieren der Schnittstelle des Servers. Der Server sendet hierzu eine Nachrichtan ein Programm, das Binder genannt wird, und gibt damit seine Existenz bekannt.Man bezeichnet diesen Vorgang als Registrierung des Servers.

Dabei übergibt der Server dem Binderm seinen Namen,m die Versionsnummer sowie ggfs. einen eindeutigen Bezeichner undm ein sog. Handle, das zur Lokalisierung des Servers dient, z.B. Ethernet- oder IP-

Adresse.Möchte der Server keinen Dienst mehr anbieten, so läßt er sich „entregistrieren“.Mit diesen Voraussetzungen ist dynamisches Binden möglich, das folgendermaßengeschieht:m Der Client ruft zum ersten mal ein entferntes UP, z.B. read, auf.m Der Client-Stub erkennt daraufhin, daß der Client an noch keinen Server gebun-

den ist.m Der Client-Stub sendet eine Nachricht an den Binder, um z.B. Version 3.1 der

Schnittstelle file_server zu importieren.Der Binder überprüft, ob (ein oder mehrere) Server eine Schnittstelle mit diesem Na-men und der entsprechenden Versionsnummer exportieren. Ist das nicht der Fall, soschlägt die Operation fehl. Falls andererseits ein passender Server existiert, so liefertder Binder das Handle und den eindeutigen Bezeichner an den Client-Stub zurück. DerClient-Stub benutzt das Handle als Adresse, an die er die Anfragenachricht sendet. DieNachricht enthält die Parameter und den eindeutigen Bezeichner, mit dem der richtigeServer ausgewählt wird, falls mehrere existieren.

Der Vorteil dynamischen Bindens ist die hohe Flexibilität. Der Binder kannm den Server in regelmäßigen Abständen überprüfen und ggfs. entregistrieren,m bei identischen Servern und Clientanfragen die Auslastung steuern (Load Ba-

lancing),m Authentifikation unterstützen.Demgegenüber hat das dynamische Binden aber auch Nachteile:m Es bedeutet zusätzlichen Aufwand für das Im- und Exportieren von Schnittstel-

len.m In großen Systemen kann der Binder zum Engpaß werden, so daß mehrere Binder

benötigt werden. Dies führt dazu, daß beim Registrieren und Entregistrieren vieleNachrichten verschickt werden müssen.

Solange sowohl Client als auch Server fehlerfrei funktionieren, erfüllt der RPC seineAufgabe sehr gut. Treten jedoch Fehler auf, so gibt es Unterschiede zwischen lokalemund entfernten Aufruf. Man unterscheidet 5 Klassen von Fehlerquellen in RPC-


- 25 -

Systemen:1. Client kann Server nicht lokalisieren,

z.B. weil kein passender Server ausgeführt wird (Versionsproblem o.ä.).Lösungsmöglichkeiten:

• Fehlertyp anzeigen lassen und reagieren oder

• Ausnahmebehandlung auslösen.2. Anfragenachricht von Client an Server geht verloren.

Ist einfach zu lösen: Kern wiederholt Anfrage nach einem Timeout.3. Antwort von Server an Client geht verloren.

Ist schwieriger als Fall 2): man unterscheidet idempotente Nachrichten undnicht idempotente. Eine idempotente Nachricht kann beliebig oft wiederholt wer-den, ohne daß sich das Ergebnis ändert, etwa das Lesen der ersten 1024 Bytes ei-ner Datei. Das Ergebnis einer nicht idempotenten Nachricht ist von der Anzahldes Eintreffens einer Nachricht abhängig, z.B. das Überweisen von 1000 DM aufein Konto.Es dürfen nur idempotente Nachrichten wiederholt werden, d.h. man muß eineSequenznummer beim Senden einfügen oder zwischen Original und Wiederho-lung unterscheiden.

4. Der Server fällt nach Erhalt einer Anfrage aus.Hierbei müssen drei Fehler unterschieden werden:

Empfang Empfang EmpfangAusführung Ausführung

Antwort Aus fal lAus fal l

REQ

REP

REQ REQ

No REP No REPa) b) c)

Abb. 2.14:Serverausfall nach Erhalt einer Anfrage

a) ist Normalfall,

b) ist gleichbedeutend damit, daß die Anfrage nie angekommen ist (→Wieder-holung),c) bedingt, daß der Fehler dem Client gemeldet werden muß.

ABER: Wie soll der Client b) und c) unterscheiden ?5. Der Client fällt aus, nachdem eine Anfrage gestellt wird.

Dann wird die Berechnung ausgeführt, obwohl niemand auf eine Antwort wartet(„verwaiste Berechnung“). Dies verschwendet Rechenzeit und kann zu Konfu-sionen führen, wenn der Client danach eine neue Anfrage startet und darauf dasalte Ergebnis eintrifft. Für dieses Problem gibt es 4 Lösungen von Nelson:m Ausrottung: Eine externe Protokollierungsdatei terminiert Waisen nach Neu-

start.


- 26 -

m Reinkarnation: Jeder Neustart bestimmt eine neue Epoche (linear aufsteigend).m sanfte Reinkarnation: In einer neuen Epoche wird versucht, im Verteilten Sy-

stem entfernte Besitzer zu finden.m Verfallszeitpunkte: Feste Zeitdauern T werden vereinbart, in denen eine An-

wort da sein muß oder erneut angefordert werden muß.

2.2.2 Implementierungsaspekte

Zugrundeliegende Konzepte und die Art ihrer Implementierung bestimmen die Lei-stungsfähigkeit eines Verteilten Systems und dessen Erfolg.m Soll man verbindungslose oder verbindungsorientierte Protokolle nutzen?

Der Vorteil verbindungsorientierter Protokolle liegt in der starken Vereinfachungder Kommunikation, d.h. wenn der Kern eine Nachricht sendet, so braucht er sichnicht darum zu kümmern, ob diese verlorengeht und kann den Austausch von Be-stätigungen erledigen. Die Sicherung wird von der Software auf niedriger Ebeneerledigt. Durch zusätzliche Software geht alklerdings auch Leistungsfähigkeitverloren. Man entscheidet sich daher bei einem relativ sicheren Netz für verbin-dungslose Protokolle.

m Soll man die Protokolle RPC-spezifisch entwickeln oder allgemeine Standardsnutzen?

In der Regel benutzen Verteilte Systeme IP (oder UDP, das auf IP aufbaut) alsBasisprotokoll. Dabei macht man sich den Vorteil zunutze, daß dieses Protokollbereits existiert und somit keine Entwicklungsarbeit mehr investiert werden muß.Im übrigen können die Pakete von fast allen UNIX-Systemen gesendet, empfan-gen und über viele Netze übertragen werden.

m Wie soll die Bestätigung geregelt werden?Hierfür gibt es verschiedene Möglichkeiten:

1

2

3

0ACK 0

ACK 1

ACK 2

ACK 3

"Stop-And-Wait"-Protokoll

1

2

3

0

ACK 0-3

"Blast"-Protokoll

Abb. 2.15: Möglichkeiten zur Bestätigung


- 27 -

Bei Stop-and-wait braucht das fehlerhafte Paket einfach nur wiederholt zu wer-den, beim Blast-Protokoll muß eine Entscheidung getroffen werden, ob komplettneu übertragen wird, oder ob man zwischenspeichert und das fehlerhafte Paketneu anfordert (selective repeat). Selective repeat ist nur mit großem Aufwand zuimplementieren, senkt aber die Netzbelastung.

m Wie sieht die Flußkontrolle aus?Bei einer begrenzten Pufferkapazität können Pakete verlorengehen, wenn kurzaufeinanderfolgend viele Pakete eintraffen (overrun error, Überschreitungsfeh-ler). Beim Stop-and-wait-Protokoll kann (im Gegensatz zum Blast-Protokoll)kein Überschreitungsfehler auftreten.

2.2.3 Kritische Pfade

Ein kritischer Pfad (critical path) ist die Folge von Instruktionen, die bei jedem RPCausgeführt werden. Dieser beginnt mit dem Aufruf des Client-Stubs durch den Client,geht dann über zum Kern, beschreibt die Nachrichtenübertragung, die Server-Seite, dieAusführung des Unterprogramms und die Rückantwort. Genauer:

Client-Seite:1. Im Client: Rufe Stub-Routine auf

→ Ab sofort Aktionen im Client-Stub.2. Bereite Nachrichtenpuffer vor, d.h. erzeuge Puffer, um Anfragenachricht

zusammenzustellen.3. Verpacke die Parameter im Puffer. d.h. konvertiere sie in ein geeignetes

Format.4. Fülle den Nachrichtenkopf aus.5. Berechne die Prüfsumme.6. Führe den Systemaufruf aus.

→ Ab sofort Aktionen im Client-Kern

• Der Kern rettet den Inhalt des Prozessorregisters und der Adreßtabelle, dieer benutzt.

• Die Nachricht wird in den Kern kopiert, da sie sich zur Verarbeitung in sei-nem Adreßraum befinden muß.

• Die Zieladresse wird bestimmt.

• Die Adresse wird in den Nachrichtenkopf eingetragen.

• Die Netzwerkschnittstelle wird initialisiert.7. Füge das Paket zur Übertragung in die Warteschlange ein.8. Übertrage das Paket über den Bus zum Steuerwerk.9. Übertrage das Paket über Ethernet.

→ Ende der Client-Seite.

Server-Seite:10. Im Server-Kern: Hole Paket beim Steuerwerk ab.


- 28 -

11. Unterbrechungsbehandlungsroutine12. Überprüfe, ob das Paket korrekt übertragen wurde, d.h. berechne die Prüf-

summe.

• Entscheide, welcher Stub die Nachricht erhält.

• Überprüfe, ob Stub wartet. Ansonsten wird die Nachricht abgelehnt oderzwischengespeichert.

• Kopiere die Nachricht in den Server-Stub.13. Kontextwechsel in den Server-Stub.

→ Ab sofort Aktionen im Server-Stub14. Packe die Parameter aus, lege die Parameter auf dem Stack ab und rufe

dann den Server auf.

• Der Server führt den Auftrag aus.Die Frage, die sich bei der Implementierung des RPCs stellt, ist nun, welcher Teil

des kritischen Pfades der aufwendigste ist, also am meisten Rechenzeit in Anspruchnimmt. Die Schwachstellen müssen analysiert und dann die Ausführung optimiert wer-den. 1990 haben Schroeder und Burrows den kritischen Pfad einer Multiprozessor-Workstation analysiert, und zwar

a) für einen „leeren RPC“, d.h. den Aufruf eines entfernten Unterprogramms oh-ne Datenübertragung,

b) für einen RPC mit einem 1440 Byte-Feld als Parameter. Dieses Feld muß alsoverpackt und als Nachricht übertragen werden.

Bearbeitungsnr. im kritischen Pfad Bearbeitungsnr. im kritischen Pfad

Aba

rbei

tung

sant

eili

n%

Aba

rbei

tung

sant

eili

n%

Client-Stub Client-Kern NETZ Server-Kern Server-Stub Client-Stub Client-Kern NETZ Server-Kern Server-Stub

a) "Leerer RPC" b) RPC mit 1440 Byte-Feld

Abbildung 2.16:Analyse eines kritischen Pfades

Interpretation: Beim „leeren RPC“ entstehen die meisten Kosten durchm den Kontextwechsel in den Server-Stub, d.h. das Retten des Inhalts von Prozes-

sorregister und Adreßtabelle und Laden der benötigten Adreßtabelle. (13.)m die Unterbrechungsbehandlungsroutine im Server-Kern (11.) undm das Übergeben des Pakets an die Netzwerkschnittstelle im Client-Kern (8.).


- 29 -

Beim „1440-Byte-RPC“ gibt es andere Engpässe:

m Die Paketübertragung über Ethernet (9.),m das Übergeben des Pakets an die Netzwerkschnittstelle im Client-Kern (wie oben,

8.)m Entnehmen des Pakets von der Netzwerkschnittstelle im Server-Kern.

Zu beachten ist allerdings, daß man diese Meßergebnisse so nicht ohne weiteres verall-gemeinern kann, da sie sich nur auf das zugrundeliegende Multiprozessorsystem be-ziehen. Die Meßwerte basieren auf einer bereits angepaßten Implementierung, die aberhinsichtlich gewisser Aspekte noch weiter verbessert werden kann:

m Das Kopieren von Daten beeinflußt die Ausführungszeit eines RPC’s ganz we-sentlich. Man wird sich also bemühen, einerseits so wenige Kopiervorgänge wiemöglich zu benötigen und diese dann andererseits so effizient wie möglich zu ge-stalten. Im Idealfall wird die Nachricht aus dem Adreßraum des Client-Stubs di-rekt auf das Netzwerk ausgegeben (Kopiervorgang 1) und in Echtzeit in denSpeicher des Server-Kerns abgelegt bzw. umgekehrt (Kopiervorgang 2). Imworst-case benötigt man 8 Kopiervorgänge (vgl. [Tan92]). Durchschnittlich be-nötigt das Kopieren eines 32-Bit-Wortes etwa 500 Nanosekunden, d.h. man be-nötigt etwa 4 Mikrosekunden bei 8 Kopiervorgängen (unabhängig von der Netz-schnelligkeit). Bei der Implementierung muß also ein Kompromiß zwischenkomplizierten Mechanismen und zeitaufwendigen Kopiervorgängen gefundenwerden.

m Ein anderer Aspekt ist die Verwaltung von Stoppuhren. Hierfür muß eine Da-tenstruktur erzeugt werden, die angibt, wann die Stoppuhr ablaufen soll und wasin diesem Fall zu unternehmen ist. Man kann hierfür eine verkettete Liste ver-wenden, die alle laufenden Uhren enthält und ein Sortieren nach Ablaufzeiten(timeouts) regelt:

1420aktuelle Zeit

1425Prozeß 3

1438Prozeß 1

1510

Prozeß 0

Ablaufzeitpunkte ineiner verketteten Liste

1420aktuelle Zeit

Ablaufzeitpunkte ineiner Prozeßtabelle

1510

1438

0

1425

(= Anhalten einerStoppuhr)

alternativ:

Abb. 2.17:Verwaltung von Stoppuhren


- 30 -

Trifft eine Antwort oder Bestätigung vor dem Ablaufen einer Stoppuhr ein, so mußder zugehörige Eintrag aus der Liste entfernt werden. In der Praxis werden nurwenige Stoppuhren ablaufen, somit macht das Eintragen/Entfernen die meisteArbeit.

2.3 Kommunikation in Verteilten Systemen

Im folgenden sollen Kommunikationsformen in Verteilten Systemen untersuchtwerden. Beim RPC wird von einer Zwei-Parteien-Kommunikation ausgegangen. Eskönnen sich jedoch auch andere Kommunikationsformen als notwendig erweisen. Diesist zum Beispiel der Fall, wenn eine Gruppe von Datei-Servern miteinander kooperiert,um einen einzelnen (fehlertoleranten) Dateidienst anzubieten. Hier muß der Client eineNachricht an alle Server senden. Nur so kann man sicherstellen, daß - auch bei Ausfalleines Servers - eine Anfrage ausgeführt wird. Aus diesem Beispielszenario folgt dieNotwendigkeit eines zum RPC alternativen Kommunikationsmechanismus, mit demman eine Nachricht an mehr als einen Empfänger schicken kann.

2.3.1 Grundbegriffe

Def.: Eine Gruppe ist eine Menge von Prozessen, die miteinander kooperieren, d.h.auf eine vom Benutzer oder System festgelegte Art und Weise zusammenarbei-ten.

Eine Gruppe besitzt folgende Eigenschaften:

• Wird eine Nachricht an eine Gruppe gesendet, so wird die Nachricht von allenMitgliedern der Gruppe empfangen:

Sender Empfänger Sender

Empfänger

Empfänger

Empfänger Empfänger

Bislang: Nun:

"Punkt-zu-Punkt"-Kommunikation oder"Eins-zu-Eins"-Kommunikation

"Punkt-zu-Mehrpunkt"-Kommunikation oder"Eins-zu-Viele"-Kommunikation

Abb. 2.18:Punkt-zu-Punkt- vs. Punkt-zu-Mehrpunkt-Kommunikation

• Gruppen sind dynamisch, d.h. neue Gruppen können erzeugt und existierendeGruppen aufgelöst werden; Gruppenmitgliedschaften brauchen nicht disjunkt zu


- 31 -

sein. Wird ein Paket an eine Gruppenadresse gesendet, so erfolgt die Übertragung automatischan alle Rechner, die dieser Adresse angehören. Diesen Prozeß bezeichnet man als Mul-ticasting. Multicasting ist die Alternative zum Broadcasting, wobei eine Nachricht an alle Rechnerübertragen wird und zum Unicasting, wobei n-mal vom Sender zu je einem Empfängerübertragen wird. Abb. 2.14 veranschaulicht die verschiedenen Übertragungsverfahren.

Empfänger

Sender

Empfänger

Empfänger

Empfänger

Empfänger

Sender

Empfänger

Empfänger

Empfänger

Empfänger

Empfänger

Empfänger

Empfänger

Sender

Multicast Broadcast Unicast

Abb. 2.19:Verschiedene Übertragungsverfahren

Die Gruppenkommunikation kann zum Beispiel bei replizierten Dateiservern angewendetwerden. Sie wird auch insbesondere bei der sog. Groupware verwendet, die die Com-puterunterstützung von Arbeitsgruppen oder Projektteams bezeichnet. Der Schwer-punkt liegt hier auf der Zusammenarbeit der einzelnen Mitarbeiter. Ein verwandterAnsatz findet sich beim Computer Supported Cooperative Work (CSCW). Groupwareläßt sich wie folgt kategorisieren:

Tabelle 2.1:Klassifikation von Gruppenkommunikationssoftware

ZeitOrt

gleichzeitig zeitlich versetzt

zentral Group Decision SupportSystem

Projektmanagementsoftware

verteilt Video Konferenz,Server Sharing

Mail-System,Textsystem für Autorengrup-

pen

Beim Entwurf von Gruppenkommunikationsdiensten müssen die gleichen Entwurf-sentscheidungen getroffen werden, wie beim 2-Parteien-RPC hinsichtlich Adressie-rung, Blockierung, Pufferung und Zuverlässigkeit. Die neue Komplexität der Archi-tektur bedingt jedoch prinzipiell 9 weitere Aspekte (von denen auf die wichtigsten imfolgenden eingegangen werden soll), die bei Punkt-zu-Punkt-Kommunikation keineRolle spielen.


- 32 -

Die Adressierung an die Gruppe erfolgt entweder durch

• Einrichtung einer eigenen Multicastadresse für die Gruppe,

• oder durch Broadcasting und Entscheidung des Kerns, ob er zur Gruppe ge-hört,

• oder durch Prädikatadressierung, bei der die Nachricht ein Prädikat enthält, dasausgewertet wird und damit die Annahme der Nachricht bestimmt.

geschlossene Gruppe

außenstehende Mitglieder könnenNachrichten nur an einzelne Gruppen-mitglieder und nicht an die gesamteGruppe senden

offene Gruppe

außenstehende Mitglieder könnenNachrichten nur an einzelne Gruppen-mitglieder und nicht an die gesamteGruppe senden

Abgeschlossenheit der Gruppe:

Strukturierung der Gruppe:

hierarchische Gruppe

symmetrische Struktur; bei Ausfalleiner Komponente wird die Gruppekleiner, arbeitet aber weiter

Ausfall des Koordinators bringtGruppe zum Stillstand, aber Koordinatorkann ggfs. Entscheidungen treffen, z.B.Ein-/Austritt eines Mitglieds

demokratische Gruppe

Koordinator

Abb. 2.20: Aspekte der Gruppenkommunikation

Desweiteren müssen die Sende- und Empfangsprimitive für die Gruppe ab group_sendund group_receive modifiziert und angepaßt werden.

Damit die Gruppenkommunikation einfach benutzbar ist, braucht man 2 weitereEigenschaften:

• Atomarität: Ein Multi- oder Broadcast wird immer entweder an alle oder ankein Mitglied der Adressatengruppe geschickt.

• Nachrichtenreihenfolgeeinhaltung (später im Kapitel über Synchronisation).

- 33 -

3 Synchronisation in

Verteilten Systemen

Bisher wurde behandelt, wie zum Zweck der Kommunikation Anfrage- und Ant-wortnachrichten ausgetauscht werden. In diesem Kapitel soll nun untersucht werden,wie Kooperation und Synchronisation auf Prozeßebene aussehen. Die klassischenMittel bei Einprozessorsystemen mit gemeinsamem Speicher sind aus der Vorlesung„Systemprogrammierung“ bekannt: Kritische Bereiche, wechselseitiger Ausschlußmittels Semaphoren, Monitoren oder Regions. Diese Ansätze sind in Verteilten Syste-men nicht realisierbar, da z.B. von verteilten Komponenten auf ein Semaphor zugegrif-fen werden müßte und dies Probleme mit sich bringt.

3.1 Uhrensynchronisation

In Synchronisationsverfahren spielt die Zeit i.d.R. die Hauptrolle. In Verteilten Sy-stemen steht aber keine allgemeine Uhr, d.h. keine globale Zeitquelle zur Verfügung,da die Gesamtheit relevanter Informationen zum Zwecke einer Auswertung nicht aneiner Stelle gesammelt wird. Dies folgt aus der Forderung, daß Verteilte Systeme feh-lertoleranter, zuverlässiger und ausfallsicherer als zentrale Systeme sein sollen.

Rechner A

Rechner B

9:44:00 9:44:01 9:44:02 9:44:03 9:44:04

9:43:58 9:43:59 9:44:00 9:44:01 9:44:02

Nachricht

t

t

Abb. 3.1: Verschiedene Systemzeiten

Abb. 3.1 zeigt zwei Rechner, die jeweils unterschiedliche Systemzeiten besitzen. Da

Verteilte Systeme 3. Synchronisation in Verteilten Systemen

- 34 -

Rechner B nachgeht, hat das Ereignis der Ankunft einer Nachricht (9:44:00) einen frü-heren Zeitpunkt als das Abschicken auf Rechner A (9:44:01). Für die meisten Zweckereicht es aus, daß sich alle Rechner auf eine Zeit verständigen, auch wenn diese nichtmit der realen Zeit übereinstimmt, d.h. es soll lediglich interne Konsistenz realisiertwerden. Diese Problemstellung führt zum Konzept der logischen Uhren.

3.1.1 Logische Uhren

Diese Uhren ermöglichen es, ein „temporal ordering“, d.h. eine zeitliche Reihenfolgevon Ereignissen zu bestimmen. Dazu muß die Uhrenabweichung im Verteilten System(0 bzw.) minimal sein. Den Grundstein hierfür legte Lamport 1978 in seiner klassi-schen Arbeit [Lam78]. In dieser Arbeit definierte Lamport für 2 Ereignisse a und b ei-ne Relation „vor“, in Zeichen a→b („a tritt vor b ein“). Dies bedeutet, daß alle Prozes-se darin übereinstimmen, daß zunächst Ereignis a und danach Ereignis b eintritt, wenn

1. a und b Ereignisse desselben Prozesses sind, und a tritt vor b ein, oder2. a ist ein Ereignis, das dem Senden einer Nachricht durch einen Prozeß entspricht,

und b ein Ereignis, das dem Empfangen einer Nachricht durch einen anderen Pro-zeß entspricht (Eine Nachricht kann nicht empfangen werden, bevor sie gesendetwurde).

Für die Relation „vor“ gilt

m Transitivität: a→b und b→c impliziert a→c.

Treten zwei Ereignisse x und y in verschiedenen Prozessen ein, die keine Nachrichtenaustauschen, so gilt weder x→y noch y→x und die Prozesse werden als nebenläufigbezeichnet. Man kann dann keine Aussage über deren Reihenfolge machen.Es wird nun für ein Ereignis eine Funktion C eingeführt, die dieses Ereignis auf dieZeit des Eintreffens dieses Ereignisses abbildet. Dabei wird die Forderung gestellt, daßwenn a→b gilt, auch C(a)<C(b) gelten muß.Lamports Algorithmus basiert nun auf den folgenden Punkten:m Das Empfangen einer Nachricht passiert nach dem Senden,

m eine Uhrzeit C schreitet stets positiv fort, und

m eine Angleichung von Uhrzeiten geschieht durch das Addieren positiver Werte.

0

6

12

18

24

30

36

42

48

54

0

8

16

24

32

40

48

56

64

72

10

20

30

40

50

60

70

80

90

0

6

12

18

24

30

36

42

60

66

0

8

16

24

32

40

51

59

67

75

10

20

30

40

50

60

70

80

90

0 0

(1)

(2)

(3)

(4)

(1)

(2)

(3)

(4)

Korrektur


- 35 -

Abb. 3.2:Uhrenkorrektur nach Lamport

Abb. 3.2 zeigt in einem Beispiel drei Prozesse, die jeweils eine eigene Uhr besitzen.Die Uhren laufen zudem mit unterschiedlichen Geschwindigkeiten. Man erkennt, daßwenn die Uhr von Prozeß 1 den Wert 6 hat, die Uhr von Prozeß 2 den Wert 8 und dieUhr von Prozeß 3 den Wert 10 hat. Prozeß 1 schickt nun eine Nachricht A zum (loka-len) Zeitpunkt 6 an Prozeß 2. Diese Nachricht erreicht Prozeß 2 zum (lokalen) Zeit-punkt 16. Man beachte, daß dies dem Zeitpunkt 12 auf dem Rechner von Prozeß 1 ent-spricht. Hier sind also bis zum Eintreffen 6 Zeiteinheiten vergangen, während für Pro-zeß 2 schon 8 Zeiteinheiten seit dem Absenden vergangen sind.Bei näherer Betrachtung von Nachricht C wird das eigentliche Problem offensichtlich:Nachricht C wird zum Zeitpunkt 60 gesendet und kommt zum Zeitpunkt 56 bei Prozeß2 an. Auch Nachricht D kommt bei Prozeß D früher an, als sie abgesendet wurde. Diesist jedoch zu vermeiden. Lamports Lösung ist im Prinzip sehr einfach: Wenn die Nach-richt C zum Zeitpunkt 60 abgesendet wurde, so darf sie frühestens zum Zeitpunkt 61ankommen. Trifft nun eine Nachricht bei einem Empfänger ein, dessen Uhr einen klei-neren Wert zeigt als der Sendezeitpunkt der Nachricht, so setzt der Empfänger seineUhr auf den Wert, der um 1 größer ist als der Sendezeitpunkt. Ab diesem Wert läuftdie lokale Uhr dann wie vorher weiter.Mit einer Erweiterung erfüllt der Algorithmus auch unsere Anforderungen an eine totalgeordnete Zeit:

3. Zwei Ereignisse treten nie zum gleichen Zeitpunkt auf.

Dies läßt sich zum Beispiel dadurch erreichen, indem man die Prozeßnummer desentsprechenden Prozesses an den Eintrittszeitpunkt, durch ein Komma getrennt, an-hängt. Mittels 1. - 3. erhält man eine totale Ordnung aller Ereignisse in einem Verteil-ten System.

In einigen Systemen (z.B. Realzeitsystemen) ist jedoch auch die reale Zeit wichtig.Hierfür braucht man dann externe, sog. physikalische Uhren.

3.1.2 Physikalische Uhren

Wegen Redundanz hinsichtlich Fehlertoleranz und anderen Aspekten sind in Ver-teilten Systemen mehrere physikalische Uhren wünschenswert. Die Probleme, die da-bei auftreten, sind

a) Wie werden diese Uhren mit realen Uhren synchronisiert undb) wie werden sie untereinander synchronisiert.

Diese Probleme erweisen sich als sehr schwierig und sollen deshalb hier nur angerissenwerden. Dazu soll zunächst die Historie der Zeitmessung betrachtet werden.

Die Zeit wurde bis zum 17. Jahrhundert astronomisch gemessen. Jeden Tag geht dieSonne im Osten auf und im Westen unter. Wenn die Sonne am Mittag ihren höchstenStand erreicht hat, so nennt man dieses Ereignis Sonnendurchlauf. Die Distanz zwi-schen zwei Sonnendurchläufen wird Sonnentag genannt. Da jeder Tag aus 24 Stundenzu je 3600 Sekunden besteht, ist die Sonnensekunde als der 864000te Teil eines Son-


- 36 -

nentages definiert. Mit der Einführung mechanischer Uhren hatte man erstmals dieMöglichkeit, die Zeit unabhängig von der Sonne zu messen. Da sich die Erde jedochnicht gleichmäßig dreht, ist auch der auf der Sonnensekunde beruhende Sekundenbe-griff ungenau (Geologen wiesen durch Untersuchungen an 300 Millionen Jahren altenKorallen nach, daß das Jahr damals aus 400 Tagen bestand).

Als 1948 die Atomuhr eingeführt wurde, konnte man den Begriff der Sekunde erheb-lich präzisieren. Eine Sekunde ist die Zeit, die ein Cäsium-133-Atom für9.192.631.770 Zustandsübergänge benötigt. Zur Zeit gibt es etwa 50 Einrichtungen aufder Welt, die über eine Cäsium-Uhr verfügen. Diese Einrichtungen teilen dem BureauInternational de l’Heure in Paris regelmäßig mit, wie ihre Uhren gehen. Aus demMittelwert errechnet sich die Internationale Atomzeit (TAI). Sie wird seit dem1.1.1958 berechnet (ganz präzise ausgedrückt, ist die TAI also die mittlere Anzahl vonZustandsübergängen der Cäsium-133-Uhren seit 0.00 Uhr am 1.1.1958 dividiert durch9.192.631.770).

Leider erweist sich aber sogar die TAI als ungenau. Dies hängt damit zusammen, daß86.400 TAI-Sekunden genau 3 Millisekunden kürzer sind als ein normaler Sonnentag.Die Rotation der Erde verlangsamt sich nämlich durch die Gezeitenreibung und dieTrägheit der Atmosphäre. Das heißt: die Anzahl der Tage pro Jahr wird bei konstanterJahreslänge kleiner, bzw. die Tage werden immer länger. Um diesen Effekt zu kom-pensieren, wurden vom BIH Schaltsekunden eingeführt, die man dann einfügt, wennder Unterschied zwischen TAI und Sonnenzeit auf 800 Millisekunden angewachsen ist(dies war seit 1958 schon etwa 30 mal der Fall). Die Zeit, die man aus der TAI durchdiese Korrektur erhält, heißt Universal Coordinated Time (UTC). Die UTC ist dieBasis der modernen Zeitrechnung, die die Greenwich Mean Time ablöste. Wenn eineSchaltsekunde einzufügen ist, so erhöhen die meisten Stromversorgungsunternehmenihre Frequenz 60 bzw. 50 mal von 60 bzw. 50 Hz auf 61 bzw. 51 Hz, um alle Uhren inihrem Versorgungsgebiet um 1 Sekunde vorzustellen. Ein Betriebssystem, das die ge-naue Zeit nachbilden möchte, muß jedoch über spezielle Software verfügen, um denEinfügeprozeß nachzuvollziehen, da die (meist sehr ungenaue) Stromfrequenz hiernicht zur Zeitmessung verwendet wird.

3.1.3 Algorithmen zur Uhrensynchronisation

Über Kurzwelle oder Satellit können Rechner die UTC empfangen. Macht einRechner hiervon Gebrauch, so muß man andere Rechner mit diesem synchronisieren.Es existieren hierzu verschiedene Algorithmen, die von Ramanathan 1990 (vgl.[RSB90]∞) untersucht und verglichen wurden. Diese Algorithmen gehen alle vom sel-ben Systemmodell aus:

Ein Rechner verfügt über eine Stoppuhr (Timer), d.h. der Timer enthält einenQuarzkristall, der unter Spannung mit einer definierten Frequenz schwingt. Außerdembesitzt der Rechner ein Zähl- und ein Laderegister. Das Zählregister wird bei einerSchwingung um eins vermindert. Hat der Zähler den Wert 0 erreicht, so wird eine Un-terbrechung ausgelöst, die man Uhrtick nennt. Anschließend wird der Zähler mit demWert des Laderegisters neu geladen. Beim Systemstart gibt der Operator Datum &


- 37 -

Uhrzeit an. Die Werte werden von diesem Zeitpunkt an dann vom Uhrtick aktualisiert(z.B. 60 mal pro Sekunde).Sei Cp(t) die Zeit zur UTC-Zeit t auf einem Rechner p. In einem idealen Verteilten Sy-

stem gilt dann Cp(t) = t, d.h. dC

dt= 1. Man spricht davon, daß eine Uhr innerhalb ihrer

Spezifikation arbeitet, wenn es eine Konstante ρ ρ ρ gibt, so daß 1-dC

dt ≤ ≤ +1 . Die

Konstante ρ wird vom Hersteller angegeben und heißt maximale Abweichung (vgl.Abb. 3.3).

dCdt

dCdt

dCdt

>1

=1

<1

normierte Uhrzeit UTC

Rechnerzeit C

schnelle Uhr

langsame Uhr

perfekte Uhr

Abb. 3.3: Langsame, perfekte und schnelle Uhren

3.1.3.1 Der Algorithmus von Christian (1989)

Die Voraussetzung für diesen Algorithmus ist ein Rechner, der eine Zeitbasis (z.B.UTC) liefert, ein sog. Zeitserver. Ziel ist es, andere Rechner mit ihm zu synchronisie-ren. Dazu sendet jeder Rechner regelmäßig eine Anfrage nach der aktuellen Uhrzeit anden Zeitserver (Abb. 3.4).

T0

T1

T2

T3t

anfragenderRechner

Zeitserver

I:=T - T ist die Zeit derUnterbrechungsbehandlung

12

I

Anfrage

Antwort:CUTC

Abb. 3.4: Zeitabfrage beim Zeitserver

Der Server setzt seine Uhr auf t CT T I

UTC= + − −3 0

2, d.h. er zählt zur UTC-Zeit noch

die Dauer einer Nachrichtenübertragung hinzu . Ist I nicht bekannt, so setzt man I=0.Problematisch ist, daß die Zeit nie rückwärts laufen darf. Dies wäre nämlich dann derFall, wenn die Uhr des aufrufenden Rechners zu schnell läuft und dann die lokale Zeit


- 38 -

später als die übermittelte CUTC ist. Somit kann das einfache Übernehmen der Informa-tion des Zeitservers Probleme bereiten. Eine Lösung wäre z.B. das Aufaddieren einerdefinierten Anzahl Millisekunden bei jeder Unterbrechung der Stoppuhr. Der Server istbei diesem Vorschlag passiv. Eine Alternative hierzu ist ein aktiver Zeitserver, der je-doch keine physikalische, sondern eine logische Uhrensynchronisation realisiert. Die-ser Algorithmus wird im folgenden vorgestellt.

3.1.3.2 Der Berkeley-Algorithmus

Hier wurde genau der umgekehrte Ansatz zu Christians Algorithmus gewählt und imBerkeley UNIX realisiert. Der Zeitserver wird Zeitdämon genannt und ist eine aktiveKomponente mit dem Ziel, die Zeit logisch zu synchronisieren. Das Verfahren eignetsich für Systeme, in denen keine exakte Zeit zur Verfügung steht.In regelmäßigen Abständen wird jeder Rechner nach seiner Zeit gefragt. Aus den er-haltenen Antworten wird der Durchschnitt berechnet und dieser den Rechnern mitge-teilt. Diese erhöhen die Uhrzeit auf den aktuellen Wert bzw. verlangsamen ihre Uhrdann. (vgl. Abb. 3.5). In der Abbildung a) sendet der Dämon seine aktuelle Zeit (3:00)an die angeschlossenen Rechner. Die jeweilige Zeitdifferenz wird in Teil b) an denDämon zurückgesendet. Dieser ermittelt die relative Abweichung, aus der dann dieneue Zeit (3:05) berechnet und abgeschickt wird.

3:00

3:25 2:50

3:00

3:25 2:50

3:05

3:25 3:05

3:00

3:00 3:00+0:25

0:00

-0:10 -0:20 +0:15

+0:05

+0:25- 0:10

0:000:15 / 3 = 0:05

geht ab jetztlangsamer

b) c)a)

Abb. 3.5: Synchronisation durch einen Zeitdämon

3.2 Wechselseitiger Ausschluß

Im folgenden soll zur Frage zurückgekehrt werden, wie Prozesse miteinander koope-rieren und wie sie sich synchronisieren lassen. Mehrprozessorsysteme werden häufigmit Hilfe von kritischen Bereichen programmiert. Ein kritischer Bereich ist ein Teileines Programms, in dem auf Ressourcen (z.B. Speicher) zugegriffen wird, die vonmehreren Rechnern oder Prozessen benutzt werden. Ist zu jedem Zeitpunkt gewährlei-stet, daß nicht mehr als ein Prozeß auf dieselben gemeinsam benutzten Ressourcen le-send oder schreibend zugreift, so können insbesondere keine Inkonsistenzen auftreten.Man spricht dann von wechselseitigem Ausschluß. In Einprozessorsystemen werden


- 39 -

kritische Bereiche z.B. durch Semaphore und Monitore geschützt (→Vorl. Systempro-grammierung). Diese Methoden sind für Verteilte Systeme nicht angemessen. Im fol-genden werden 3 Algorithmen angegeben, mit denen man in Verteilten Systemen kriti-sche Bereiche und wechselseitigen Ausschluß realisieren kann.

3.2.1 Der zentrale Algorithmus

Beim zentralen Algorithmus wird ein Einprozessorsystem simuliert. Ein Prozeßwird hier zum Koordinator ernannt (z.B. der mit der höchsten Netzwerkadresse). DerKoordinator gewährleistet, daß sich zu jedem Zeitpunkt höchstens 1 Prozeß in einembestimmten kritischen Bereich befindet.Der Algorithmus arbeitet in folgender Weise, wie in Abbildung 3.6 dargestellt. Möchteein Prozeß (Nr.1) in einen kritischen Bereich eintreten, so stellt er eine Anfrage an denKoordinator. Dieser hat Informationen darüber, ob sich bereits andere Prozesse im kri-tischen Bereich befinden oder der kritische Bereich -wie im Beispiel- zum Anfrage-zeitpunkt von keinem anderen Prozeß benutzt wird. In letzterem Fall wird seitens desKoordinators ein OK an die anfragende Einheit gesendet. Erfolgen weitere Anfragenvon Prozessen, die ebenfalls in den kritischen Bereich eintreten wollen (Nr. 3, 2, 4), sowerden die zugehörigen Prozeßnummern in der Reihenfolge ihres Anfragens in einerWarteschlange des Koordinators gespeichert. Gibt der benutzende Prozeß (Nr. 1) denkritischen Bereich mit einer Fertigmeldung frei, so erhält der am längsten wartendeProzeß ein OK und seine Prozeßnummer wird aus der Warteschlange entfernt.

1 2 3 4

K

1 2 3 4 1 2 3 4

1 2 3 4 1 2 3 4 1 2 3 4

KKK

KK

Warteschlange

3 32

324

24

4

Koordinator

1 2 3

4 5 6 usw.

Prozesse

(Anforderung & Zuteilung)

im KB

OKDarf Ich?

Darf Ich? Darf Ich?

Darf Ich?Fertig! OK OK

Fertig!

Freigabe

Warteschlange Warteschlange

Warteschlange Warteschlange Warteschlange

Abb 3.6: Zentraler Algorithmus

Die Vorteile des zentralen Algorithmus sind

• Fairneß: Die Reihenfolge der Anfrage bleibt erhalten und kein Prozeß wartetewig,


- 40 -

• die relativ einfache Implementierung der 3 Operationen Anforderung (= DarfIch?), Zuteilung (= OK) und Freigabe (= Fertig!).

Demgegenüber gibt es aber auch Nachteile:

• Der Koordinator bildet einen Engpaß.

• Der Koordinator darf nicht ausfallen. Insbesondere die Ausfallsicherheit stellt einen wesentlichen Aspekt dar. Daher hat mannach Alternativen zum zentralen Ansatz gesucht.

3.2.2 Der verteilte Algorithmus von Ricart und Agrawala

Voraussetzung hierfür ist eine totale Ordnung der Ereignisse im System, d.h. für je-des Paar von Ereignissen ist die Reihenfolge ihres Auftretens eindeutig bestimmt (diesläßt sich z.B. mit dem Algorithmus von Lamport erreichen).Das Prinzip: Wenn ein Prozeß in den kritischen Bereich eintreten will, so sendet ereine Anfragenachricht mit dem Namen des kritischen Bereichs, seiner Prozeßnummerund der aktuellen Zeit (total geordnet) an alle Prozesse des Verteilten Systems (alleanderen und sich selbst). Das Senden soll zuverlässig sein, d.h. jede Nachricht wirdbestätigt. Was passiert nun, wenn eine Komponente des Verteilten Systems eine solcheAnfrage erhält? Dazu sind drei Fälle zu unterscheiden:a) Der Empfänger befindet sich nicht im kritischen Bereich und will auch nicht in die-

sen eintreten → sendet OK an den Sender.

b) Der Empfänger befindet sich im kritischen Bereich → sendet kein OK, sondernmerkt sich die Anfrage in Warteschlange vor.

c) Der Empfänger will selbst in den kritischen Bereich, hat „fast“ zeitgleich eine eige-ne Anfrage abgesendet → er vergleicht die Zeitstempel der Nachrichten, der früheregewinnt.

Der Sender wartet auf alle OKs, dann tritt er in den kritischen Bereich (Kb) ein. BeimVerlassen sendet er OKs an alle Prozesse in seiner Warteschlange und entfernt dieProzesse hieraus (Vgl. Abb. 3.7).Vorteile dieses Algorithmus sind Fairneß und Deadlockfreiheit. Allerdings ist dieNetzwerkbelastung durch 2(n-1) Nachrichten für eine Anfrage bei n Komponenten imSystem recht hoch. Problematisch ist hier auch, daß bei Ausfall einer Komponente dieAntwort auf eine Anfrage nicht möglich ist, was ggfs. als Ablehnung interpretiert wird.Somit sind alle folgenden Versuche blockiert, in den kritischen Bereich einzutreten.Ein Ausweg wäre, daß falls nach einem Timeout noch keine Antwort eingetroffen ist,erneut eine Anfrage gestellt wird und dann ggfs. davon ausgegangen wird, daß derEmpfänger ausgefallen ist.Der Algorithmus ist also zwar verteilt, aber auch langsamer, komplizierter und wenigerrobust als der zentrale.


- 41 -

A

B C

D

6

6 611 8

811 6

811

11 8

Fast zeitgleich sendenA: 6B: 11C: 8um in den KB einzutreten

A

D

B C

CB

B

OK OKOK

A hat frühesten Zeitstempel und gewinnt.D sendet wegen a) OK an A, B und CB und C wegen c) ein OK an A, B auch an Calso hat A alle OKs, tritt in KB ein und merktsich C und B in seiner Warteschlange vor.

A

B C

D

A

B C

D

A

B C

D

A

B C

D

B A verläßt den KB, sendet OK an die wartendenProzesse C und B und löscht die Warteschlange.C hatte schon zuvor von B und D das OKbekommen und kann in den Kb eintreten.

C verläßt den KB, sendet OK an B.B hat nun alle OKs und kann in den KB eintreten

Abb. 3.7: Verteilter Algorithmus

3.2.3 Ein Token-Ring-Algorithmus

Gegeben seien n Prozesse. Auf diesen wird ein logischer Ring aufgebaut, in dem je-dem Prozeß (z.B. gemäß aufsteigender Netzwerkadresse) eine Position zugewiesenwird. Damit hat jeder Prozeß einen Nachfolger (der letzte Prozeß hat wieder den erstenals Nachfolger), vgl. Abb. 3.8.


- 42 -

1 2 537

1

7

3

2

5

Erhält bei Initialisierungein Token

Abb. 3.8: Token-Ring

Bei der Initialisierung erhält ein Prozeß ein Token. Will dieser Prozeß in einen kriti-schen Bereich eintreten, so hat er die Möglichkeit.Verläßt er den kritischen Bereich, sogibt er das Token an seinen Nachfolger. Will er nicht eintreten, so gibt er es gleichweiter. Will kein Prozeß in einen kritischen Bereich eintreten, so zirkuliert das Tokenmit hoher Geschwindigkeit im Ring. Der Algorithmus ist korrekt, da zu jedem Zeit-punkt nur ein Prozeß das Token besitzen und somit auch nur dieser Prozeß in den kriti-schen Bereich eintreten kann. Durch die Zirkulation ist gewährleistet, daß jeder Prozeßnur endlich lange auf den Eintritt in einen kritischen Bereich warten muß (bei unendli-cher Wartezeit spricht man auch von einem starvation problem).Probleme bei diesem Algorithmus sind der Verlust des Tokens und Ausfall eines Pro-zesses. Insbesondere das Entdecken des Tokenverlusts ist schwierig, da die Zeit zwi-schen zwei Token auf dem Netzwerk nicht begrenzt ist.Beim Vergleich der drei Algorithmen erweist sich der zentrale Algorithmus als amgünstigsten. Dieser erfordert jedoch die Benennung eines Koordinators. Diese Aus-wahl wird durch bestimmte Regeln (z.B. höchste Netzwerkadresse) oder sog. Wahlal-gorithmen getroffen.

3.3 Atomare Transaktionen

Die bisher kennengelernten Synchronisationsmechanismen befinden sich auf einemsemantisch niedrigen Niveau, d.h. der Programmierer ist gezwungen, sich mit Detailswie wechselseitigem Ausschluß, Deadlockvermeidung u.a. auseinanderzusetzen. DasZiel ist aber eine höhere Abstraktionsstufe, die technische Details verbirgt. Eine solcheAbstraktion wird in Verteilten Systemen häufig eingesetzt und als (atomare) Transak-tion bezeichnet.Das Prinzip: Zwischen zwei Parteien wird - Wie bei einem Vertrag - eine Vereinba-rung ausgehandelt, wer welche Leistungen zu erbringen hat. Diese Vereinbarung istatomar und kann nur ganz oder gar nicht ausgeführt werden.Beispiel: Ein Kaufhaus hat auf einem Magnetband den Bestand vom Vortag und

auf einem 2. Magnetband die Ein- und Verkäufe vom Tage gespeichert. EinComputer soll auf einem 3. Band den neuen Bestand berechnen. Falls einFehler auftritt, so werden alle Bänder zurückgespult und alles wiederholt.

Der Vorteil dieser Vorgehensweise liegt darin, daß beispielsweise bei einem Bankpro-gramm, welches Geld überweist (d.h. erst einen Betrag von einem Konto A abhebt unddanach den gleichen Betrag auf Konto B gutschreibt), ein Systemabsturz dazu führen


- 43 -

kann, daß sich das Geld „in Luft auflöst“.Für Transaktionen verwendet man folgendes Modell: Das verteilte System bestehe ausn unabhängigen Prozessen, die zufällig ausfallen können. Unsichere Kommunikationwerde von der Software auf unteren Schichten behoben. Ferner wird vorausgesetzt:m Stabiler Speicher: Da ein RAM-Inhalt bei Stromausfall verloren gehen kann und

ein Plattenspeicher bei einem Hardwaredefekt zu Problemen führen kann, erhältman einen stabilen Speicher z.B. durch redundante Abspeicherung auf Platten(z.B. doppelt mit Prüfsumme; bei unterschiedlichen Platteninformationen wirddie Platte mit korrekter Prüfsumme als richtig angenommen und die andere mitdiesen Informationen überschrieben).

Transaktionsprimitive müssen entweder vom Betriebssystem oder vom Laufzeitsy-stem einer Sprache zur Verfügung gestellt werden, z.B.:

BEGIN_TRANSACTIONEND_TRANSACTIONABORT_TRANSACTIONREAD, WRITE,...

Beispiel: FlugbuchungBEGIN_TRANSACTION {Flugbuchung Düsseldorf-St.Louis}

reserve DDorf-Frankfurtreserve Frankfurt-Chicagoreserve Chicago-St.Louis

END_TRANSACTION Ist der Flug Chicago-St.Louis ausgebucht, so folgt ABORT_TRANSACTION und

alle Reservierungen werden storniert. Transaktionen müssen drei Eigenschaften besitzen:

m Serialisierbarkeit: Nebenläufige Transaktionen haben aufeinander keine Auswir-kungen - es macht also keinen Unterschied, ob sie seriell oder parallel ausgeführtwerden.

m Atomarität: Eine Transaktion ist - von außen betrachtet - unteilbar.m Permanenz: Falls eine Transaktion gelingt, so sind alle durch diese Transaktion

ausgeführten Änderungen festgeschrieben. Oft wird auch der Begriff der ACID-Transaktion verwendet. Diese Abkürzung steht

für Atomarität, Nebenläufigkeit, Isolierung und Permanenz . Besitzen Transaktionen untergeordnete Transaktionen, so spricht man von geschach-

telten Transaktionen.

3.4 Deadlocks in Verteilten Systemen

...ähneln denen in Einprozesorsystemen, sind aber schlimmer!Zunächst wird die Deadlock-Erkennung in Verteilten Systemen behandelt. Wird ein


- 44 -

Deadlock in einem Verteilten System erkannt, das auf atomaren Transaktionen auf-baut, so wird der Deadlock durch den Abbruch der Transaktion behoben.

3.4.1 Zentrale Deadlock-Erkennung

Prinzip: Jeder Rechner verwaltet einen Betriebsmittelgraphen für seine Prozesse undBetriebsmittel. Zusätzlich verwaltet ein Koordinator den Betriebsmittelgraphen für dasGesamtsystem (als Vereinigung aller Einzelgraphen). Entdeckt der Koordinator einenZyklus, so bricht er zur Auflösung des Zyklus einen Prozeß ab. Im Unterschied zu ei-nem zentralen System müssen hier die einzelnen Komponenten ihre Betriebsmittelgra-phen explizit an den Koordinator senden (vgl. Fehler! Verweisquelle konnte nichtgefunden werden.).

fordert

belegt

A

B

R

S

Rechner 1:

Prozeß A belegt BM S undfordert R an, was von B belegt wird

Rechner 2:

S C

T

C belegt T und fordert S an

belegt

Koordinator:

A

B

R

S

A

B

R

S C

T

Normalfall:Konfiguration ist sicher:Ist B beendet, so erhält A das BM Rund gibt am Ende S für C frei

Abb. 3.9Zentrale Deadlock-Erkennung


- 45 -

Problem: B gibt R frei und fordert T an, aber beim Koordinator kommen die Nach-richten vom Rechner 1 (Freigabe von BM R) und Rechner 2 (Warten auf BMT) in verkehrter Reihenfolge an, so daß ein scheinbarer Deadlock entsteht.

Ausweg: Mittels des Algorithmus von Lamport kann man eine globale Zeit bereit-stellen und jeder Nachricht einen Zeitstempel geben.

3.4.2 Verteilte Deadlock-Erkennung

Zur verteilten Deadlock-Erkennung existieren verschiedene Algorithmen. Interes-sant ist dabei vor allem der Chandy-Misra-Haas-Algorithmus. Dieser Algorithmus hatden Vorteil, daß es den Prozessen gestattet ist, mehrere Betriebsmittel auf einmal stattnacheinander anzufordern.Modell:

Man schreibt statt einfach

oder

A R B A BR

A B

Man erhält z.B.:

A

B

B C DE

F

G H

I

Rechner 1 Rechner 2 Rechner 3wartet auf

Abb. 3.10: Verteilte Deadlock-Erkennung

Prinzip:Der Algorithmus wird aufgerufen, wenn ein Prozeß auf ein BM wartet, dasvon einem anderen Prozeß belegt wird.

Braucht beispielsweise ein Prozeß A ein Betriebsmittel von Prozeß B, so wird einesogenannte Untersuchungsnachricht erzeugt und an alle Prozesse gesendet, die diesesBetriebsmittel belegen. Diese Nachricht besteht aus

• dem Bezeichner des wartenden Prozesses,

• dem Bezeichner des sendenden Prozesses,

• dem Bezeichner des Prozesses, an den die Nachricht gesendet wird, also z.B. (A,A,B). Trifft die Nachricht ein, so überprüft der Empfänger, ob er auf das gleiche Betriebs-

mittel wartet. Ist dies der Fall, so werden Sender- und Empfängerfelder ersetzt, daserste Feld bleibt.

A B C DE

F

(A,A,B) (A,B,C) (A,C,D)(A,D,E)

(A,D,F)

...

...

(A,H,A) zum Schluß


- 46 -

Abb. 3.11: Prinzip von Chandy et. al

Kommt die Nachricht zum ursprünglichen Empfänger zurück, dann existiert ein Zy-klus, und das System befindet sich in einer Deadlock-Situation.

Hierfür gibt es verschiedene Möglichkeiten. Die einfachste ist, daß der initiierendeProzeß Selbstmord begeht. Dies kann allerdings Probleme mit sich bringen, falls evtl.2 Zyklen existieren. Alternativ hierzu könnte jeder Prozeß seine eigene Nummer an dieUntersuchungsnachricht anhängen, dann könnte der Prozeß mit der höchsten Nummerbeginnen.

Eine Alternative zur Deadlock-Erkennung ist die Deadlock-Vermeidung. Hier kon-struiert man die Systeme gleich so, daß Deadlocks nicht möglich sind.

- 47 -

4 Prozesse und Prozessoren

in Verteilten Systemen

Ging es bisher im wesentlichen um Kommunikation und Synchronisation in VerteiltenSystemen, so soll nun auf die Verwaltung der Prozesse näher eingegangen werden.Insbesondere umfaßt dies Aspekte zum den Kontrollflüssen innerhalb von Prozessoren,

m der Organisation von Prozessen und Prozessoren,

m der Zuteilung von Prozessoren und

m dem Scheduling.

4.1 Threads

In traditionellen Betriebssystemen verfügt jeder Prozeß über e i n e n Adreßraumund e i n e n einzelnen Kontrollfluß. Ziel in Verteilten Systemen ist es nun, mehrereKontrollflüsse innerhalb eines Adreßraums zuzulassen, die quasi-parallel ausgeführtwerden. Obwohl sie sich also den Adreßraum teilen, werden sie wie unabhängige Pro-zesse behandelt.

Es ist zum Beispiel denkbar, daß ein Dateiserver blockiert, um auf eine Festplatte zuwarten. Verfügt der Server über mehrere Kontrollflüsse, so kann ein zweiter ausgeführtwerden, während der erste wartet. Als Ergebnis erreicht man einen höheren Durchsatzund eine bessere Leistung. Allerdings kann dieses Ziel mit zwei Serverprozessen nichterreicht werden, da diese über einen gemeinsamen Cache verfügen müßten, der abereinen gemeinsamen Adreßraum erfordert. Es werden neue Mechanismen benötigt, diei.d.R. bisher nicht in Einprozessorsystemen zu finden sind. Prägnant zusammengefaßtist die Idee wie folgt: So, wie sich ein Rechner zu seinen Prozessen verhält, so soll sich

Verteilte Systeme 4. Prozesse und Prozessoren in Verteilten Systemen

- 48 -

ein Prozeß zu seinen Threads verhalten. Thread bedeutet ursprünglich Faden, Strahloder auch Garn.

Ein Thread ist also ein Ausführungspfad, der parallel zu anderen Threads abgear-beitet werden kann. Gemäß [Tr95] kann ein Thread auch als ein Prozeß definiert wer-den, der mit anderen, gleichartigen Threads Stack und Speicherraum gemeinsam hat,unter der Kontrolle eines Prozesses läuft und nicht vom Scheduler des Betriebssystemsverwaltet wird.

Abb. 4.1: Drei Prozesse mit jeweils einem Thread

m Jeder Prozeß besitzt einen eigenen Programmzähler, Stack, Registersatz und Adreß-raum.

m Prozesse sind unabhängig voneinander, außer daß sie über Kommunikationsprimiti-ve des Systems (Monitore, Semaphore, Nachrichten,… ) miteinander kommunizie-ren können.


- 49 -

Abb. 4.2: Ein Prozeß mit drei Threads

m Jeder Thread verfügt über seinen eigenen Programmzähler, Stack und Registersatz.

m Threads sind nicht so unabhängig wie Prozesse: Sie teilen sich einen Adreßraumund können so alle globalen Variablen gemeinsam nutzen.

Jeder Thread kann auf jede virtuelle Adresse zugreifen und folglich den Stack vonanderen Threads lesen, schreiben oder löschen. Ein Schutz davor ist nicht möglich undsollte in der jeweiligen Implementierung nicht notwendig sein.

Threads teilen sich - analog zu Prozessen - den einen Prozessor, d.h. die Threadswerden der Reihe nach im Timesharing ausgeführt. Eine Ausnahme bilden hierbei dieMultiprozessorsysteme, bei denen jeder Thread einen Prozessor exklusiv bekommt.Wenn ein Thread dann allerdings blockiert, wird der Prozessor einem anderen Threadzugeteilt. Dies erfolgt analog zu dem Fall, daß ein Prozeß blockiert und ein anderer aufdem Rechner zur Ausführung kommt. In vielerlei Hinsicht sind die Threads wie Mini-Prozesse, sie werden deshalb auch als leichtgewichtige Prozesse bezeichnet.

Zusammenfassend kann man festhalten: Ein Prozeß kann mehrere Threads erzeu-gen, die zusammenarbeiten und sich nicht behindern. Anders als verschiedene Prozes-se, die verschiedenen Benutzern gehören können (die sich mitunter auch nicht freund-schaftlich gesonnen sind), kann ein Benutzer auf alle Threads seines Prozesses zugrei-fen.

Threads befinden sich in einem von vier Zuständen:

m rechnend, d.h. dem Thread ist ein Prozessor zugeteilt,

m blockiert bzgl. eines Semaphors,

m rechenbereit auf die Zuteilung eines Prozessors wartend oder

m terminiert. Ein terminierter Thread muß von seinem Erzeuger „eingesammelt“ wer-den.

Bei der Benutzung von Threads erfolgt i.d.R. eine Kombination von Threads mit Sy-stem-Mailboxen (oder Warteschlangen) und einem Scheduler. Der Scheduler ist eineKomponente, die dem Prozessor die einzelnen, in der Ausführung befindlichen Pro-gramme (bzw. Threads) abwechselnd zuteilt, so daß eine quasi-parallele Verarbeitungstattfinden kann.

Als Beispiel zur Veranschaulichung soll das Konzept der ANSAware dienen: Zu-sätzlich zu den oben bereits genannten Komponenten werden noch sogenannte Taskseingeführt, von denen eine beliebige, jedoch feste Anzahl existiert. Ein Thread kannnur dann arbeiten, wenn ihm zuvor ein Task zugewiesen wurde, vgl. auch [PSW95].Dies geschieht durch den Scheduler.


- 50 -

Abb. 4.3: Konzept der ANSAware

Einem Task kann immer nur ein Thread zugewiesen sein. Beide bleiben solangemiteinander verbunden, bis der Thread terminiert. Übersteigt die Anzahl der Threadsdie der freien Tasks, so werden wartende Threads durch den Scheduler in einer Warte-schlange verwaltet, bis Tasks freiwerden.Die Zuordnung der Tasks zum Prozessor kann auf verschiedene Arten erfolgen:

Beim Verteiler-Arbeiter-Modell entnimmt ein Thread, der sogenannte Verteiler,alle Anfragen aus der System-Mailbox. Dann wählt er einen untätigen (blockierten)Arbeiter-Thread aus und übergibt ihm die Anfrage mittels einer Nachricht. Dadurchweckt er den Thread auf, d.h. die Blockierung ist beendet. Der Arbeiter überprüft, obdie Anfrage mit dem gemeinsamen Block-Cache, auf den alle Threads zugreifen kön-nen, erfüllt werden kann. Ist dies nicht der Fall, sendet er eine Nachricht an die Fest-platte, um den gewünschten Block anzufordern. Bis diese Festplattenoperation ausge-führt ist, legt er sich wieder schlafen, vgl. Abb. 4.3 a).

Im Team-Modell sind alle Threads gleich. Jeder Thread erhält und verarbeitet seineeigenen Anfragen ohne Verteiler. Sind Threads auf bestimmte Aufgaben spezialisiertund kann eine Anfrage von einem Thread nicht bearbeitet werden, so kann eine Listedie unerledigten Anfragen speichern. Ein Thread muß dann erst die Liste überprüfen,bevor er eine Anfrage aus der System-Mailbox entnimmt, vgl. Abb. 4.3 b).

Das Pipeline-Modell sollte nur für spezielle Anwendungen genutzt werden. Der er-ste Thread erzeugt Daten und übergibt sie zur Bearbeitung an den nächsten Thread.Auf diese Weise werden sie sukzessive durch die Threads geschleust. Bei jeder Wei-tergabe werden Berechnungen ausgeführt, vgl. Abb. 4.3 c).


- 51 -

Abb. 4.4: Zuordnungsmöglichkeiten der Tasks zum Prozessor

Einsatzmöglichkeiten von Threads in Verteilten Systemen sind viele denkbar. Ne-ben dem bereits erwähnten Datei-Server, der sich in viele einzelne Threads aufspaltenkann, wäre z.B. auch ein Client denkbar, der eine Datei auf mehreren Servern replizie-ren will und dabei für jeden Server einen eigenen Thread nutzt. Generell ist es günstig,immer dann, wenn ein Client auf ein Signal wartet, einem Thread diese Aufgabe zuübergeben.

In Verteilten Systemen werden sowohl RPCs als auch Threads verwendet.

4.2 Systemmodelle

Prozesse werden von Prozessoren ausgeführt. Klassische Systeme besitzen einenProzessor. Verteilte Systeme besitzen mehrere Prozessoren. Es stellt sich die Frage,welcher Prozessor benutzt werden soll. Prozessoren können in Verteilten Systemen aufverschiedene Weisen organisiert sein. Insbesondere gibt es zwei Grundformen: dasWorkstation- und das Prozessor-Pool-Modell.

4.2.1 Das Workstation-Modell

Die zugrundeliegende Architektur ist hier ein System aus leistungsfähigen PC’soder Workstations, welche über ein LAN verbunden sind. Alternativ besitzen dieWorkstations entweder lokale Festplatten oder sind plattenlos.

Im Falle plattenloser Workstations muß durch einen oder mehrere Dateiserver ir-gendwo im Netz ein Dateisystem zur Verfügung gestellt werden, das es ermöglicht,Dateien zu lesen bzw. zu schreiben. Ein wesentlicher Vorteil plattenloser Workstationsist sicherlich der geringere Anschaffungspreis. Die Kosten eines Dateiservers mit we-nigen, großen Platten liegen deutlich unter dem Preis für eine separate, kleine Fest-platte in jeder einzelnen Workstation. Darüber hinaus läßt sich die einfache Verwal-tung neuer Programmversionen anführen, die auf dem Dateiserver schneller installiert


- 52 -

sind, als auf jedem Rechner eines weit Verteilten Systems. Die Datensicherung mittelsBackup ist ebenfalls einfacher. Festplatten stellen u.U. eine Geräuschbelästigung darund sollten daher möglichst ausgelagert werden. Plattenlose Workstations unterstützendarüberhinaus das Prinzip von „Symmetrie und Flexibilität“, denn jeder Benutzer kannan jeder Workstation mit seinen Daten arbeiten. Allerdings hat der plattenlose Ansatzden Nachteil, daß das Netz stark belastet wird. Dateiserver können zu Engpässen wer-den.

Bei Workstations mit lokalen Festplatten unterscheidet man vier Varianten.1. Die lokalen Festplatten werden nur für das Paging und temporäre Dateien benutzt.

Es wird also weiterhin ein zentraler Datei-Server verwendet. Lokale Platten werdenzusätzlich für relativ kleine Datenmengen benutzt. Diese Daten können nicht ge-meinsam genutzt weren und werden i.d.R. am Ende einer Sitzung gelöscht.

2. Neben temporären Dateien werden ausführbare Systemprogramme wie z.B. Com-piler, Texteditoren oder Mail-Programme lokal gespeichert. Beim Programmaufrufentsteht so eine geringere Netzbelastung. Die Programme ändern sich selten und re-duzieren die Netzlast.

3. Zusätzlich zu den unter 2. aufgeführten Dateien kann der Nutzer explizit zusätzlicheDateien von dem Server auf seine lokale Platte laden. Am Ende der Sitzung könnendie modifizierten Dateien auf den Datei-Server zurückgespeichert werden. Das Re-sultat ist eine nochmalige Reduzierung der Netzlast. Allerdings tritt nun das Pro-blem auf, daß mehrere Benutzer evtl. auf die lokalen Kopien der selben Dateienmodifizierend zugreifen.

4. Die letzte Variante arbeitet mit einem vollständig lokalen Dateisystem. Ein Nutzerhat die Möglichkeit, Dateisysteme anderer Rechner zu importieren. Im wesentlichenarbeitet er jedoch lokal und hat eine gleichmäßige, garantierte Antwortzeit. DieNetzlast ist gering. Die gemeinsame Nutzung von Daten wird allerdings erschwert.Ein solches System ist eher ein Netzwerkbetriebssystem als ein wirklich transpa-rentes, verteiltes Betriebssystem.

Man kann die Idee der plattenlosen Workstation noch weiterführen und zusätzlichzu den Datei-Servern auch „Rechen-Server“ einführen.

4.2.2 Das Prozessor-Pool-Modell

Bei diesem Ansatz steht eine größere Menge Prozessoren zur Verfügung, die nachAnforderung dynamisch verteilt werden. Dies bringt eine Reihe von Vorteilen mit sich.Die Kosten für Stromversorgung, Gehäuse etc. reduzieren sich. Das Modell nach Abb.4.5 erlaubt inkrementelles Wachstum. Eine gleichmäßigere Auslastung wird forciert.


- 53 -

Abb. 4.5: Das Prozessor-Pool-Modell

Die Auslastung resultiert aus folgenden Überlegungen:

Gegeben sei eine Ankunftsrate λ. Diese gibt die Anzahl der Aufträge an, welche proSekunde von allen Rechnern zusammen eintreffen. Die Aufträge werden in eine demProzessor-Pool zugeordnete Warteschlange eingereiht. Die Bedienrate µ bezeichne dieAnzahl der Aufträge pro Sekunde, die bei maximaler Auslastung im Prozessor-Poolverarbeitet werden können. Damit die Warteschlange nicht überläuft und keine Aufträ-ge unbearbeitet bleiben, muß λ < µ gelten. Die Ankunftsrate darf die maximale Ausla-stung nicht übersteigen.

Abb. 4.6: Prozessor-Pool Warteschlange

Für die Zeit T, die im mittel zwischen dem Abschicken eines Auftrags und dem Er-halt der Rückantwort vergeht, gilt dann nach [Bol89] bei genau einem Rechner

T =µ −

1λ

.

Faßt man n Rechner zu einem Pool zusammen, ergibt sich

( )Tn n n

Tnpool =

µ −=

µ −=1 1

λ λ.

Man erreicht also eine Antwortzeit, die nur noch 1/n der ursprünglichen Antwortzeitbeträgt, also eine um den Faktor n höhere Geschwindigkeit. Dies ist ein für den An-wender erfreuliches Ergebnis, welches zunächst einmal ein Argument gegen VerteilteSysteme darstellt. Die Übertragungszeiten sind bei dieser Überlegung allerdings ausseracht gelassen worden. Beim Prozessor-Pool-Modell kommt zur kurzen Antwortzeit dieÜbertragung über das Netz hinzu!

- 54 -

5 Literatur

[Bol89] Bolch: Leistungsbewertung von Rechensystemen mittels analytischer War-teschlangenmodelle, Teubner Verlag, Stuttgart, 1989

[Cou94] Coullouris/Dollimore: Distributed Systems: Concepts and Design,Addison-Wesley, 1994

[Gei95] Geihs: Client-/Server-Systeme,Thomsons aktuelle Tutorien, 1995

[Lam78] Lamport: Time, Clocks and the Ordering of Events in a DistributedSystem, Communications of the ACM, vol. 21, pp. 558-564, July 1978

[Mul94] Mullender: Distributed Systems,Addison-Wesley, 1994

[RSB90] Ramanathan, P. et. al.: Fault-Tolerant Clock Synchronisation inDistributed Systems, IEEE Computer, vol. 23, pp.33-42, Oct. 1990

[Slo88] Sloman/Kramer: Verteilte Systeme und Rechnernetze,Hanser Verlag, 1988

[Spa94] Spaniol/Popien/Meyer: Dienste und Dienstvermittlung in Client-/Server-Systemen, Thomsons aktuelle Tutorien, 1994

[St94] Staude: Echtzeitprogrammierung, Prozesse am Faden. Nutzung der Thread-Library von Solaris 2.2 für die Datenkommunikation,in: iX 5/1994, S.188ff.

[Tan92] Tanenbaum: Modern Operating Systems,Prentice-Hall International Editions, 1992

[Tr95] Trapp: Am dünnen Faden oder: POSIX - Definitionen zur Thread-Programmierung, in: iX 4/1995, S.136ff.

Documents

1 · Der Beginn der „Modern Computer-Era“ ist um das Jahr 1945 herum anzusiedeln. Typisch für die Zeit waren (nach heutigen Maßstäben gerechnet) große und teure Computer,