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

بحلول نهاية هذا الدرس ستكون قادرا على تتبع وتقييم جدولة FCFS و SJF و Priority و Round Robin يدويا، والتحقق من مخططات Gantt التي تحلها يدويا مقابل محاكي C# مبني حول ready queue حقيقي.

الأهداف

• تحديد معايير الجدولة واستخدامها للحكم على ما إذا كانت خوارزمية جدولة معينة تؤدي عملها بشكل جيد.
• تتبع، يدويا، مخطط Gantt الناتج عن جدولة FCFS و SJF (non-preemptive و preemptive) و Priority (non-preemptive و preemptive) و Round Robin.
• شرح، من الناحية المفهومية، كيف توجه جدولة Multilevel Queue و Multilevel Feedback Queue العمليات بين الـ queues، بما في ذلك كيف يقاوم aging الـ starvation في نسخة الـ feedback queue. هاتان الخوارزميتان مشروحتان بالتعريف والمخطط فقط: لا واحدة منهما تحصل على مثال رقمي محلول يدويا أو مهمة عملية، لأن أي مسألة محلولة تحتاج مجموعة بيانات كاملة لأوقات الوصول وأوقات الـ burst لا يوفرها المادة الخاصة بالخوارزمية نفسها.
• حساب completion time و turnaround time و waiting time ومتوسطاتها وكفاءة المعالج لمجموعة من العمليات.
• توسيع class جدولة يعتمد فقط على burst time إلى محاكي يفهم أوقات الوصول و ready queue و time quantum قابل للتهيئة.
• التحقق من مخطط Gantt محلول يدويا مقابل برنامج C# فعلي ومقابل الفحوصات الحسابية (اتساق CT/TAT/WT) المستخدمة في هذا الدرس بالكامل.

المتطلبات السابقة

• إنهاء درس FCFS السابق و الـ class الخاص بها FCFS (مصفوفة double[] لأوقات الـ burst مع GetTurnAroundTime و GetWaitingTime و GetAverageWaitingTime و GetAverageTurnAroundTime).
• فهم أساسي لحالات العملية والـ process control block (PCB: السجل الخاص بكل عملية والذي يحفظه نظام التشغيل ويعيد استرجاعه كل مرة ينقل فيها المعالج من عملية إلى أخرى).
• تثبيت .NET SDK ومعرفة أساسية بلغة C# (الـ classes و List<T> و LINQ بسيط). تأكد من ذلك بتشغيل dotnet --version قبل بدء المهمة 3؛ إذا لم يتعرف على هذا الأمر، ثبت الـ SDK من صفحة تحميل .NET الرسمية لنظام تشغيلك أولا.
• الاستعداد لرسم مخططات Gantt على الورق؛ النصف الخاص بالمحاكاة من هذا الدرس يصبح أسهل بكثير بعد ترسيخ النصف النظري.

معايير الجدولة

قبل مقارنة الخوارزميات نحتاج إلى مصطلحات مشتركة لمعنى "جيدة". خمسة معايير تتكرر في هذا الدرس بالكامل؛ ثلاثة منها (Efficiency و turnaround time و waiting time) تحصل على مثال رقمي محلول بالكامل، بينما throughput و response time يعرفان هنا ثم يتحولان إلى شيء ملموس بحساب قصير مباشرة بعد القائمة:

• Efficiency: مقدار الوقت الذي يقضيه المعالج في عمل مفيد بدلا من الجلوس خاملا، محسوبا كالوقت المفيد مقسوما على الوقت الإجمالي. هذه القيمة هي التي تحسب في Problem 2 أدناه.
• Throughput: عدد العمليات المكتملة في وحدة الزمن. الخوارزمية التي تنهي العمليات القصيرة بسرعة (مثل SJF) تميل إلى إعطاء throughput أعلى من خوارزمية تسمح لعملية طويلة بالاستحواذ على المعالج.
• Turnaround time: إجمالي الوقت الذي تقضيه عملية في النظام، من وصولها إلى ready queue حتى اكتمالها بالكامل: Turnaround Time = Completion Time - Arrival Time.
• Waiting time: الوقت الذي تقضيه عملية في الانتظار داخل ready queue، وليس على المعالج. بما أن burst time هو الوقت المستغرق فعليا على المعالج، فإن ما تبقى من turnaround time هو وقت الانتظار: Waiting Time = Turnaround Time - Burst Time.
• Response time: الوقت من وصول العملية حتى تحصل على المعالج لأول مرة، ويحسب فقط أول مرة يتم فيها dispatch لها، وليس أي مرة لاحقة تحصل فيها على المعالج بعد أن تكون قد تعرضت لـ preemption. هذا المعيار مهم بشكل خاص في الأنظمة التفاعلية القائمة على time-sharing، حيث يحتاج المستخدم أن يرى النظام يستجيب حتى قبل أن تنتهي العملية بالكامل.

لجعل throughput و response time أمرا ملموسا لا مجرد تعريف: في Problem 1 أدناه، تنتهي خمس عمليات جميعها في الزمن 19، فيكون throughput = 5 عمليات / 19 ms، أي حوالي 0.26 عملية في كل ms (أي عملية واحدة تقريبا كل 3.8 ms). تطبيق تعريف response time على مخطط Gantt الخاص بـ Problem 4 أدناه (preemptive SRTF) يوضح لماذا response time و waiting time هما فعلا رقمان مختلفان: response time يحسب فقط أول dispatch، فيحصل P1 و P2 على المعالج في نفس لحظة وصولهما فيكون response time لهما 0، و P3 (يصل في 3، ويعمل أول مرة في 6) له response time يساوي 3 ms، و P4 (يصل في 8، ويعمل أول مرة في 12) له response time يساوي 4 ms، فيكون متوسط response time = (0+0+3+4)/4 = 1.75 ms، وهو أقل بكثير من متوسط waiting time لتلك المسألة والذي يساوي 5.5 ms.

كل مسألة محلولة أدناه تختصر إلى تعبئة جدول من arrival time (AT) و burst time (BT) و completion time (CT) و turnaround time (TAT) و waiting time (WT)، ثم حساب متوسط عمودي TAT و WT. الخطوة التي لا يوجد لها اختصار هي بناء مخطط Gantt بشكل صحيح؛ وبعد أن يكون ذلك صحيحا، كل ما تبقى هو حساب.

جدولة First-Come, First-Served (FCFS)

التعريف: العملية التي تطلب المعالج أولا هي التي تحصل عليه أولا. الغرض: أبسط سياسة ممكنة، سهلة الفهم والتنفيذ. كيف تعمل: ready queue هي queue من نوع FIFO عادي. عند وصول عملية، يربط PCB الخاص بها بذيل الـ queue؛ وعندما يصبح المعالج فارغا، يذهب إلى العملية الموجودة في رأس الـ queue، والتي تحذف بعد ذلك من الـ queue. FCFS غير preemptive: بمجرد أن تحصل عملية على المعالج، لا شيء يأخذه منها حتى تنتهي أو تحظر لـ I/O.

flowchart LR
    New([Process arrives]) -->|linked to tail| Q["FIFO ready queue"]
    Q -->|head, when CPU is free| Dispatch["Dispatch to CPU\n(removed from queue)"]
    Dispatch -->|terminates or blocks for I/O| Done([Leaves the CPU])

مثال (convoy effect): ثلاث عمليات P1 (burst 24) و P2 (burst 3) و P3 (burst 3)، وتصل جميعها في الزمن 0.

إذا وصلت بالترتيب P1، P2، P3:

|   P1   |   P2   |   P3   |
0       24       27       30

أوقات الانتظار هي 0، 24، 27، فيكون متوسط وقت الانتظار (0+24+27)/3 = 17 ms.

إذا وصلت العمليات الثلاث نفسها بالترتيب P2، P3، P1:

|   P2   |   P3   |   P1   |
0        3        6       30

أوقات الانتظار الآن هي 0، 3، 6، فينخفض متوسط وقت الانتظار إلى (0+3+6)/3 = 3 ms.

نفس العمليات، ونفس أوقات الـ burst، وفقط ترتيب الوصول تغير، ومع ذلك انخفض متوسط وقت الانتظار من 17 ms إلى 3 ms. هذا هو الـ convoy effect: عملية طويلة تصل قبل عدة عمليات قصيرة تجبر كل عملية قصيرة على الانتظار خلفها. FCFS سهلة التنفيذ لكن متوسط وقت الانتظار فيها ليس أدنى ما يمكن بشكل عام، وهذا قد يكون كارثيا لأنظمة time-sharing، حيث يتوقع أن تحصل كل عملية على نصيب من المعالج على فترات منتظمة.

