جدولة المعالج: تمارين ومحاكاة بلغة C#

قدمت المحاضرة خوارزميات الجدولة (scheduling algorithms) واحدة تلو الأخرى. أما في هذا الدرس فتكتسب السرعة والدقة في تطبيقها. نأخذ مجموعة واحدة من العمليات، ونجدولها بخوارزميات FCFS وSJF وSRTF والأولوية (بنوعيها) والتناوب الدائري (Round Robin)، ونرسم كل مخطط جانت (Gantt chart) قرارا بعد قرار، كما يفعل محاكي الجدولة. ثم يشغل برنامج قصير بلغة C# الخوارزميات الست نفسها ويطبع المخططات نفسها، فتستطيع التحقق من أي إجابة تحلها يدويا.

الأهداف

بنهاية هذا الدرس ينبغي أن تكون قادرا على:

• بناء مخطط جانت لخوارزميات FCFS وSJF وSRTF والأولوية، بنوعيها غير الاستباقي (non-preemptive) والاستباقي (preemptive)، والتناوب الدائري.
• حساب زمن الاكتمال (completion time, CT) وزمن الدوران (turnaround time, TAT) وزمن الانتظار (waiting time, WT) لكل عملية، ومتوسطاتها.
• تطبيق قواعد كسر التعادل (tie rules): تساوي أزمنة الوصول، وتساوي أزمنة التنفيذ، وتساوي الأولويات، وترتيب طابور التناوب الدائري.
• حساب كفاءة (efficiency) الجدولة عندما يكلف كل إسناد للمعالج (dispatch) وحدة واحدة من الكلفة الإضافية (overhead).
• شرح التجويع (starvation) والتقادم (aging)، ووصف جدولة الطوابير متعددة المستويات (multilevel queue) وجدولة الطوابير متعددة المستويات بالتغذية الراجعة (multilevel feedback queue).
• قراءة برنامج بلغة C# يحاكي هذه الخوارزميات، وتشغيله، والتوسع فيه.

الجزء 1: الأدوات الأساسية

قراءة مخطط جانت

يبين مخطط جانت أي عملية (process) تشغل المعالج (CPU) في كل لحظة. هذا مثال FCFS من المحاضرة: تصل P3 عند 0، وP1 عند 4، وP5 عند 5، وتصل P2 وP4 كلتاهما عند 6.

| P3 | idle |   P1  |  P5 |  P2 | P4 |
0    3      4       9     13    17   19

• كل خانة هي عملية واحدة تشغل المعالج. والأرقام تحت الحدود هي أزمنة الساعة.
• خانة الخمول (idle) من 3 إلى 4 تعني أنه لا توجد عملية جاهزة: فقد انتهت P3 ولم تصل P1 بعد، لذا ينتظر المعالج.
• زمن الاكتمال (CT) لعملية ما هو الحافة اليمنى لآخر خانة لها: تكتمل P1 عند 9، وP4 عند 19.

كل سؤال في هذا الدرس يحل بالطريقة نفسها: ارسم المخطط أولا، ثم اقرأ منه كل الأرقام.

ثلاث صيغ واختصار

TAT = CT - AT
WT  = TAT - BT
ΣTAT / n    ΣWT / n

زمن الدوران (TAT) هو كل الزمن من الوصول إلى الانتهاء، وزمن الانتظار (WT) هو الجزء من TAT الذي لا تقضيه العملية في التنفيذ. والمتوسط هو مجموع العمود (ΣTAT أو ΣWT) مقسوما على عدد العمليات n.

عندما ينتزع المعالج من عملية (preemption) فإنها تظهر في عدة خانات. وعندئذ تستطيع قراءة زمن انتظارها من المخطط مباشرة:

WT = S - R - AT
WT = S - AT - k x q

في هاتين الصيغتين S بداية آخر خانة للعملية، وR الزمن الذي عملته قبل تلك الخانة. والسطر الثاني هو صورة التناوب الدائري: كل خانة سابقة شريحة زمنية كاملة، لذا R = k x q، حيث k عدد مرات انتزاع المعالج من العملية. وتعطي الصيغتان زمن الانتظار نفسه تماما الذي تعطيه TAT - BT. استخدم إحداهما للحساب والأخرى للتحقق من نفسك.

قواعد كسر التعادل

• تساوي زمن الوصول (arrival time, AT): تبدأ العملية ذات المعرف (ID) الأصغر.
• تساوي زمن التنفيذ (burst time, BT) أو تساوي الأولوية: نرجع إلى FCFS، فتبدأ العملية الأسبق وصولا.
• أرقام الأولوية: اقرأ السؤال. تستخدم أمثلة المحاضرة الاصطلاحين كليهما: أحيانا يكون الرقم الأصغر هو الأولوية الأعلى (0 هو الأفضل)، وأحيانا يكون الرقم الأكبر هو الأعلى.
• الخوارزميات الاستباقية: لا تأخذ العملية الجديدة المعالج إلا إذا كانت أفضل تماما. وعند التعادل تحتفظ العملية الجارية بالمعالج (قاعدة FCFS للتعادل). ولا تحتوي أي مسألة في هذا الدرس على تعادل من هذا النوع.
• التناوب الدائري: إذا وصلت عملية في اللحظة نفسها التي تنتهي فيها الشريحة الزمنية (time quantum) لعملية أخرى، تدخل العملية الجديدة طابور الجاهزية (ready queue) أولا، وتقف العملية التي انتزع منها المعالج خلفها.

