Process Scheduling Algorithms: FCFS, Round Robin, Priority, SJF & Linux CFS

Scheduling Levels

Operating systems use three scheduling levels:

1. High-level scheduling (job scheduling)
   - Decides which jobs enter the system
   - Common in batch systems

2. Medium-level scheduling (swapping scheduling)
   - Decides which processes are swapped out of memory
   - Suspends/activates processes

3. Low-level scheduling (process scheduling)
   - Decides which ready process gets the CPU
   - Most frequent and most important

First-Come, First-Served (FCFS)

Algorithm Idea

FIFO = First In First Out

Service processes in order of arrival

Like a cafeteria line:
First come, first served

Example

Process arrival order: A(0s), B(1s), C(2s)
Service times: A=3s, B=4s, C=2s

Gantt chart:
│   A   │    B    │ C │
0      3       7   9

Turnaround times:
A: 3 - 0 = 3s
B: 7 - 1 = 6s
C: 9 - 2 = 7s
Average turnaround: (3+6+7)/3 = 5.33s

Waiting times:
A: 0s
B: 3s (waits for A)
C: 7s (waits for A+B)
Average waiting: (0+3+7)/3 = 3.33s

Pros and Cons

Pros:
✅ Simple, easy to implement
✅ Fair

Cons:
❌ Convoy effect (large jobs make small jobs wait long)
❌ Average waiting time not necessarily minimal

Round Robin (RR)

Algorithm Idea

Each process runs for one time quantum
When quantum expires, move to tail of queue

Time quantum size is critical:
- Too large → degrades to FCFS
- Too small → frequent context switches

Example

Time quantum = 2s
Processes arrive: A(0s), B(0s), C(0s)
Service times: A=4s, B=4s, C=4s

Gantt chart:
│ A(2) │ B(2) │ C(2) │ A(2) │ B(2) │ C(2) │
0      2      4      6      8      10     12

Turnaround times:
A: 10 - 0 = 10s
B: 11 - 0 = 11s
C: 12 - 0 = 12s
Average: (10+11+12)/3 = 11s

Waiting times:
A: 0+2+4+6 = 12s - actual 4s = 8s
B: 2+4+6+8 = 20s - 4s = 16s
C: 4+6+8+10 = 28s - 4s = 24s

Time Quantum Selection

Rule of thumb:
Time quantum ≈ 80% of processes finish within this time

Too short: high context-switch overhead
Too long: poor response time

Typical values:
- Desktop systems: 10-50ms
- Servers: ~100ms

Priority Scheduling

Algorithm Idea

Assign each process a priority
Higher priority runs first

Static priority:
- Fixed at creation
- Never changes

Dynamic priority:
- Adjusted by waiting time, behavior
- Prevents low-priority starvation

Example

Processes:
A: priority 3, service 4s
B: priority 1, service 2s
C: priority 2, service 3s
(higher number = higher priority)

Execution order: C → A → B

Gantt chart:
│   C(3)   │    A(4)    │ B(2) │
0          3            7      9

Turnaround times:
C: 3s
A: 7s
B: 9s
Average: (3+7+9)/3 = 6.33s

Priority Inversion Problem

Problem:
- High-priority P1 waits for resource held by low-priority P3
- Medium-priority P2 runs
- P3 preempted by P2, cannot release resource
- P1 blocked indefinitely

Solution: Priority Inheritance
- P3 temporarily inherits P1's priority
- P3 completes quickly and releases resource
- P1 resumes

Shortest Job First (SJF)

Algorithm Idea

Shortest service time runs first

SJF = Shortest Job First

Theoretically optimal
But requires knowing service times in advance

Example

Service times: A=6s, B=3s, C=2s, D=1s
Sorted by service time: D, C, B, A

Gantt chart:
│ D(1) │ C(2) │ B(3) │   A(6)   │
0      1      3      6          12

Average turnaround: (1+3+6+12)/4 = 5.5s
(FCFS would need 10.5s)

Drawbacks

1. Requires knowing service time
   - Hard to estimate accurately

2. Long jobs may starve
   - Continuous stream of short jobs
   - Long job never gets CPU

3. Ignores waiting time
   - Only considers service time

Highest Response Ratio Next (HRRN)

Algorithm Idea

Response Ratio = (Waiting Time + Service Time) / Service Time
               = Waiting Time / Service Time + 1

Run process with highest response ratio

Considers both waiting time and service time

Example

Processes: A(6s), B(3s), C(2s)
Arrival times: all at 0

Initial:
Response ratios: A=1, B=1, C=1
Choose: B (tie-break by FCFS/random)

After B finishes (t=3):
- A waited 3s: RR = (3+6)/6 = 1.5
- C waited 3s: RR = (3+2)/2 = 2.5
Choose: C

After C finishes (t=5):
- A waited 5s: RR = (5+6)/6 = 1.83
Choose: A

Multilevel Queue Scheduling

Algorithm Idea

Maintain multiple ready queues
Each queue has its own scheduling algorithm

┌──────────────────────────────────────┐
│           Scheduling Queues          │
├─────────────┬─────────────┬──────────┤
│ System Proc │ Interactive │ Batch    │
│ Queue (1)   │ Queue (2)   │ Queue (3)│
│ Highest pri │ RR          │ FCFS     │
└─────────────┴─────────────┴──────────┘

Multilevel Feedback Queue (MLFQ)

Multilevel Feedback Queue (MLFQ):
- New processes enter highest-priority queue
- If time quantum expires, demote to lower queue
- I/O-bound processes stay in higher queues

Prevents long-job starvation!

Real-Time Scheduling

Hard vs Soft Real-Time

Hard real-time:
- Must meet deadline
- Missing deadline causes catastrophe
- Example: flight control

Soft real-time:
- Should meet deadline
- Occasional miss not fatal
- Example: video playback

Rate Monotonic (RMA)

Periodic task scheduling
Shorter period → higher priority

Simple but optimal for fixed-priority

Earliest Deadline First (EDF)

Dynamic priority scheduling
Earlier deadline → higher priority

Theoretically optimal
But complex to implement

Linux Schedulers

O(n) Scheduler (pre-2.6)

Before 2.6
- Scheduling complexity O(n)
- n = number of ready processes
- Low efficiency

O(1) Scheduler (early 2.6)

One ready queue per CPU
Priority arrays
Constant O(1) scheduling complexity

CFS (Completely Fair Scheduler)

Since 2.6.23

Core idea:
- Each process has "virtual runtime"
- Process with smallest virtual runtime runs next
- Completely fair scheduling

nice value affects weight

BFS and EEVDF

BFS (Brain Fuck Scheduler):
- Desktop optimization
- Simpler design

EEVDF (Earliest Eligible Virtual Deadline First):
- Adopted in Linux 6.6+
- Improved fair scheduling

Summary: Choosing a Scheduling Algorithm

Common algorithm comparison:

FCFS:
- Simple, fair
- Convoy effect

RR:
- Uniform response
- Quantum selection tricky

Priority:
- Differentiates urgency
- May starve

SJF/HRRN:
- High efficiency
- Need estimation

Practical choices:
- Desktop: RR, CFS
- Server: CFS, multilevel queues
- Real-time: EDF, RMA

Remember : There is no perfect scheduling algorithm, only the most suitable for the scenario!

Key Takeaways :

FCFS is simple and fair but suffers from convoy effect

RR guarantees uniform response; quantum selection matters

Priority scheduling differentiates urgency

SJF is theoretically optimal but requires service-time prediction

Real systems use complex schedulers like CFS