Understanding Disk Scheduling: SCAN, LOOK, and SSTF Algorithms

Disk scheduling is a crucial aspect of operating systems, enabling efficient data retrieval from storage devices. With various algorithms available, developers need to understand their workings, advantages, and disadvantages. In this article, we will dive deep into three popular disk scheduling algorithms: SCAN, LOOK, and SSTF.

What is Disk Scheduling?

Disk scheduling refers to the method an operating system uses to determine the order in which disk I/O requests are serviced. Given that multiple processes can compete for disk access simultaneously, an effective scheduling algorithm can significantly enhance overall system performance.

Why is Disk Scheduling Important?

Disk I/O is one of the slowest operations in computing systems. Optimizing the order of access requests reduces latency and increases throughput, resulting in faster application response times. It is especially vital in environments like servers and databases, where disk access patterns can greatly affect performance.

Common Disk Scheduling Algorithms

We will focus on three popular disk scheduling approaches:

• SCAN (Elevator Algorithm)
• LOOK
• SSTF (Shortest Seek Time First)

1. SCAN Algorithm

The SCAN algorithm works similarly to an elevator moving between floors. It scans the disk in one direction and services any pending requests until it reaches the last track, then reverses direction and performs the same operation again.

How SCAN Works

Assume a disk with requests at the following cylinders:

• 95
• 180
• 34
• 119
• 11
• 123

Let’s visualize the disk requests and their processing:

Current Head Position: 50 (Moving Right)

     Direction: Right
     [11]  [95]
                     |
          [119] [123] [180]

In this scenario, the head will first service requests from 50 to 180 and then reverse back to 11.

Advantages of SCAN

• Reduces average wait time compared to FIFO and simpler algorithms.
• Provides a fair distribution of service across all requests.

Disadvantages of SCAN

• Can lead to longer wait times for requests at the edges (e.g., the farthest cylinders).
• The performance heavily relies on the current head position and disk load.

2. LOOK Algorithm

The LOOK algorithm is similar to SCAN but with a key difference: the head does not go all the way to the end of the disk. Instead, it only moves to the furthest request in the current direction and then reverses.

How LOOK Works

Consider the same setup as before, with requests at:

• 95
• 180
• 34
• 119
• 11
• 123

With LOOK, the current head position being 50, the processing would look as follows:

Current Head Position: 50 (Moving Right)

     Direction: Right
     [11]  [95]
                     |
          [119] [123] [180]

Unlike SCAN, the head will only serve up to 180, as no requests exist beyond this point.

Advantages of LOOK

• Improved efficiency as it avoids unnecessary movements to unrequested outer tracks.
• Similar fairness characteristics as SCAN but with faster response times for certain workloads.

Disadvantages of LOOK

• May lead to longer wait times than SCAN for extreme edge requests.
• Less predictable behavior can occur depending on workload distribution.

3. SSTF (Shortest Seek Time First)

SSTF focuses on servicing the nearest disk request next. This minimizes the movement of the disk head and aims to reduce the total seek time.

How SSTF Works

Given the same disk requests:

• 95
• 180
• 34
• 119
• 11
• 123

With a current position of 50, the SSTF algorithm will first pick the request with the shortest distance, which is from 50 to 34:

Current Head Position: 50

Request Sequence:
1. Move to 34
2. Move to 11
3. Move to 95
4. Move to 119
5. Move to 123
6. Move to 180

Advantages of SSTF

• Generally achieves better performance than both SCAN and LOOK in average seek time.
• Simple to implement due to straightforward logic in choosing the next request.

Disadvantages of SSTF

• Can lead to starvation, especially for requests that are further away from the current head position.
• Performance can be heavily affected by the distribution of incoming requests.

Choosing the Right Disk Scheduling Algorithm

The choice of disk scheduling algorithm is influenced by specific workload requirements and system architecture. Here are some guidelines to consider:

• If minimizing average wait time is crucial, consider SSTF.
• For fairness and better performance in varied workloads, SCAN or LOOK may be suitable.
• In systems with predictable read/write patterns, simpler algorithms may suffice.

Conclusion

Disk scheduling is a fundamental aspect that affects system performance, especially in I/O-intensive applications. Understanding the mechanisms behind algorithms like SCAN, LOOK, and SSTF aids developers in optimizing their systems for better efficiency and responsiveness.

Experiment with different algorithms, benchmark their performance in real-world scenarios, and always keep workload characteristics in mind when making your selection. Mastering these concepts will undoubtedly enhance your skills in systems programming and operating system design.