المجموعة A: مدخل واحد لكل الخوارزميات

تستخدم كل الأمثلة المحلولة العمليات الخمس نفسها، لتتمكن من مقارنة الخوارزميات مباشرة. الأزمنة بالمللي ثانية (ms)، والرقم الأصغر هنا يعني أولوية أعلى.

مجموع أزمنة التنفيذ 24، ولا تترك أي خوارزمية المعالج خاملا مع هذا المدخل، لذا ينتهي كل مخطط عند 24.

الجزء 2: FCFS وSJF

كلتا الخوارزميتين غير استباقية: متى حصلت العملية على المعالج احتفظت به حتى تنتهي. ولا يتخذ المجدول (scheduler) قرارا إلا عندما يتحرر المعالج.

FCFS وتأثير القافلة

تخدم خوارزمية الأسبق وصولا أولا (first-come, first-served) العمليات بترتيب وصولها، باستخدام طابور جاهزية من نوع FIFO. إنها بسيطة، لكن متوسط زمن الانتظار فيها يعتمد كثيرا على الترتيب. خذ ثلاث عمليات تصل عند الزمن 0 بأزمنة تنفيذ 18 و3 و3:

العمل متطابق، ومع ذلك ينتظر الترتيب الأول أكثر من أربعة أضعاف الترتيب الثاني: فالعمليات القصيرة عالقة خلف العملية الطويلة. هذا هو تأثير القافلة (convoy effect).

مثال محلول: FCFS على المجموعة A

نخدم بحسب الوصول تماما: P1 عند 0، وP2 عند 2، وP3 عند 3، وP4 عند 4، وP5 عند 6. وصلت كل عملية قبل أن يتحرر المعالج، لذا لا يوجد زمن خمول.

|     P1    | P2 |  P3 | P4 |    P5   |
0           8    11    15   17        24

متوسط TAT = 60 / 5 = 12. متوسط WT = 36 / 5 = 7.2.

مثال محلول: الكفاءة مع وحدة واحدة من الكلفة الإضافية

تضيف مسألة FCFS الثانية في المحاضرة كلفة للجدولة: قبل إعطاء المعالج لأي عملية، يقضي النظام وحدة زمنية واحدة (يرمز لها del). الفكرة نفسها على المجموعة A:

| del |   P1   | del | P2 | del | P3 | del | P4 | del |   P5  |
0     1        9     10   13    14   18    19   21    22      29

• الزمن الكلي T: تنتهي آخر عملية عند 29.
• الزمن الضائع D: 5 تأخيرات طول كل منها 1 = 5.
• الزمن المفيد T - D: 29 - 5 = 24، وهو مجموع أزمنة التنفيذ بالضبط.

والكفاءة η هي نسبة الزمن المفيد من الزمن الكلي:

η = (T - D) / T = 24 / 29 = 0.8276 = 82.76%

مثال محلول: SJF (غير الاستباقية) على المجموعة A

تعطي خوارزمية أقصر مهمة أولا (shortest job first) المعالج المتحرر للعملية المنتظرة صاحبة أقصر زمن تنفيذ تال على المعالج؛ وعند التعادل تبدأ العملية الأسبق وصولا. عند الزمن 0 لا توجد إلا P1، فتعمل من 0 إلى 8، ولأن SJF هنا غير استباقية لا تستطيع أي عملية انتزاع المعالج منها. وعند 8 تكون العمليات الأخرى كلها منتظرة:

|     P1    | P4 | P2 |  P3 |    P5   |
0           8    10   13    17        24

متوسط TAT = 57 / 5 = 11.4. متوسط WT = 33 / 5 = 6.6.

وصلت P4 آخر العمليات الأربع لكنها تعمل أولا: تنظر SJF إلى زمن التنفيذ لا إلى زمن الوصول. وينخفض متوسط WT من 7.2 (FCFS) إلى 6.6.

الجزء 3: SRTF، أي SJF الاستباقية

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

مثال محلول: SRTF على المجموعة A

الفخ عند الزمن 4: تحتاج P4 إلى 2 فقط، وهو أقل من زمن التنفيذ الكامل لـP2 وهو 3، لكن المتبقي من P2 هو 1 فقط. قارن دائما بالزمن المتبقي.

| P1 | P2 | P4 |  P3 |   P1   |    P5   |
0    2    5    7     11       17        24

أزمنة الانتظار بالاختصار (آخر بداية - الزمن المنفذ قبلها - AT):

متوسط TAT = 49 / 5 = 9.8. متوسط WT = 25 / 5 = 5.

