Round Robin Scheduler

CPU scheduling simulation implementing time-sliced process scheduling in C.

Jul 20, 20255 min read

SystemsProcessesTutorial

Let’s start by defining a process. A process is simply something in execution. A process can be an executable binary, an app, or even this blog site. It’s an illusion provided by the OS to the program that it owns the entire computer space. We’ll keep track of its process ID (PID), burst time (the total time a process needs to execute on the CPU), remaining time, and completion time. Below is a sample definition of a process:

#ifndef _PROCESS_H_
#define _PROCESS_H_

typedef struct {
    int pid;
    int burst_time;
    int remaining_time;
    int completion_time;
} Process;

#endif

Save it as a file like process.h.

A round-robin scheduler works by giving each process a fixed amount of time to run. This fixed time snippet is called a time quantum. Each process runs for that entire duration (unless the process ends early).

This ensures fair scheduling. However, if the time quantum is too small, we may spend more time context switching than actually performing tasks (this is called thrashing). Additional drawbacks include: time quantum being too large (making the system feel unresponsive) and lack of prioritization (critical tasks might need to execute faster).

Let’s use our process definition to define a few processes.

Process processes[] = {
    {1, 10, 10, 0},
    {2, 5, 5, 0},
    {3, 8, 8, 0}
};

Let’s also define the number of processes we have by taking the size of the entire processes array and dividing it by the size of a single process.

int num_processes = sizeof(processes) / sizeof(processes[0]);

We’re now ready to write our round-robin scheduler! Remember, the main idea is to keep giving processes a certain amount of time to run until each process is finished.

int time_quantum = 3;

void round_robin(Process processes[], int num_processes, int time_quantum) {
    int n = num_processes;
    int i = 0;
    int time = 0;

    while (num_processes > 0) {
        // TO-DO

        i = (i + 1) % n;
    }
}

We now have a simple function blueprint. We pass in the processes, the number of them, and the time quantum. We want to keep track of the number of processes in a separate variable, since we’ll be decreasing the num_processes parameter later on. We iterate by incrementing i and wrapping it around if it goes out of bounds (using the modulo operator with the number of processes). Let’s continue (promise we’re almost done)!

int time_quantum = 3;

void round_robin(Process processes[], int num_processes, int time_quantum) {
    int n = num_processes;
    int i = 0;
    int time = 0;

    while (num_processes > 0) {
        int exec_time = (processes[i].remaining_time > time_quantum) ? time_quantum : processes[i].remaining_time;

        printf("Time %d: Process %d runs for %d units\n", time, processes[i].pid, exec_time);

        time += exec_time;

        processes[i].remaining_time -= exec_time;

        // TO-DO

        i = (i + 1) % n;
    }
}

Whew! That was a lot… let’s go through it: we declare a variable execution_time, which basically says: if there’s more remaining time than the time quantum, then run it for the quantum; else, just finish the process. We then increment time based on execution_time and decrease the process’s remaining time. Final stretch:

int time_quantum = 3;

void round_robin(Process processes[], int num_processes, int time_quantum) {
    int n = num_processes;
    int i = 0;
    int time = 0;

    while (num_processes > 0) {
        int exec_time = (processes[i].remaining_time > time_quantum) ? time_quantum : processes[i].remaining_time;

        printf("Time %d: Process %d runs for %d units\n", time, processes[i].pid, exec_time);

        time += exec_time;

        processes[i].remaining_time -= exec_time;

        if (processes[i].remaining_time == 0) {
            processes[i].completion_time = time;
            num_processes -= 1;
        }
        i = (i + 1) % n;
    }

    printf("\nCompletion Times:\n");
    for (int j = 0; j < n; j++) {
        printf("Process %d completed at %d units\n", processes[j].pid, processes[j].completion_time);
    }
}

And that’s it! We simply check whether there’s any remaining time left for that process. If it’s done, we set its completion time to time and decrease the number of processes left. We then go through all our processes and print out their completion times.

Now we just need to put it all together:

#include <stdio.h>
#include "process.h"

// pid, burst_time, remaining_time, completion_time
Process processes[] = {
    {1, 10, 10, 0},
    {2, 5, 5, 0},
    {3, 8, 8, 0}
};

int num_processes = sizeof(processes) / sizeof(processes[0]);

int time_quantum = 3;

void round_robin(Process processes[], int num_processes, int time_quantum) {
    int n = num_processes;
    int i = 0;
    int time = 0;

    while (num_processes > 0) {
        if (processes[i].remaining_time > 0) {
            int exec_time = (processes[i].remaining_time > time_quantum) ? time_quantum : processes[i].remaining_time;

            printf("Time %d: Process %d runs for %d units\n", time, processes[i].pid, exec_time);
            time += exec_time;

            processes[i].remaining_time -= exec_time;

            if (processes[i].remaining_time == 0) {
                processes[i].completion_time = time;
                num_processes -= 1;
            }
        }
        i = (i + 1) % n;
    }

    printf("\nCompletion Times:\n");
    for (int j = 0; j < n; j++) {
        printf("Process %d completed at %d units\n", processes[j].pid, processes[j].completion_time);
    }
}

int main() {
    round_robin(processes, num_processes, time_quantum);
    return 0;
}

Save it as a file like round_robin.c.

Hope you enjoyed implementing a super simple simulation of a round-robin (RR) scheduler.

Thanks for reading! Found this useful? Share it or reach out with thoughts.