Implementation of Disk Scheduling Algorithms - FCFS,: SSTF, Cscan

K. J.
Somaiya College of Engineering, Mumbai-77

(An Autonomous College Affiliated to University of Mumbai)
Batch: B4 Roll No.: 1913121

Experiment / assignment / tutorial No. 11.
Grade: AA / AB / BB / BC / CC / CD /DD
Signature of the Staff In-charge with date
TITLE: Deadlock
AIM: Implementation of Disk scheduling algorithms
OUTCOME: Student can understand working of an OS as a manager for file, memory and
I/O system.
 Implementation of Disk scheduling algorithms - FCFS,

SSTF, CSCAN.
FCFS Algorithms:
1. Input the maximum number of cylinders and work queue and its head starting position.
2. First Come First Serve Scheduling (FCFS) algorithm – The operations are performed in
order requested.
3. There is no reordering of work queue.
4. Every request is serviced, so there is no starvation.
5. The seek time is calculated.
6. Shortest Seek Time First Scheduling (SSTF) algorithm – This algorithm selects the request
with the minimum seek time from the current head position.
7. Since seek time increases with the number of cylinders traversed by the head, SSTF
chooses the pending request closest to the current head position.
9. SCAN Scheduling algorithm – The disk arm starts at one end of the disk, and moves
toward the other end, servicing requests as it reaches each cylinder, until it gets to the other
end of the disk.
10. At the other end, the direction of head movement is reversed, and servicing continues.
11. The head continuously scans back and forth across the disk.
13. Display the seek time and terminate the program
SSTF 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.
Department of Electronics and Telecommunication Engineering
OS/Sem V/ Aug- Dec 20 Page No

K. J. Somaiya College of Engineering, Mumbai-77
6. Go to step 2 until all tracks in request array have not been serviced.
 Take one example and draw diagram and verify theoretical

results.
1. Consider a disk queue with requests for I/O to blocks on cylinders 98, 183,
41, 122, 14, 124, 65, 67. The SSTF scheduling algorithm is used. The head
is initially at cylinder number 53 moving towards larger cylinder numbers on
its servicing pass. The cylinders are numbered from 0 to 199. The total
head movement (in number of cylinders) incurred while servicing these
requests is .
Solution-
Total head movements incurred while servicing these requests

= (65 – 53) + (67 – 65) + (67 – 41) + (41 – 14) + (98 – 14) + (122 – 98) + (124 –
122) + (183 – 124)
= 12 + 2 + 26 + 27 + 84 + 24 + 2 + 59
= 236
2. Consider a disk system with 100 cylinders. The requests to access the
cylinders occur in following sequence-
4, 34, 10, 7, 19, 73, 2, 15, 6, 20

Assuming that the head is currently at cylinder 50, what is the time taken to satisfy
all requests if it takes 1 ms to move from one cylinder to adjacent one and shortest
seek time first policy is used?
Solution-
Total head movements incurred while servicing these requests

= (50 – 34) + (34 – 20) + (20 – 19) + (19 – 15) + (15 – 10) + (10 – 7) + (7 – 6) + (6
– 4) + (4 – 2) + (73 – 2)
= 16 + 14 + 1 + 4 + 5 + 3 + 1 + 2 + 2 + 71
= 119
Time taken for one head movement = 1 msec. So,

Time taken for 119 head movements
= 119 x 1 msec
= 119 msec
 Write full code for all algorithm along with output and
screen shot.

FCFS:
CODE:
#include <conio.h>
#include <stdio.h>
int main()
{
int i, j, sum = 0, n;
int ar[20], tm[20];
int disk;
printf("enter number of location\t");
scanf("%d", &n);
printf("enter position of head\t");
scanf("%d", &disk);
printf("enter elements of disk queue\n");
for (i = 0; i < n; i++)
{
scanf("%d", &ar[i]);
tm[i] = disk - ar[i];
if (tm[i] < 0)
{
tm[i] = ar[i] - disk;
}
disk = ar[i];
sum = sum + tm[i];
}
/*for(i=0;i<n;i++)
{
printf("\n%d",tm[i]);
} */
printf("\nmovement of total cylinders %d", sum);

getch();
return 0;
}
OUTPUT:
SSTF:
CODE:
#include<stdio.h>
#include<stdlib.h>
int main()
{
int RQ[100],i,n,TotalHeadMoment=0,initial,count=0;
printf("Enter the number of Requests\n");
scanf("%d",&n);
printf("Enter the Requests sequence\n");
for(i=0;i<n;i++)
scanf("%d",&RQ[i]);
printf("Enter initial head position\n");
scanf("%d",&initial);
// logic for sstf disk scheduling

/* loop will execute until all process is completed*/
while(count!=n)
{
int min=1000,d,index;

for(i=0;i<n;i++)
{
d=abs(RQ[i]-initial);
if(min>d)
{
min=d;
index=i;
}
}
TotalHeadMoment=TotalHeadMoment+min;
initial=RQ[index];
// 1000 is for max
// you can use any number
RQ[index]=1000;
count++;
}
printf("Total head movement is %d",TotalHeadMoment);

return 0;
}
OUTPUT:

Signature of faculty in-charge

Implementation of Disk Scheduling Algorithms - FCFS,: SSTF, Cscan

Uploaded by

Copyright:

Available Formats

Implementation of Disk Scheduling Algorithms - FCFS,: SSTF, Cscan

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Implementation of Disk Scheduling Algorithms - FCFS,: SSTF, Cscan

Uploaded by

Copyright:

Available Formats

K. J.

Somaiya College of Engineering, Mumbai-77

Batch: B4 Roll No.: 1913121

Signature of the Staff In-charge with date

 Implementation of Disk scheduling algorithms - FCFS,

Department of Electronics and Telecommunication Engineering

OS/Sem V/ Aug- Dec 20 Page No

 Take one example and draw diagram and verify theoretical

Total head movements incurred while servicing these requests

Department of Electronics and Telecommunication Engineering

OS/Sem V/ Aug- Dec 20 Page No

Total head movements incurred while servicing these requests

Time taken for one head movement = 1 msec. So,

Department of Electronics and Telecommunication Engineering

OS/Sem V/ Aug- Dec 20 Page No

OS/Sem V/ Aug- Dec 20 Page No

// logic for sstf disk scheduling

Department of Electronics and Telecommunication Engineering

OS/Sem V/ Aug- Dec 20 Page No

Department of Electronics and Telecommunication Engineering

OS/Sem V/ Aug- Dec 20 Page No

printf("Total head movement is %d",TotalHeadMoment);

Department of Electronics and Telecommunication Engineering

OS/Sem V/ Aug- Dec 20 Page No

Department of Electronics and Telecommunication Engineering

OS/Sem V/ Aug- Dec 20 Page No

You might also like