Disk Scheduling Algorithms in OS

Last Updated on July 21, 2023 by Mayank Dham

In the vast realm of operating systems (OS), managing disk I/O operations efficiently is a critical challenge. Disk scheduling in OS plays a vital role in optimizing the performance of storage devices by determining the order in which pending disk requests are serviced. By intelligently organizing and prioritizing these requests, disk scheduling algorithms aim to minimize seek times, reduce latency, and maximize overall system throughput.

As computers increasingly handle larger volumes of data and perform a multitude of tasks simultaneously, the need for efficient disk scheduling algorithms becomes even more pronounced. The ability to access and retrieve data from storage devices quickly and effectively can significantly impact the overall responsiveness and performance of an operating system.

What are Disk Scheduling Algorithms?

Disk scheduling algorithms are a set of techniques used by operating systems to determine the order in which pending disk I/O (Input/Output) requests are serviced. These algorithms aim to minimize the seek time, reduce latency, and optimize the overall performance of storage devices such as hard disk drives (HDDs) and solid-state drives (SSDs).

When a computer system receives multiple disk I/O requests simultaneously or in quick succession, the disk scheduling algorithm determines the most efficient way to access the requested data on the disk. It determines the order in which the requests should be serviced to minimize the movement of the disk’s read/write heads and reduce the time it takes to retrieve the data.

Disk scheduling algorithms consider various factors to make informed decisions about request ordering. These factors include the current position of the disk head, the distance between the current position and the location of the requested data, the direction of head movement, and the arrival time of requests. Disk scheduling is important because:

• Different processes may send out many I/O requests, but the disc controller can only handle one I/O request at once. As a result, scheduling and waiting in the waiting queue are required for further I/O requests.
• Two or more requests may be far apart, which can cause the disc arm to move more.
• As one of the slower components of the computer system, hard discs require effective access.

Important Terminologies for Disk Scheduling Algorithms in OS

These are some of the important terms that you must be comfortable with in order to understand the disk scheduling algorithms in os.

• Seek Time
  The time taken by the read/write head to move from one position to another position is present on the hard drive. It is of two types, average or maximum where the mean time to move is the average time while the maximum it can take is the maximum time.

• Rotational Latency
  The data gets stored with the help of a rotating disk where the read/write head gets the position of the disk for accessing the data. The time taken between the request and read data is known to be rotational latency. In this manner, the lesser the rotational latency, the better.

• Disk Access Time
  The total time taken to get the first required data processing a read/write request. It comprises access time and data transfer time or in other words, it can be the summation of Rotational Latency, Seek Time and Transfer Time.

• Transfer Time
  The time taken to fetch the data after the request is made from the user side and providing the output is known as “Transfer Time”.

• Disk Response Time
  The average of the waiting time is known as the “Disk Response Time”.

Types of Scheduling Algorithm

Now having some basic understanding of what disk scheduling algorithms are and the necessary terminologies required for learning disk scheduling algorithms in os, let us go through each algorithm.

First Come First Serve

It is a disk scheduling algorithm that processes the requests made in the order of the time they arrived. We can assume the queue data structure to understand this algorithm as the request that came in earlier will be the first one to be performed.

It is not the most optimal as a long time-taking request needs to be performed completely before a shorter one and it has the non-preemptive property that makes it complete the current task and avoid any other execution before the completion of the current.

Example:
Let us consider the request sequence as 82, 170, 43, 140, 24, 16 and 190 and current position of head at 50.

Here the seek time for this example will be

Seek time for FCFS = (82-50) + (170-82) + (170-43) + (140-43) + (140-24) + (24-16) + (190-16) = 642

Advantages:

• Easy Implementation
• No Starvation

Disadvantages:

Low Efficiency
More Seek Time

Shortest Seek Time First

Another disk scheduling algorithm in os that looks for the least seek time needed for read/write head to access drive data. Thus, the read/write head approaches data that is closest to its position.

It is faster as compared to another algorithm as it is preemptive which enables it to switch to requests that arrived later. It also minimizes the seek time needed to access data but creates problems such as Starvation wherein some requests never get the read/write head.

Example:
Let us consider the request sequence as 82, 170, 43, 140, 24, 16 and 190 and current position of head at 50.

Here the seek time for this example will be

Calculation of Seek Time  for SSTF = (50-43) + (43-24) + (24-16) + (82-16) + (140-82) + (170-140) + (190-170) = 208

Advantages:

• Less Disk Response Time
• Increased Efficiency than FCFS

Disadvantages:

• Low Speed
• Starvation can occur

SCAN Scheduling Disk Algorithm

It also goes by the name of the Elevator Algorithm, similarly to an elevator, it scans from starting point in a hard drive to the ending point and returns back to its initial stage at the starting point working on requests.

It has a drawback where it can make the user wait longer for more amount of requests in the queue because it set the priorities of the request currently being scanned which can make one wait longer for requests at the far end of the disk.

Example:
Let us consider the request sequence as 82, 170, 43, 140, 24, 16 and 190 and current position of head at 50.

Here the seek time for this example will be

Calculation of Seek Time for SCAN = (199-50) + (199-16) =332

Advantages:

• Easy Implementation.
• No waiting of requests in the queue.

Disadvantages:

• No matter if there are requests in the direction, the head keeps on moving to the end.

LOOK Algorithm

It is a variant of the SCAN Scheduling algorithm it moves from start to end but on fulfilment of requests, it returns back by reversing the direction rather than going to the very end.

This technique is helpful in reducing waiting time for requests lying far from the initial point.

Example:
Let us consider the request sequence as 82, 170, 43, 140, 24, 16 and 190 and current position of head at 50.

