Linux I/O Schedulers

I/O schedulers decide the order in which disk requests are served to improve:

• Performance (throughput)

• Fairness

• Disk seek efficiency

---

1. Elevator Algorithm (SCAN)

📌 Idea

The disk head moves like an elevator:

• Goes in one direction (e.g., inward)

• Services all requests in that direction

• Then reverses direction

---

⚙️ How it works

1. Requests are sorted by disk block number

2. Disk head moves sequentially

3. Services requests along the path

4. At the end → reverses direction

---

📊 Example

Requests: 10, 22, 20, 2, 40
Head at: 15

Order served:

20 → 22 → 40 → (reverse) → 10 → 2

---

✅ Advantages

• Reduces seek time

• Avoids excessive head movement

• Good throughput

---

❌ Disadvantages

• Can cause starvation (far requests wait longer)

• Not fair to all processes

---

🧠 Key Idea

👉 Optimizes disk movement, not fairness

---

2. Completely Fair Queuing (CFQ)

📌 Idea

Each process gets a fair share of disk access time

---

⚙️ How it works

• Each process has its own request queue

• Scheduler allocates time slices to each queue

• Requests are served in a round-robin fashion

---

🧩 Features

• Time-based fairness (not just request order)

• Supports priorities

• Tries to balance:

  • Throughput

  • Latency

  • Fairness

---

📊 Example

Processes:

• P1 → many requests

• P2 → few requests

CFQ ensures:

• P2 is not starved

• Both get fair disk time

---

✅ Advantages

• Prevents starvation

• Fair to all processes

• Good for multi-user systems

---

❌ Disadvantages

• Slightly higher overhead

• May reduce maximum throughput compared to elevator

---

🧠 Key Idea

👉 Optimizes fairness across processes

---

🔁 Comparison

Feature	Elevator (SCAN)	CFQ
Goal	Reduce seek time	Fairness
Strategy	Sorted by disk position	Per-process queues
Fairness	Low	High
Starvation	Possible	Avoided
Performance	High throughput	Balanced

---

 Summary

• Elevator algorithm: Moves disk head sequentially like an elevator, reducing seek time but may cause starvation.

• CFQ (Completely Fair Queuing): Gives each process equal access to disk using time slices, ensuring fairness but with some overhead.