دراسة تحليلية لخوارزميات جدولة المهام الدورية في نظم الزمن الحقيقي على معالج متعدد النوى

الملخص

Real Time Systems are considered nowadays as the most common systems, because its wide spread and usage in many areas including technical and applied researches, also the installation of such systems on multicore platforms made them very desirable as embedded systems and control units, because of its high performance and robustness comparing to multiprocessors platforms.

Scheduling is the basic operation in real time systems, and relies in ordering the execution of tasks depending on priorities witch is set according to scheduling policies.

This paper aims to introduce an analytical study of the most important scheduling algorithms to find the one with best performance according to number of parameters such as system load, context switching overheads, and scheduling overheads, when they applied to number of periodic tasks generated randomly.

We use for this purpose SIMSO real time systems simulator, because of its reliability, robustness, and the support to a large number of scheduling algorithms, and cache memory simulation with its different levels witch is considered to be the main component in multicore platforms.

تعتبر نظم الزمن الحقيقي من أكثر النظم شيوعاً في الوقت الحاضر، نظراً لانتشارها الواسع واستخدامها في شتى المجالات بما في ذلك الأبحاث التقنية والتطبيقية، فضلاً عن أنّ تطبيق مثل هذه النظم على منصات عمل متعددة النوى أضحى أمراً مرغوباً كما هو الحال في الأنظمة المضمنة ووحدات التحكم بسبب سرعة أداء مثل هذه المنصات وتماسكها مقارنة مع المنصات الأخرى متعددة المعالجات والتي تعاني من بطء في تبادل المعطيات المختلفة بسبب مقدار سرعة قنوات الاتصال بينها والذي عادة ما يكون أبطأ من ذلك الموجود في المنصات متعددة النوى.

تشكل جدولة المهام محور عمل نظم الزمن الحقيقي، وهي في حقيقتها تقوم على مبدأ ترتيب تنفيذ المهام اعتماداً على الأفضليات المسندة لها، وتختلف عملية الإسناد هذه باختلاف الخوارزمية المتبعة في الجدولة.

يهدف هذا البحث إلى تقديم دراسة تحليلية لأهم خوارزميات جدولة المهام الدورية وذلك لمقارنة أدائها على منصة متعددة النوى من حيث مجموعة من البارامترات مثل حمل المعالج، أعباء عمليات تبديل السياق، وأعباء اتخاذ قرار الجدولة، وذلك من أجل انتخاب الخوارزمية الأفضل من بين هذه الخوارزميات من حيث البارامترات المعتبرة عند تطبيقها على مجموعة من المهام الدورية المولدة عشوائياً.

تم استخدام المحاكي SIMSO لهذا الغرض، وذلك بسبب موثوقيته ودعمه لعدد كبير من خوارزميات الجدولة، بالإضافة إلى أنه يحاكي استخدام ذاكرة الكاش بمستوياتها المختلفة والتي تعتبر حجر الأساس في بنية المنصات متعددة النوى.