# Shortest Job First Preemptive

I will write code for all scheduling algorithm in future that is why scheduling.h will contain common data members and member functions. Please help me to improve and optimise this code.

scheduling.h

#ifndef SCHEDULING_H_
#define SCHEDULING_H_

#include <vector>

typedef unsigned int uint;

class Scheduling
{
uint currActiveProcessID;
uint timeCounter = 0;

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;

public:
Scheduling(uint);
Scheduling()                             = default;
Scheduling(const Scheduling&)            = delete;
Scheduling &operator=(const Scheduling&) = delete;
Scheduling(Scheduling&&)                 = delete;
Scheduling &operator=(Scheduling&&)      = delete;
~Scheduling()                            = default;

void calcWaitingTime();
void printInfo();
};

#endif


sjf_preemptive.cpp

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

typedef unsigned int uint;

Scheduling::Scheduling(uint n)
{
for ( int i = 0; i < n; i++)
{
arrivalTime.reserve(n);
burstTime.reserve(n);
waitingTime.reserve(n);

uint val;
std::cout << "Enter arrival time for process " << i+1 << "\n";
std::cin >> val;
arrivalTime.push_back(val);

std::cout << "Enter burst time for process " << i+1 << "\n";
std::cin >> val;
burstTime.push_back(val);

waitingTime.push_back(0);
}
}

bool isAllZeroes(std::vector<uint>& burstTimeCopy)
{
for (int i = 0; i < burstTimeCopy.size(); i++)
{
if (burstTimeCopy[i] != 0)
{
return false;
}
else
{
return true;
}
}
}

void Scheduling::calcWaitingTime()
{
std::vector<uint> burstTimeCopy;
burstTimeCopy.reserve(burstTime.size());
uint index = 0;
std::vector<uint>::iterator it;
while (isAllZeroes(burstTimeCopy) == false)
{
auto max = std::max_element(arrivalTime.begin(), arrivalTime.end());
if (timeCounter <= *max)
{
it = arrivalTime.end();
it = std::find(arrivalTime.begin(), arrivalTime.end(), timeCounter);
if (it != arrivalTime.end())
{
index = std::distance(arrivalTime.begin(), it);
}

if (burstTimeCopy.empty() == true || index != currActiveProcessID)
{
burstTimeCopy.push_back(burstTime[index]);
}

uint minBurstTime = std::numeric_limits<uint>::max();
//Find index with minimum burst Time remaining
for (int i = 0; i < burstTimeCopy.size(); i++)
{
if (burstTimeCopy[i] != 0 && burstTimeCopy[i] < minBurstTime)
{
minBurstTime = burstTimeCopy[i];
index = i;
}
}
currActiveProcessID = index;
burstTimeCopy[currActiveProcessID] -= 1;

for (int i = 0; i < arrivalTime.size(); i++)
{
if (timeCounter >= arrivalTime[i] && i != currActiveProcessID
&& burstTimeCopy[i] != 0)
{
waitingTime[i] += 1;
}
}
timeCounter++;
}
else
{
uint minBurstTime = std::numeric_limits<uint>::max();
//Find index with minimum burst Time remaining
for (int i = 0; i < burstTimeCopy.size(); i++)
{
if (burstTimeCopy[i] != 0 && burstTimeCopy[i] < minBurstTime)
{
minBurstTime = burstTimeCopy[i];
index = i;
}
}
currActiveProcessID = index;
burstTimeCopy[index] -= minBurstTime;

for (int i = 0; i < arrivalTime.size(); i++)
{
if (i != currActiveProcessID && burstTimeCopy[i] != 0)
{
waitingTime[i] = waitingTime[i] + minBurstTime;
}
}
timeCounter += minBurstTime;
}
}
}

void Scheduling::printInfo()
{
std::cout << "ProcessID\tArrival Time\tBurst Time\tWaiting Time\n";
for (int i = 0; i < arrivalTime.size(); i++)
{
std::cout << i+1 << "\t\t" << arrivalTime[i] << "\t\t" << burstTime[i];
std::cout << "\t\t" << waitingTime[i] << "\n";
}
}

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


Some things to consider:

1. You've tagged your question with , implying that you're using that version of the C++ language to compile your code. As such, you should shun the use of typedef as much as possible, since in C++11, the much more flexible and much more readable using was introduced. Applied to your code, typedef unsigned int uint would become using uint = unsigned int, for example.
2. Speaking of type aliases: Please put your code into an appropriate namespace. Especially since you just straight up typedef the extremely common name uint, the probability of causing some sort of incompatibility with other libraries is extremely high. Speaking of that, do you really need the uint typedef? Usually, you should strive to keep your headers as clean as possible, and that typedef strikes me as neither aimed at users of your library nor as helpful in any other way.
3. Instead of offering both a default constructor and a constructor taking a single uint, consider removing the default constructor and adding a default argument value of 0 to the uint-constructor, since calling that constructor with argument 0 does basically the same as default constructing.
4. In for-loops, such as in for ( int i = 0; i < n; i++), don't use int unless you're sure it's appropriate. In this case, n is of type unsigned int, so as a user I could theoretically pass std::numeric_limits<unsigned int>::max(), in which case your code would have undefined behavior.
5. You're reserving n entries of memory for your three vectors in each iteration of the for-loop in Scheduling(uint n), i.e. n^2 entries in general. This is bad, because 1) reserve is not a cheap operation, 2) you're running a serious risk of your program dieing from out of memory for large n and 3) you don't need that much memory at all. Instead of reserving every iteration, reserve n elements up front, then iterate.
6. Related to the above point, while you are filling arrivalTime and burstTime with data from standard input, waitingTime is only filled with 0s. Luckily, std::vector comes with a constructor that exist exactly for this purpose (= creating a vector with n copies of an element). I recommend you instead put the initialization of waitingTime into the member initialization list, like so: Scheduling::Scheduling(uint n) : waitingTime(n, 0) { ....
7. There are a lot of things wrong with isAllZeroes:
1. First of all, this function should be static, since it is not exported via your header and thus only used locally.
2. Secondly, the function is bugged and does not work. You're not actually checking whether all elements are 0; instead, you're just checking the first element and return whether that's 0 or not.
3. Third, you're taking one argument, named burstTimeCopy, via non-const reference. However, you're not doing any modifications to it; so that should be a const reference. Also, there's no actual copying involved, so the variable name is misleading.
4. Fourth, that for-loop has the same issue I already mentioned in point 4 above. Since std::vector::size() returns a result of type std::size_t, you should make your iteration variable of that type as well, or risk undefined behavior via overflow. However, you actually don't need to manually write out that for-loop at all, since there exists a for-each construct since C++11: for (uint element : bustTimeCopy) does the same, but is much more concise and doesn't introduce another clutter variable.
5. Actually, this whole function can be replaced by a single call to std::all_of from the algorithm header. You could just write return std::all_of(burstTimeCopy.begin(), burstTimeCopy.end(), [] (uint e) { return e == 0; }); for the function body and be done, or even drop the function all together and replace its invocations by this one liner.
8. Don't compare boolean results for equality. By this I mean that writing if (some_bool_thing == true) or if (some_bool_thing == false) can and should be replaced by if (some_bool_thing) and if (!some_bool_thing), respectively. Otherwise, you're just being unnecessarily verbose.
9. calcWaitingTime is somewhat messy right now. The method spans a whopping 70 lines, and consists of a lot of nested ifs, fors and whiles. As of right now, the method is barely readable, and probably even harder to maintain.

What can be done about that? First of all, one of the most important principles for writing good and maintainable code is to granularize, i.e. to split up everything into small, digestible pieces that are easier to verify and easier to work with than giant, monolithic constructs. As a rule of thumb, almost all functions should consist of no more than a handful of individual statements, where a handful varies a bit by whom you ask, but is generally somewhere below 20, or even below 10.

Coming back to the example at hand, I recommend you to go through the method, and every time you see a new if, or a for or a while, take some time and think whether these could be succinctly expressed as their own functions. If you think they can be, go ahead and write that function, and replace the existing structure with that. Then, go through the code once more and look for similarities in the functions you just extracted. If you find that two functions are similar enough, try merging them into a single function.

Another thing I recommend you is taking some time and getting familiar with the functionality offered in the algorithm library, of which you have already made use a little. These algorithms encode extremely common patterns, such as checking whether all things in a container satisfy certain criteria, or finding elements, or summing all elements, etc. Then, go through you code again and try to look for common patterns which can be easily expressed through these algorithms. For example, there's a comment saying //Find index with minimum burst Time remaining in there, which suggests that the following code might be easily replaceable by a call to std::find or one of its friends.

I am not going to go into the gory details of calcWaitingTime here and analyze it, because I find the method as it currently is extremely hard to parse and understand, and I don't want to invest the time necessary to get a good overview. If you're interested in a more in-depth review of that method, please do some clean-up and post a follow up question, or hope that somebody has more patience than I do and will go through the whole 70 lines.

10. When printing out single characters, such as \n, use single quotes instead of double quotes, i.e. std::cout << '\n' over std::cout << "\n". The latter entails a pointer dereference and a call to std::strlen, which are both wasted performance. (The performance loss is probably negligible in most cases, but the change is so small and simple that it's still worth doing, in my opinion.)

Some of the above criticism is pretty harsh, I admit. Still, I hope that you're not taking it too personally, because my goal is not to denigrate or attack you, just to point out what's not good about your code and how to improve it. Admittedly, I'm not know to sugarcoat things, so please tell me if you feel that my criticism is unjust, or wrong, or in any other way not fair. Also, while this should go without saying, please feel free to ask if there's anything unclear.

Code looks clean overall and quite easy to digest. But there are some issues.

1) isAllZeroes() is not correctly implemented.

2) You make a copy of the burstTime vector but the original doesn't seem to be updated. Why a copy then?

3) The copy is not actually done, only the allocation.

Note that I don't have full knowledge of the algorithm you implemented here.

• I have made copy because I don't want to modify original burstTime and function calcWaitingTime() modifies burstTimeCopy.\ – coder Jun 22 '18 at 18:35