جدولة Shortest Job First (SJF)

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

• SJF غير preemptive: بمجرد أن تبدأ عملية بالعمل، تكمل حتى النهاية، حتى لو وصلت عملية أقصر بينما هي تعمل.
• SJF preemptive، ويسمى أيضا Shortest-Remaining-Time-First (SRTF): إذا وصلت عملية جديدة يكون burst التالي لها أقصر من الوقت المتبقي للعملية التي تعمل حاليا، تتعرض العملية العاملة لـ preemption ويعطى المعالج للعملية الجديدة الواصلة. العملية المعرضة للـ preemption تحتفظ بما تبقى لها من burst time وتدخل مرة أخرى في المقارنة لاحقا.

flowchart TD
    Arrive([New process arrives]) --> Compare{"Is its next burst shorter than\nthe running process's remaining time?"}
    Compare -->|No, or nothing is running| Queue["Joins the ready queue"]
    Compare -->|"Yes, and scheduling is preemptive (SRTF)"| Preempt["Running process is preempted\nand re-enters the ready queue"]
    Preempt --> Dispatch["New arrival gets the CPU"]
    Queue --> Pick["Whoever has the shortest\nnext burst runs next"]

الصعوبة الحقيقية هي أن طول burst المعالج التالي لعملية غير معروف مسبقا؛ الـ scheduler لا يمكنه إلا تقدير ذلك، عادة بافتراض أن الـ burst التالي مشابه في الطول للـ bursts السابقة. لهذا السبب، لا يمكن تنفيذ SJF حرفيا على مستوى short-term scheduling (مستوى الـ scheduler الذي يختار أي عملية جاهزة تحصل على المعالج التالي)، لكن التقدير لا يزال مفيدا، والخوارزمية التالية تستعير فكرتها الأساسية.

مثال (غير preemptive، أربع عمليات P1 إلى P4 بأوقات burst 6، 8، 7، 3 ms، وتصل جميعها في الزمن 0):

|   P4   |   P1   |   P3   |   P2   |
0        3        9       16       24

الحساب الكامل لوقت الانتظار والمتوسط لهذا المثال بالضبط موضح في Problem 3 أدناه.

مشكلة SJF/SRTF: السعي لأصغر متوسط وقت انتظار ممكن له تكلفة. إذا استمرت عمليات أقصر في الوصول، فإن عملية طويلة جالسة في ready queue (أو، في حالة SRTF، عملية طويلة تتعرض لـ preemption مرارا) يمكن أن تتجاهل إلى ما لا نهاية، لأن هناك دائما شيء أقصر جاهز للعمل أولا. هذه هي نفس مشكلة starvation المناقشة أدناه بخصوص جدولة Priority، والجدولة الـ preemptive بشكل عام يمكن أن تسببها لهذا السبب بالضبط: أي قاعدة تحدد من يعمل بعد ذلك يمكنها دائما أن تجد مرشحا "أفضل" من الذي انتظر أطول.

جدولة Priority

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

flowchart TD
    Arrive([New process arrives]) --> Compare{"Is its priority better than\nthe running process's priority?"}
    Compare -->|No| Queue["Joins the ready queue,\nordered by priority (ties: FCFS)"]
    Compare -->|"Yes, non-preemptive"| WaitHead["Waits at the head of the queue\nuntil the running process finishes"]
    Compare -->|"Yes, preemptive"| Takeover["Takes the CPU immediately;\nrunning process re-enters the queue"]

راقب الاتفاقية المستخدمة في مسألة معينة: بعضها يقول إن أصغر رقم هو أعلى priority (0 = الأهم)، وبعضها يقول إن أكبر رقم هو الأعلى. تحقق دائما قبل رسم مخطط Gantt.

مثال (غير preemptive، الرقم الأصغر = priority أعلى): خمس عمليات تصل جميعها في الزمن 0: P1 (BT 10، priority 3)، P2 (BT 1، priority 1)، P3 (BT 2، priority 4)، P4 (BT 1، priority 5)، P5 (BT 5، priority 2).

|   P2   |   P5   |   P1   |   P3   |   P4   |
0        1        6       16       18       19

متوسط waiting time = (6+0+16+18+1)/5 = 8.2 ms. مجموعة البيانات هذه يعاد استخدامها كبلوك Priority (non-preemptive) في قائمة البرنامج الكاملة في نهاية هذا الدرس (المهام 3 إلى 5).

مثال (غير preemptive، الرقم الأكبر = priority أعلى، أوقات وصول متدرجة): هذا المثال الثاني موجود خصيصا لتوضيح تحذير الاتفاقية أعلاه في حالة يكون فيها الأمر مهما بالفعل. خمس عمليات: P1 (AT 0، BT 4، priority 2)، P2 (AT 1، BT 3، priority 3)، P3 (AT 2، BT 1، priority 4)، P4 (AT 3، BT 5، priority 5)، P5 (AT 4، BT 2، priority 5). هنا الرقم الأكبر هو الـ priority الأعلى.

|   P1   |   P4   |   P5   |   P3   |   P2   |
0        4        9       11       12       15

P1 تصل أولا وتعمل حتى الاكتمال بغض النظر عن الـ priority، لأن هذه غير preemptive: حتى لو كانت كل عملية أخرى (priority 3، 4، 5، 5) تتفوق على P1 (priority 2)، لا يمكن لأي منها أخذ المعالج بعد أن يكون بيد P1. في الزمن 4، تنتهي P1، وتكون P2 و P3 و P4 و P5 قد وصلت جميعها وتنتظر. أعلى priority بينها هي 5، مشتركة بين P4 و P5؛ ويحل التعادل بـ FCFS، و P4 وصلت أولا (الزمن 3، مقابل زمن P5 وهو 4)، فتعمل P4 التالية. بعد P4، أعلى priority متبقية هي priority P5 وهي 5، ثم priority P3 وهي 4، ثم priority P2 وهي 3.

متوسط turnaround time = (4+14+10+6+7)/5 = 8.2 ms. متوسط waiting time = (0+11+9+1+5)/5 = 5.2 ms.

مشكلة priority scheduling: عملية ذات priority منخفضة تكون جاهزة لكنها لا تحصل على المعالج أبدا تكون blocked، وتيار مستمر من الوصولات ذات priority أعلى يمكن أن يتركها منتظرة إلى الأبد، وهي حالة تسمى indefinite blocking أو starvation. الحل هو aging: رفع priority العملية تدريجيا كلما طال انتظارها. على سبيل المثال، مع priorities من 0 (الأعلى) إلى 127 (الأدنى)، يمكن أن ينخفض رقم عملية منتظرة بمقدار 1 كل 15 دقيقة، بحيث تصبح حتى عملية بدأت عند 127 في النهاية أعلى priority في النظام ويضمن لها أن تعمل. قسم Multilevel Feedback Queue أدناه يرسم نفس آلية الـ aging هذه.

جدولة Round Robin (RR)

التعريف: صممت Round Robin خصيصا لأنظمة time-sharing. تتصرف مثل FCFS، لكن مع إضافة preemption من خلال time quantum (عادة من 10 إلى 100 ms): يسمح لكل عملية بالعمل لمدة quantum واحد كحد أقصى قبل أن تتعرض لـ preemption وترسل إلى نهاية الـ queue. كيف تعمل: تعامل ready queue كـ circular FIFO queue.

flowchart LR
    P1 --> P2 --> P3 --> P4 --> Pdots["..."] --> P10 --> P1
    Head(("head of the\ncircular queue")) -.-> P1
    Sched["CPU scheduler"] -. "always dispatches\nwhoever is at the head" .-> Head

P1 مرسومة في الرأس فقط لأن المخطط يجب أن يبدأ من مكان ما؛ وبمجرد أن تنزع العمليات من الـ queue وترسل إلى الذيل، تجد عملية مختلفة في الرأس في كل دورة حول الدائرة. الـ scheduler دائما يرسل ما هو في رأس الـ queue للعمل ويضبط مؤقتا لمدة quantum واحد. حينها يمكن أن يحدث أحد شيئين: إذا كان الـ burst المتبقي للعملية أقصر من الـ quantum، تنتهي وتطلق المعالج طواعية؛ وإلا يفعل المؤقت، وتتعرض العملية لـ preemption، وتوضع في ذيل الـ queue خلف أي عمليات وصلت بينما كانت تعمل. حالة التعادل المهمة عند الحدود الدقيقة: إذا انتهى quantum عملية في نفس المللي ثانية بالضبط التي تصل فيها عملية جديدة، تلتحق الوصول الجديد بالـ queue أولا، وتدخل العملية التي تعرضت للتو لـ preemption خلفها.

