SSTF Disk Scheduling Algorithm

Shortest Seek Time First Algorithm

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-

1. Arrange all the I/O requests in ascending order.
    
2. 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 
    
3. Current request - previous request (if the current request is greater)
    
4. Previous request - current request (if the previous request is greater)
    
5. Then the head will move another nearest request which has not been serviced present in any direction. 
    
6. 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.

Input 

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

Initial head position - 53

Output

1. Arranging all the requests in ascending order, we get - { 14, 37, 65, 67, 98, 122, 124, 183 }.
    
2. 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.
    
3. The nearest request to 65 is 67, so the head will move from 65 to 67, and head movement becomes 12 + (67 - 65) = 14.
    
4. 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.
    
5. 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.
    
6. 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.
    
7. 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.
    
8. 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.
    
9. 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.
    
10. 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.

Input

I/O requests - { 95, 180, 34, 119, 11, 123, 62, 64 }

Initial head position - 50

Output

1. Arranging all the requests in ascending order, we get - { 11, 34, 62, 64, 95, 119, 123, 180 }.
2. 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 total head movement is calculated as: 

= (62 - 50) + (64 - 62) + (64 - 34) + (34 - 11) + (95 - 11) + (119 - 95) + (123 - 119) + (180 - 123) 

= 12 + 2 + 30 + 23 + 84 + 24 + 4 + 57

= 236

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.

Input 

I/O requests - { 19, 80, 134, 11, 110, 23, 162, 64 }

Initial head position - 50

Output

1. Arranging all the requests in ascending order, we get - { 11, 19, 23, 64, 80, 110, 134, 162 }.
2. 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.

The total head movement is calculated as: 

= (64 - 50) + (80 - 64) + (110 - 80) + (134 - 110) + (162 - 134) + (162 - 23) + (23 - 19) + (19 - 11)

= 14 + 16 + 30 + 24 + 28 + 139 + 4 + 8

= 263

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

Thus, the order in which requests are served is- 64, 80, 110, 134, 162, 23, 19, 11, with a total head movement of 263. 

Implementation

• C++
• Java
• Python
• Javascript
• C#

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int absDiff(int a, int b) {
    return abs(a - b);
}

int shortestSeekTimeFirst(vector<int> requests, int currentPos) {
    int totalSeekTime = 0;
    vector<int> sortedRequests = requests;
    sort(sortedRequests.begin(), sortedRequests.end());

    int n = sortedRequests.size();
    int currentIndex = 0;
    while (!sortedRequests.empty()) {
        int minDiff = INT_MAX;
        int minIndex = -1;
        for (int i = 0; i < sortedRequests.size(); ++i) {
            int diff = absDiff(currentPos, sortedRequests[i]);
            if (diff < minDiff) {
                minDiff = diff;
                minIndex = i;
            }
        }
        totalSeekTime += minDiff;
        currentPos = sortedRequests[minIndex];
        sortedRequests.erase(sortedRequests.begin() + minIndex);
    }
    return totalSeekTime;
}

int main() {
    vector<int> requests = {98, 183, 37, 122, 14, 124, 65, 67};
    int currentPos = 53;
    int seekTime = shortestSeekTimeFirst(requests, currentPos);
    cout << "Total seek time using SSTF: " << seekTime << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.ArrayList;
import java.util.Collections;

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

Run Code

Python

def shortest_seek_time_first(requests, current_pos):
    total_seek_time = 0
    sorted_requests = sorted(requests)

    while sorted_requests:
        min_diff = float('inf')
        min_index = -1
        for i, req in enumerate(sorted_requests):
            diff = abs(current_pos - req)
            if diff < min_diff:
                min_diff = diff
                min_index = i
        total_seek_time += min_diff
        current_pos = sorted_requests[min_index]
        sorted_requests.pop(min_index)
    return total_seek_time

if __name__ == "__main__":
    requests = [98, 183, 37, 122, 14, 124, 65, 67]
    current_pos = 53
    seek_time = shortest_seek_time_first(requests, current_pos)
    print("Total seek time using SSTF:", seek_time)

You can also try this code with Online Python Compiler

Run Code

Javascript

function shortestSeekTimeFirst(requests, currentPos) {
    let totalSeekTime = 0;
    let sortedRequests = requests.slice().sort((a, b) => a - b);

    while (sortedRequests.length > 0) {
        let minDiff = Number.MAX_SAFE_INTEGER;
        let minIndex = -1;
        for (let i = 0; i < sortedRequests.length; ++i) {
            let diff = Math.abs(currentPos - sortedRequests[i]);
            if (diff < minDiff) {
                minDiff = diff;
                minIndex = i;
            }
        }
        totalSeekTime += minDiff;
        currentPos = sortedRequests[minIndex];
        sortedRequests.splice(minIndex, 1);
    }
    return totalSeekTime;
}

let requests = [98, 183, 37, 122, 14, 124, 65, 67];
let currentPos = 53;
let seekTime = shortestSeekTimeFirst(requests, currentPos);
console.log("Total seek time using SSTF:", seekTime);

You can also try this code with Online Javascript Compiler

Run Code

C#

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 Scheduling Algorithm

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 SSTF Disk Scheduling Algorithm

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.

Also read about - Prims and Kruskal Algorithm

Frequently Asked Questions

What is SSTF in disk scheduling?

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.

Recommended Readings

• Difference between FCFS and Scan Disk Scheduling Algorithms
• Scan v/s C-Scan Disk Scheduling
• Design and Analysis of Algorithms
• Look and C-look Algorithm
• scheduling algorithms in operating system

Also check out the Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.

Refer to our guided pathways on Code studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Happy Learning!