Priority Scheduling Algorithm Preemptive

Question

After implementing suggestions from my previous question and after modifying I have written this code. Function sortAccordingArrivalTime() sorts arrivalTime burstTime and priority according to arrival time. I have tried to enter Arrival Time, Burst Time and Priority in respective order for each process at a time. Help me to improve this code and optimize it with more use of C++11 and C++14.

scheduling.h

#ifndef SCHEDULING_H_
#define SCHEDULING_H_

#include <vector>

using uint = unsigned int;

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

    std::vector<uint> arrivalTime;
    //When process start to execute
    std::vector<uint> burstTime;
    //process wait to execute after they have arrived
    std::vector<uint> waitingTime;
    //total time taken by processes
    std::vector<uint> turnArountTime;

  public:
    Scheduling(uint 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 printInfo();

  private:
    void sortAccordingArrivalTime();
};

#endif

priority.cpp

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

using uint = unsigned int;

std::vector<uint> priority;

Scheduling::Scheduling(uint n): waitingTime(n, 0)
{
      arrivalTime.reserve(n);
      burstTime.reserve(n);
      waitingTime.reserve(n);
      turnArountTime.reserve(n);
      priority.reserve(n);
      std::cout << "Enter Arrival Time, Burst Time, Priority in respective ";
      std::cout << "order (eg 2 15 4)\n";
      std::cout << "Lower integer has higher priority";

    for (uint i = 0; i < n; i++)
    {
        uint arrivalVal, burstVal, priorityVal;
        std::cout << "\nProcess " << i+1 << ": ";
        std::cin >> arrivalVal >> burstVal >> priorityVal;
        arrivalTime.push_back(arrivalVal);
        burstTime.push_back(burstVal);
        priority.push_back(priorityVal);
    }
}

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])
            {
                uint temp = arrivalTime[i];
                arrivalTime[i] = arrivalTime[j];
                arrivalTime[j] = temp;

                temp = burstTime[i];
                burstTime[i] = burstTime[j];
                burstTime[j] = temp;

                temp = priority[i];
                priority[i] = priority[j];
                priority[j] = temp;
            }
        }
    }
}

void Scheduling::calcWaitingTime()
{
    std::vector<uint> burstTimeCopy;
    std::copy(burstTime.begin(), burstTime.end(),
              std::back_inserter(burstTimeCopy));

    //If entered arrival time are not sorted
    if (! (std::is_sorted(arrivalTime.begin(), arrivalTime.end())) )
    {
        sortAccordingArrivalTime();
    }

    while (!(std::all_of(burstTimeCopy.begin(),
             burstTimeCopy.end(), [] (uint e) { return e == 0; })))
    {
        auto maxArrivalTime = std::max_element(arrivalTime.begin(),
                                               arrivalTime.end());
        if (timeCounter <= *maxArrivalTime)
        {
            uint maxPriority = std::numeric_limits<uint>::max();
            for (std::size_t i = 0; i < burstTimeCopy.size(); i++)
            {
                if (burstTimeCopy[i] != 0 && priority[i] < maxPriority
                     && arrivalTime[i] <= timeCounter)
                {
                    maxPriority = priority[i];
                    currActiveProcessID = i;
                }
            }

            burstTimeCopy[currActiveProcessID] -= 1;

            for (std::size_t i = 0; i < burstTimeCopy.size(); i++)
            {
                if (timeCounter >= arrivalTime[i] && i != currActiveProcessID
                      && burstTimeCopy[i] != 0)
                {
                    waitingTime[i] += 1;
                }
            }
            timeCounter++;
        }
        else
        {
            uint maxPriority = std::numeric_limits<uint>::max();
            for (std::size_t i = 0 ; i < burstTimeCopy.size(); i++)
            {
                if (burstTimeCopy[i] != 0 && priority[i] < maxPriority)
                {
                    maxPriority = priority[i];
                    currActiveProcessID = i;
                }
            }
            for (std::size_t i = 0; i < burstTimeCopy.size(); i++)
            {
                if (i != currActiveProcessID && burstTimeCopy[i] != 0)
                {
                    waitingTime[i] += burstTimeCopy[currActiveProcessID];
                }
            }
            timeCounter += burstTimeCopy[currActiveProcessID];
            burstTimeCopy[currActiveProcessID] = 0;
        }
    }
    uint sum = 0;
    for (auto element: waitingTime)
    {
        sum += element;
    }
    avgWaitingTime = sum / waitingTime.size();
}

