P4-L8: preemptive scheduling algorithms

preemptive scheduling

Allows the OS to interrupt a running process and switch to another, usually based on priority or time slice (quantum)

round robin

Each process gets a fixed time quantum to run. After that, it’s put at the back of the queue.
✅ Fair
❌ High context switching if quantum is too short

time quantum

The maximum slice of CPU time a process gets in Round Robin before being preempted.

quantum based priority scheduling (QBPS - windows)

A hybrid system used in Windows:

• Each process has a priority level

• Higher-priority gets longer quantum and earlier access

• May preempt mid-quantum if a higher-priority process arrives

aging (in QBPS)

Processes gain priority over time to prevent starvation. Can be:

• Linear

• Step-based

• Exponential

completely fair scheduler (CFS - linux)

Each process gets a fair share of CPU time, tracked by vruntime (virtual runtime).
Lower vruntime = more CPU time

runtime

CFS metric that tracks how much CPU time a process has used relative to others.
Less vruntime = process has gotten less CPU = higher priority

red black tree (CFS)

Balanced binary tree used in CFS to organize processes by vruntime for efficient scheduling.

fairness

CFS and RR prioritize fairness — ensuring all processes eventually get CPU time.

starvation prevention

• RR: every process gets a turn

• CFS: dynamically prioritizes under-served processes

• QBPS: aging boosts priority over time

context switching

Can increase with short time slices. Tradeoff between responsiveness and CPU overhead.

preemptive priority scheduling

Higher-priority process can interrupt a lower-priority one — can lead to starvation without aging.