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 seeHow oftenSection
๐Ÿ”ด "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 optimaloftenยง2

1Metrics & the two formulas ๐Ÿ”ด

MetricMeaningGoal
CPU utilizationhow busy the CPU ismaximize
Throughputprocesses finished per time unitmaximize
Turnaround timefinish โˆ’ arrival (total time in the system)minimize
Waiting timetotal time spent in the ready queueminimize
Response timetime to the first responseminimize
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 ๐Ÿ”ด

AlgorithmRulePreemptive?Starvation?
FCFS (First Come First Served)run in arrival order (FIFO)NoNo (but convoy effect)
SJF (Shortest Job First)run the shortest burst nextNoYes
SRTF (Shortest Remaining Time First)SJF, but a shorter new arrival preemptsYesYes
Priorityrun the highest priority (smallest number) nextNo (here)Yes (fix: aging)
Round Robin (RR)each process runs one time quantum, then goes to the queue tailYesNo
๐ŸŽฏ 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

  1. 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).
  2. For non-preemptive (FCFS/SJF/Priority): once a process starts, it runs to the end. Re-decide only when it finishes.
  3. For SRTF: re-decide at every arrival โ€” if a newly arrived job has less remaining time, switch to it.
  4. 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.
  5. Write each process's completion time from the chart.
  6. 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.