CPU Scheduling
The scheduler decides which ready process runs next. Goals: maximise CPU utilisation and throughput, minimise waiting and response time, stay fair.
Key metrics
| Term | Meaning |
|---|---|
| Arrival time | When the process enters the ready queue |
| Burst time | CPU time required |
| Turnaround time | Completion time − arrival time |
| Waiting time | Turnaround time − burst time |
| Response time | First run time − arrival time |
Algorithms
| Algorithm | Idea | Pre-emptive | Drawback |
|---|---|---|---|
| FCFS | First come, first served | No | Convoy effect (short jobs wait behind long ones) |
| SJF | Shortest burst first | No | Starvation of long jobs; needs burst estimates |
| SRTF | Shortest remaining time first | Yes | Starvation, frequent switches |
| Round Robin | Each process gets a time quantum | Yes | Quantum too small = overhead; too large = FCFS |
| Priority | Highest priority first | Either | Starvation (fix with aging) |
| MLFQ | Several queues; jobs move between them | Yes | Complex to tune |
Round Robin example
Processes P1 (burst 5), P2 (3), P3 (2), all arriving at time 0, quantum = 2.
Gantt: | P1 | P2 | P3 | P1 | P2 | P1 |
0 2 4 6 8 9 10
Completion times: P3 = 6, P2 = 9, P1 = 10. Average waiting time = ((10−5) + (9−3) + (6−2)) / 3 = 5.
A tiny simulator
round_robin.py
from collections import deque
def round_robin(bursts, quantum):
queue = deque(bursts.items()) # (name, remaining)
time, finish = 0, {}
while queue:
name, left = queue.popleft()
run = min(quantum, left)
time += run
if left - run:
queue.append((name, left - run))
else:
finish[name] = time
return finish
print(round_robin({"P1": 5, "P2": 3, "P3": 2}, 2))
# {'P3': 6, 'P2': 9, 'P1': 10}
Loading Comments...