الوحدة 9: جدولة أحادية المعالج

1️⃣ أنواع جدولة المعالج (Types of Processor Scheduling)

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

تنقسم جدولة المعالج إلى ثلاثة أنواع رئيسية، تختلف في نطاقها الزمني ومسؤولياتها:

🎯 تركيز الوحدة: نحن نركز في هذه الوحدة بشكل أساسي على **الجدولة قصيرة المدى (CPU Scheduling)**، وهي التي يتحكم بها ما يسمى بـ Scheduler (الجادول) داخل نواة نظام التشغيل.

2️⃣ خوارزميات جدولة المعالج (Scheduling Algorithms)

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

📍 أ. First-Come, First-Served (FCFS) - الداخل أولاً يُخدم أولاً

• الوصف: هي أبسط خوارزمية جدولة. تُنفذ كل عملية حسب ترتيب وصولها إلى قائمة الانتظار الجاهزة (Ready Queue). تشبه طابور الانتظار في البنك أو السوبر ماركت.
• النوع: غير استباقية. بمجرد أن تبدأ العملية، فإنها تستمر في التنفيذ حتى تكتمل أو تنتظر عملية I/O.
• المزايا: سهلة الفهم والتنفيذ.
• العيوب:
  • تأثير العربة (Convoy Effect): إذا كانت هناك عملية طويلة جدًا في بداية الطابور، فإنها ستجعل جميع العمليات القصيرة تنتظر وقتًا طويلاً جدًا، مما يزيد من متوسط وقت الانتظار.
  • غير مناسبة للأنظمة التفاعلية حيث وقت الاستجابة مهم.

📌 مثال توضيحي لـ FCFS:

لنفترض العمليات التالية:

العملية	وقت الوصول	وقت التنفيذ (Burst Time)
P1	0	8
P2	1	4
P3	2	2

مخطط جانت (Gantt Chart):

| P1 (8) | P2 (4) | P3 (2) |
0        8        12       14
                                

• وقت انتظار P1 = 0
• وقت انتظار P2 = 8 (P1 انتهت عند 8)
• وقت انتظار P3 = 12 (P2 انتهت عند 12)

متوسط وقت الانتظار = $(0 + 8 + 12) / 3 = 20 / 3 \approx 6.67$

لاحظ أن P3، وهي عملية قصيرة جدًا، اضطرت للانتظار 12 وحدة زمنية بسبب P1 و P2.

📍 ب. Shortest Job Next (SJN) / Shortest Job First (SJF) - أقصر مهمة تالية / أقصر مهمة أولاً

• الوصف: تُنفذ العملية ذات أقصر وقت تنفيذ (Burst Time) أولًا من بين العمليات الجاهزة.
• النوع: يمكن أن تكون غير استباقية (SJF) أو استباقية (SRTF).
• المزايا: تُعد مثالية من حيث تقليل متوسط وقت الانتظار.
• العيوب:
  • صعوبة التنفيذ العملي: تتطلب معرفة مسبقة بوقت التنفيذ الكلي لكل عملية، وهو أمر نادرًا ما يكون متاحًا في الأنظمة الحقيقية. يتم تقدير وقت التنفيذ عادةً بناءً على السلوك السابق.
  • قد تُسبب مجاعة (Starvation) للعمليات الطويلة إذا استمر وصول العمليات القصيرة.

🧠 نسخة استباقية: Shortest Remaining Time First (SRTF) - أقصر وقت متبقي أولاً

هي النسخة الاستباقية من SJF. في كل مرة تصل فيها عملية جديدة أو تنتهي عملية، يقوم Scheduler بفحص جميع العمليات الجاهزة (بما في ذلك العملية الجارية) ويختار العملية التي لديها أقصر وقت تنفيذ متبقي.

مثال لـ SRTF بنفس العمليات السابقة:

العملية	وقت الوصول	وقت التنفيذ
P1	0	8
P2	1	4
P3	2	2

مخطط جانت (Gantt Chart):

| P1 (1) | P2 (4) | P3 (2) | P1 (7) |
0        1        5        7        14
                                

• عند t=0: P1 تبدأ.
• عند t=1: P2 تصل (وقت P1 المتبقي = 7، وقت P2 = 4). P2 أقصر، لذا P1 تُقاطع وP2 تبدأ.
• عند t=2: P3 تصل (وقت P1 المتبقي = 7، وقت P2 المتبقي = 3، وقت P3 = 2). P3 أقصر، لذا P2 تُقاطع وP3 تبدأ.
• عند t=4: P3 تنتهي. (وقت P1 المتبقي = 7، وقت P2 المتبقي = 3). P2 أقصر، لذا P2 تستأنف.
• عند t=7: P2 تنتهي. (وقت P1 المتبقي = 7). P1 تستأنف.
• عند t=14: P1 تنتهي.

متوسط وقت الانتظار هنا سيكون أقل بكثير.

📍 ج. Priority Scheduling - الجدولة بالأولوية

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

🎯 حل مشكلة المجاعة: Aging (التقادم)

لحل مشكلة المجاعة، يتم استخدام تقنية "التقادم" (Aging)، حيث يتم رفع أولوية العملية تدريجيًا كلما انتظرت في قائمة الانتظار. هذا يضمن أن العمليات ذات الأولوية المنخفضة ستحصل في النهاية على فرصة للتنفيذ.

📍 د. Round Robin (RR) - الجولة الدائرية

