الجدولة (الحوسبة)

يُعدّ مُجدوِل العمليات جزءًا من نظام التشغيل، وهو المسؤول عن تحديد أيّ العمليات تُنفّذ في وقتٍ مُعيّن. وعادةً ما يمتلك القدرة على إيقاف عمليةٍ قيد التشغيل مؤقتًا، ونقلها إلى نهاية قائمة الانتظار، ثمّ بدء عمليةٍ جديدة؛ ويُعرف هذا النوع من المُجدوِل باسم المُجدوِل الاستباقي . أما إذا لم يتمكّن المُجدوِل من إيقاف عمليةٍ قيد التشغيل مؤقتًا وبدء عمليةٍ جديدة، فيُعرف باسم المُجدوِل التعاوني . ^{[ 5 ]}

نميز بين الجدولة طويلة الأجل ، والجدولة متوسطة الأجل ، والجدولة قصيرة الأجل بناءً على عدد مرات اتخاذ القرارات. ^{[ 6 ]}

خوارزمية "الأول في الأول خارج " ( FIFO )، والمعروفة أيضًا باسم " الأول في الأول وصولًا" (FCFS)، هي أبسط خوارزميات الجدولة. ببساطة، تقوم FIFO بوضع العمليات في قائمة الانتظار حسب ترتيب وصولها إلى قائمة الانتظار الجاهزة. تُستخدم هذه الخوارزمية عادةً لـقائمة المهام ، على سبيل المثال كما هو موضح في هذا القسم.

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

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

يشبه هذا الأسلوب أسلوب "أقصر مهمة أولاً" (SJF). في هذا الأسلوب، يقوم المجدول بترتيب العمليات التي يتبقى لها أقل وقت معالجة مُقدّر لتكون التالية في قائمة الانتظار. يتطلب هذا معرفة متقدمة أو تقديرات دقيقة للوقت اللازم لإتمام كل عملية.

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

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

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

يُخصّص المُجدوِل وحدة زمنية ثابتة لكل عملية، ثم يُجري دورة بينها. إذا اكتملت العملية خلال تلك الفترة الزمنية، يتم إنهاؤها، وإلا يُعاد جدولتها بعد إعطاء الفرصة لجميع العمليات الأخرى.

• تتضمن جدولة السكك الحديدية تكاليف إضافية كبيرة، خاصة مع وحدة زمنية صغيرة.
• إنتاجية متوازنة بين FCFS/FIFO و SJF/SRTF، حيث يتم إنجاز المهام الأقصر بشكل أسرع من FIFO ويتم إنجاز العمليات الأطول بشكل أسرع من SJF.
• متوسط ​​وقت الاستجابة جيد، ووقت الانتظار يعتمد على عدد العمليات، وليس على متوسط ​​طول العملية.
• بسبب أوقات الانتظار الطويلة، نادراً ما يتم الالتزام بالمواعيد النهائية في نظام RR البحت.
• لا يمكن أن يحدث تجويع، إذ لا تُعطى أي أولوية. يعتمد ترتيب تخصيص وحدات الوقت على وقت وصول العملية، على غرار نظام FIFO (الوارد أولاً يُصرف أولاً).
• إذا كانت شريحة الوقت كبيرة، فإنها تصبح FCFS/FIFO أو إذا كانت قصيرة، فإنها تصبح SJF/SRTF.

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

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

توجد العديد من مشاكل الجدولة التي يكون الهدف منها هو تحديد أي مهمة تذهب إلى أي محطة وفي أي وقت، بحيث يتم تقليل إجمالي مدة الإنجاز :

• جدولة ورش العمل – يوجد عدد n من المهام وعدد m من المحطات المتطابقة. يجب تنفيذ كل مهمة على آلة واحدة. يُعتبر هذا عادةً مشكلةً متصلةً بالإنترنت. 
• جدولة العمل المفتوح – هناك n وظيفة و m محطة مختلفة. يجب أن تقضي كل وظيفة بعض الوقت في كل محطة، بترتيب حر. 
• جدولة التدفق في خط الإنتاج - هناك n وظيفة و m محطة مختلفة. يجب أن تقضي كل وظيفة بعض الوقت في كل محطة، بترتيب محدد مسبقًا. 

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

