fcfs_scheduling.cpp File Reference

Implementation of FCFS CPU scheduling algorithm. More...

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

Include dependency graph for fcfs_scheduling.cpp:

Go to the source code of this file.

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

Definition in file fcfs_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< 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.

Definition at line 226 of file fcfs_scheduling.cpp.

                                                       {
    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

Definition at line 288 of file fcfs_scheduling.cpp.

           {
    test();  // run self-test implementations
    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
t2	Second tuple

Returns

true if t1 and t2 are in the CORRECT order

false if t1 and t2 are in the INCORRECT order

Definition at line 46 of file fcfs_scheduling.cpp.

                                                     {
    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

Definition at line 257 of file fcfs_scheduling.cpp.

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