FCFS Scheduling - Disk Scheduling Algorithms | OneNoughtOne

0/236

Operating SystemsDisk Scheduling Algorithms

Disk Scheduling Algorithms

LevelIntermediate

Duration90 mins

TopicDisk Scheduling Algorithms

1 / 5

FCFS Scheduling

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?

What You Will Learn

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:

Components of Disk Access Time
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

Why Seek Time Dominates

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.

fcfs_scheduler.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
"""
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 dataclass
from collections import deque
from typing import List, Tuple
import time
 
@dataclass
class 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 behavior
def 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()

Implementation Insight

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

FCFS Execution Trace
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!

Converting Mermaid diagram...

The Cost of Randomness

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}$$

Practical Implication

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.

FCFS Performance Characteristics by Workload Type
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:

Strengths of FCFS

•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

Weaknesses of FCFS

•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.

The Convoy Effect

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:

Appropriate Use Cases for FCFS

•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.

Modern Context: SSDs Change the Game

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.

FCFS Decision Matrix
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!

The Performance Gap

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.

Summary: FCFS Disk Scheduling

We have thoroughly examined First-Come, First-Served disk scheduling. Let's consolidate the key concepts:

Key Takeaways

•FCFS services requests in arrival order—simple FIFO queue with no reordering
•Seek time dominates disk access latency and is the primary optimization target for disk scheduling
•Expected seek distance is N/3 for uniform random requests on an N-cylinder disk
•FCFS is starvation-free but suffers from convoy effects and poor average performance
•FCFS can be 3-5x less efficient than optimal scheduling for random workloads
•FCFS is appropriate for SSDs, low-load systems, and fairness-critical applications
•Modern storage (NVMe) reduces the importance of seek optimization, making FCFS more viable

What's Next:

FCFS establishes our baseline and reveals the inefficiency of random ordering. In the next page, we'll study SSTF (Shortest Seek Time First)—an algorithm that greedily minimizes seek distance at each step. You'll see how SSTF dramatically improves throughput but introduces the critical problem of starvation.

Page Complete

You now understand FCFS disk scheduling at an expert level—its algorithm, performance characteristics, mathematical behavior, and appropriate use cases. This foundation enables you to evaluate all subsequent scheduling algorithms against a clear baseline.

Operating SystemsDisk Scheduling Algorithms

Disk Scheduling Algorithms

LevelIntermediate

Duration90 mins

TopicDisk Scheduling Algorithms

1 / 5

FCFS Scheduling

The Disk Access Problem

The fundamental question disk scheduling algorithms answer is: In what order should pending I/O requests be serviced to optimize performance?

What You Will Learn

Understanding Disk Access Time

Total Disk Access Time consists of three components:

$$T_{access} = T_{seek} + T_{rotation} + T_{transfer}$$

Let's examine each component in detail:

Components of Disk Access Time
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

Why Seek Time Dominates

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

fcfs_scheduler.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
"""
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 dataclass
from collections import deque
from typing import List, Tuple
import time
 
@dataclass
class 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 behavior
def 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()

Implementation Insight

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

FCFS Execution Trace
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}$$

Converting Mermaid diagram...

The Cost of Randomness

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}$$

Practical Implication

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.

FCFS Performance Characteristics by Workload Type
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:

Strengths of FCFS

•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

Weaknesses of FCFS

•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:

$$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.

The Convoy Effect

When to Use FCFS

Despite its inefficiencies, FCFS remains appropriate in specific scenarios:

Appropriate Use Cases for FCFS

•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.

Modern Context: SSDs Change the Game

FCFS Decision Matrix
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:

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!

The Performance Gap

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.

Summary: FCFS Disk Scheduling

We have thoroughly examined First-Come, First-Served disk scheduling. Let's consolidate the key concepts:

Key Takeaways

•FCFS services requests in arrival order—simple FIFO queue with no reordering
•Seek time dominates disk access latency and is the primary optimization target for disk scheduling
•Expected seek distance is N/3 for uniform random requests on an N-cylinder disk
•FCFS is starvation-free but suffers from convoy effects and poor average performance
•FCFS can be 3-5x less efficient than optimal scheduling for random workloads
•FCFS is appropriate for SSDs, low-load systems, and fairness-critical applications
•Modern storage (NVMe) reduces the importance of seek optimization, making FCFS more viable

What's Next:

Page Complete