Comparison of Disk Scheduling Algorithms (FCFS, SSTF, SCAN, C-SCAN, LOOK)

---

Aim

To implement and compare the disk scheduling algorithms FCFS, SSTF, SCAN, C-SCAN, and LOOK using the same set of disk requests and compute their total head movements.

---

Objectives

• Understand different disk scheduling techniques

• Measure total seek movement

• Compare efficiency of algorithms

---

Theory

1. FCFS (First Come First Serve)

• Services requests in arrival order

• Simple but inefficient

• Can cause large head movement

2. SSTF (Shortest Seek Time First)

• Selects nearest request from current head

• Reduces seek time

• May cause starvation

3. SCAN (Elevator Algorithm)

• Head moves in one direction servicing requests

• Goes to disk end, then reverses

• Better fairness than SSTF

4. C-SCAN (Circular SCAN)

• Head moves in one direction only

• After reaching disk end, jumps to start

• Provides uniform waiting time

5. LOOK

• Similar to SCAN

• Does not go to disk end

• Stops at last request and reverses

• Saves unnecessary movement

---

Algorithm (General Steps)

1. Input number of disk requests.

2. Input request queue.

3. Input initial head position.

4. Input disk size.

5. Apply each algorithm:

   • FCFS → sequential service

   • SSTF → choose nearest request

   • SCAN → move to end then reverse

   • C-SCAN → move to end then jump to start

   • LOOK → reverse at last request

6. Compute total head movement.

7. Display comparison table.

---

Program (C Implementation)

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

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 fcfs(int req[], int n, int head){
    int total=0, cur=head;
    for(int i=0;i<n;i++){
        total+=abs(cur-req[i]);
        cur=req[i];
    }
    return total;
}

int sstf(int req[], int n, int head){
    int visited[MAX]={0}, total=0, cur=head;
    for(int s=0;s<n;s++){
        int min=1e9, idx=-1;
        for(int i=0;i<n;i++){
            if(!visited[i]){
                int d=abs(cur-req[i]);
                if(d<min){min=d; idx=i;}
            }
        }
        visited[idx]=1;
        total+=min;
        cur=req[idx];
    }
    return total;
}

int scan(int req[], int n, int head, int size){
    int a[MAX]; for(int i=0;i<n;i++) a[i]=req[i];
    sort(a,n);
    int total=0, cur=head;

    for(int i=0;i<n;i++)
        if(a[i]>=head){ total+=abs(cur-a[i]); cur=a[i]; }

    total+=abs(cur-(size-1));
    cur=size-1;

    for(int i=n-1;i>=0;i--)
        if(a[i]<head){ total+=abs(cur-a[i]); cur=a[i]; }

    return total;
}

int cscan(int req[], int n, int head, int size){
    int a[MAX]; for(int i=0;i<n;i++) a[i]=req[i];
    sort(a,n);
    int total=0, cur=head;

    for(int i=0;i<n;i++)
        if(a[i]>=head){ total+=abs(cur-a[i]); cur=a[i]; }

    total+=abs(cur-(size-1));
    cur=size-1;

    total+=abs(cur-0);
    cur=0;

    for(int i=0;i<n;i++)
        if(a[i]<head){ total+=abs(cur-a[i]); cur=a[i]; }

    return total;
}

int look(int req[], int n, int head){
    int a[MAX]; for(int i=0;i<n;i++) a[i]=req[i];
    sort(a,n);
    int total=0, cur=head;

    for(int i=0;i<n;i++)
        if(a[i]>=head){ total+=abs(cur-a[i]); cur=a[i]; }

    for(int i=n-1;i>=0;i--)
        if(a[i]<head){ total+=abs(cur-a[i]); cur=a[i]; }

    return total;
}

int main(){
    int n, head, size, req[MAX];

    printf("Enter number of requests: ");
    scanf("%d",&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: ");
    scanf("%d",&size);

    printf("\n=========================================\n");
    printf(" Disk Scheduling Comparison Table\n");
    printf("=========================================\n");
    printf("Algorithm\tTotal Head Movement\n");
    printf("-----------------------------------------\n");

    printf("FCFS\t\t%d\n",fcfs(req,n,head));
    printf("SSTF\t\t%d\n",sstf(req,n,head));
    printf("SCAN\t\t%d\n",scan(req,n,head,size));
    printf("C-SCAN\t\t%d\n",cscan(req,n,head,size));
    printf("LOOK\t\t%d\n",look(req,n,head));

    printf("=========================================\n");

    return 0;
}

---

Sample Input

Number of requests = 8
Queue = 98 183 37 122 14 124 65 67
Initial head = 53
Disk size = 200

---

Sample Output

=========================================
 Disk Scheduling Comparison Table
=========================================
Algorithm       Total Head Movement
-----------------------------------------
FCFS            640
SSTF            236
SCAN            331
C-SCAN          382
LOOK            299
=========================================

---

Observation

• SSTF gives minimum movement but may cause starvation

• LOOK reduces unnecessary travel compared to SCAN

• C-SCAN provides uniform waiting time

• FCFS is simplest but inefficient

---

Result

The disk scheduling algorithms FCFS, SSTF, SCAN, C-SCAN, and LOOK were successfully implemented and compared.
Among them, SSTF produced the least head movement for the given input.