Disk scheduling is done by operating systems to schedule I/O requests arriving for the disk and the algorithm used for the disk scheduling is called Disk Scheduling Algorithm.
In this post, we will discuss the Shortest Seek Time First Disk Scheduling Algorithm. As the name suggests, the I/O requests are addressed in the order where the distance between the head and the I/O request is least.
We will use C++ to write this algorithm due to the standard template library support. Hence, we will write the program of Shortest Seek Time First in C++, although, it’s very similar to C.
INPUT:
The first line is the size of the disk (m).
The second line is the number of I/O requests (n).
The third line is an array of I/O requests (a[n]).
The fourth line is the head position (h).
OUTPUT:
Print the total head movement and average head movement.
Here’s is the program of Shortest Seek Time First Algorithm.
#include<bits/stdc++.h>
using namespace std;
int main(){
int i,j,k,n,m,sum=0,x,y,h;
cout<<"Enter the size of disk\n";
cin>>m;
cout<<"Enter number of requests\n";
cin>>n;
cout<<"Enter the requests\n";
//creating two arrays, array a will store the input
//I/O requests and array b will store the output
vector <int> a(n),b;
//creating a map to store the count of each element
//in the array a.
map <int,int> mp;
for(i=0;i<n;i++){
cin>>a[i];
mp[a[i]]++;
}
for(i=0;i<n;i++){
if(a[i]>m){
cout<<"Error, Unknown position "<<a[i]<<"\n";
return 0;
}
}
cout<<"Enter the head position\n";
cin>>h;
int temp=h;
int ele;
b.push_back(h);
int count=0;
while(count<n){
//initially taking diff to be very large.
int diff=999999;
//traversing in map to find the least difference
for(auto q:mp){
if(abs(q.first-temp)<diff){
ele=q.first;
diff=abs(q.first-temp);
}
}
//deleting the element that has the least
//difference from the map
mp[ele]--;
if(mp[ele]==0){
mp.erase(ele);
}
//adding that element to our output array.
b.push_back(ele);
temp=ele;
count++;
}
//printing the output array
cout<<b[0];
temp=b[0];
for(i=1;i<b.size();i++){
cout<<" -> "<<b[i];
sum+=abs(b[i]-temp);
temp=b[i];
}
cout<<'\n';
cout<<"Total head movements = "<< sum<<'\n';
cout<<"Average head movement = "<<(float)sum/n<<'\n';
return 0;
}
OUTPUT:
Enter the size of disk 199 Enter number of requests 8 Enter the requests 98 183 37 122 14 124 65 67 Enter the head position 53 53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183 Total head movements = 236 Average head movement = 29.5
Other disk scheduling algorithms:
- FCFS Disk Scheduling
- Shortest Seek Time First Disk Scheduling
- SCAN Disk Scheduling
- CLOOK Disk Scheduling
- LOOK Disk Scheduling
- CSCAN Disk Scheduling
Let us know in the comments if you are having any questions regarding this Shortest Seek Time First Disk Scheduling Algorithm.
And if you found this post helpful, then please help us by sharing this post with your friends.
Thank You.