اختيار الـ quantum مهم جدا. إذا كان كبيرا جدا، تتحول Round Robin إلى FCFS، لأن العملية الأولى تعمل ببساطة حتى الاكتمال قبل أن تحصل أي عملية أخرى على دورها. وإذا كان صغيرا جدا، يحدث context switching مفرط، لأن الـ overhead الخاص بحفظ واستعادة حالة العملية يبدأ بالسيطرة على العمل المفيد. اختيار quantum جيد هو الغاية الكاملة للخوارزمية.

Round Robin أيضا تعطي response time أفضل بشكل واضح من FCFS. في FCFS، عملية في رأس الـ queue تعمل حتى الاكتمال بدون preemption، فإذا كانت تملك burst طويل، تنتظر كل عملية خلفها طوال هذا الوقت قبل أن تحصل على المعالج حتى لمرة واحدة. الـ preemption في Round Robin تضمن لكل عملية دورا مرة واحدة على الأقل في كل دورة حول الـ queue، وهذا يحافظ على response time منخفض بغض النظر عن طول الـ burst الكلي لأي عملية.

جدولة Multilevel Queue

التعريف: بدلا من ready queue واحدة، تصنف العمليات إلى مجموعات (على سبيل المثال، foreground/interactive مقابل background/batch)، وتحصل كل مجموعة على queue دائمة خاصة بها. الغرض: فئات مختلفة من العمليات لها احتياجات response-time مختلفة، فمن المفيد جدولتها بشكل مختلف. كيف تعمل: كل queue تشغل خوارزمية جدولة خاصة بها داخليا (queue الـ foreground قد تستخدم Round Robin للبقاء تفاعلية، و queue الـ background تستخدم FCFS عادية لأن الانتظار فيها مقبول)، وهناك أيضا جدولة بين الـ queues، وأكثرها شيوعا هي fixed-priority preemptive: عملية في queue أعلى priority يمكنها أخذ المعالج من عملية تعمل في queue أقل priority. بعد التخصيص، تبقى العملية في queue خاصتها بشكل دائم، وهذه هي الخاصية الأساسية التي تفصل هذه الخوارزمية عن الخوارزمية التالية.

مثال نموذجي يستخدم خمس queues بترتيب priority: system و interactive و interactive editing و batch و student processes. queue الـ student، بكونها أقل priority، لا تعمل إلا عندما تكون كل queue فوقها فارغة، وأي وصول في أي queue أعلى priority يأخذ منها المعالج فورا.

flowchart TB
    Sys["System processes (highest priority)"]
    Int["Interactive processes"]
    IntEdit["Interactive editing processes"]
    Batch["Batch processes"]
    Student["Student processes (lowest priority)"]
    Sys -->|preempts| Int -->|preempts| IntEdit -->|preempts| Batch -->|preempts| Student

جدولة Multilevel Feedback Queue (MLFQ)

التعريف: امتداد لـ multilevel queue scheduling، حيث يسمح للعمليات بـ الانتقال بين الـ queues بدلا من تخصيصها بشكل دائم لواحدة منها. الغرض: فصل العمليات بحسب السلوك الفعلي لـ CPU bursts الخاصة بها، بحيث لا تحظر عملية كثيفة الاستخدام للمعالج العمليات التفاعلية أو المرتبطة بالـ I/O إلى الأبد، مع الاستمرار في حماية العمليات التي انتظرت طويلا من الـ starvation. كيف تعمل: عملية تستخدم وقت معالج كثير جدا في queue عالية priority تخفض إلى queue أقل؛ وعملية تنتظر طويلا جدا في queue منخفضة priority ترفع إلى queue أعلى (نفس فكرة aging المستخدمة ضد starvation في priority scheduling).

flowchart LR
    New([New process]) --> Q0["Q0 - quantum 8 ms"]
    Q0 -->|does not finish in 8 ms| Q1["Q1 - quantum 16 ms"]
    Q1 -->|does not finish in 16 ms| Q2["Q2 - FCFS"]
    Q1 -->|waited too long: aging| Q0
    Q2 -->|waited too long: aging| Q1
    Q0 -->|finishes| Done([Terminates])
    Q1 -->|finishes| Done
    Q2 -->|finishes| Done

يعرف MLFQ scheduler بالكامل بخمسة معاملات: عدد الـ queues، وخوارزمية الجدولة المستخدمة داخل كل queue، وطريقة تحديد وقت ترفيع عملية إلى queue أعلى priority، وطريقة تحديد وقت تخفيض عملية إلى queue أقل priority، وطريقة تحديد أي queue تدخلها العملية عند حاجتها للخدمة لأول مرة. في المخطط أعلاه، تحصل عملية على 8 ms في الـ queue العلوية؛ وإذا احتاجت أكثر، تنتقل إلى 16 ms في الـ queue الوسطى؛ وإذا احتاجت أكثر، تنتهي على FCFS في الـ queue السفلية. الـ queues الأعلى priority تخدم دائما أولا، تماما كما في multilevel queue scheduling، لكن هنا لا تبقى أي عملية عالقة بشكل دائم في الـ queue التي بدأت فيها.

المهمة 1: حل ست مسائل جدولة محلولة بالكامل يدويا

اعمل على الست مسائل أدناه على الورق. لكل واحدة، رسم مخطط Gantt أولا؛ كل قيمة أخرى تستنتج منه.

Problem 1 (FCFS بأوقات وصول مختلفة). خمس عمليات: P1 (AT 4، BT 5)، P2 (AT 6، BT 4)، P3 (AT 0، BT 3)، P4 (AT 6، BT 2)، P5 (AT 5، BT 4). عندما تصل عمليتان في نفس الزمن، تسبق الأصغر process ID. بناء مخطط Gantt، مع تذكر وضع علامة على أي وقت idle للمعالج.

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

متوسط turnaround time = (5+11+3+13+8)/5 = 8 ms. متوسط waiting time = (0+7+0+11+4)/5 = 4.4 ms.

Problem 2 (FCFS مع وحدة واحدة من overhead الجدولة). ست عمليات P1..P6 تصل في الأزمنة 0، 1، 2، 3، 4، 5 بأوقات burst 3، 2، 1، 4، 5، 2. هذه المرة يحتاج النظام وحدة تأخير إضافية واحدة قبل أن يتمكن من تسليم المعالج لعملية، سواء كان ذلك أول dispatch لها أو انتقالا من عملية أخرى. أوجد كفاءة الجدولة.

|  del   |   P1   |  del   |   P2   |  del   |   P3   |  del   |   P4   |  del   |   P5   |  del   |   P6   |
0        1        4        5        7        8        9       10       14       15       20       21       23

الوقت المهدر (idle/overhead) هو التأخيرات الستة ذات الوحدة الواحدة: 6 × 1 = 6 وحدات. الوقت الكلي لإنهاء كل الست عمليات هو 23 وحدة (completion time لـ P6). الوقت المفيد = الوقت الكلي - الوقت المهدر = 23 - 6 = 17 وحدة.

Efficiency = الوقت المفيد / الوقت الكلي = 17 / 23 = 0.7391 = 73.91%.

Problem 3 (SJF غير preemptive). أربع عمليات P1..P4 تصل جميعها في الزمن 0 بأوقات burst 6، 8، 7، 3 ms. جدولها بـ SJF غير preemptive.

|   P4   |   P1   |   P3   |   P2   |
0        3        9       16       24

بما أن الأربع تصل معا، فإن وقت انتظار كل عملية هو ببساطة الزمن الذي تبدأ فيه: P4 تنتظر 0، P1 تنتظر 3، P3 تنتظر 9، P2 تنتظر 16.

متوسط waiting time = (3+16+9+0)/4 = 7 ms. للمقارنة، تشغيل نفس الأربع عمليات بالضبط تحت FCFS (بترتيب الـ ID) يعطي متوسط waiting time يساوي 10.25 ms، وهو أسوأ: إعطاء المعالج لأقصر عملية أولا يقلل إجمالي الانتظار في النظام.

Problem 4 (SJF preemptive / SRTF). تصل أربع عمليات كالتالي: P1 (AT 0، BT 12)، P2 (AT 2، BT 4)، P3 (AT 3، BT 6)، P4 (AT 8، BT 5). يستخدم النظام preemptive shortest-remaining-time-first scheduling. أوجد متوسط waiting time.

|   P1   |   P2   |   P3   |   P4   |   P1   |
0        2        6       12       17       27