تعطي SRTF أصغر متوسط لزمن الانتظار بين الخوارزميات الست على المجموعة A (5، مقابل 6.6 لـSJF غير الاستباقية). لكن المشكلة، كما تشرح المحاضرة، أن نظام التشغيل لا يستطيع معرفة طول زمن التنفيذ التالي على المعالج. كل ما يستطيعه هو التنبؤ به، بافتراض أن زمن التنفيذ التالي سيكون قريبا في طوله من الأزمنة السابقة، ثم الجدولة بحسب القيمة المتنبأ بها.

الجزء 4: جدولة الأولوية

لكل عملية أولوية (priority)، ويذهب المعالج إلى العملية الجاهزة ذات الأولوية الأعلى؛ والأولويات المتساوية تخدم بطريقة FCFS. في الأولوية غير الاستباقية توضع العملية الجديدة الأفضل على رأس طابور الجاهزية، وتنتظر هناك حتى تنتهي العملية الجارية. وفي الأولوية الاستباقية تأخذ العملية الجديدة الأفضل المعالج فورا. وSJF نفسها خوارزمية أولوية، أولويتها هي زمن التنفيذ التالي (المتنبأ به) على المعالج: كلما طال زمن التنفيذ انخفضت الأولوية.

في المجموعة A الرقم الأصغر هو الأولوية الأعلى: 1 هو الأفضل و5 هو الأسوأ.

مثال محلول: الأولوية غير الاستباقية على المجموعة A

تبدأ P1 (الأولوية 4) عند 0 وتعمل حتى 8. وتصل في أثناء ذلك P3 (الأولوية 2) وP4 (الأولوية 1) وهما أفضل منها، لكن عليهما الانتظار: فالخوارزمية غير استباقية. وعند 8 تعمل العمليات المنتظرة بترتيب أولوياتها: P4 (1)، ثم P3 (2)، ثم P5 (3)، ثم P2 (5).

|     P1    | P4 |  P3 |    P5   | P2 |
0           8    10    14        21   24

متوسط TAT = 62 / 5 = 12.4. متوسط WT = 38 / 5 = 7.6.

مثال محلول: الأولوية الاستباقية على المجموعة A

| P1 | P3 | P4 | P3 |    P5   |   P1  | P2 |
0    3    4    6    9         16      21   24

متوسط TAT = 61 / 5 = 12.2. متوسط WT = 37 / 5 = 7.4.

التجويع والتقادم

لـP2 أسوأ أولوية، وهي تنتظر 19 وحدة من أصل 24 في مخططي الأولوية كليهما. ومع تدفق مستمر من العمليات الأعلى أولوية قد تنتظر إلى الأبد. والعملية الجاهزة التي لا تحصل على المعالج أبدا تكون محجوبة (blocked)، وتسمى هذه المشكلة الحجب غير المحدود (indefinite blocking) أو التجويع.

والحل هو التقادم: رفع أولوية العملية تدريجيا كلما طال انتظارها. في مثال المحاضرة تمتد الأولويات من 127 (الأدنى) إلى 0 (الأعلى)، وترتفع العملية المنتظرة درجة واحدة كل 15 دقيقة، لذا تصل إلى القمة في النهاية حتى العملية التي تبدأ عند 127:

127 x 15 = 1905
1905 / 60 = 31.75

أي 1905 من الدقائق، أو 31.75 ساعة.

الجزء 5: التناوب الدائري

صمم التناوب الدائري لأنظمة المشاركة الزمنية (time-sharing). وهو FCFS مع إضافة الانتزاع عن طريق شريحة زمنية (تذكر المحاضرة قيما من 10 إلى 100 ms في الأنظمة الحقيقية):

1. طابور الجاهزية طابور من نوع FIFO؛ وتنضم العمليات الجديدة إلى ذيله.
2. تحصل العملية التي على رأس الطابور على المعالج مدة شريحة زمنية واحدة على الأكثر.
3. إذا احتاجت إلى أقل من شريحة، تنتهي وتحرر المعالج طوعا.
4. إذا انتهت الشريحة، تحدث مقاطعة المؤقت (timer interrupt)، ويحفظ تبديل السياق (context switch) حالة العملية، وتذهب إلى ذيل الطابور.
5. إذا وصلت عملية في اللحظة نفسها التي تنتهي فيها شريحة، تدخل العملية الجديدة الطابور أولا، وتقف العملية التي انتزع منها المعالج خلفها.

مثال محلول: التناوب الدائري على المجموعة A، q = 3

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

اللحظات التي تستحق نظرة أدق:

• t = 3: تصل P3 تماما عند انتهاء شريحة P1. تدخل P3 الطابور أولا ثم P1، فيكون الطابور P3، P1 بينما تعمل P2.
• t = 6: احتاجت P2 إلى 3 فقط، فانتهت داخل شريحتها وحررت المعالج.
• t = 20: P5 وحدها. تنتهي شريحتها عند 23، فتذهب إلى الطابور (الفارغ) ويعود إليها المعالج فورا، ولهذا يظهر في المخطط خانتان لـP5.

| P1 | P2 | P3 | P1 | P4 | P5 | P3 | P1 | P5 | P5 |
0    3    6    9    12   14   17   18   20   23   24

متوسط TAT = 67 / 5 = 13.4. متوسط WT = 43 / 5 = 8.6.

