Disk Scheduling Algorithms

Category: Advanced Operating System Concepts
Type: Operating System Concept
Generated on: 2025-07-10 03:02:42
For: System Administration, Development & Technical Interviews

Disk Scheduling Algorithms: A Comprehensive Cheatsheet

1. Quick Overview

Disk scheduling algorithms optimize the order in which disk I/O requests are serviced. Why is this important? Because disk access is significantly slower than memory access. Efficiently scheduling requests minimizes seek time (moving the disk arm), rotational latency (waiting for the sector to rotate under the head), and overall response time, leading to improved system performance. Poor disk scheduling can become a major bottleneck.

2. Key Concepts

Seek Time: The time taken to move the disk head to the desired track (cylinder). This is the dominant factor.
Rotational Latency: The time taken for the desired sector to rotate under the disk head.
Transfer Time: The time taken to transfer data to/from the disk. (relatively small compared to seek time)
Disk Request Queue: A list of pending requests (cylinder numbers) waiting to be serviced.
Head Position: The current cylinder number where the disk head is located.
I/O Request: A request to read or write data at a specific cylinder/sector.
Throughput: The number of requests serviced per unit of time.
Response Time: The time taken to service a request from submission to completion.
Fairness: Ensuring that all requests are serviced eventually and that no request is starved.

3. How It Works (Step-by-Step Explanations with Diagrams)

Let’s assume the following:

Disk Head is currently at cylinder 50.
Disk has cylinders numbered 0 to 199.
Request Queue: 95, 180, 34, 119, 11, 123, 62, 64 (represents the order of requests arriving)

Here’s how different algorithms handle this:

A. First-Come, First-Served (FCFS)

Concept: Serves requests in the order they arrive.
Simple, but not efficient.

Head Start: 50
Request Queue: 95, 180, 34, 119, 11, 123, 62, 64

Movement:  50 -> 95 -> 180 -> 34 -> 119 -> 11 -> 123 -> 62 -> 64

Total Head Movement: |95-50| + |180-95| + |34-180| + |119-34| + |11-119| + |123-11| + |62-123| + |64-62|
                   = 45 + 85 + 146 + 85 + 108 + 112 + 61 + 2
                   = 644 cylinders

B. Shortest Seek Time First (SSTF)

Concept: Selects the request closest to the current head position, regardless of arrival order.
Minimizes seek time, but can lead to starvation.

Head Start: 50
Request Queue: 95, 180, 34, 119, 11, 123, 62, 64

Movement: 50 -> 62 -> 64 -> 34 -> 11 -> 95 -> 119 -> 123 -> 180

Total Head Movement: |62-50| + |64-62| + |34-64| + |11-34| + |95-11| + |119-95| + |123-119| + |180-123|
                   = 12 + 2 + 30 + 23 + 84 + 24 + 4 + 57
                   = 236 cylinders

C. SCAN (Elevator Algorithm)

Concept: The disk arm moves in one direction, servicing all requests in its path. When it reaches the end of the disk, it reverses direction and continues servicing requests.
Provides better uniformity than SSTF.

Let’s assume the arm is moving towards 199 (higher cylinder numbers).

Head Start: 50 (moving towards 199)
Request Queue: 95, 180, 34, 119, 11, 123, 62, 64

Movement: 50 -> 62 -> 64 -> 95 -> 119 -> 123 -> 180 -> 199 -> 11 -> 34

Total Head Movement: |62-50| + |64-62| + |95-64| + |119-95| + |123-119| + |180-123| + |199-180| + |11-199| + |34-11|
                   = 12 + 2 + 31 + 24 + 4 + 57 + 19 + 188 + 23
                   = 360 cylinders

D. C-SCAN (Circular SCAN)

Concept: Similar to SCAN, but when the arm reaches the end of the disk, it immediately returns to the beginning (without servicing any requests) and starts scanning again.
Provides even more uniform wait times than SCAN.

Let’s assume the arm is moving towards 199 (higher cylinder numbers).

Head Start: 50 (moving towards 199)
Request Queue: 95, 180, 34, 119, 11, 123, 62, 64

Movement: 50 -> 62 -> 64 -> 95 -> 119 -> 123 -> 180 -> 199 -> 0 -> 11 -> 34

Total Head Movement: |62-50| + |64-62| + |95-64| + |119-95| + |123-119| + |180-123| + |199-180| + |0-199| + |11-0| + |34-11|
                   = 12 + 2 + 31 + 24 + 4 + 57 + 19 + 199 + 11 + 23
                   = 382 cylinders

E. LOOK and C-LOOK

Concept: Optimized versions of SCAN and C-SCAN. Instead of going all the way to the end of the disk, the arm reverses direction or returns to the beginning only when there are no more requests to service in the current direction.

Let’s assume the arm is moving towards 199 (higher cylinder numbers).

LOOK:

Head Start: 50 (moving towards 199)
Request Queue: 95, 180, 34, 119, 11, 123, 62, 64

Movement: 50 -> 62 -> 64 -> 95 -> 119 -> 123 -> 180 -> 11 -> 34

Total Head Movement: |62-50| + |64-62| + |95-64| + |119-95| + |123-119| + |180-123| + |11-180| + |34-11|
                   = 12 + 2 + 31 + 24 + 4 + 57 + 169 + 23
                   = 322 cylinders

C-LOOK:

Head Start: 50 (moving towards 199)
Request Queue: 95, 180, 34, 119, 11, 123, 62, 64

Movement: 50 -> 62 -> 64 -> 95 -> 119 -> 123 -> 180 -> 11 -> 34

