خوارزمية جدولة الأولويات: استباقية، غير استباقية
ناثانيال بروكس
⚡ ملخص ذكي
جدولة الأولويات هي طريقة لجدولة وحدة المعالجة المركزية (CPU) تختار العمليات بناءً على الأولوية، حيث تُنفذ المهام ذات الأولوية الأعلى أولاً. يمكن أن تكون هذه الجدولة استباقية أو غير استباقية، وتُعالج العمليات ذات الأولوية المتساوية وفقًا لأسبقية الوصول أو بالتناوب الدوري.
ما هي جدولة الأولويات؟
جدولة الأولوية هي طريقة لجدولة العمليات على أساس الأولوية. في هذه الخوارزمية، يقوم المجدول باختيار المهام للعمل حسب الأولوية.
يجب تنفيذ العمليات ذات الأولوية الأعلى أولاً ، في حين يتم تنفيذ الوظائف ذات الأولويات المتساوية على أساس دوري أو على أساس FCFS. تعتمد الأولوية على متطلبات الذاكرة ومتطلبات الوقت وما إلى ذلك.
أنواع جدولة الأولويات
ينقسم جدولة الأولويات إلى نوعين رئيسيين:
جدولة وقائية
في الجدولة الوقائية، يتم تعيين المهام في الغالب وفقًا لأولوياتها. في بعض الأحيان يكون من المهم تشغيل مهمة ذات أولوية أعلى قبل مهمة أخرى ذات أولوية أقل، حتى لو كانت المهمة ذات الأولوية المنخفضة لا تزال قيد التشغيل. يتم الاحتفاظ بالمهمة ذات الأولوية المنخفضة لبعض الوقت وتستأنف عندما تنتهي المهمة ذات الأولوية الأعلى من تنفيذها.
جدولة غير استباقية
في هذا النوع من جدولة المهام، يتم تخصيص وحدة المعالجة المركزية لعملية محددة. تقوم العملية التي تشغل وحدة المعالجة المركزية بتحريرها إما عن طريق تغيير سياقها أو إنهاء عملها. هذه هي الطريقة الوحيدة التي يمكن استخدامها على مختلف منصات الأجهزة، لأنها لا تتطلب أجهزة خاصة (مثل المؤقت) كما هو الحال في جدولة المهام الاستباقية.
خصائص جدولة الأولويات
- خوارزمية وحدة المعالجة المركزية التي تقوم بجدولة العمليات بناءً على الأولوية.
- يتم استخدامه في Operaأنظمة تينغ لأداء العمليات المجمعة.
- إذا كانت هناك وظيفتان لهما نفس الأولوية جاهزتان، فسيتم العمل على أ من يأتي اولا، يخدم اولا الأساس.
- في جدولة الأولويات، يتم تعيين رقم لكل عملية يشير إلى مستوى الأولوية الخاص بها.
- كلما انخفض الرقم، زادت الأولوية.
- في هذا النوع من خوارزميات الجدولة، إذا وصلت عملية أحدث ذات أولوية أعلى من العملية قيد التشغيل حاليًا، فسيتم مقاطعة العملية قيد التشغيل حاليًا.
مثال على جدولة الأولويات
ضع في اعتبارك العمليات الخمس التالية من P1 إلى P5. لكل عملية أولوية فريدة، ووقت تنفيذ، ووقت وصول.
| طريقة عملنا | درجة الأهمية | وقت الانفجار | وقت الوصول |
|---|---|---|---|
| P1 | 1 | 4 | 0 |
| P2 | 2 | 3 | 0 |
| P3 | 1 | 7 | 6 |
| P4 | 3 | 4 | 11 |
| P5 | 2 | 2 | 12 |
الخطوة 0) عند الزمن = 0، تصل العمليتان P1 وP2. تتمتع P1 بأولوية أعلى من P2. يبدأ التنفيذ بالعملية P1، والتي يبلغ زمن تنفيذها 4.
الخطوة 1) عند الزمن = 1، لا تصل أي عملية جديدة. يستمر التنفيذ مع العملية P1.
الخطوة 2) في الوقت 2، لا تصل أي عملية جديدة، لذا يمكنك المتابعة مع P1. P2 في قائمة الانتظار.
الخطوة 3) في الوقت 3، لا تصل أي عملية جديدة، لذا يمكنك المتابعة مع العملية P1. لا تزال العملية P2 في قائمة الانتظار.
الخطوة 4) في الوقت 4، انتهى P1 من تنفيذه. يبدأ P2 التنفيذ.
الخطوة 5) عند الزمن = 5، لا تصل أي عملية جديدة، لذلك نستمر مع العملية P2.
الخطوة 6) عند الزمن = 6، يصل البرنامج P3. يتمتع P3 بأولوية أعلى (1) مقارنةً بـ P2 الذي يتمتع بأولوية (2). يتم مقاطعة P2، ويبدأ P3 تنفيذه.
| طريقة عملنا | درجة الأهمية | وقت الانفجار | وقت الوصول |
|---|---|---|---|
| P1 | 1 | 4 | 0 |
| P2 | 2 | 1 من أصل 3 معلق | 0 |
| P3 | 1 | 7 | 6 |
| P4 | 3 | 4 | 11 |
| P5 | 2 | 2 | 12 |
الخطوة 7) في الوقت 7، لم تصل أي عملية جديدة، لذلك نواصل مع P3. P2 في قائمة الانتظار.
الخطوة 8) عند الزمن = 8، لا تصل أي عملية جديدة، لذلك يمكننا المتابعة مع العملية P3.
الخطوة 9) عند الزمن = 9، لا توجد عملية جديدة، لذلك يمكننا المتابعة مع العملية P3.
الخطوة 10) في الفترة الزمنية 10، لا تظهر أي عملية جديدة، لذلك نواصل مع العملية P3.
الخطوة 11) عند الوقت = 11، يصل P4 بالأولوية 4. P3 لديه أولوية أعلى، لذلك يستمر في تنفيذه.
| طريقة عملنا | درجة الأهمية | وقت الانفجار | وقت الوصول |
|---|---|---|---|
| P1 | 1 | 4 | 0 |
| P2 | 2 | 1 من أصل 3 معلق | 0 |
| P3 | 1 | 2 من أصل 7 معلق | 6 |
| P4 | 3 | 4 | 11 |
| P5 | 2 | 2 | 12 |
الخطوة 12) عند الزمن = 12، يصل P5. يتمتع P3 بأولوية أعلى، لذا يستمر في التنفيذ.
الخطوة 13) عند الزمن 13، يكتمل تنفيذ العملية P3. لدينا العمليات P2 وP4 وP5 في قائمة الانتظار. تتمتع العمليتان P2 وP5 بنفس الأولوية. يصل P2 قبل P5، لذا يبدأ P2 التنفيذ.
| طريقة عملنا | درجة الأهمية | وقت الانفجار | وقت الوصول |
|---|---|---|---|
| P1 | 1 | 4 | 0 |
| P2 | 2 | 1 من أصل 3 معلق | 0 |
| P3 | 1 | 7 | 6 |
| P4 | 3 | 4 | 11 |
| P5 | 2 | 2 | 12 |
الخطوة 14) عند الزمن 14، تكون العملية P2 قد انتهت من تنفيذها. أما العمليتان P4 وP5 فهما في حالة انتظار. تتمتع العملية P5 بأعلى أولوية وتبدأ التنفيذ.
الخطوة 15) عند الزمن = 15، يستمر P5 في التنفيذ.
الخطوة 16) عند الزمن 16، تكون العملية P5 قد انتهت من تنفيذها. العملية P4 هي العملية الوحيدة المتبقية، وهي تبدأ التنفيذ.
الخطوة 17) عند الزمن = 20، يكون P4 قد أكمل التنفيذ ولم يتبق أي عملية.
الخطوة 18) لنحسب متوسط وقت الانتظار للمثال أعلاه.
وقت الانتظار = وقت البدء – وقت الوصول + وقت الانتظار للاندفاع التالي
P1 = 0 - 0 = 0 P2 = 4 - 0 + 7 = 11 P3 = 6 - 6 = 0 P4 = 16 - 11 = 5 Average Waiting time = (0 + 11 + 0 + 5 + 2)/5 = 18/5 = 3.6
مزايا جدولة الأولويات
فيما يلي فوائد/مزايا استخدام طريقة جدولة الأولويات:
- طريقة جدولة سهلة الاستخدام.
- يتم تنفيذ العمليات على أساس الأولوية، لذلك لا تحتاج العمليات ذات الأولوية العالية إلى الانتظار لفترة طويلة، مما يوفر الوقت.
- توفر هذه الطريقة آلية جيدة يمكن من خلالها تحديد الأهمية النسبية لكل عملية بدقة.
- مناسبة للتطبيقات ذات متطلبات الوقت والموارد المتقلبة.
عيوب جدولة الأولويات
فيما يلي سلبيات/عيوب جدولة الأولويات:
- إذا تعطل النظام في النهاية، فستفقد كافة العمليات ذات الأولوية المنخفضة.
- إذا كانت العمليات ذات الأولوية العالية تستغرق الكثير من وقت وحدة المعالجة المركزية، فقد تتوقف العمليات ذات الأولوية المنخفضة عن العمل وسيتم تأجيلها لفترة غير محددة.
- قد تترك خوارزمية الجدولة هذه بعض العمليات ذات الأولوية المنخفضة تنتظر إلى أجل غير مسمى.
- سيتم حظر العملية عندما تكون جاهزة للتشغيل ولكن يجب عليها انتظار وحدة المعالجة المركزية (CPU) لأن هناك عملية أخرى قيد التشغيل حاليًا.
- إذا استمرت عملية جديدة ذات أولوية أعلى في الظهور في قائمة الانتظار الجاهزة، فقد تحتاج العملية الموجودة في حالة الانتظار إلى الانتظار لفترة طويلة من الوقت.