• الوصف: هي خوارزمية جدولة استباقية مصممة خصيصًا للأنظمة الزمنية (Time-sharing Systems) حيث يكون وقت الاستجابة مهمًا. يتم تخصيص فترة زمنية ثابتة وصغيرة جدًا (تُسمى Quantum أو Time Slice) لكل عملية. يتم التبديل بين العمليات بالتناوب بعد انتهاء Quantum الخاص بها، أو إذا انتهت العملية قبل انتهاء Quantum.
• النوع: استباقية.
• المزايا:
  • وقت استجابة جيد: تضمن أن كل عملية تحصل على جزء من وقت المعالج بشكل منتظم، مما يعطي انطباعًا بأن جميع العمليات تعمل في نفس الوقت.
  • مناسبة للأنظمة التفاعلية.
  • تمنع المجاعة.
• العيوب:
  • قد تزيد من متوسط وقت الإنهاء (Turnaround Time) ووقت الانتظار مقارنة بـ SJF إذا كان Quantum كبيرًا جدًا.
  • اختيار حجم Quantum المناسب أمر حيوي:
    • إذا كان Quantum صغيرًا جدًا، يزداد الحمل الزائد (Overhead) بسبب كثرة تبديل السياق (Context Switching).
    • إذا كان Quantum كبيرًا جدًا، فإن RR تتحول إلى FCFS.

📘 مثال لـ Round Robin:

إذا كان لدينا 3 عمليات P1 (وقت تنفيذ 10)، P2 (وقت تنفيذ 4)، P3 (وقت تنفيذ 2)، و Quantum = 4.

| P1(4) | P2(4) | P3(2) | P1(4) | P1(2) |
0       4       8       10      14      16
                                

• P1 تُنفذ 4 وحدات زمنية.
• P2 تُنفذ 4 وحدات زمنية.
• P3 تُنفذ 2 وحدات زمنية (وتنتهي).
• P1 تُنفذ 4 وحدات زمنية أخرى.
• P1 تُنفذ آخر 2 وحدات زمنية (وتنتهي).

لاحظ كيف يتم التناوب بين العمليات لضمان حصول الجميع على وقت معالج.

📍 هـ. Multilevel Queue Scheduling - جدولة الطوابير متعددة المستويات

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

📍 و. Multilevel Feedback Queue - جدولة الطوابير متعددة المستويات مع التغذية الراجعة

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

3️⃣ معايير تقييم خوارزميات الجدولة

لتقييم مدى فعالية خوارزمية جدولة معينة، يستخدم مهندسو أنظمة التشغيل مجموعة من المعايير التي تساعد في تحديد الأداء العام للنظام وتجربة المستخدم.

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

4️⃣ الجدولة في نظام Unix التقليدي

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

آلية الجدولة في Unix التقليدي:

• الأولوية الديناميكية (Dynamic Priority):

  بدلاً من الأولوية الثابتة، يتم تعديل أولوية العملية أثناء التشغيل. هذا يسمح للنظام بالتكيف مع سلوك العمليات وتجنب المجاعة.

• قيمة "Niceness":

  كل عملية تملك قيمة "niceness" (عادةً تتراوح من -20 إلى +19). هذه القيمة يحددها المستخدم أو العملية نفسها. قيمة "niceness" الأعلى (أكثر إيجابية) تعني أولوية أقل (أي أن العملية "لطيفة" وتسمح للآخرين بالتشغيل). قيمة "niceness" الأقل (أكثر سلبية) تعني أولوية أعلى.

• تعديل الأولوية بناءً على استخدام المعالج:

  يقوم نظام Unix بتخفيض أولوية العملية تدريجيًا كلما استخدمت وقتًا أطول من المعالج (CPU). هذا يشجع العمليات التي تحتاج إلى I/O (I/O-bound processes) على الحصول على المعالج بشكل أسرع، ويمنع العمليات التي تستهلك المعالج بكثرة (CPU-bound processes) من احتكاره.

• التبديل السياقي (Context Switching):

  يحدث التبديل بين العمليات بشكل منتظم (عادةً كل 100 ميلي ثانية) لضمان الاستجابة الجيدة للأنظمة التفاعلية.

📘 قراءة موسعة: Unix Process Scheduling – Operating Systems: Principles and Practice (PDF)

5️⃣ أنشطة وتطبيقات مقترحة

لتعزيز فهمك لخوارزميات الجدولة وتأثيرها على أداء النظام، يُنصح بالقيام بالأنشطة والتطبيقات العملية التالية:

• رسم Gantt Chart لعمليات متعددة:

  اختر مجموعة من العمليات بأوقات وصول وأوقات تنفيذ مختلفة. قم برسم مخطط جانت (Gantt Chart) لكل من خوارزميات FCFS, SJF (غير استباقية واستباقية - SRTF), Priority (مع وبدون Aging), و Round Robin (بأحجام Quantum مختلفة). بعد الرسم، قم بحساب متوسط وقت الانتظار، وقت الاستجابة، ووقت الإنهاء لكل خوارزمية وقارن النتائج.

• استخدام محاكيات جدولة على الويب:

  هناك العديد من الأدوات التفاعلية المتاحة عبر الإنترنت التي تسمح لك بتجربة خوارزميات الجدولة المختلفة وتصور كيفية عملها. جرب الروابط التالية:

  • CPULator: CPU Scheduling Simulator
  • University of San Francisco: Scheduling Algorithm Visualization

  استخدم هذه المحاكيات لتغيير أوقات وصول العمليات، أوقات التنفيذ، الأولويات، وأحجام Quantum، ولاحظ كيف تتغير مقاييس الأداء.

• تحليل نتائج SJF مقابل RR:

  قم بتحليل متعمق للمفاضلة بين خوارزميتي SJF و Round Robin. متى تكون SJF أفضل؟ ومتى يكون Round Robin هو الخيار الأفضل؟ فكر في سيناريوهات مختلفة (مثل الأنظمة الدفعية مقابل الأنظمة التفاعلية) وحدد الخوارزمية الأكثر ملاءمة لكل سيناريو بناءً على معايير الأداء.