C Program to Simulate SCAN (Elevator) Disk Scheduling Algorithm in OS | Program Logic Explained


SCAN DISK disk scheduling algorithm c program
C Program to Simulate SCAN Algorithm - Code by Nived Kannada


SCAN Algorithm is used for Disk Scheduling in Operating System.
In this post, we are going to see how to simulate this SCAN algorithm using C. The logic is actually very simple.

In this program, we have 3 arrays namely queue[], queue1[] and queue2[]
queue[] is our main array. 

After reading the max range, initial headposition and the number of upcoming requests, we are going to read each of the incoming requests. Right within the loop in which we read those requests, we will split those into the two different arrays queue1 and queue2 based on whether it is greater than the initial headposition or not. 


Web Design for Beginners in Malayalam - Full Course (മലയാà´³ം)
WATCH VIDEO

That is, here we are reading the initial head position before reading the requests from the user, so that we can check whether each request is greater than initial headposition. If a request is greater than headposition, then that request will go to the array queue1[]. temp1 and temp2 are indexing variables used for queue1[] and queue2[] respectively.

As we all know, the SCAN algorithm starts from the headposition, moves towards the end of the disk and then reverses direction and moves towards 0. It processes all the requests that come in its way while this traversal occurs. 

So, after reading all the requests from the user, we have to sort the queue1[] in its ascending order and queue2[] in the descending order. You can use any sorting methods for this. 

(Here we are assuming that the head always move towards the largest cylinder at first.)

After sorting, we have to concatenate these two arrays queue1[] and queue2[] and then copy it to queue[]. Then we will have a proper queue[] full of requests in the correct order according to the SCAN algorithm. But still, we have to set the 0th index of array queue[] to be equal to the headposition. So, now we can traverse through the requests properly and calculate the seek time and see how the disk head moves.

Make sure to read the comments given for each section of code to understand the logic even further.









Open in OnlineGDB 

// C Program to Simulate SCAN Disk Scheduling Algorithm
//visit www.nanogalaxy.org for more programs.

#include<stdio.h>
int absoluteValue(int); // Declaring function absoluteValue

void main()
{
    int queue[25],n,headposition,i,j,k,seek=0, maxrange,
    difference,temp,queue1[20],queue2[20],temp1=0,temp2=0;
    float averageSeekTime;

    // Reading the maximum Range of the Disk. 
    printf("Enter the maximum range of Disk: ");
    scanf("%d",&maxrange);
    
    // Reading the number of Queue Requests(Disk access requests)
    printf("Enter the number of queue requests: ");
    scanf("%d",&n);
    
    // Reading the initial head position.(ie. the starting point of execution)
    printf("Enter the initial head position: ");
    scanf("%d",&headposition);
    
    // Reading disk positions to be read in the order of arrival
    printf("Enter the disk positions to be read(queue): ");
    for(i=1;i<=n;i++)   // Note that i varies from 1 to n instead of 0 to n-1
    {
        scanf("%d",&temp);  //Reading position value to a temporary variable
        
        //Now if the requested position is greater than current headposition,
        //then pushing that to array queue1
        if(temp>headposition)
        {
            queue1[temp1]=temp; //temp1 is the index variable of queue1[]
            temp1++; //incrementing temp1
        }
        else    //else if temp < current headposition,then push to array queue2[]
        {   
            queue2[temp2]=temp; //temp2 is the index variable of queue2[]
            temp2++;
        }
    }
    
    //Now we have to sort the two arrays
    //SORTING array queue1[] in ascending order
    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;
            }
        }
    }
    
    //SORTING array queue2[] in descending order
    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;
            }
        }
    }    
    
    //Copying first array queue1[] into queue[]
    for(i=1,j=0;j<temp1;i++,j++)
    {
        queue[i]=queue1[j]; 
    }
    
    //Setting queue[i] to maxrange because the head goes to
    //end of disk and comes back in scan Algorithm
    queue[i]=maxrange;
    
    //Copying second array queue2[] after that first one is copied, into queue[]
    for(i=temp1+2,j=0;j<temp2;i++,j++)
    {
        queue[i]=queue2[j];
    }
    
    //Setting queue[i] to 0. Because that is the innermost cylinder.
    queue[i]=0;

    //At this point, we have the queue[] with the requests in the 
    //correct order of execution as per scan algorithm.
    //Now we have to set 0th index of queue[] to be the initial headposition. 
    queue[0]=headposition;
    
    // Calculating SEEK TIME. seek is initially set to 0 in the declaration part.
    
    for(j=0; j<=n; j++) //Loop starts from headposition. (ie. 0th index of queue) 
    {   
        // Finding the difference between next position and current position.
        difference = absoluteValue(queue[j+1]-queue[j]);
        
        // Adding difference to the current seek time value
        seek = seek + difference;
        
        // Displaying a message to show the movement of disk head
        printf("Disk head moves from position %d to %d with Seek %d \n",
        queue[j], queue[j+1], difference);
    }
    
    // Calculating Average Seek time 
    averageSeekTime = seek/(float)n;
    
    //Display Total and Average Seek Time(s)
    printf("Total Seek Time= %d\n", seek);
    printf("Average Seek Time= %f\n", averageSeekTime);
}

// Defining function absoluteValue
int absoluteValue(int x)
{
    if(x>0)
    {
        return x;
    }
    else
    {
        return x*-1;
    }
}


// END OF CODE 
//Code written and commented by Nived Kannada

Output





If you found this article helpful, please share it with your friends. We are happy to help if you have any doubts. Please let us know if there are any errors in this code. Thanks!

1 comment:

  1. Good day! is it alright if you show another program where the head moves towards[zero] the left? It would be greatly appreciated!

    ReplyDelete

Pages

Nanogalaxy is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for website owners to earn advertising fees by advertising and linking to amazon.com and any other website that may be affiliated with Amazon Service LLC Associates Program.