void Scheduling::calcTurnAroundTime()
{
    uint sum = 0;
    for (std::size_t i = 0; i < arrivalTime.size(); i++)
    {
        uint val = burstTime[i] + waitingTime[i];
        turnArountTime.push_back(val);
        sum += val;
    }
    avgTurnAroundTime = sum / turnArountTime.size();
}

void Scheduling::printInfo()
{
    std::cout << "ProcessID\tArrival Time\tBurst Time\tPriority\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" << priority[i] << "\t\t" << waitingTime[i];
        std::cout << "\t\t" << turnArountTime[i] << '\n';
    }
    std::cout << "Average Waiting Time : " << avgWaitingTime << '\n';
    std::cout << "Average Turn Around Time : " << avgTurnAroundTime << '\n';
}

int main()
{
    int num;
    std::cout << "Enter the number of processes\n";
    std::cin >> num;
    Scheduling prioritySchedule(num);
    prioritySchedule.calcWaitingTime();
    prioritySchedule.calcTurnAroundTime();
    prioritySchedule.printInfo();
}

Answer 1

I see a number of improvements you could make to your code.

Rethink your classes

There are a number of parallel vectors that each hold one element of a task. I'd highly recommend instead creating a Task class and then creating a std::vector<Task> to hold them. Many of the things you're doing would be much easier to read and understand that way.

Eliminate global variables where practical

Having routines dependent on global variables makes it that much more difficult to understand the logic and introduces many opportunities for error. In this case, priority should really be part of the Task class I mentioned above.

Separate I/O from construction

First we have main asking for some data, and then the constructor for Scheduler asks for still more. This is probably not a good design. What I'd suggest instead would be to create a friend std::istream operator>> and read in the data that way. If you write a corresponding operator<<, you could use that instead of your printInfo() method.

Encapsulate or eliminate type aliases

Right now, the program has this line:

using uint = unsigned int;

Try not to pollute the global namespace with either typedef or using, especially with such a commonly defined name as uint. You could either wrap the declaration in a namespace or just use unsigned instead which is only slightly longer and would make the code easier to read by using standard names instead of redefined ones.

Make sure constructors create coherent objects

The currActiveProcessID data member of your class is not initialized within the constructor. It's much better to initialize at least enough of the member variables in a class to make the class consistent, coherent and usable when the constructor has completed.

Fix the bug

Right now, the program will crash unless one of the tasks has an arrival time of 0. That's a bug that should be fixed and it has to do with the previous suggestion.

Don't test; just sort

The code currently contains these lines:

//If entered arrival time are not sorted
if (! (std::is_sorted(arrivalTime.begin(), arrivalTime.end())) )
{
    sortAccordingArrivalTime();
}

I would bet that there's no performance gain by checking first and then sorting, and there's definitely a human reader comprehension gain if you replace that with just this:

sortAccordingArrivalTime();

Any efficiency gain you might lose will easily be recovered by the next suggestion.

Use a standard sort

The sortAccordingArrivalTime function is not pretty. If you were to use a std::vector of Task objects instead of several parallel vectors, as suggested earlier, the entire routine can be replaced with this:

std::sort(task.begin(), task.end(), [](const Task &a, const Task &b){
        return a.arrivalTime < b.arrivalTime;
});

Or using a named lambda:

static const auto byArrival = [](const Task &a, const Task &b){
        return a.arrivalTime < b.arrivalTime;
};
std::sort(task.begin(), task.end(), byArrival);

Isn't that nicer?

Fix the spelling

I am thinking that turnArountTime should be turnAroundTime. It doesn't make any difference to the compiler, of course, but human readers will appreciate correct spelling.

