non_preemptive_sjf_scheduling.cpp File Reference

Implementation of SJF CPU scheduling algorithm. More...

#include <algorithm>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <queue>
#include <random>
#include <unordered_set>
#include <vector>

Include dependency graph for non_preemptive_sjf_scheduling.cpp:

Go to the source code of this file.

Classes
class	Compare< S, T, E >
	Comparator class for priority queue. More...
class	SJF< S, T, E >
	Class which implements the SJF scheduling algorithm. More...

Functions
template<typename S, typename T, typename E>
bool	sortcol (tuple< S, T, E > &t1, tuple< S, T, E > &t2)
	Comparator function for sorting a vector.
template<typename S, typename T, typename E>
vector< tuple< S, T, E, double, double, double > >	get_final_status (vector< tuple< S, T, E > > input)
	Computes the final status of processes after applying non-preemptive SJF scheduling.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Implementation of SJF CPU scheduling algorithm.

shortest job first (SJF), also known as shortest job next (SJN), is a scheduling policy that selects for execution the waiting process with the smallest execution time. SJN is a non-preemptive algorithm. Shortest remaining time is a preemptive variant of SJN. detailed description on SJF scheduling Author : Lakshmi Srikumar

Definition in file non_preemptive_sjf_scheduling.cpp.

Function Documentation

get_final_status()

template<typename S, typename T, typename E>

vector< tuple< S, T, E, double, double, double > > get_final_status

(

vector< tuple< S, T, E > >

input

)

Computes the final status of processes after applying non-preemptive SJF scheduling.

Template Parameters

S	Data type of Process ID
T	Data type of Arrival time
E	Data type of Burst time

Parameters

input

A vector of tuples containing Process ID, Arrival time, and Burst time

Returns

A vector of tuples containing Process ID, Arrival time, Burst time, Completion time, Turnaround time, and Waiting time

Definition at line 228 of file non_preemptive_sjf_scheduling.cpp.

                                  {
    // 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;
}

main()

int main

(

void

)

Main function.

Returns

0 on successful exit

Definition at line 313 of file non_preemptive_sjf_scheduling.cpp.

           {
    test();
    return 0;
}

sortcol()

template<typename S, typename T, typename E>

bool sortcol	(	tuple< S, T, E > &	t1,
		tuple< S, T, E > &	t2 )

Comparator function for sorting a vector.

Template Parameters

S	Data type of Process ID
T	Data type of Arrival time
E	Data type of Burst time

Parameters

t1	First tuple<S,T,E>t1
t2	Second tuple<S,T,E>t2

Returns

true if t1 and t2 are in the CORRECT order

false if t1 and t2 are in the INCORRECT order

Definition at line 45 of file non_preemptive_sjf_scheduling.cpp.

                                                     {
    if (get<1>(t1) < get<1>(t2) ||
        (get<1>(t1) == get<1>(t2) && get<0>(t1) < get<0>(t2))) {
        return true;
    }
    return false;
}

test()

void test ( )

static

Self-test implementations.

Returns

void

Definition at line 267 of file non_preemptive_sjf_scheduling.cpp.

                   {
    // 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;
}