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

◆ 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;
}