non_preemptive_sjf_scheduling.cpp

Go to the documentation of this file.

 
#include <algorithm>      
#include <cassert>        
#include <iomanip>        
#include <iostream>       
#include <queue>          
#include <random>         
#include <unordered_set>  
#include <vector>         
 
using std::cin;
using std::cout;
using std::endl;
using std::get;
using std::left;
using std::make_tuple;
using std::priority_queue;
using std::tuple;
using std::unordered_set;
using std::vector;
 
template <typename S, typename T, typename E>
bool sortcol(tuple<S, T, E>& t1, tuple<S, T, E>& t2) {
    if (get<1>(t1) < get<1>(t2) ||
        (get<1>(t1) == get<1>(t2) && get<0>(t1) < get<0>(t2))) {
        return true;
    }
    return false;
}
 
template <typename S, typename T, typename E>
class Compare {
 public:
    bool operator()(tuple<S, T, E, double, double, double>& t1,
                    tuple<S, T, E, double, double, double>& t2) {
        // Compare burst times for SJF
        if (get<2>(t2) < get<2>(t1)) {
            return true;
        }
        // If burst times are the same, compare arrival times
        else if (get<2>(t2) == get<2>(t1)) {
            return get<1>(t2) < get<1>(t1);
        }
        return false;
    }
};
 
template <typename S, typename T, typename E>
class SJF {
    priority_queue<tuple<S, T, E, double, double, double>,
                   vector<tuple<S, T, E, double, double, double>>,
                   Compare<S, T, E>>
        schedule;
 
    // Stores final status of all the processes after completing the execution.
    vector<tuple<S, T, E, double, double, double>> result;
 
    // Stores process IDs. Used for confirming absence of a process while  it.
    unordered_set<S> idList;
 
 public:
    void addProcess(S id, T arrival, E burst) {
        // Add if a process with process ID as id is not found in idList.
        if (idList.find(id) == idList.end()) {
            tuple<S, T, E, double, double, double> t =
                make_tuple(id, arrival, burst, 0, 0, 0);
            schedule.push(t);
            idList.insert(id);
        }
    }
 
    vector<tuple<S, T, E, double, double, double>> scheduleForSJF() {
        // Variable to keep track of time elapsed so far
        double timeElapsed = 0;
 
        while (!schedule.empty()) {
            tuple<S, T, E, double, double, double> cur = schedule.top();
 
            // If the current process arrived at time t2, the last process
            // completed its execution at time t1, and t2 > t1.
            if (get<1>(cur) > timeElapsed) {
                timeElapsed += get<1>(cur) - timeElapsed;
            }
 
            // Add Burst time to time elapsed
            timeElapsed += get<2>(cur);
 
            // Completion time of the current process will be same as time
            // elapsed so far
            get<3>(cur) = timeElapsed;
 
            // Turnaround time = Completion time - Arrival time
            get<4>(cur) = get<3>(cur) - get<1>(cur);
 
            // Waiting time = Turnaround time - Burst time
            get<5>(cur) = get<4>(cur) - get<2>(cur);
 
            // Turnaround time >= Burst time
            assert(get<4>(cur) >= get<2>(cur));
 
            // Waiting time is never negative
            assert(get<5>(cur) >= 0);
 
            result.push_back(cur);
            schedule.pop();
        }
        return result;
    }
    void printResult(
        const vector<tuple<S, T, E, double, double, double>>& processes) {
        cout << std::setw(17) << left << "Process ID" << std::setw(17) << left
             << "Arrival Time" << std::setw(17) << left << "Burst Time"
             << std::setw(17) << left << "Completion Time" << std::setw(17)
             << left << "Turnaround Time" << std::setw(17) << left
             << "Waiting Time" << endl;
 
        for (const auto& process : processes) {
            cout << std::setprecision(2) << std::fixed << std::setw(17) << left
                 << get<0>(process) << std::setw(17) << left << get<1>(process)
                 << std::setw(17) << left << get<2>(process) << std::setw(17)
                 << left << get<3>(process) << std::setw(17) << left
                 << get<4>(process) << std::setw(17) << left << get<5>(process)
                 << endl;
        }
    }
};
 
template <typename S, typename T, typename E>
vector<tuple<S, T, E, double, double, double>> get_final_status(
    vector<tuple<S, T, E>> input) {
    // Sort the processes based on Arrival time and then Burst time
    sort(input.begin(), input.end(), sortcol<S, T, E>);
 
    // Result vector to hold the final status of each process
    vector<tuple<S, T, E, double, double, double>> result(input.size());
    double timeElapsed = 0;
 
    for (size_t i = 0; i < input.size(); i++) {
        // Extract Arrival time and Burst time
        T arrival = get<1>(input[i]);
        E burst = get<2>(input[i]);
 
        // If the CPU is idle, move time to the arrival of the next process
        if (arrival > timeElapsed) {
            timeElapsed = arrival;
        }
 
        // Update timeElapsed by adding the burst time
        timeElapsed += burst;
 
        // Calculate Completion time, Turnaround time, and Waiting time
        double completion = timeElapsed;
        double turnaround = completion - arrival;
        double waiting = turnaround - burst;
 
        // Store the results in the result vector
        result[i] = make_tuple(get<0>(input[i]), arrival, burst, completion,
                               turnaround, waiting);
    }
 
    return result;
}
 
static void test() {
    // A vector to store the results of all processes across all test cases.
    vector<tuple<uint32_t, uint32_t, uint32_t, double, double, double>>
        finalResult;
 
    for (int i{}; i < 10; i++) {
        std::random_device rd;  // Seeding
        std::mt19937 eng(rd());
        std::uniform_int_distribution<> distr(1, 10);
 
        uint32_t n = distr(eng);
        SJF<uint32_t, uint32_t, uint32_t> readyQueue;
        vector<tuple<uint32_t, uint32_t, uint32_t, double, double, double>>
            input(n);
 
        // Generate random arrival and burst times
        for (uint32_t i{}; i < n; i++) {
            get<0>(input[i]) = i;
            get<1>(input[i]) = distr(eng);  // Random arrival time
            get<2>(input[i]) = distr(eng);  // Random burst time
        }
 
        // Print processes before scheduling
        cout << "Processes before SJF scheduling:" << endl;
        readyQueue.printResult(input);
 
        // Add processes to the queue
        for (uint32_t i{}; i < n; i++) {
            readyQueue.addProcess(get<0>(input[i]), get<1>(input[i]),
                                  get<2>(input[i]));
        }
 
        // Perform SJF schedulings
        auto finalResult = readyQueue.scheduleForSJF();
 
        // Print processes after scheduling
        cout << "\nProcesses after SJF scheduling:" << endl;
        readyQueue.printResult(finalResult);
    }
    cout << "All the tests have successfully passed!" << endl;
}
 
int main() {
    test();
    return 0;
}