تحقق باختصار التناوب الدائري، WT = آخر بداية - AT - عدد مرات الانتزاع x q:

قاعدة التعادل مهمة: لو أعيدت P1 إلى الطابور قبل P3 عند الزمن 3، لصار متوسط WT يساوي 8.8 بدلا من 8.6.

اختيار الشريحة الزمنية

المجموعة A نفسها مع شرائح زمنية مختلفة. وتبديل العملية (process switch) هنا هو حد في المخطط تسلم عنده عملية المعالج إلى عملية أخرى.

• كبيرة جدا: مع q = 8 لا ينتزع المعالج من أي عملية أبدا، ويرسم التناوب الدائري مخطط FCFS نفسه تماما (4 تبديلات).
• صغيرة جدا: مع q = 1 يبدل المعالج العمليات 20 مرة؛ وكل تبديل هو تبديل سياق، يكلف وقتا في النظام الحقيقي.
• يجب أن تحقق الشريحة الزمنية توازنا بين الحالتين.

تفاعلي: ابن المخطط وحدة زمنية بعد وحدة

اختر خوارزمية، وعدل جدول العمليات، واضغط زر التشغيل: ينمو مخطط جانت وحدة زمنية واحدة في كل مرة، مع طابور الجاهزية، وسبب كل قرار، وقيم CT وTAT وWT لكل عملية عند انتهائها.

افتح أداة مخطط جانت بملء الشاشة

الجزء 6: مقارنة خوارزميات الجدولة الست

لـSRTF أصغر متوسط لزمن الانتظار. وللتناوب الدائري أكبر متوسط هنا؛ أما قوته فهي زمن الاستجابة (response time)، إذ تحصل كل عملية منتظرة على دور مرة في كل دورة للطابور.

تشغل الأداة التفاعلية (widget) الثانية الخوارزميات الست على المدخل نفسه بساعة مشتركة واحدة. غير الشريحة الزمنية، أو بدل قاعدة الأولوية، أو اسحب مجموعة عشوائية، وراقب تغير المتوسطات.

افتح أداة المقارنة بملء الشاشة

الجزء 7: الطوابير متعددة المستويات

جدولة الطوابير متعددة المستويات

عندما تنقسم العمليات إلى مجموعات واضحة، يمكن تقسيم طابور الجاهزية إلى عدة طوابير. وتخصص كل عملية بشكل دائم لطابور واحد، بناء على خاصية مثل نوعها أو أولويتها أو حجم ذاكرتها. ولكل طابور خوارزميته الخاصة: مثلا التناوب الدائري لطابور الواجهة (foreground) التفاعلي، وFCFS لطابور الخلفية (background). وهناك أيضا جدولة بين الطوابير، وعادة تكون جدولة استباقية بأولوية ثابتة (fixed-priority preemptive): لا يعمل طابور إلا عندما تكون كل الطوابير التي فوقه فارغة، والوصول إلى طابور أعلى ينتزع المعالج من عملية في طابور أدنى. وفي مثال المحاضرة خمسة طوابير، من الأعلى أولوية إلى الأدنى:

1. عمليات النظام
2. العمليات التفاعلية
3. عمليات التحرير التفاعلي
4. العمليات الدفعية (batch)
5. عمليات الطلاب

لا تعمل عملية الطالب إلا عندما تكون الطوابير الأربعة التي فوقها كلها فارغة.

جدولة الطوابير متعددة المستويات بالتغذية الراجعة

تسمح النسخة ذات التغذية الراجعة للعمليات بالانتقال بين الطوابير. فالعملية التي تستخدم وقتا كثيرا من المعالج تنتقل إلى أسفل، والعملية التي تنتظر طويلا في طابور منخفض تنتقل إلى أعلى، وهذا شكل من أشكال التقادم يمنع التجويع. في مثال المحاضرة يعطي Q0 شريحة زمنية 8 ms، ويعطي Q1 شريحة زمنية 16 ms، ويعمل Q2 بطريقة FCFS؛ ولا يعمل طابور أدنى إلا عندما تكون الطوابير التي فوقه فارغة.

new process -> Q0 (quantum 8) --not done in 8--> Q1 (quantum 16) --not done in 16--> Q2 (FCFS)

العملية التي زمن تنفيذها 30 ms تعمل 8 ms في Q0، و16 ms في Q1، وآخر 6 ms في Q2. وتعرف جدولة الطوابير متعددة المستويات بالتغذية الراجعة بخمسة معاملات: عدد الطوابير، وخوارزمية كل طابور، وطريقة تحديد وقت ترقية العملية، وطريقة تحديد وقت خفضها، وطريقة تحديد الطابور الذي تدخله العملية عندما تحتاج إلى الخدمة.

فحص سريع

هذه أسئلة بأسلوب الامتحان حلت في فيديو مسائل المحاضرة. جربها قبل قراءة الإجابات في النهاية.

