Understanding the 'SCAN' Disk Scheduling Algorithm in Operating Systems

Disk scheduling is a crucial aspect of operating systems, ensuring that disk I/O requests are handled efficiently to improve system performance. One of the most popular disk scheduling algorithms is SCAN, also known as the Elevator Algorithm. Let’s explore how this algorithm works and why it's widely used.

How SCAN Works:

The SCAN algorithm moves the disk arm towards one end of the disk, servicing all requests along the way, then reverses direction to service requests in the opposite direction. It works like an elevator moving up and down in a building, picking up passengers (I/O requests) along the way.

For example, if the read/write head is at position 50 and needs to service requests at cylinders 25, 70, 10, and 90, the head will first move in one direction (e.g., from 50 to 0), servicing the requests in its path, and then change direction.

Key Features:

1. Bidirectional Movement: SCAN moves in two directions, reducing the wait time for requests at the extreme ends of the disk.
2. Fairness: Each request is guaranteed to be serviced, ensuring no request is left indefinitely unprocessed.
3. Performance: While not as fast as some other algorithms (like Shortest Seek Time First - SSTF), SCAN provides a good balance between performance and fairness.

Advantages of SCAN:

• Predictability: By servicing requests in both directions, SCAN ensures a predictable performance, especially in systems with high I/O loads.
• Reduced Starvation: Unlike SSTF, where requests near the middle may starve those at the ends, SCAN services all requests in a timely manner.

Disadvantages of SCAN:

• Longer Wait Times: Requests just behind the head may have to wait until the head reaches the end of the disk and reverses direction.
• High Seek Time: Compared to more dynamic algorithms like C-SCAN, SCAN can have slightly higher seek times due to the bidirectional movement.

SCAN vs. Other Algorithms:

• FCFS (First-Come, First-Served): SCAN outperforms FCFS by reducing average seek times.
• SSTF (Shortest Seek Time First): SCAN avoids the starvation issue present in SSTF.
• C-SCAN (Circular SCAN): C-SCAN is a variation of SCAN where the head moves only in one direction and, after reaching the end, returns directly to the beginning. This reduces the wait time for requests at the beginning of the disk.

Conclusion:

The SCAN algorithm is a practical choice in systems that require balanced performance and fairness. By mimicking an elevator’s movement, SCAN ensures that no request is left behind while maintaining efficient disk utilization. It’s a great example of how thoughtful scheduling can optimize resource management in operating systems.

Let's break down the key parts of the SCAN disk scheduling algorithm code and understand how each part works:

1. Input and Initialization

int i, j, n, totalTracks, head, direction;
int diskQueue[20], seekSequence[20], distance = 0, temp;

printf("Enter the number of tracks in the request queue: ");
scanf("%d", &n);

printf("Enter the request queue (track numbers): ");
for (i = 0; i < n; i++) {
    scanf("%d", &diskQueue[i]);
}

printf("Enter the initial head position: ");
scanf("%d", &head);

printf("Enter total number of tracks on the disk: ");
scanf("%d", &totalTracks);

printf("Enter the head movement direction (1 for high, 0 for low): ");
scanf("%d", &direction);
        

Explanation:

1.The program first declares variables:

• n: Number of tracks in the request queue.
• diskQueue[]: Array storing the requested track numbers.
• seekSequence[]: Array that will store the order in which tracks will be serviced (the seek sequence).
• head: The initial position of the disk head (the current track it is at).
• totalTracks: The total number of tracks on the disk.
• direction: The direction of disk head movement (1 for increasing track numbers, 0 for decreasing track numbers).
• The program asks for user input to fill these variables and prepares the necessary data for the algorithm.

2. Sorting the Request Queue

// Sorting the request queue
for (i = 0; i < n - 1; i++) {
    for (j = i + 1; j < n; j++) {
        if (diskQueue[i] > diskQueue[j]) {
            temp = diskQueue[i];
            diskQueue[i] = diskQueue[j];
            diskQueue[j] = temp;
        }
    }
}
        

Explanation:

• The algorithm sorts the request queue (diskQueue[]) in ascending order using a simple bubble sort algorithm.
• Sorting is necessary because the SCAN algorithm services requests in one direction and then reverses. Sorting allows the algorithm to easily handle all requests between the current head position and the end of the track range.

3. Finding the Initial Head Position in the Sorted Queue

// Finding the position of the initial head in the sorted queue
int headIndex = 0;
for (i = 0; i < n; i++) {
    if (diskQueue[i] > head) {
        headIndex = i;
        break;
    }
}        

Explanation:

• After sorting, the program finds the position of the first request in diskQueue[] that is greater than the current head position. This is stored in headIndex.
• This index is crucial because it helps determine where to start servicing requests in the selected direction (either high or low).

4. SCAN Scheduling Logic

int k = 0;
if (direction == 1) {
    // Moving towards high track numbers
    for (i = headIndex; i < n; i++) {
        seekSequence[k++] = diskQueue[i];
    }
    seekSequence[k++] = totalTracks; // Adding the end of the disk
    // Moving towards low track numbers
    for (i = headIndex - 1; i >= 0; i--) {
        seekSequence[k++] = diskQueue[i];
    }
} else {
    // Moving towards low track numbers
    for (i = headIndex - 1; i >= 0; i--) {
        seekSequence[k++] = diskQueue[i];
    }
    seekSequence[k++] = 0; // Adding the start of the disk
    // Moving towards high track numbers
    for (i = headIndex; i < n; i++) {
        seekSequence[k++] = diskQueue[i];
    }
}        

Explanation:

• This is the core SCAN logic, where the program services requests based on the direction of head movement.
• If direction == 1 (moving towards higher tracks):

First, the algorithm services all requests from the head to the last request at the highest track number.

Then, it adds the total number of tracks (totalTracks) as a boundary to simulate the disk head reaching the end.

After that, it reverses and services the remaining lower-numbered tracks.

• If direction == 0 (moving towards lower tracks):

The head first services all requests downwards, adds the boundary (track 0), and then moves up to service the remaining high-numbered requests.

The seek sequence is stored in seekSequence[] in the order of the requests being serviced.

5. Calculating the Total Seek Distance

// Calculating total seek distance

distance = abs(head - seekSequence[0]);

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

distance += abs(seekSequence[i] - seekSequence[i - 1]);

}

Explanation:

• The total seek distance is calculated by first finding the distance between the initial head position and the first request in the seek sequence.
• Then, the program sums the distances between each successive request in the seek sequence.
• This gives the total distance that the disk head has moved to service all the requests.

6. Displaying the Result

// Printing the result

printf("Seek sequence: ");

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

printf("%d ", seekSequence[i]);

}

printf("\nTotal seek distance: %d\n", distance);

Explanation:

• The program prints the seek sequence (the order in which the requests are serviced) and the total seek distance (the total distance traveled by the disk head).

Summary:

1. Input: The program gathers information about the request queue, head position, and direction.
2. Sorting: The request queue is sorted to allow for easy sequential servicing of requests.
3. Head Movement: Based on the direction, the program services requests in one direction and then reverses, mimicking elevator-like behavior.
4. Distance Calculation: The total distance traveled by the head is computed to evaluate the efficiency of the SCAN algorithm.