جدولة الأولويات الديناميكية

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

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

تعتمد فكرة الجدولة الآنية على تقييد استخدام المعالج ضمن نطاق الاستخدام المُجدول لخوارزمية جدولة معينة، والذي يتراوح بين 0 و1. كلما ارتفع نطاق الاستخدام المُجدول، زاد استغلال الموارد، وبالتالي تحسنت الخوارزمية. في الجدولة القابلة للمقاطعة، توفر جدولة الأولوية الديناميكية، مثل جدولة أقرب موعد نهائي أولاً (EDF)، الاستخدام الأمثل المُجدول وهو 1، مقارنةً بأقل من 0.69 مع جدولة الأولوية الثابتة، مثل جدولة المعدل الرتيب (RM) . ^{[ 1 ]}

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

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

تقوم خوارزمية الجدولة هذه أولاً باختيار العمليات التي لديها أقل "وقت فائض". يُعرَّف وقت الفائض بأنه الفرق الزمني بين الموعد النهائي ووقت الجاهزية ووقت التشغيل.

بصورة أكثر رسمية، وقت الفراغ${\displaystyle s}$يتم تعريف العملية على النحو التالي:

${\displaystyle s=(dt)-c'}$

أين${\displaystyle d}$هو الموعد النهائي للعملية،${\displaystyle t}$هو الوقت الفعلي منذ بداية الدورة، و${\displaystyle c'}$يمثل الوقت المتبقي للحساب.

في خوارزميات الجدولة الآنية للوظائف الدورية، يلزم إجراء اختبار قبول قبل قبول أي وظيفة متقطعة ذات موعد نهائي محدد. ومن أبسط اختبارات القبول لهذه الوظائف حساب مقدار الوقت المتاح بين وقت إصدارها وموعد تسليمها النهائي.

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

• جدولة الموعد النهائي الأقرب أولاً - خوارزمية مختلفة لجدولة الأولويات الديناميكية، والتي تضمن الإنتاجية المثلى.