CPU scheduling
How the OS decides who runs next, and why that choice changes both average waiting time and fairness.
There is always more work than CPU. The scheduler picks one ready process at a time, and that choice decides who waits. Different goals — throughput, latency, fairness — lead to different algorithms.
A long job arrives first. Watch how everything behind it waits.
| Process | Arrival | Burst | State | Used |
|---|---|---|---|---|
| P1 | 0 | 6 | waiting | — |
| P2 | 1 | 4 | waiting | — |
| P3 | 2 | 2 | waiting | — |
| P4 | 3 | 1 | waiting | — |
- P1
P1 arrives with a burst of 6ms
- Avg waiting time
- 0
- Avg turnaround time
- 0
- Total time
- 0
| Algorithm | Avg waiting time | Avg turnaround time | Total time |
|---|---|---|---|
| First-Come, First-Served | 5.5 | 8.75 | 13 |
| Shortest Job First | 4 | 7.25 | 13 |
| Round-Robin | 5.75 | 9 | 13 |
Waiting time is how long a process sat ready without running. Turnaround time is from arrival to completion. These two numbers are what scheduling algorithms are actually judged on.
Round-Robin gives each process a fixed slice (a quantum) and rotates. No process waits forever, which is why it feels responsive — but short quanta mean more context switches, and those cost real time.
# Правило, которое стоит запомнить:
#
# waiting time = (момент завершения - приход) - burst
# turnaround time = момент завершения - приход
#
# Пример из набора «convoy» (P1=6, P2=4, P3=2, P4=1):
#
# FCFS: P1[0..6] P2[6..10] P3[10..12] P4[12..13]
# среднее ожидание = (0 + 5 + 8 + 9) / 4 = 5.5
#
# SJF : P1[0..6] P4[6..7] P3[7..9] P2[9..13]
# среднее ожидание = (0 + 3 + 5 + 8) / 4 = 4.0
#
# SJF выигрывает, потому что короткие работы успевают
# пройти раньше, а не стоят за длинной. Это и есть convoy effect.Practice
Which algorithm can starve a long job indefinitely if short jobs keep arriving?
Hints
- Think about which job keeps getting overtaken by shorter arrivals.
- One of these algorithms never lets a new short job jump the queue.
12 XP
Using the simulator below, compare FCFS and SJF on the same process set. Which gives a lower average waiting time, and why?
Hints
- Run both and compare the average waiting time the simulator prints.
- Ask whether a long job is delaying the short ones behind it.
18 XP
Put the scheduling decisions in the order Round-Robin makes them for P1(4ms), P2(2ms) with a 2ms quantum.
Hints
- Each process gets the quantum before being preempted.
- A process that finishes early leaves the queue.
15 XP