CPU Scheduling Algorithms — Deep Dive & Solved Numericals

CSS Optional — Paper-II, Section-A · P-II.III.II (cont.) · Scheduling-algorithm Gantt-chart numericals are the single most-repeated OS numerical type across past papers. The [Process Management] page gives the summary table; this page works every algorithm through a full worked numerical, step by step, so the method is drilled, not just memorized.

1. The General Method (applies to every algorithm below)

1. List each process with Arrival Time (AT) and Burst Time (BT) [+ Priority if relevant].
2. Draw the Gantt chart by simulating the algorithm's rule tick-by-tick (preemptive) or event-by-event (non-preemptive).
3. Read off each process's Completion Time (CT) from the chart.
4. Turnaround Time (TAT) = CT − AT.
5. Waiting Time (WT) = TAT − BT.
6. Average TAT / WT = sum ÷ number of processes.

Always show all four columns (CT, TAT, WT) even if only the average is asked for — the intermediate values carry marks, and a correct Gantt chart alone earns partial credit even with an arithmetic slip later.

2. FCFS — Worked Numerical

FCFS simply runs processes in the order they arrive, no preemption:

1. t=0: only P1 has arrived → run P1 for its full burst (0→5).
2. t=5: P1 finishes. P2 (arrived t=1) and P3 (arrived t=2) are both waiting → P2 arrived first → run P2 (5→8).
3. t=8: P2 finishes. P3 and P4 are waiting → P3 arrived first (t=2) → run P3 (8→16).
4. t=16: P3 finishes. Only P4 left → run P4 (16→22).

Gantt:  | P1(0-5) | P2(5-8) | P3(8-16) | P4(16-22) |

Avg TAT = 45/4 = 11.25 · Avg WT = 23/4 = 5.75. Notice P3's 6-unit wait and P4's 13-unit wait despite short arrival gaps — this pile-up behind long jobs is the convoy effect, FCFS's signature weakness.

3. SJF (Non-Preemptive) — Worked Numerical

Step by step:

1. t=0: only P1 has arrived → non-preemptive means once it starts it must run to completion, even though shorter jobs (P2, P3, P4) arrive later → run P1 (0→7).
2. t=7: P1 finishes. P2(rem4), P3(rem1), P4(rem4) have all arrived → pick the shortest burst → P3(1) → run P3 (7→8).
3. t=8: P3 finishes. P2(4) and P4(4) tie → break the tie by arrival order → P2 arrived first (t=1 vs t=3) → run P2 (8→12).
4. t=12: P2 finishes. Only P4 left → run P4 (12→16).

Gantt: | P1(0-7) | P3(7-8) | P2(8-12) | P4(12-16) |

Avg TAT = 37/4 = 9.25 · Avg WT = 21/4 = 5.25.

4. SRTF (Preemptive SJF) — Worked Numerical

Unlike SJF above, SRTF re-checks remaining time at every new arrival and preempts the running process if a shorter remaining-time job shows up:

t=0: only P1 ready -> runs. rem P1=8.
t=1: P2 arrives (rem4) < P1's rem(7) -> preempt, run P2.
t=2: P3 arrives (rem9); running P2 rem=3 -> still shortest, continue P2.
t=3: P4 arrives (rem5); running P2 rem=2 -> still shortest, continue P2.
t=5: P2 completes. Candidates: P1(rem7), P3(rem9), P4(rem5) -> run P4 (shortest).
t=10: P4 completes. Candidates: P1(rem7), P3(rem9) -> run P1.
t=17: P1 completes. Only P3 left (rem9) -> run P3.
t=26: P3 completes.

Gantt: | P1(0-1) | P2(1-5) | P4(5-10) | P1(10-17) | P3(17-26) |

Avg TAT = 52/4 = 13 · Avg WT = 26/4 = 6.5. Notice P1 is preempted at t=1 after just 1 unit, then has to wait until t=10 to resume — SRTF minimizes average waiting time but can badly delay long jobs (a form of starvation risk, fixable by aging just like plain Priority scheduling below).

5. Priority Scheduling (Non-Preemptive) — Worked Numerical, + Aging

All arrive at t=0 (lower number = higher priority):

Step by step (all arrive at t=0, so purely priority-ordered):

1. Rank by priority (lower number = higher priority): P2(1) > P4(2) > P1(3) > P3(4).
2. t=0: highest priority ready is P2 → run P2 (0→3).
3. t=3: P2 done. Next-highest is P4 → run P4 (3→9).
4. t=9: P4 done. Next is P1 → run P1 (9→14).
5. t=14: P1 done. Only P3 left → run P3 (14→22).

Gantt: | P2(0-3) | P4(3-9) | P1(9-14) | P3(14-22) |

Avg TAT = 48/4 = 12 · Avg WT = 26/4 = 6.5.

