อัลกอริธึมการซิงโครไนซ์เวลาและการวิเคราะห์อัลกอริธึมอัลกอริธึมการเลือกตั้งตามวงแหวนอย่างง่าย

อัลกอริธึมการซิงโครไนซ์เวลาถูกนำมาใช้กันอย่างแพร่หลาย

ตัวอย่างเช่น ในระบบ Unix คำสั่ง Make ใช้เพื่อคอมไพล์ไฟล์โค้ดที่แก้ไขใหม่เท่านั้น คำสั่ง Make ใช้นาฬิกาของไคลเอ็นต์ที่รันอยู่เพื่อกำหนดว่าไฟล์ใดได้รับการแก้ไข อย่างไรก็ตาม หากโค้ดถูกวางบนไฟล์เซิร์ฟเวอร์ และเวลาของโฮสต์ที่รันคำสั่ง make แตกต่างจากเวลาของไฟล์เซิร์ฟเวอร์ คำสั่ง make อาจทำงานไม่ถูกต้อง

ตัวอย่างเช่น เมื่อเล่น Dota ไคลเอนต์หลายรายจำเป็นต้องมีนาฬิกาที่ซิงโครไนซ์เพื่อให้ภาพของทุกคนสอดคล้องกัน ตัวอย่างเช่น เวลาเซิร์ฟเวอร์การซิงโครไนซ์คอมพิวเตอร์พีซีสามารถบรรลุความแม่นยำในการซิงโครไนซ์ที่สูงมาก

อัลกอริธึมการซิงโครไนซ์เวลา

อัลกอริธึมการซิงโครไนซ์เวลามีวิธีแก้ไขดังต่อไปนี้:

อัลกอริทึมของคริสเตียน

พื้นหลังแอปพลิเคชันของอัลกอริทึมอัลกอริทึมของ Cristian ส่วนใหญ่จะเกิดขึ้นเมื่อกระบวนการ P เหมือนกับเวลาที่เซิร์ฟเวอร์ S ร้องขอ:

1. P ส่งแพ็กเก็ตคำขอไปที่ S เพื่อขอเวลา

2. หลังจากที่ S ได้รับแพ็กเก็ตคำขอของ P มันจะเพิ่มเวลา S ปัจจุบันให้กับแพ็กเก็ตแล้วส่งกลับ

3. หลังจากที่ P ได้รับแพ็กเก็ตข้อมูลแล้ว จะตั้งเวลาปัจจุบันเป็น T+RTT/2

RTT แสดงถึง Round Trip Time ซึ่งเป็นเวลาตั้งแต่ P ส่งไปจนถึงการรับแพ็กเก็ตข้อมูล อัลกอริทึมจะถือว่าการส่งและรับแพ็กเก็ตใช้เวลาบนเครือข่ายเท่ากัน และสันนิษฐานว่าเวลาของ S นั้นน้อยมากเมื่อดำเนินการตามคำขอ จากสมมติฐานข้างต้น สามารถปรับปรุงอัลกอริทึมได้ดังนี้:

ส่งแพ็กเก็ตคำขอหลายรายการจาก P ถึง S จากนั้นนำ RTT ที่น้อยที่สุดเป็น RTT หารด้วยสอง แล้วบวกเข้ากับเวลาที่รวมอยู่ในแพ็กเก็ตนี้

การวิเคราะห์ความแม่นยำของอัลกอริทึม: สมมติว่า min คือเวลาที่สั้นที่สุดจาก S ถึง P และ T คือเวลาที่รวมอยู่ใน RTT ที่กำหนดไว้ข้างต้น จากนั้น ช่วงเวลาการตั้งค่า P ควรเป็น [T+min, T+RTT-min] ด้วยวิธีนี้ ช่วงการเบี่ยงเบนของเวลาจะอยู่ภายใน RTT-2 นาที ความแม่นยำของอัลกอริทึมที่ได้รับการปรับปรุงควรเป็น RTT/2 นาที

อัลกอริธึม อัลกอริธึมเบิร์กลีย์

สภาพแวดล้อมการใช้งานของอัลกอริทึม Berkeley แตกต่างจากอัลกอริทึมแบบ Cristian อัลกอริธึม Cristian ถูกใช้เมื่อไคลเอนต์ร้องขอเวลาที่ถูกต้องจากเซิร์ฟเวอร์ อัลกอริธึม Berkeley เป็นอัลกอริธึมสำหรับการซิงโครไนซ์นาฬิการะหว่างไคลเอนต์หลายตัว อัลกอริธึมเฉพาะมีดังนี้:

1. ขั้นแรกเลือกโหนดจากวงแหวนเป็น Master จนถึง Change และ Algorithm ของ Robert

2. มาสเตอร์ใช้อัลกอริธึม Cristian เพื่อขอเวลาของแต่ละโหนด

3. ต้นแบบจะประเมินค่าเบี่ยงเบนเวลาของแต่ละโหนดโดยการบันทึก RTT เฉลี่ยและกำจัด RTT ที่มีการเบี่ยงเบนมาก

4. Master จะส่งค่าเบี่ยงเบนเวลาของแต่ละโหนดไปยังแต่ละโหนด เพื่อให้โหนดสามารถแก้ไขตัวเองได้

