Disk Scheduling Algorithms: FCFS, SSTF, SCAN, C-SCAN - Complete Implementation Guide

Disk scheduling algorithms are fundamental components of operating systems that determine the order in which disk I/O requests are processed. These algorithms significantly impact system performance by minimizing seek time and optimizing data access patterns. Understanding these algorithms is crucial for system administrators, developers, and anyone working with storage systems.

Table of Contents

Understanding Disk Scheduling Fundamentals

Before diving into specific algorithms, it’s essential to understand the physical structure of a disk drive. A hard disk consists of multiple platters with read/write heads that move across tracks to access data. The seek time – the time required to move the head to the correct track – is typically the most significant factor in disk access time.

Disk scheduling algorithms aim to:

Minimize total seek time
Maximize throughput
Ensure fairness among requests
Prevent starvation of requests

First-Come, First-Served (FCFS) Algorithm

FCFS is the simplest disk scheduling algorithm that processes requests in the order they arrive. While easy to implement and inherently fair, it doesn’t optimize for seek time reduction.

How FCFS Works

The algorithm maintains a queue of disk requests and processes them sequentially without considering the current head position or the physical location of requested tracks.

FCFS Implementation Example

Let’s consider a disk with 200 tracks (0-199) and the following request sequence:

Request Queue: 98, 183, 37, 122, 14, 124, 65, 67

Initial Head Position: 53

Step	Current Track	Next Request	Seek Distance	Total Seek Time
1	53	98	45	45
2	98	183	85	130
3	183	37	146	276
4	37	122	85	361
5	122	14	108	469
6	14	124	110	579
7	124	65	59	638
8	65	67	2	640

Total Seek Time: 640 units

Average Seek Time: 640/8 = 80 units per request

FCFS Advantages and Disadvantages

Advantages:

Simple to implement and understand
Fair to all requests (no starvation)
Low overhead

Disadvantages:

High average seek time
Poor performance with random access patterns
No optimization for disk head movement

Shortest Seek Time First (SSTF) Algorithm

SSTF selects the request with the minimum seek time from the current head position. This greedy approach significantly reduces total seek time compared to FCFS but may cause starvation of requests located far from the current position.

SSTF Implementation Example

Using the same request queue and initial position:

Request Queue: 98, 183, 37, 122, 14, 124, 65, 67

Initial Head Position: 53

Step	Current Track	Available Requests	Closest Request	Seek Distance	Total Seek Time
1	53	98, 183, 37, 122, 14, 124, 65, 67	65	12	12
2	65	98, 183, 37, 122, 14, 124, 67	67	2	14
3	67	98, 183, 37, 122, 14, 124	98	31	45
4	98	183, 37, 122, 14, 124	122	24	69
5	122	183, 37, 14, 124	124	2	71
6	124	183, 37, 14	183	59	130
7	183	37, 14	37	146	276
8	37	14	14	23	299

Total Seek Time: 299 units

Average Seek Time: 299/8 = 37.4 units per request

SSTF Advantages and Disadvantages

Advantages:

Better average response time than FCFS
Reduced total seek time
Good performance for localized access patterns

Disadvantages:

Potential starvation of distant requests
Not optimal in all cases
Unfair to requests at disk extremes

SCAN Algorithm (Elevator Algorithm)

The SCAN algorithm moves the disk head in one direction, servicing all requests in its path until it reaches the end of the disk, then reverses direction. This approach eliminates starvation while maintaining reasonable seek times.

SCAN Implementation Example

Assuming the head is moving toward higher tracks initially:

Request Queue: 98, 183, 37, 122, 14, 124, 65, 67

Initial Head Position: 53 (moving right)

Disk Size: 0-199

Sorted requests by track number: 14, 37, 65, 67, 98, 122, 124, 183

Step	Current Track	Next Request	Seek Distance	Total Seek Time	Direction
1	53	65	12	12	Right
2	65	67	2	14	Right
3	67	98	31	45	Right
4	98	122	24	69	Right
5	122	124	2	71	Right
6	124	183	59	130	Right
7	183	199 (end)	16	146	Right
8	199	37	162	308	Left
9	37	14	23	331	Left

Total Seek Time: 331 units

Average Seek Time: 331/8 = 41.4 units per request

SCAN Advantages and Disadvantages

Advantages:

Eliminates starvation
Good for systems with heavy disk usage
Predictable access patterns
Better than FCFS for most scenarios

Disadvantages:

Requests at disk extremes may wait longer
Head movement to disk ends even without requests
Not always optimal for seek time

Circular SCAN (C-SCAN) Algorithm

C-SCAN improves upon SCAN by treating the disk as circular. After reaching one end, the head immediately returns to the other end and continues in the same direction, providing more uniform wait times.

C-SCAN Implementation Example

Using the same scenario with head moving toward higher tracks:

Request Queue: 98, 183, 37, 122, 14, 124, 65, 67

Initial Head Position: 53 (moving right)

Step	Current Track	Next Request	Seek Distance	Total Seek Time	Direction
1	53	65	12	12	Right
2	65	67	2	14	Right
3	67	98	31	45	Right
4	98	122	24	69	Right
5	122	124	2	71	Right
6	124	183	59	130	Right
7	183	199 (end)	16	146	Right
8	199	0 (start)	199	345	Jump
9	0	14	14	359	Right
10	14	37	23	382	Right

Total Seek Time: 382 units

Average Seek Time: 382/8 = 47.8 units per request

C-SCAN Advantages and Disadvantages

Advantages:

More uniform wait times than SCAN
Better for requests distributed across the disk
Eliminates the bias against requests at disk ends
Predictable performance characteristics

Disadvantages:

Higher seek time due to head return
More complex implementation
May not be optimal for clustered requests

Performance Comparison and Analysis

Let’s compare the performance of all four algorithms using our example:

Algorithm	Total Seek Time	Average Seek Time	Best Use Case
FCFS	640 units	80 units	Light disk usage, fairness critical
SSTF	299 units	37.4 units	Localized access patterns
SCAN	331 units	41.4 units	Heavy disk usage, mixed patterns
C-SCAN	382 units	47.8 units	Uniform access distribution

Algorithm Selection Guidelines

Choose the appropriate algorithm based on your system requirements:

FCFS: Use when fairness is more important than performance, or for systems with light disk usage
SSTF: Ideal for applications with localized data access patterns and where some starvation is acceptable
SCAN: Best for general-purpose systems with moderate to heavy disk usage
C-SCAN: Optimal for systems requiring uniform response times across all disk locations

Real-World Considerations

Modern storage systems often implement hybrid approaches that consider:

Request priorities: Critical system requests may bypass normal scheduling
Deadline scheduling: Ensuring requests complete within time limits
Anticipatory scheduling: Briefly waiting for nearby requests before moving the head
SSD considerations: Solid-state drives don’t have mechanical seek times, changing optimization strategies

Implementation Tips and Best Practices

When implementing disk scheduling algorithms:

Monitor system performance: Use metrics like average seek time, throughput, and request latency
Consider workload patterns: Database systems may benefit from different algorithms than web servers
Implement adaptive scheduling: Switch algorithms based on current load and access patterns
Account for modern hardware: NCQ (Native Command Queuing) in SATA drives provides hardware-level optimization
Test thoroughly: Benchmark different algorithms with realistic workloads

Understanding disk scheduling algorithms is crucial for optimizing system performance and ensuring efficient resource utilization. Each algorithm offers distinct advantages and trade-offs, making the choice dependent on specific system requirements, workload characteristics, and performance goals. As storage technology continues to evolve, these fundamental concepts remain relevant for system designers and administrators seeking to maximize storage efficiency.