Disk Scheduling Algorithms
FCFS Scheduling
Read aloud is unavailable in this browser.
The Disk Access Problem
In a multi-programmed computing environment, multiple processes constantly compete for disk access. Each process generates I/O requests that must be serviced by the disk drive—a mechanical device where the physical movement of read/write heads introduces substantial latency. Unlike CPU scheduling, where context switches happen in microseconds, disk scheduling decisions can impact performance by orders of magnitude.
Consider a hard disk drive (HDD) receiving requests for sectors scattered across the disk surface. The disk head must physically move to each requested track, wait for the platter to rotate to the correct sector, and then perform the data transfer. This mechanical choreography is excruciatingly slow compared to electronic operations—seek times of 5-15 milliseconds and rotational latencies of 2-8 milliseconds dwarf the nanosecond-scale speeds of RAM access.
The fundamental question disk scheduling algorithms answer is: In what order should pending I/O requests be serviced to optimize performance?
By the end of this page, you will thoroughly understand First-Come, First-Served (FCFS) disk scheduling—the simplest scheduling algorithm. You'll grasp its implementation, calculate its performance metrics, understand its guarantees and limitations, and establish the baseline against which all other disk scheduling algorithms are measured.
Understanding Disk Access Time
Before diving into scheduling algorithms, we must deeply understand the components of disk access time. This understanding is essential because disk scheduling algorithms primarily optimize for seek time, the largest and most variable component of disk latency.
Total Disk Access Time consists of three components:
$$T_{access} = T_{seek} + T_{rotation} + T_{transfer}$$
Let's examine each component in detail:
| Component | Description | Typical Range | Controllable by Scheduling? |
|---|---|---|---|
| Seek Time ($T_{seek}$) | Time for the disk arm to move the read/write head to the target track/cylinder | 0-15 ms (HDD), ~0.1 ms (SSD) | Yes — Primary optimization target |
| Rotational Latency ($T_{rotation}$) | Time for the disk platter to rotate until the target sector is under the head | 0-8.33 ms (at 7200 RPM) | Partially — Some algorithms consider this |
| Transfer Time ($T_{transfer}$) | Time to read/write the data once head is positioned | 0.01-0.1 ms per sector | No — Fixed by disk technology |
Seek Time Mechanics:
Seek time is not linear with distance. A typical seek time function follows:
$$T_{seek}(d) = a + b \cdot \sqrt{d}$$
Where:
- $d$ = number of tracks to traverse
- $a$ = startup time (overcoming inertia, typically 1-2 ms)
- $b$ = constant depending on arm acceleration characteristics
For practical calculations, we often use a simplified linear model:
$$T_{seek}(d) = T_{min} + \frac{d}{D_{max}} \cdot (T_{max} - T_{min})$$
Where:
- $T_{min}$ = minimum seek time (track-to-track, ~0.5-1 ms)
- $T_{max}$ = maximum seek time (full stroke, ~15-20 ms)
- $D_{max}$ = maximum number of tracks
- $d$ = tracks to traverse
For a 7200 RPM disk with 4ms average seek time and 4.16ms average rotational latency, seek time often contributes 40-60% of total access time for random workloads. More importantly, seek time is the only component that varies based on request ordering—making it the primary target for scheduling optimization.
Rotational Latency:
Once the head reaches the correct track, the disk must rotate until the target sector passes under the head. On average, the sector is halfway around the platter:
$$T_{rotation_avg} = \frac{1}{2} \cdot \frac{60}{RPM} = \frac{30}{RPM} \text{ seconds}$$
For common disk speeds:
- 5400 RPM: Average rotational latency = 5.56 ms
- 7200 RPM: Average rotational latency = 4.17 ms
- 10000 RPM: Average rotational latency = 3.00 ms
- 15000 RPM: Average rotational latency = 2.00 ms
FCFS: The Algorithm
First-Come, First-Served (FCFS) is the most intuitive disk scheduling algorithm. Requests are processed in the exact order they arrive in the disk queue—no reordering, no optimization, pure sequential servicing.
The algorithm maintains a simple FIFO (First-In, First-Out) queue of pending requests. When the disk becomes available, it services the request at the front of the queue, then moves to the next, continuing until the queue is empty.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162
"""FCFS (First-Come, First-Served) Disk Scheduling Algorithm This implementation demonstrates the complete FCFS scheduling logic,including metric calculation and detailed trace generation.""" from dataclasses import dataclassfrom collections import dequefrom typing import List, Tupleimport time @dataclassclass DiskRequest: """Represents a single disk I/O request.""" request_id: int cylinder: int # Target cylinder/track number arrival_time: float # When request was submitted process_id: int # Requesting process is_read: bool # True for read, False for write class FCFSScheduler: """ FCFS Disk Scheduling Implementation Maintains a FIFO queue and processes requests in arrival order. Provides detailed metrics and scheduling trace. """ def __init__(self, initial_head_position: int, total_cylinders: int): """ Initialize the FCFS scheduler. Args: initial_head_position: Starting cylinder position of disk head total_cylinders: Total number of cylinders on the disk """ self.queue: deque[DiskRequest] = deque() self.head_position = initial_head_position self.total_cylinders = total_cylinders # Metrics tracking self.total_seek_distance = 0 self.requests_serviced = 0 self.service_order: List[int] = [] self.seek_sequence: List[Tuple[int, int]] = [] # (from, to) def submit_request(self, request: DiskRequest) -> None: """Add a new request to the end of the queue.""" self.queue.append(request) def get_next_request(self) -> DiskRequest | None: """ Get the next request to service (FIFO order). Returns: The next request, or None if queue is empty. """ if not self.queue: return None return self.queue.popleft() def service_request(self, request: DiskRequest) -> dict: """ Service a disk request and update metrics. Returns: Dictionary containing service details. """ old_position = self.head_position seek_distance = abs(request.cylinder - self.head_position) # Move the head to the requested cylinder self.head_position = request.cylinder # Update metrics self.total_seek_distance += seek_distance self.requests_serviced += 1 self.service_order.append(request.cylinder) self.seek_sequence.append((old_position, request.cylinder)) return { "request_id": request.request_id, "cylinder": request.cylinder, "seek_distance": seek_distance, "head_moved_from": old_position, "head_moved_to": request.cylinder, } def run_scheduling(self) -> dict: """ Run FCFS scheduling until queue is empty. Returns: Complete scheduling results with metrics. """ results = [] while self.queue: request = self.get_next_request() if request: result = self.service_request(request) results.append(result) return { "algorithm": "FCFS", "service_order": self.service_order, "total_seek_distance": self.total_seek_distance, "average_seek_distance": ( self.total_seek_distance / self.requests_serviced if self.requests_serviced > 0 else 0 ), "requests_serviced": self.requests_serviced, "seek_sequence": self.seek_sequence, "detailed_results": results, } def get_pending_count(self) -> int: """Return number of pending requests.""" return len(self.queue) # Example usage demonstrating FCFS behaviordef demonstrate_fcfs(): """ Demonstrate FCFS with a realistic request sequence. Disk configuration: - 200 cylinders (0-199) - Head starts at cylinder 50 - Request queue: 95, 180, 34, 119, 11, 123, 62, 64 """ scheduler = FCFSScheduler(initial_head_position=50, total_cylinders=200) # Simulate requests arriving in a specific order requests = [95, 180, 34, 119, 11, 123, 62, 64] for i, cylinder in enumerate(requests): scheduler.submit_request(DiskRequest( request_id=i, cylinder=cylinder, arrival_time=time.time(), process_id=1000 + i, is_read=True, )) # Run the scheduler results = scheduler.run_scheduling() # Display results print(f"Algorithm: {results['algorithm']}") print(f"Service Order: {' -> '.join(map(str, ['50'] + results['service_order']))}") print(f"Total Seek Distance: {results['total_seek_distance']} cylinders") print(f"Average Seek Distance: {results['average_seek_distance']:.2f} cylinders") print(f"Seek Sequence:") for i, (from_cyl, to_cyl) in enumerate(results['seek_sequence']): print(f" Move {i+1}: {from_cyl} -> {to_cyl} (distance: {abs(to_cyl - from_cyl)})") return results if __name__ == "__main__": demonstrate_fcfs()The simplicity of FCFS makes it trivial to implement correctly. The queue can be a simple array with head/tail pointers or a linked list. No sorting or comparison operations are needed—just enqueue arriving requests and dequeue for service. This makes FCFS extremely predictable in terms of scheduling overhead.
Worked Example: Complete FCFS Trace
Let's trace through a complete FCFS scheduling scenario step by step, calculating all metrics precisely.
Scenario:
- Disk has 200 cylinders (numbered 0-199)
- Disk head starts at cylinder 50
- Request queue (in arrival order): 95, 180, 34, 119, 11, 123, 62, 64
| Step | Current Head | Request Serviced | Seek Distance | Cumulative Seek | Direction |
|---|---|---|---|---|---|
| Initial | 50 | — | — | 0 | — |
| 1 | 50 → 95 | 95 | |95 - 50| = 45 | 45 | Outward ↑ |
| 2 | 95 → 180 | 180 | |180 - 95| = 85 | 130 | Outward ↑ |
| 3 | 180 → 34 | 34 | |34 - 180| = 146 | 276 | Inward ↓ |
| 4 | 34 → 119 | 119 | |119 - 34| = 85 | 361 | Outward ↑ |
| 5 | 119 → 11 | 11 | |11 - 119| = 108 | 469 | Inward ↓ |
| 6 | 11 → 123 | 123 | |123 - 11| = 112 | 581 | Outward ↑ |
| 7 | 123 → 62 | 62 | |62 - 123| = 61 | 642 | Inward ↓ |
| 8 | 62 → 64 | 64 | |64 - 62| = 2 | 644 | Outward ↑ |
Performance Metrics:
$$\text{Total Seek Distance} = 45 + 85 + 146 + 85 + 108 + 112 + 61 + 2 = 644 \text{ cylinders}$$
$$\text{Average Seek Distance} = \frac{644}{8} = 80.5 \text{ cylinders}$$
Observation: Notice how the head movements are chaotic and inefficient. The head swings back and forth across the disk multiple times (observe the Direction column), traveling far more distance than necessary. The move from cylinder 180 to 34 alone (146 cylinders) is almost 75% of the entire disk width!
The head travels 644 cylinders to service requests spanning only 169 cylinders (from 11 to 180). An optimal ordering would require traversing this range only once—about 169 cylinders total. FCFS requires 3.8x more seek distance than optimal for this workload!
Mathematical Analysis
Understanding the expected behavior of FCFS requires probability theory. Let's derive the expected seek distance for random request patterns.
Assumptions:
- Disk has $N$ cylinders (numbered 0 to $N-1$)
- Requests are uniformly distributed across cylinders
- Requests arrive in random order
Expected Seek Distance for Uniform Random Requests:
For any two uniformly random cylinder positions $X$ and $Y$ on a disk of $N$ cylinders, the expected distance between them is:
$$E[|X - Y|] = \frac{N}{3}$$
Derivation:
Let $X$ and $Y$ be independent, uniformly distributed on $[0, N]$. The expected absolute difference is:
$$E[|X - Y|] = \int_0^N \int_0^N \frac{|x - y|}{N^2} , dx , dy$$
By symmetry, we can compute:
$$= 2 \int_0^N \int_0^y \frac{(y - x)}{N^2} , dx , dy = 2 \int_0^N \frac{y^2}{2N^2} , dy = \frac{1}{N^2} \cdot \frac{N^3}{3} = \frac{N}{3}$$
For a 10,000-cylinder disk with random requests, FCFS produces an average seek distance of approximately 3,333 cylinders per request. With an average seek time of 10ms for full-stroke seeks, this translates to roughly 3.3ms per seek on average—before rotational latency and transfer time are even considered.
Variance and Worst-Case Analysis:
FCFS exhibits high variance in seek distance. The variance of $|X - Y|$ for uniform distribution is:
$$Var[|X - Y|] = \frac{N^2}{18}$$
This high variance is problematic for real-time systems where predictable latency is crucial.
Worst-Case Behavior:
The worst case for FCFS occurs when requests alternate between extremes of the disk:
- Request sequence: 0, N-1, 0, N-1, 0, N-1, ...
- Each seek traverses the entire disk: $(N-1)$ cylinders
- For $k$ requests: Total seek = $k \cdot (N-1)$
This pathological case demonstrates that FCFS provides no protection against adversarial or unlucky request patterns.
| Workload Pattern | Expected Seek Distance | Relative Efficiency | Notes |
|---|---|---|---|
| Uniform Random | $N/3$ per request | ~33% of worst-case | Typical for general-purpose systems |
| Sequential | ~0 cylinders | Near optimal | File streaming, sequential reads |
| Alternating Extremes | $(N-1)$ per request | Worst possible | Pathological case |
| Clustered (locality) | Much less than $N/3$ | Better than random | Database with hot tables |
| Bimodal (two hot regions) | Distance between regions | Moderate | Split workloads |
FCFS Properties and Guarantees
Despite its performance limitations, FCFS possesses several important properties that make it valuable in certain contexts:
- •Fairness: Every request is eventually served; no starvation
- •Simplicity: Trivial to implement correctly
- •Predictability: Request latency is FIFO-ordered
- •No Reordering Overhead: Zero CPU time for scheduling decisions
- •Deterministic Behavior: Same input always produces same output
- •Minimal Memory: Only queue storage needed
- •Poor Seek Optimization: No attempt to minimize head movement
- •High Average Latency: Random order means wasted seeks
- •High Variance: Unpredictable service times
- •Convoy Effect: Slow requests block following requests
- •Inefficient at Scale: Performance degrades with queue depth
- •Ignores Disk Geometry: Treats disk like random-access memory
The Starvation-Free Guarantee:
FCFS is starvation-free by construction. Every request that enters the queue will eventually be serviced—the wait time is exactly the sum of service times for all requests ahead in the queue. This is expressed as:
$$W_i = \sum_{j=1}^{i-1} S_j$$
Where:
- $W_i$ = wait time for request $i$
- $S_j$ = service time for request $j$
This guarantee is not provided by many optimizing algorithms like SSTF, which we'll explore later. The tradeoff between fairness and performance is a recurring theme in scheduling.
When a request far from the current head position arrives and reaches the front of the queue, all subsequent requests must wait for this long seek—even if those requests are near the current head position. This 'convoy effect' can significantly degrade average response time.
When to Use FCFS
Despite its inefficiencies, FCFS remains appropriate in specific scenarios:
- •Low I/O Load Systems: When the disk queue is typically empty or contains only 1-2 requests, scheduling optimization provides minimal benefit. FCFS's simplicity dominates.
- •Fairness-Critical Applications: Systems where strict ordering guarantees are required—transaction logs, audit trails, or situations where request order has semantic meaning.
- •Debugging and Testing: FCFS's deterministic behavior makes it invaluable for reproducing issues and validating correct behavior.
- •SSDs and NVMe Storage: Solid-state drives have negligible seek times, eliminating the primary motivation for seek optimization. FCFS overhead approaches zero.
- •Embedded Systems: When CPU cycles for scheduling logic are precious and the disk controller has limited resources.
- •Reference Implementation: FCFS serves as a baseline for evaluating other algorithms and for educational purposes.
With SSDs, the seek time component essentially vanishes. Modern NVMe SSDs have access times measured in tens of microseconds—making the scheduling algorithm choice far less critical. FCFS becomes perfectly adequate, and its simplicity becomes an advantage. This is why many SSD-focused systems use simpler scheduling or no scheduling at all.
| Factor | Favor FCFS | Avoid FCFS |
|---|---|---|
| Average Queue Depth | < 2-3 requests | 5 requests typically |
| Storage Technology | SSD, NVMe | HDD, especially high-RPM |
| Workload Pattern | Sequential or highly localized | Random across disk |
| Fairness Requirements | Strict FIFO ordering needed | Throughput more important |
| System Complexity | Minimal resources | Sufficient CPU for optimization |
| Latency Sensitivity | Average latency acceptable | Tail latency critical |
FCFS vs. Optimal Scheduling
To truly understand FCFS's limitations, let's compare it to optimal scheduling—the theoretically best possible ordering for a given request set.
Finding the Optimal Schedule:
The optimal disk scheduling problem is actually the famous Traveling Salesman Problem (TSP) in one dimension. Given $n$ requests and a starting position, find the ordering that minimizes total seek distance.
For one-dimensional TSP (disk scheduling), the optimal solution is known:
- Go to one extreme of the request range
- Traverse toward the other extreme, servicing all requests along the way
The optimal total seek distance for requests spanning from cylinder $min$ to $max$, starting at position $head$, is:
$$D_{optimal} = \max(|head - min| + (max - min), |head - max| + (max - min))$$
Simplified: Go to the nearest extreme first, then sweep to the other.
Comparison Using Our Example:
Given: Head at 50, requests at {11, 34, 62, 64, 95, 119, 123, 180}
FCFS Total Seek: 644 cylinders (as calculated earlier)
Optimal Strategy:
- Min = 11, Max = 180, Head = 50
- Option A: Go to 11 first → (50-11) + (180-11) = 39 + 169 = 208 cylinders
- Option B: Go to 180 first → (180-50) + (180-11) = 130 + 169 = 299 cylinders
- Optimal choice: Option A = 208 cylinders
Efficiency Ratio:
$$\text{Efficiency} = \frac{D_{optimal}}{D_{FCFS}} = \frac{208}{644} = 32.3%$$
FCFS achieves only 32% of optimal efficiency for this workload!
FCFS required 3.1x more head movement than the optimal solution. For a disk with 10ms average seek time, this translates to roughly 4.36 seconds of additional seek time for just 8 requests. At scale (thousands of requests per second), this inefficiency becomes catastrophic.
Why Don't We Use Optimal Scheduling?
If optimal is so much better, why not always use it? Several reasons:
- Starvation: Optimal scheduling (like SSTF) can starve requests at disk extremes indefinitely
- Reordering: Requests may complete out of order, violating application semantics
- Computational Cost: Finding optimal for streaming requests requires constant recalculation
- Predictability: Applications cannot predict when their requests will complete
- Fairness: Some processes may receive dramatically better service than others
The algorithms we'll study in subsequent pages (SSTF, SCAN, C-SCAN, LOOK) represent various tradeoffs between FCFS's fairness guarantees and optimal's efficiency.
KEEP LEARNING
Keep learning for free.
Read the complete lesson, save your notes and pick up where you left off with a free account. No card needed.