تحديد الموعد النهائي الأقرب أولاً

خوارزمية "الأقرب موعدًا أولًا " ( EDF )، أو "الأقل وقتًا متبقيًا" ، هي خوارزمية جدولة ديناميكية تُستخدم في أنظمة التشغيل الآنية لوضع العمليات في قائمة انتظار ذات أولوية . عند حدوث أي حدث جدولة (انتهاء مهمة، أو إطلاق مهمة جديدة، إلخ)، يتم البحث في قائمة الانتظار عن العملية الأقرب إلى موعدها النهائي. هذه العملية هي التالية التي يتم جدولتها للتنفيذ.

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

مع جدولة العمليات الدورية التي تساوي مواعيدها النهائية فتراتها، فإن لـ EDF حد استخدام بنسبة 100%. وبالتالي، فإن اختبار قابلية الجدولة ^{[ 1 ] [ 2 ]} لـ EDF هو:

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq 1,}$

حيث${\displaystyle \left\{C_{i}\right\}}$تمثل هذه أسوأ أوقات الحساب في الحالة${\displaystyle n}$العمليات و${\displaystyle \left\{T_{i}\right\}}$^{[ 3 ]} هي فترات الوصول بين كل منها (بافتراض أنها تساوي المواعيد النهائية النسبية).

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

لاحظ أنه يجب استخدام صيغة اختبار الجدولة مع اعتبار الموعد النهائي هو الفترة. عندما يكون الموعد النهائي أقل من الفترة، يختلف الأمر. إليك مثال: هناك أربع مهام دورية تحتاج إلى جدولة، حيث تُمثل كل مهمة برقم المهمة (وقت الحساب، الموعد النهائي النسبي، الفترة). هذه المهام هي: T0 (5، 13، 20)، T1 (3، 7، 11)، T2 (4، 6، 10)، وT3 (1، 1، 20). تحقق هذه المجموعة من المهام شرط ألا يتجاوز معدل الاستخدام 1.0، حيث يُحسب معدل الاستخدام كالتالي: 5/20 + 3/11 + 4/10 + 1/20 = 0.97 (بعد تقريب الرقمين)، ولكنها لا تزال غير قابلة للجدولة. راجع شكل "فشل جدولة EDF" لمزيد من التفاصيل.

تُعدّ خوارزمية EDF أيضًا خوارزمية جدولة مثالية على المعالجات أحادية النواة غير القابلة للمقاطعة، ولكن فقط ضمن فئة خوارزميات الجدولة التي لا تسمح بإدخال وقت خمول. عند جدولة العمليات الدورية التي تساوي مواعيدها النهائية فتراتها، يصبح اختبار قابلية الجدولة الكافي (ولكن ليس الضروري) لخوارزمية EDF كما يلي: ^{[ 4 ]}

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq {1-p},}$

حيث يمثل p عقوبة عدم الاستباق، المعطاة بالحد الأقصى${\displaystyle \left\{C_{i}\right\}}$/ دقيقة${\displaystyle \left\{T_{i}\right\}}$إذا أمكن إبقاء هذا العامل صغيرًا، فإن EDF غير الاستباقي يمكن أن يكون مفيدًا نظرًا لانخفاض تكلفة التنفيذ.

مع ذلك، عندما يتعرض النظام لحمل زائد، يصبح من الصعب التنبؤ بمجموعة العمليات التي ستتأخر عن المواعيد النهائية (إذ تعتمد على المواعيد النهائية الدقيقة ووقت حدوث الحمل الزائد). يُعد هذا عيبًا كبيرًا لمصممي أنظمة الوقت الحقيقي. كما أن الخوارزمية صعبة التنفيذ في الأجهزة ، وتوجد مشكلة معقدة في تمثيل المواعيد النهائية ضمن نطاقات مختلفة (لا يمكن أن تكون المواعيد النهائية أدق من دقة الساعة المستخدمة في الجدولة). إذا استُخدمت حسابات نمطية لحساب المواعيد النهائية المستقبلية نسبةً إلى الوقت الحالي، فيجب أن يستوعب الحقل الذي يخزن الموعد النهائي النسبي المستقبلي على الأقل قيمة ((مدة أطول وقت متوقع للإنجاز * 2) + الوقت الحالي). لذلك، لا يُستخدم EDF عادةً في أنظمة الحاسوب الصناعية التي تعمل في الوقت الحقيقي.

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

هناك مجموعة كبيرة من الأبحاث التي تتناول جدولة EDF في الحوسبة في الوقت الحقيقي ؛ من الممكن حساب أسوأ أوقات استجابة العمليات في EDF، والتعامل مع أنواع أخرى من العمليات غير العمليات الدورية، واستخدام الخوادم لتنظيم الأحمال الزائدة.

