جدولة التناوب الدوري

تُعدّ خوارزمية التوزيع الدوري ( Round-robin ) إحدى الخوارزميات المستخدمة في جدولة العمليات والشبكات في الحوسبة . ^{[ 1 ] [ 2 ]} وكما هو شائع، تُخصّص فترات زمنية (تُعرف أيضًا باسم الكميات الزمنية) ^{[ 3 ]} لكل عملية بالتساوي وبترتيب دائري، مع معالجة جميع العمليات دون تحديد أولوية (يُعرف أيضًا باسم التنفيذ الدوري ). تتميز جدولة التوزيع الدوري بالبساطة وسهولة التنفيذ وعدم وجود مشكلة تجويع الموارد . ويمكن تطبيقها على مشاكل جدولة أخرى، مثل جدولة حزم البيانات في شبكات الحاسوب. وهي مفهوم خاص بأنظمة التشغيل .

اسم الخوارزمية مشتق من مبدأ التناوب الدوري المعروف في مجالات أخرى، حيث يأخذ كل شخص حصة متساوية من شيء ما بالتناوب.

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

تعتبر خوارزمية التناوب الدوري خوارزمية استباقية حيث يقوم المجدول بإخراج العملية من وحدة المعالجة المركزية بمجرد انتهاء الحصة الزمنية.

على سبيل المثال، إذا كانت الفترة الزمنية 100 مللي ثانية، واستغرقت المهمة الأولى 250 مللي ثانية لإكمالها، فسيقوم مُجدول التناوب بتعليق المهمة بعد 100 مللي ثانية، ليمنح المهام الأخرى وقتها على وحدة المعالجة المركزية. وبمجرد حصول المهام الأخرى على حصتها المتساوية (100 مللي ثانية لكل منها)، ستحصل المهمة الأولى على تخصيص آخر لوقت وحدة المعالجة المركزية ، وتتكرر الدورة. تستمر هذه العملية حتى تنتهي المهمة ولا تحتاج إلى مزيد من الوقت على وحدة المعالجة المركزية.

• Job1 = إجمالي الوقت اللازم لإكمال المهمة 250 مللي ثانية (الكم 100 مللي ثانية) .

1. التخصيص الأول = 100 مللي ثانية.
2. التخصيص الثاني = 100 مللي ثانية.
3. التخصيص الثالث = 100 مللي ثانية، لكن المهمة 1 تنتهي ذاتيًا بعد 50 مللي ثانية.
4. إجمالي وقت وحدة المعالجة المركزية للمهمة 1 = 250 مللي ثانية

انظر إلى الجدول التالي الذي يوضح وقت الوصول ووقت التنفيذ للعملية مع زمن كمي قدره 100 مللي ثانية لفهم جدولة التناوب الدوري:

ثمة نهج آخر يتمثل في تقسيم جميع العمليات إلى عدد متساوٍ من وحدات التوقيت بحيث يتناسب حجم الوحدة مع حجم العملية. وبالتالي، تنتهي جميع العمليات في نفس الوقت.

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

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

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

إذا تم تقديم جودة خدمة مضمونة أو متميزة، وليس فقط التواصل بأفضل جهد، فقد يتم النظر في جدولة التناوب بالعجز (DRR)، أو جدولة التناوب المرجح (WRR)، أو جدولة الانتظار العادلة المرجحة (WFQ).

في الشبكات متعددة الوصول ، حيث يتم توصيل العديد من المحطات الطرفية بوسط مادي مشترك، يمكن توفير جدولة التناوب الدوري من خلال مخططات الوصول إلى القناة عن طريق تمرير الرمز المميز مثل Token Ring ، أو عن طريق الاستقصاء أو حجز الموارد من محطة تحكم مركزية.

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

• طابور متعدد المستويات
• SCHED_RR

• خوارزمية جدولة وحدة المعالجة المركزية المُحسّنة بتقنية التناوب الدوري
• جدولة التناوب الدوري في لغة C++
• جدولة التناوب الدوري في لغة C