Überblick
Definition
Von Tanenbaum (leicht abgewandelt von Lehmann)
Anzahl gekoppelter, voneinander unabhängiger Computer, die den Benutzer vermitteln, es handelt sich um einen Computer
Im Unterricht: Jedes System, dass mehrere CPUs miteinander verbindet
Eigenschaften von Verteilten Systemen
Wirtschaftlichkeit
Verbund von leistungsschwächeren Systemen günstiger als ein High-End-System
Höchstleistungsrechner
Verbund von CPUs (Mikrocontroller) deutlich höhere Rechenleistung als Einzelrechner
Bis zu 10.000 CPUs verbindbar (nach heutiger Technik)
Einzelsystem mit ungefähr gleicher Leistung physikalisch unmöglich (nach heutigem Stand)
Inhärent verteilte Systeme
Vorgaukelung eines Systems (Zentralseitige Abfrage bei mehreren Märkten, S.17)
Coorparative Work
Ein verteiltes System zum Zusammenfassen von Teilergebnissen
Zuverlässigkeit und (Ausfall)-Sicherheit
Dank Redundanz deutlich ausfallsicherer als Einzelsystem
Wachstum
Stück für Stück erweiterbar
Vorteile (gegenüber Einzelsysteme)
Gemeinsame Nutzung
sowohl von Geräten als von Dateien
Kommunikation
Flexibilität
Nachteile
Software deutlich komplexer
Betroffen von Netzwerkprolemen
Zugriff auf potentiell sichere Dateien möglich
Hardware-Konzepte
Single instruction stream, single data stream (SISD)
Single instruction stream, multiple data stream (SIMD)
Multiple instruction stream, single data stream (MISD)
Multiple instruction stream, multiple data stream (MIMD)
mit gemeinsamen Speicher: Multiprozessor-Rechner
ohne gemeinsamen Speicher: Multicomputer
-
Art der Kopplung
Eng gekoppelt
Per Bus (eine Verbindung)
meist „parallele Systeme“
Lose gekoppelt
Per Netz
meist „verteilte Systeme“
Busbasierte Multiprozessorsysteme
mehrere CPUs
bis zu 64 (im Normalfall)
über einen Bus auf einen gemeinsamen Speicher zugreifend
kohärenter Speicher
Performanceprobleme bei bereits wenigen CPUs
Bus ist Flaschenhals
Cache pro CPU als Performance-Lösung
daher Kohärenzproblem (Konsistentproblem)
führt im Problemfall zu Inkohärenz
Einsatz von Write-Through-Cache
Schreibvorgänge direkt in gemeinsamen Speicher
Ständige Abhörung des Busses
Bei Schreibvorgang eines anderen Caches, Aktualisierung eigenes Wertes oder Löschung aus dem Cache
Verbindungsorientierte Multiprozessorsysteme
Aufteilung des Speichers in n Module
System hat n CPUs
Durch Schaltnetz jede CPU mit jedem Speicher verbindbar
Kreuzschienenverteiler:
-
nur warten, wenn mehrere CPUs auf einen Speicher gleichzeitig zugreifen wollen
n² Mikroschalter nötig
für große n sehr große Kosten (nahezu unbezahlbar)
daher Omega-Switching-Netzwerk
-
Omega-Switching-Netzwerk
-
log2(n) Schaltvorgänge, mit jeweils n/2 Umschaltungen
log2(n)+n/2 Schalter nötig
1 Schalter hat zwei Ein- und zwei Ausgänge
Schaltverzögerung pro Schalter
größer für größeres n
-
Non-Uniform-Memory-Access (NUMA)
wie Omega-Switch-Netzwerk, nur mit lokalen Speicher an der CPU
Zugriff zu eigenem Speicher schnell
Zugriff zu Speicher von anderen CPUs langsam
Zusätzliche Komplexität
Busbasierter Multicomputer
Jede CPU besitzt eigenen lokalen Speicher
Kommunikation nur von CPU zu CPU
via Bus
Verbindungsorientierter Multicomputer
CPU hat direkten, exklusiven Zugriff auf lokalen Speicher
-
Netztopologien
Gitter
-
selbsterklärend
-
Hypercube
n-dimensionaler Würfel
n jede CPU n-Verbindungen zu anderen CPUs
insgesammt n*2(n-1) Verbindungen
Anzahl Verbindungen wächst bei Gitter quadratisch
Anzahl Verbindungen wächst bei Hyperqube logarithmisch
Netz-Betriebssysteme
(Software-Konzept)
lose gekoppelte Hardware
lose gekoppelte Software
heterogene & homogene Clients möglich (einheitliche/unterschiedliche)
bei heterogenen müssen Namenskonventionen kompatibel sein
Echte verteilte Systeme (Software-Konzept)
lose gekoppelte Hardware
eng gekoppelte Software
wird auch genannt:
einheitliche Systemsicht
virtueller Einzelprozessor
Bis heute kein Betriebssystem, welches die Anforderungen ideal erfüllt
Eigenschaften
globaler Mechanismus für Interprozesskommunikation
Jeder Prozess muss mit jedem sprechen können
globalen & einheitlichen Schutzprozess für Objekte (Dateien, Prozesse, …)
einheitliches Prozessmanagement
erzeugen, starten, stoppen, zerstören
Benennungsprozess
Einheitliche Menge für Systemaufrufe
Einheitliches Dateisystem
Unter Berücksichtigung von Rechten soll jede Datei von überall aufrufbar sein
Identische Kernels
Müssen miteinander kommunizieren können, zur Prozess(last)aufteilung
Multiprozessor-Timesharing-Systeme (Software-Konzept)
-
eng gekoppelte Hardware
eng gekoppelte Software
globale Systemwarteschlange
Datenstruktur im gemeinsamen Speicher
Da gemeinsamer Speicher egal, welcher Prozess wo ausgeführt wird
jedoch leichter Performancegewinn, wenn Prozess immer auf gleicher CPU ausgeführt wird (dank Cache)
-
Multiprozessor-Timesharing-Systeme
Siehe Skript von Hascher. Prozesse werden durch die Prozessoren "rotiert"Softwarekonzepte im Überblick
Transparenz
verhält sich wie ein Einprozessor-Timesharing-System
Ortstransparenz
Anwender & Programmierer erkennen nicht, wo die Datei liegt (Name des Rechners nicht im Dateipfad)
Migrationstransparenz
Verschieben von Objekten für Anwender und Anwendungen unbemerkt geschehen
Keine Änderung im Zugriff für Anwender & Anwendung
Replikationstransparenz
Kopien erstellen, ohne dass Anwender oder Anwendung etwas mitbekommt
Nebenläufigkeitstransparenz
Mehrere User zugriff auf eine Ressource ohne Bemerkung der anderen User
Parallelitätstransparenz
Ablaufen von parallelen Aktivitäten ohne gegenseitige Behinderung
Zuverlässigkeit
Zuverlässigkeit durch Redundanz der Dienste und Dateien
Je höher die Redundanz, desto komplexer die Konsistenz von Dateien
dezentrale Komponenten & Algorithmen
Keine Maschine besitzt vollständige Informationen zum gesamten Systemstatus
Maschinen treffen nur Entscheidungen, die auf lokalen Informationen basieren
Ausfall einer Einzelmaschine hat keine Auswirkung auf den Algorithmus
keine implizite Annahme einer globalen Uhr
nicht möglich: genaue Uhrensynchronisation
Kommunikation und Dateisysteme
Kommunikation durch Protokolle geregelt
Sitzungsschicht (Schicht 5)
Dialogsteuerung auf höherer Ebene
beinhaltet Synchronisationswerkzeuge
Im praktischen Einsatz nur selten implementiert
Darstellungsschicht
definiert Datenformate (ASCII, EBCDIC, HTML, JPEG, …)
stellt richtiges Format bereit (für Anwendungsschicht)
IPv6
128 Bit lang
in 8 Teilbereiche unterteilt
16 Bit pro Bereich
dient der besseren Lesbarkeit
als HEX-Wert dargestellt
getrennt durch :
Schreibregeln
Führende Nullen weglassbar
mehrere Teilbereiche hintereinander, deren Wert 0 ist, durch zwei :: ersetzbar
nur einmal in einer Adresse, sonst nicht eindeutig
ersten 64 Bits
Routing-Prefix
unterteilt in
Global Routing Prefix (Länge n)
Vorgegeben
Subnet ID (Länge 64 – n)
Selbst festlegbar
Bestimmt das Netz
Subnetzmaske mt /x angeben
letzten 64 Bits
Interface-ID
bildet Adressteil
eindeutiger Identifier innerhalb des Netzes
Spezielle Adressen
Unspecified Address
::0 (= 0:0:0:0:0:0:0:0)
Loopback-Adresse (Localhost)
::1
IPv4-mapped-Adressen
::FFFF:x:x
für x:x wird eine IPv4 Adresse eingesetzt
gemischte Schreibweise:
::FFFF:n.n.n.n
Global Unicast-Adressen (Prefix: 2000-3FFF)
normal im Internet benutzbare Adressen
identifizieren genau ein einziges Gerät
Local Unicast-Adressen (Prefix: FC00-FDFF)
privater Adressraum
Link Local Unicast-Adressen (Prefix FE8-FEB)
Nur innerhalb eines Netzsegments gültig
dürfen von Routern nicht geroutet werden
Mulicast-Adressen (Prefix: FF00-FFFF)
ersetzen Broadcast-Adressen
Client-Server-Modell
verbindungsloses Frage-Antwortprotokoll
Nur 3 Schichten genutzt (von OSI)
Physikalische und Sicherungsschicht (Layer 1, 2)
In Hardware umgesetzt
Schicht 3 & 4 entfallen (da verbindungslos)
Schicht 5 implementiert Frage-Antwort-Protokoll
Mikrokernel stellt zwei Systemaufrufe zur Verfügung
Sender der Nachricht
Empfangen der Nachricht
Beide Aufrufe blockieren
Adressierung
Prozesse werden addresiert
<host>.<local-id>
Nicht mehr Ortstranzparent
Zentral verwaltetes Prozessadressierungsschema
spricht gegen Designaspekt (keine zentralen Dienste)
Broadcasting
Prozessliste (Dienstliste) vereinbart, die auf jedem Client ist
Client sendet Broadcast für einen Dienst
Server (falls vorhanden) antwortet mit Dienstnummer und Serveradresse
Client speichert Information im Cache
Server-Broadcasting
Server sendet seine Dienste & Adresse in bestimmten Zeitabständen als Broadcast
Nameserver
Spezieller Server im Netz mit Dienstliste anderer Server
Client fragt Nameserver
Nameserver gibt Adressen von Servern mit Diensten
Primitiven für Nachrichtenüberteragung
blockierende Primitiven
synchrone Primitiven
Timeout zum abbrechen
nicht-blockierende Primitiven
asynchrine Primitiven
Performancevorteil
Zwei Arten
Senden mit Kopieren in Kernelpuffer (kostet Zeit)
Senden mit Interrupt (schwierig zu programmieren)
Mailbox
für ankommende Nachrichten
puffernde Primitive
kann ebenfalls (wie jeder Puffer) überlaufen
Zuverlässige Primitiven
Möglichkeit 1. Anwendungen gehen von verlorenen Paketen aus
unzuverlässige Primitive
Anwendung muss Vollständigkeit überprüfen
Möglichkeit 2. Kernel kümmert sich um verlorene Pakete
leichter für die Programmierung der Anwendung
Möglichkeit 3. Bestätigung des Erhalts durch Kommunikationspartner
-
Remote Procedute Call
Aufrufen von Prozeduen auf fremden Maschinen
für Programmierer vollkommen transparent
soll wie lokaler Prozeduraufruf aussehen
Ergebnisse gehen wieder an Aufrufer
-
Darstellungsschicht (Layer 6) sehr wichtig!
Unterschiedliche Codierung (ASCII, EBCDIC, …)
Unterschiedliche Größen (32Bit-Integer, 64Bit-Integer, …)
Unterschiedliche Nummerierung der Bytes (NUR Bytes, nicht Bits!)
rechts nach links „little endian“
links nach rechts „big endian“
Betrifft nur Typen (Integer, Float, ...) mit mehreren Bytes
Einigung auf Übertragungsformat
Übergabe von Zeigern
call-by-reference durch call-by-copy/restore ersetzten
durch Client/Server-Stub der Prozedur
klappt nur bei Zeiger auf Arrays, Strukturen
Dynamisches Binden
Timeouts gegen Fehler (Übetragungsfehler oder Server/Client-Ausfall)
Gruppenkommunikation
Kommunizieren eines Prozesses mit Gruppe
Gruppe sind andere Prozesse, die als eine Abstraktion angesehen werden können
Kommunikation von Dateisystemen
Dateiserver
Server stellt Dateidienst zur Verfügung
sagt dem Client, was mit einer Datei getan werden kann, nicht wie
Kann auf mehreren Servern aufgeteilt sein
Idealfall: Client weiß nicht, wie viele Server (tranzparenz) (und es funktioniert trotzdem)
Dateidienst
verantwortlich für Dateioperationen
schreiben, lesen, anhängen, …
Verzeichnisdienst
verantwortlich für Verzeichnisoperationen
kopieren, neu anlegen, verschieben, …
Dateien
unstrukturierte Bytefolge
erst durch Programm wird daraus Information
besitzen Attribute
Dateidienst
muss Primitiven zum Lesen & Schreiben der Dateiattribute bereitstellen
Teilweise nur CREATE und READ
vereinfacht Datei-Caching und Replikation (da keine Aktualisierungen)
Zwei Modelle
Upload/Download-Modell
einfach zu implementieren
große Netzlast
größerer Client-Speicher
Modell des entfernten Zugriff
nur Blöcke übertragen (keine ganzen Dateien)
geringere Netzlast
kleiner Client-Speicher reicht
Anzahl an Operationen muss zur Verfügung gestellt werden
Verzeichnisdienst
Stellt Operationen für Verzeichnisse zur verfügung
Teilweise mit Links
-
Problem:
Verknüpfung von A→B gelöscht
Zähler bei B auf 1
B bleibt bestehen, jedoch nicht mehr erreichbar
Fatal für Verteilte Systeme
Häufig Pfadangabe mit Servernamen im Pfad
Server kann überall im Netzwerk stehen → Ortstranzparent
Jedoch Ortsabhängig (da vom Server abhängig)
3 Mechanismen zur Bennenung von Dateien und Verzeichnissen
Recher + Pfad
Importieren ferner Dateisysteme in die lokale Dateihierarchie
Ein einziger Namensraum für alle Maschinen im Netz
Gleiche Verzeichnisstruktur auf allen Maschinen
Namensgebung auf zwei Ebenen
erste Ebene: vom Benutzer gewählter Namen
zweite Ebene: binärer Name
kürzer
eindeutige Netzwerkweite Objektnamen
Implementation verteilter Dateisysteme
gemachte Beobachtungen
Dateien häufig klein (<10K)
häufger gelesen als geschrieben
Lese- & Schreiboperationen sequenziell
meisten Dateien haben kurze Lebensdauer
gemeinsame Nutzung von Dateien selten
Prozesse benötigen (i.d.R.) nur wenige Dateien
unterschiedliche Klassen von Dateien mit unterschiedlichen Eigenschaften
z.B. .EXE ändern sich selten, nur bei Updates
Erkentnisse
kurzlebige Dateien nicht an Server überrtragen
Caching des Clients, da geringe meinsame Nutzung
Für unterschiedliche Dateiklassen unterschiedliche Verfahren
Strukturierung von Datei- und Verzeichnisdiensten
beides auf einem Server
geringerer Kommunikationsbedarf
auf getrennten Servern
höhere Flexibilität
-
Statuslose vs. Statusbehaftete Dateiservices
Caching
4 Möglichkeiten zur Speicherung
Festplatte Server
einfachste Umsetzung
viel Speicherplatz
für alle Clients erreichbar
keine Konsistenzprobleme
Performanceprobleme
laden in den HS und Übertragung
Server-Caching
performanter
trotzdem immer wieder Übertragung über Netz
geringerer Speicher
keine Konsistenzprobleme
Client-Caching im HS
Caching nur Prozessweit
Caching im Kernel
Daten stehen allen Prozessen zur Verfügung
Nachteil: Kernelaufruf
Spezieller Cache-Manager auf Benutzerebene
Client-Cache auf Festplatte
nicht wirklich angewandt
Lösungen für die durch Client-Cache verursachte Inkosistenz
Write-Through-Algorithmus
Änderung an Datei direkt auch an Server geschickt
Clients mit gecachter Version stimmen sich mit Server über Korrektheit ab
per Version oder Hashes
Verzögertes Schreiben
Performanceverbesserung durch 30-Sekündiges Sammeln von Änderungen
nur ein Aufruf statt viele
temporäre Dateien wieder gelöscht, bevor abgeschickt
Sitzungsprotokoll
erst Schreiben beim Schließen
teilweise erst 30 Sekunden später
Zentrale Steuerung
Nur ein Client darf Datei offen haben
nicht geeignet für große Systeme
Replikation
Kopie eines Objektes auf anderer Maschine
mehrere Replikate möglich
Vorteile
Erhöhte Zuverlässigkeit
Zugriff möglich, wenn ein Server nicht verfügbar (Wartung, Absturz, …)
Verteilung der Arbeitslast
Implementation von Replikation
-
explizite Replikation
Client steuert Replikation
keine Transparenz
träge Replikation
Server erzeugt Replikation, wenn er Zeit hat (nicht ausgelastet ist)
Replikation per Gruppenkommunikation (Siehe Ende Kapitel 2)
ein WRITE-Aufruf wird an alle Server gleichzeitig übertragen
-
Middleware
Softwareschicht
Schnittstelle zwischen Betriebssystem und Anwendung
Dateisysembasierte Middleware
nach zwei Transfermodellen programmierbar
Upload/Download Modell
Kopie der Datei
Upload nach Änderung
Vorteile
einfache Implementierung
Effizienter ganze Dateien zu übertragen (solange kein Overhead)
Nachteile
genügend Speicher auf Client
Konsistenzprobleme
Remote-Access Modell
Client sendet Komandos an Server
-
Network File System (NFS)
ein Remote-Access Modell
unterstützt heterogene Systeme
zufällige Menge von Clients und Server bilden ein gemeinsames Dateisystem
NFS-Server exportiert ein oder mehrere Verzeichnisse
NFS-Client kann Verzeichnisse importieren (mounten)
Vorteile
Plattenlose Rechner mit NFS betreibbar
Kommunikation über Dateien in gemeinsamen Verzeichnissen
Importprotokoll
Client sendet Pfad des Imprtverzeichnisses an Server
Server gibt (bei Gültigkeit) Datei-Handle zurück
zukünftige Zugriffe auf Dateien des importierten Verzeichnisses arbeiten mit diesem Handle
automatisches Importieren
Client sendet Anfrage an alle Server mit der Datei
Client importiert Datei vom Ersten Server der Antwortet
Vorteile
Bei Serverausfall trotzdem importierbar
Performancevorteil, da Server mit geringster Last (wahrscheinlich) am schnellsten Antworten wird
Nachteil
importierendes Dateisystem muss auf allen Servern gleich sein
NFS bietet keinen Replikationsmechanismen
daher häufig nur Read-Only-Dateisysteme
Datei- und Verzeichniszugriffsprotokoll
Jede Operation in sich abgeschlossen
kein OPEN & CLOSE
statuslos
keine Sperren auf Dateien
arbeitet mit UNIX rwx-Bits
verschlüsselte Übertragung der Gruppe & Users
NFS-Impelementierung
oberste Schicht
Systemaufrufschicht
READ, WRITE, OPEN, CLOSE
mittlere Schicht: Virtual File System (VFS)
Verwaltet V-Nodes
gibt an, ob lokal oder enfternte Datei
-
unterste Schicht: Betriebssystem oder NFS
Übertragung vom/zum (Lesen/Schreiben) Server in 8K-Einheiten
höhere Effizienz
Client-Cache
Nach Ablauf eines Timers verworfen
Beim Öffenen Aktualität der Datei prüfen
Andrew Filesystem (AFS)
Upload/Download-Modell
Workstations in Zellen gruppiert
ein LAN
Zellen bilden eine Gruppe
Verzeichnisbaum modifizierter klassischer UNIX-Baum
/cmu beinhaltet gemountete entfernte Verzeichnisse
Öffnen holt gesammte Datei vom Server
Schließen lädt Datei auf Server hoch
Cachen der Datei
Server merkt sich, wer welche Datei hat
Wenn anderer Client B Datei anfordert, informiert Server Client A
Client A schickt, bei Änderung, die geänderte Datei an Server
Besonders geeignet für Einsatz im WAN
-
Remote-Dateizugriff unter Windows-NT-Familie
Minschform von statusbehaftetem & statuslosem Server
LANMan Redirector
Treiber für Clients
sendet Anfragen an LANMan Server
LANMan Server
Treiber für Server
verarbeitet Anfragen von LANMan Redirector
Client-Caching
Zur Verhinderung von Inkonsistenz Benutzung des Protokolls Oplock (opportunistic locking)
-
Oplock
Ebene-I-Oplock
Client verfügt exklusiven Zugriff auf Datei
Client darf Lese- und Schreibzugriffe ausführen
Ebene-II-Oplock
Schreibzugriffe verboten
Will Client schreiben, wird Oplock ungültig
Stapel-Oplock
darf Lesen & Schreiben
Ohne Oplock darf Datei nicht lokal gecacht werden
Alle Änderungen an den Server sofort übertragen
Jeder Lesezugriff direkt vom Server
-
Common Object Request Broker Architecture (COBRA)
Objektorientiertes Client-Server-System
heterogen
Object Request Brokers (ORB)
kapseln low-level Verteilungs- und Kommunikationsdetails & verstecken sie vor Client- und Server-Code
Interface Definition Language (IDL)
Angabe welche Methoden eines Objektes exportiert werden, sowie deren Parameter(typen)
Jedes COBRA-Objekt kann nur auf einem einzigen Server sein
bei starken Zugriff Performanceprobleme
Schlussfolgerungen
Clientzyklen sind günstiger
Was möglich ist, auf Client ausführen
Caching so häufig wie möglich einsetzen
Viele Zugriffe auf temporäre Dateien ohne gemeinsamen Nutzen
Systemweites Wissen minimieren
Sicherheit von möglichst wenigen Komponenten abhängig machen
Wo möglich Batchbetrieb einsetzen
Synchronisierung in verteilten Systemen
Physikalische Uhren
Quarzblock in Schwingung
pro Schwingung bestimmter Zähler eins erniedrigt
sobald Zähler auf 0, interrupt, ein Uhrtick rauf
Zähler wieder auf Ausgangswert
Anhand des Zählers die Tickrate der Uhr einstellbar
Algorithmen zur Uhrensynchronisation
Über Zeit eine Abweichung der Uhren
für Verteilte Systeme schon im kleinsten Bereich fatal
Christian-Algorithmus
Maschinen fragen periodisch bei Zeitserver (mit UTC-Empfänger) nach aktueller Zeit
Zurückstellen nicht möglich
daher verminderten Zeitwert pro Tick hinzufügen, bis synchron
Vorstellen durch erhöhten Zeitwert pro Tick bis synchron
Abziehen der Transportzeit
Transportzeit T = (T3 – T0) – (T2 – T1)
Logische Uhren (ehr nicht)
richtige Reihenfolge teilweise ausreichend
nur synchronisieren, wenn Prozesse miteinander kooperieren
Lamport-Algorithmus
nebenläufige Ereignisse
zwei oder mehr Prozesse, ohne Abhängigkeit in der Zeit
Uhrzeit nur vorwärts, niemals rückwärts
-
Vorderung: niemals 2 Ereignisse zur gleichen Zeit
Prozessnummer an Zeit anhängen
zwei Prozesse zur selben Zeit, niedrigere Prozessnummer wird als früher interpretiert
Vollständig sortierter Multicast
Multicastnachrichtenh gehen ebenfalls an Sender & tragen Lamport-Zeitstempel
Voraussetzung: Keine Nachricht geht verloren
Nachricht wird lokal anhand des Zeitstempels einsortiert
Bestätigungsmulticast geht an andere Prozesse
Nach gewisser Zeit haben alle gleiche Warteschlange
Prozess darf Nachricht nur verarbeiten, wenn
Nachricht am Beginn der Warteschlange
Nachricht von allen anderen Prozessen bestätigt