Self synchronizing clocks for real time systems

Abstract

The two functions achieved by clock synchronization algorithms are clock precision and clock accuracy The former keeps the drift between any two clocks in a given set of clocks within defined limits ; the latter maintains the drift between a given clock and a reference clock within defined limits While distributed non realtime systems need only clock precision for their correct operation clock accuracy is an absolute must for distributed realtime systems Many of the existing softwarebased clock synchronization algorithms implement only clock precision treating clock accuracy as a secondary problem often solved at a high cost As modern distributed realtime systems are emerging more and more it becomes necessary to devise an approach that deals with the precision and accuracy issues equally and in an integrated way The work presented in this paper consisted in the design and implementation of a softwarebased clock synchronization algorithm which achieves at the same time clock accuracy and clock precision The proposed algorithm is built upon a new mechanism referred to as self synchronization through which a clock can continuously synchronize itself relative to a reference clock independently of the others and with minimal message exchange An important aspect of this mechanism is to permit the implementation of a very low cost faulttolerant algorithm without resorting to any specific hardware We finally show that with proper architectural support the level of attainable accuracy can match hardwarebased solutions

إن الدورين الرئيسيين اللذين تقوم بهما خوارزميات تزامن عدادات الزمن هما دقة مجموعة من العدادات بالنسبة بعضها لبعض، وضبطها بالنسبة لزمن مرجعي حقيقي فالأولى تبقي الفرق بين أي عدادين من المجموعة ضمن حدود معروفة أما الثانية، فالهدف منها هو إبقاء الفرق بين أي عداد داخل المجموعة والعداد المرجعي في حدود معينة في حين أن النظم الموزعة غير المعتمدة على الزمن تحتاج إلى دقة العدادات فقط، فإن نظم الزمن الحقيقي لا يمكنها أن تستغنى عن الضبط بالنسبة لزمن مرجعي حقيقي إن العديد من الخوارزميات المبرمجة للقيام بتزامن العدادات تعتمد فقط على دقتها متعاملة مع مشكلة ضبط العدادات على أنها ثانوية مما يؤدي عادة إلى حلها بصفة مكلفة مع التطوير المتزايد لنظم الزمن الحقيقي الموزعة فقد أصبح لازما تصميم طريقة تأخذ بعين الاعتبارفي نفس الوقت وبصفة متوازيةدقة وضبط العدادات وقد قام هذا البحث بتصميم وتطبيق خوارزميات مبرمجة لتزامن العدادات تهدف إلى الحصول على دقة وضبط العدادات في آن واحد إن الخوارزمي المقترح مبني على نمطية جديدة تسمى [التزامن الذاتي]، والذي يتم من خلالها تزامن ذاتي مستمر من طرف أي عداد بالنسبة للعداد المرجعي، وبصفة مستقلة عن العدادات الأخرى ويتم هذا بالقيام بأقل قسط ممكن من تبادل الرسالات (عبر شبكات الحاسوب) إن الجانب المهم لهذه النمطية هو إمكانية القيام بتطبيق خوارزميات تزامن العدادات بحيث تكون أقل تكلفة وقابليتها لتحمل الأخطاء دون الرجوع إلى أي أجهزة إلكترونية مختصة وقد برهنا أخيرا على أنه باستعمال هيكلة مناسبة فإن مستوى الدقة الذي يمكن الحصول عليها تضاهي أي حل مرتكز على الأجهزة الإلكترونية من نوع الـ VLSI