1. مجموعة من n مهمة ذات أزمنة تشغيل معروفة تعمل على معالج واحد. أي خوارزمية تعطي أقصى إنتاجية (throughput): التناوب الدائري، أم SJF، أم أعلى نسبة استجابة أولا (highest response ratio next)، أم FCFS؟
2. أي مما يلي غير استباقي: التناوب الدائري، أم FIFO، أم الطوابير متعددة المستويات، أم الطوابير متعددة المستويات بالتغذية الراجعة؟
3. صواب أم خطأ: قد تسبب SRTF التجويع؛ قد تسبب الجدولة الاستباقية التجويع؛ التناوب الدائري أفضل من FCFS في زمن الاستجابة.
4. خوارزمية تجعل الأولوية متناسبة مع زمن الانتظار، وتبدأ كل عملية بالأولوية 0، ويعاد تقييم الأولويات كل T وحدة زمنية. تصل العمليات كلها عند 0 ولا تنفذ أي إدخال وإخراج (I/O). ما الخوارزمية المكافئة لها؟

الجزء 8: محاكاة بلغة C#

يجدول البرنامج أدناه المجموعة A بالخوارزميات الست كلها، ويطبع كل مخطط جانت مع جدوله ومتوسطاته. أنشئ مشروع تطبيق طرفية (console): في Visual Studio أنشئ مشروع Console App جديدا، أو في الطرفية نفذ dotnet new console -n CpuScheduling. ثم ضع الشيفرة الموجودة في نهاية هذا الجزء مكان محتوى Program.cs، وشغل البرنامج.

البيانات

public class Process
{
    public string Id { get; }
    public int Arrival { get; }
    public int Burst { get; }
    public int Priority { get; }
    public int Remaining { get; set; }   // burst still to run
    public int Completion { get; set; }  // CT, set when Remaining reaches 0
    // constructor sets Remaining = burst
}
 
public record Slice(string Id, int Start, int End);

• Id وArrival وBurst وPriority هي المدخلات من السؤال، ولا تتغير أبدا.
• Remaining تنقص بمقدار 1 مع كل وحدة زمنية تعمل فيها العملية، وتعتمد SRTF عليها في ترتيب العمليات.
• Completion هي CT، وتضبط عندما تصل Remaining إلى 0. ويحسب منها TAT وWT بالصيغتين المعتادتين.
• Slice هي خانة واحدة في مخطط جانت.

محرك واحد لـFCFS وSJF وSRTF والأولوية

while (done < ps.Count)
{
    var ready = ps.Where(p => p.Arrival <= time && p.Remaining > 0 && p != running)
                  .OrderBy(rank).ThenBy(p => p.Arrival).ThenBy(p => p.Id).ToList();
    if (running == null)
        running = ready.FirstOrDefault();            // CPU free: take the best
    else if (preemptive && ready.Count > 0 && rank(ready[0]) < rank(running))
        running = ready[0];                          // strictly better: preempt
    AddTick(gantt, running?.Id ?? "idle", time, false);
    if (running != null && --running.Remaining == 0)
    {
        running.Completion = time + 1; running = null; done++;
    }
    time++;
}

• الساعة time تتقدم وحدة واحدة في كل دورة من الحلقة، تماما كالتقدم خطوة خطوة في المخطط.
• تحوي ready كل عملية وصلت ولم تنته وليست جارية، مرتبة بحسب rank، ثم بحسب الوصول، ثم بحسب المعرف: هذه هي قواعد كسر التعادل.
• rank هي الشيء الوحيد الذي يتغير بين الخوارزميات: p => p.Arrival لـFCFS، وp => p.Burst لـSJF، وp => p.Remaining لـSRTF، وp => p.Priority للأولوية (الأصغر أفضل).
• عندما يكون المعالج متحررا تحصل عليه أفضل عملية جاهزة. وإذا كانت preemptive تساوي true، فإن العملية الجاهزة الأفضل تماما تأخذ المعالج أيضا من العملية الجارية.
• AddTick تمد الخانة الأخيرة وحدة واحدة أو تبدأ خانة جديدة.

التناوب الدائري يحتاج إلى طابور حقيقي

foreach (var p in ps.Where(p => p.Arrival == time).OrderBy(p => p.Id))
    queue.Enqueue(p);                            // 1. new arrivals join first
if (running != null && used == quantum)
{
    queue.Enqueue(running);                      // 2. then the preempted process
    running = null;
}
bool dispatched = false;
if (running == null && queue.Count > 0)
{
    running = queue.Dequeue();                   // 3. the head gets the CPU
    used = 0;
    dispatched = true;
}

ترتيب الخطوتين 1 و2 هو قاعدة كسر التعادل: العمليات الواصلة في هذه اللحظة تدخل الطابور قبل العملية التي انتهت شريحتها للتو. وإذا بدلت الكتلتين أنتج البرنامج الإجابة الخاطئة المذكورة في الجزء 5.

تشغيل البرنامج

var ps = SetA();
Report.Print("FCFS", ps, Scheduler.Run(ps, p => p.Arrival, false));
ps = SetA();
Report.Print("SJF (non-preemptive)", ps, Scheduler.Run(ps, p => p.Burst, false));
ps = SetA();
Report.Print("SRTF (preemptive SJF)", ps, Scheduler.Run(ps, p => p.Remaining, true));
ps = SetA();
Report.Print("Priority (non-preemptive)", ps, Scheduler.Run(ps, p => p.Priority, false));
ps = SetA();
Report.Print("Priority (preemptive)", ps, Scheduler.Run(ps, p => p.Priority, true));
ps = SetA();
Report.Print("Round Robin q=3", ps, Scheduler.RoundRobin(ps, 3));

