SSTF: Shortest Seek Time First

In SSTF (Shortest Seek Time First) disk scheduling algorithm we have to calculate the seek time first.
That is, before serving any request, seek time is calculated for each request and then the request with least seek time will be served.
If we define in terms of hardware then, the request which are closure to disk head position will be served first. SSTF also aims to overcome some of the limitations in FCFS.

Advantages:

• Better Performance compared to FCFS.
• Response time and waiting time is less.
• In FCFS, fair chance given to each request.
• Increased throughput, helps in Batch Processing System. (Throughput is the amount of completed work against time consumed)

Disadvantages:

• SSTF can be time consuming due to frequent switching.
• There might be chance of Starvation since it is designed to serve the closer requests first compared to the farther ones.
• Lack of Predictability.
• There are chances of Overhead (Indirect computation time) since seek time is calculated for each request in advance.

Example:

• Consider a disk that contains 200 tracks (0-199). The request queue includes track number 176, 79, 34, 60, 92, 11, 41, 114 respectively.
  The current position of the read/write head is 50.
• Before solving the above example, we have to know about the seek time.
  Seek time = Destination - Source or Source - Destination
• As mentioned in the following example, disk contains 200 tracks. So, we will take a track line between 0 to 199.
• The current position of the read/write head is 50. So, we start at 50.




• We can see in the following figure that the current or initial position of read/write head is 50. Now for further movement of read/write head, we calculate the seek time.
• Total Number of cylinders moved by the head
  = (50-41)+(41-34)+(34-11)+(60-11)+(79-60)+(92-79)+(114-92)+(176-114)
  = 204

Steps to Implement Algorithm:

1. Let Request array represents an array storing indexes of tracks that have been requested. ‘head’ is the position of disk head.
2. Find the positive distance of all tracks in the request array from head.
3. Find a track from requested array which has not been accessed/serviced yet and has minimum distance from head.
4. Increment the total seek count with this distance.
5. Currently serviced track position now becomes the new head position.
6. Go to step 2 until all tracks in request array have not been serviced.

Time Complexity: O ( N² )   Auxiliary Space: O ( N )

Simulate