CPU Scheduling โ Easy Exam Guide Unit u08. Almost every exam asks you to draw a Gantt chart and compute the average waiting time (~3 pts). This is mechanical once you know the steps. ๐ด = comes a lot.
Written in simple (B1) English. Read it from top to bottom before the exam.
0How "scheduling" comes in the exam
There is almost always one scheduling task: you get a table of processes (arrival time, CPU burst, sometimes priority) and you must draw the Gantt chart and compute the average waiting time (and sometimes turnaround). It is worth ~3 points and is pure method โ no guessing.
| The question you will see | How often | Section |
|---|---|---|
| ๐ด "Draw the Gantt chart for SRTF / Round Robin / Priority and give the average waiting time" | almost every exam | ยง3 |
| ๐ด True/false: which algorithms are preemptive, RR quantum effects, SJF is optimal | often | ยง2 |
1Metrics & the two formulas ๐ด
| Metric | Meaning | Goal |
|---|---|---|
| CPU utilization | how busy the CPU is | maximize |
| Throughput | processes finished per time unit | maximize |
| Turnaround time | finish โ arrival (total time in the system) | minimize |
| Waiting time | total time spent in the ready queue | minimize |
| Response time | time to the first response | minimize |
The only two formulas you need:
turnaround = completion_time โ arrival_time waiting = turnaround โ burst (= total time waiting in the queue) average = (sum over all processes) / (number of processes)
โ The #1 mistake
For preemptive algorithms (SRTF, RR) a process runs in several pieces. Its waiting time is the sum of every gap it spends in the queue โ not just the first wait. The safe way: always use waiting = turnaround โ burst.2The five algorithms ๐ด
| Algorithm | Rule | Preemptive? | Starvation? |
|---|---|---|---|
| FCFS (First Come First Served) | run in arrival order (FIFO) | No | No (but convoy effect) |
| SJF (Shortest Job First) | run the shortest burst next | No | Yes |
| SRTF (Shortest Remaining Time First) | SJF, but a shorter new arrival preempts | Yes | Yes |
| Priority | run the highest priority (smallest number) next | No (here) | Yes (fix: aging) |
| Round Robin (RR) | each process runs one time quantum, then goes to the queue tail | Yes | No |
- Convoy effect: in FCFS, short jobs stuck behind a long job wait a long time for nothing. SJF fixes it (shortest first).
- SJF is optimal for minimizing average waiting time โ but it needs to know burst lengths in advance (estimated with an exponential average).
- RR quantum: very large quantum โ behaves like FCFS; very small quantum โ too many context switches (overhead). Ties usually broken by FCFS.
๐ฏ In the exam โ MCQ (2025-01-28 RR, 2023-02-17 preemption)
Remember: non-preemptive = FCFS, SJF, Priority; preemptive = SRTF, RR. A bigger RR quantum means fewer context switches and more FCFS-like behavior. RR is not waiting-time optimal (SJF is).3How to draw a Gantt chart & compute waiting ๐ด the ~3-point task
- Make a timeline starting at t=0. At each decision point, pick the next process by the algorithm's rule (among the ones that have already arrived).
- For non-preemptive (FCFS/SJF/Priority): once a process starts, it runs to the end. Re-decide only when it finishes.
- For SRTF: re-decide at every arrival โ if a newly arrived job has less remaining time, switch to it.
- For RR: run the head of the queue for
min(quantum, remaining); if work remains, send it to the tail. A job that arrives during a quantum joins the queue before the just-preempted job re-enters. - Write each process's completion time from the chart.
- For each: turnaround = completion โ arrival; waiting = turnaround โ burst. Average the waiting times.
โถ SRTF example (like 2025-09-17 Ex11)
P1 arr 0 burst 15 | P2 arr 0 burst 13 | P3 arr 3 burst 12 | P4 arr 3 burst 11 | P5 arr 4 burst 6 Gantt: P2[0-4] P5[4-10] P2[10-19] P4[19-30] P3[30-42] P1[42-57] (P2 starts; at t=4 P5 has the least remaining (6) โ preempts; P5 done at 10; P2 resumes โฆ) completion: P1=57 P2=19 P3=42 P4=30 P5=10 waiting = turnaround โ burst: P1=57-0-15=42 P2=19-0-13=6 P3=42-3-12=27 P4=30-3-11=16 P5=10-4-6=0 average waiting = (42+6+27+16+0)/5 = 18.2
4One-page trap sheet
- turnaround = completion โ arrival. waiting = turnaround โ burst. average = sum / n.
- For SRTF/RR a process runs in pieces โ use waiting = turnaround โ burst (sums all gaps).
- Non-preemptive: FCFS, SJF, Priority. Preemptive: SRTF, RR.
- FCFS โ convoy effect. SJF โ optimal average waiting but can starve. SRTF โ preemptive SJF.
- Priority: smaller number = higher priority; can starve; fix with aging.
- RR: big quantum โ like FCFS; small quantum โ too many context switches. A job arriving during a quantum enters the queue before the preempted job.