• مشاكل نقص الموارد
• قدرة عالية جدًا على التنبؤ؛ مما يسمح بتنفيذ أنظمة الوقت الحقيقي الصارمة
• لا توجد تكاليف إضافية تقريبًا
• قد لا يكون مثاليًا لجميع التطبيقات
• تعتمد الفعالية كلياً على التنفيذ

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

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

كان نظام التشغيل IBM OS/360 متوفرًا بثلاثة مُجدولات مختلفة. وكانت الاختلافات كبيرة لدرجة أن هذه المتغيرات كانت تُعتبر في كثير من الأحيان ثلاثة أنظمة تشغيل مختلفة:

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

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

كانت أنظمة MS-DOS وMicrosoft Windows في بداياتها غير داعمة لتعدد المهام، ولذلك لم تكن مزودة بجدول زمني. استخدم Windows 3.1x جدولًا زمنيًا غير استباقي، أي أنه لم يقاطع البرامج. كان يعتمد على البرنامج لإنهاء عمله أو إخبار نظام التشغيل بأنه لم يعد بحاجة إلى المعالج ليتمكن من الانتقال إلى عملية أخرى. يُعرف هذا عادةً بتعدد المهام التعاوني. قدم Windows 95 جدولًا زمنيًا استباقيًا بدائيًا؛ ومع ذلك، ولأغراض دعم الأنظمة القديمة، سمح بتشغيل تطبيقات 16 بت دون مقاطعة. ^{[ 10 ]}

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

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

يستخدم نظام التشغيل Mac OS 9 جدولة تعاونية للخيوط، حيث تتحكم عملية واحدة في عدة خيوط تعاونية، كما يوفر جدولة استباقية لمهام المعالجة المتعددة. تقوم النواة بجدولة مهام المعالجة المتعددة باستخدام خوارزمية جدولة استباقية. تعمل جميع عمليات مدير العمليات ضمن مهمة معالجة متعددة خاصة، تُسمى المهمة الزرقاء . تُجدول هذه العمليات بشكل تعاوني، باستخدام خوارزمية جدولة بالتناوب ؛ حيث تُسلّم عملية ما التحكم في المعالج إلى عملية أخرى عن طريق استدعاء دالة حظر صريحة WaitNextEvent. لكل عملية نسخة خاصة بها من مدير الخيوط الذي يُجدول خيوط تلك العملية بشكل تعاوني؛ حيث يُسلّم خيط ما التحكم في المعالج إلى خيط آخر عن طريق استدعاء YieldToAnyThreadدالة حظر YieldToThread. ^{[ 14 ]}

يستخدم نظام macOS طابور تغذية راجعة متعدد المستويات، مع أربع نطاقات أولوية للخيوط : عادي، وأولوية عالية للنظام، ووضع النواة فقط، والوقت الحقيقي. ^{[ 15 ]} تُجدول الخيوط بشكل استباقي؛ كما يدعم macOS أيضًا جدولة الخيوط بشكل تعاوني في تطبيقه لمدير الخيوط في Carbon . ^{[ 14 ]} 

في نظام AIX الإصدار 4، توجد ثلاث قيم محتملة لسياسة جدولة الخيوط:

