Modeling the Scheduling Algorithms of Periodic Tasks and Analyzing its Performance on Real-Time Multiprocessor Systems

يقدم البحث نمذجة و تحليل أداء عدد من خوارزميات الجدولة في أنظمة الزمن الحقيقي متعددة المعالجات. حيث تم تحليل أداء كل من الخوارزميات الثلاث: خوارزمية الجدولة بالزمن الحرج الأقصر أولاً EDF ، و خوارزمية الجدولة بالزمن الأقل خمولاً أولاً LLF ، و خوارزمية الجدولة بالزمن الحرج أولاً عند الخمول الصفري EDZL . شملت هذه الدراسة جدولة مهام دورية ذات قيود زمنية مساوية لدورها ، و مستقلة، و قابلة للمقاطعة على عدة معالجات متطابقة . تمت مقارنة الخوارزميات الثلاث من ناحية الحمل على المعالج (مشغولية المعالجات)، و من ناحية عدد الهجرات، و عدد المقاطعات، و عدد المرات التي لم تنجح فيها هذه الخوارزميات في تحقيق الحدود الزمنية للمهام، حيث يعتبر الأخير أهم معيار من معايير عملية الجدولة في الزمن الحقيقي. كما تضمنت الدراسة جدولة مجموعات متزايدة من المهام الدورية تبدأ من 4 مهام لتصل حتى 64 مهمة ، و ذلك لدراسة تأثير ازدياد عدد المهام و المعالجات على أداء خوارزميات الجدولة، و كنتيجة يقدم البحث نقاط القوة و الضعف في أداء هذه الخوارزميات و يقترح لكل خوارزمية - حسب نقاط القوة في أدائها- نوع منظومة الزمن الحقيقي التي من الأفضل تطبيقها فيها.

The research presents molding and analytical study of several scheduling algorithms types in real-time multiprocessor systems. The performance of three scheduling algorithms have been analyzed : Earliest Deadline First Scheduling (EDF) , Least Laxity First Scheduling (LLF), and Earliest Deadline First until Zero Laxity Scheduling (EDZL). This paper considers the scheduling of n periodic, independed, and preempted tasks with implicit deadlines on a platform of m homogenous multiprocessor. It has compared in terms of the load on the processor (processor's busyness) , the number of migrations, and the number of preemptions and the number of times in which these algorithms did not succeed in achieving the time limits for tasks where the latter is considered the most important criterion in real time scheduling. It also considers scheduling growing task sets of periodic tasks starting from 4 task set up to 64 task set, in order to study the effect of increasing the number of tasks and processors also on the performance of the scheduling algorithms. As a result of research, the strengths and weaknesses in the performance of these three algorithms have presented. It is proposed the best type of real-time system to apply each algorithm according to the strengths of its performance.