Write a C Program to Implement the Disk Scheduling Algorithm for Shortest Seek Time First (SSTF)

Aim:

To write a C Program to Implement the Disk Scheduling Algorithm for Shortest Seek Time First (SSTF).

Description:

  • Disk Scheduling is the process of deciding which of the cylinder request is in the ready queue is to be accessed next.
  • The access time and the bandwidth can be improved by scheduling the servicing of disk I/O requests in good order.

Access Time:

The access time has two major components: Seek time and Rotational Latency.

Seek Time:

Seek time is the time for disk arm to move the heads to the cylinder containing the desired sector.

Rotational Latency:

Rotational latency is the additional time waiting for the disk to rotate the desired sector to the disk head.

Bandwidth:

The disk bandwidth is the total number of bytes transferred, divided by the total time between the first request for service and the completion of the last transfer.

Algorithm:

  1. Shortest Seek Time First Scheduling (SSTF) algorithm – This algorithm selects the request with the minimum seek time from the current head position.
  2. Since seek time increases with the number of cylinders traversed by the head, SSTF chooses the pending request closest to the current head position.
  3. The seek time is calculated.

Exercise:

  • Consider that a disk drive has 5,000 cylinders, numbered 0 to 4,999.
  • The drive is currently serving a request at cylinder 2,150, and the previous request was at cylinder 1,805.
  • The queue of pending requests, in FIFO order, is: 2,069, 1,212, 2,296, 2,800, 544, 1,618, 356, 1,523, 4,965, 3681

Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests for each of the following disk-scheduling algorithms?

  1. FCFS
  2. SSTF
  3. SCAN
  4. LOOK
  5. C-SCAN
  6. C-LOOK

Program:

#include<stdio.h>
#include<stdbool.h>
int request[50];
long SIZE;
bool flag[50];
int dist(int,int);
struct max{
int data;
int dis;
int dat; 
}kate[50],kat;
struct max check(int head,int n)
{
int i;
int j=0;
for(i=0;i<n;i++)
{
if(flag[i]==0){
kate[j].dis=dist(head,request[i]);
kate[j].data=request[i];
kate[j].dat=i;
j++;
}
}
n=j;
for (i = 0; i < n-1; i++)      
{     
for (j = 0; j < n-i-1; j++) 
{
if (kate[j].dis > kate[j+1].dis)
{
int temp=kate[j].data;
kate[j].data=kate[j+1].data;
kate[j+1].data=temp;
temp=kate[j].dis;
kate[j].dis=kate[j+1].dis;
kate[j+1].dis=temp;
temp=kate[j].dat;
kate[j].dat=kate[j+1].dat;
kate[j+1].dat=temp;
}
}
}
return kate[0];
}
int dist(int a,int b)
{
if(a>b)
return a-b;
return b-a;
}
void stsk(int n)
{
int head,i;
int seekcount=0;
printf("ENTER THE CURRENT HEAD :\n");
scanf("%d",&head);
printf("SEEK SEQUENCE = ")	;
for(i=0;i<n;i++)
{
if(request[i]<SIZE-1)
{
printf("%d ",head);
kat=check(head,n);	
seekcount=seekcount+kat.dis;
head=kat.data;
flag[kat.dat]=true;
}
}
printf("%d\nTOTAL DISTANCE : %d",head,seekcount);	
}
int main()
{
int n,i;
printf("ENTER THE DISK SIZE :\n");
scanf("%d",&SIZE);
printf("ENTER THE NO OF REQUEST SEQUENCE :\n");
scanf("%d",&n);
printf("ENTER THE REQUEST SEQUENCE :\n");
for(i=0;i<n;i++){
scanf("%d",&request[i]);
flag[i]=0;
}
stsk(n);
}

Execution:

Input:
200 8 176 79 34 60 92 11 41 114 50


Output:

ENTER THE DISK SIZE :
ENTER THE NO OF REQUEST SEQUENCE :
ENTER THE REQUEST SEQUENCE :
ENTER THE CURRENT HEAD :
SEEK SEQUENCE = 50 41 34 11 60 79 92 114 176
TOTAL DISTANCE : 204

Result:

Thus Disk Scheduling Algorithm for Shortest Seek Time First (SSTF) program was executed Successfully.

Leave a Comment