Round Robin Scheduling Algorithm

Question

Here I have implemented code for Round Robin CPU Scheduling Algorithm. scheduling.h header file is also used in Shortest Job First Scheduling Algorithm and Priority Scheduling Algorithm, so it contains common data members and member functions.

First I have calculated end time in calcEndTime() then using formula turnAroundTime = endTime - arrivalTime calculated Turnaround time and using waitingTime = turnAroundTime - burstTime calculated Waiting time.

Please help me to improve and optimize this code using more C++11 and C++14 features.

scheduling.h

#ifndef SCHEDULING_H_
#define SCHEDULING_H_

#include <vector>

class Scheduling
{
    uint currActiveProcessID;
    uint timeCounter = 0;
    double avgWaitingTime;
    double avgTurnAroundTime;

    std::vector<unsigned> arrivalTime;
    //When process start to execute
    std::vector<unsigned> burstTime;
    //process wait to execute after they have arrived
    std::vector<unsigned> waitingTime;
    //total time taken by processes
    std::vector<unsigned> turnAroundTime;
    //time when a process end
    std::vector<unsigned> endTime;

  public:
    Scheduling(unsigned num = 0);
    Scheduling(const Scheduling&)            = delete;
    Scheduling &operator=(const Scheduling&) = delete;
    Scheduling(Scheduling&&)                 = delete;
    Scheduling &operator=(Scheduling&&)      = delete;
    ~Scheduling()                            = default;

    void calcWaitingTime();
    void calcTurnAroundTime();
    void calcEndTime();
    void printInfo();

  private:
    void sortAccordingArrivalTime();
};

#endif

roundrobin.cpp

#include <iostream>
#include <vector>
#include <algorithm> // std::find
#include <iterator> // std::begin, std::end
#include <limits> //std::numeric_limits
#include "scheduling.h"

unsigned timeQuantum = 0;

Scheduling::Scheduling(unsigned num)
{
    unsigned arrivalVal, burstVal;
    currActiveProcessID = 0;
    timeCounter = 0;
    std::cout << "\nEnter time quantum : ";
    std::cin >> timeQuantum;
    arrivalTime.reserve(num);
    burstTime.reserve(num);
    endTime.reserve(num);

    std::cout << "\nEnter arrival time and burst time eg(5 18)\n";
    for (unsigned i = 0; i < num; i++)
    {
        std::cout << "\nProcess" << i+1 << ": ";
        std::cin >> arrivalVal >> burstVal;
        arrivalTime.push_back(arrivalVal);
        burstTime.push_back(burstVal);
    }
}

void Scheduling::sortAccordingArrivalTime()
{
    for (std::size_t i = 0; i < arrivalTime.size(); i++)
    {
        for (std::size_t j = i+1; j < arrivalTime.size(); j++)
        {
            if (arrivalTime[i] > arrivalTime[j])
            {
                std::swap(arrivalTime[i], arrivalTime[j]);
                std::swap(burstTime[i], burstTime[j]);
            }
        }
    }
}

void Scheduling::calcEndTime()
{
    //If arrival time is not sorted
    //sort burst time according to arrival time
    sortAccordingArrivalTime();

    //copy values of burst time in new vector
    std::vector<unsigned> burstTimeCopy;
    std::copy(burstTime.begin(), burstTime.end(),
              std::back_inserter(burstTimeCopy));

    while (!(std::all_of(burstTimeCopy.begin(), burstTimeCopy.end(),
            [] (unsigned e) { return e == 0; })))
    {
        currActiveProcessID = 0;
        auto it = burstTimeCopy.begin();
        while (it != burstTimeCopy.end())
        {
            if (burstTimeCopy[currActiveProcessID] > timeQuantum)
            {
                burstTimeCopy[currActiveProcessID] -= timeQuantum;
                timeCounter += timeQuantum;
            }
            else if (burstTimeCopy[currActiveProcessID] > 0)
            {
                timeCounter += burstTimeCopy[currActiveProcessID];
                burstTimeCopy[currActiveProcessID] = 0;
                endTime[currActiveProcessID] = timeCounter;
            }
            currActiveProcessID++;
            it++;
        }
    }
}

