Disc Scheduling: The operating system performs a disc scheduling process to schedule I/O requests that arrive at the disc. Disc scheduling is important since-

Many I/O requests may arrive from different processes, and the disc 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.

Note: Seek time is the time for the disc arm to move the heads to the cylinder containing the desired sector.

To perform disc scheduling, we have six-disc scheduling algorithms. These are-

In this article, we will study the SSTF Scheduling Algorithm.

What is Shortest Seek Time First Disk Scheduling Algorithm?

Shortest Seek Time First (SSTF) is similar to choosing the shortest line at the grocery store. It prioritizes data requests that are closest to the location of the computer's reading arm on the hard drive. This reduces the arm's back-and-forth movement, making data access faster.

It appears reasonable to service all the requests close to the current head position before moving the head far away to service other requests. This assumption is the basis for the Shortest Seek Time First (SSTF) Algorithm.

The SSTF 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, SSTF chooses the pending request closest to the current head position.

To understand the shortest seek time first disk scheduling algorithm, let us assume a disc queue with requests for I/O. â€˜headâ€™ is the position of the disc head. We will now apply the SSTF algorithm-

Arrange all the I/O requests in ascending order.

The head will find the nearest request (which has a minimum distance from the head) present in any direction (left or right) and will move to that request. Total head movement is calculated as

Current request - previous request (if the current request is greater)

Previous request - current request (if the previous request is greater)

Then the head will move another nearest request which has not been serviced present in any direction.

This process is repeated until all the requests are served and we get total head movement.

Example of Shortest Seek Time First Disk Scheduling Algorithm

Example 1

Consider a disc queue with requests for I/O to blocks on cylinders 98, 183, 37, 122, 14, 124, 65, 67. The head is initially at cylinder number 53. We will now use the SSTF algorithm to serve these I/O requests.

Arranging all the requests in ascending order, we get - { 14, 37, 65, 67, 98, 122, 124, 183 }.

Head will find the nearest request. Between 37 and 65, 65 is nearest (since 53 - 37 = 16 and 65 - 53 = 12). So, the head will move from 53 (current position) to 65 (next request). Head movement = 65 - 53 = 12.

The nearest request to 65 is 67, so the head will move from 65 to 67, and head movement becomes 12 + (67 - 65) = 14.

Similarly, the nearest request to 67 is 37, so the head will go from 67 to 37, and head movement becomes 14 + (67 - 37) = 44.

Similarly, the nearest request to 37 is 14, so the head will go from 37 to 14, and head movement becomes 44 + (37 - 14) = 67.

Similarly, the nearest request to 14 is 98, so the head will go from 14 to 98, and head movement becomes 67 + (98 - 14) = 151.

Similarly, the nearest request to 98 is 122, so the head will go from 98 to 122, and head movement becomes 151 + (122 - 98) = 175.

Similarly, the nearest request to 122 is 124, so the head will go from 122 to 124, and head movement becomes 175 + (124 - 122) = 177.

Similarly, the nearest request to 124 is 183, so the head will go from 124 to 183, and head movement becomes 177 + (183 - 124) = 236.

Since 183 was the last request, the process will stop. We get the total head movement as 236.

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

Thus, the order in which requests are served is- 65, 67, 37, 14, 98, 122, 124, 183 with a total head movement of 236.

Now, let us consider one more example.

Example 2

Consider a disc queue with requests for I/O to blocks on cylinders 95, 180, 34, 119, 11, 123, 62, 64. The head is initially at cylinder number 50. We will now use the SSTF algorithm to serve these I/O requests.

Arranging all the requests in ascending order, we get - { 11, 34, 62, 64, 95, 119, 123, 180 }.

The Head will start moving from 50 to the nearest request,i.e. 62. After 62 head will move to 64, and similarly head will follow the sequence - 34, 11, 95, 119, 123, 180.

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

Thus, the order in which requests are served is- 62, 64, 34, 11, 95, 119, 123, 180 with a total head movement of 236.

Let us consider one more example.

Example 3

