Hallo zusammen. In diesem Video geht es darum, wie man mithilfe der logischen Zeit,

die ihr im vorherigen Video kennengelernt habt, Synchronisation in einem verteilten

System realisieren kann. Dazu schauen wir uns auch das Log-Protokoll von Lampard an,

das ihr in dieser Aufgabe implementieren sollt. Wenn mehrere Prozesse gleichzeitig auf ein

gemeinsames Betriebsmittel zugreifen, braucht es eine Koordination dieser Zugriffe, also eine

Art wechselseitiger Ausstoß. Das gilt natürlich nicht nur bei mehrfädigem Programm, sondern auch

in einem verteilten System. Dabei gibt es verschiedene Möglichkeiten. Man kann einen

zentralen Koordinator einsetzen. Alle Zugriffe, egal von welchem Prozess, werden dann an dieser

einen Stelle koordiniert. Man kann sich die Prozesse aber auch untereinander selbstständig

koordinieren lassen. In beiden Fällen kann man einen exklusiven Zugriff auf eine Ressource aber

äquivalent zu der Bestimmung einer totalen Ordnung auf diese Ressource ansehen. Die Komponenten

einigen sich quasi darauf, in welcher Reihenfolge die Ressource verwendet werden darf. Also wann ein

Prozess den kritischen Abschnitt für diese Ressource betreten kann und realisieren so die

Koordinierung. Wie funktioniert das jetzt mit einem zentralen Koordinator? Hier wird ein Prozess

bestimmt, der für die Zuteilung zuständig ist. Alle anderen Prozesse müssen, wenn sie auf die

Ressource zugreifen wollen, bei diesem Koordinator anfragen. Diese sammelt die Anfragen, ordnet sie

und gibt jeweils dem nächsten Prozess, der an der Reihe ist, die Ressource frei, damit dieser dann

die Ressource verwenden kann, also den kritischen Abschnitt betreten kann. Wenn der Prozess fertig

ist, gibt es dem Koordinator Bescheid. Dieser kann nun im nächsten Prozess die Ressource zuteilen.

Auch wenn die Synchronisation mit einem zentralen Koordinator relativ einfach ist,

hat sie doch den Nachteil, dass alle Zugriffe eben über diesen zentralen Koordinator laufen

müssen und dort recht schnell ein Bottleneck entsteht. Daher gibt es die andere Möglichkeit,

die Synchronisation durch Einigung der Prozesse untereinander zu koordinieren.

Ein Algorithmus zur Synchronisation ohne zentralen Koordinator ist das Log-Protokoll von Lampard.

Hier verwendet man die durch den logischen Zeitstempel generierte totale Ordnung,

um Log-Anfragen an eine Ressource zu koordinieren. Es gibt einige Voraussetzungen,

damit der Algorithmus überhaupt erst funktioniert. Man braucht einen FIFO-Kanal für die Nachrichten.

Zuerst versendete Nachrichten müssen also auch zuerst ankommen. Die Reihenfolge der

Nachrichten darf nicht verändert werden. Zudem muss der Kanal zuverlässig sein. Es dürfen also

keine Nachrichten verloren gehen. Zusätzlich toleriert der Algorithmus ohne weiteres erst einmal

keine Ausfälle von den Prozessen. Wenn diese Voraussetzungen erfüllt sind, läuft das Protokoll

dann aber folgendermaßen ab. Erstens, wenn ein Prozess eine geteilte Ressource verwenden möchte,

schickt er eine Request-Nachricht per Broadcast an alle anderen Prozesse.

Jeder Prozess verwaltet jetzt eine Warteschlange mit allen aktuellen Request-Anfragen,

in der auch die eigene Anfrage eingereitet wird. Jetzt wartet ein Prozess, bis seine

eigene Anfrage ganz vorne in der Warteschlange ist und es keine andere Möglichkeit gibt,

dass ein anderer Prozess sich noch vor ihm in dieser Warteschlange einreihen könnte.

Diese Entscheidungen werden anhand der logischen Zeitstempel der Request-Nachrichten getroffen.

Wenn ein Prozess dann anhand dieser Kriterien als nächstes an der Reihe ist, kann er den

kritischen Abschnitt betreten und die Ressource verwenden. Anschließend, also wenn er mit der

Ressource fertig ist, sendet er per Broadcast eine Release-Nachricht an alle anderen Prozesse,

die dadurch wissen, dass der Prozess fertig ist und die Anfrage aus der Request-Warteschlange

gelöscht werden kann. Dann geht es mit dem nächsten Eintrag in der Warteschlange und im

nächsten Prozess weiter und so wird die ganze Sache koordiniert. Betrachten wir die einzelnen

Schritte aber noch mal genauer. Um zu wissen, welche Anfrage als nächstes an der Reihe ist,

verwaltet jeder Prozess eine Warteschlange für alle Request-Nachrichten. Alle eingehenden

Request-Nachrichten werden dort eingereicht. Das schließt auch die selbst gesendeten Nachrichten

mit ein. Die Sortierung der Warteschlange wird anhand der total geordneten Zeitstempel der logischen

Uhr durchgeführt. Ein Element wird dabei dann erst vom Kopf der Warteschlange entfernt,

wenn man ein korrespondierendes Release empfangen hat. Auch hier wird wieder nicht unterschieden,