• أسبقية الوصول، أسبقية الخروج: بمجرد جدولة عملية ما وفقًا لهذه السياسة، فإنها تستمر في العمل حتى اكتمالها ما لم يتم حظرها، أو تتنازل طواعيةً عن التحكم في وحدة المعالجة المركزية، أو تصبح عملية أخرى ذات أولوية أعلى قابلة للتنفيذ. ولا يمكن تطبيق سياسة جدولة أسبقية الوصول إلا على العمليات ذات الأولوية الثابتة.
• التوزيع الدوري: يشبه هذا النظام آلية التوزيع الدوري في نظام AIX الإصدار 3، والتي تعتمد على  فترات زمنية مدتها 10 مللي ثانية. عندما يتحكم أحد خيوط التوزيع الدوري في نهاية الفترة الزمنية، ينتقل إلى نهاية قائمة الخيوط القابلة للتوزيع وفقًا لأولويته. لا يمكن تطبيق سياسة التوزيع الدوري إلا على الخيوط ذات الأولوية الثابتة.
• أخرى: تُعرَّف هذه السياسة في معيار POSIX1003.4a على أنها مُحدَّدة حسب التنفيذ. في نظام AIX الإصدار 4، تُعرَّف هذه السياسة على أنها مُكافئة لسياسة RR، باستثناء أنها تُطبَّق على الخيوط ذات الأولوية غير الثابتة. إعادة حساب قيمة أولوية الخيط الجاري عند كل مقاطعة ساعة يعني أن الخيط قد يفقد التحكم لأن قيمة أولويته قد ارتفعت فوق قيمة أولوية خيط آخر قابل للإرسال. هذا هو سلوك نظام AIX الإصدار 3.

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

يُطبّق نظام AIX 5 سياسات الجدولة التالية: FIFO، والتوزيع الدوري، والتوزيع الدوري العادل. تتضمن سياسة FIFO ثلاثة تطبيقات مختلفة: FIFO، وFIFO2، وFIFO3. تُسمى سياسة التوزيع الدوري SCHED_RR في نظام AIX، بينما يُسمى التوزيع الدوري العادل SCHED_OTHER. ^{[ 16 ]}

يستخدم نظام FreeBSD طابور تغذية راجعة متعدد المستويات بأولويات تتراوح من 0 إلى 255. تُخصص الأولويات من 0 إلى 63 للمقاطعات، ومن 64 إلى 127 للجزء العلوي من النواة، ومن 128 إلى 159 لخيوط المستخدم في الوقت الحقيقي، ومن 160 إلى 223 لخيوط المستخدم ذات المشاركة الزمنية، ومن 224 إلى 255 لخيوط المستخدم الخاملة. وكما هو الحال في نظام Linux، يستخدم FreeBSD إعداد الطابور النشط، ولكنه يتضمن أيضًا طابورًا للخيول الخاملة. ^{[ 25 ]}

يستخدم نظام NetBSD قائمة انتظار متعددة المستويات ذات أولويات تتراوح من 0 إلى 223. يتم حجز الأرقام من 0 إلى 63 للخيوط المشتركة زمنيًا (الافتراضي، سياسة SCHED_OTHER)، ومن 64 إلى 95 لخيوط المستخدم التي دخلت مساحة النواة ، ومن 96 إلى 128 لخيوط النواة، ومن 128 إلى 191 لخيوط المستخدم في الوقت الحقيقي (سياسات SCHED_FIFO وSCHED_RR)، ومن 192 إلى 223 لمقاطعات البرامج .

يستخدم نظام سولاريس طابور تغذية راجعة متعدد المستويات، تتراوح أولوياته بين 0 و169. تُخصص الأولويات من 0 إلى 59 للخيوط المُشاركة زمنيًا، ومن 60 إلى 99 لخيوط النظام، ومن 100 إلى 159 لخيوط الوقت الحقيقي، ومن 160 إلى 169 للمقاطعات ذات الأولوية المنخفضة. على عكس لينكس، ^{[ 25 ]} عند انتهاء عملية ما من استخدام حصتها الزمنية، تُمنح أولوية جديدة وتُعاد إلى الطابور.  قدم سولاريس 9 فئتين جديدتين للجدولة، وهما فئة الأولوية الثابتة وفئة المشاركة العادلة. تتمتع الخيوط ذات الأولوية الثابتة بنفس نطاق أولوية فئة المشاركة الزمنية، ولكن أولوياتها لا تُعدل ديناميكيًا. تستخدم فئة الجدولة العادلة حصص وحدة المعالجة المركزية لتحديد أولويات الخيوط عند اتخاذ قرارات الجدولة. تشير حصص وحدة المعالجة المركزية إلى استحقاق مواردها، وتُخصص لمجموعة من العمليات، تُعرف مجتمعةً باسم مشروع. ^{[ 7 ]}