تبني SetA() قائمة جديدة في كل تشغيل، لأن التشغيل يغير Remaining وCompletion: وإعادة استخدام القائمة تجعل الخوارزمية التالية تبدأ بعمليات منتهية. المخرجات:

=== FCFS
P1 0-8 | P2 8-11 | P3 11-15 | P4 15-17 | P5 17-24
P1  AT= 0  BT= 8  CT= 8  TAT= 8  WT= 0
P2  AT= 2  BT= 3  CT=11  TAT= 9  WT= 6
P3  AT= 3  BT= 4  CT=15  TAT=12  WT= 8
P4  AT= 4  BT= 2  CT=17  TAT=13  WT=11
P5  AT= 6  BT= 7  CT=24  TAT=18  WT=11
Average WT = 7.20   Average TAT = 12.00
 
=== SJF (non-preemptive)
P1 0-8 | P4 8-10 | P2 10-13 | P3 13-17 | P5 17-24
P1  AT= 0  BT= 8  CT= 8  TAT= 8  WT= 0
P2  AT= 2  BT= 3  CT=13  TAT=11  WT= 8
P3  AT= 3  BT= 4  CT=17  TAT=14  WT=10
P4  AT= 4  BT= 2  CT=10  TAT= 6  WT= 4
P5  AT= 6  BT= 7  CT=24  TAT=18  WT=11
Average WT = 6.60   Average TAT = 11.40
 
=== SRTF (preemptive SJF)
P1 0-2 | P2 2-5 | P4 5-7 | P3 7-11 | P1 11-17 | P5 17-24
P1  AT= 0  BT= 8  CT=17  TAT=17  WT= 9
P2  AT= 2  BT= 3  CT= 5  TAT= 3  WT= 0
P3  AT= 3  BT= 4  CT=11  TAT= 8  WT= 4
P4  AT= 4  BT= 2  CT= 7  TAT= 3  WT= 1
P5  AT= 6  BT= 7  CT=24  TAT=18  WT=11
Average WT = 5.00   Average TAT = 9.80
 
=== Priority (non-preemptive)
P1 0-8 | P4 8-10 | P3 10-14 | P5 14-21 | P2 21-24
P1  AT= 0  BT= 8  CT= 8  TAT= 8  WT= 0
P2  AT= 2  BT= 3  CT=24  TAT=22  WT=19
P3  AT= 3  BT= 4  CT=14  TAT=11  WT= 7
P4  AT= 4  BT= 2  CT=10  TAT= 6  WT= 4
P5  AT= 6  BT= 7  CT=21  TAT=15  WT= 8
Average WT = 7.60   Average TAT = 12.40
 
=== Priority (preemptive)
P1 0-3 | P3 3-4 | P4 4-6 | P3 6-9 | P5 9-16 | P1 16-21 | P2 21-24
P1  AT= 0  BT= 8  CT=21  TAT=21  WT=13
P2  AT= 2  BT= 3  CT=24  TAT=22  WT=19
P3  AT= 3  BT= 4  CT= 9  TAT= 6  WT= 2
P4  AT= 4  BT= 2  CT= 6  TAT= 2  WT= 0
P5  AT= 6  BT= 7  CT=16  TAT=10  WT= 3
Average WT = 7.40   Average TAT = 12.20
 
=== Round Robin q=3
P1 0-3 | P2 3-6 | P3 6-9 | P1 9-12 | P4 12-14 | P5 14-17 | P3 17-18 | P1 18-20 | P5 20-23 | P5 23-24
P1  AT= 0  BT= 8  CT=20  TAT=20  WT=12
P2  AT= 2  BT= 3  CT= 6  TAT= 4  WT= 1
P3  AT= 3  BT= 4  CT=18  TAT=15  WT=11
P4  AT= 4  BT= 2  CT=14  TAT=10  WT= 8
P5  AT= 6  BT= 7  CT=24  TAT=18  WT=11
Average WT = 8.60   Average TAT = 13.40

كل مخطط وكل متوسط يطابق الحلول اليدوية أعلاه.

