Zeitsynchronisationsalgorithmen sind weit verbreitet.
In Unix-Systemen wird der Make-Befehl beispielsweise nur zum Kompilieren neu geänderter Codedateien verwendet. Der Make-Befehl verwendet die Uhr des laufenden Clients, um zu bestimmen, welche Dateien geändert wurden. Wenn der Code jedoch auf dem Dateiserver platziert wird und die Uhrzeit, zu der der Host den Make-Befehl ausführt, von der des Dateiservers abweicht, funktioniert der Make-Befehl möglicherweise nicht ordnungsgemäß.
Wenn Sie beispielsweise Dota spielen, benötigen mehrere Clients eine synchronisierte Uhr, um das Bild aller konsistent zu halten. Beispielsweise kann durch die Serverzeitsynchronisation eines PC-Computers eine sehr hohe Synchronisationsgenauigkeit erreicht werden.
Zeitsynchronisationsalgorithmus
Der Zeitsynchronisationsalgorithmus bietet die folgenden Lösungen:
Cristians Algorithmus
Der Anwendungshintergrund des Cristian-Algorithmus liegt hauptsächlich darin, dass ein Prozess P wie ein Server S ist, der Zeit anfordert:
1. P sendet ein Anforderungspaket an S, um die Uhrzeit anzufordern.
2. Nachdem S das Anforderungspaket von P empfangen hat, fügt es dem Paket die aktuelle S-Zeit hinzu und sendet es dann zurück.
3. Nachdem P das Datenpaket empfangen hat, setzt es die aktuelle Zeit auf T+RTT/2.
RTT stellt eine Round Trip Time dar, also die Zeit vom Senden von P bis zum Empfangen eines Datenpakets. Der Algorithmus geht davon aus, dass das Senden und Empfangen von Paketen im Netzwerk gleich lange dauert. Und es wird auch davon ausgegangen, dass die Zeit von S bei der Bearbeitung von Anfragen vernachlässigbar ist. Basierend auf den oben genannten Annahmen kann der Algorithmus wie folgt verbessert werden:
Senden Sie mehrere Anforderungspakete von P nach S, nehmen Sie dann die kleinste RTT als RTT dividiert durch zwei und addieren Sie sie zur in diesem Paket enthaltenen Zeit.
Analyse der Algorithmusgenauigkeit: Nehmen Sie an, dass min die kürzeste Zeit von S nach P und T die in der oben definierten RTT enthaltene Zeit ist. Dann sollte der Bereich der P-Einstellzeit [T+min, T+RTT-min] sein. Auf diese Weise liegt der Zeitabweichungsbereich innerhalb von RTT-2min. Die Genauigkeit des verbesserten Algorithmus sollte RTT/2-Minuten betragen.
Algorithmus Berkeley-Algorithmus
Die Nutzungsumgebung des Berkeley-Algorithmus unterscheidet sich vom Cristian-Algorithmus. Der Cristian-Algorithmus wird verwendet, wenn ein Client die korrekte Zeit von einem Server anfordert. Der Berkeley-Algorithmus ist ein Algorithmus zur Synchronisierung von Uhren zwischen mehreren Clients. Der spezifische Algorithmus lautet wie folgt:
1. Wählen Sie zunächst mithilfe von Change und Roberts Algorithmus einen Knoten aus einem Ring als Master aus.
2. Ein Master verwendet den Cristian-Algorithmus, um die Zeit jedes Knotens anzufordern.
3. Der Master bewertet die Zeitabweichung jedes Knotens, indem er die durchschnittliche RTT aufzeichnet und RTTs mit großen Abweichungen eliminiert.
4. Der Master sendet die Zeitabweichung jedes Knotens an jeden Knoten, sodass sich die Knoten selbst korrigieren können.
Nachdem der Client die Uhrzeit erhalten hat, wird er die aktuelle Uhrzeit im Allgemeinen nicht mehr anpassen. Denn dies führt zu unerklärlichen Fehlern im Programm. Denn in vielen Algorithmen wird grundsätzlich davon ausgegangen, dass die Zeit nicht zurückverstellt wird. Beispiel: make command.
Es gibt eine Lösung: Lassen Sie die Uhr einfach langsamer laufen. Nehmen Sie sich etwas Zeit, um sich auf die richtige Zeit einzustellen.
Darüber hinaus müssen der Algorithmus Change und der Robert-Algorithmus diskutiert werden. Dieser Algorithmus ist derselbe wie der Zeitsynchronisationsalgorithmus und wird beim Spielen von Dota benötigt. Wenn Dota initialisiert wird, müssen die Uhren jedes Spielers synchronisiert werden. Nachdem Sie offline waren, muss ein bestimmter Algorithmus verwendet werden, um einen neuen Host zu finden:
Veränderung und Roberts Algorithmus
Der Algorithmus von Change und Robert geht davon aus, dass jeder Prozess eine UID hat und dass es in einem ringförmigen Netzwerk einen richtungslosen Kommunikationskanal geben kann. Der Algorithmus ist wie folgt:
1. Zunächst identifiziert sich jeder Knoten im Ring als Nichtteilnehmer.
2. Wenn ein Prozess feststellt, dass der Host offline ist, identifiziert er sich zunächst als Teilnehmer und sendet dann ein vom Host ausgewähltes Paket mit seiner eigenen UID an den Nachbarn.
3. Wenn das Datenpaket den Nachbarn erreicht, vergleicht dieser es zunächst mit seiner eigenen UID, identifiziert sich als Teilnehmer, ändert die UID im Datenpaket und sendet diese ebenfalls Daten im Uhrzeigersinn.
4. Wenn ein Prozess ein Datenpaket empfängt und feststellt, dass die UID im Datenpaket mit seiner eigenen UID übereinstimmt, startet er die zweite Phase des Algorithmus:
5. Dieser Prozess identifiziert sich als Nichtteilnehmer und sendet Informationen über den ausgewählten Host an den Nachbarn, einschließlich UID-Informationen.
6. Dieser Zyklus wird fortgesetzt, bis der Prozess zu dem als Host ausgewählten Prozess zurückkehrt. Der gesamte Prozess endet.
Dies ist ein Algorithmus zur Auswahl eines Hosts in einem verteilten System. Natürlich können Sie unter bestimmten Umständen die Auswahlbedingungen ändern, z. B. diejenige mit der schnellsten Netzwerkgeschwindigkeit oder der schnellsten CPU als Host auswählen. Gleichzeitig kann dieser Algorithmus auch vermeiden, dass mehrere Prozesse gleichzeitig feststellen, dass der Host offline ist, und mehrere Prozesse gleichzeitig nach dem Host suchen.
Der Pseudocode dieses Algorithmus kann wie folgt beschrieben werden:
Start: M:= i:
<i> an den Nachbarn senden;
Beim Empfang der Nachricht <j>;
Wenn M<j, dann M:=j;
<j> an den Nachbarn senden;
Elseif M=j dann Anführer;
Endif;
Eine detaillierte Komplexitätsanalyse, mathematische Modelle und statistische Tabellen dieses Algorithmus finden Sie in diesem Dokument:
http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf
In diesem Artikel werden nur mehrere Zeitsynchronisationsalgorithmen in zentrilisierten Systemen analysiert, nicht jedoch die Synchronisationsalgorithmen Network Time Protocol und Reference Broadcast in verteilten Systemen. Ich werde NTP studieren, wenn ich in Zukunft Zeit habe.