خوارزمية جدولة جولة روبن مع مثال
فريق التحرير
⚡ ملخص ذكي
تعتبر جدولة Round-Robin أقدم وأبسط خوارزمية استباقية لوحدة المعالجة المركزية، حيث تعمل كل عملية جاهزة لفترة زمنية ثابتة في قائمة انتظار دورية، مما يضمن تنفيذًا عادلًا وخاليًا من الحرمان من أجل تعدد المهام.
ما هي جدولة جولة روبن؟
يأتي اسم هذه الخوارزمية من مبدأ روبن الدائري، حيث يحصل كل شخص على حصة متساوية من شيء ما بالتناوب. إنها أقدم وأبسط خوارزمية جدولة، والتي تستخدم في الغالب للمهام المتعددة.
في جدولة التناوب الدوري، تُنفَّذ كل مهمة جاهزة بالتناوب فقط في طابور دوري لفترة زمنية محدودة. كما توفر هذه الخوارزمية تنفيذًا للعمليات دون حدوث أي انقطاع.
خصائص جدولة جولة روبن
فيما يلي الخصائص المهمة لجدولة Round-Robin:
- خوارزمية التناوب الدوري هي خوارزمية استباقية.
- يتم نقل وحدة المعالجة المركزية إلى العملية التالية بعد فترة زمنية ثابتة، والتي تسمى وحدة زمنية/شريحة زمنية.
- تتم إضافة العملية التي تم استباقها إلى نهاية قائمة الانتظار.
- نظام التناوب الدوري هو نموذج هجين يعتمد على التوقيت.
- ينبغي أن تكون الفترة الزمنية المخصصة للمهمة المحددة التي تحتاج إلى معالجة قصيرة. ومع ذلك، قد تختلف هذه الفترة من نظام تشغيل إلى آخر.
- إنها خوارزمية تعمل في الوقت الفعلي وتستجيب للحدث خلال فترة زمنية محددة.
- تُعتبر خوارزمية التناوب الدوري واحدة من أقدم الخوارزميات وأكثرها عدلاً وسهولة.
- إنها طريقة جدولة شائعة الاستخدام في أنظمة التشغيل التقليدية.
مثال على جدولة جولة روبن
ضع في اعتبارك العمليات الثلاث التالية:
| قائمة انتظار العملية | وقت الانفجار |
|---|---|
| P1 | 4 |
| P2 | 3 |
| P3 | 5 |
الخطوة 1) يبدأ التنفيذ بالعملية P1، التي لها وقت انفجاري 4. هنا، يتم تنفيذ كل عملية لمدة ثانيتين. لا يزال P2 وP2 في قائمة الانتظار.
الخطوة 2) عند الزمن = 2، تتم إضافة P1 إلى نهاية قائمة الانتظار ويبدأ P2 في التنفيذ.
الخطوة 3) عند الزمن = 4، يتم مقاطعة العملية P2 وإضافتها إلى نهاية قائمة الانتظار. وتبدأ العملية P3 بالتنفيذ.
الخطوة 4) عند الزمن = 6، يتم مقاطعة العملية P3 وإضافتها إلى نهاية قائمة الانتظار. وتبدأ العملية P1 بالتنفيذ.
الخطوة 5) عند الزمن = 8، يكون زمن تنفيذ العملية P1 هو 4. لقد أكملت العملية التنفيذ. تبدأ العملية P2 التنفيذ.
الخطوة 6) مدة تنفيذ العملية P2 هي 3. وقد نفذت بالفعل فترتين. عند الزمن 9، تنتهي العملية P2 من التنفيذ. ثم تبدأ العملية P3 بالتنفيذ حتى تنتهي.
الخطوة 7) لنحسب متوسط وقت الانتظار للمثال أعلاه.
Wait time P1 = 0 + 4 = 4 P2 = 2 + 4 = 6 P3 = 4 + 3 = 7
مزايا جدولة التناوب الدوري
فيما يلي مزايا وفوائد طريقة جدولة التناوب الدوري:
- لا تواجه هذه الدولة مشاكل المجاعة أو تأثير القوافل.
- تحصل جميع الوظائف على توزيع عادل لوحدة المعالجة المركزية.
- يتعامل مع جميع العمليات دون أي أولوية.
- إذا كنت تعرف العدد الإجمالي للعمليات في قائمة انتظار التشغيل، فيمكنك أيضًا افتراض وقت الاستجابة الأسوأ لنفس العملية.
- لا تعتمد طريقة الجدولة هذه على وقت الذروة، ولذلك يسهل تطبيقها على النظام.
- بمجرد تنفيذ عملية لمجموعة محددة من الفترة، يتم استباق العملية، ويتم تنفيذ عملية أخرى لتلك الفترة الزمنية المحددة.
- يسمح لنظام التشغيل باستخدام طريقة تبديل السياق لحفظ حالات العمليات التي تمت مقاطعتها.
- فهو يعطي أفضل أداء من حيث متوسط وقت الاستجابة.
مساوئ جدولة جولة روبن
فيما يلي عيوب/سلبيات استخدام جدولة التناوب الدوري:
- إذا كان وقت تقطيع نظام التشغيل منخفضًا، فسيتم تقليل إنتاج المعالج.
- تستغرق هذه الطريقة وقتاً أطول في تبديل السياق.
- يعتمد أدائها بشكل كبير على الكم الزمني.
- لا يمكن تحديد الأولويات للعمليات.
- لا يمنح نظام الجدولة بالتناوب أولوية خاصة للمهام الأكثر أهمية.
- يقلل ذلك من الفهم.
- يؤدي انخفاض كمية الوقت إلى زيادة الحمل الزائد لتبديل السياق في النظام.
- إن إيجاد كمية زمنية صحيحة مهمة صعبة للغاية في هذا النظام.
أسوأ حالة الكمون
يستخدم هذا المصطلح للحد الأقصى من الوقت المستغرق لتنفيذ جميع المهام.
- dt = يشير إلى وقت الكشف عند إضافة مهمة إلى القائمة
- st = يشير إلى وقت الانتقال من مهمة إلى أخرى
- et = يشير إلى وقت تنفيذ المهمة
الصيغة:
Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti + eti) N} + tISR
tISR = sum of all execution times