หลังจากที่ลูกค้าได้รับเวลา โดยทั่วไปแล้ว จะไม่ปรับเวลาปัจจุบันกลับ เพราะจะทำให้เกิดข้อผิดพลาดบางอย่างที่อธิบายไม่ได้ในโปรแกรม เนื่องจากในอัลกอริธึมหลายๆ ตัว มันเป็นสมมติฐานพื้นฐานที่ว่าเวลาจะไม่ถูกปรับกลับ เช่น ทำคำสั่ง

มีวิธีแก้ไขคือปล่อยให้นาฬิกาเดินช้าลง ใช้เวลาในการปรับตัวให้เป็นเวลาที่ถูกต้อง

นอกจากนี้ จำเป็นต้องมีการหารือเกี่ยวกับการเปลี่ยนแปลงอัลกอริทึมและอัลกอริทึมของโรเบิร์ต อัลกอริธึมนี้เหมือนกับอัลกอริธึมการซิงโครไนซ์เวลา และจำเป็นเมื่อเล่น Dota เมื่อ Dota เริ่มต้นขึ้น นาฬิกาของผู้เล่นแต่ละคนจะต้องซิงโครไนซ์กัน หลังจากออฟไลน์ ต้องใช้อัลกอริธึมเฉพาะเพื่อค้นหาโฮสต์ใหม่:

การเปลี่ยนแปลงและอัลกอริทึมของโรเบิร์ต

อัลกอริธึม Change and Robert's Algorithm ถือว่าแต่ละกระบวนการมี UID และสามารถมีช่องทางการสื่อสารแบบไร้ทิศทางในเครือข่ายรูปวงแหวน อัลกอริทึมมีดังนี้:

1. ขั้นแรก แต่ละโหนดในวงแหวนจะระบุตัวเองว่าไม่ใช่ผู้เข้าร่วม

2. เมื่อกระบวนการพบว่าโฮสต์ออฟไลน์อยู่ ก่อนอื่นกระบวนการจะระบุตัวเองว่าเป็นผู้เข้าร่วม จากนั้นจะส่งแพ็กเก็ตที่โฮสต์เลือกซึ่งมี UID ของตัวเองไปยังเพื่อนบ้าน

3. เมื่อแพ็กเก็ตข้อมูลไปถึงเพื่อนบ้าน อันดับแรกจะเปรียบเทียบกับ UID ของตัวเอง หาก UID ของตัวเองมีขนาดใหญ่กว่า UID นี้ ก็จะระบุตัวเองว่าเป็นผู้เข้าร่วม แก้ไข UID ในแพ็กเก็ตข้อมูล และยังส่งข้อมูลนี้ใน ข้อมูลทิศทางตามเข็มนาฬิกา

4. เมื่อกระบวนการได้รับแพ็กเก็ตข้อมูลและพบว่า UID ในแพ็กเก็ตข้อมูลเหมือนกับ UID ของตัวเอง กระบวนการจะเริ่มขั้นตอนที่สองของอัลกอริทึม:

5. กระบวนการนี้ระบุตัวเองว่าไม่ใช่ผู้เข้าร่วมและส่งข้อมูลเกี่ยวกับโฮสต์ที่เลือกไปยังเพื่อนบ้าน รวมถึงข้อมูล UID

6. วงจรนี้จะดำเนินต่อไปจนกว่ากระบวนการจะกลับสู่กระบวนการที่เลือกเป็นโฮสต์ กระบวนการทั้งหมดจะสิ้นสุดลง

นี่คืออัลกอริทึมสำหรับการเลือกโฮสต์ในระบบแบบกระจาย แน่นอน ภายใต้สถานการณ์เฉพาะ คุณสามารถเปลี่ยนเงื่อนไขการเลือกได้ เช่น การเลือกเงื่อนไขที่มีความเร็วเครือข่ายเร็วที่สุดหรือ CPU ที่เร็วที่สุดเป็นโฮสต์ ในเวลาเดียวกัน อัลกอริทึมนี้ยังสามารถหลีกเลี่ยงสถานการณ์ที่หลายกระบวนการพบว่าโฮสต์ออฟไลน์ในเวลาเดียวกัน และหลายกระบวนการค้นหาโฮสต์ในเวลาเดียวกัน

รหัสเทียมของอัลกอริทึมนี้สามารถอธิบายได้ดังต่อไปนี้:

เริ่มต้น : ม:= ฉัน:

ส่ง <i> ให้เพื่อนบ้าน;

เมื่อได้รับข้อความ <j>;

ถ้า M<j แล้ว M:=j;

ส่ง <j> ให้เพื่อนบ้าน;

Elseif M=j จากนั้นเป็นผู้นำ;

เอนดิฟ;

สำหรับการวิเคราะห์ความซับซ้อนโดยละเอียด แบบจำลองทางคณิตศาสตร์ และตารางทางสถิติของอัลกอริทึมนี้ โปรดดูเอกสารนี้:

http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf

บทความนี้วิเคราะห์เฉพาะอัลกอริธึมการซิงโครไนซ์เวลาหลายครั้งในระบบศูนย์กลาง และไม่ได้วิเคราะห์โปรโตคอลเวลาเครือข่ายและอัลกอริธึมการซิงโครไนซ์การออกอากาศอ้างอิงในระบบแบบกระจาย ฉันจะเรียน NTP เมื่อมีเวลาในอนาคต