SCAN & C - SCAN Disk Scheduling Algorithm

 SCAN Disk Scheduling Algorithm

SCAN is a disk scheduling algorithm that works by servicing I/O requests in a specific order. 

In SCAN, the disk head moves in a particular direction (either towards the outermost or innermost track of the disk), servicing all the requests in its path until it reaches the end of the disk. At that point, the direction of the disk head is reversed, and it begins servicing requests in the opposite direction.

//Scan

#include <stdio.h>

#include <math.h>

int main()

{

    int queue[20], n, head, i, j, k, seek = 0, max, diff, temp, queue1[20],

    queue2[20], temp1 = 0, temp2 = 0;

    float avg;

    printf("Enter the max range of disk\n");

    scanf("%d", &max);

    printf("Enter the initial head position\n");

    scanf("%d", &head);

    printf("Enter the size of queue request\n");

    scanf("%d", &n);

    printf("Enter the queue of disk positions to be read\n");

    for (i = 1; i <= n; i++)

    {

        scanf("%d", &temp);

        if (temp >= head)

        {

            queue1[temp1] = temp;

            temp1++;

        }

        else

        {

            queue2[temp2] = temp;

            temp2++;

        }

    }

    for (i = 0; i < temp1 - 1; i++)

    {

        for (j = i + 1; j < temp1; j++)

        {

            if (queue1[i] > queue1[j])

            {

                temp = queue1[i];

                queue1[i] = queue1[j];

                queue1[j] = temp;

            }

        }

    }

    for (i = 0; i < temp2 - 1; i++)

    {

        for (j = i + 1; j < temp2; j++)

        {

            if (queue2[i] < queue2[j])

            {

                temp = queue2[i];

                queue2[i] = queue2[j];

                queue2[j] = temp;

            }

        }

    }

    for (i = 1, j = 0; j < temp1; i++, j++)

        queue[i] = queue1[j];

    queue[i] = max;

    for (i = temp1 + 2, j = 0; j < temp2; i++, j++)

        queue[i] = queue2[j];

    queue[i] = 0;

    queue[0] = head;

    for (j = 0; j <= n + 1; j++)

    {

        diff = abs(queue[j + 1] - queue[j]);

        seek += diff;

        printf("Disk head moves from %d to %d with seek %d\n", queue[j],

        queue[j + 1], diff);

    }

    printf("Total seek time is %d\n", seek);

    avg = seek / (float)n;

    printf("Average seek time is %f\n", avg);

    return 0;

}

The SCAN algorithm is also known as the Elevator algorithm because the disk head behaves like an elevator moving up and down the floors of a building.

In SCAN, when a new I/O request arrives, it is added to the queue, and the queue is sorted based on the location of the request on the disk. The requests are then serviced in the order they appear in the sorted queue, with the disk head moving in the appropriate direction.

SCAN scheduling can result in a more efficient disk usage as it minimizes the amount of seeking required by the disk head. However, it can lead to longer wait times for requests that are located far away from the current position of the disk head.

To address this issue, variations of the SCAN algorithm have been developed, such as the C-SCAN algorithm, which works by moving the disk head only in one direction and wrapping around to the beginning of the disk when it reaches the end. This ensures that requests located far away from the current position of the disk head are serviced quickly, as they will be on the path of the disk head when it wraps around to the beginning of the disk.

C - SCAN Disk Scheduling Algorithm

C-SCAN (Circular SCAN) is a disk scheduling algorithm that is a variation of the SCAN algorithm. It works by servicing I/O requests in a specific order, similar to the SCAN algorithm, but with a different approach to handling requests at the end of the disk.

//C Scan

#include <stdio.h>

#include <stdlib.h>

int main(){

    int RQ[100], i, j, n, TotalHeadMoment = 0, initial, size, move;

    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);

    printf("Enter total disk size\n");

    scanf("%d", &size);

    for (i = 0; i < n; i++){

        for (j = 0; j < n - i - 1; j++){

            if (RQ[j] > RQ[j + 1]){

                int temp;

                temp = RQ[j];

                RQ[j] = RQ[j + 1];

                RQ[j + 1] = temp;

            }

        }

    }

int index;

    for (i = 0; i < n; i++){

        if (initial < RQ[i]){

            index = i;

            break;

        }

    }

    if (move == 1){

        for (i = index; i < n; i++){

            TotalHeadMoment = TotalHeadMoment + abs(RQ[i] - initial);

            initial = RQ[i];

        }

        TotalHeadMoment = TotalHeadMoment + abs(size - RQ[i - 1] - 1);

        TotalHeadMoment = TotalHeadMoment + abs(size - 1 - 0);

        initial = 0;

        for (i = 0; i < index; i++){

        TotalHeadMoment = TotalHeadMoment + abs(RQ[i] - initial);

            initial = RQ[i];

        }

    }

    else{

        for (i = index - 1; i >= 0; i--){

            TotalHeadMoment = TotalHeadMoment + abs(RQ[i] - initial);

            initial = RQ[i];

        }

        TotalHeadMoment = TotalHeadMoment + abs(RQ[i + 1] - 0);

        TotalHeadMoment = TotalHeadMoment + abs(size - 1 - 0);

        initial = size - 1;

for (i = n - 1; i >= index; i--){

            TotalHeadMoment = TotalHeadMoment + abs(RQ[i] - initial);

            initial = RQ[i];

        }

    }

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

    return 0;

}

In C-SCAN, the disk head moves in one direction, servicing all the requests in its path until it reaches the end of the disk. At that point, it jumps to the beginning of the disk and continues servicing requests in the same direction. This creates a circular path, hence the name C-SCAN.

When a new I/O request arrives, it is added to the request queue, and the queue is sorted based on the location of the request on the disk. The requests are then serviced in the order they appear in the sorted queue, with the disk head moving in one direction.

C-SCAN scheduling is more efficient than SCAN in terms of disk usage because it eliminates the need for the disk head to travel all the way back to the other end of the disk to service requests on the opposite end. Instead, requests at the end of the disk are handled quickly because the disk head jumps to the beginning of the disk.

However, C-SCAN scheduling can lead to longer wait times for requests that are located far away from the current position of the disk head, especially if there are many requests in the queue.

Overall, C-SCAN is suitable for systems with high levels of disk activity and a large number of I/O requests, where efficient disk usage is important. However, it may not be the most suitable algorithm for systems with low to moderate levels of disk activity.