بالمرور على الحل: تبدأ P1 في الزمن 0. في الزمن 2، تصل P2 ببرست 4، أقل من المتبقي لـ P1 وهو 10، فتتعرض P1 لـ preemption. في الزمن 3، تصل P3 ببرست 6، لكن P2 لديها فقط 3 ms متبقية، فتستمر P2 في العمل وتنتهي عند 6. في الزمن 8، تصل P4 ببرست 5، لكن P3 (تعمل منذ 6) لديها فقط 4 ms متبقية، فتنتهي P3 عند 12. عند 12 يكون الاختيار بين P1 (10 ms متبقية) و P4 (5 ms، لم تلمس): تعمل P4 من 12 إلى 17، ثم تعمل P1 آخر 10 ms المتبقية لها من 17 إلى 27.

في جدولة preemptive، من الأسهل قراءة waiting time مباشرة من مخطط Gantt بدلا من حساب completion time أولا، باستخدام Waiting Time = (last time the process got the CPU) - (milliseconds already executed before that) - Arrival Time. هذه ليست صيغة جديدة، فقط الصيغة المعروفة WT = TAT - BT = (CT - AT) - BT معاد ترتيبها: بمجرد أن تبدأ عملية شريحتها الأخيرة، لا شيء يتعرض لها لـ preemption مرة أخرى، فيكون completion time الخاص بها يساوي زمن هذا البدء الأخير زائد ما تبقى لها من burst، و"البرست المتبقي" هو فقط إجمالي burst time ناقص المللي ثوانى التي نفذت لها سابقا. تعويض CT = (last start) + BT - (executed earlier) في WT = CT - AT - BT يحذف حد BT ويترك بالضبط الصيغة أعلاه:

متوسط waiting time = (15+0+3+4)/4 = 5.5 ms.

Problem 5 (Priority preemptive، 0 = أعلى priority). خمس عمليات: P1 (AT 0، BT 11، priority 2)، P2 (AT 5، BT 28، priority 0)، P3 (AT 12، BT 2، priority 3)، P4 (AT 2، BT 10، priority 1)، P5 (AT 9، BT 16، priority 4). الـ scheduler هو preemptive priority scheduling.

|   P1   |   P4   |   P2   |   P4   |   P1   |   P3   |   P5   |
0        2        5       33       40       49       51       67

تتبع الحل: تبدأ P1 في الزمن 0. في الزمن 2، تصل P4 بـ priority 1، أفضل من priority P1 وهي 2، فتتعرض P1 (نفذ منها 2 من 11 ms) لـ preemption. في الزمن 5، تصل P2 بـ priority 0، وهي أفضل قيمة ممكنة، تأخذ المعالج من P4 وتعمل دون انقطاع حتى الاكتمال عند 33، لأن لا شيء يصل لاحقا (P5 عند 9، P3 عند 12) يتفوق على priority 0. عند 33 تحتوي ready queue على P1 (priority 2، 9 ms متبقية) و P3 (priority 3، 2 ms) و P4 (priority 1، 7 ms متبقية) و P5 (priority 4، 16 ms): إعطاء الأولوية للأفضل priority يعطي P4 أولا (تنتهي عند 40)، ثم P1 (تنتهي عند 49)، ثم P3 (تنتهي عند 51)، ثم P5 (تنتهي عند 67).

باستخدام نفس صيغة Waiting Time = (last start) - (executed earlier) - Arrival Time المستنتجة في Problem 4:

متوسط waiting time = (38+0+37+28+42)/5 = 29 ms.

Problem 6 (Round Robin، quantum = 4 ms). ثلاث عمليات P1 (BT 24)، P2 (BT 3)، P3 (BT 3)، وتصل جميعها في الزمن 0.

|   P1   |   P2   |   P3   |   P1   |   P1   |   P1   |   P1   |   P1   |
0        4        7       10       14       18       22       26       30

تستخدم P1 quantum الأول لها (0-4)، ثم تنتهي P2 و P3 كل منهما خلال quantum واحد فقط لكل منهما (تحتاجان فقط 3 ms، فتطلقان المعالج طواعية)، وبعد ذلك تكون P1 هي العملية الوحيدة المتبقية، فتحصل على المعالج مرارا وتكرارا حتى تستهلك الـ 20 ms المتبقية لها في خمس شرائح إضافية من 4 ms.

متوسط turnaround time = (30+7+10)/3 = 15.67 ms. متوسط waiting time = (6+4+7)/3 = 5.67 ms.

المهمة 2: حل أربع مسائل جدولة بمفردك

الآن اعمل الشيء نفسه بدون حل جاهز أمامك: رسم مخطط Gantt، وتعبئة جدول CT/TAT/WT مثل الجداول أعلاه، وحساب المتوسطات المطلوبة. تحقق من عملك بنفس الطريقة التي تفحص بها أي مسألة محلولة أعلاه: يجب أن يساوي WT دائما TAT ناقص BT لكل عملية، ويجب أن يساوي آخر completion time مجموع كل أوقات الـ burst زائد أي فترات idle وضعت علامة عليها، وبالنسبة لمسألة 4 أدناه، اختيار قاعدة التعادل المذكورة في قسم Round Robin يجب أن يكون هو الحكم الوحيد المتبقي، وليس تخمينا. المهمة 5 لاحقا تجعلك تربط واحدة من هذه الأربع مجموعات بيانات نفسها بالمحاكي، وهذا يعطيك فحصا ثانيا مستقلا بمجرد أن تصل إلى ذلك.

1. FCFS. P1 (AT 0، BT 6)، P2 (AT 1، BT 2)، P3 (AT 2، BT 8)، P4 (AT 3، BT 3). أوجد متوسط waiting time ومتوسط turnaround time.
2. SJF غير preemptive. P1 و P2 و P3 و P4 تصل جميعها في الزمن 0 بأوقات burst 7، 4، 1، 4 ms. أوجد متوسط waiting time. (عمليتان تتعادلان في burst time؛ تذكر كيف يحل التعادل.)
3. Priority غير preemptive، الرقم الأصغر = priority أعلى. كل الأربع عمليات تصل في الزمن 0: P1 (BT 8، priority 3)، P2 (BT 6، priority 1)، P3 (BT 1، priority 4)، P4 (BT 3، priority 2). أوجد متوسط waiting time ومتوسط turnaround time.
4. Round Robin، quantum = 3 ms. P1 (AT 0، BT 8)، P2 (AT 1، BT 4)، P3 (AT 2، BT 9)، P4 (AT 3، BT 5). رسم مخطط Gantt الكامل وأوجد متوسط waiting time ومتوسط turnaround time.

الناتج المتوقع: لكل مسألة، مخطط Gantt (مرسوم كجدول ASCII، بنفس الأسلوب المستخدم في المهمة 1)، وجدول CT/TAT/WT، والمتوسطان المطلوبان، مع تحقق WT = TAT - BT في كل صف. الأرقام النهائية للتحقق منها: مسألة 1 تعطي متوسط turnaround time يساوي 10.75 ms ومتوسط waiting time يساوي 6.00 ms؛ مسألة 2 تعطي متوسط waiting time يساوي 3.75 ms؛ مسألة 3 تعطي متوسط turnaround time يساوي 12.5 ms ومتوسط waiting time يساوي 8.00 ms؛ مسألة 4 تعطي متوسط turnaround time يساوي 20.00 ms ومتوسط waiting time يساوي 13.5 ms.

المهمة 3: توسيع class الـ FCFS إلى محاكي يفهم أوقات الوصول

قائمة البرنامج الكاملة في نهاية هذا الدرس تبني مباشرة على الـ class السابق FCFS: صيغتا turnaround time و waiting time لم تتغيرا، لكن بدلا من مصفوفة double[] مسطحة لأوقات الـ burst، العمليات الآن هي class اسمها Process تحمل ID و arrival time و burst time و priority، وبدلا من افتراض أن كل عملية جاهزة في الزمن 0، ready queue حقيقية لا تجعل عملية مؤهلة إلا بعد أن يمر arrival time الخاص بها.

الأنواع الثلاثة الداعمة هي:

public class Process
{
    public string Id { get; }
    public int ArrivalTime { get; }
    public int BurstTime { get; }
    public int Priority { get; }
    public int RemainingTime { get; set; }
 
    public Process(string id, int arrivalTime, int burstTime, int priority = 0)
    {
        Id = id;
        ArrivalTime = arrivalTime;
        BurstTime = burstTime;
        Priority = priority;
        RemainingTime = burstTime;
    }
}
 
public readonly struct GanttSlice
{
    public string ProcessId { get; }
    public int Start { get; }
    public int End { get; }
 
    public GanttSlice(string processId, int start, int end)
    {
        ProcessId = processId;
        Start = start;
        End = end;
    }
}
 