Consider a disc queue with requests for I/O to blocks on cylinders 19, 80, 134, 11, 110, 23, 162, 64. The head is initially at cylinder number 50. We will now use the SSTF algorithm to serve these I/O requests.

Arranging all the requests in ascending order, we get - { 11, 19, 23, 64, 80, 110, 134, 162 }.

The Head will start moving from 50 to the nearest request,i.e. 64. After 64 head will move to 80, and like this, the head will follow the sequence - 110, 134, 162, 23, 19, 11.

public class SSTF { public static int shortestSeekTimeFirst(ArrayList<Integer> requests, int currentPos) { int totalSeekTime = 0; ArrayList<Integer> sortedRequests = new ArrayList<>(requests); Collections.sort(sortedRequests);

while (!sortedRequests.isEmpty()) { int minDiff = Integer.MAX_VALUE; int minIndex = -1; for (int i = 0; i < sortedRequests.size(); ++i) { int diff = Math.abs(currentPos - sortedRequests.get(i)); if (diff < minDiff) { minDiff = diff; minIndex = i; } } totalSeekTime += minDiff; currentPos = sortedRequests.get(minIndex); sortedRequests.remove(minIndex); } return totalSeekTime; }

public static void main(String[] args) { ArrayList<Integer> requests = new ArrayList<>(); Collections.addAll(requests, 98, 183, 37, 122, 14, 124, 65, 67); int currentPos = 53; int seekTime = shortestSeekTimeFirst(requests, currentPos); System.out.println("Total seek time using SSTF: " + seekTime); } }

You can also try this code with Online Java Compiler

using System; using System.Collections.Generic; using System.Linq;

class Program { static int ShortestSeekTimeFirst(List<int> requests, int currentPos) { int totalSeekTime = 0; List<int> sortedRequests = requests.OrderBy(x => x).ToList();

while (sortedRequests.Any()) { int minDiff = int.MaxValue; int minIndex = -1; for (int i = 0; i < sortedRequests.Count; ++i) { int diff = Math.Abs(currentPos - sortedRequests[i]); if (diff < minDiff) { minDiff = diff; minIndex = i; } } totalSeekTime += minDiff; currentPos = sortedRequests[minIndex]; sortedRequests.RemoveAt(minIndex); } return totalSeekTime; }

static void Main(string[] args) { List<int> requests = new List<int> { 98, 183, 37, 122, 14, 124, 65, 67 }; int currentPos = 53; int seekTime = ShortestSeekTimeFirst(requests, currentPos); Console.WriteLine("Total seek time using SSTF: " + seekTime); } }

Advantages of SSTF Disk SchedulingAlgorithm

The advantages of the SSTF Algorithm are-

It has a much better access time.

Its performance is better than the FCFS scheduling algorithm.

It provides less average response time and waiting time.

It provides increased throughput.

Disadvantages of SSTFDisk SchedulingAlgorithm

The disadvantages of the SSTF Algorithm are-

It may cause starvation. For example- there are two requests - 14 and 186. While 14 is being served, a new request near 14 arrives. This new request will be served next, making the request at 186 wait. While this request is being served, another request close to 14 could arrive. In this way, the request at 186 may starve.

There can be switching of directions repeatedly, which can make the process slow.

The variance between the response time and waiting time is very high.

Finding out the closest request adds additional overhead to the entire process.

SSTF (Shortest Seek Time First) is a disk scheduling algorithm which selects the request which is closest to the current head position. To achieve this, it selects the request which has the least seek time from the current position of the head.

In which disk scheduling algorithm requests having shortest seek time are executed first?

SSTF (Shortest Seek Time First) prioritizes requests with the shortest seek time. As a result, the seek time of each request in the queue is computed in advance, and they are then scheduled based on their anticipated seek time. As a result, the request closest to the disk arm will be executed first.

Conclusion

In this article, we studied the SSTF Disk Scheduling Algorithm. We explored the topic thoroughly using its examples. We also discussed the advantages and disadvantages of the SSTF algorithm.

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