تستخدم خوارزميات مزامنة الوقت على نطاق واسع.
على سبيل المثال، في أنظمة Unix، يتم استخدام أمر Make فقط لتجميع ملفات التعليمات البرمجية المعدلة حديثًا. يستخدم أمر Make ساعة العميل قيد التشغيل لتحديد الملفات التي تم تعديلها. ومع ذلك، إذا تم وضع التعليمات البرمجية على خادم الملفات وكان وقت المضيف الذي يقوم بتشغيل أمر الإنشاء مختلفًا عن وقت خادم الملفات، فقد لا يعمل أمر الإنشاء بشكل صحيح.
على سبيل المثال، عند تشغيل Dota، يحتاج العديد من العملاء إلى ساعة متزامنة للحفاظ على اتساق الصورة للجميع. على سبيل المثال، يمكن أن يحقق وقت خادم مزامنة الكمبيوتر الشخصي دقة مزامنة عالية جدًا.
خوارزمية مزامنة الوقت
تحتوي خوارزمية مزامنة الوقت على الحلول التالية:
خوارزمية كريستيان
خلفية تطبيق خوارزمية كريستيان هي بشكل أساسي عندما تكون العملية P مثل الخادم S الذي يطلب الوقت:
1. يرسل P حزمة طلب إلى S لطلب الوقت.
2. بعد أن يتلقى S حزمة طلب P، فإنه يضيف وقت S الحالي إلى الحزمة ثم يرسلها مرة أخرى.
3. بعد أن يستقبل P حزمة البيانات، فإنه يضبط الوقت الحالي على T+RTT/2.
يمثل RTT وقت الرحلة ذهابًا وإيابًا، وهو الوقت من إرسال حزمة البيانات إلى استلامها. تفترض الخوارزمية أن إرسال واستقبال الحزم يستغرق نفس القدر من الوقت على الشبكة. ومن المفترض أيضًا أن وقت S لا يكاد يذكر عند معالجة الطلبات. بناءً على الافتراضات المذكورة أعلاه، يمكن تحسين الخوارزمية على النحو التالي:
أرسل حزم طلب متعددة من P إلى S، ثم خذ أصغر RTT مثل RTT مقسومًا على اثنين وأضفه إلى الوقت المضمن في هذه الحزمة.
تحليل دقة الخوارزمية: افترض أن الحد الأدنى هو أقصر وقت من S إلى P، وأن T هو الوقت المتضمن في RTT المحدد أعلاه. بعد ذلك، يجب أن يكون نطاق وقت الإعداد P [T+min، T+RTT-min]. وبهذه الطريقة، يكون نطاق الانحراف الزمني ضمن RTT-2min. يجب أن تكون دقة الخوارزمية المحسنة RTT/2-min.
خوارزمية بيركلي
تختلف بيئة استخدام خوارزمية بيركلي عن خوارزمية كريستيان. يتم استخدام خوارزمية كريستيان عندما يطلب العميل الوقت الصحيح من الخادم. خوارزمية بيركلي هي خوارزمية لمزامنة الساعات بين عدة عملاء. الخوارزمية المحددة هي كما يلي:
1. حدد أولاً عقدة من حلقة باعتبارها العقدة الرئيسية من خلال التغيير وخوارزمية روبرت.
2. يستخدم المعلم خوارزمية كريستيان لطلب وقت كل عقدة.
3. يقوم السيد بتقييم الانحراف الزمني لكل عقدة عن طريق تسجيل متوسط RTT وإزالة RTTs ذات الانحرافات الكبيرة.
4. يرسل السيد الانحراف الزمني لكل عقدة إلى كل عقدة، مما يسمح للعقد بتصحيح نفسها.
بعد أن يتلقى العميل الوقت، بشكل عام، لن يقوم بتعديل الوقت الحالي مرة أخرى. لأن هذا سوف يسبب بعض الأخطاء غير المبررة في البرنامج. لأنه في العديد من الخوارزميات، هناك افتراض أساسي بأن الوقت لن يتم تعديله مرة أخرى. على سبيل المثال، إصدار أمر.
هناك حل: فقط دع الساعة تعمل بشكل أبطأ. خذ بعض الوقت للتكيف مع الوقت الصحيح.
بالإضافة إلى ذلك، يجب مناقشة تغيير الخوارزمية وخوارزمية روبرت. هذه الخوارزمية هي نفس خوارزمية مزامنة الوقت وهي مطلوبة عند لعب Dota. عند تهيئة دوتا، يجب مزامنة ساعات كل لاعب. بعد عدم الاتصال بالإنترنت، يجب استخدام خوارزمية محددة للعثور على مضيف جديد:
التغيير وخوارزمية روبرت
تفترض خوارزمية التغيير وخوارزمية روبرت أن كل عملية لها معرف فريد (UID) وأنه يمكن أن تكون هناك قناة اتصال بدون اتجاه في شبكة على شكل حلقة. الخوارزمية هي كما يلي:
1. أولاً، تُعرّف كل عقدة في الحلقة نفسها على أنها غير مشاركة.
2. عندما تكتشف إحدى العمليات أن المضيف غير متصل بالإنترنت، فإنها تقوم أولاً بتعريف نفسها كمشارك، ثم ترسل حزمة مختارة من قبل المضيف تحتوي على UID الخاص بها إلى الجهاز المجاور.
3. عندما تصل حزمة البيانات إلى الجار، فإنها تقوم أولاً بمقارنتها مع UID الخاص بها. إذا كان UID الخاص بها أكبر من UID هذا، فإنها تعرف نفسها كمشارك، وتقوم بتعديل UID في حزمة البيانات، وترسل هذا أيضًا في ملف. اتجاه عقارب الساعة البيانات.
4. عندما تتلقى عملية ما حزمة بيانات وتجد أن UID الموجود في حزمة البيانات هو نفس UID الخاص بها، فإنها تبدأ المرحلة الثانية من الخوارزمية:
5. تعرّف هذه العملية نفسها على أنها غير مشاركة وترسل معلومات حول المضيف المحدد إلى الجار، بما في ذلك معلومات UID.
6. تستمر هذه الدورة حتى تعود العملية إلى العملية المحددة كمضيف، وتنتهي العملية بأكملها.
هذه خوارزمية لاختيار مضيف في نظام موزع. بالطبع، في ظل ظروف معينة، يمكنك تغيير شروط الاختيار، مثل اختيار الخادم الذي يتمتع بأقصى سرعة للشبكة أو أسرع وحدة معالجة مركزية كمضيف. في الوقت نفسه، يمكن لهذه الخوارزمية أيضًا تجنب الموقف الذي تجد فيه عمليات متعددة أن المضيف غير متصل بالإنترنت في نفس الوقت، وتبحث العديد من العمليات عن المضيف في نفس الوقت.
يمكن وصف الكود الكاذب لهذه الخوارزمية على النحو التالي:
البداية : م:= ط:
إرسال <i> إلى الجار؛
عند تلقي الرسالة <j>؛
إذا كان M<j ثم M:=j;
إرسال <j> إلى الجار؛
السيف م=ي ثم الزعيم؛
إنديف؛
للحصول على تحليل التعقيد التفصيلي والنماذج الرياضية والجداول الإحصائية لهذه الخوارزمية، يرجى الرجوع إلى هذه الورقة:
http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf
تحلل هذه المقالة فقط خوارزميات مزامنة الوقت المتعددة في النظام المركزي، ولا تحلل بروتوكول وقت الشبكة وخوارزميات مزامنة البث المرجعي في الأنظمة الموزعة. سأدرس NTP عندما يكون لدي الوقت في المستقبل.