DISC SCHEDULING ALGORITHMS

Mrs Sangeeta Bhandari

Hans Raj Mahila Maha Vidyalaya, Jalandhar

Disk Scheduling

• Disc scheduling is an important process in operating systems that determines the order in which disk access requests are serviced.
• The objective of disc scheduling is to minimize the time it takes to access data on the disk and to minimize the time it takes to complete a disk access request.

Disk Scheduling

• Disk access time is determined by two factors: seek time and rotational latency.
• Seek time is the time it takes for the disk head to move to the desired location on the disk.
• Rotational latency is the time taken by the disk to rotate the desired data sector under the disk head.

Disk Scheduling

• Disk scheduling algorithms are an essential component of modern operating systems and are responsible for determining the order in which disk access requests are serviced.
• The primary goal of these algorithms is to minimize disk access time and improve overall system performance.

Disc Scheduling Algorithms

• FCFS
• Shortest Seek Time First
• Scan
• C-Scan
• Look
• C-Look

First-Come-First-Serve

• This scheduling algorithm is one of the simplest and most straightforward disk scheduling algorithms.
• It operates on the principle of servicing disk access requests in the order in which they are received.
• In the FCFS algorithm, the disk head is positioned at the first request in the queue and the request is serviced. The disk head then moves to the next request in the queue and services that request. This process continues until all requests have been serviced.
• Suppose we have an order of disk access requests: 20 150 90 70 30 60. The disk head is currently located at track 50The total seek time = (50-20) + (150-20) + (150-90) + (90-70) + (70-30) + (60-30) = 310

​

Shortest-Seek-Time-First

• This is used to efficiently manage disk I/O operations.
• The goal of SSTF is to minimize the total seek time required to service all the disk access requests.
• In SSTF, the disk head moves to the request with the shortest seek time from its current position, services it, and then repeats this process until all requests have been serviced.
• The algorithm prioritizes disk access requests based on their proximity to the current position of the disk head, ensuring that the disk head moves the shortest possible distance to service each request.

​

​

​

​

​

​

​

​

​

​

• In this case, for the same order of success request, the total seek time = (60-50) + (70-60) + (90-70) + (90-30) + (30-20) + (150-20) = 240

SCAN

• The SCAN algorithm moves the disk head in a single direction and services all requests until it reaches the end of the disk, and then it reverses direction and services all the remaining requests.
• In SCAN, the disk head starts at one end of the disk, moves toward the other end, and services all requests that lie in its path. Once the disk head reaches the other end, it reverses direction and services all requests that it missed on the way. This continues until all requests have been serviced.

​

​

​

​

​

​

​

​

​

• If we consider that the head direction is left in case of SCAN, the total seek time = (50-30) + (30-20) + (20-0) + (60-0) + (60-70) + (90-70) + (90-150) = 200

C-SCAN

• The C-SCAN (Circular SCAN) algorithm operates similarly to the SCAN algorithm, but it does not reverse direction at the end of the disk. Instead, the disk head wraps around to the other end of the disk and continues to service requests.
• This algorithm can reduce the total distance the disk head must travel, improving disk access time.
• However, this algorithm can lead to long wait times for requests that are made near the end of the disk, as they must wait for the disk head to wrap around to the other end of the disk before they can be serviced.
• The C-SCAN algorithm is often used in modern operating systems due to its ability to reduce disk access time and improve overall system performance.

​

​

​

​

​

​

​

​

​

​

• For C-SCAN, the total seek time = (60-50) + (70-60) + (90-70) + (150-90) + (199-150) + (199-0) + (20-0) + (30-20) = 378

LOOK

• The LOOK algorithm is similar to the SCAN algorithm but stops servicing requests as soon as it reaches the end of the disk.
• This algorithm can reduce the total distance the disk head must travel, improving disk access time.
• However, this algorithm can lead to long wait times for requests that are made near the end of the disk, as they must wait for the disk head to wrap around to the other end of the disk before they can be serviced.

​

​

​

​

​

​

​

​

​

• Considering the head direction is right, in this case, the total seek time = (60-50) + (70-60) + (90-70) + (150-90) + (150-30) + (30-20) = 230

C-LOOK

• C-LOOK is similar to the C-SCAN disk scheduling algorithm.
• In this algorithm, goes only to the last request to be serviced in front of the head in spite of the disc arm going to the end, and then from there it goes to the other end’s last request.
• Thus, it also prevents the extra delay which might occur due to unnecessary traversal to the end of the disk.

​

​

​

​

​

​

​

​

​

• For the C-LOOK algorithm, the total seek time = (60-50) + (70-60) + (90-70) + (150-90) + (150-20) + (30-20) = 240

Conclusion

• Disk scheduling algorithms play a crucial role in modern operating systems and are responsible for determining the order in which disk access requests are serviced.
• The choice of which algorithm to use is often dependent on the workload and disk access patterns, and there are several different algorithms to choose from, each with its own set of strengths and weaknesses.
• Ultimately, the goal of disk scheduling algorithms is to minimize disk access time and improve overall system performance, and this goal is achieved through the use of sophisticated algorithms and advanced computational techniques.

Thanks