خوارزمية جدولة الأولويات: مثال وقائي وغير وقائي
ناثانيال بروكس
ما هي جدولة الأولويات؟
جدولة الأولوية هي طريقة لجدولة العمليات على أساس الأولوية. في هذه الخوارزمية، يقوم المجدول باختيار المهام للعمل حسب الأولوية.
يجب تنفيذ العمليات ذات الأولوية الأعلى أولاً ، في حين يتم تنفيذ الوظائف ذات الأولويات المتساوية على أساس دوري أو على أساس 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، يكون P5 قد أكمل التنفيذ ولم يتبق أي عملية.
الخطوة 18) دعونا نحسب متوسط وقت الانتظار للمثال أعلاه.
وقت الانتظار = وقت البدء – وقت الوصول + وقت الانتظار للاندفاع التالي
P1 = o - o = o P2 =4 - o + 7 =11 P3= 6-6=0 P4= 16-11=5 Average Waiting time = (0+11+0+5+2)/5 = 18/5= 3.6
مزايا جدولة الأولويات
فيما يلي فوائد/إيجابيات استخدام طريقة جدولة الأولويات:
- طريقة جدولة سهلة الاستخدام
- يتم تنفيذ العمليات على أساس الأولوية بحيث لا تحتاج الأولوية العالية إلى الانتظار لفترة طويلة مما يوفر الوقت
- توفر هذه الطريقة آلية جيدة حيث يمكن تحديد الأهمية النسبية لكل عملية بدقة.
- مناسبة للتطبيقات ذات متطلبات الوقت والموارد المتقلبة.
عيوب جدولة الأولويات
فيما يلي سلبيات/عيوب جدولة الأولويات
- إذا تعطل النظام في النهاية، فستفقد كافة العمليات ذات الأولوية المنخفضة.
- إذا كانت العمليات ذات الأولوية العالية تستغرق الكثير من وقت وحدة المعالجة المركزية، فقد تتوقف العمليات ذات الأولوية المنخفضة عن العمل وسيتم تأجيلها لفترة غير محددة.
- قد تترك خوارزمية الجدولة هذه بعض العمليات ذات الأولوية المنخفضة تنتظر إلى أجل غير مسمى.
- سيتم حظر العملية عندما تكون جاهزة للتشغيل ولكن يجب عليها انتظار وحدة المعالجة المركزية (CPU) لأن هناك عملية أخرى قيد التشغيل حاليًا.
- إذا استمرت عملية جديدة ذات أولوية أعلى في الظهور في قائمة الانتظار الجاهزة، فقد تحتاج العملية الموجودة في حالة الانتظار إلى الانتظار لفترة طويلة من الوقت.
الملخص
- جدولة الأولوية هي طريقة لجدولة العمليات التي تعتمد على الأولوية. في هذه الخوارزمية، يقوم المجدول باختيار المهام للعمل حسب الأولوية.
- في الجدولة الوقائية ذات الأولوية، يتم تعيين المهام في الغالب مع أولوياتها.
- في طريقة الجدولة ذات الأولوية غير الوقائية، تم تخصيص وحدة المعالجة المركزية لعملية محددة.
- يتم تنفيذ العمليات على أساس الأولوية بحيث لا تحتاج الأولوية العالية إلى الانتظار لفترة طويلة مما يوفر الوقت
- إذا كانت العمليات ذات الأولوية العالية تستغرق الكثير من وقت وحدة المعالجة المركزية، فقد تتوقف العمليات ذات الأولوية المنخفضة عن العمل وسيتم تأجيلها لفترة غير محددة.
