SCAN Disk Scheduling Algorithm

Aim

To simulate the SCAN disk scheduling algorithm and compute the total head movement, displaying Step, From, To, Movement.

---

Theory

The SCAN algorithm moves the disk head in one direction first, servicing all requests in its path until it reaches the end of the disk, then reverses direction and services remaining requests.

Because the head sweeps back and forth like an elevator, SCAN is also called:

👉 Elevator Algorithm

Advantages

• Better than FCFS in reducing seek time

• Avoids starvation seen in SSTF

• Provides more uniform waiting time

Disadvantage

• Requests at extreme ends may wait longer

---

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.

---

Program: SCAN Disk Scheduling (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;
}

---

Example 

Input

Enter number of requests: 8
Enter requests:
98 183 37 122 14 124 65 67
Enter initial head position: 53
Enter disk size (max track number): 200
Enter direction (1=RIGHT, 0=LEFT): 1

---

Sorted Queue

14 37 65 67 98 122 124 183

---

Sample Run (SCAN RIGHT first)

Service right side:

53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 (disk end)

Then reverse:

199 → 37 → 14

---

Output Table

Step   From   To    Movement
--------------------------------
1      53     65    12
2      65     67    2
3      67     98    31
4      98     122   24
5      122    124   2
6      124    183   59
7      183    199   16
8      199    37    162
9      37     14    23
--------------------------------
Total head movement = 331

---

Observation

Algorithm	Total Movement
FCFS	640
SSTF	236
SCAN	331

👉 SCAN gives better fairness than SSTF but sometimes more movement.

---

Result

The SCAN disk scheduling algorithm was successfully implemented and tested.

For the given example, total head movement = 331 tracks.