لنفترض وجود ثلاث عمليات دورية مجدولة على معالج أحادي قابل للمقاطعة. أوقات التنفيذ وفتراتها موضحة في الجدول التالي:

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

مخطط التوقيت

في مخطط التوقيت، تمثل الأعمدة شرائح زمنية مع زيادة الوقت إلى اليمين، وتبدأ جميع العمليات فتراتها عند الشريحة الزمنية 0. يشير التظليل الأزرق والأبيض المتناوب في مخطط التوقيت إلى فترات كل عملية، مع وجود مواعيد نهائية عند تغيرات اللون.

أول عملية مجدولة من قبل شركة EDF هي P2، لأن مدتها هي الأقصر، وبالتالي لها أقرب موعد نهائي. وبالمثل، عند اكتمال P2، يتم جدولة P1، تليها P3.

في الفترة الزمنية 5، يكون لكل من P2 و P3 نفس الموعد النهائي، حيث يتعين عليهما إكمال المهمة قبل الفترة الزمنية 10، لذلك قد تقوم شركة EDF بجدولة أي منهما.

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

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

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

في تحليلٍ لحركة مرور كثيفة لسلوك طابور خادم واحد في ظل سياسة جدولة "الأسبقية للأقرب موعدًا" مع إمكانية التراجع عن المواعيد، ^{[ 5 ]} فإن العمليات لها مواعيد نهائية ولا تُخدَم إلا حتى انقضاء تلك المواعيد. ويُعدّ جزء "العمل المتراجع عنه"، والذي يُعرَّف بأنه العمل المتبقي الذي لم يُخدَم بسبب انقضاء المواعيد النهائية، مقياسًا مهمًا للأداء.

من المتعارف عليه أن تطبيق جدولة الاستباق ذات الأولوية الثابتة (FPS) أبسط من جدولة الأولوية الديناميكية، مثل EDF. مع ذلك، عند مقارنة الاستخدام الأمثل للجدولة ذات الأولوية الثابتة (مع تحديد أولوية كل خيط بواسطة جدولة المعدل الرتيب )، يمكن أن تصل EDF إلى 100%، بينما تبلغ القيمة القصوى النظرية لجدولة المعدل الرتيب حوالي 69%. إضافةً إلى ذلك، يمكن جعل الحمل الزائد في أسوأ الحالات لتطبيق EDF (استباق كامل أو محدود/غير استباق) للمهام الدورية و/أو المتقطعة متناسبًا مع لوغاريتم أكبر تمثيل زمني مطلوب لنظام معين (لترميز المواعيد النهائية والفترات) باستخدام أشجار البحث الرقمية. ^{[ 6 ]} في الحالات العملية، مثل الأنظمة المدمجة التي تستخدم تمثيلًا زمنيًا ثابتًا 32 بت، يمكن اتخاذ قرارات الجدولة باستخدام هذا التطبيق في وقت ثابت قصير لا يعتمد على عدد مهام النظام. في مثل هذه الحالات، وجدت التجارب فرقًا طفيفًا ملحوظًا في الحمل الزائد بين EDF وFPS، حتى بالنسبة لمجموعات المهام ذات العدد الكبير نسبيًا. ^{[ 6 ]}

تجدر الإشارة إلى أن EDF لا يفترض أي افتراض محدد بشأن دورية المهام؛ وبالتالي، يمكن استخدامه لجدولة المهام الدورية وغير الدورية على حد سواء. ^{[ 3 ]}

على الرغم من أن تطبيقات EDF ليست شائعة في نواة الأنظمة التجارية التي تعمل في الوقت الحقيقي، إليك بعض الروابط لنواة مفتوحة المصدر وأنظمة تعمل في الوقت الحقيقي تطبق EDF:

