Amoeba 1

Kapitel 27: Amoeba - Ein Verteiltes BetriebssystemLiteratur: Tanenbaum, Moderne Betriebssysteme

TransparenzKein HeimrechnerJede Aktivität verstreut im NetzLastausgleichAuch Testumgebung für Verteilteund parallele Programme

HardwareViele Prozessoren, Pool, viel Speicher, lokal, auch gemeinsam

MikrokernServer für die üblichen BS-DiensteKern auf den Rechnern des Pools, den Terminals, den Servern1. Prozessverwaltung2. Speicherverwaltung3. Kommunikation4. Untere Ebene der E/A

Amoeba 2

Amoeba 3

Amoeba 4

Prozess- Adressraum- (mehrere) Threads

Thread- Register- Programmzähler- Stack

Speicher in SegmentenEinblenden

KommunikationPunkt - zu - Punkt, Anfrage - AntwortGruppen - K.

Eine Quelle, viele Empfänger, zuverlässig, FLIP-Protokoll, Netzwerkschicht

E/A, Gerätetreiber

Amoeba 5

Klient-Server-ModellObjekte, durch Server

verwaltetZugriff mit Capabilities- kryptographisch geschützt

Objekte z.B.- Datei- Verzeichnis- Speichersegment- Bildschirmfenster- Prozessor- Festplatte

Serverdienste:- Fernaufruf (RPC) Bullet- (Datei-) Server- Read-only Semantik Verzeichnis-Server- Pfadname Capability, mit - der Dateien angesprochen werden. Server für - Objektreplikation - Prozesserzeugung - Überwachung von Serverausfall - Kommunikation mit der Außenwelt - Benutzerspezifisch

Amoeba 6

Objekte = Abstrakte Datentypen

- Verwaltung durch Server-Prozesse- Aufruf via RPC, der blockiert · Orte transparent

Server: - Benutzerprozesse - selten Kernprozess - - Prozess-Server - - Speicher-Server - Benutzung einheitlich

Capabilities

Das Stub-Unterprogramm im Klient stellt bei Aufruf eineNachricht zusammen.

Server-Port: Logischer Name des (der) Server(s) - nicht Rechner

Objekt: NameRechtePrüffeld: Schutz, Zufallszahl

Amoeba 7

Amoeba 8

Schutz von ObjektenBei der Erzeugung des Objekts generiert der Server die Capability,die er versendet und speichert. Will der Klient diese mit eingeschränkten Rechten weiter geben, erhält er auf Anforderung vom Server dazu eine weitere, veränderte Capability mit dem Prüffeld:Wird später diese neue Capabilitypräsentiert, verifiziert der Serverdas Prüffeld mit f (EingeschränkteRechte

exor reduziertes Prüffeld), wobei f eine Einwegfunktion ist.

Es gibt keine Zugriffskontrollisten.Der Verbleib von Capabilitieskann nicht kontrolliert werden, sie können nicht zurückge-nommen werden.

Amoeba 9

Amoeba 10

Amoeba 11

Prozesse, ThreadsEin Prozess ist ein Objekt. Der Erzeuger kann ihn mit derCapability suspendieren, neu starten oder auflösen.Er wird vom Prozess-Server auf einem bestimmten Rechner mit gewünschtem Speicherbild erzeugt.Der Rechen-Server wählt dengeeigneten Prozessor aus.

Prozessschnittstelle, unterste Ebene(es gibt drei Ebenen)- exec, Parameter Capability und Prozesskriptor. Startet den Prozess auf dem angegebenen Rechner. Zurück: Capability für den Prozess.- getload, liefert Informationen über Rechnergeschwindigkeit, Last und verfügbarem Speicher; dient dem Rechen-Server zur Rechnerauswahl- stun, Anhalten eines Sohnprozesses-- Normalfall, der Sohn beendet ggf. die

Kette von RPCs.-- Notfall, sofort

Amoeba 12

Amoeba 13

Diese und weitere Operationen werden von der Prozess-schnittstelle höherer Ebene benutzt. Hier:- newproc, erzeugt neuen Prozess, benötigt Parameter für dessen Beschreibung, z.B. ProgrammThreads:Ein Prozess besitzt anfangs einen Thread. Dieser kann weitere erzeugen. Terminieren möglich.