public class ScheduleResult
{
    public List<GanttSlice> Gantt { get; } = new();
    public Dictionary<string, int> CompletionTime { get; } = new();
}

بالمرور على هذا سطرا بسطر:

• public string Id { get; } هي read-only auto-property: وجود { get; } بدون set يعني أن C# يولد لك backing field مخفيا، لكن هذا الحقل لا يمكن تعيينه إلا داخل constructor الخاص بالـ class نفسها، وليس أبدا من الخارج. بمجرد بناء Process، لا يمكن لـ Id و ArrivalTime و BurstTime و Priority أن تتغير أبدا (RemainingTime، الموضحة بعد ذلك، هي الاستثناء الوحيد).
• public int RemainingTime { get; set; } هي الخاصية الوحيدة في Process التي تملك set، لأن Round Robin (المهمة 4) تحتاج إلى تقليصها كل مرة تتنازل فيها العملية عن المعالج دون أن تنتهي.
• constructor الـ Process يستقبل القيم الأربع التي تحتاجها العملية ويعين كل واحدة إلى الخاصية المطابقة لها؛ priority = 0 هو parameter افتراضي، بحيث تستطيع مجموعات بيانات FCFS و SJF (التي لا تستخدم priority) استدعاء new Process(id, arrivalTime, burstTime) بدون توفير واحدة. RemainingTime تبدأ مساوية لـ BurstTime، لأن شيئا لم يعمل بعد.
• GanttSlice تحل محل مصفوفة Process/burst-time المسطحة بشريحة واحدة من المخطط: أي عملية عملت (ProcessId، وتكون "IDLE" بالنسبة للفراغ)، وزمن Start و End الخاص بتلك الشريحة. أعلنت كـ readonly struct بدلا من class: الـ struct هو value type (ينسخ، لا يشار إليه، عند تمريره)، وكلمة readonly تعني أنه لا يمكن تغيير أي من خصائصه بعد البناء، وهذا يناسب شريحة Gantt تكتب مرة واحدة ولا تعدل بعد ذلك أبدا. الـ class قد تصلح أيضا، لكن نوع صغير غير قابل للتغيير وينشأ بشكل متكرر مثل هذا هو الحالة الكلاسيكية لاستخدام struct.
• ScheduleResult هي كل ما تحتاجه خوارزمية لتعيده: Gantt هي القائمة الكاملة المرتبة للشرائح، و CompletionTime هي Dictionary<string, int> تربط ID كل عملية بزمن انتهائها. هذا الـ dictionary وحده هو كل ما يحتاجه Report.Print بعد ذلك لاستنتاج turnaround time و waiting time، باستخدام الصيغتين نفسيهما تماما من class الـ FCFS الأصلية. = new() على كل خاصية يهيئ قائمة فارغة و dictionary فارغا لحظة إنشاء ScheduleResult، فتستطيع كل خوارزمية أدناه أن تبدأ في الإضافة إلى Gantt وتعيين مدخلات في CompletionTime بدون خطوة تهيئة منفصلة.

1. انظر إلى method Scheduler.RunFcfs أدناه (مستنسخة بالكامل في قائمة البرنامج الكاملة في نهاية هذا الدرس). هي ترتب العمليات بحسب arrival time، ثم تمر عليها، وتدرج شريحة "IDLE" كل مرة لا تكون العملية التالية قد وصلت بعد بحلول وقت تحرر المعالج.

public static ScheduleResult RunFcfs(List<Process> processes)
{
    var result = new ScheduleResult();
    var ordered = processes.OrderBy(p => p.ArrivalTime).ThenBy(p => p.Id).ToList();
    int time = 0;
 
    foreach (var p in ordered)
    {
        if (p.ArrivalTime > time)
        {
            result.Gantt.Add(new GanttSlice("IDLE", time, p.ArrivalTime));
            time = p.ArrivalTime;
        }
 
        int end = time + p.BurstTime;
        result.Gantt.Add(new GanttSlice(p.Id, time, end));
        result.CompletionTime[p.Id] = end;
        time = end;
    }
 
    return result;
}

بالمرور على هذا سطرا بسطر:

• var ordered = processes.OrderBy(p => p.ArrivalTime).ThenBy(p => p.Id).ToList(); ترتب قائمة العمليات كاملة مرة واحدة، بحسب arrival time أولا و ID العملية كقاعدة تعادل، مطابقة لقاعدة مسألة 1 القائلة "تسبق العملية ذات ID الأصغر"؛ .ToList() تجمد هذا الترتيب بحيث تستطيع بقية الـ method أن تمر عليه من البداية إلى النهاية فقط.
• int time = 0; هي الساعة الجارية. لا تتحرك أبدا إلا للأمام.
• foreach (var p in ordered) تزور كل عملية مرة واحدة بالضبط، بالترتيب الثابت الذي تحدد أعلاه. FCFS لا تحتاج أبدا لإعادة النظر في هذا الترتيب، لأن لا شيء يتعرض أبدا للـ preemption في أي شيء.
• if (p.ArrivalTime > time) { ... } هي فحص وقت الـ idle: إذا لم تصل العملية التالية في الترتيب بعد بحلول وقت تحرر المعالج، تضاف شريحة "IDLE" تغطي الفراغ، وتتقدم الساعة إلى ذلك الوصول، بالضبط شريحة idle المرسومة في مخطط Gantt لمسألة 1.
• int end = time + p.BurstTime; تحسب أين تنتهي شريحة هذه العملية: تعمل، بدون انقطاع، طوال burst time الخاص بها، لأن FCFS غير preemptive.
• result.Gantt.Add(new GanttSlice(p.Id, time, end)); تضيف شريحة هذه العملية إلى المخطط.
• result.CompletionTime[p.Id] = end; تسجل completion time لهذه العملية، وهو الرقم الوحيد الذي يحتاجه Report.Print بعد ذلك لحساب TAT و WT.
• time = end; تنقل الساعة إلى نهاية شريحة هذه العملية قبل أن تنظر الحلقة إلى العملية التالية.

2. شغل البرنامج بـ dotnet run.
3. الناتج المتوقع: بلوك التقرير الأول، المسمى FCFS، يجب أن يظهر نفس مخطط Gantt الخاص بمسألة 1 في المهمة 1، وسطراه الأخيران يجب أن يقرآ Average Waiting Time = 4.40 و Average Turnaround Time = 8.00.

المهمة 4: مقارنة الأربع خوارزميات كلها في تشغيل واحد

قائمة البرنامج الكاملة تنفذ أيضا Scheduler.RunSjf و Scheduler.RunPriority و Scheduler.RunRoundRobin(processes, quantum). RunFcfs ترتب كل العمليات مرة واحدة ثم تمر على هذا الترتيب الثابت في حلقة foreach واحدة، لأن ترتيب الوصول لا يتغير أبدا بعد ترتيب العمليات. RunSjf و RunPriority لا يمكنهما فعل ذلك: بما أن العملية "الأفضل" التالية للعمل تعتمد على من وصل حتى الآن، فهما تستخدمان بدلا من ذلك حلقة while (remaining.Count > 0) تعيد تصفية العمليات التي وصلت ولم تعمل بعد وتعيد اختيار الأفضل (أصغر burst time، أو أفضل priority) في كل نقطة dispatch بمفردها. فالحلقتان لهما شكل مختلف حقيقة، لا فرق في مفتاح الترتيب فقط؛ ما تتشاركانه هو كيف تتعاملان مع فراغ لا يوجد فيه شيء جاهز، بإدراج شريحة "IDLE" وتقديم الساعة إلى الوصول التالي، بالضبط كما تفعل RunFcfs. RunRoundRobin هي التي تحتاج فعلا Queue<Process> حقيقية، لأنها الخوارزمية الوحيدة هنا التي تعيد عملية إلى مكانها بعد إعطائها المعالج.

public static ScheduleResult RunSjf(List<Process> processes)
{
    var result = new ScheduleResult();
    var remaining = new List<Process>(processes);
    int time = 0;
 
    while (remaining.Count > 0)
    {
        var ready = remaining.Where(p => p.ArrivalTime <= time).ToList();
        if (ready.Count == 0)
        {
            int nextArrival = remaining.Min(p => p.ArrivalTime);
            result.Gantt.Add(new GanttSlice("IDLE", time, nextArrival));
            time = nextArrival;
            ready = remaining.Where(p => p.ArrivalTime <= time).ToList();
        }
 
        var next = ready
            .OrderBy(p => p.BurstTime)
            .ThenBy(p => p.ArrivalTime)
            .ThenBy(p => p.Id)
            .First();
 
        int end = time + next.BurstTime;
        result.Gantt.Add(new GanttSlice(next.Id, time, end));
        result.CompletionTime[next.Id] = end;
        time = end;
        remaining.Remove(next);
    }
 
    return result;
}

