CPU Scheduling Algorithms; Threads

CPU Scheduling Algorithms

17.1 FCFS — First-Come, First-Served

Non-preemptive
Processes scheduled in arrival order
Simple but can cause Convoy Effect (short jobs wait behind long jobs)

Example:

Process  Burst Time  Arrival Time
P1        24ms        0
P2         3ms        0
P3         3ms        0

Gantt Chart:    | P1 (0-24) | P2 (24-27) | P3 (27-30) |
Waiting Times:  P1=0, P2=24, P3=27
Average Waiting: (0+24+27)/3 = 17ms

17.2 SJF — Shortest Job First

Non-preemptive (or preemptive = SRTF)
Schedule process with shortest burst time next
Optimal for minimizing average waiting time
Problem: Requires knowing burst time in advance

SRTF (Shortest Remaining Time First): Preemptive version of SJF

Example:

Process  Burst Time  Arrival Time
P1        6ms        0
P2         8ms        0
P3         7ms        0
P4         3ms        0

Order: P4(3ms) → P1(6ms) → P3(7ms) → P2(8ms)
Average Waiting = (3+16+9+0)/4 = 7ms   (vs FCFS: 10.25ms)

17.3 Round Robin (RR)

Preemptive
Each process gets a fixed time quantum (time slice) — usually 10-100ms
After time quantum expires, process is preempted and moved to back of ready queue
Most common in time-sharing systems

Example (q=4ms):

Process  Burst Time
P1        24ms
P2         3ms
P3         3ms

Gantt: |P1(0-4)|P2(4-7)|P3(7-10)|P1(10-14)|P1(14-18)|P1(18-22)|P1(22-26)|P1(26-30)|

Tradeoff: Large quantum → behaves like FCFS; Small quantum → more context switches

17.4 Priority Scheduling

Each process has a priority number (lower number = higher priority)
Highest priority process runs first
Preemptive or Non-preemptive
Problem: Starvation — low priority processes may never run

Solution: Aging — gradually increase priority of waiting processes

17.5 Multilevel Queue Scheduling

Multiple queues for different process types:

Foreground (interactive) — Round Robin

Background (batch) — FCFS

Different queues have different priorities

17.6 Multilevel Feedback Queue

Processes can move between queues based on behavior
CPU-bound processes → lower priority queue
I/O-bound processes → higher priority queue
Most complex but most flexible

Algorithm Comparison

Algorithm	Preemptive	Avg Wait	Starvation	Overhead
FCFS	No	High	No	Low
SJF	No	Optimal	Yes (long jobs)	Medium
SRTF	Yes	Optimal	Yes	High
Round Robin	Yes	Medium	No	Medium
Priority	Both	Medium	Yes (low priority)	Low
Multilevel Feedback	Yes	Good	No (with aging)	High

Threads

What is a Thread?

A thread is the smallest unit of CPU execution — a lightweight process.

Process vs Thread:

Feature	Process	Thread
Definition	Program in execution	Lightweight sub-unit of a process
Memory	Own address space	Shares process address space
Creation cost	Expensive	Cheap
Communication	IPC required	Shared memory directly
Context switch	Heavy	Light
Failure	Isolated	Can crash other threads

Types of Threads

Type	Description
User-level threads	Managed by user-space library (not OS)
Kernel-level threads	Managed by OS kernel
Hybrid threads	Combination

Multi-threading Models

Model	Description	Example
Many-to-One	Many user threads → one kernel thread	Old Green threads
One-to-One	Each user thread = one kernel thread	Windows, Linux
Many-to-Many	Many user → many kernel threads	Solaris, HP-UX

Thread Benefits

Faster creation than processes
Faster context switching within same process

Shared memory enables easy data sharing

Enables true parallelism on multi-core CPUs
Responsive UI (one thread handles UI, another does background work)