void Scheduling::calcTurnAroundTime()
{
    double sum = 0.00;
    for (std::size_t i = 0; i < arrivalTime.size(); i++)
    {
        unsigned val = endTime[i] - arrivalTime[i];
        turnAroundTime.push_back(val);
        sum += (double)val;
    }
    avgTurnAroundTime = sum / turnAroundTime.size();
}

void Scheduling::calcWaitingTime()
{
    double sum = 0.00;
    for (std::size_t i = 0; i < burstTime.size(); i++)
    {
        unsigned val = turnAroundTime[i] - burstTime[i];
        waitingTime.push_back(val);
        sum += (double)val;
    }
    avgWaitingTime = sum / waitingTime.size();
}

void Scheduling::printInfo()
{
    std::cout << "ProcessID\tArrival Time\tBurst Time\tEnd Time\tWaiting Time";
    std::cout << "\tTurnaround Time\n";
    for (std::size_t i = 0; i < arrivalTime.size(); i++)
    {
        std::cout << i+1 << "\t\t" << arrivalTime[i] << "\t\t" << burstTime[i];
        std::cout << "\t\t"<<endTime[i] << "\t\t" << waitingTime[i] <<"\t\t";
        std::cout << turnAroundTime[i] <<'\n';
    }
    std::cout << "Average Waiting Time : " << avgWaitingTime << '\n';
    std::cout << "Average Turn Around Time : " << avgTurnAroundTime << '\n';
}


int main()
{
    int num;
    std::cout << "Enter number of process: ";
    std::cin >> num;
    Scheduling roundRobin(num);
    roundRobin.calcEndTime();
    roundRobin.calcTurnAroundTime();
    roundRobin.calcWaitingTime();
    roundRobin.printInfo();
}

Answer 1

Where does the uint type come from?

The currActiveProcessID member of Scheduling can be removed from the class, as it is only used internally to calcEndTime().

timeQuantum should be entered in main (or a helper function) or passed in on the command line, not as part of the class constructor. Then pass it into the class as a parameter to the constructor, and store it within the class.

All of your accesses to endTime result in Undefined Behavior. You reserve() some space in the vector, but never actually resize the vector. This leaves the vector with a size() of 0.

If you use a struct to hold your various time vectors, then your sort can easily be a simple call to std::sort (which will be faster than the sort you wrote). Changing from a struct-of-vectors to a vector-of-structs approach would also simplify other parts of your code (calcTurnAroundTime, calcWaitingTime), since you wouldn't need to index into multiple arrays. Just user iterators. If you leave them as separate vectors, you copy of burstTime can be auto burstTimeCopy = burstTime; without using std::copy (although burstTimeCopy can be eliminated; see below).

The while loop in calcEndTime has an iterator into burstTimeCopy, so you don't need to use burstTimeCopy[currActiveProcessID]; just use *it. Also, you should use ++it to increment the iterator, which avoids creating an unused copy of the iterator (which may or may not be optimized out).

However the while loop can be rewritten to not need burstTimeCopy at all. Keep track of the total elapsed time and use that, rather than reducing all your times towards zero.

printInfo can be a const member function.

Answer 2

You seem to be using the same definition of the Scheduling class, which is declared in Scheduling.h, and defining it multiple times in different files. Here, you define it in roundrobin.cpp, but in this question, you define it in a completely different .cpp file. This is a very odd way to be organizing your code.

Here is how I would do it instead:

1. Scheduling is a strange name for an object. It should be a concrete noun like Scheduler. Your Scheduler class should be declared in a header file, Scheduler.hpp, and then defined in a separate file of the same name, Scheduler.cpp.

2. If you're implementing multiple schedulers that use the same interface, then these schedulers should inherit from a common base class. As such, you should make Scheduler an abstract base class and then have other schedulers inherit from them. They would have names like RoundRobinScheduler, for example. RoundRobinScheduler would be declared in a header file RoundRobinScheduler.hpp and then defined in a separate file, RoundRobinScheduler.cpp.

This more closely follows conventions and allows someone to be able to use more than one of your schedulers at the same time. It will also give you experience in designing derived classes that share a common interface, which is a necessary skill to have when doing object-oriented programming.