Total Head Movement: |62-50| + |64-62| + |95-64| + |119-95| + |123-119| + |180-123| + |11-180| + |34-11|
                   = 12 + 2 + 31 + 24 + 4 + 57 + 169 + 23
                   = 322 cylinders

Summary Table

Algorithm	Description	Advantages	Disadvantages
FCFS	Serves requests in arrival order	Simple to implement	Inefficient, high variance in response time
SSTF	Serves the nearest request	Minimizes seek time	Can lead to starvation, high variance in response time
SCAN	Arm moves in one direction, then reverses	More uniform response time than SSTF	Long seek times at the edges
C-SCAN	Arm moves in one direction, then returns to the beginning	More uniform response time than SCAN	Longer average seek time than SCAN
LOOK	SCAN optimized - reverses direction only when no requests in current direction	More efficient than SCAN	Still favors requests in the middle cylinders
C-LOOK	C-SCAN optimized - returns to the beginning when no requests in current direction	More efficient than C-SCAN	Still favors requests in the middle cylinders

4. Real-World Examples

Database Servers: Databases rely heavily on disk I/O. SSTF, SCAN, or LOOK can significantly improve query performance by minimizing seek times.
Operating Systems: Operating systems use disk scheduling algorithms to manage virtual memory paging and file access.
Video Streaming: Efficient disk scheduling is crucial for smooth video playback, especially for high-resolution content. SCAN and LOOK are often used.
RAID Arrays: RAID systems benefit from optimized disk scheduling to improve overall performance and reliability.
Embedded Systems: Devices with limited resources need efficient disk scheduling to conserve power and improve response times.

5. Common Issues

Starvation: SSTF can lead to starvation if requests for cylinders far from the current head position are continuously arriving.
High Variance in Response Time: FCFS and SSTF can have a wide range of response times, making them unsuitable for real-time applications.
Overhead: Implementing complex algorithms like SCAN and C-SCAN can introduce some overhead, especially on low-powered devices.
Choosing the Right Algorithm: The optimal algorithm depends on the workload and system requirements. No single algorithm is always the best. Profiling and monitoring are essential.
Disk Fragmentation: Disk fragmentation can negate the benefits of disk scheduling algorithms by increasing seek times. Regular defragmentation is important.

Troubleshooting Tips:

Monitor Disk I/O: Use system monitoring tools to track disk utilization, seek times, and response times.
Profile Workloads: Analyze the disk access patterns of your applications to identify potential bottlenecks.
Experiment with Different Algorithms: Test different algorithms to see which one performs best for your specific workload.
Consider Disk Defragmentation: Regularly defragment your disks to reduce seek times.
Upgrade to SSDs: Solid-state drives (SSDs) have no moving parts and are much faster than traditional hard drives. They eliminate the need for disk scheduling algorithms in many cases.

6. Interview Questions

Q1: Explain the difference between SCAN and C-SCAN disk scheduling algorithms.

A: SCAN moves the disk arm in one direction, servicing all requests, and then reverses direction. C-SCAN moves in one direction, services requests, and then immediately returns to the beginning of the disk without servicing any requests on the return trip. C-SCAN provides more uniform wait times.

Q2: What is starvation in the context of disk scheduling, and which algorithm is most prone to it?

A: Starvation occurs when a request is indefinitely delayed and never serviced. SSTF is most prone to starvation because it always chooses the nearest request, potentially ignoring requests that are far away.

Q3: Compare and contrast FCFS and SSTF disk scheduling algorithms.

A: FCFS is simple and serves requests in arrival order, but it can be very inefficient. SSTF minimizes seek time by serving the nearest request, but it can lead to starvation. FCFS is fair, but SSTF aims for higher throughput (at the expense of fairness).

Q4: Why are LOOK and C-LOOK considered improvements over SCAN and C-SCAN?

A: LOOK and C-LOOK are optimized versions of SCAN and C-SCAN. They improve efficiency by reversing direction or returning to the beginning only when there are no more requests to service in the current direction. This avoids unnecessary head movement to the physical end of the disk.

Q5: If you have a system where fairness is paramount, which disk scheduling algorithm would you choose and why?

A: FCFS (First-Come, First-Served) would be the most appropriate choice. While it may not be the most efficient in terms of minimizing seek time, it guarantees that each request is serviced in the order it arrived, preventing starvation and ensuring fairness. However, consider if performance is acceptable with FCFS, as other algorithms with modifications for fairness could be considered.

Q6: How does an SSD affect the relevance of disk scheduling algorithms?

A: SSDs have no moving parts and offer near-instantaneous access times compared to HDDs. This significantly reduces or eliminates the need for disk scheduling algorithms, as seek time and rotational latency are no longer major performance bottlenecks. However, some internal flash management within SSDs might benefit from scheduling, but the impact is much less pronounced.

Q7: Imagine you’re designing a database server. Which disk scheduling algorithm would you favor, and why?

A: SSTF, LOOK, or C-LOOK would be good choices. Database servers often have a high volume of disk I/O requests. Minimizing seek time is crucial for query performance. SSTF is a good starting point, but LOOK or C-LOOK might be preferred to mitigate the risk of starvation. Regular workload profiling is essential to fine-tune the choice.

7. Further Reading

Operating System Concepts (Silberschatz, Galvin, Gagne): A classic textbook with detailed coverage of disk scheduling.
Modern Operating Systems (Andrew S. Tanenbaum): Another excellent resource for understanding operating system principles.
Kernel Documentation: Explore the source code and documentation of your operating system’s disk scheduler.
Research Papers: Search for research papers on disk scheduling algorithms for more advanced topics and recent developments.
Online Forums and Communities: Participate in online forums and communities to learn from other developers and system administrators.