Eigener stack, eigene Register. Globale Variablen mit Bib-liotheksroutinen.Synchronisation:- Signale; auslösen, abfangen, ignorieren- Mutex für wechselseitigen Anschluss- Zählender Semaphor

Threadverwaltung im Kern. Scheduling mit Prioritäten.

Amoeba 14

SpeicherverwaltungVirtueller Adressraum mit Seg-menten, kein virtueller Speicher!Argumentation: Geschwindigkeit, große, billige Speicher verfügbar.

Operationen für Segmente:Erzeugen, Anfangswerte setzen, Größe ändern, Lesen, Schreiben, Einblenden, Ausblenden, Auflösen.Nach Ausblenden mit Capability wieder zu benutzen.

Segmente können von mehreren Prozessen ge-meinsam benutzt werden.

Amoeba 15

Amoeba 16

Kommunikation: FernaufrufeAufrufer blockiert bis zur Antwort. (Strukturierung)Klient ruft eine Stub-Routine auf, die den Auftrag mit Para-metern verpackt. Ein Kern-Primitiv versendet, während dem die Stub-Routine blockiert ist.Diese übergibt dann die Antwort an den Klienten.Logische Adresse eines Server-Threads ist ein Port, eine Zufalls-zahl (48 bit) ohne Hinweis auf den Ort. Alle Nachrichten werden mit

Ports adressiert.In jeder Capability steht ein Port, die Adresse des Servers, der das zugehörige Objekt verwaltet.RPC-PrimitiveSystemaufrufe, benutzt in Bib-liotheksroutinen.1. get-request, Server ist bereit,

den Port abzuhören.2. put-reply: Server sendet

Antwort.3. trans: Klient sendet Auftrag

und wartet auf Antwort.

Amoeba 17

Amoeba 18

Alle Nachrichten haben einen Kopf und -optional- einen Puffer:- Port : Ziel- Signatur: zur Zeit unbenutzt- dann: Parameter, vereinbart zwischen Sender und EmpfängerServer: get-request (& kopf, puffer,

länge)- kopf: Der referenzierte Kopf

enthält erst den Port des Servers, bei der Antwort dann i.d.R. die Capability eines Objekts, das zu bearbeiten ist,

in Port (6) und privater Teil (10).Manche Aufträge brauchen keinen Puffer, z.B. READ (Datei)- der Bereich der Datei ist in Offset (4), Größe (2) gegeben.get-request blockiert den Server.Mit put-reply (&kopf, puffer,länge) antwortet der Server.

get-request und put-reply müssen paarweise auftreten.

Amoeba 19

Der Klient ruft die Stub-Routine auf, welche den Systemdienst trans (& kopf, puffer1, länge1, & kopf 2, puffer 2, länge 2) benutzt.- Nachricht 1: Auftrag- Nachricht 2: AntwortIn dieser Form wäre der RPC unsicher. Ein betrügerischer Server könnte Aufträge via get-request abfangen, da die Ports öffentlich sind. Daher ist jeder Port ein Paar:der get-port (privat) und der put-port (öffentlich)

Mit einer Einwegfunktion F gilt put-port = F (get-port).Ein Server führt get-request immer mit dem get-port aus. Der Kern berechnet daraus den put-port und fügt ihn in die Tabelle der abgehörten Ports ein.Klienten benutzen den put-port.

Amoeba 20

Amoeba 21

Gruppenkommunikation

Gruppe: Menge von Prozessen, ge-meinsame Aufgabe oder gemeinsa- mes Bereitstellen eines Dienstes.

Geschlossen: die Gruppenstruktur istvon außen verborgen; soll die Gruppe um einen Dienst gebeten werden, wird von außen ein Mitglied angesprochen, das intern weiterleitet.Operationen:- Create Group erzeugt neue Gruppe und etabliert ihren Gruppenidentifikator.

Parameter z.B. Grad der Fehlertoleranz- Join Group, wobei keine Nachricht an alle Gruppen- mitglieder weitergegeben wird.- Leave Group, Der letzte löst damit die Gruppe auf.- Send To Group, atomar, zuverlässig, in der Reihen- folge abgeliefert.

