FCFS vs SSTF vs SCAN: Key Differences and When to Use Each

The FCFS (First-Come, First-Served) algorithm processes disk requests in the order they arrive, leading to simple but sometimes inefficient scheduling. SSTF (Shortest Seek Time First) selects the request closest to the current head position, reducing seek time but risking starvation. SCAN moves the disk head in one direction servicing requests until it reaches the end, then reverses, balancing efficiency and fairness.

Quick Comparison

Here is a quick comparison of FCFS, SSTF, and SCAN disk scheduling algorithms based on key factors.

Factor	FCFS	SSTF	SCAN
Scheduling Order	Processes requests in arrival order	Processes closest request next	Moves head in one direction servicing requests
Seek Time Efficiency	Low (can be high)	High (minimizes seek time)	Moderate (systematic scanning)
Starvation Risk	No starvation	Possible starvation for far requests	No starvation
Fairness	Fair (order preserved)	Less fair (prioritizes close requests)	Fair (serves all in direction)
Implementation Complexity	Simple	Moderate	Moderate
Use Case	Simple systems, low overhead	Performance-focused, small queues	Balanced performance and fairness

Key Differences

FCFS is the simplest disk scheduling algorithm that handles requests strictly in the order they arrive. This simplicity means it is easy to implement but can cause long delays if requests are scattered across the disk, leading to high average seek times.

SSTF improves efficiency by always selecting the request closest to the current head position, reducing the movement needed. However, this can cause starvation where requests far from the current head position wait indefinitely if closer requests keep arriving.

SCAN addresses starvation by moving the disk head in one direction, servicing all requests along the way until it reaches the end, then reversing direction. This approach balances seek time efficiency and fairness, ensuring all requests get serviced in a predictable manner.

Code Comparison

Here is a simple Python example demonstrating the FCFS disk scheduling algorithm handling a list of disk requests.

python

def fcfs(requests, head_start):
    seek_sequence = [head_start] + requests
    total_seek = 0
    for i in range(len(seek_sequence) - 1):
        total_seek += abs(seek_sequence[i+1] - seek_sequence[i])
    return total_seek, seek_sequence

# Example usage
requests = [55, 58, 39, 18, 90, 160, 150, 38, 184]
head_start = 50
seek_time, sequence = fcfs(requests, head_start)
print(f"FCFS Total Seek Time: {seek_time}")
print(f"Seek Sequence: {sequence}")

Output

FCFS Total Seek Time: 642
Seek Sequence: [50, 55, 58, 39, 18, 90, 160, 150, 38, 184]

SSTF Equivalent

This Python code shows how the SSTF algorithm selects the closest request to the current head position each time.

python

def sstf(requests, head_start):
    requests = requests.copy()
    seek_sequence = [head_start]
    total_seek = 0
    current_pos = head_start
    while requests:
        closest = min(requests, key=lambda x: abs(x - current_pos))
        total_seek += abs(closest - current_pos)
        current_pos = closest
        seek_sequence.append(closest)
        requests.remove(closest)
    return total_seek, seek_sequence

# Example usage
requests = [55, 58, 39, 18, 90, 160, 150, 38, 184]
head_start = 50
seek_time, sequence = sstf(requests, head_start)
print(f"SSTF Total Seek Time: {seek_time}")
print(f"Seek Sequence: {sequence}")

Output

SSTF Total Seek Time: 236
Seek Sequence: [50, 55, 58, 39, 38, 18, 90, 150, 160, 184]

When to Use Which

Choose FCFS when simplicity and fairness are priorities, and the request load is low or predictable, as it is easy to implement but can be inefficient.

Choose SSTF when you want to minimize seek time and improve performance in systems with moderate request loads, but be aware of possible starvation for distant requests.

Choose SCAN when you need a balanced approach that avoids starvation and provides more predictable service times, especially in systems with heavy or continuous disk requests.

Key Takeaways

FCFS is simple and fair but can cause high seek times due to processing requests in arrival order.

SSTF reduces seek time by choosing the nearest request but risks starving far requests.

SCAN moves the head in one direction servicing all requests, balancing efficiency and fairness.

Use FCFS for simplicity, SSTF for performance with small queues, and SCAN for balanced, fair scheduling.

Understanding these algorithms helps optimize disk performance based on workload and fairness needs.