Use a better algorithm

The current algorithm is not very efficient since it increments the clock by one tick for much of the duration of the program, even if there's nothing really happening. We can do better. The goal of a pre-emptive scheduler is to always run the highest priority task until either completion or until a higher priority task arrives. For this program, since it knows all of the tasks and their arrival times, priorities and execution durations before beginning processing, we can use a std::priority_queue to keep track of the highest priority item at any time. Also, once a task is running, we know how long it will run: it runs either to completion or at least until the next task arrives. Since both values are known, we can advance the time by the appropriate amount and skip over the periods in which nothing is really happening.

Calculate values only when needed

If we think carefully about the per-task values, it doesn't take too long to work out that the turnAroundTime is always the difference between the task end time and the task arrival time. In other words, turnAroundTime = endTime - arrivalTime. It's also clear that waitingTime = turnAroundTime - burstTime. By calculating each value only once when the task is complete, not only is the processing efficient, but it can also be delegated to a Task object, simplifying the rest of the code. Note also that these calculations are invariant among scheduling algorithms, so if you decide, for example, to experiment with other scheduling schemes, these calculations could remain unchanged.

Understand automatic mathematical conversions

The avgWaitingTime and avgTurnAroundTime variables are both double. However, the way the calculations are done will only give integer results. To understand why, let's look at one of the calculations:

void Scheduling::calcTurnAroundTime()
{
    uint sum = 0;
    for (std::size_t i = 0; i < arrivalTime.size(); i++)
    {
        uint val = burstTime[i] + waitingTime[i];
        turnArountTime.push_back(val);
        sum += val;
    }
    avgTurnAroundTime = sum / turnArountTime.size();
}

If we look closely at that last line, we are dividing a uint (which is an alias for unsigned int) by a std::size_t which is another unsigned integral value. This means we're dividing an integer by another integer and only then are we assigning the value to a double. The result of dividing an integer by another integer in C++ is an integer, so we're not getting a double's worth of precision. Here's how I'd rewrite that function:

double meanTurnAroundTime() const {
    return std::accumulate(task.begin(), task.end(), 0.0, 
        [](double a, const Task& t){
            return a + t.turnAroundTime;
        }) / task.size();
}

This uses std::accumulate and assumes that task is an iterable collection of Task objects, each of which has a turnAroundTime element accessible to this code. Because the starting values for std::accumulate in this usage is specified as 0.0 (which is a double), the result will be a double and the division will be performed in full floating point.

Answer 2

A few things I noticed:

the standard library includes a swap function I would suggest using it or at least put the swap algorithm in its own function.

Instead of synchronized collections, it would simplify and increase maintainability to have an embedded class to hold the times. This way you have one collection and the times are automatically synchronized. Implementing the standard comparison operators(<,==,>) allows you to simplify the sorting:

#include <vector>

using uint = unsigned int;
using std::vector;
class Scheduler
{
    class ProcessTimes
    {
        uint arrivalTime = 0;
        uint burstTime = 0;
        uint waitingtime = 0;
        uint turnAroundTime = 0;
        uint priority = 0;
    public:
        ProcessTimes();
        ProcessTimes(uint arrival, uint burst, uint waiting, uint turnAround, uint priority) :
            arrivalTime(arrival),
            burstTime(burst),
            waitingtime(waiting),
            turnAroundTime(turnAround),
            priority(priority)
        {}
        ~ProcessTimes();
        bool operator ==(ProcessTimes& other) { return arrivalTime == other.arrivalTime; }
        bool operator <(ProcessTimes& other) { return arrivalTime < other.arrivalTime; }
        bool operator >(ProcessTimes& other) { return arrivalTime > other.arrivalTime; }
        int compareTo(ProcessTimes& other) { return arrivalTime < other.arrivalTime ? -1 
                                            : arrivalTime > other.arrivalTime ? 1 :0; }
    };
    vector<ProcessTimes> times;
};

Once you have this done, I would suggest looking into a min Heap Priority Queue.