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

Assignment 03: CPU Scheduling Algorithms

I. Objective & Theoretical Framework

This assignment explores the mechanisms by which an operating system manages multiprogramming. You will simulate various CPU scheduling algorithms to determine how processes in the ready queue are allocated CPU time, calculating the turnaround time and waiting time for each.

You will implement the following scheduling policies assuming all processes arrive at the same time:

II. Prerequisite Knowledge & Resources

III. Starter Code & Partial Implementations

The following skeleton demonstrates the logic for calculating Waiting Time and Turnaround Time in an FCFS environment where all processes are assumed to arrive at time 0. Use this as the baseline for constructing the other algorithms.

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

int main(int argc, char *argv[]) {
    if (argc < 2) {
        printf("Usage: %s <burst_time_1> <burst_time_2> ...\n", argv[0]);
        return 1;
    }

    int n = argc - 1;
    int bt[20], wt[20], tat[20];
    float wtavg = 0, tatavg = 0;

    for(int i = 0; i < n; i++) {
        bt[i] = atoi(argv[i+1]); // Convert string arguments to integers
    }

    // FCFS Wait Time and Turnaround Time Logic
    wt[0] = 0;
    tat[0] = bt[0];

    for(i = 1; i < n; i++) {
        wt[i] = wt[i-1] + bt[i-1];
        tat[i] = tat[i-1] + bt[i];
    }

    for(i = 0; i < n; i++) {
        wtavg += wt[i];
        tatavg += tat[i];
    }

    printf("\nAverage Waiting Time: %f", wtavg / n);
    printf("\nAverage Turnaround Time: %f\n", tatavg / n);

    return 0;
}

IV. Step-by-Step Task List

  1. FCFS Implementation: Complete the starter code above to display a formatted table outputting the Process ID, Burst Time, Waiting Time, and Turnaround Time for every process, matching the calculations.

  2. SJF Implementation: Create a new program for SJF. Before calculating wt and tat, implement a sorting algorithm (like Bubble Sort) to arrange the processes in ascending order based on their CPU burst times.

  3. Priority Implementation: Create a new program. Prompt the user for both Burst Time and a Priority value for each process. Sort the queue based on the Priority value before executing the calculations.

  4. Round Robin Implementation: Create a new program. Prompt the user for a time slice (quantum) size. Use a while loop to iteratively deduct the time slice from the burst time of each process in a circular fashion until all burst times reach zero.

V. Common Pitfalls & Debugging Strategies

VI. Real-World Case Study

While foundational, these algorithms are highly applicable to complex computational environments like distributed systems and edge computing. In a network of edge nodes processing latency-sensitive tasks, schedulers must constantly balance workloads. A localized edge server might employ a variation of Shortest Job First to quickly clear lightweight data processing tasks (like sensor telemetry), preventing bottlenecking before sending heavier computational loads to the central cloud infrastructure.

VII. Advanced Variant Tasks

VIII. Resources & Further Reading