==============================================================
Experiment 15: Disk Scheduling Algorithms
(FCFS, SSTF, SCAN, C-SCAN, LOOK)
==============================================================
[Back to Index]
==============================================================
PART 1: First Come First Serve (FCFS)
==============================================================
ALGORITHM:
1. Read number of disk requests n.
2. Read the request queue.
3. Read the initial head position.
4. Set total head movement = 0.
5. For each request in order:
Calculate distance = |current head - request|.
Add distance to total movement.
Move head to that request.
6. Display total head movement.
--------------------------------------------------------------
SOURCE CODE: disk_fcfs.c
--------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
int main() {
int n, head, total = 0;
printf("Enter number of requests: ");
scanf("%d", &n);
int req[n];
printf("Enter the requests:\n");
for(int i = 0; i < n; i++)
scanf("%d", &req[i]);
printf("Enter initial head position: ");
scanf("%d", &head);
printf("\nStep\tFrom\tTo\tMovement\n");
printf("--------------------------------\n");
for(int i = 0; i < n; i++) {
int movement = abs(head - req[i]);
printf("%d\t%d\t%d\t%d\n", i+1, head, req[i], movement);
total += movement;
head = req[i];
}
printf("--------------------------------\n");
printf("Total head movement = %d\n", total);
return 0;
}
--------------------------------------------------------------
COMPILE: gcc -o disk_fcfs disk_fcfs.c
==============================================================
PART 2: Shortest Seek Time First (SSTF)
==============================================================
ALGORITHM:
1. Read number of disk requests.
2. Read request queue.
3. Read initial head position.
4. Mark all requests as unvisited.
5. From current head:
Find request with minimum absolute distance.
Move head to that request.
Add movement to total.
Mark request visited.
6. Repeat until all requests are serviced.
--------------------------------------------------------------
SOURCE CODE: disk_sstf.c
--------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
int main() {
int n, head, total = 0;
printf("Enter number of requests: ");
scanf("%d", &n);
int req[n], visited[n];
printf("Enter the requests:\n");
for(int i = 0; i < n; i++) {
scanf("%d", &req[i]);
visited[i] = 0;
}
printf("Enter initial head position: ");
scanf("%d", &head);
printf("\nStep\tFrom\tTo\tMovement\n");
printf("--------------------------------\n");
for(int step = 0; step < n; step++) {
int min = 100000, index = -1;
for(int i = 0; i < n; i++) {
if(!visited[i]) {
int dist = abs(head - req[i]);
if(dist < min) {
min = dist;
index = i;
}
}
}
printf("%d\t%d\t%d\t%d\n", step+1, head, req[index], min);
total += min;
head = req[index];
visited[index] = 1;
}
printf("--------------------------------\n");
printf("Total head movement = %d\n", total);
return 0;
}
--------------------------------------------------------------
COMPILE: gcc -o disk_sstf disk_sstf.c
==============================================================
PART 3: SCAN (Elevator Algorithm)
==============================================================
ALGORITHM:
1. Read number of disk requests.
2. Read request queue.
3. Read initial head position.
4. Read disk size.
5. Read direction (LEFT or RIGHT).
6. Sort request queue.
7. If direction = RIGHT:
Service all requests greater than head (ascending).
Move to disk end.
Reverse and service remaining smaller requests.
8. If direction = LEFT:
Service smaller requests first (descending).
Move to 0.
Reverse and service larger requests.
9. Compute total movement.
--------------------------------------------------------------
SOURCE CODE: disk_scan.c
--------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
void sort(int a[], int n) {
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++)
if(a[j]>a[j+1]) {
int t=a[j]; a[j]=a[j+1]; a[j+1]=t;
}
}
int main() {
int n, head, size, dir;
int total = 0;
printf("Enter number of requests: ");
scanf("%d",&n);
int req[n];
printf("Enter requests:\n");
for(int i=0;i<n;i++)
scanf("%d",&req[i]);
printf("Enter initial head position: ");
scanf("%d",&head);
printf("Enter disk size (max track number): ");
scanf("%d",&size);
printf("Enter direction (1=RIGHT, 0=LEFT): ");
scanf("%d",&dir);
sort(req,n);
printf("\nStep\tFrom\tTo\tMovement\n");
printf("--------------------------------\n");
int cur = head, step = 1;
if(dir==1) { // RIGHT
for(int i=0;i<n;i++){
if(req[i] >= head){
printf("%d\t%d\t%d\t%d\n",step++,cur,req[i],abs(cur-req[i]));
total += abs(cur-req[i]);
cur = req[i];
}
}
// move to disk end
printf("%d\t%d\t%d\t%d\n",step++,cur,size-1,abs(cur-(size-1)));
total += abs(cur-(size-1));
cur = size-1;
// reverse direction
for(int i=n-1;i>=0;i--){
if(req[i] < head){
printf("%d\t%d\t%d\t%d\n",step++,cur,req[i],abs(cur-req[i]));
total += abs(cur-req[i]);
cur = req[i];
}
}
} else { // LEFT
for(int i=n-1;i>=0;i--){
if(req[i] <= head){
printf("%d\t%d\t%d\t%d\n",step++,cur,req[i],abs(cur-req[i]));
total += abs(cur-req[i]);
cur = req[i];
}
}
// move to 0
printf("%d\t%d\t%d\t%d\n",step++,cur,0,abs(cur));
total += abs(cur);
cur = 0;
// reverse
for(int i=0;i<n;i++){
if(req[i] > head){
printf("%d\t%d\t%d\t%d\n",step++,cur,req[i],abs(cur-req[i]));
total += abs(cur-req[i]);
cur = req[i];
}
}
}
printf("--------------------------------\n");
printf("Total head movement = %d\n",total);
return 0;
}
--------------------------------------------------------------
COMPILE: gcc -o disk_scan disk_scan.c
==============================================================
PART 4: C-SCAN (Circular SCAN)
==============================================================
ALGORITHM:
1. Read number of disk requests.
2. Read request queue.
3. Read initial head position.
4. Read disk size.
5. Sort requests.
6. Move head in one direction only (RIGHT assumed):
Service all requests greater than head.
7. Move head to disk end.
8. Jump to track 0.
9. Continue servicing remaining smaller requests.
10. Calculate total head movement.
--------------------------------------------------------------
SOURCE CODE: disk_cscan.c
--------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
void sort(int a[], int n){
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++)
if(a[j]>a[j+1]){
int t=a[j]; a[j]=a[j+1]; a[j+1]=t;
}
}
int main(){
int n, head, size;
int total=0;
printf("Enter number of requests: ");
scanf("%d",&n);
int req[n];
printf("Enter requests:\n");
for(int i=0;i<n;i++)
scanf("%d",&req[i]);
printf("Enter initial head position: ");
scanf("%d",&head);
printf("Enter disk size (max track number): ");
scanf("%d",&size);
sort(req,n);
printf("\nStep\tFrom\tTo\tMovement\n");
printf("--------------------------------\n");
int cur=head, step=1;
// service requests to the RIGHT first
for(int i=0;i<n;i++){
if(req[i]>=head){
printf("%d\t%d\t%d\t%d\n",step++,cur,req[i],abs(cur-req[i]));
total+=abs(cur-req[i]);
cur=req[i];
}
}
// move to disk end
printf("%d\t%d\t%d\t%d\n",step++,cur,size-1,abs(cur-(size-1)));
total+=abs(cur-(size-1));
cur=size-1;
// jump to 0
printf("%d\t%d\t%d\t%d\n",step++,cur,0,abs(cur-0));
total+=abs(cur-0);
cur=0;
// service remaining requests
for(int i=0;i<n;i++){
if(req[i]<head){
printf("%d\t%d\t%d\t%d\n",step++,cur,req[i],abs(cur-req[i]));
total+=abs(cur-req[i]);
cur=req[i];
}
}
printf("--------------------------------\n");
printf("Total head movement = %d\n",total);
return 0;
}
--------------------------------------------------------------
COMPILE: gcc -o disk_cscan disk_cscan.c
==============================================================
PART 5: LOOK
==============================================================
ALGORITHM:
1. Read disk requests.
2. Read initial head position.
3. Sort the request queue.
4. Choose direction (LEFT or RIGHT).
5. If RIGHT:
Service all requests greater than head (ascending).
Reverse direction.
Service remaining smaller requests (descending).
6. If LEFT:
Service smaller requests first.
Reverse and service larger ones.
7. Sum total head movement.
--------------------------------------------------------------
SOURCE CODE: disk_look.c
--------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
void sort(int a[], int n){
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++)
if(a[j]>a[j+1]){
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
int main(){
int n, head, dir;
int total = 0;
printf("Enter number of requests: ");
scanf("%d",&n);
int req[n];
printf("Enter the requests:\n");
for(int i=0;i<n;i++)
scanf("%d",&req[i]);
printf("Enter initial head position: ");
scanf("%d",&head);
printf("Enter direction (1 = RIGHT, 0 = LEFT): ");
scanf("%d",&dir);
sort(req,n);
printf("\n-------------------------------------------\n");
printf("Step\tFrom\tTo\tMovement\n");
printf("-------------------------------------------\n");
int cur = head, step = 1;
if(dir==1){ // RIGHT FIRST
for(int i=0;i<n;i++){
if(req[i] >= head){
int move = abs(cur - req[i]);
printf("%d\t%d\t%d\t%d\n", step, cur, req[i], move);
total += move;
cur = req[i];
step++;
}
}
for(int i=n-1;i>=0;i--){
if(req[i] < head){
int move = abs(cur - req[i]);
printf("%d\t%d\t%d\t%d\n", step, cur, req[i], move);
total += move;
cur = req[i];
step++;
}
}
} else { // LEFT FIRST
for(int i=n-1;i>=0;i--){
if(req[i] <= head){
int move = abs(cur - req[i]);
printf("%d\t%d\t%d\t%d\n", step, cur, req[i], move);
total += move;
cur = req[i];
step++;
}
}
for(int i=0;i<n;i++){
if(req[i] > head){
int move = abs(cur - req[i]);
printf("%d\t%d\t%d\t%d\n", step, cur, req[i], move);
total += move;
cur = req[i];
step++;
}
}
}
printf("-------------------------------------------\n");
printf("Total Head Movement = %d\n", total);
printf("-------------------------------------------\n");
return 0;
}
--------------------------------------------------------------
COMPILE: gcc -o disk_look disk_look.c
==============================================================
[Prev: Exp 14] | [Back to Index]
==============================================================