Implement the Round Robin Scheduling Algorithm

Introduction

In this lab, we will learn how to implement the Round Robin Scheduling Algorithm in C++. Round Robin Scheduling algorithm is a preemptive algorithm in which a process is executed for a fixed time slice known as a time quantum. If the process completes its execution within the time quantum, it gets terminated, otherwise, it is shifted to the end of the ready queue.

Create a new C++ file

First, create a new C++ file in the ~/project directory. You can name it round_robin.cpp.

$ cd ~/project
$ touch round_robin.cpp

Include necessary libraries

Include the necessary libraries in the round_robin.cpp file.

#include <iostream>
using namespace std;

Define the main() function

Define the main() function and initialize the process IDs, burst times, the quantum, and the number of processes.

int main()
{
    // Process IDs
    int processes[] = { 1, 2, 3, 4 };

    // Burst time of all processes
    int burst_time[] = { 5, 9, 6, 8 };

    // Time quantum
    int quantum = 2;

    // Number of processes
    int n = sizeof processes / sizeof processes[0];

    return 0;
}

Implement the function to find waiting time

The function findWaitingTime() is used to find the waiting time for all processes. This function is defined to iterate over the processes in round-robin manner.

void findWaitingTime(int processes[], int n, int bt[], int wt[], int quantum)
{
    // Make a copy of burst times bt[] to store remaining
    // burst times.
    int rem_bt[n];
    for (int i = 0; i < n; i++)
        rem_bt[i] = bt[i];

    int t = 0; // Current time

    // Keep traversing processes in round-robin manner
    // until all of them are not done.
    while (1) {
        bool done = true;

        // Traverse all processes one by one repeatedly
        for (int i = 0; i < n; i++) {
            // If burst time of a process is greater than 0
            // then only need to process further
            if (rem_bt[i] > 0) {
                done = false; // There is a pending process

                /* If remaining burst time is greater than
                quantum then decrease the time slice
                from remaining burst time */
                if (rem_bt[i] > quantum) {
                    // Increase the value of t i.e. shows
                    // how much time a process has been processed
                    t += quantum;

                    // Decrease the burst_time of current process
                    // by quantum
                    rem_bt[i] -= quantum;
                }
                /* If remaining burst time is smaller than
                or equal to quantum then the remaining
                burst time for this process is 0.*/
                else {
                    // Increase the value of t i.e. shows
                    // how much time a process has been processed
                    t += rem_bt[i];

                    // Waiting time is current time minus time
                    // used by this process
                    wt[i] = t - bt[i];

                    // As the process gets fully executed
                    // make its remaining burst time = 0
                    rem_bt[i] = 0;
                }
            }
        }

        // If all processes are done
        if (done == true)
            break;
    }
}

Implement the function to find turn around time

The function findTurnAroundTime() is used to find the turn around time for all processes.

void findTurnAroundTime(int processes[], int n,
                         int bt[], int wt[], int tat[])
{
    // calculating turnaround time by adding
    // bt[i] + wt[i]
    for (int i = 0; i < n; i++)
        tat[i] = bt[i] + wt[i];
}

Implement the function to calculate average time

The function findavgTime() is used to calculate the average waiting time and average turn around time for all the processes.

void findavgTime(int processes[], int n, int bt[],
                                                 int quantum)
{
    int wt[n], tat[n], total_wt = 0, total_tat = 0;

    // Function to find waiting time of all processes
    findWaitingTime(processes, n, bt, wt, quantum);

    // Function to find turn around time for all processes
    findTurnAroundTime(processes, n, bt, wt, tat);

    // Display processes along with all details
    cout << "Processes "
         << " Burst time "
         << " Waiting time "
         << " Turn around time\n";

    // Calculate total waiting time and total turn
    // around time
    for (int i = 0; i < n; i++) {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        cout << " " << i + 1 << "\t\t" << bt[i] << "\t "
             << wt[i] << "\t\t " << tat[i] << endl;
    }

    cout << "Average waiting time = "
         << (float)total_wt / (float)n;
    cout << "\nAverage turn around time = "
         << (float)total_tat / (float)n;
}

Call the findavgTime() function

Call the findavgTime() function to calculate the average waiting time and average turn around time for the processes.

int main()
{
    int processes[] = { 1, 2, 3, 4 };

    // Burst time of all processes
    int burst_time[] = { 5, 9, 6, 8 };

    // Time quantum
    int quantum = 2;

    // Number of processes
    int n = sizeof processes / sizeof processes[0];

    // Function to find average time
    findavgTime(processes, n, burst_time, quantum);

    return 0;
}

To run the code in a terminal, execute the following command from the ~/project directory.

$ g++ round_robin.cpp -o round_robin && ./round_robin

Summary

In this lab, we learned how to implement the Round Robin Scheduling Algorithm in C++. The algorithm is used to schedule processes in an operating system for a time slice known as a time quantum. We have also seen how to calculate the average waiting time and average turn around time for a set of processes.