سطرا بسطر:

• var remaining = new List<Process>(processes); تنسخ قائمة الإدخال، بحيث تبقى قائمة الـ caller دون تغيير؛ تحذف العمليات من هذه النسخة واحدة تلو الأخرى مع عملها، وهذا كيف تعرف الحلقة أدناه متى تتوقف.
• while (remaining.Count > 0) تحل محل foreach الخاصة بـ RunFcfs: SJF لا يمكنها تحديد ترتيب التشغيل مسبقا، لأن أي عملية هي "الأفضل" يعتمد على من وصل بحلول وقت تحرر المعالج، فعلى الـ method أن تتخذ قرارا جديدا في كل dispatch.
• var ready = remaining.Where(p => p.ArrivalTime <= time).ToList(); تصفي remaining إلى العمليات التي وصلت فعلا بحلول الزمن الحالي فقط.
• بلوك if (ready.Count == 0) هي نفس حركة وقت الـ idle الخاصة بـ RunFcfs، لكن مكتوبة لقائمة بدلا من عملية "تالية" واحدة: إذا لم يصل أحد بعد، تدرج شريحة "IDLE"، وتنتقل الساعة إلى أقرب وصول متبق، وتعاد تصفية ready.
• .OrderBy(p => p.BurstTime).ThenBy(p => p.ArrivalTime).ThenBy(p => p.Id).First() هي قاعدة SJF نفسها: من بين كل الجاهزين الآن، اختر أصغر burst time، وحل التعادل بأقدم وصول ثم بـ Id، نفس قاعدة التعادل المستخدمة في المهمة 1 بالكامل.
• الأربعة أسطر المتبقية (int end = ... إلى remaining.Remove(next)) هي نفس المحاسبة الخاصة بـ RunFcfs (إضافة الشريحة، تسجيل completion time، تقديم الساعة)، مع إضافة واحدة: remaining.Remove(next) تخرج العملية التي عملت للتو من المجموعة، بحيث تنتهي حلقة while من العمل في النهاية وتتوقف.

Scheduler.RunPriority هي نفس الـ method مع سطر واحد مغير: .OrderBy(p => p.BurstTime) تصبح .OrderBy(p => p.Priority). كل شيء آخر، معالجة وقت الـ idle، سلسلة التعادل، المحاسبة، متطابق، وهذه طريقة الكود للتعبير عن النقطة السابقة القائلة أن SJF هي priority scheduling حيث تكون الـ priority هي burst time نفسه.

public static ScheduleResult RunRoundRobin(List<Process> processes, int quantum)
{
    var result = new ScheduleResult();
    var byArrival = processes.OrderBy(p => p.ArrivalTime).ThenBy(p => p.Id).ToList();
    var readyQueue = new Queue<Process>();
    int time = 0;
    int nextToArrive = 0;
 
    void EnqueueArrivals(int upToTime)
    {
        while (nextToArrive < byArrival.Count && byArrival[nextToArrive].ArrivalTime <= upToTime)
        {
            readyQueue.Enqueue(byArrival[nextToArrive]);
            nextToArrive++;
        }
    }
 
    void AdvanceToNextArrivalIfIdle()
    {
        if (readyQueue.Count == 0 && nextToArrive < byArrival.Count)
        {
            int nextArrival = byArrival[nextToArrive].ArrivalTime;
            if (nextArrival > time)
            {
                result.Gantt.Add(new GanttSlice("IDLE", time, nextArrival));
            }
            time = nextArrival;
            EnqueueArrivals(time);
        }
    }
 
    EnqueueArrivals(0);
    AdvanceToNextArrivalIfIdle();
 
    while (readyQueue.Count > 0)
    {
        var current = readyQueue.Dequeue();
        int start = time;
        int slice = Math.Min(quantum, current.RemainingTime);
        time += slice;
        current.RemainingTime -= slice;
        result.Gantt.Add(new GanttSlice(current.Id, start, time));
 
        EnqueueArrivals(time);
        if (current.RemainingTime > 0)
        {
            readyQueue.Enqueue(current);
        }
        else
        {
            result.CompletionTime[current.Id] = time;
        }
 
        AdvanceToNextArrivalIfIdle();
    }
 
    return result;
}

EnqueueArrivals و AdvanceToNextArrivalIfIdle هما local functions: methods معلنة داخل method أخرى، مرئية فقط داخل RunRoundRobin، وقابلة للاستدعاء مثل أي method أخرى من أي مكان بعد إعلانها في نفس الـ method. الشيء الذي يستحق التوقف عنده هو أنهما تقرآن وتكتبان time و nextToArrive، وهما متغيران معلنان في الـ method الخارجية، بدون تمرير أي منهما كـ parameter. هذا قانوني لأن local function هي closure: تلتقط متغيرات الـ method المحيطة بها by reference، فعندما تنفذ EnqueueArrivals سطر nextToArrive++، فإنها تغير نفس المتغير بالضبط الذي تقرؤه بقية RunRoundRobin في السطر التالي، وليس نسخة local خاصة. لم يحتج أي شيء في المهام 1 إلى 3 لهذا، لأن RunFcfs و RunSjf و RunPriority تفحص فراغ idle في مكان واحد فقط كل منها؛ Round Robin عليها أن تفعل نفس الفحص في كل مرة تنزع فيها عملية من الـ queue، فسحب المنطق المتكرر إلى دالتين مسماتين وقادرتين على الـ closure يتجنب كتابة نفس الأربعة أو الخمسة أسطر ثلاث مرات.

سطرا بسطر:

• var byArrival = processes.OrderBy(p => p.ArrivalTime).ThenBy(p => p.Id).ToList(); ترتب كل العمليات بحسب arrival time مرة واحدة، بنفس قاعدة التعادل السابقة. بخلاف RunFcfs، هذا الترتيب يحدد فقط من يلتحق بالـ queue ومتى، لا ترتيب عمل العمليات.
• var readyQueue = new Queue<Process>(); هي queue من نوع FIFO حقيقية (System.Collections.Generic.Queue<T>)، لأن Round Robin هي الخوارزمية الوحيدة هنا التي تعيد عملية إلى دورها بعد أن عملت من قبل.
• int nextToArrive = 0; هي index داخل byArrival: كل من الفهرس 0 إلى nextToArrive - 1 قد التحق بالـ queue في وقت ما؛ وكل من nextToArrive فما بعده لم يصل بعد.
• EnqueueArrivals(int upToTime) تمر على byArrival بدءا من nextToArrive وتدرج كل من يكون arrival time الخاص به عند أو قبل upToTime، وتقدم nextToArrive بعد كل من تدرجه؛ شرط while الخاص بها يتوقف لحظة الوصول إلى شخص لم يصل بعد، أو استنفاد العمليات.
• AdvanceToNextArrivalIfIdle() تتعامل مع الحالة التي تكون فيها الـ queue قد فرغت بالكامل بينما لا تزال عمليات تنتظر الوصول: تسجل شريحة "IDLE" إن كانت هناك فترة فراغ، وتقدم time إلى ذلك الوصول التالي، وتستدعي EnqueueArrivals فورا بحيث لا تبقى الـ queue فارغة عند الفحص التالي للحلقة.
• EnqueueArrivals(0); AdvanceToNextArrivalIfIdle(); قبل الحلقة الرئيسية تهيئان الـ queue للزمن 0، وتغطيان الحالة التي لا تصل فيها حتى العملية الأولى إلا بعد الزمن 0.
• داخل while (readyQueue.Count > 0): var current = readyQueue.Dequeue(); تأخذ من هو في رأس الـ queue. int slice = Math.Min(quantum, current.RemainingTime); هي قاعدة الـ quantum نفسها: عمل لمدة quantum واحد، أو لما تبقى من الـ burst، أيهما أصغر. time += slice; current.RemainingTime -= slice; تقدم الساعة وتقلص الحقل المتغير الوحيد في Process، وهذا بالضبط سبب امتلاك RemainingTime لـ set في عرض النوع أعلاه، بينما كل خاصية أخرى للقراءة فقط.
• EnqueueArrivals(time); تعمل قبل أن توضع العملية التي عملت للتو في الـ queue مرة أخرى إن أمكن. هذا الترتيب هو قاعدة التعادل من قسم Round Robin مترجمة إلى كود: "إذا انتهى quantum عملية في نفس المللي ثانية بالضبط التي تصل فيها عملية جديدة، تلتحق الوصول الجديد بالـ queue أولا، وتدخل العملية التي تعرضت للتو لـ preemption خلفها."
• if (current.RemainingTime > 0) { readyQueue.Enqueue(current); } else { result.CompletionTime[current.Id] = time; } هي التفرع الذي تفتقده كل خوارزمية أخرى هنا: عملية لا يزال لديها burst time متبق تعود إلى الـ queue بدلا من أن تعلم كمكتملة.
• AdvanceToNextArrivalIfIdle(); في أسفل الحلقة تغطي queue فرغت للتو لأن العملية التي انتهت، أو تعرضت لـ preemption، كانت الأخيرة الموجودة، بينما لا يزال آخرون مستحقي الوصول لاحقا.

