Disk scheduling refers to the method used by an operating system to determine the order in which disk I/O requests are processed.
Whenever a program needs to read or write data, it sends a request to the operating system. These requests are stored in a disk request queue. Since multiple processes may request disk access simultaneously, the OS must schedule them in a way that minimizes delays. Operating System Concepts
Definition
Disk scheduling refers to a process of the operating system that identifies the sequence in which disk input/output requests are handled to optimise performance and spend less time accessing disk.
The use of disk scheduling in Hard Disk drives (HDDs) is quite significant since devices are based on mechanical materials like a spinning platter and a travelling head of read/write.
Why Disk Scheduling is Important
Disk access is significantly slower than CPU or memory operations. Poor scheduling can lead to excessive disk head movement, which increases access time.
Proper disk scheduling helps achieve the following goals:
1. Reduce Seek Time
Seek time refers to the time taken by the disk head to move from one track to another.
2. Improve System Throughput
Efficient scheduling increases the number of disk operations completed per second.
3. Reduce Waiting Time
Processes spend less time waiting for disk operations to finish.
4. Ensure Fairness
All processes should eventually get access to the disk without starvation.
5. Improve Response Time
Faster disk access improves overall system responsiveness.
Components of Disk Access Time
Before understanding scheduling algorithms, it is useful to understand the factors affecting disk performance.
| Component | Description |
| Seek Time | Time taken for the disk head to move to the correct track |
| Rotational Latency | Time waiting for the desired sector to rotate under the disk head |
| Transfer Time | Time required to transfer data between disk and memory |
| Controller Overhead | Time taken by the disk controller to process commands |
Among these, seek time is usually the largest factor, which is why disk scheduling algorithms mainly focus on minimizing it.
Types of Disk Scheduling Algorithms
Several disk scheduling algorithms have been developed over time to improve performance. The most commonly used ones include:
- FCFS (First Come First Serve)
- SSTF (Shortest Seek Time First)
- SCAN Algorithm
- C-SCAN (Circular SCAN)
- LOOK Algorithm
- C-LOOK Algorithm
Each algorithm approaches the scheduling problem differently.
FCFS (First Come First Serve) Disk Scheduling
FCFS is the simplest disk scheduling algorithm. As the name suggests, requests are processed in the exact order they arrive.
The operating system maintains a queue of disk requests, and the first request in the queue is serviced first.
How FCFS Works
Imagine the disk head is currently at cylinder 50, and the request queue is:
95, 180, 34, 119, 11, 123, 62, 64
The disk head services the requests in this exact order.
Advantages of FCFS
- Very simple to implement
- Fair to processes based on arrival order
- No starvation occurs
Disadvantages of FCFS
- Can result in very large head movements
- High average seek time
- Poor performance when requests are scattered across the disk
Example Table
| Step | Current Head Position | Next Request | Movement |
| 1 | 50 | 95 | 45 |
| 2 | 95 | 180 | 85 |
| 3 | 180 | 34 | 146 |
| 4 | 34 | 119 | 85 |
This shows how inefficient the algorithm can become.
SSTF (Shortest Seek Time First)
The Shortest Seek Time First (SSTF) algorithm improves upon FCFS by selecting the request closest to the current head position.
Instead of following arrival order, the algorithm always chooses the request that requires the least head movement.
How SSTF Works
If the head is at cylinder 50, and the queue contains:
95, 180, 34, 119, 11, 123, 62, 64
The closest request is 62, so the disk head moves there first.
After servicing that request, the algorithm again selects the nearest remaining request.
Advantages
- Reduces total head movement
- Improves overall performance
- Faster than FCFS in most cases
Disadvantages
- Can cause starvation
- Requests far from the current head position may wait indefinitely
Example Table
| Current Head | Closest Request | Movement |
| 50 | 62 | 12 |
| 62 | 64 | 2 |
| 64 | 34 | 30 |
| 34 | 11 | 23 |
The algorithm continues until all requests are serviced.
SCAN Algorithm
The SCAN algorithm is often compared to the movement of an elevator.
The disk head moves in one direction, servicing requests along the way. When it reaches the end of the disk, it reverses direction and services requests on the way back.
This approach ensures that all requests eventually get serviced.
How SCAN Works
If the disk head starts moving toward higher-numbered cylinders:
- Service requests in ascending order
- Continue until reaching the disk end
- Reverse direction
- Service remaining requests
Advantages
- Better performance than FCFS and SSTF
- Reduces starvation
- Provides more predictable wait times
Disadvantages
- Requests at the ends of the disk may wait longer
- Some unnecessary movement may occur
C-SCAN (Circular SCAN) Algorithm
The C-SCAN algorithm improves upon SCAN by moving the disk head in one direction only.
Once the head reaches the end of the disk, it quickly returns to the beginning without servicing requests during the return movement.
This creates a circular scanning pattern.
How C-SCAN Works
- The disk head moves in one direction
- It services all requests along that path
- When it reaches the end, it jumps back to the start
- The process continues
Advantages
- Provides more uniform waiting time
- Fairer distribution of service across disk cylinders
- Prevents long delays for requests near disk ends
Disadvantages
- Additional movement during the jump back to the start
- Slightly more complex than SCAN
LOOK Disk Scheduling Algorithm
The LOOK algorithm is an improved version of SCAN.
Instead of moving the disk head all the way to the end of the disk, the head only moves as far as the last request in that direction.
Once the last request is serviced, the head reverses direction.
Why LOOK is Efficient
In SCAN, the disk head may travel to the disk’s end even if no requests exist there. LOOK avoids this unnecessary movement.
Advantages
- Reduces unnecessary head movement
- Faster than SCAN in many situations
- Improves efficiency
Disadvantages
- Slightly more complex to implement than SCAN
C-LOOK Algorithm
C-LOOK is the circular version of the LOOK algorithm.
Instead of going to the disk end, the head moves only up to the last request in the current direction, then jumps back to the first request at the other end.
Benefits of C-LOOK
- Eliminates unnecessary disk movement
- Provides balanced waiting times
- Improves efficiency compared to C-SCAN
Comparison of Disk Scheduling Algorithms
The following table summarizes the major differences between disk scheduling algorithms.
| Algorithm | Strategy | Performance | Starvation | Complexity |
| FCFS | Processes requests in arrival order | Low | No | Very Simple |
| SSTF | Chooses nearest request | High | Possible | Moderate |
| SCAN | Moves head like an elevator | Good | Rare | Moderate |
| C-SCAN | Circular scanning | Very Good | Rare | Moderate |
| LOOK | SCAN but stops at last request | Better | Rare | Moderate |
| C-LOOK | Circular LOOK | Best efficiency | Rare | Moderate |
Disk Scheduling Example Comparison
| Algorithm | Average Seek Time | Fairness | Efficiency |
| FCFS | High | Good | Low |
| SSTF | Low | Poor | High |
| SCAN | Moderate | Good | High |
| C-SCAN | Moderate | Very Good | High |
| LOOK | Low | Good | Very High |
| C-LOOK | Lowest | Very Good | Very High |
Disk Scheduling in Modern Operating Systems
While the classical algorithms discussed above are widely taught in operating system courses, modern operating systems often use more advanced hybrid algorithms.
Examples include:
- Deadline Scheduler
- Completely Fair Queuing (CFQ)
- NOOP Scheduler
These algorithms consider additional factors such as:
- Request priority
- Process fairness
- SSD optimization
- Parallel disk operations
With the rise of Solid State Drives (SSDs), disk scheduling has evolved because SSDs do not suffer from mechanical seek delays like HDDs.
However, the fundamental concepts of disk scheduling remain important for understanding operating system design.
Key Advantages of Disk Scheduling
Disk scheduling offers several significant benefits for operating system performance.
1. Improved Disk Efficiency
Proper scheduling reduces unnecessary disk head movement.
2. Faster Data Access
Processes can retrieve data more quickly.
3. Increased System Throughput
More disk operations can be completed in a given time.
4. Reduced System Bottlenecks
Efficient disk management prevents delays in system processes.
5. Better Resource Utilization
Disk hardware resources are used more effectively.
Challenges in Disk Scheduling
Despite its benefits, disk scheduling also presents certain challenges.
- Balancing fairness and performance
- Preventing starvation of certain requests
- Handling real-time applications
- Managing modern storage technologies
Designing a scheduling algorithm that satisfies all requirements remains a complex task.
Final Thought
Disk scheduling algorithms form a very crucial component of operating system design. They define the sequence in which disk requests will be sequenced and processed which has direct influence on the performance and efficiency of the system. Although recent storage technologies transformed the nature of disk access, the original concepts of disk scheduling remain extremely important in system optimisation and resource management.
Also Read: https://www.easytechtrends.com
