Synchronisation1 Flashcards
Welche Probleme gibts es mit der Zeit bei zentralisierten und verteilten Systemen?
In einem zentralisierten System kein Problem, da es dort
nur eine Zeitquelle gibt.
In verteilten Systemen hat jedoch jeder Knoten seine
eigene Zeitquelle und damit u.U. eine andere Uhrzeit.
Wann läuft eine Uhr korrekt?
eine Uhr läuft korrekt, wenn sie die vom Hersteller
angegebene Driftrate ρ einhält, auch wenn sie dann zu
langsam oder schnell läuft.
Wie stellt man sicher, dass eine Uhr nie mehr als einen gewünschten Wert falsch geht?
Man muss sie periodisch synchronisieren
Wie funktioniert der Algorithmus von Christian?
Es wird die Existenz eines UTC-Empfängers im System
angenommen, der dann als Zeit-Server fungiert.
Jede andere Maschine sendet Time Requests an den Server, der so schnell wie möglich mit der aktuellen UTC antwortet.
Was sind die beiden Probleme, die beim Algorithmus von Christian auftreten?
Client-Uhr geht vor
Wegen Signallaufzeit ist Antwort, wenn sie kommt, schon veraltet.
Was will man mit der Einführung von NTP (Network Time Protocol) erreichen?
-Clients sollen sich möglichst genau mit UTC synchronisieren
können
-Bereitstellung eines zuverlässigen Dienstes mittels
Redundanz
-Clients sollen in der Lage sein, sich oft zu synchronisieren
Beschreiben Sie die funktionsweise von NTP
Der NTP-Dienst wird von einem Netzwerk von Servern
erbracht, Primary Servers sind direkt mit der UTC-Quelle
verbunden und Secondary Servers synchronisieren sich mit den Primary Servers.
-Clients synchronisieren sich mit dem Server mit der
geringsten gemessenen Signallaufzeit.
Wie funktioniert der Berkeley-Algorithmus?
-Ein Rechner wird als Zeit-Server bestimmt
-Zeit-Server fragt regelmäßig aktiv bei allen Rechner nach
aktueller Zeit und bildet Durchschnitt
-Durchschnitt wird allen Rechnern mitgeteilt, die ihre Uhren
danach anpassen
Warum wurde die logische Zeit eingeführt?
Da es unmöglich ist, physikalische Uhren in verteilten Systemen absolut zu synchronisieren. Einige Anwendungen benötigen jedoch genau diese Information, dafür aber keinen Bezug zur realen Zeit.
Beschreiben Sie die Happened-Before-Beziehung
-Notation a → b bedeutet: a hat vor b stattgefunden
-wenn in einem Prozess pi gilt: a →i b, dann gilt auch für das Gesamtsystem: a → b
-Ereignisse, die nicht in dieser Beziehung stehen, gelten als
nebenläufig
Wie funktioniert der zentrale Algorithmus zum gegenseitigen Ausschluss?
- Einer der Prozesse wird zum Koordinator für kritische Region bestimmt.
- Alle anderen benötigen Erlaubnis zum Betreten kritischer Region von Koordinator.
- Wenn kritische Region frei, erteilt Koordinator OK
- Token.
-Nach Verlassen kritischer Region
gibt Prozess Token zurück.
-Wenn kritische Region nicht frei, nimmt Koordinator Prozess in Warteschlange auf. Prozess erhält erst Token, wenn alle Prozesse vor ihm bedient wurden
Vorteile des zentralen Algorithmus?
-gegenseitiger Ausschluss wird erreicht
-fair: Tokens werden in Reihenfolge der Anfragen vergeben
-einfach zu implementieren
-nur 3 Nachrichten pro Zugang zu kritischer Region
(Anfrage, Erlaubnis, Freigabe)
Nachteile des zentralen Algorithmus?
- Koordinator ist Single Point of Failure
- mangelnde Skalierbarkeit (bzgl. Anzahl beteiligter Prozesse)
- Keine Antwort kann lange Warteschlange oder toten Koordinator bedeuten
Wie funktioniert der verteilte Algorithmus zum gegenseitigen Ausschluss?
- Besitzt keinen ausgewiesenen Koordinator.
- Jeder Prozess verwendet logische Uhr
- Wenn Prozess kritische Region betreten will, sendet er Request an alle anderen Prozesse.
- Erst wenn alle Prozesse OK gegeben haben, kann der Prozess die kritische Region betreten.
Warum ist der verteilte Algorithmus so scheisse?
- Jeder Knoten ist ein Single Point of Failure (lässt sich durch sofortige Bestätigungsnachrichten minimieren, aber nicht ausschalten)
- Jeder Prozess muss bei jeder Entscheidung mitwirken, auch wenn er selbst nicht konkurriert (Skalierbarkeit!)
- mehr Nachrichten, größere Netzwerklast
- Knoten mit langsamster Zeit gewinnt → nicht fair