البرنامج كاملا

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace CpuScheduling
{
    // One process: what the scheduler knows about it, plus two fields it fills in.
    public class Process
    {
        public string Id { get; }
        public int Arrival { get; }
        public int Burst { get; }
        public int Priority { get; }
        public int Remaining { get; set; }   // burst still to run
        public int Completion { get; set; }  // CT, set when Remaining reaches 0
 
        public Process(string id, int arrival, int burst, int priority = 0)
        {
            Id = id;
            Arrival = arrival;
            Burst = burst;
            Priority = priority;
            Remaining = burst;
        }
    }
 
    // One bar of the Gantt chart.
    public record Slice(string Id, int Start, int End);
 
    public static class Scheduler
    {
        // FCFS, SJF, SRTF and Priority share one engine. The clock moves one unit
        // at a time; "rank" says which ready process is best (smaller is better).
        public static List<Slice> Run(List<Process> ps, Func<Process, int> rank, bool preemptive)
        {
            var gantt = new List<Slice>();
            Process? running = null;
            int time = 0, done = 0;
 
            while (done < ps.Count)
            {
                var ready = ps.Where(p => p.Arrival <= time && p.Remaining > 0 && p != running)
                              .OrderBy(rank).ThenBy(p => p.Arrival).ThenBy(p => p.Id).ToList();
                if (running == null)
                    running = ready.FirstOrDefault();            // CPU free: take the best
                else if (preemptive && ready.Count > 0 && rank(ready[0]) < rank(running))
                    running = ready[0];                          // strictly better: preempt
                AddTick(gantt, running?.Id ?? "idle", time, false);
                if (running != null && --running.Remaining == 0)
                {
                    running.Completion = time + 1; running = null; done++;
                }
                time++;
            }
            return gantt;
        }
 
        // Round Robin: a FIFO ready queue and a time quantum.
        public static List<Slice> RoundRobin(List<Process> ps, int quantum)
        {
            var gantt = new List<Slice>();
            var queue = new Queue<Process>();
            Process? running = null;
            int time = 0, used = 0, done = 0;
 
            while (done < ps.Count)
            {
                foreach (var p in ps.Where(p => p.Arrival == time).OrderBy(p => p.Id))
                    queue.Enqueue(p);                            // 1. new arrivals join first
                if (running != null && used == quantum)
                {
                    queue.Enqueue(running);                      // 2. then the preempted process
                    running = null;
                }
                bool dispatched = false;
                if (running == null && queue.Count > 0)
                {
                    running = queue.Dequeue();                   // 3. the head gets the CPU
                    used = 0;
                    dispatched = true;
                }
 
                AddTick(gantt, running?.Id ?? "idle", time, dispatched);
                if (running != null)
                {
                    used++;
                    if (--running.Remaining == 0)
                    {
                        running.Completion = time + 1;
                        running = null;
                        done++;
                    }
                }
                time++;
            }
            return gantt;
        }
 
        // Extend the last bar by one unit, or start a new bar.
        static void AddTick(List<Slice> gantt, string id, int time, bool newDispatch)
        {
            if (!newDispatch && gantt.Count > 0 && gantt[^1].Id == id && gantt[^1].End == time)
                gantt[^1] = gantt[^1] with { End = time + 1 };
            else
                gantt.Add(new Slice(id, time, time + 1));
        }
    }
 
    public static class Report
    {
        public static void Print(string title, List<Process> ps, List<Slice> gantt)
        {
            Console.WriteLine($"=== {title}");
            Console.WriteLine(string.Join(" | ", gantt.Select(s => $"{s.Id} {s.Start}-{s.End}")));
 
            double sumTat = 0, sumWt = 0;
            foreach (var p in ps.OrderBy(p => p.Id))
            {
                int tat = p.Completion - p.Arrival;   // TAT = CT - AT
                int wt = tat - p.Burst;               // WT  = TAT - BT
                sumTat += tat;
                sumWt += wt;
                Console.WriteLine($"{p.Id}  AT={p.Arrival,2}  BT={p.Burst,2}  CT={p.Completion,2}  TAT={tat,2}  WT={wt,2}");
            }
            Console.WriteLine($"Average WT = {sumWt / ps.Count:0.00}   Average TAT = {sumTat / ps.Count:0.00}");
            Console.WriteLine();
        }
    }
 
    public static class Program
    {
        // Set A from the lesson. Lower priority number = higher priority.
        // A new list every call: each run changes Remaining and Completion.
        static List<Process> SetA() => new()
        {
            new("P1", 0, 8, 4),
            new("P2", 2, 3, 5),
            new("P3", 3, 4, 2),
            new("P4", 4, 2, 1),
            new("P5", 6, 7, 3),
        };
 
        public static void Main()
        {
            var ps = SetA();
            Report.Print("FCFS", ps, Scheduler.Run(ps, p => p.Arrival, false));
            ps = SetA();
            Report.Print("SJF (non-preemptive)", ps, Scheduler.Run(ps, p => p.Burst, false));
            ps = SetA();
            Report.Print("SRTF (preemptive SJF)", ps, Scheduler.Run(ps, p => p.Remaining, true));
            ps = SetA();
            Report.Print("Priority (non-preemptive)", ps, Scheduler.Run(ps, p => p.Priority, false));
            ps = SetA();
            Report.Print("Priority (preemptive)", ps, Scheduler.Run(ps, p => p.Priority, true));
            ps = SetA();
            Report.Print("Round Robin q=3", ps, Scheduler.RoundRobin(ps, 3));
        }
    }
}

تمارين

نحو 30 دقيقة. حل كل مسألة على الورق أولا: ارسم المخطط، واملأ الجدول، ثم احسب المتوسطات. تحقق من نفسك بأداة مخطط جانت أو بوضع البيانات في SetA() في برنامج C#. الإجابات في النهاية.

التمرين 1: FCFS مع معالج خامل

