Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Some important terms
3.
What is Disk scheduling algorithms
4.
Importance of Disk Scheduling in Operating System
5.
Key Terms Associated with Disk Scheduling
6.
Types of Disk Scheduling Algorithm in OS
7.
FCFS scheduling algorithm
8.
SSTF Scheduling Algorithm
9.
SCAN Scheduling Algorithm
10.
C-SCAN Scheduling Algorithm
11.
LOOK Scheduling Algorithm
12.
C-LOOK Scheduling Algorithm
13.
Frequently Asked Questions
13.1.
Which scheduling algorithm is the most efficient - FCFS, SSTF, SCAN, C-SCAN, LOOK, or C-LOOK?
13.2.
What is the need for disk scheduling?
14.
Conclusion
Last Updated: Mar 27, 2024
Easy

Disk Scheduling Algorithms

Author Pakhi Garg
0 upvote
gp-icon
Operating system track
Free guided path
14 chapters
83+ problems
gp-badge
Earn badges and level up

Introduction

We all know that our data resides on secondary memory(HDD). But have you ever wondered where exactly this data is present on the hard disk? Let’s find out.

A hard disk is a collection of multiple platters. A platter has a flat circular shape like a CD with a diameter ranging from 1.8 to 5.25 inches. A platter is logically divided into multiple circular tracks. Inside a track, there are multiple sectors. The set of tracks at one arm position makes up a cylinder. When a user stores some data, the operating system stores that data in these sectors of the hard disk. And when a user fetches some data, that data is fetched from these sectors only. For this purpose, the hard disk has an actuator arm, and every platter has a read-write head that moves back and forth to get us to the desired track.

Disk Scheduling Algorithms

Since the operating system needs to access the sectors repeatedly, sometimes for storing the data and sometimes for fetching the data, multiple I/O requests get scheduled. Thus, the operating system performs a disk scheduling process to schedule the I/O requests that arrive at the disk. To perform disk scheduling, the operating system uses disk scheduling algorithms. Before moving to them, let’s discuss some important terms.

Some important terms

  • Seek Time: The seek time is the time taken by the disk arm to move the read-write head to the track containing the desired sector.
  • Rotational Latency: The rotational latency is the time the desired sector takes to rotate itself towards the read-write head to access the read-write head.
  • Transfer Time: The transfer time is the time taken to transfer the data. It is determined by the disk’s rotational speed and the number of bytes to be transferred.
  • Disk Access Time: The disk access time is calculated as-

Disk access time = Seek time + Rotational Latency + Transfer time

  • Disk Response Time: The disk response time is the average time each request spends waiting for the I/O operation.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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-

  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.

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.

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.

Types of Disk Scheduling Algorithm in OS

Disc Scheduling Algorithms

The goal of the disk scheduling algorithm is-

  1. Have a minimum average seek time.
  2. Have minimum rotational latency.
  3. 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.

 

Input: I/O requests - { 98, 183, 37, 122, 14, 124, 65, 67 }

Initial head position - 53

 

Output: The following chart shows the sequence in which requests are served using the FCFS algorithm. 

FCFS

FCFS

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.

 

Input: I/O requests - { 98, 183, 37, 122, 14, 124, 65, 67 }

Initial head position - 53

 

Output: The following chart shows the sequence in which requests are served using the SSTF algorithm. 

SSTF

SSTF

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.

 

Input: I/O requests - { 98, 183, 37, 122, 14, 124, 65, 67 }

Initial head position - 53

Direction - towards the larger number of cylinders

 

Output: The following chart shows the sequence in which requests are served using the SCAN algorithm. 

SCAN

SCAN

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.

 

Input: I/O requests - { 98, 183, 37, 122, 14, 124, 65, 67 }

Initial head position - 53

Direction - towards the larger number of cylinders

 

Output: The following chart shows the sequence in which requests are served using the C-SCAN algorithm. 

CSCAN

CSCAN

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.

 

Input: I/O requests - { 98, 183, 37, 122, 14, 124, 65, 67 }

Initial head position - 53

Direction - towards the larger number of cylinders

 

Output: The following chart shows the sequence in which requests are served using the LOOK algorithm. 

LOOK

LOOK

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.

 

Input: I/O requests - { 98, 183, 37, 122, 14, 124, 65, 67 }

Initial head position - 53

Direction - towards the larger number of cylinders

 

Output: The following chart shows the sequence in which requests are served using the C-LOOK algorithm. 

CLOOK

CLOOK

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.

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 Coding Ninjas Studio.

Reader, don’t stop here. Start your learning journey in the operating system with Coding Ninjas by taking the OS course.

Recommended Reading:

 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Learning!

Previous article
Difference between SSD and HDD
Next article
SSTF Disk Scheduling Algorithm
Guided path
Free
gridgp-icon
Operating system track
14 chapters
83+ Problems
gp-badge
Earn badges and level up
Live masterclass