Skip to main content

9.2 FCFS & Shortest Seek Time First (SSTF) Disk Scheduling

Back to Operating Systems Notes
📚Module 09: Storage & Disk SchedulingTopic 9.2⏱️18 min read
🎯High-Yield For:Computer Science Foundations • Systems Engineering • Storage Systems

💡 Core Intuition​

🍳 The Everyday Analogy: The City Courier Delivery Route​

Imagine an express motorcycle courier with 8 packages to deliver across a 200-block avenue:

Architecture Flow

The Courier Routing Strategy Pipeline

Contrasting order-of-call dispatching with proximity-first optimization

💡 Hover or click any card for deep-dive operational details
📞Naive Driver

Deliver in Order of Phone Calls

FCFS Policy

Call 1 came from Block 98, Call 2 from Block 183, Call 3 from Block 14.

→
Alternative Policy
🗺️Greedy Driver

Deliver to Nearest Customer First

SSTF Policy

At Block 53, the driver checks their GPS: 'Who is closest to where I am standing right now?'

→
The Hidden Trap
⏳The Forgotten Guy

Customer at Block 183 Forgotten

Starvation Pathology

If new orders keep arriving at downtown blocks 50–70, the customer at Block 183 starves forever.

  • FCFS: Fair and starvation-free, but causes erratic back-and-forth arm thrashing.
  • SSTF: Minimizes seek movements locally via greedy proximity, but can cause peripheral requests to starve indefinitely.

💻 Bridging to Computer Science​

When a system runs multiple concurrent processes, read and write requests accumulate in the Disk Request Queue.

Because moving the physical read/write head (Seek Time) is by far the most expensive operation in secondary storage (3–10 ms3\text{–}10\text{ ms}), the operating system must reorder pending requests to minimize the total head traversal distance (measured in total cylinders traversed).

📚 Core Deep-Dive & Concepts​

1. First-Come, First-Served (FCFS) Scheduling​

Algorithm Mechanics​

  • Services I/O requests strictly in the order they arrive in the device queue.
  • Operates as a simple FIFO queue of cylinder numbers.
  • Imposes zero computational sorting overhead.

Mathematical Trace: FCFS​

Given the initial head position at Cylinder 53 and the request queue:

Queue: [ 98,  183,  37,  122,  14,  124,  65,  67 ]\text{Queue: } [\,98,\; 183,\; 37,\; 122,\; 14,\; 124,\; 65,\; 67\,]

💽

FCFS Disk Head Trajectory

Erratic actuator arm oscillations across disk cylinders: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

Showing All 8 Traversal Legs
0143753656798122124183199Δ 45Δ 85Δ 146Δ 85Δ 108Δ 110Δ 59Δ 2Start: 53#1 (98)#2 (183)#3 (37)#4 (122)#5 (14)#6 (124)#7 (65)#8 (67)
💡Hover over any node or click [Next Step ▶] to inspect seek displacement (Δ) and cumulative travel (Σ).
Total Head Movement640 Cylinders
Requests Serviced8 Requests
Initial PositionCylinder 53
Seek PatternUnoptimized FIFO
StepFrom CylinderTo Target CylinderTraversal FormulaDistance MovedCumulative Movement
15398$98 - 53$
298183$183 - 98$
318337$37 - 183$
437122$122 - 37$
512214$14 - 122$
614124$124 - 14$
712465$65 - 124|$59
86567$67 - 65|$2

Total Head Movement (FCFS)=45+85+146+85+108+110+59+2=640 Cylinders\mathbf{\text{Total Head Movement (FCFS)} = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640\text{ Cylinders}}

Architectural Evaluation: FCFS​

  • Advantages:
    • Trivial to implement.
    • Intrinsically fair: every request is guaranteed service in finite time.
    • Zero Starvation.
  • Disadvantages:
    • Wild, erratic head swings across the disk surface (e.g. from 183183 down to 3737, then up to 122122, then down to 1414).
    • Results in abysmal I/O throughput and long average response times.

2. Shortest Seek Time First (SSTF) Scheduling​

Algorithm Mechanics​

  • Selects the request with the minimum seek distance from the current head position: Next Target=arg⁡min⁡Ri∈Q∣Head−Ri∣\text{Next Target} = \arg\min_{R_i \in Q} |\text{Head} - R_i|
  • Operates analogously to Shortest Job First (SJF) in CPU scheduling.
  • A greedy heuristic designed to maximize instantaneous I/O throughput.

3. Step-by-Step Mathematical Trace: SSTF​

  • Initial Head Position: 53
  • Remaining Queue: [ 98, 183, 37, 122, 14, 124, 65, 67 ]
💽

SSTF Disk Head Trajectory

Greedy proximity seeking slashes travel: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183

Showing All 8 Traversal Legs
0143753656798122124183199Δ 12Δ 2Δ 30Δ 23Δ 84Δ 24Δ 2Δ 59Start: 53#1 (65)#2 (67)#3 (37)#4 (14)#5 (98)#6 (122)#7 (124)#8 (183)
💡Hover over any node or click [Next Step ▶] to inspect seek displacement (Δ) and cumulative travel (Σ).
Total Head Movement236 Cylinders
Improvement vs FCFS63.1% Less Travel
Requests Serviced8 Requests
Seek PatternLocally Greedy