ارسم مخطط FCFS (وحدد أي زمن خمول)، وأوجد CT وTAT وWT لكل عملية، ومتوسط TAT ومتوسط WT. لاحظ أن P3 وP4 تصلان معا.

التمرين 2: SRTF

طبق SJF الاستباقية (SRTF) على هذه العمليات. وأوجد متوسط WT ومتوسط TAT. ثم طبق SJF غير الاستباقية على العمليات نفسها وقارن.

التمرين 3: الأولوية الاستباقية، الرقم الأكبر أولوية أعلى

في هذه المسألة الرقم الأكبر يعني أولوية أعلى (5 هو الأفضل). ارسم مخطط الأولوية الاستباقية، وأوجد متوسط WT ومتوسط TAT.

التمرين 4: التناوب الدائري مع ست عمليات، q = 2

ارسم المخطط مع تتبع طابور الجاهزية، وأوجد متوسط WT ومتوسط TAT. انتبه لما يحدث عند t = 7.

التمرين 5 (اختياري، C#)

أضف إلى البرنامج دالة SetPractice4() ببيانات التمرين 4، وشغل عليها Scheduler.RoundRobin بشريحة زمنية 2، وتأكد من إجابتك. ثم بدل الكتلتين المرقمتين 1 و2 في RoundRobin وشغله مرة أخرى: زمن انتظار أي عملية يتغير، ولماذا؟

الإجابات

التمرين 1

| P2 |  P1 | P3 | P4 | idle | P5 |
0    2     6    9    10     13   15

متوسط TAT = 22 / 5 = 4.4. متوسط WT = 10 / 5 = 2.

تصل P3 وP4 كلتاهما عند 3، فتبدأ P3 (المعرف الأصغر). ويكون المعالج خاملا من 10 إلى 13 في انتظار P5.

التمرين 2

| P1 | P2 | P1 | P4 | P1 |   P3  |
0    2    4    7    8    11      16

متوسط TAT = 24 / 4 = 6. متوسط WT = 8 / 4 = 2.

عند 6 تحتاج P3 إلى 5 بينما المتبقي من P1 هو 4 فقط، لذا تحتفظ P1 بالمعالج. ومع SJF غير الاستباقية:

|     P1    | P4 | P2 |   P3  |
0           8    9    11      16

متوسط TAT = 29 / 4 = 7.25. متوسط WT = 13 / 4 = 3.25.

يخفض الانتزاع متوسط WT هنا لأن العمليتين القصيرتين P2 وP4 لم تعودا تنتظران خلف P1.

التمرين 3

| P1 | P2 | P1 | P5 | P1 | P3 |  P4 |
0    2    4    7    10   11   14    18

متوسط TAT = 41 / 5 = 8.2. متوسط WT = 23 / 5 = 4.6.

إذا قرأت الأولويات بالعكس (الرقم الأصغر = أولوية أعلى) حصلت على مخطط مختلف ومتوسط WT يساوي 6.2: تحقق دائما من الاصطلاح أولا.

التمرين 4

| P1 | P2 | P1 | P3 | P4 | P5 | P3 | P6 | P4 | P5 | P3 |
0    2    4    5    7    9    11   13   15   16   18   19

متوسط TAT = 51 / 6 = 8.5. متوسط WT = 32 / 6 = 5.33.

عند t = 7 تصل P5 تماما عند انتهاء شريحة P3، فتدخل P5 الطابور قبل P3.

التمرين 5

static List<Process> SetPractice4() => new()
{
    new("P1", 0, 3), new("P2", 1, 2), new("P3", 4, 5),
    new("P4", 6, 3), new("P5", 7, 4), new("P6", 8, 2),
};

استدعها في Main هكذا: var ps = SetPractice4(); Report.Print("Practice 4, q=2", ps, Scheduler.RoundRobin(ps, 2));.

مع الترتيب الصحيح يطبع البرنامج متوسط WT يساوي 5.33 ومتوسط TAT يساوي 8.5، وهما نتيجة الحل اليدوي نفسها. ومع تبديل الكتلتين تعود العملية التي انتزع منها المعالج إلى الطابور قبل العمليات الواصلة في تلك اللحظة. فعند t = 7 تنتهي شريحة P3 لحظة وصول P5، فتتقدم P3 الآن على P5: ينخفض زمن انتظار P3 من 10 إلى 8، ويرتفع زمن انتظار P5 من 7 إلى 8، ويصبح متوسط WT يساوي 5.17. وقاعدة المحاضرة هي الترتيب الأول.

فحص سريع

1. SJF: تنتهي أقصر المهام أولا، فيكتمل أكبر عدد من العمليات في كل وحدة زمنية.
2. FIFO، وهو اسم آخر لـFCFS: تحتفظ العملية بالمعالج حتى تنتهي.
3. العبارات الثلاث كلها صحيحة. قد تتخطى SRTF عملية طويلة إلى الأبد، وأي أسلوب استباقي قد يسبب تجويع عملية ما، والتناوب الدائري يعطي كل عملية دورا مرة في كل دورة للطابور.
4. التناوب الدائري: إعادة التقييم كل T وحدة وتفضيل من انتظر أطول يسلكان سلوك شريحة زمنية طولها T.