Key Takeaways From the Blog
- Disk scheduling works to lessen the movement of the disk arm resulting in less seek time and faster system performance.
- The words that are most often used in the context of disk scheduling are seek time, rotational latency, transfer time, disk access time, and starvation.
- On the one hand, there are algorithms such as FCFS that are very simple but inefficient. On the other hand, there are algorithms such as SSTF which reduce seek time but can starve far requests.
- FCFS is a very primitive algorithm which just puts the requests in the order in which they were received. SSTF selects the request that is closest to the current position of the disk head thus reducing seek time.
- SCAN and C-SCAN achieve perfection by continuing the movement in only one direction thus saving time that could be wasted when the disk head moves from one end to the other.
- LOOK and C-LOOK are even more perfect versions of SCAN since the disk head doesn't have to go all the way to the end.
Introduction
Disk scheduling in an operating system (OS) is required to make disk drive operation as efficient as possible. As there is more than one process involved in current systems, all of which attempt to access the disk, disk scheduling algorithms assist in queuing these requests to optimise disk access. Disk scheduling attempts to reduce the time spent by the read/write head of the disk traveling, which improves the overall system performance. The algorithms can lead to less waiting time and an active system.
This article will discuss disk scheduling algorithms in operating systems, types and examples with advantages and disadvantages.
What Are Disk Scheduling Algorithms in OS?
Disk scheduling algorithms control the sequence of disk I/O (input/output) requests being executed. The fundamental concept is to reduce disk arm movement so that it serves all the requests with minimum overhead. Essentially, these algorithms decide the order of operation or the path through which the disk access requests are executed.
Disk scheduling is important because the hard disk is one of the slower devices in the system, particularly relative to the CPU and memory. As a result, effectively managing how and when data is read or written to disk can impact system performance. Disk scheduling prevents these I/O requests from being serviced in a manner that will cause delays and reduce throughput.
Quick Note: Disk scheduling is essential because disk access is slow; optimizing request order significantly improves overall OS performance.
Key Terms of Disk Scheduling in Operating Systems
Disk scheduling is a method that deals with how the requests for disk input/output are carried out to achieve the highest performance. The following are the essential terms related to disk scheduling:
1. Seek Time
Seek time is the time that the disk arm is being moved to the track which has the required data. It is the main factor of disk performance and the most important parameter in the development of disk access.
2. Rotational Latency
At rotational latency, the read/write head is waiting for the arrival of the desired sector. In order to reduce the rotational latency to a minimal value, it is necessary to have high disk speeds, which therefore leads to an overall improvement of the disk efficiency and the data-accessing speed.
3. Transfer Time
Transfer time is the time that is taken for the data to be moved to memory after the read/write head is positioned. Generally, it is less than the seek time and the rotational latency.
4. Disk Access Time
Disk access time is the sum of time consumed by a disk operation, i.e., seek time, rotational latency, and transfer time. It shows the effectiveness of reading data from a disk.
5. Disk Response Time
Disk response time is a request's average wait time to complete its I/O operation. Reduced response times mean superior scheduling and better system performance.
6. Starvation
Starvation is when a request has to wait forever because other requests are always serviced with a higher priority. Disk scheduling algorithms prevent starvation by ensuring each request has an equal opportunity.
Key Takeaways So Far
- Seek time is the most expensive component.
- Response time depends on both queue order and head movement.
- Starvation must be considered when evaluating fairness.
Types of Disk Scheduling Algorithms in OS
Several disk scheduling algorithms are designed to optimize different aspects of disk access. Below are some of the most common disc scheduling algorithms:
1. FCFS Disk Scheduling Algorithm
The FCFS disk scheduling algorithm serves disk access requests based on their arrival time, regardless of their physical location on the disk. The earliest arrived request is served first, making it one of the simplest and easiest-to-implement scheduling algorithms.
Example
We have a disk containing 200 tracks (track 0 to track 199). The request sequence is (60, 150, 25, 130, 80, 10, 190). The disk head's initial position is 50.
Explanation
In the FCFS (First Come, First Serve) disk scheduling algorithm, the disk arm goes through each request in their arrival order, not moving the head optimally.
- The disk arm is at position 50 initially.
- It initially arrives at request 60, then at 150, then at 25, and so on, depending upon the arrival sequence.
- The disk arm processes all requests in order of arrival, without reordering.
Seek Time Calculation
Seek time is computed as the sum of the absolute differences of the current disk head position and the target track.
Seek Time = (60−50)+(150−60)+(150−25)+(130−25)+(130−80)+(80−10)+(190−10)
=10+90+125+105+50+70+180
= 630
Advantages
Here are the advantages of fcfs disk scheduling:
- Easy to implement.
- Equitable to every request.
- No complicated calculation is needed.
- No starvation risk.
- Easy to predict as the requests are serviced in arrival order.
Disadvantages
Here are the disadvantages of fcfs disk scheduling:
- Seek time is significantly increased, particularly if requests are distant.
- Inefficient because it fails to minimize head movement.
- Increased waiting time for distant requests from the head.
- It disregards the request's position.
- It can lead to performance bottlenecks when numerous requests exist.
Quick Note: FCFS processes requests strictly by arrival order, making it fair but extremely inefficient when requests are physically far apart.
2. SSTF Disk Scheduling Algorithm
The SSTF disk scheduling algorithm chooses the closest request to the disk arm's current location. The disk arm moves to the closest requested track and, when it completes, moves to the next closest request. SSTF always chooses the closest request and, therefore, minimizes the seek time.
Example
Suppose the same 200-track disk (0-199). The order of requests is: (60, 150, 25, 130, 80, 10, 190). The head's initial position is 50.
Explanation
In the SSTF algorithm, the disk arm travels to the request nearest to its current position, reducing seek time per move.
- The disk arm begins at 50.
- The nearest request is 60, so it travels to 60.
- From 60, the subsequent nearest request is 80.
- Once 80 has been served, the next request is 130, and so on.
Calculation of Seek Time
Seek Time = (60−50)+(80−60)+(130−80)+(150−130)+(190−150)+(25−190)+(10−25)
= 10+20+50+20+40+165+15
= 320
Advantages
Here are the advantages of sstf disk scheduling:
- It decreases seek time and enhances performance compared to FCFS.
- Improves over FCFS in minimizing arm movement.
- Decreases waiting time in the majority of cases.
- Suitable for high near-real-time workloads.
- Improved response time for near requests.
Disadvantages
Here are the disadvantages of sstf disk scheduling:
- Defeats far requests from the head.
- The overhead of constantly computing the nearest request.
- Does not function well for huge request queues.
- Not suitable for all workloads, particularly a combination of far and near requests.
- Performance is greatly dependent on request distribution.
Key Takeaway: SSTF improves performance but can lead to starvation for far requests.
3. SCAN Disk Scheduling Algorithm
The SCAN disk scheduling algorithm has the disk arm travel in one direction (either from the innermost track to the outermost track or vice versa), servicing all requests along the way. The arm switches directions at the end of the disk and continues servicing requests in the opposite direction. This technique is also called the elevator algorithm, which was named after the direction the arm moves back and forth.
Example
The same disk with 200 tracks (0-199). The sequence of requests is: (60, 150, 25, 130, 80, 10, 190). The head starts at position 50.
Explanation
- In the disk's SCAN algorithm, the disk arm travels in one direction, servicing all requests in that direction. It reverses at the end of the disk and begins servicing requests in the other direction. This algorithm is also referred to as the Elevator Algorithm.
- The disk arm begins at 50 and travels in the direction of the larger requests.
- It moves towards laying additional tracks, completing requests 60, 80, 130, and 150.
- Upon reaching the opposite end (track 199), it turns around and completes requests 25 and 10.
Calculation of Seek Time
Seek Time=(199−50)+(199−10)
=149+189
=338
Advantages
- Simple to implement and easy.
- Less seek time than FCFS.
- Less starvation than SSTF.
- Efficient for batches of requests at either end of the disk.
- Easy sorting is not needed.
Disadvantages
- The disk arm has to travel unnecessarily to the extreme if no request is present.
- Unequal service times are needed if the requests are local to one segment.
- Seek time could still be huge in remotely placed requests.
- Requests at the remotest ends get postponed.
- Reversing direction increases movement time.
Key Takeaway: SCAN is efficient but may cause unnecessary movement to the disk ends.
4. C-SCAN Disk Scheduling Algorithm
The C-SCAN disk scheduling algorithm is the same as SCAN, with one significant difference: when the disk arm hits the end of the disk, it returns to the beginning without serving any requests in the return direction. It then serves requests in only one direction, which makes the disk arm movement more consistent.
Example
Assume the same disk is divided into 200 tracks (0-199). The request sequence is: (60, 150, 25, 130, 80, 10, 190). The head is currently at location 50.
Explanation
- In the C-SCAN (Circular SCAN) algorithm, the disk arm travels in one direction to the disk edge, servicing all the requests. It then travels back to the beginning point and, in the same direction, travels further and services more requests.
- The disk arm begins at 50 and travels toward 199, servicing requests.
- After it reaches 199, it returns to 0 but keeps going the same way and serves requests accordingly.
Calculation of Seek Time:
Seek Time = (199−50)+(199−0)+(43−0)
= 149+199+43
= 391
Advantages
- Even distribution of wait time across requests.
- Improved response time compared to SCAN.
- Smooth disk arm movement.
- Does not waste back-and-forth movement.
- Suitable for heavy workloads with random request points.
Disadvantages
- The arm must move the entire disk length, even without requests.
- Time spent finding the location can be more significant as the arm moves to the end.
- Less efficient for random request patterns.
- Can still generate high seek times if requests are uniformly distributed.
- Does not perform well with fluctuating request patterns.
Bottom Line: C-SCAN offers consistent performance and fairness by preventing priority bias toward middle tracks.
5. LOOK Disk Scheduling Algorithm
The LOOK disk scheduling algorithm is like SCAN but with one advancement. Unlike SCAN, LOOK never goes to the end of the disk (although there are no requests there). It goes only as far as the farthest request in its direction. After it satisfies the farthest request, it changes direction and begins to satisfy the remaining requests.
Example
Suppose the same disk with 200 tracks (0-199). The sequence of requests is: (60, 150, 25, 130, 80, 10, 190). The head starts at position 50.
Explanation
- In LOOK disk scheduling, the arm heads in the direction of the last request as far as possible, but does not go to the other end of the disk if there are no requests. Then, when it is at the last request farthest, it turns around and comes back towards the previous last requested track.
- The disk arm begins at 50, swings to 150, and goes back to 10, satisfying every requirement.
Calculation of Seek Time
Seek Time = (150−50)+(150−10)
= 100+140
= 240
Advantages
Here are the advantages of look disk scheduling:
- No time is wasted traveling to the end of the disk at termination.
- Fewer seeks than SCAN.
- Better fairness in scheduling than SSTF.
- Will not need to sort requests.
Disadvantages
Here are the disadvantages of look disk scheduling:
- can still lead to starvation of requests at the far end from the head.
- More unpredictable head movement.
- Won't handle random request-distributed workloads optimally.
- The efficiency of the algorithm depends on request distribution.
- Additional logic is needed to locate the farthest request.
Quick Note: LOOK stops at the last request instead of the disk edge, reducing unnecessary travel and improving efficiency over SCAN.
6. C-LOOK Disk Scheduling Algorithm
The C-LOOK (Circular LOOK) disk scheduling algorithm is an enhanced version of the LOOK algorithm. Similar to LOOK, the disk arm travels in one direction to the farthest request. However, rather than traveling to the end of the disk, when it reaches the farthest request, it jumps to the start and continues serving requests in the same direction.
Example
Imagine the same 200-track disc (0-199). The head's initial position is 50. The request sequence is: (60, 150, 25, 130, 80, 10, 190).
Explanation
The C-LOOK (Circular LOOK) algorithm is the same as LOOK, except that it does not reach the end of the disk while returning. Instead, it jumps back to the last request in the opposite direction after serving the furthest request and continues serving.
The disk arm begins at 50, travels to 150, then jumps to 10, serving all requests in between.
Calculation of Seek Time
Seek Time = (150−50)+(150−10)+(190−10)
= 100+140+180
= 420
Advantages
Here are the advantages of clook disk scheduling:
- More efficient than LOOK.
- Same response time as the arm moves in one direction.
- Less idle time than SCAN.
- No requirement to reach the end of the disk.
- Fairer to all the requests in the queue.
Disadvantages
Here are the disadvantages of clook disk scheduling:
- Returning to the start might add delays.
- Seek time can also be huge for edge requests.
- Inefficient with sporadic or irregular request patterns.
- Can lead to longer waiting times for some of the requests.
- More complex logic than SCAN.
Bottom Line: C-LOOK combines consistency with minimized travel, making it one of the most efficient scheduling techniques.
Other Disk Scheduling Algorithms
In addition to the popular algorithms like SCAN, C-LOOK disk scheduling algorithm, and FCFS, there are a few other disk scheduling methods that provide solutions for different scenarios or system requirements. These methods are mostly significant in the context of random due dates, random processing times, random weights, and situations where the starvation of requests and stochastic machine breakdowns are possible.
1. Random Scheduling
Random Scheduling chooses the next I/O request randomly from the disk queue without consideration of the position or arrival time. This method is mainly used for performance evaluation and system simulation in which random processing time or random due dates are the major factors. Although it does not minimize seek time, it can serve as a way to model unpredictable workloads or check system stability.
2. Last-In First-Out (LIFO) Algorithm
Last-In First-Out algorithm is the one that performs the I/O operation that has been most recently requested by the user. In this way, it is possible to maximize the locality and resource utilization since the newer requests may be related to each other or be in the same cluster. However, LIFO can lead to the phenomenon of starvation of requests that arrived earlier if new requests continue to come, as older requests may be constantly deferred.
3. N-STEP SCAN
N-STEP SCAN organizes the disk queue into sub-queues or buffers of N requests each. All requests in the current buffer are serviced using the SCAN disk scheduling algorithm, and new requests are held in subsequent buffers until the current one is completed. This method guarantees service for all requests in a buffer and prevents starvation, as every request is eventually processed in its turn.
4. F-SCAN
F-SCAN improves upon N-STEP SCAN by using two sub-queues: one for current requests and one for new arrivals. During each scan, only the requests present in the active queue at the start are serviced, while new requests are added to the secondary queue and held until the next scan. This approach helps prevent the disk arm from getting stuck servicing a continuous stream of new requests and ensures fairness and guaranteed service.
Key Takeaways So Far:
- Disk scheduling aims to minimize seek time and optimize disk arm movement.
- Algorithms like FCFS, SSTF, SCAN, and C-SCAN differ in efficiency and fairness.
- Each algorithm has its strengths and weaknesses depending on the workload and system requirements.
- Advanced algorithms like LOOK and C-LOOK address inefficiencies in SCAN and C-SCAN by avoiding unnecessary travel.
Practice Problems and Solutions
To solidify your understanding of disk scheduling algorithms, let’s work through several example problems. These practical scenarios demonstrate how to apply the algorithms and calculate key metrics like seek time.
Problem 1: FCFS Disk Scheduling Algorithm
Scenario:
A disk has cylinders numbered from 0 to 199. The disk queue contains I/O requests for the following cylinders in order: 98, 183, 41, 122, 14, 124, 65, 67. The disk head starts at cylinder 53.
Calculate:
The total head movement (seek time) incurred while servicing these requests using the FCFS disk scheduling algorithm.
Solution:
- Initial position: 53
- Requests: 98, 183, 41, 122, 14, 124, 65, 67
Calculate the movement for each step (absolute difference):
- |98 – 53| = 45
- |183 – 98| = 85
- |41 – 183| = 142
- |122 – 41| = 81
- |14 – 122| = 108
- |124 – 14| = 110
- |65 – 124| = 59
- |67 – 65| = 2
Total Seek Time = 45 + 85 + 142 + 81 + 108 + 110 + 59 + 2 = 632
Problem 2: Randomized Job Attributes
Scenario:
Suppose you have a disk with blocks of disk numbered 0–199. The disk queue contains requests with random due dates, random processing times, and random weights due to stochastic machine breakdowns. The requests arrive at: 25, 89, 132, 45, 10. The head starts at 50.
Question:
If the requests have the following random weights (importance):
- 25 (weight 3), 89 (weight 1), 132 (weight 2), 45 (weight 5), 10 (weight 4)
And the processing times are: - 25 (2ms), 89 (4ms), 132 (3ms), 45 (1ms), 10 (2ms)
How would you prioritize the disk queue if you wanted to minimize total weighted seek time, and what would the seek time be for your chosen order?
Solution:
One approach is to serve requests in order of highest weight first, breaking ties by shortest processing time:
Order: 45 (5), 10 (4), 25 (3), 132 (2), 89 (1)
Calculate seek times:
- |45 – 50| = 5
- |10 – 45| = 35
- |25 – 10| = 15
- |132 – 25| = 107
- |89 – 132| = 43
Total Seek Time = 5 + 35 + 15 + 107 + 43 = 205
Problem 3: Dealing with Stochastic Machine Breakdowns
Scenario:
A disk scheduling system faces stochastic machine breakdowns, causing delays in servicing I/O requests. Given a disk queue of requests: 30, 70, 110, 150, with the head at 40, and a breakdown occurs after servicing the second request, causing a 5ms delay.
Question:
Calculate the total seek time and account for the breakdown delay.
Solution:
Order: 70, 110, 150
- |70 – 40| = 30
- |110 – 70| = 40
- Machine breakdown: add 5ms delay
- |150 – 110| = 40
Total Seek Time = 30 + 40 + 40 = 110
Total Time Including Delay = 110 (seek) + 5 (breakdown) = 115
Key Takeaways So Far
- FCFS example shows inefficiency.
- Weighted scheduling matters in advanced scenarios.
- Real-world issues like breakdowns affect total time.
Conclusion
To sum up, disk scheduling algorithms are a major factor of the success of operations related to disk I/O in an operating system. From FCFS to C-LOOK, all algorithms have their pros and cons, and the best algorithm depends on the particular system requirements. The algorithms in question work to reduce the time it takes to move the disk arm thus they minimize seek time, rotational latency, and system performance. Understanding the advantages and disadvantages of each disk scheduling algorithm is the key to making the best speed-fairness-resource utilization tradeoff in different computer systems.
Why It Matters?
Scheduling of the disk is one of the performance factors of the OS that cannot be overlooked. Good algorithms are the cause of very few I/O operations delays thus they contribute to the system's responsiveness. In such environments where I/O requests are abundant, perfecting disk scheduling can have a great positive effect on throughput and user experience.
Practical Advice for Learners
- Master seek time, latency, and access time.
- Use the worked examples to compare all the algorithms.
- Head movement diagram will help you to visualize the behavior.
- Different request patterns should be used when testing algorithms.
Frequently Asked Questions
1. What is Disk Scheduling?
Disk scheduling is the process for scheduling the sequence in which disk I/O requests are serviced. The primary objective is to maximize the efficiency of disk operations, minimize the time required by each I/O operation, and achieve fairness among competing processes.
2. Why is Disk Scheduling Important?
Disk scheduling is necessary because it has a direct relation to system performance. Proper disk scheduling results in quick data access, the optimum utilization of disk resources, and minimizing aggregate I/O operation time. Bad disk scheduling can result in huge seek times and response times, making the system inefficient.
3. What are the Different Types of Disk Scheduling Algorithms?
The common types of disk scheduling algorithms are:
- First-Come, First-Served (FCFS)
- Shortest Seek Time First (SSTF)
- SCAN
- C-SCAN (Circular SCAN)
- LOOK
- C-LOOK (Circular LOOK)
Each algorithm operates in servicing disk I/O requests differently regarding efficiency, fairness, and complexity.
4. What is the difference between C-SCAN and SCAN algorithms?
SCAN and C-SCAN have the disk arm scanning from one side of the disk to the other. The only difference is:
- SCAN: When the disk arm is at the end of the disk, it turns around and begins to serve requests in the opposite direction.
- C-SCAN: Upon arriving at the end of the disk, the arm immediately returns to the initial position without fulfilling any requests on its way back and then continues to fulfill the requests in the same direction.
