Scheduling: Worked Examples

Worked example 1: FCFS, SJF, RR

Three processes arrive at time 0 with CPU bursts: P1 = 24, P2 = 3, P3 = 3.

FCFS (arrival order P1, P2, P3):

Process	Start	End	Turnaround	Waiting
P1	0	24	24	0
P2	24	27	27	24
P3	27	30	30	27

• Average turnaround: $(24+27+30)/3 = 27$ ms.
• Average waiting: $(0+24+27)/3 = 17$ ms.

SJF (non-preemptive):

Shortest job first: P2(3), P3(3), P1(24).

Process	Start	End	Turnaround	Waiting
P2	0	3	3	0
P3	3	6	6	3
P1	6	30	30	6

• Average turnaround: $(3+6+30)/3 = 13$ ms.
• Average waiting: $(0+3+6)/3 = 3$ ms.

RR with $q = 4$:

Time	Queue (front)	Action
0–3	P1,P2,P3 → P2 runs 3 ms, finishes
3–7	P3,P1 → P3 runs 3 ms, finishes
7–11	P1 → P1 runs 4 ms, remaining 20
11–15	P1(20) → runs 4 ms, remaining 16
…	continues for 5 more quanta

• Turnaround: P2=3, P3=7, P1=30 → average = 13.3 ms.
• Waiting: P2=0, P3=3, P1=6 → average = 3 ms.

In this case, RR performs comparably to SJF for waiting time (because the short jobs never wait behind the long one for more than one quantum), but slightly worse turnaround for the long job (which is interrupted).

Worked example 2: CFS (2024 Paper 2 Q3)

Five CPU-bound processes arrive simultaneously: CPU demands of 10, 20, 30, 40, 50 ms. Target latency = 60 ms, minimum granularity = 2 ms.

Step 1: All 5 processes have weight 1024 (nice 0). Target latency 60 ms → each gets 12 ms.

• Round 1 (12 ms each):

  • P1: 10 ms used → finishes (2 ms unused, redistributed)
  • P2: 12/20 ms done → 8 ms remaining
  • P3: 12/30 ms done → 18 ms remaining
  • P4: 12/40 ms done → 28 ms remaining
  • P5: 12/50 ms done → 38 ms remaining

• Round 2 (4 runnable, 60/4 = 15 ms each):

  • P2: 8 ms used → finishes (7 ms unused)
  • P3: 15/18 ms done → 3 ms remaining
  • P4: 15/28 ms done → 13 ms remaining
  • P5: 15/38 ms done → 23 ms remaining

• Round 3 (3 runnable, 60/3 = 20 ms each):

  • P3: 3 ms used → finishes (17 ms unused)
  • P4: 13 ms used → finishes (7 ms unused)
  • P5: 20/23 ms done → 3 ms remaining

• Round 4: P5 uses 3 ms → all complete.

Total context switches: 4 (start) + 3 (end of round 1) + 2 (end round 2) + 2 (end round 3) = 11? Actually, more carefully: P1 starts, finishes within quantum (auto-next). The number of context switches is the number of process-to-process transitions, which is total_processes - 1 + number_of_preemptions. Here all run to quantum expiry except final quanta, so there are many switches.

Comparison: For batch workloads, larger quantum (fewer switches) is preferable — higher throughput. For interactive workloads, smaller quantum (more switches, better response time) — CFS balances this with its proportional-share fairness.

Key Tripos technique

When a question asks for a schedule under a given algorithm, draw a Gantt chart:

P2 | P3 | P1   | P1   | P1   | P1   |...
0    3    6    10    14    18    22

Then compute turnaround and waiting times from the chart. Presenting the answer as a table is clearer than narrative text. Always label the time axis. In CFS questions, show the vruntime at each scheduling decision — it demonstrates you understand the key mechanism.

---

Past Paper Questions

2024 Paper 2 Question 3: Five CPU-bound processes (10, 20, 30, 40, 50 ms). Give schedules under RR (q=5, q=20) and CFS (target latency=60 and 20 ms, granularity=2 and 5 ms). [10 marks]