• SHARK : ^{[ 14 ]} نظام التشغيل SHaRK RTOS، الذي يُنفذ إصدارات مختلفة من خوارزميات جدولة EDF وجدولة حجز الموارد
• ERIKA Enterprise : ^{[ 15 ]} ERIKA Enterprise، التي توفر تطبيقًا لـ EDF مُحسَّنًا لوحدات التحكم الدقيقة الصغيرة مع واجهة برمجة تطبيقات مشابهة لواجهة برمجة تطبيقات OSEK .
• نواة Everyman : ^{[ 16 ]} تقوم نواة Everyman بتنفيذ جدولة EDF أو جدولة Deadline Monotonic اعتمادًا على تكوين المستخدم.
• MaRTE OS : ^{[ 17 ]} يعمل MaRTE OS كوقت تشغيل لتطبيقات Ada وينفذ مجموعة واسعة من خوارزميات الجدولة بما في ذلك EDF.
• يمثل مشروع AQuoSA تعديلًا لنواة لينكس، يُثري مُجدول العمليات بإمكانيات جدولة EDF. لا يمكن أن يكون توقيت الجدولة دقيقًا كما هو الحال في أنظمة التشغيل ذات الوقت الحقيقي الصارمة المذكورة أعلاه، ولكنه دقيق بما يكفي لتعزيز إمكانية التنبؤ بشكل كبير، وبالتالي تلبية متطلبات الوقت الحقيقي لتطبيقات الوسائط المتعددة. يُعد AQuoSA أحد المشاريع القليلة التي توفر إمكانيات جدولة الوقت الحقيقي للمستخدمين غير المميزين على النظام بطريقة مُحكمة، من خلال نموذج مُصمم بشكل مناسب للتحكم في الوصول. ^{[ 18 ]}
• تحتوي نواة لينكس على تطبيق "الأولوية الأولى" الذي يُطلق عليه اسم "الأولوية الأولى" SCHED DEADLINEوهو متاح منذ الإصدار 3.14.
• يُعدّ مُجدوِل الوقت الحقيقي ^{[ 19 ]،} الذي طُوّر في إطار مشروع IRMOS الأوروبي ^{[ 20 ]} ، مُجدوِلًا متعدد المعالجات يعمل في الوقت الحقيقي لنواة لينكس، وهو مناسبٌ بشكلٍ خاص للعزل الزمني وتوفير ضمانات جودة الخدمة لمكونات البرامج المعقدة متعددة الخيوط، وكذلك للآلات الافتراضية بأكملها . على سبيل المثال، عند استخدام لينكس كنظام تشغيل مضيف و KVM كمُشرف للآلات الافتراضية، يُمكن استخدام IRMOS لتوفير ضمانات الجدولة للآلات الافتراضية الفردية، وفي الوقت نفسه عزل أدائها لتجنب التداخلات الزمنية غير المرغوب فيها. يتميز IRMOS بمُجدوِل هرمي مُدمج يجمع بين EDF وFP . على المستوى الخارجي، يوجد مُجدوِل EDF مُقسّم على وحدات المعالجة المركزية المُتاحة. ومع ذلك، فإن الحجوزات متعددة وحدات المعالجة المركزية، ويتم استخدام FP عالمي عبر مُعالجات متعددة على المستوى الداخلي لجدولة الخيوط (أو العمليات) المُرفقة بكل حجز EDF خارجي. ^{[ 21 ]}
• يحتوي نظام Xen على مُجدول EDF منذ فترة. ^{[ 22 ]}
• يتضمن نظام التشغيل Plan 9 من مختبرات Bell بروتوكول EDFI، [ 23 ^{] وهو "} بروتوكول جدولة خفيف الوزن في الوقت الحقيقي يجمع بين EDF وتوريث المواعيد النهائية على الموارد المشتركة". ^{[ 24 ]}
• RTEMS : ^{[ 25 ]} سيكون برنامج جدولة EDF متاحًا في الإصدار 4.11. ^{[ 26 ]}
• Litmus-RT : ^{[ 27 ]} امتدادٌ لنظام لينكس يعمل في الوقت الحقيقي، ويركز على جدولة ومزامنة المعالجات المتعددة في الوقت الحقيقي. تتضمن مجموعة خوارزمياته للوقت الحقيقي خوارزميات جدولة Partitioned-EDF وGlobal-EDF وClustered-EDF.
• جدولة XNU Clutch: ^{[ 28 ]} اعتبارًا من عام 2018، تقوم نواة XNU الخاصة بشركة Apple بتنفيذ خوارزمية EDF في جدولة Clutch بهدف تحسين الاستجابة.
• نظام التشغيل SuperTinyKernel RTOS : ^{[ 29 ]} نظام تشغيل خفيف الوزن وعالي الأداء مصمم للأنظمة المدمجة المزودة بمعالجات ARM Cortex-M أو RISC-V. منذ الإصدار 1.1.2، يوفر STK مُجدول EDF للتطبيقات ذات الوقت الحقيقي الصارم ، مما يتيح توقيتًا قابلاً للتنبؤ على الأجهزة ذات الموارد المحدودة.

• جدولة الأولويات الديناميكية
• تحديد الموعد النهائي الافتراضي المبكر أولاً
• سياسة موارد المكدس