نمذجة خوارزميات الجدولة للمهام الدورية وتحليل أدائها في أنظمة الزمن الحقيقي متعددة المعالجات

Abstract

يقدم البحث نمذجة وتحليل أداء عدد من خوارزميات الجدولة في أنظمة الزمن الحقيقي متعددة المعالجات. حيث تم تحليل أداء كل من الخوارزميات الثلاث: خوارزمية الجدولة بالزمن الحرج الأقصر أولاً 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.