Amoeba 22

Amoeba 23

Das zuverlässige “Broadcast”-Protokollfür Gruppenkommunikation.Zentrale Instanz: “Ordner”; bei Ausfall: Election.Gruppennachricht eines Benutzer-prozesses:1. Nachricht an den Kern2. Dieser blockiert den Benutzer3. und sendet eine Punkt-zu-Punkt-Nach-richt

an den Ordner.4. Dieser erzeugt eine Reihenfolgenum- mer, trägt sie in den Nachrichtenkopf ein und sendet die Nachricht an alle.5. Sobald der Kern des Absenders die

Nachricht erhält, entblockiert er den Benutzerprozess.

2./3. Der Auftrag an den Ordner-Request for Broadcast - erhält einen eindeutigen Nachrichtenidentifikator (Duplikate) und die Reihen-folgenummer des zuletzt empfangenen Broadcast als (späte) Quittung - “Piggy-back”.Beim Senden dieses Auftrags an den Ordner wird ein Wecker gestellt. Kommt der Broadcast vor Ablauf hier an, wird der auftraggebende Benutzerprozess entblockiert - der Normallfall.

Amoeba 24

Amoeba 25

Wecker läuft ab: - Auftrag verloren oder - Nachricht des Broadcast verloren - oder langsam. - Neuer Auftrag an den Ordner.Hatte der nichts erhalten, verfährt er wie üblich, sonst beruhigt er nur den beautragenden Kern.Ordner erhält Auftrag. Duplikat?- ja: Nur Absender beruhigen.- nein:-- Neue Reihenfolgenummer-- Diese und die Nachricht speichern,

mit Identifikator--Nachricht an alle senden, mit Nummer.

Kern erhält Broadcast-Nachricht:Vergleich der Reihenfolgenum-mer der letzt empfangenen. Ist die neue um 1 höher, wird die Nachricht an eine wartende An-wendung weitergereicht.Andernfalls wird sie gepuffert, und mit einer Punkt-zu-Punkt-Nachricht wird der Ordner auf-gefordert, die vorige Nachrichtzu wiederholen. Trifft sie ein,werden beide Nachrichten in der richtigen Reihenfolge ab-geliefert.

Amoeba 26

Amoeba 27

Leeren des Puffers im Ordner:Jedem Auftrag an den Ordner ist eine Bestätigung k beigefügt, die besagt, dass alle Broadcast-Nach-richten bis Nr. k korrekt empfan-gen wurden. (“piggybacked ack-nowledgement”).Damit ermittelt der Ordner, welche gepufferten Nachrichten sicher nicht mehr benötigt werden.Ein Rechner, der lange keinen Auf-trag sendet, sendet extra eine Be-stätigung k, oder der Ordner for-dert mit einem Broadcast von allen diesen besonderen Bestätigungen.

Das tritt selten auf, weshalb per Broad-cast etwas mehr als 2 Nachrichtenüber das Netz gehen, im Durchschnitt.Alternatives, logisch äquivalentes Protokoll: Der beauftragende Kern sendet die Nachricht gleich an alle Rechner der Gruppe. Sobald der Ord-ner sie erhält, sendet er an allen einekurze Nachricht mit der Reihenfolge-nummer; Zuordnung mit eindeutigem Identifikator. Bandbreitenersparnis:die 2. Nachricht kann kürzer sein; aber jeder Rechner muss 2 statt einer Nachricht annehmen.

Amoeba 28

Amoeba 29

Fehlertoleranz hinsichtlich Rech-nerausfall: Bis zu k ausgefallene Rechner werden verkraftet; der Mehraufwand wächst mit dem wählbaren k.Antwortet ein Rechner nicht mehr, markieren die das be-merkenden Kerne ihn als tot und die Gruppe als nicht benutzbar. Danach schlägt Gruppenkommu-nikation fehl. Jeder, der das be-merkte, ruft resetGroup auf, und schlägt sich so als Koordinator vor. Damit ist eine Broadcast-Nachricht an die Gruppe verbunden: melden! An jeden daran senden alle lebendi-

