EECS3221: OS Process Scheduler Simulation in C

Safa Bayar included in Systems Programming Academic

2023-11-07 605 words 3 minutes

Contents

EECS3221: OS Process Scheduler Simulation in C

eecs3221 implements classic operating system process scheduling algorithms in C, built as part of the EECS 3221 Operating Systems course. The simulator takes a process workload and outputs scheduling decisions, wait times, and turnaround times for each algorithm.

Scheduling Algorithms Implemented

FCFS — First-Come, First-Served
SJF — Shortest Job First (non-preemptive)
Priority Scheduling — non-preemptive
Round Robin — preemptive with configurable time quantum

Process Representation

typedef struct {
    int pid;
    int arrival_time;
    int burst_time;
    int priority;
    int remaining_time;
    int start_time;
    int finish_time;
    int waiting_time;
    int turnaround_time;
} Process;

FCFS Scheduler

void schedule_fcfs(Process *procs, int n) {
    // Sort by arrival time
    qsort(procs, n, sizeof(Process), cmp_arrival);

    int current_time = 0;
    for (int i = 0; i < n; i++) {
        if (current_time < procs[i].arrival_time)
            current_time = procs[i].arrival_time;

        procs[i].start_time    = current_time;
        procs[i].finish_time   = current_time + procs[i].burst_time;
        procs[i].waiting_time  = procs[i].start_time - procs[i].arrival_time;
        procs[i].turnaround_time = procs[i].finish_time - procs[i].arrival_time;

        current_time = procs[i].finish_time;
    }
}

Shortest Job First (Non-Preemptive)

void schedule_sjf(Process *procs, int n) {
    int completed = 0, current_time = 0;
    int done[MAX_PROCS] = {0};

    while (completed < n) {
        int shortest = -1;
        for (int i = 0; i < n; i++) {
            if (!done[i] && procs[i].arrival_time <= current_time) {
                if (shortest == -1 ||
                    procs[i].burst_time < procs[shortest].burst_time)
                    shortest = i;
            }
        }

        if (shortest == -1) {
            current_time++;
            continue;
        }

        Process *p = &procs[shortest];
        p->start_time      = current_time;
        p->finish_time     = current_time + p->burst_time;
        p->waiting_time    = p->start_time - p->arrival_time;
        p->turnaround_time = p->finish_time - p->arrival_time;

        current_time = p->finish_time;
        done[shortest] = 1;
        completed++;
    }
}

Round Robin

void schedule_rr(Process *procs, int n, int quantum) {
    int queue[MAX_PROCS * 100], head = 0, tail = 0;
    int current_time = 0, completed = 0;

    for (int i = 0; i < n; i++)
        procs[i].remaining_time = procs[i].burst_time;

    // Enqueue processes that arrive at time 0
    for (int i = 0; i < n; i++)
        if (procs[i].arrival_time == 0)
            queue[tail++] = i;

    while (completed < n) {
        if (head == tail) {
            current_time++;
            for (int i = 0; i < n; i++)
                if (procs[i].arrival_time == current_time)
                    queue[tail++] = i;
            continue;
        }

        int idx = queue[head++];
        Process *p = &procs[idx];

        if (p->start_time == -1)
            p->start_time = current_time;

        int run = (p->remaining_time < quantum) ? p->remaining_time : quantum;
        current_time += run;
        p->remaining_time -= run;

        // Enqueue newly arrived processes
        for (int i = 0; i < n; i++)
            if (procs[i].arrival_time > current_time - run &&
                procs[i].arrival_time <= current_time &&
                procs[i].remaining_time > 0 && i != idx)
                queue[tail++] = i;

        if (p->remaining_time == 0) {
            p->finish_time     = current_time;
            p->turnaround_time = p->finish_time - p->arrival_time;
            p->waiting_time    = p->turnaround_time - p->burst_time;
            completed++;
        } else {
            queue[tail++] = idx;
        }
    }
}

Statistics Output

void print_stats(Process *procs, int n, const char *algo) {
    float avg_wait = 0, avg_turnaround = 0;

    printf("\n=== %s ===\n", algo);
    printf("%-6s %-8s %-8s %-8s %-12s %-12s\n",
           "PID", "Arrival", "Burst", "Start", "Waiting", "Turnaround");

    for (int i = 0; i < n; i++) {
        printf("%-6d %-8d %-8d %-8d %-12d %-12d\n",
               procs[i].pid,
               procs[i].arrival_time,
               procs[i].burst_time,
               procs[i].start_time,
               procs[i].waiting_time,
               procs[i].turnaround_time);
        avg_wait       += procs[i].waiting_time;
        avg_turnaround += procs[i].turnaround_time;
    }

    printf("\nAverage Waiting Time:    %.2f\n", avg_wait / n);
    printf("Average Turnaround Time: %.2f\n", avg_turnaround / n);
}

Sample Output

=== Round Robin (Q=3) ===
PID    Arrival  Burst    Start    Waiting      Turnaround
1      0        10       0        12           22
2      1        4        3        2            6
3      2        5        7        5            10

Average Waiting Time:    6.33
Average Turnaround Time: 12.67

Key Learnings

FCFS minimizes implementation complexity but suffers from the convoy effect
SJF minimizes average waiting time but requires burst time knowledge upfront
Round Robin provides fairness at the cost of higher context-switch overhead for small quanta
Priority Scheduling can cause starvation without aging mechanisms

Source: GitHub