Aging illustration: suppose a 5th process P5 (priority 5, the lowest) also arrived at t=0. Plain priority scheduling would run it dead last (after P3), giving it a wait time of 22 — and if lower-priority processes kept arriving, P5 could starve indefinitely. Aging fixes this by incrementing a waiting process's priority (lowering its number) periodically — e.g. +1 priority level for every 3 units spent waiting: P5 would reach priority 4 by t=3, priority 3 by t=6, priority 2 by t=9, and priority 1 by t=12 — by which point it out-ranks P1, P3, and P4, guaranteeing it eventually gets scheduled. Aging is the standard textbook answer whenever a question asks "how do you prevent starvation in priority scheduling."

6. Priority Scheduling (Preemptive) — Worked Numerical

t=0: only P1 ready -> runs.
t=1: P2 arrives (priority1, better than P1's3) -> preempt, run P2.
t=2: P2 completes. P3 arrives (priority4, worse than P1's3) -> P1 resumes (better priority than P3).
t=3: P4 arrives (priority2, better than P1's3) -> preempt, run P4.
t=4: P4 completes. Candidates: P1(pri3), P3(pri4) -> P1 resumes (better priority).
t=12: P1 completes (ran its remaining 8 units). Only P3 left -> runs.
t=14: P3 completes.

Gantt: | P1(0-1) | P2(1-2) | P1(2-3) | P4(3-4) | P1(4-12) | P3(12-14) |

Avg TAT = 26/4 = 6.5 · Avg WT = 12/4 = 3.

7. Round Robin — Worked Numerical

Quantum = 2. New arrivals join the ready queue before the just-preempted process is requeued (the standard convention):

Step by step (ready queue shown after each dispatch; quantum=2):

1. t=0: Queue=[P1]. Run P1 (0→2), rem=3. During this slice P2(t=1) arrives → queue becomes [P2,P1(rem3)].
2. t=2: P3(t=2) arrives, joins before P1 is requeued → queue=[P2,P3,P1(rem3)]. Run P2 (2→4), rem=1. P4(t=3) arrives mid-slice → requeue order becomes [P3,P1(rem3),P4,P2(rem1)].
3. t=4: Run P3 (4→5) — needs only 1 unit (<quantum), finishes, no requeue. Queue=[P1(rem3),P4,P2(rem1)].
4. t=5: Run P1 for quantum (5→7), rem=1, requeue → [P4,P2(rem1),P1(rem1)].
5. t=7: Run P4 for quantum (7→9), rem=2, requeue → [P2(rem1),P1(rem1),P4(rem2)].
6. t=9: Run P2 (9→10) — needs only 1, finishes. Queue=[P1(rem1),P4(rem2)].
7. t=10: Run P1 (10→11) — finishes. Queue=[P4(rem2)].
8. t=11: Run P4 (11→13) — finishes.

Gantt: | P1(0-2) | P2(2-4) | P3(4-5) | P1(5-7) | P4(7-9) | P2(9-10) | P1(10-11) | P4(11-13) |

Avg TAT = 33/4 = 8.25 · Avg WT = 20/4 = 5. P3 (BT=1) finishes inside its very first quantum without needing to requeue — a good example of why short jobs still do reasonably well under RR despite no explicit "shortest job" preference.

8. Multilevel Queue — Worked Numerical

Two permanent queues, foreground (RR quantum=2) has absolute priority over background (FCFS) — background only runs when foreground is completely empty:

Step by step (Foreground has absolute priority; RR quantum=2 within it; Background is FCFS and only runs once Foreground is fully empty):

1. t=0: Foreground queue=[F1]. Run F1 for quantum (0→2), rem=2.
2. t=2: F2(t=2) arrives → Foreground=[F2,F1(rem2)]. Run F2 for quantum (2→4), rem=1.
3. t=4: Foreground=[F1(rem2),F2(rem1)]. Run F1 (4→6) — exactly its remaining 2 → finishes.
4. t=6: Only F2(rem1) left in Foreground → run F2 (6→7) — finishes. Foreground now empty.
5. t=7: Switch to Background (FCFS by arrival): B1(t=0) before B2(t=1) → run B1 to completion (7→13).
6. t=13: Run B2 to completion (13→15).

Gantt: | F1(0-2) | F2(2-4) | F1(4-6) | F2(6-7) | B1(7-13) | B2(13-15) |

Foreground processes fully drain first (F1 and F2 trade RR turns until both finish at t=7); only then does the background FCFS queue get any CPU time at all.

This is exactly the starvation risk to name in an exam answer: if new foreground jobs kept arriving, B1/B2 could wait indefinitely — a rigid Multilevel Queue has no aging mechanism between queues (that's precisely what MLFQ below fixes).

9. Multilevel Feedback Queue (MLFQ) — Worked Numerical

Three queues — Q0 (RR, quantum=2, highest priority), Q1 (RR, quantum=4), Q2 (FCFS, run-to-completion, lowest priority). A process that doesn't finish within its quantum is demoted one level; higher queues always preempt lower ones; new arrivals always enter at Q0:

t=0: Q0=[P1]. Run P1 for quantum 2 -> rem7, doesn't finish -> demote to Q1.
t=2: P2 (arrived t=1) enters Q0. Run P2 for quantum 2 -> rem2, doesn't finish -> demote to Q1.
t=4: Q0 empty, Q1=[P1(rem7), P2(rem2)]. Run P1 for quantum 4 -> rem3, still doesn't finish -> demote to Q2.
t=8: Q1=[P2(rem2)]. Run P2 for quantum 4 -> needs only 2, completes at t=10.
t=10: Q0, Q1 empty. Q2=[P1(rem3)] (FCFS, runs to completion) -> completes at t=13.

Gantt: | P1(0-2) | P2(2-4) | P1(4-8) | P2(8-10) | P1(10-13) |

Avg TAT = 22/2 = 11 · Avg WT = 9/2 = 4.5. P1 is demoted twice (Q0→Q1→Q2) because it keeps needing more CPU than its quantum allows — exactly the "CPU-bound processes sink to lower queues, I/O-bound/short processes stay near the top" behaviour that makes MLFQ self-tuning without knowing burst times in advance.

---

🎯 CSS Exam Angle

When a numerical doesn't name the algorithm explicitly and just gives a scenario, look for these signal words: "quantum" → Round Robin; "lowest burst time first" → SJF; "can be interrupted by a shorter job" → SRTF; "promoted/demoted between queues" → MLFQ; "foreground/background" → Multilevel Queue. Always state your tie-breaking rule explicitly (usually arrival order) before the Gantt chart, since two students can get different but equally valid charts if the question's tie-break isn't specified.

📌 Past CSS Paper Frequency (Scheduling Numericals Specifically)

See [Process Management] → Worked Numericals for the exact past-paper versions of these; the numericals on this page are additional practice covering every algorithm the summary table lists, since scheduling questions can name any of them.

⚠️ MCQ Traps

• SJF (non-preemptive) still must run whichever process is already executing to completion — a shorter job arriving mid-burst does NOT preempt it; only SRTF preempts.
• RR's tie-break for "who joins the queue first" (new arrival vs the just-preempted process) changes the entire chart — always state which convention you're using.
• In MLFQ, a process is demoted only for using its FULL quantum without finishing — a process that voluntarily blocks for I/O before its quantum expires is NOT demoted in the standard scheme (some variants even promote it), a frequently mis-answered nuance.
• Multilevel Queue has no promotion/demotion at all — a process is permanently assigned to its queue for its whole lifetime; only MLFQ allows movement between queues. Confusing the two costs easy marks.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2017 · Paper-II · Q4(c) · 6 marks

Q. Three processes P1 (burst 24), P2 (7) and P3 (10) arrive together. Find the average waiting time and average turnaround time with Round-Robin scheduling, time quantum 4.

Ans.

• Gantt chart:

| P1 | P2 | P3 | P1 | P2 | P3 | P1 | P3 | P1 | P1 | P1 |
0    4    8    12   16   19   23   27   29   33   37   41

• Completion times: P2 = 19, P3 = 29, P1 = 41.

• Average turnaround time = (41 + 19 + 29) / 3 = 29.67.
• Average waiting time = (17 + 12 + 19) / 3 = 16.

2022 · Paper-II · Q2(a) · 10 marks

Q. Processes are scheduled by preemptive priority scheduling with round robin among equal priorities (higher number = higher priority; quantum 10; preempted process goes to the end of its queue; an idle task has priority 0). P1 (priority 40, burst 20, arrival 0), P2 (30, 25, 25), P3 (30, 25, 30), P4 (35, 15, 60), P5 (5, 10, 100), P6 (10, 10, 105). Show the Gantt chart and the turnaround and waiting time of each process.

Ans.

• Gantt chart:

| P1 | idle | P2 | P3 | P2 | P3 | P4 | P2 | P3 | idle | P5 | P6 | P5 |
0    20     25   35   45   55   60   75   80   90     100   105  115  120

• Reasoning: P1 runs alone until 20. The CPU idles until P2 arrives at 25. P2 and P3 (equal priority) alternate in 10-unit slices. P4 (priority 35) arrives at 60 and preempts P3, and it runs to completion at 75. P2 and P3 finish, and the CPU idles until 100. P5 starts, but is preempted at 105 by P6 (priority 10), which finishes at 115, and then P5 completes.

• Averages: turnaround = 180 / 6 = 30, waiting = 75 / 6 = 12.5.

MCQs

2025 P-II · Q12. Which module gives control of the CPU to the process selected by the short-term scheduler?

• (A) Dispatcher ✅
• (B) Interrupt
• (C) Scheduler
• (D) None of these
• Answer: (A) Dispatcher.
• Why: the scheduler only chooses the process. The dispatcher does the context switch, switches to user mode and jumps to the chosen process. An interrupt is a signal, not a module.