gen Gruppenmitglieder die Reihen-folgenummer der letzten empfan-genen Nachricht. Haben sich meh-rere als Koordinator vorgeschlagen, gewinnt der mit dem höchsten Paar (Reihenfolgenummer, Rechner-adresse). Der Gewinner sammelt die vermissten Nachrichten ein, wird neuer Ordner und teilt dies und die höchste Reihenfolgenummer allen mit. Diese fordern dann an, was ihnen fehlt, erhalten und bestätigen das. Sind alle Bestätigungen beim neuen Ordner, löscht dieser den Puffer.

Amoeba 30

Amoeba 31

Bei k > 0 führen außer dem Ord-ner die k Gruppen-Kerne mit denniedrigsten Adressen den Puffer. Bei Ausfall von bis zu k Rechnern bleibt also mindestens ein Puffer erhalten.

Bei k > 0 wird das alternativeProtokoll, leicht verändert, ver-wendet.Erhält der Ordner eine Nachricht,wartet er auf eine Bestätigung von allen Puffer-führenden Kernen.

Erst dann verbreitert er die Reihenfolgenummer. Erst da- mit ist der Broadcast abge-schlossen.

Amoeba 32

Das Fast-Local-Internet-Protokoll

(FLIP) der Netzwerkschicht (ISO-Referenzmodell) für- Fernaufrufe und- GruppenkommunikationWarum ein neues Protokoll?IP ginge auch.Wünschenswerte Eigenschaften, die andere Protokolle nicht alle besitzen. Typische FLIP-Konfiguration: Lokale Rechnernetze mit Möglichkeiten des Broad- und Multicast.

Jeder Prozess erhält für die Dauer seiner Existenz eine FLIP-Adresse, unverändert bei Migration und bei Änderung der Netzwerktopologie oder -adressierung:64 Bit Zufallszahl Z, genauerÖffentliche Adresse =

DES Z (0...0),

wobei Z der Schlüssel für DES und die private Adresse ist. Server hö-ren private Adressen ab, Klientensenden an öffentliche Adressen.

Amoeba 33

Amoeba 34

Amoeba 35

FLIP-Schnittstelle nach oben:Mit Init lässt sich die RPC-Schicht registrieren; dabei über-gibt sie zwei Zeiger auf Proze-duren, die beim Eintreffen eines normalen bzw. nicht übertragba-ren Paketes aufgerufen werden.End: Eintrag löschenEin Prozess berechnet seineprivate FLIP-Adresse undübergibt sie mit Register an die FLIP-Schicht. Dort wird mit DES die öffentliche Adresse berechnet und gespeichert.

AdressberechnungFLIP erhält von oben Pakete mit FLIP-Adressen des Ziels. Um die Netzwerk-adresse dazu zu finden, wird eine Rou-ting-Tabelle geführt. Einem eintreffen-den Paket wird die FLIP- und die Netz-werkadresse des Senders entnommenund, wenn nicht vorhanden, gespeichert. Ferner der Hop-Zähler, der beim Passie-ren eines Verbindungsrechners erhört wird - ein grobes Entfernungsmaß. Das Sicherheitsbit zeigt an, ob der Weg ab-hörgefährdet oder ganz vertrauenswürdig war. Der Alter-Eintrag erhöht sich für eine LRV-Verdrängungsstrategieder Einträge.

Amoeba 36

Amoeba 37

Amoeba 38

Beispiel: Verbindung Klient A und Server BErzeugung von B: Kern erzeugt FLIP-Adresse und registriert sie in der FLIP-Schicht.B startet und ruft get_request mit seinem Get-Port auf.Die RPC-Schicht sucht oder gene-riert den Put-Port und blockiert B.A führt trans mit dem Put-Port aus. Beim ersten mal findet die RPC-Schicht dazu keine FLIP-Adresse.Sie sendet ein spezielles Broadcast-Paket mit maximalem Hop = 1 - so wird nur im lokalen Netz gesucht.

Kommt nach Time-out keine Ant-wort, neuer Versuch mit Hop = 2 - geht bis in die Nachbarnetze; usw.Wenn B dieses Broadcast-Paket er-hält, antwortet die FLIP-Schicht mit der FLIP-Adresse. Empfängt A das, erzeugt die FLIP-Schicht einen Eintrag in die Routing-Tabelle und übergibt die FLIP-Adresse an die RPC-Schicht. Diese speichert Put-Port und FLIP-Adresse zusammen.Jetzt und in Zukunft kann die RPC-Schicht Aufträge mit der FLIP-Adresse versehen und senden.