1. شغل البرنامج مرة أخرى واقرأ كل الأربعة بلوكات تقرير: FCFS و SJF (non-preemptive) و Priority (non-preemptive) و Round Robin (quantum = 4).
2. طابق مجموعة بيانات كل بلوك مع الأمثلة المحلولة في هذا الدرس: بلوك FCFS يطابق مسألة 1 من المهمة 1، وبلوك SJF يطابق مسألة 3 من المهمة 1، وبلوك Priority يطابق أول مثال priority من قسم جدولة Priority (الرقم الأصغر = priority أعلى، وكل العمليات تصل في الزمن 0)، وبلوك Round Robin يطابق مسألة 6 من المهمة 1.
3. الناتج المتوقع: SJF (non-preemptive) تطبع Average Waiting Time = 7.00؛ Priority (non-preemptive) تطبع Average Waiting Time = 8.20؛ Round Robin (quantum = 4) تطبع Average Waiting Time = 5.67 و Average Turnaround Time = 15.67. أي عدم تطابق يكون تقريبا دائما bug في قاعدة التعادل (أقدم وصول، ثم أصغر ID) أو bug في ترتيب الـ queue: عملية وصلت حديثا يجب أن تلتحق بالـ queue قبل أن تعود العملية المعرضة لـ preemption إليها.

المهمة 5: إضافة مجموعة بياناتك الخاصة و quantum خاص بك

1. في method الـ Main (المعروضة في قائمة البرنامج الكاملة في نهاية هذا الدرس)، أضف بلوكا خامسا يشغل واحدة من الأربع مسائل التي حللتها بنفسك في المهمة 2 (اختر مسألة Round Robin، لأنها تشغل أكبر قدر من الكود) عبر method الـ Scheduler.Run... المطابقة لها، واطبع تقريرها بـ Report.Print.
2. غير الـ quantum الممرر إلى Scheduler.RunRoundRobin من 4 إلى قيمة أكبر كثيرا (مثلا 30) على مجموعة بيانات مسألة 6 من المهمة 1، وشغل البرنامج مرة أخرى.
3. الناتج المتوقع: متوسطات البلوك الجديد يجب أن تطابق إجابتك المحلولة يدويا في المهمة 2. مع quantum يساوي 30، يجب أن ينهار بلوك Round Robin على مجموعة بيانات مسألة 6 إلى تشغيل متواصل بأسلوب FCFS لـ P1 ثم P2 ثم P3، مع متوسط waiting time أعلى (أسوأ) بشكل واضح من تشغيل quantum-4: مقايضة الـ quantum من قسم Round Robin، مترجمة إلى شيء ملموس.

التسليم المقيم لهذا الدرس يتبع نفس نموذج تكليف FCFS السابق: يفحص مقابل مجموعة اختبارات وحدة مخفية تسلم عبر GitHub Classroom، وليس مقابل قائمة البرنامج الكاملة المعروضة في نهاية هذا الدرس، فطابق أسماء methods الخاصة بك وأشكال القيم المعادة مع ما يحدده قالب الـ classroom لهذا التكليف قبل الاعتماد على هذه القائمة كمرجع.

الملخص

• تحكم كل خوارزمية بنفس الخمسة معايير: Efficiency و Throughput و turnaround time و waiting time و response time؛ وكل مسألة تختصر إلى مخطط Gantt صحيح متبوعا بحساب.
• FCFS بسيطة وغير preemptive لكنها تعاني من الـ convoy effect: عملية طويلة تصل مبكرا تجبر كل عملية قصيرة خلفها على الانتظار أطول بكثير من اللازم.
• SJF (وشكلها الـ preemptive، SRTF) تقلل متوسط وقت الانتظار بتفضيل أقصر burst تالي على المعالج، بتكلفة الحاجة إلى التنبؤ بطول burst لا يمكن معرفته حقا مسبقا.
• جدولة Priority تعمم SJF إلى رقم priority عشوائي، preemptive أو غير ذلك؛ ونقطة ضعفها، starvation العمليات ذات priority منخفضة، تصلح بـ aging.
• Round Robin تضيف time quantum إلى جدولة على أسلوب FCFS بحيث تحصل كل عملية على نصيب من المعالج، وهذا أساسي لأنظمة time-sharing؛ والـ quantum هو مقايضة بين سلوك شبيه بـ FCFS (كبير جدا) و overhead context-switch مفرط (صغير جدا).
• جدولة Multilevel Queue تقسم العمليات إلى مجموعات دائمة، كل واحدة بخوارزميتها الخاصة وجدولة fixed-priority بين الـ queues؛ وجدولة Multilevel Feedback Queue تضيف ترفيعا وتخفيضا بين الـ queues، باستخدام aging ضد starvation.
• المحاكي المعروض في قائمة البرنامج الكاملة أدناه يربط الأربع خوارزميات الملموسة كلها حول نفس أنواع Process و GanttSlice و ScheduleResult ونفس صيغتي turnaround/waiting time من class الـ FCFS الأصلية؛ فقط قاعدة اختيار العملية التالية، وهل تعود أبدا إلى ready queue، تتغير بينها.

