Disk scheduling algorithms in an operating system manage the order in which disk I/O requests are processed. As multiple processes request data from the disk, these algorithms determine the most efficient sequence to reduce seek time and improve overall system performance. Key disk scheduling algorithms include First-Come, First-Served (FCFS), Shortest Seek Time First (SSTF), and more advanced methods like SCAN and C-SCAN, each designed to optimize data retrieval and minimize delays in accessing disk resources.
What is Disk scheduling algorithms?
The operating system performs a disk scheduling process to schedule the I/O requests that arrive at the disk. Disk scheduling is important since-
Many I/O requests may arrive from different processes, and the disk controller can only serve one I/O request at a time. As a result, other I/O requests need to wait in the waiting queue and get scheduled.
The operating system needs to manage the hardware efficiently.
To reduce seek time.
Key Terms Associated with Disk Scheduling
When discussing disk scheduling in operating systems, several key terms are commonly used to describe various aspects of the process. Here are some important terms associated with disk scheduling:
Seek Time: The time it takes for the disk arm to position itself over the desired track. Seek time is a significant component of the total time it takes to access data on a disk.
Rotational Latency: The time it takes for the desired disk sector to rotate under the disk head after the head is positioned over the correct track. It is influenced by the rotational speed of the disk.
Transfer Time: The time it takes to transfer data between the disk and the computer's memory. It is determined by the data transfer rate of the disk.
Disk Access Time: The sum of seek time, rotational latency, and transfer time. It represents the total time required to access a specific piece of data on the disk.
Disk Scheduling Algorithm: A method or strategy used by the operating system to determine the order in which I/O requests are serviced. Common algorithms include FCFS (First-Come-First-Serve), SSTF (Shortest Seek Time First), SCAN, C-SCAN, LOOK, and C-LOOK.
Request Queue: A queue that holds pending I/O requests for the disk. The disk scheduling algorithm selects requests from this queue to determine the order in which they are processed.
Head Movement: The physical movement of the disk arm as it seeks to position the read/write heads over the desired track. Minimizing head movement is a key goal of disk scheduling algorithms.
Elevator Algorithm: A disk scheduling algorithm that works like an elevator, servicing requests in one direction until reaching the end of the disk and then reversing direction. Also known as SCAN or C-SCAN.
Cylinder: The concentric circular tracks on the disk surface where data is stored. The disk arm moves to position the read/write heads over the desired cylinder to access data.
Starvation: A condition where a process or I/O request is consistently delayed or denied service by the disk scheduling algorithm. Preventing starvation is a consideration in designing effective scheduling algorithms.
Deadline Scheduling: A disk scheduling approach that assigns deadlines to I/O requests, and the algorithm attempts to meet these deadlines to ensure timely delivery of data.
Track-to-Track Seek Time: The time it takes for the disk arm to move from one track to an adjacent track. This is a measure of the efficiency of head movement between adjacent cylinders.
Importance of Disk Scheduling in Operating System
Disk scheduling is crucial in operating systems for several reasons, as it directly impacts the efficiency and performance of I/O operations. Here are the key reasons highlighting the importance of disk scheduling:
Optimizing Disk Access Time: Disk scheduling algorithms aim to reduce the seek time, rotational latency, and transfer time collectively known as the disk access time. Efficient disk scheduling ensures that data is retrieved with minimal delays, improving overall system performance.
Enhancing Throughput: By minimizing the time spent on disk seeks and rotations, disk scheduling contributes to higher throughput. Throughput is a measure of the number of I/O operations the system can handle in a given time, and effective disk scheduling helps maximize this metric.
Fair Resource Allocation: In multi-user or multi-tasking environments, multiple processes or users may be contending for disk access. Disk scheduling ensures fair and equitable distribution of the disk resource, preventing any single process from monopolizing disk access and leading to potential system bottlenecks.
Reducing Disk Head Movement: Disk scheduling algorithms work to minimize the movement of the disk's read/write heads. By optimizing the order in which requests are serviced, these algorithms decrease head movement, resulting in faster data retrieval and improved overall disk performance.
Improving System Responsiveness: Disk scheduling directly influences the responsiveness of the operating system. Processes requiring disk access, such as file read and write operations, experience reduced waiting times, leading to a more responsive and user-friendly system.
Types of Disk Scheduling Algorithm in OS
The goal of the disk scheduling algorithm is-
Have a minimum average seek time.
Have minimum rotational latency.
Have high throughput.
Now, we will discuss these disk scheduling algorithms one by one.
FCFS scheduling algorithm
FCFS scheduling algorithm is the simplest disk scheduling algorithm. As the name suggests, it is a first-come, first-serve algorithm. In this algorithm, the I/O requests are processed in the order they arrive in the disk queue. Let us understand this algorithm using an example.
Example: Consider a disc queue with requests for I/O to blocks on cylinders 98, 183, 37, 122, 14, 124, 65, and 67. The read-write head is initially at cylinder number 53. We will now use the FCFS algorithm to serve these I/O requests.
Output: The following chart shows the sequence in which requests are served using the FCFS algorithm.
SSTF Scheduling Algorithm
The SSTF algorithm stands for the shortest seek time first algorithm. This algorithm selects the request having the minimum distance from the current head position. Since distance increases with the number of cylinders traversed by the head, the SSTF chooses the pending request closest to the current head position. Let us understand this algorithm using an example.
Example: Consider a disc queue with requests for I/O to blocks on cylinders 98, 183, 37, 122, 14, 124, 65, 67. The read-write head is initially at cylinder number 53. We will now use the SSTF algorithm to serve these I/O requests.
Output: The following chart shows the sequence in which requests are served using the SSTF algorithm.
SCAN Scheduling Algorithm
In the SCAN scheduling algorithm, the disk arm begins at one end of the disk and moves towards the other end, servicing requests as it reaches each cylinder until it gets to the other end of the disk. As soon as it reaches the other end, the direction of head movement is reversed, and servicing continues. The head moves back and forth across the disk, continuously servicing requests. Let us understand this algorithm using an example.
Example: Consider a disc queue with requests for I/O to blocks on cylinders 98, 183, 37, 122, 14, 124, 65, 67. The read-write head is initially at cylinder number 53. We will now use the SCAN algorithm to serve these I/O requests.
Direction - towards the larger number of cylinders
Output: The following chart shows the sequence in which requests are served using the SCAN algorithm.
C-SCAN Scheduling Algorithm
The C-SCAN (Circular Scan) scheduling algorithm is a variant of the SCAN scheduling algorithm designed to provide a more uniform wait time. Like SCAN, C-SCAN moves the head from one end of the disk to the other, servicing requests along the way. However, when the head reaches the other end, it immediately returns to the beginning of the disk without servicing any requests on the return trip. Let us understand this algorithm using an example.
Example: Consider a disc queue with requests for I/O to blocks on cylinders 98, 183, 37, 122, 14, 124, 65, 67. The read-write head is initially at cylinder number 53. We will now use the C-SCAN algorithm to serve these I/O requests.
Direction - towards the larger number of cylinders
Output: The following chart shows the sequence in which requests are served using the C-SCAN algorithm.
LOOK Scheduling Algorithm
The LOOK scheduling algorithm is identical to the SCAN disk scheduling algorithm, except that, instead of traveling to the end of the disk, the head goes till the last request to be handled and then reverses the head from there and processes the requests in the opposite direction. As a result, the extra time caused by unneeded overhead to the disk end is avoided. Let us understand this algorithm using an example.
Example: Consider a disc queue with requests for I/O to blocks on cylinders 98, 183, 37, 122, 14, 124, 65, and 67. The read-write head is initially at cylinder number 53. We will now use the LOOK algorithm to serve these I/O requests.
Direction - towards the larger number of cylinders
Output: The following chart shows the sequence in which requests are served using the LOOK algorithm.
C-LOOK Scheduling Algorithm
The C-LOOK scheduling algorithm is similar to the C-SCAN scheduling algorithm, except that the head does not move to the end of the disk in the C-LOOK algorithm. It goes until the last request is processed in one end and then reverses its direction and does not process any request. It stops at the last request in the opposite direction and continues the process until all requests are served. Let us understand this algorithm using an example.
Example: Consider a disc queue with requests for I/O to blocks on cylinders 98, 183, 37, 122, 14, 124, 65, and 67. The read-write head is initially at cylinder number 53. We will now use the C-LOOK algorithm to serve these I/O requests.
Direction - towards the larger number of cylinders
Output: The following chart shows the sequence in which requests are served using the C-LOOK algorithm.
Frequently Asked Questions
Which scheduling algorithm is the most efficient - FCFS, SSTF, SCAN, C-SCAN, LOOK, or C-LOOK?
The performance of a disk scheduling algorithm depends on the total seek time given by that scheduling algorithm. Out of FCFS, SSTF, SCAN, C-SCAN, LOOK, and C-LOOK; SSTF and LOOK algorithms are the most efficient ones.
What is the need for disk scheduling?
Disk scheduling is important since- 1) Many I/O requests may arrive from different processes, and the disk controller can only serve one I/O request at a time. As a result, other I/O requests need to wait in the waiting queue and get scheduled. 2) The operating system needs to manage the hardware efficiently. 3) To reduce seek time.
What are the 3 different types of scheduling queues?
The three types of scheduling queues are:
Job Queue: Holds all processes waiting for execution.
Ready Queue: Contains processes ready to execute, awaiting CPU.
Device (I/O) Queues: Manage processes waiting for I/O device access.
Conclusion
In this article, we studied disk scheduling and disk scheduling algorithms. We went through each algorithm and explored it using its examples. You can find detailed articles on each disk scheduling algorithm on Code360.
Reader, don’t stop here. Start your learning journey in the operating system with Coding Ninjas by taking the OS course.
39+ registered 