Amoeba 39

Also zwei Abbildungen:1. RPC-Schicht: Put-Port FLIP-

Adresse2. FLIP-Schicht: FLIP-Adresse

NetzwerkadresseDie FLIP-Schicht ist unabhängig von dem Port-Konzept, also allge-meiner.Mehrere Server können denselben Dienst anbieten und denselben Port abhören. Jeder hat aber eine andere FLIP-Adresse. So kann die RPC-Schicht eines Auftraggebers auswählen.

Server können migrieren, für die Klienten ändert sich dabei nichts.Auch nicht bei Änderung der Netz-konfigurationen.Ein ausgefallener Server erhält beim Neustart eine andere FLIP-Adresse. Damit kann man die at-most-once-Semantik durchsetzen.

Amoeba 40

FLIP in WeitbereichsnetzenAmoeba kann auf Rechnern laufen, diedie auch über ein WAN verbunden sind.Dabei wird der Datenverkehr z.B. über TCP/IP abgewickelt, was aber in Amoeba transparent ist.Ein Broadcast wird mit einzelnen Nachrichten simuliert.

Beispiel Klient A sucht Server E:1 Hop: A, B, C2 Hops: D, G3 Hops: E, F, H, I

Amoeba 41

Amoeba 42

Die Amoeba-ServerDie meisten BS-Dienste für An-wender werden von Servern an-geboten.Um einen Dienst zu benutzen, wird eine Stub-Routine aufgeru-fen. In ihr ist festgelegt, welche Dienste ein Server anbietet und welche Parameter dabei zu spe-zifieren sind.Stubs werden in der Amoeba Inter-face Language (AIL) definiert und vom AIL-Compiler in Stub-Routinen übersetzt.

Der Bullet-Server(Geschoss - sehr schnell)Das Amoeba-Dateisystem:- Bullet-Server zur Speicherung der Dateien- Verzeichnis-Server für Datei- namen und Verzeichnisse- Replikations-Server

Daneben können auch andere Da-teisysteme implementiert werden.Dateien konstant- Größe fest- zusammenhängend gespeichert, im Cache und auf der Platte- zusammenhängend transportiert- Replikationen einfach

Amoeba 43

Konzeptionelles Modell:Der Klient stellt Daten in seinem Speicher zusammen, erzeugt mit create (ein RPC, der die Daten an den Bullet-Server sendet) eine Da-tei, erhält eine Capability dafür zu-rück.Diese geht, zusammen mit dem Dateinamen, in ein Verzeichnis.Ändern:Datei lesen, im Speicher ändern, neue Datei anlegen. Evtl. wird die alte Version aufbewahrt, oder ge-löscht.

Konzession an die Realität- es können Teile gelesen werden- Vorstufe zu festgelegten Da- teien:(permanent): unfestgelegte mit kurzer Lebensdauer, welche nicht zu lesen sind, aber geän-dert werden können.Administrator-Dienste:- Cache auf Platte- Platte aufräumen- Defektes Dateisystem repa- rieren(spezielle Capability)

Amoeba 44

Amoeba 45

Amoeba 46

Datei lesen:- Capability senden- Objektnummer ist Index in die Dateitabelle- Prüffeld mit dem dort ge- speicherten Wert vergleichen- Datei von der Platte in den Cache- Verdrängungsstrategie: LRUAufräumen:Unfestgelegte Dateien werden nach 10 min. ohne Zugriff gelöscht.Festgelegte Dateien:Zähler in Dateitabelleneintrag,mit MAX-LIFETIME initialisiert.

Ein Dämon ruft periodisch einen RPC des Bullet-Servers auf, deralle Zähler dekrementiert (age-Operation); wo der 0 wird, wird die Datei gelöscht.

Touch, angewendet auf einzelne Dateien, setzt den Zähler auf MAX-LIFETIME. Für Dateien in Verzeichnissen wird stündlich touch aufgerufen.Ohne das wird sie nach 24 Stun-den gelöscht.