قائمة البرنامج الكاملة

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace SchedulingSimulator
{
    /// <summary>
    /// A single process, arrival-time aware. This replaces the plain
    /// double[] of burst times used by the earlier FCFS class: every
    /// process now knows when it is allowed to enter the ready queue,
    /// and carries a priority for the Priority-scheduling algorithm.
    /// </summary>
    public class Process
    {
        public string Id { get; }
        public int ArrivalTime { get; }
        public int BurstTime { get; }
        public int Priority { get; }       // lower value = higher priority
        public int RemainingTime { get; set; }
 
        public Process(string id, int arrivalTime, int burstTime, int priority = 0)
        {
            Id = id;
            ArrivalTime = arrivalTime;
            BurstTime = burstTime;
            Priority = priority;
            RemainingTime = burstTime;
        }
    }
 
    /// <summary>One bar of the Gantt chart: which process ran, and from when to when.</summary>
    public readonly struct GanttSlice
    {
        public string ProcessId { get; }
        public int Start { get; }
        public int End { get; }
 
        public GanttSlice(string processId, int start, int end)
        {
            ProcessId = processId;
            Start = start;
            End = end;
        }
    }
 
    /// <summary>
    /// Everything a scheduling run produces: the full Gantt chart, plus
    /// a completion time per process. That is all Report.Print needs to
    /// derive turnaround time and waiting time, using the same two
    /// formulas as the original FCFS class.
    /// </summary>
    public class ScheduleResult
    {
        public List<GanttSlice> Gantt { get; } = new();
        public Dictionary<string, int> CompletionTime { get; } = new();
    }
 
    public static class Scheduler
    {
        /// <summary>
        /// First-Come, First-Served: sort by arrival time (ties broken by
        /// process Id), then run each process to completion in that
        /// order. Non-preemptive. Inserts an "IDLE" slice whenever the
        /// CPU would otherwise sit empty waiting for the next arrival.
        /// </summary>
        public static ScheduleResult RunFcfs(List<Process> processes)
        {
            var result = new ScheduleResult();
            var ordered = processes.OrderBy(p => p.ArrivalTime).ThenBy(p => p.Id).ToList();
            int time = 0;
 
            foreach (var p in ordered)
            {
                if (p.ArrivalTime > time)
                {
                    result.Gantt.Add(new GanttSlice("IDLE", time, p.ArrivalTime));
                    time = p.ArrivalTime;
                }
 
                int end = time + p.BurstTime;
                result.Gantt.Add(new GanttSlice(p.Id, time, end));
                result.CompletionTime[p.Id] = end;
                time = end;
            }
 
            return result;
        }
 
        /// <summary>
        /// Shortest Job First, non-preemptive: at every decision point,
        /// pick the arrived process with the smallest burst time. Ties
        /// go to whoever arrived first, then to the smaller Id, exactly
        /// the FCFS tie-break rule from the lecture.
        /// </summary>
        public static ScheduleResult RunSjf(List<Process> processes)
        {
            var result = new ScheduleResult();
            var remaining = new List<Process>(processes);
            int time = 0;
 
            while (remaining.Count > 0)
            {
                var ready = remaining.Where(p => p.ArrivalTime <= time).ToList();
                if (ready.Count == 0)
                {
                    int nextArrival = remaining.Min(p => p.ArrivalTime);
                    result.Gantt.Add(new GanttSlice("IDLE", time, nextArrival));
                    time = nextArrival;
                    ready = remaining.Where(p => p.ArrivalTime <= time).ToList();
                }
 
                var next = ready
                    .OrderBy(p => p.BurstTime)
                    .ThenBy(p => p.ArrivalTime)
                    .ThenBy(p => p.Id)
                    .First();
 
                int end = time + next.BurstTime;
                result.Gantt.Add(new GanttSlice(next.Id, time, end));
                result.CompletionTime[next.Id] = end;
                time = end;
                remaining.Remove(next);
            }
 
            return result;
        }
 
        /// <summary>
        /// Priority scheduling, non-preemptive: lower Priority value
        /// wins; ties go to whoever arrived first, then to the smaller
        /// Id. Structurally identical to RunSjf above, just ordering by
        /// Priority instead of BurstTime -- SJF is, after all, priority
        /// scheduling where the priority is the burst time itself.
        /// </summary>
        public static ScheduleResult RunPriority(List<Process> processes)
        {
            var result = new ScheduleResult();
            var remaining = new List<Process>(processes);
            int time = 0;
 
            while (remaining.Count > 0)
            {
                var ready = remaining.Where(p => p.ArrivalTime <= time).ToList();
                if (ready.Count == 0)
                {
                    int nextArrival = remaining.Min(p => p.ArrivalTime);
                    result.Gantt.Add(new GanttSlice("IDLE", time, nextArrival));
                    time = nextArrival;
                    ready = remaining.Where(p => p.ArrivalTime <= time).ToList();
                }
 
                var next = ready
                    .OrderBy(p => p.Priority)
                    .ThenBy(p => p.ArrivalTime)
                    .ThenBy(p => p.Id)
                    .First();
 
                int end = time + next.BurstTime;
                result.Gantt.Add(new GanttSlice(next.Id, time, end));
                result.CompletionTime[next.Id] = end;
                time = end;
                remaining.Remove(next);
            }
 
            return result;
        }
 
        /// <summary>
        /// Round Robin: a real FIFO ready queue and a configurable time
        /// quantum. This is the one algorithm above that ever puts a
        /// process back into the queue. A newly-arrived process is
        /// always enqueued BEFORE the process being preempted goes back
        /// in, matching the worked example in the lesson: an arrival at
        /// the exact instant of preemption gets ahead of the preempted
        /// process.
        /// </summary>
        public static ScheduleResult RunRoundRobin(List<Process> processes, int quantum)
        {
            var result = new ScheduleResult();
            var byArrival = processes.OrderBy(p => p.ArrivalTime).ThenBy(p => p.Id).ToList();
            var readyQueue = new Queue<Process>();
            int time = 0;
            int nextToArrive = 0;
 
            void EnqueueArrivals(int upToTime)
            {
                while (nextToArrive < byArrival.Count && byArrival[nextToArrive].ArrivalTime <= upToTime)
                {
                    readyQueue.Enqueue(byArrival[nextToArrive]);
                    nextToArrive++;
                }
            }
 
            void AdvanceToNextArrivalIfIdle()
            {
                if (readyQueue.Count == 0 && nextToArrive < byArrival.Count)
                {
                    int nextArrival = byArrival[nextToArrive].ArrivalTime;
                    if (nextArrival > time)
                    {
                        result.Gantt.Add(new GanttSlice("IDLE", time, nextArrival));
                    }
                    time = nextArrival;
                    EnqueueArrivals(time);
                }
            }
 
            EnqueueArrivals(0);
            AdvanceToNextArrivalIfIdle();
 
            while (readyQueue.Count > 0)
            {
                var current = readyQueue.Dequeue();
                int start = time;
                int slice = Math.Min(quantum, current.RemainingTime);
                time += slice;
                current.RemainingTime -= slice;
                result.Gantt.Add(new GanttSlice(current.Id, start, time));
 
                // Arrivals up to "time" join the tail first...
                EnqueueArrivals(time);
                // ...then the process we just preempted goes in behind them.
                if (current.RemainingTime > 0)
                {
                    readyQueue.Enqueue(current);
                }
                else
                {
                    result.CompletionTime[current.Id] = time;
                }
 
                AdvanceToNextArrivalIfIdle();
            }
 
            return result;
        }
    }
 
    public static class Report
    {
        /// <summary>
        /// Turnaround Time = Completion Time - Arrival Time
        /// Waiting Time    = Turnaround Time - Burst Time
        /// These are exactly the formulas from the earlier FCFS class;
        /// they still work here because every algorithm above only
        /// needs to fill in a completion time per process.
        /// </summary>
        public static void Print(string title, List<Process> processes, ScheduleResult result)
        {
            Console.WriteLine();
            Console.WriteLine($"=== {title} ===");
 
            Console.WriteLine("Gantt chart:");
            Console.WriteLine(string.Join(" | ", result.Gantt.Select(s => $"{s.ProcessId} ({s.Start}-{s.End})")));
            Console.WriteLine();
 
            double totalWaiting = 0;
            double totalTurnaround = 0;
 
            Console.WriteLine("Process  AT  BT  CT  TAT  WT");
            foreach (var p in processes.OrderBy(p => p.Id))
            {
                int ct = result.CompletionTime[p.Id];
                int tat = ct - p.ArrivalTime;
                int wt = tat - p.BurstTime;
                totalTurnaround += tat;
                totalWaiting += wt;
                Console.WriteLine($"{p.Id,-7}  {p.ArrivalTime,2}  {p.BurstTime,2}  {ct,2}  {tat,3}  {wt,3}");
            }
 
            Console.WriteLine();
            Console.WriteLine($"Average Waiting Time = {totalWaiting / processes.Count:0.00}");
            Console.WriteLine($"Average Turnaround Time = {totalTurnaround / processes.Count:0.00}");
        }
    }
 
    public static class Program
    {
        public static void Main()
        {
            // Dataset from Problem 1 (FCFS, Task 1). Expected:
            // Average Waiting Time = 4.40, Average Turnaround Time = 8.00
            var fcfsProcesses = new List<Process>
            {
                new("P1", arrivalTime: 4, burstTime: 5),
                new("P2", arrivalTime: 6, burstTime: 4),
                new("P3", arrivalTime: 0, burstTime: 3),
                new("P4", arrivalTime: 6, burstTime: 2),
                new("P5", arrivalTime: 5, burstTime: 4),
            };
            Report.Print("FCFS", fcfsProcesses, Scheduler.RunFcfs(fcfsProcesses));
 
            // Dataset from Problem 3 (SJF, non-preemptive, Task 1). Expected:
            // Average Waiting Time = 7.00
            var sjfProcesses = new List<Process>
            {
                new("P1", arrivalTime: 0, burstTime: 6),
                new("P2", arrivalTime: 0, burstTime: 8),
                new("P3", arrivalTime: 0, burstTime: 7),
                new("P4", arrivalTime: 0, burstTime: 3),
            };
            Report.Print("SJF (non-preemptive)", sjfProcesses, Scheduler.RunSjf(sjfProcesses));
 
            // Dataset from the Priority Scheduling section's example
            // (lower number = higher priority). Expected:
            // Average Waiting Time = 8.20
            var priorityProcesses = new List<Process>
            {
                new("P1", arrivalTime: 0, burstTime: 10, priority: 3),
                new("P2", arrivalTime: 0, burstTime: 1, priority: 1),
                new("P3", arrivalTime: 0, burstTime: 2, priority: 4),
                new("P4", arrivalTime: 0, burstTime: 1, priority: 5),
                new("P5", arrivalTime: 0, burstTime: 5, priority: 2),
            };
            Report.Print("Priority (non-preemptive)", priorityProcesses, Scheduler.RunPriority(priorityProcesses));
 
            // Dataset from Problem 6 (Round Robin, quantum = 4, Task 1). Expected:
            // Average Waiting Time = 5.67, Average Turnaround Time = 15.67
            var rrProcesses = new List<Process>
            {
                new("P1", arrivalTime: 0, burstTime: 24),
                new("P2", arrivalTime: 0, burstTime: 3),
                new("P3", arrivalTime: 0, burstTime: 3),
            };
            Report.Print("Round Robin (quantum = 4)", rrProcesses, Scheduler.RunRoundRobin(rrProcesses, quantum: 4));
        }
    }
}