These are the notes for CS Fundamentals for Placements, episode 21. You now have many processes and threads ready to run, and a CPU core runs only one at a time. Who runs next? Today you learn preemptive vs non-preemptive scheduling, the scheduling criteria (CPU utilisation, throughput, turnaround time, waiting time, response time), the times every numerical uses (arrival time, burst time, completion time, TAT = CT − AT, WT = TAT − BT), the Gantt chart, First Come First Served (FCFS), the convoy effect, CPU idle time, and average-time numericals, checked by a small Python simulator. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.
All program outputs below are real: the Python code was run with Python 3.13 on 30 October 2026, exactly as in the SyntaxPilot compiler.
Refresher from episode 17: a process alternates between CPU bursts (computing) and I/O bursts (waiting for a disk, the network or the user). Ready processes wait in the ready queue; the short-term scheduler picks one and the dispatcher gives it the CPU.
The six problems
| Problem | What it teaches |
|---|---|
| Many ready, one CPU | CPU scheduler, scheduling algorithm, burst time |
| Can we take the CPU back? | Non-preemptive vs preemptive, the four decision points, timer interrupt |
| Is a schedule good? | Five criteria; AT, BT, CT, TAT, WT, RT and their formulas |
| The simplest rule | FCFS, Gantt chart, a full numerical with CPU idle time |
| Check answers in code | A simulator; the idle-time bug; averages, utilisation, throughput |
| One slow job in front | The convoy effect; FCFS pros and cons |
Problem 1: many ready, one CPU
Real-life example: one railway ticket window.
| At the station | In the OS |
|---|---|
| A line of passengers, all ready | The ready queue: processes ready to run, waiting only for the CPU |
| One window serving one person at a time | A CPU core runs one process (thread) at a time |
| The clerk calls "Next!" | The CPU scheduler (short-term scheduler) picks the next process; the dispatcher starts it |
The rule the scheduler uses is a scheduling algorithm. In numericals, each process comes with its burst time (BT): how much CPU time it needs (its next CPU burst), in milliseconds or just "time units". While one process waits for I/O, another can use the CPU; that is the whole point of scheduling.
Problem 2: can we take the CPU back?
Real-life example: a barber vs a hospital doctor. A barber never leaves a haircut half done: once you're in the chair, you stay until you're finished. A hospital doctor pauses your check-up when an emergency arrives.
| Non-preemptive scheduling | Preemptive scheduling | |
|---|---|---|
| Meaning | Once a process gets the CPU it keeps it until it finishes or blocks (waits for I/O) | The OS can take the CPU away in the middle of a burst and put the process back in the ready queue |
| Real life | Barber | Doctor with an emergency |
| Examples | FCFS, SJF, non-preemptive priority | SRTF, preemptive priority, Round Robin (episodes 22-23) |
| Good for | Simple batch jobs, low overhead | Interactive systems, fairness, urgent work |
| Cost | A long job can hog the CPU | More context switches; needs care with shared data |
To preempt means to take over before someone else. Preemption is driven by the timer interrupt: a hardware alarm the OS sets so that it gets control back regularly, and no process can keep the CPU forever.
When does the scheduler decide?
| # | Event | Non-preemptive decides? | Preemptive decides? |
|---|---|---|---|
| 1 | Running → waiting (asks for I/O, calls wait) |
Yes (CPU is free) | Yes |
| 2 | Running → terminated (finished) | Yes (CPU is free) | Yes |
| 3 | Running → ready (timer interrupt) | No | Yes |
| 4 | Waiting → ready (I/O finished; maybe more urgent) | No | Yes |
If scheduling happens only at 1 and 2, the scheduler is non-preemptive (also called cooperative); if also at 3 and 4, it is preemptive.
Problem 3: is a schedule good? (criteria)
| Criterion | Meaning | We want it |
|---|---|---|
| CPU utilisation | Percentage of time the CPU is busy | High |
| Throughput | Number of processes completed per unit of time | High |
| Turnaround time (TAT) | Time from arrival to completion | Low |
| Waiting time (WT) | Total time spent waiting in the ready queue | Low |
| Response time (RT) | Time from arrival until the process first gets the CPU | Low (matters for interactive apps) |
A scheduling algorithm affects only the time spent waiting in the ready queue, not the time a process needs on the CPU or for I/O. That's why waiting time is the favourite comparison number.
The times, from a hospital visit
Real-life example. You arrive at 10:00 and take a token. The doctor needs 15 minutes with you. You leave at 10:45.
| Hospital | Scheduling term | Value |
|---|---|---|
| You arrive at 10:00 | Arrival time (AT): when the process enters the ready queue | 10:00 |
| Doctor needs 15 min | Burst time (BT): CPU time needed | 15 min |
| You leave at 10:45 | Completion time (CT): when the process finishes | 10:45 |
| 45 min in the hospital | Turnaround time = CT − AT | 45 min |
| 30 min not with the doctor | Waiting time = TAT − BT | 30 min |
| First saw the doctor at 10:30 | Response time = first start − AT | 30 min |
The formulas
- TAT = CT − AT (turnaround = completion − arrival)
- WT = TAT − BT (waiting = turnaround − burst) (for a process that does no I/O in between)
- RT = time it first gets the CPU − AT
- Average TAT / WT / RT = sum over all processes ÷ number of processes
- CPU utilisation = busy time ÷ total time (× 100 for a percentage)
- Throughput = number of processes completed ÷ total time
(Textbooks usually measure "total time" from 0 to the last completion. If a question's first arrival is later than 0, check whether it wants the length from the first arrival instead.)
Problem 4: the simplest rule (FCFS)
First Come, First Served (FCFS), also called FIFO: the process that arrived first runs first, like the ticket window. It is non-preemptive: each process runs its whole burst. Ties (same arrival time) go in the order given, usually by process number.
Worked numerical
| Process | AT | BT |
|---|---|---|
| P1 | 0 | 4 |
| P2 | 1 | 3 |
| P3 | 2 | 1 |
| P4 | 10 | 2 |
Step 1: draw the Gantt chart. A Gantt chart is a time bar showing which process had the CPU and when.
| P1 | P2 | P3 | idle | P4 |
0 4 7 8 10 12
P1 arrived first: 0-4. P2: 4-7. P3: 7-8. P4 only arrives at 10, so from 8 to 10 nobody is ready and the CPU is idle (CPU idle time: time when the ready queue is empty). P4: 10-12.
Step 2: read CT from the chart, then apply the formulas.
| Process | AT | BT | CT | TAT = CT − AT | WT = TAT − BT | RT |
|---|---|---|---|---|---|---|
| P1 | 0 | 4 | 4 | 4 | 0 | 0 |
| P2 | 1 | 3 | 7 | 6 | 3 | 3 |
| P3 | 2 | 1 | 8 | 6 | 5 | 5 |
| P4 | 10 | 2 | 12 | 2 | 0 | 0 |
| Average | 18/4 = 4.5 | 8/4 = 2 | 2 |
- CPU idle = 2 units (8 to 10); utilisation = 10/12 = 83.3%
- Throughput = 4 processes / 12 units = 0.33 per unit
- In FCFS a process never stops once started, so RT = WT for every process.
Problem 5: check answers in code
The obvious simulator (fails)
procs = [("P1", 0, 4), ("P2", 1, 3), ("P3", 2, 1), ("P4", 10, 2)]
time = 0
print("P AT BT CT TAT WT")
for name, at, bt in procs: # FCFS: in order of arrival
time = time + bt # finish = last finish + burst
ct = time
tat = ct - at
wt = tat - bt
print(f"{name} {at:2} {bt:2} {ct:2} {tat:3} {wt:2}")
Output:
P AT BT CT TAT WT
P1 0 4 4 4 0
P2 1 3 7 6 3
P3 2 1 8 6 5
P4 10 2 10 0 -2
A negative waiting time is impossible. Why: the clock was at 8 when P3 finished, so the code started P4 at 8, but P4 only arrives at 10. It ignored CPU idle time. (f"{at:2}" is a Python f-string that prints at right-aligned in 2 characters.)
The fixed simulator
procs = [("P1", 0, 4), ("P2", 1, 3), ("P3", 2, 1), ("P4", 10, 2)]
procs.sort(key=lambda p: p[1]) # FCFS: earliest arrival first
time, idle, gantt = 0, 0, ""
sum_tat = sum_wt = 0
print("P AT BT CT TAT WT")
for name, at, bt in procs:
if time < at: # nobody is ready: CPU idle
idle += at - time
gantt += f"| idle {time}-{at} "
time = at
start = time
time += bt # runs to the end: no preemption
ct, tat = time, time - at
wt = tat - bt
sum_tat += tat
sum_wt += wt
gantt += f"| {name} {start}-{ct} "
print(f"{name} {at:2} {bt:2} {ct:2} {tat:3} {wt:2}")
n = len(procs)
print(gantt + "|")
print(f"avg TAT = {sum_tat / n}, avg WT = {sum_wt / n}")
print(f"CPU idle = {idle}, utilisation = {(time - idle) / time:.1%}")
print(f"throughput = {n}/{time} = {n / time:.2f} processes per unit")
Output:
P AT BT CT TAT WT
P1 0 4 4 4 0
P2 1 3 7 6 3
P3 2 1 8 6 5
P4 10 2 12 2 0
| P1 0-4 | P2 4-7 | P3 7-8 | idle 8-10 | P4 10-12 |
avg TAT = 4.5, avg WT = 2.0
CPU idle = 2, utilisation = 83.3%
throughput = 4/12 = 0.33 processes per unit
Exactly the hand solution. procs.sort(key=lambda p: p[1]) sorts by arrival time; Python's sort is stable (equal keys keep their original order), which matches FCFS tie-breaking. :.1% formats a fraction as a percentage with one decimal.
Problem 6: one slow job in front (the convoy effect)
Three processes all arrive at time 0: P1 needs 24, P2 and P3 need 3 each. Same simulator, two orders:
P1 first: procs = [("P1", 0, 24), ("P2", 0, 3), ("P3", 0, 3)]
P AT BT CT TAT WT
P1 0 24 24 24 0
P2 0 3 27 27 24
P3 0 3 30 30 27
| P1 0-24 | P2 24-27 | P3 27-30 |
avg TAT = 27.0, avg WT = 17.0
CPU idle = 0, utilisation = 100.0%
throughput = 3/30 = 0.10 processes per unit
Short jobs first: procs = [("P2", 0, 3), ("P3", 0, 3), ("P1", 0, 24)]
P AT BT CT TAT WT
P2 0 3 3 3 0
P3 0 3 6 6 3
P1 0 24 30 30 6
| P2 0-3 | P3 3-6 | P1 6-30 |
avg TAT = 13.0, avg WT = 3.0
CPU idle = 0, utilisation = 100.0%
throughput = 3/30 = 0.10 processes per unit
Same work, same CPU, same utilisation and throughput, but average waiting time 17 vs 3, just from the order.
Real-life example: the truck on the ghat road. A slow truck leads on a single-lane hill road with no overtaking; fast cars behind it crawl at truck speed. The convoy effect is when short processes pile up behind one long process in FCFS, so the average waiting time shoots up. It also wastes devices: while I/O-bound processes (short CPU bursts) wait behind one CPU-bound process (long CPU bursts), the disk and network sit idle; then they all rush to I/O while the CPU sits idle.
FCFS: pros and cons
| Good | Bad |
|---|---|
| Simplest: one FIFO queue | Convoy effect |
| Fair in arrival order | High, order-dependent average waiting time |
| No starvation: every process eventually runs | Non-preemptive: a long job can freeze interactive apps |
| Almost no scheduling overhead | Rarely used alone for general-purpose CPU scheduling; it appears inside other schemes (e.g. FIFO order within one priority level) |
Starvation means a process waits forever because others keep getting chosen. FCFS can't starve anyone; next episode's SJF can.
The whole chain
| Step | Idea | Its limit (the next problem) |
|---|---|---|
| Ready queue + scheduler | Someone picks who runs | Can it take the CPU back? |
| Preemptive vs non-preemptive | When the scheduler may decide | How to judge a rule? |
| Five criteria, formulas | Utilisation, throughput, TAT, WT, RT | The simplest rule? |
| FCFS + Gantt chart | Arrival order, read the times | Checking by hand is slow |
| Simulator with idle time | Clock jumps to the next arrival | Order hurts: convoy effect |
| Convoy effect | Short jobs stuck behind a long one | → let short jobs go first (SJF, next episode) |
Common mistakes
| Mistake | Real result | Why | Fix |
|---|---|---|---|
| Starting P4 at 8 though it arrives at 10 | P4 10 2 10 0 -2 |
Ignored CPU idle time | start = max(clock, arrival) |
| TAT = CT − BT | wrong turnaround | formula mix-up | TAT = CT − AT, WT = TAT − BT |
| Averaging over 3 processes when there are 4 | wrong average | skipped a zero-wait process | divide by all processes |
| Utilisation = busy ÷ sum of bursts | always 100% | idle gaps forgotten | busy ÷ total time |
| Ignoring tie order at the same arrival time | different Gantt chart | FCFS ties go in the given order | keep the order (stable sort) |
| Treating FCFS as preemptive when a new process arrives | wrong chart | FCFS never preempts | run each burst to the end |
Mini project: add response time to the simulator
procs = [("P1", 0, 3), ("P2", 1, 6), ("P3", 4, 4), ("P4", 6, 2)]
procs.sort(key=lambda p: p[1])
time = 0
print("P AT BT ST CT TAT WT RT")
for name, at, bt in procs:
time = max(time, at) # idle until it arrives
st = time # start: first time on the CPU
time += bt
ct = time
tat, wt, rt = ct - at, ct - at - bt, st - at
print(f"{name} {at:2} {bt:2} {st:2} {ct:2} {tat:3} {wt:2} {rt:2}")
Output:
P AT BT ST CT TAT WT RT
P1 0 3 0 3 3 0 0
P2 1 6 3 9 8 2 2
P3 4 4 9 13 9 5 5
P4 6 2 13 15 9 7 7
max(time, at) is the one-line idle fix. In FCFS the RT column always equals WT; in preemptive algorithms (next episodes) they differ, so keep this column. Extension: read the process list from input, and print the Gantt chart.
Practice
1. FCFS: P1 (AT 0, BT 3), P2 (1, 6), P3 (4, 4), P4 (6, 2). Find the average TAT and WT.
Solution
Gantt: | P1 0-3 | P2 3-9 | P3 9-13 | P4 13-15 |
| P | AT | BT | CT | TAT | WT |
|---|---|---|---|---|---|
| P1 | 0 | 3 | 3 | 3 | 0 |
| P2 | 1 | 6 | 9 | 8 | 2 |
| P3 | 4 | 4 | 13 | 9 | 5 |
| P4 | 6 | 2 | 15 | 9 | 7 |
Average TAT = 29/4 = 7.25, average WT = 14/4 = 3.5 (the simulator prints avg TAT = 7.25, avg WT = 3.5).
2. FCFS with idle time: P1 (AT 2, BT 3), P2 (AT 9, BT 4). What is the CPU utilisation from time 0?
Solution
Gantt: | idle 0-2 | P1 2-5 | idle 5-9 | P2 9-13 |. Busy = 7, total = 13, idle = 6. Utilisation = 7/13 = 53.8%. Both processes wait 0. (Measured from the first arrival at 2, it would be 7/11 = 63.6%; read the question.)
3. Four jobs arrive together with bursts A = 8, B = 4, C = 2, D = 1. Which FCFS order gives the highest and the lowest average waiting time?
Solution
Try all 24 orders:
from itertools import permutations
bursts = {"A": 8, "B": 4, "C": 2, "D": 1} # all arrive at time 0
def avg_wt(order):
t = total = 0
for p in order:
total += t # waits until everyone before it is done
t += bursts[p]
return total / len(order)
best = min(permutations(bursts), key=avg_wt)
worst = max(permutations(bursts), key=avg_wt)
print("best ", "".join(best), avg_wt(best))
print("worst", "".join(worst), avg_wt(worst))
Output:
best DCBA 2.75
worst ABCD 8.5
Longest first is worst (waits 0, 8, 12, 14), shortest first is best (0, 1, 3, 7). That observation is the next algorithm: SJF.
4. In FCFS, can the response time of a process differ from its waiting time?
Solution
No (for processes with a single CPU burst). FCFS is non-preemptive: once a process starts, it runs to the end, so the only waiting is before its first run, and RT = WT.
5. Five processes finish by time 40 and the CPU was idle for 6 units. Find throughput and utilisation.
Solution
Throughput = 5/40 = 0.125 processes per unit. Utilisation = (40 − 6)/40 = 85%.
6. Why is FCFS bad for an interactive system like a phone?
Solution
It is non-preemptive: if a long background job gets the CPU, the touch-screen handler waits until that job's burst ends, so the phone feels frozen (huge response time). Interactive systems use preemptive schedulers.
Quick quiz
| Process | AT | BT |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 2 | 3 |
| P3 | 4 | 1 |
FCFS: what is the average waiting time? A. 2 B. 2.33 C. 3 D. 6.33
Answer
B. 2.33. Gantt: P1 0-5, P2 5-8, P3 8-9. TAT = 5, 6, 5; WT = 0, 3, 4; average = 7/3 = 2.33. (6.33 would be the average if you forgot to subtract arrival times.)
Interview questions
- What is CPU scheduling? Which scheduler does it? Choosing which ready process gets the CPU next; the short-term (CPU) scheduler, with the dispatcher switching to it.
- Preemptive vs non-preemptive? Preemptive can take the CPU from a running process (timer interrupt, a more urgent arrival); non-preemptive waits until it finishes or blocks.
- List the scheduling criteria. CPU utilisation and throughput (maximise); turnaround, waiting and response time (minimise).
- Turnaround vs waiting vs response time? TAT = CT − AT; WT = TAT − BT; RT = first run − AT.
- What is a Gantt chart? A timeline of which process ran when; used to read completion times.
- Explain FCFS. Is it preemptive? Serve in arrival order; non-preemptive.
- What is the convoy effect? Short processes stuck behind a long one in FCFS, raising average waiting time and leaving devices idle.
- Can FCFS cause starvation? No: every process eventually reaches the front.
- When is the CPU idle in a schedule? When no process is in the ready queue; the clock jumps to the next arrival.
- Why do schedulers mostly try to reduce waiting time? The algorithm only changes time spent in the ready queue; burst and I/O times are fixed.
Glossary
| Term | Meaning in plain words | Example |
|---|---|---|
| CPU scheduling | Choosing which ready process runs next | who gets the window |
| CPU (short-term) scheduler | OS part that picks the next process from the ready queue | "Next!" |
| Dispatcher | Gives the CPU to the chosen process (context switch, jump to its code) | episode 17 |
| Scheduling algorithm | The rule the scheduler uses | FCFS |
| Ready queue | Processes ready to run, waiting for the CPU | the passenger line |
| CPU burst / I/O burst | A stretch of computing / of waiting for I/O | compute, then read a file |
| Burst time (BT) | CPU time a process needs | BT = 4 |
| Arrival time (AT) | When a process enters the ready queue | AT = 10 |
| Completion time (CT) | When a process finishes | CT = 12 |
| Turnaround time (TAT) | CT − AT: total time in the system | 45 min at the hospital |
| Waiting time (WT) | TAT − BT: time spent in the ready queue | 30 min waiting |
| Response time (RT) | First time on the CPU − AT | first saw the doctor |
| CPU utilisation | Busy time ÷ total time | 83.3% |
| Throughput | Processes completed ÷ total time | 0.33 per unit |
| Non-preemptive (cooperative) scheduling | A running process keeps the CPU until it finishes or blocks | barber |
| Preemptive scheduling | The OS can take the CPU away mid-burst | doctor and emergency |
| Preempt | Take over before someone else | — |
| Timer interrupt | Hardware alarm that hands control back to the OS regularly | enables preemption |
| Gantt chart | Time bar of who ran when | | P1 0-4 | P2 4-7 | |
| CPU idle time | Time when no process is ready | 8 to 10 |
| FCFS (First Come First Served) | Run processes in arrival order, non-preemptively | ticket window |
| FIFO | First in, first out | a queue |
| Convoy effect | Short processes stuck behind a long one | truck on a ghat road |
| CPU-bound process | Mostly long CPU bursts | video encoding |
| I/O-bound process | Mostly short CPU bursts and much I/O | a text editor |
| Starvation | A process waits forever while others keep running | not in FCFS |
| Stable sort | Sorting that keeps equal items in their original order | Python sort |
| Average time | Sum over all processes ÷ number of processes | 18/4 = 4.5 |
Summary
- The CPU scheduler picks the next process from the ready queue; non-preemptive schedulers wait for the CPU to be free, preemptive ones can take it back (timer interrupt, urgent arrival).
- Judge schedules by CPU utilisation and throughput (high) and turnaround, waiting and response time (low).
- TAT = CT − AT, WT = TAT − BT, RT = first run − AT; averages divide by all processes.
- FCFS runs processes in arrival order, non-preemptively; always draw the Gantt chart first, and remember idle gaps when nobody has arrived.
- One long job in front causes the convoy effect: average WT 17 vs 3 for the same jobs in a different order.
Next episode: CPU scheduling 2: SJF, SRTF and priority scheduling, starvation and aging, with numericals.