Amoeba 47

Verzeichnis-Serverbilden menschengerechte Objekt-namen auf Capabilities ab.In einem Verzeichnis stehen, grob gesprochen, mehrere Paare Namen-Capability.Hierarchisch angeordnete Verzeich-nisse bilden schrittweise Pfadnamen auf Capabilities ab.Ein Verzeichnis ist selbst ein Ob-jekt. Jeder Eintrag dient einem Ob-jekt. Er kann mehrere Capabilities für identische Kopien des Objektes enthalten. Dazu sind Benutzerrechtespezifiziert, differenziert

in Domänen für verschiedene Be-nutzergruppen, die Antwort-Capa-bility wird bei eingeschränktenRechten mit der Einwegfunktion berechnet.Einträge können hinzugefügt, ver-ändert, gelöscht werden.Jede Art von Objekt kann verwal-tet werden: es kann irgendwo ge-speichert sein.Bei einer Anfrage werden ggf. alle gespeicherten Capabilities geliefert.Ein Verzeichnis wird mit mehreren Capabilities angesprochen, für jede Domäne eins.

Amoeba 48

Amoeba 49

Indem Verzeichnisse Paare von Verzeichnisnahmen und ihren Capabilities enthalten, entstehen Verzeichnisgraphen. In ihnen können Rechte sehr differenziert vergeben werden. Jeder Benutzer hat ein eigenesWurzelverzeichnis.

Beispiel: Benutzer 1 möchte eine Datei anlegen und sucht den Bul-let-Server A. Zu/Benutzer1/public/cap/Bullet-Server1 erhält er dann dessen Capability.

Implementierung des Verzeichnis- ServersVerzeichnis-Server speichern die Verzeichnisse zweimal, auf zwei ver-schiedenen Bullet-Servern, wegen der Sicherheit. Jedes Verzeichnis hat deswegen zwei Capabilities.Ein Auftrag an den Verzeichnis-Server enthält in dessen Capability im Objektfeld eine Nummer, die das Verzeichnis, mit dem etwas ge-schehen soll, bezeichnet. Mit dieser Nummer als Index werden dann aus einer besonderen Datenstruktur auf der Platte, einem Vektor von Capa-bility-Paaren, zwei Capabilities ge-lesen, die die beiden Verzeichnis-Kopien auf den Bullet Servern iden-tifizieren.

Amoeba 50

Amoeba 51

Amoeba 52

Amoeba 53

Der Replikations-Serverpraktiziert träge Replikation:Objekte, die mehrfach vorhanden sein sollen, werden erst einmal erzeugt; der Replikations-Server überprüft regelmäßig aus dem Hintergrund, ob Kopien anzu-legen sind.Ferner steuert er die Alterungs-kontrolle mit age-Nachrichten, und sendet die touch-Nachrichten als Jungbrunnen.Der Rechen-ServerEin Prozessor-Pool wird durch ein Verzeichnis -Pooldir - repräsentiert.

Es enthält für jede Architektur ein Unterverzeichnis, und diese für den Prozess-Server eines jeden Rechners die Capability.Ein Rechen-Server verwaltet eine Menge von Prozessor-Pools.Soll ein Program ausgeführt werden, das es z.B. für mehrere Architek-turen in /bin gibt, wählt der Rechen-Server zunächst die möglichen Ar-chitekturen aus, dann den Prozessor gemäß- reicht der verfügbare Arbeitsspeicher?- wo ist Rechenkapazität frei?Der Auftraggeber erhält die Capability des Prozess-Servers des ausgewählten Prozessors.

Amoeba 54

Amoeba 55

Der Boot-Serverstellt Fehlertoleranz bereit, indem er überprüft, ob Server ausgefallen sind, und ggf. deren Dienste neu startet.

Der TCP-IP-Servererschließt dieses Protokoll, z.B. für- die Benutzung des Internet,- Verbindungen mit Nicht-Amoeba- Rechnern

Weitere Server-Platte (Felder von Capability- Paaren)- E / A- Tageszeit- Wecker-gesteuerter Start von Aktivitäten- Zufallszahlen für Ports, Capa- bilities, FLIP-Adressen