The seek Time for the above example,

Seek Time for LOOK = (190-50) + (190-16) =314

Advantages:

• There is no starvation.
• There is no time wastage as the head does not goes to the end.

Disadvantages:

• The arm must need to be conscious while finding the last request.

C-SCAN Algorithm

Another algorithm is slightly similar to SCAN where the scanning is performed from one end to another servicing the requests, but instead of returning back, it moves to the other end of the disk and continues scanning in the reversed direction it was initially scanning.

This in turn creates a C-Shaped Path traversed in terms of movement. It has a better performance and reduces the wait time.

Example:
Let us consider the request sequence as 82, 170, 43, 140, 24, 16 and 190 and current position of head at 50.

The seek time for the above algorithm wll be

Seek Time of C-SCAN =(199-50) + (199-0) + (43-0) =391

Advantages:

• Uniform distribution of waiting time among the requests.
• This has good response time.

Disadvantages:

• The head will keep going to the end of the disk.
• Time requires to locate the spot is increased in this algorithm.

C-LOOK Algorithm

It follows the exact same procedure as C-SCAN Algorithm by moving to the other ends of the disk upon servicing all the requests with a slight change in that the C-SCAN algorithm reverses the direction after moving to the other end but the C-LOOK disk scheduling algorithm in os continues scanning in the same direction.

Example:
Let us consider the request sequence as 82, 170, 43, 140, 24, 16 and 190 and current position of head at 50.

The seek Time for the above algorithm will be

Seek Time of C-LOOK = (190-50) + (190-16) + (43-16) =341

Advantages:

• Reduction in waiting time.
• There is no starvation.

Disadvantages:

• The arm need to be conscious while dealing with the last request.

Why We should use Disk Scheduling Algorithms in OS

Disk scheduling algorithms are used to improve the performance of a computer’s hard disk by efficiently accessing and retrieving data from the disk. The main reason for using disk scheduling algorithms is to reduce the seek time and rotational latency of the disk, which are the two major factors that affect the disk’s access time.

When a computer needs to access data from the disk, it sends a request to the disk controller, which then retrieves the data from the disk. The disk scheduling algorithm is responsible for deciding the order in which these requests are processed by the disk controller. By optimizing the order of these requests, the disk scheduler can minimize the time it takes for the disk to access the data, which in turn improves the overall performance of the system.

Disk scheduling algorithms are particularly important in systems where multiple processes or applications are accessing the disk simultaneously. In such cases, the disk scheduler must prioritize the requests in a fair and efficient manner to prevent any single process from monopolizing the disk and causing delays for other processes.

Conclusion
Disk scheduling algorithms play a crucial role in optimizing the performance of operating systems by efficiently organizing and prioritizing disk I/O operations. Throughout this article, we explored various disk scheduling algorithms, including First-Come, First-Served (FCFS), Shortest Seek Time First (SSTF), SCAN, C-SCAN, LOOK, and C-LOOK. Each algorithm has its strengths and weaknesses, making them suitable for specific scenarios and workloads.

By understanding the principles and characteristics of different disk scheduling algorithms, system administrators, IT professionals, and computer science enthusiasts can make informed decisions when configuring disk I/O operations. Choosing the right disk scheduling algorithm can lead to reduced latency, minimized seek times, and improved overall system throughput.

Frequently Asked Questions on Disk Scheduling in OS

Here are some Frequently Asked Questions related to “Disk Scheduling in OS”.
Q1: Can a single disk scheduling algorithm work optimally for all scenarios?
A: No, there is no one-size-fits-all disk scheduling algorithm that works optimally for every scenario. The efficiency of a disk scheduling algorithm depends on factors such as workload characteristics, disk I/O patterns, and the desired trade-off between fairness and response times. It is crucial to analyze the specific requirements and workload of a system to select the most appropriate algorithm.

Q2: What are the key factors to consider when choosing a disk scheduling algorithm?
A: When choosing a disk scheduling algorithm, it is important to consider factors such as seek time, rotational latency, head movements, and the presence of multiple queues. These factors significantly impact the performance and efficiency of disk I/O operations. Understanding the workload and system requirements helps in selecting the algorithm that minimizes access times and maximizes resource utilization.

Q3: Are there any real-world examples of using disk scheduling algorithms?
A: Yes, disk scheduling algorithms are widely used in various real-world scenarios. For example, in database management systems, disk scheduling algorithms play a crucial role in optimizing data retrieval, ensuring quick and efficient access to stored information. Operating systems for servers, personal computers, and other computing devices also utilize disk scheduling algorithms to improve the overall system performance and responsiveness.

Q4: Can disk scheduling algorithms eliminate disk I/O delays entirely?
A: While disk scheduling algorithms can minimize disk I/O delays by optimizing the order of servicing requests, they cannot eliminate delays entirely. Disk I/O operations inherently involve physical movements of the disk’s read/write heads and have inherent latency. Disk scheduling algorithms aim to reduce seek times and improve overall performance, but eliminating delays completely is not possible due to the physical limitations of the disk hardware.

Q5: Are there any advanced disk scheduling algorithms beyond the ones discussed in the article?
A: Yes, beyond the commonly discussed disk scheduling algorithms (FCFS, SSTF, SCAN, C-SCAN, LOOK, and C-LOOK), there are more advanced algorithms such as N-Step-SCAN, Deadline-Based Scheduling, and Elevator Algorithm. These advanced algorithms incorporate additional considerations and optimizations to address specific challenges or improve performance in certain scenarios. They are often tailored for specialized environments or specific requirements.