| Step | Current Head | Remaining Candidates in Queue | Distances ∣Head−Ri∣|\text{Head} - R_i| | Minimum Selected | Distance Moved | | :---: | :---: | :---: | :---: | :---: | :---: | | 1 | 53 | 98, 183, 37, 122, 14, 124, 65, 67 | 98 (45), 37 (16), 65 (12), 67 (14) | 65 | ∣65−53∣=12|65 - 53| = \mathbf{12} | | 2 | 65 | 98, 183, 37, 122, 14, 124, 67 | 67 (2), 98 (33), 37 (28) | 67 | ∣67−65∣=2|67 - 65| = \mathbf{2} | | 3 | 67 | 98, 183, 37, 122, 14, 124 | 37 (30), 98 (31), 122 (55) | 37 | ∣37−67∣=30|37 - 67| = \mathbf{30} | | 4 | 37 | 98, 183, 122, 14, 124 | 14 (23), 98 (61) | 14 | ∣14−37∣=23|14 - 37| = \mathbf{23} | | 5 | 14 | 98, 183, 122, 124 | 98 (84), 122 (108), 124 (110), 183 (169) | 98 | ∣98−14∣=84|98 - 14| = \mathbf{84} | | 6 | 98 | 183, 122, 124 | 122 (24), 124 (26), 183 (85) | 122 | ∣122−98∣=24|122 - 98| = \mathbf{24} | | 7 | 122 | 183, 124 | 124 (2), 183 (61) | 124 | ∣124−122∣=2|124 - 122| = \mathbf{2} | | 8 | 124 | 183 | 183 (59) | 183 | ∣183−124∣=59|183 - 124| = \mathbf{59} |

Total Head Movement (SSTF)=12+2+30+23+84+24+2+59=236 Cylinders\mathbf{\text{Total Head Movement (SSTF)} = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236\text{ Cylinders}}

Performance Comparison on Benchmark:​

  • FCFS Head Movement: 640640 Cylinders
  • SSTF Head Movement: 236236 Cylinders
  • Improvement: 63.1%63.1\% reduction in actuator arm travel!

4. Comprehensive Comparison Matrix​

🏭 In The Real World: Production Case Study​

Database Log Flushing & Sequential Write Optimization​

In high-write enterprise databases (such as PostgreSQL Write-Ahead Logging WAL or Cassandra CommitLogs), random seek times destroy transaction commit throughput:

  1. Why SSTF is Dangerous for General Purpose Workloads:
    • In desktop and server operating systems, a batch of requests reading a file in cylinder 50 can indefinitely stall a critical user click trying to load a binary from cylinder 190.
  2. The Modern Evolution:
    • Because SSTF introduces starvation, modern production kernels evolved toward Elevator Algorithms (SCAN, C-SCAN, and LOOK), which achieve near-SSTF throughput while mathematically eliminating starvation!

🎯 Exam & Interview Pitfall Check​

Core Conceptual Questions

Question 1: Why is SSTF scheduling considered a greedy algorithm, and why does it NOT guarantee the globally optimal total seek time? Answer:

  1. SSTF is greedy because at every step it makes the locally optimal choice—selecting the candidate cylinder closest to the current head position without considering future arrivals or the global path.
  2. It does not guarantee the global minimum seek time. For example, moving to a nearby cylinder might leave the head stranded near one edge of the disk, requiring a massive full-stroke sweep later. A different initial choice might have allowed the arm to sweep past multiple cylinders monotonically, yielding a lower aggregate total.

Question 2: Under what workload condition does SSTF degenerate into severe starvation? Answer:

  • SSTF causes starvation when a continuous stream of I/O requests arrives for tracks near the current head position.
  • The algorithm will continuously satisfy these newly arriving nearby requests, keeping the actuator arm tethered to that local zone.
  • Any request located far away on an outer or inner cylinder track will sit in the queue indefinitely, suffering unbounded starvation.
Common Interview Traps
  • The Tie-Breaking Distance Trap: At step 3 of the SSTF trace from cylinder 6767, candidate 3737 has distance ∣37−67∣=30|37 - 67| = 30, while candidate 9898 has distance ∣98−67∣=31|98 - 67| = 31. Students frequently pick 9898 by guessing that higher numbers are closer. Always calculate absolute numerical differences: ∣67−37∣=30<31|67 - 37| = 30 < 31!
  • The "SSTF Eliminates Seek Time" Fallacy: SSTF minimizes head movement compared to FCFS, but seek time is still required. Only sequential contiguous allocations on the same cylinder achieve true zero-seek performance.
🗺️View Complete Operating Systems Roadmap & Syllabus
← Previous Topic9.1 Magnetic Disk AnatomyNext Topic →9.3 SCAN & C-SCAN Disk Scheduling
💬

Discussion & Doubts