Les algorithmes de synchronisation temporelle sont largement utilisés.
Par exemple, dans les systèmes Unix, la commande Make est uniquement utilisée pour compiler les fichiers de code nouvellement modifiés. La commande Make utilise l'horloge du client en cours d'exécution pour déterminer quels fichiers ont été modifiés. Cependant, si le code est placé sur le serveur de fichiers et que l'heure à laquelle l'hôte exécute la commande make est différente de celle du serveur de fichiers, la commande make peut ne pas fonctionner correctement.
Par exemple, lorsque vous jouez à Dota, plusieurs clients ont besoin d'une horloge synchronisée pour que l'image de chacun reste cohérente. , Par exemple, l'heure du serveur de synchronisation de l'ordinateur PC peut atteindre une précision de synchronisation très élevée.
Algorithme de synchronisation temporelle
L'algorithme de synchronisation temporelle propose les solutions suivantes :
L'algorithme de Cristian
Le contexte d'application de l'algorithme de Cristian est principalement lorsqu'un processus P est comme un serveur S demandant du temps :
1. P envoie un paquet de requête à S pour demander l'heure.
2. Une fois que S a reçu le paquet de requête de P, il ajoute l'heure actuelle de S au paquet, puis le renvoie.
3. Une fois que P a reçu le paquet de données, il règle l'heure actuelle sur T+RTT/2.
RTT représente un Round Trip Time, qui est le temps écoulé entre l'envoi et la réception d'un paquet de données. L'algorithme suppose que l'envoi et la réception de paquets prennent le même temps sur le réseau. Et on suppose également que le temps de S est négligeable lors du traitement des requêtes. Sur la base des hypothèses ci-dessus, l'algorithme peut être amélioré comme suit :
Envoyez plusieurs paquets de requêtes de P à S, puis prenez le plus petit RTT comme RTT divisé par deux et ajoutez-le au temps inclus dans ce paquet.
Analyse de la précision de l'algorithme : supposons que min soit le temps le plus court entre S et P et que T soit le temps inclus dans le RTT défini ci-dessus. Ensuite, la plage du temps de réglage P doit être [T+min, T+RTT-min]. De cette façon, la plage d'écart temporel est comprise dans RTT-2min. La précision de l’algorithme amélioré devrait être RTT/2 min.
algorithme Algorithme de Berkeley
L'environnement d'utilisation de l'algorithme de Berkeley est différent de celui de Cristian. L'algorithme Cristian est utilisé lorsqu'un client demande l'heure correcte à un serveur. L'algorithme de Berkeley est un algorithme permettant de synchroniser les horloges entre plusieurs clients. L'algorithme spécifique est le suivant :
1. Sélectionnez d'abord un nœud d'un anneau comme maître à travers le changement et l'algorithme de Robert.
2. Un maître utilise l'algorithme Cristian pour demander l'heure de chaque nœud.
3. Le maître évalue l'écart temporel de chaque nœud en enregistrant le RTT moyen et en éliminant les RTT présentant des écarts importants.
4. Le maître envoie l'écart temporel de chaque nœud à chaque nœud, permettant aux nœuds de se corriger.
Une fois que le client a reçu l'heure, d'une manière générale, il ne réajustera pas l'heure actuelle. Parce que cela provoquera des erreurs inexplicables dans le programme. Parce que dans de nombreux algorithmes, l’hypothèse de base est que le temps ne sera pas réajusté. Par exemple, faites une commande.
Il existe une solution : laisser l’horloge tourner plus lentement. Prenez le temps de vous adapter à l’heure correcte.
De plus, l'algorithme Change et l'algorithme de Robert doivent être discutés. Cet algorithme est le même que l'algorithme de synchronisation temporelle et est nécessaire pour jouer à Dota. Lorsque dota est initialisé, les horloges de chaque joueur doivent être synchronisées. Après avoir été hors ligne, un algorithme spécifique doit être utilisé pour trouver un nouvel hôte :
Le changement et l'algorithme de Robert
L'algorithme de changement et de Robert suppose que chaque processus possède un UID et qu'il peut y avoir un canal de communication sans direction dans un réseau en forme d'anneau. L'algorithme est le suivant :
1. Premièrement, chaque nœud de l’anneau s’identifie comme non participant.
2. Lorsqu'un processus découvre que l'hôte est hors ligne, il s'identifie d'abord en tant que participant, puis envoie au voisin un paquet sélectionné par l'hôte contenant son propre UID.
3. Lorsque le paquet de données atteint le voisin, celui-ci le compare d'abord avec son propre UID. Si son propre UID est plus grand que cet UID, il s'identifie en tant que participant, modifie l'UID dans le paquet de données et l'envoie également dans le paquet de données. données dans le sens des aiguilles d’une montre.
4. Lorsqu'un processus reçoit un paquet de données et constate que l'UID du paquet de données est le même que son propre UID, il démarre la deuxième phase de l'algorithme :
5. Ce processus s'identifie comme non participant et envoie des informations sur l'hôte sélectionné au voisin, y compris des informations UID.
6. Ce cycle se poursuit jusqu'à ce que le processus revienne au processus sélectionné comme hôte. L'ensemble du processus se termine.
Il s'agit d'un algorithme de sélection d'un hôte dans un système distribué. Bien entendu, dans des circonstances spécifiques, vous pouvez modifier les conditions de sélection, comme choisir celui ayant la vitesse de réseau la plus rapide ou le processeur le plus rapide comme hôte. Dans le même temps, cet algorithme peut également éviter la situation dans laquelle plusieurs processus découvrent que l'hôte est hors ligne en même temps et où plusieurs processus recherchent l'hôte en même temps.
Le pseudocode de cet algorithme peut être décrit comme suit :
Début : M:= i:
Envoyez <i> au voisin ;
Lors de la réception du message <j> ;
Si M < j alors M : = j ;
Envoyer <j> au voisin ;
Sinon M=j alors leader ;
Finif ;
Pour une analyse détaillée de la complexité, des modèles mathématiques et des tableaux statistiques de cet algorithme, veuillez vous référer à cet article :
http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf
Cet article analyse uniquement plusieurs algorithmes de synchronisation temporelle dans le système centralisé et n'analyse pas les algorithmes de synchronisation de protocole de temps réseau et de diffusion de référence dans les systèmes distribués. J'étudierai NTP quand j'aurai le temps à l'avenir.