Dr. Soumadip Biswas
Computer Science & Engineering | Student | Researcher | Educator

Assignment 09: Disk Scheduling Operations

I. Objective & Theoretical Framework

One of the core responsibilities of an operating system is to utilize hardware efficiently. For magnetic disk drives, meeting this responsibility entails minimizing access time and maximizing disk bandwidth. Both metrics can be significantly improved by managing the execution order of pending disk I/O requests. This process is called disk scheduling.

You will program simulations for three prominent disk scheduling algorithms:

II. Prerequisite Knowledge & Resources

III. Starter Code & Partial Implementations

The following skeleton demonstrates the logic for FCFS disk scheduling. It calculates the header movements required to traverse a given array of track requests.

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

int main() {
    int t[20], n, i, tohm[20], tot = 0;
    float avhm;
    clock_t start, end;
    double cpu_time_used;

    // --- I/O OPERATIONS (OUTSIDE TIMER) ---
    printf("Enter the number of tracks: ");
    scanf("%d", &n);
    
    printf("Enter the tracks to be traversed: ");
    for(i = 1; i <= n; i++) {
        scanf("%d", &t[i]);
    }

    printf("Enter the initial position of the read/write head: ");
    scanf("%d", &t[0]);

    // --- CORE ALGORITHM LOGIC (INSIDE TIMER) ---
    start = clock();

    for(i = 0; i < n; i++) {
        tohm[i] = t[i+1] - t[i];
        if(tohm[i] < 0) {
            tohm[i] = tohm[i] * (-1); // Convert to absolute value
        }
        tot += tohm[i];
    }
    avhm = (float)tot / n;

    end = clock();
    // ------------------------------------------

    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

    // --- OUTPUT OPERATIONS (OUTSIDE TIMER) ---
    printf("\nTracks traversed\tDifference between tracks\n");
    for(i = 0; i < n; i++) {
        printf("%d\t\t\t%d\n", t[i+1], tohm[i]);
    }
    printf("\nAverage header movements: %f\n", avhm);
    printf("Algorithm Execution Time: %f seconds\n", cpu_time_used);

    return 0;
}

IV. Step-by-Step Task List

  1. FCFS Evaluation: Complete and execute the FCFS starter code. Test it with a variety of track sequences to observe how highly erratic requests cause massive seek overhead.

  2. SCAN Implementation: Create a new program. Prompt the user for the number of tracks, the initial head position, and the array of requests.

  • Sort the request array in ascending order.

  • Locate where the initial head position falls within the sorted array.

  • Traverse the array towards the 0 track (or the maximum track, depending on your chosen initial direction), calculating distances, then reverse direction and process the remaining requests.

  1. C-SCAN Implementation: Create a new program for C-SCAN. Prompt the user for the total disk boundaries (e.g., 0 to 199). Implement the logic so that when the head reaches the maximum boundary, it calculates the jump back to 0, but does not service requests during that jump, before continuing its sweep.

V. Common Pitfalls & Debugging Strategies

VI. Real-World Case Study

It is a common misconception that disk scheduling algorithms are obsolete in the era of Solid State Drives (SSDs) because flash memory has no moving read/write head and thus a physical “seek time” of zero. However, operating system I/O schedulers (such as the Linux BFQ or Kyber schedulers) still utilize variants of these elevator algorithms. Instead of optimizing physical arm movement, they optimize for flash page erasure block cycles, grouping logical block addresses together to maximize parallel data channel bandwidth and minimize wear on the NAND flash gates.

VII. Advanced Variant Tasks

VIII. Resources & Further Reading

SDB Watermark