Verteilte Systeme CS5001

Th. LetschertTH Mittelhessen Gießen

University of Applied Sciences

Einführung

Seite 2

Administratives

Unterlagen Verwendbar: Master of Science (Informatik)

Wahlpflichtfach (Theorie-Pool)

Unterlagen Folien: homepages.thm.de/hg51– Aufgaben: homepages.thm.de/hg51 [Moodle-Kurs] Literatur

Veranstaltungsform 4 SWS, Vorlesung und Übung (seminaristisch) Bitte bringen Sie Ihr Notebook zu jeder Veranstaltung mit! Bitte kommen Sie pünktlich und nur wenn Sie sich an der Veranstaltung aktiv oder

passiv beteiligen wollen!

Bewertung Eine End-Klausur Eine Hausübung als Klausurzulassung

Hausübung = Lösung + Präsentation der Übungen

Seite 3

Administratives

VoraussetzungenKenntnisse und Fertigkeiten:

– Bachelor in Informatik– Ausreichende Entwicklerkompetenz – Kenntnis der wesentlichen Konzepte der Nebenläufigkeit (Synchronisation, Mutex,

Semaphor, etc.) – Mathematische Grundlagen (Diskrete Strukturen)

InhaltVerteilte Systeme mit Schwerpunkt auf verteilten Algorithmen

LiteraturG. Tel: Introduction to Distributed Algorithms, Cambridge University Press A. D. Kshemkalyani, M. Singhal: Distributed ComputingV. K. Garg : Concurrent and Distributed Computing in Java, John WileyA. S.Tanenbaum, M. van Steen: Distributed Systems, Prentice HallNancy Lynch: Distributed Algorithms, Morgan Kaufmann

Seite 4

Verteilte Systeme

Was ist ein verteiltes SystemEin verteiltes System ist

– ein System das aus mehreren aktiven Komponenten besteht – die sich an verschiedenen (eventuell logischen) Orten befinden und– die eine gemeinsame Anwendung realisieren.

Also ein– lose gekoppeltes

d.h. keine gemeinsamen Ressourcen, nur Nachrichtenaustausch– nebenläufiges System.

Aktive Komponenten = autonome Handlungsträger (Agenten: Personen, Rechner, Prozesse, ...)

– kooperieren– nur durch den Austausch von Nachrichten

Die Verteiltheit kann– physikalisch sein (Verteilung im Raum)– logisch sein (kommunizierende Prozesse)

Seite 5

Verteilte Systeme

Warum verteilt– Natürliche Verteiltheit

Viele Systeme sind der Aufgabenstellung her verteilt (Email, Web, ..)

– Steigerung der Leistung Lastteilung Parallele Verarbeitung

– erhöhte Robustheit Redundanz Backup-Systeme

– Wirtschaftlichkeit Viele kleine Systeme sind kostengünstiger als

ein gleich leistungsfähiges großes System

Seite 6

Verteilte Systeme

Besondere Herausforderungen– Komplexe und vielfältige Problemstellungen

– Algorithmische Probleme der Verteiltheit Verteilt = Nebenläufig unter verschärften Bedingungen (ohne gemeinsamen Speicher, gemeinsame Uhr, ...)

sequenziell + Prozesse => nebenläufignebenläufig – gemeinsamer Ressource => verteilt

– Komplexe Infrastruktur / Heterogenes Umfeld(diverse) Netze,

(diverse) Betriebssysteme (diverse) Datendarstellungen

(diverse) neueste / coolste / heftig umstrittene / wechselnde Infrastrukturkonzepte mit ihren Marketingstrategien

Seite 7

Verteilte Systeme

ZielVerteilte Systeme haben die Aufgabe, die besonderen Probleme der Verteiltheit zu lösen und damit die Verteiltheit auf irgendeiner Ebene transparent (unsichtbar) zu machen.

– unsichtbar für den Benutzerverteilte Anwendungen machen die Verteiltheit für den Benutzer transparent

– unsichtbar für das Anwendungsprogrammverteilte Betriebssysteme / Middleware machen die Verteiltheit für die Anwendung transparent

– Unsichtbar für andere Systemprogrammez.B. IP-Routing macht IP-Netze für TCP/UDP transparent

Transparenz – ist schwer zu erreichen und darum oft nur graduell angestrebt– hat verschiedene Aspekte (Ortstransparenz, Replikationstransparenz, ...)

Seite 8

Verteilte Systeme

Verteilte AlgorithmenVerteilte Algorithmen sind ein wichtiges Thema der verteilten systeme und Schwerpunkt der Veranstaltung

Herausforderungen verteilter Algorithmen

Nebenläufig / Nichtdeterministisch / ohne 'globale Sicht'

– Kein beteiligter Agent (Maschine / Prozess,..) verfügt über vollständige Informationen über das (Gesamt-) System

– Entscheidungen müssen auf Basis unvollständiger Informationen getroffen werden

– Nichtdeterministisch: Variierende Nachrichtenlaufzeit, divergierende Prozessorgeschwindigkeit, …

– Der Ausfall eines Agenten (Maschine / Prozess,..) stoppt das Gesamtsystem nicht: es kann – und muss (wie?) ! – weiter betrieben werden.

Seite 9

Verteilte Algorithmen

EinsatzVerteilte Algorithmen sind vor allem in der Software der Infrastruktur im Einsatz

– Netzprotokolle Routing Fehlerkontrolle Verbindungsmanagement

– Transaktionssysteme Reservierungen verteilte DB

– Middelware Synchronisation Terminierungs- / Deadlock-Entdeckung verteilte (virtuelle) Ressourcen: Speicher, Uhr, …

– Mobile Anwendungen

– Sensornetze

– · · ·

Seite 10

Verteilte Algorithmen

Verteilt vs. nicht verteilt– Nicht-verteilt

Berechnung: Funktion Input ~> Output– Verteilt

Netz von Knoten die sich Nachrichten zusenden Jeder Knoten wickelt einen lokalen Algorithmus ab, wenn Nachrichten

eintreffen I.d.R. Weniger Algorithmen als Knoten Berechnung: End(?)-Zustand eines / aller Knoten

Funktion

Eingabe

Ausgabe

Nicht verteilt: sequentiell - funktional

R

R

R

I

R

Verteilt: zustandsoroientiert, reaktiv

Seite 11

Verteilte Systeme

Ziel der Veranstaltung

Vertrautheit mit etablierten Themen- und Problemstellungen Denkweisen Theorien Ergebnissen

der verteilten Systeme mit Schwerpunkt auf verteilten Algorithmen

Seite 12

Verteilte Systeme

Beispiel

Gegeben ein Netz aus Knoten

Jeder Knoten hat eine positive ganze Zahl als Startwert

Jeder Knoten kann seinen Nachbarn Nachrichten beliebigen Inhalts zusenden. Weitere Interaktionen sind nicht erlaubt. Außer der Bekanntschaft mit ihren Nachbarn haben die Knoten keine Information über das Gesamtnetz

Gesucht: Ein Algorithmus oder mehrere Algorithmen deren Ausführung auf den Knoten dazu führt, dass irgendwann jeder Knoten den GGT aller Startwerte kennt und sich auch dieser Tatsache bewusst ist.

60 72

114

10284

18