Disk Scheduling Algorithms
IntermediateDisk scheduling algorithms determine the order in which I/O requests are serviced to minimise total disk head seek time and improve throughput.
Overview
HDDs (Hard Disk Drives) have a moving read/write head. Seek time — time to move the head to the correct track — dominates HDD latency. Disk scheduling algorithms reorder the request queue to reduce total head movement. FCFS (First Come First Served) is fair but slow. SSTF (Shortest Seek Time First) minimises seek time but can cause starvation. SCAN (Elevator) moves the head back and forth servicing requests in each direction. C-SCAN (Circular SCAN) only services requests on one direction and resets to the beginning, providing more uniform wait times. LOOK and C-LOOK are variants that stop at the last request rather than the disk edge. Modern Linux uses deadline and mq-deadline schedulers. SSDs largely make disk scheduling irrelevant due to uniform random access times.
FCFS, SSTF, and SCAN with Worked Example
Request queue: {98, 183, 37, 122, 14, 124, 65, 67}, initial head position: 53. Calculate total head movement for each algorithm by tracing the order requests are serviced.
import java.util.*;
int[] requests = {98, 183, 37, 122, 14, 124, 65, 67};
int head = 53;
// ── FCFS ─────────────────────────────────────────────────────────────────────
// Service in arrival order: 53→98→183→37→122→14→124→65→67
// Movement: |98-53|+|183-98|+|37-183|+|122-37|+|14-122|+|124-14|+|65-124|+|67-65|
// = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640
int fcfsTotal = 0, cur = head;
for (int r : requests) { fcfsTotal += Math.abs(r - cur); cur = r; }
System.out.println("FCFS total movement: " + fcfsTotal); // 640
// ── SSTF ─────────────────────────────────────────────────────────────────────
// Always service closest request: 53→65→67→37→14→98→122→124→183
// Movement: 12+2+30+23+84+24+2+59 = 236
List<Integer> sstfQueue = new ArrayList<>();
for (int r : requests) sstfQueue.add(r);
int sstfTotal = 0, sstfCur = head;
while (!sstfQueue.isEmpty()) {
int nearest = sstfQueue.stream()
.min(Comparator.comparingInt(r -> Math.abs(r - sstfCur))).get();
sstfTotal += Math.abs(nearest - sstfCur);
sstfCur = nearest;
sstfQueue.remove(Integer.valueOf(nearest));
}
System.out.println("SSTF total movement: " + sstfTotal); // 236
// ── SCAN (Elevator) ──────────────────────────────────────────────────────────
// Head moves toward higher tracks first: 53→65→67→98→122→124→183→37→14
// (reaches 183, reverses direction, services 37 then 14)
// Movement: 12+2+31+24+2+59+146+23 = 299 (approximately)
int[] scanOrder = {65, 67, 98, 122, 124, 183, 37, 14};
int scanTotal = 0, scanCur = head;
for (int r : scanOrder) { scanTotal += Math.abs(r - scanCur); scanCur = r; }
System.out.println("SCAN total movement: " + scanTotal); // 299C-SCAN, C-LOOK and Modern OS Schedulers
C-SCAN services requests in one direction only, then jumps back to the beginning (no servicing on return). This provides more uniform waiting times. C-LOOK is like C-SCAN but stops at the last pending request rather than going to disk edge. Linux's mq-deadline scheduler adds per-request deadlines to prevent starvation.
// C-SCAN: move toward 199 (disk end), service along the way,
// then jump to 0 and sweep up again
// Order for same queue (head=53): 65→67→98→122→124→183 → jump to 0 → 14→37
// Movement: (183-53) + (183-0) + (37-0) = 130 + 183 + 37 = 350
// C-LOOK: stop at 183 (last request), jump to 14 (lowest request)
// Order: 65→67→98→122→124→183 → jump to 14 → 37
// Movement: (183-53) + (183-14) + (37-14) = 130 + 169 + 23 = 322
// Summary table for request queue {98,183,37,122,14,124,65,67}, head=53:
// Algorithm | Total Movement | Notes
// ----------|----------------|-------------------------------
// FCFS | 640 | Simple, poor performance
// SSTF | 236 | Best seek time, starvation risk
// SCAN | 299 | Good balance, slight bias at ends
// C-SCAN | 350 | Uniform wait time across disk
// C-LOOK | 322 | SCAN variant, doesn't go to disk edge
// Modern Linux I/O schedulers (check /sys/block/sda/queue/scheduler):
// - mq-deadline: adds per-request deadline to prevent starvation (default for HDD)
// - bfq (Budget Fair Queuing): bandwidth-proportional per-process scheduling
// - none: no reordering (appropriate for SSDs — random access is uniform)
// - kyber: low-latency scheduler for fast NVMe SSDs
// Java relevance: on SSDs, disk scheduling is irrelevant — focus on:
// - Sequential vs random I/O patterns (SSDs still prefer sequential)
// - Page cache utilisation (Files.readAllBytes vs streaming)
// - Direct I/O (FileChannel with O_DIRECT flag via JNA) to bypass page cacheKey Points to Remember
- 1FCFS is fair but has the worst average seek time; never use it for high-throughput disk workloads.
- 2SSTF minimises seek time on average but can starve requests at the extremes of the disk.
- 3SCAN (elevator) prevents starvation by guaranteeing the head will eventually reach every position.
- 4C-SCAN provides more uniform wait times than SCAN by only servicing in one direction.
- 5SSDs have no moving parts, so seek time is negligible — disk scheduling algorithms are largely irrelevant for NVMe.
- 6Linux's mq-deadline is the recommended scheduler for HDDs; use none for SSDs.
Interview Questions
Sign in to ask AriaCompare SSTF and SCAN disk scheduling algorithms — when would you prefer each?
Calculate the total head movement for SCAN given requests {98, 183, 37, 122, 14, 124, 65, 67} with head at 53.
Why are disk scheduling algorithms less relevant for SSDs compared to HDDs?
What is the difference between SCAN and C-SCAN? Which provides more uniform response times?
Ask Aria about Disk Scheduling Algorithms
Your personal AI tutor — ask anything about this concept
Revision Status
Personal Notes
Sign in to save personal notes for this topic.
Discussion
Sign in to join the discussion.