fcfs_scheduling.cpp File Reference

Implementation of FCFS CPU scheduling algorithm. More...

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>

Include dependency graph for fcfs_scheduling.cpp:

Classes
class	Compare< S, T, E >
	Comparator class for priority queue. More...
class	FCFS< S, T, E >
	Class which implements the FCFS 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< uint32_t, uint32_t, uint32_t > > input)
	Function to be used for testing purposes. This function guarantees the correct solution for FCFS scheduling algorithm.
static void	test ()
	Self-test implementations.
int	main ()
	Entry point of the program.

Detailed Description

Implementation of FCFS CPU scheduling algorithm.

FCFS is a non-preemptive CPU scheduling algorithm in which whichever process arrives first, gets executed first. If two or more processes arrive simultaneously, the process with smaller process ID gets executed first. https://bit.ly/3ABNXOCPratyush Vatsa

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< uint32_t, uint32_t, uint32_t > >

input

)

Function to be used for testing purposes. This function guarantees the correct solution for FCFS scheduling algorithm.

Parameters

input

the input data

Sorts the input vector according to arrival time. Processes whose arrival times are same get sorted according to process ID For each process, completion time, turnaround time and completion time are calculated, inserted in a tuple, which is added to the vector result.

Returns

A vector of tuples consisting of process ID, arrival time, burst time, completion time, turnaround time and waiting time for each process.

                                                       {
    sort(input.begin(), input.end(), sortcol<S, T, E>);
    vector<tuple<S, T, E, double, double, double>> result(input.size());
    double timeElapsed = 0;
    for (size_t i{}; i < input.size(); i++) {
        T arrival = get<1>(input[i]);
        E burst = get<2>(input[i]);
 
        if (arrival > timeElapsed) {
            timeElapsed += arrival - timeElapsed;
        }
        timeElapsed += burst;
        double completion = timeElapsed;
        double turnaround = completion - arrival;
        double waiting = turnaround - burst;
 
        get<0>(result[i]) = get<0>(input[i]);
        get<1>(result[i]) = arrival;
        get<2>(result[i]) = burst;
        get<3>(result[i]) = completion;
        get<4>(result[i]) = turnaround;
        get<5>(result[i]) = waiting;
    }
    return result;
}

Here is the call graph for this function:

main()

int main

(

void

)

Entry point of the program.

Returns

0 on exit

           {
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

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
t2	Second tuple

Returns

true if t1 and t2 are in the CORRECT order

false if t1 and t2 are in the INCORRECT order

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

test()

static void test ( )

static

Self-test implementations.

Returns

void

                   {
    for (int i{}; i < 1000; i++) {
        srand(time(nullptr));
        uint32_t n = 1 + rand() % 1000;
        FCFS<uint32_t, uint32_t, uint32_t> readyQueue;
        vector<tuple<uint32_t, uint32_t, uint32_t>> input(n);
 
        for (uint32_t i{}; i < n; i++) {
            get<0>(input[i]) = i;
            srand(time(nullptr));
            get<1>(input[i]) = 1 + rand() % 10000;
            srand(time(nullptr));
            get<2>(input[i]) = 1 + rand() % 10000;
        }
 
        for (uint32_t i{}; i < n; i++) {
            readyQueue.addProcess(get<0>(input[i]), get<1>(input[i]),
                                  get<2>(input[i]));
        }
        vector<tuple<uint32_t, uint32_t, uint32_t, double, double, double>>
            res = get_final_status<uint32_t, uint32_t, uint32_t>(input);
        assert(res == readyQueue.scheduleForFcfs());
        // readyQueue.printResult();
    }
    cout << "All the tests have successfully passed!" << endl;
}

Here is the call graph for this function: