SJF< S, T, E > Class Template Reference

Class which implements the SJF scheduling algorithm. More...

Public Member Functions
void	addProcess (S id, T arrival, E burst)
	Adds the process to the ready queue if it isn't already there.
vector< tuple< S, T, E, double, double, double > >	scheduleForSJF ()
	Algorithm for scheduling CPU processes according to the Shortest Job First (SJF) scheduling algorithm.
void	printResult (const vector< tuple< S, T, E, double, double, double > > &processes)
	Utility function for printing the status of each process after execution.

Private Attributes
priority_queue< tuple< S, T, E, double, double, double >, vector< tuple< S, T, E, double, double, double > >, Compare< S, T, E > >	schedule
vector< tuple< S, T, E, double, double, double > >	result
unordered_set< S >	idList

Detailed Description

template<typename S, typename T, typename E>
class SJF< S, T, E >

Class which implements the SJF scheduling algorithm.

Template Parameters

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

Definition at line 96 of file non_preemptive_sjf_scheduling.cpp.

Member Function Documentation

addProcess()

template<typename S , typename T , typename E >

void SJF< S, T, E >::addProcess ( S id, T arrival, E burst )

inline

Adds the process to the ready queue if it isn't already there.

Parameters

id	Process ID
arrival	Arrival time of the process
burst	Burst time of the process

Returns

void

Definition at line 127 of file non_preemptive_sjf_scheduling.cpp.

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

printResult()

template<typename S , typename T , typename E >

void SJF< S, T, E >::printResult ( const vector< tuple< S, T, E, double, double, double > > & processes )

inline

Utility function for printing the status of each process after execution.

Returns

void

Definition at line 197 of file non_preemptive_sjf_scheduling.cpp.

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

scheduleForSJF()

template<typename S , typename T , typename E >

vector< tuple< S, T, E, double, double, double > > SJF< S, T, E >::scheduleForSJF ( )

inline

Algorithm for scheduling CPU processes according to the Shortest Job First (SJF) scheduling algorithm.

Non pre-emptive SJF is an algorithm that schedules processes based on the length of their burst times. The process with the smallest burst time is executed first.In a non-preemptive scheduling algorithm, once a process starts executing,it runs to completion without being interrupted.

I used a min priority queue because it allows you to efficiently pick the process with the smallest burst time in constant time, by maintaining a priority order where the shortest burst process is always at the front.

Returns

void

Definition at line 154 of file non_preemptive_sjf_scheduling.cpp.

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

Member Data Documentation

idList

template<typename S , typename T , typename E >

unordered_set<S> SJF< S, T, E >::idList

private

Definition at line 116 of file non_preemptive_sjf_scheduling.cpp.

result

template<typename S , typename T , typename E >

vector<tuple<S, T, E, double, double, double> > SJF< S, T, E >::result

private

Definition at line 113 of file non_preemptive_sjf_scheduling.cpp.

schedule

template<typename S , typename T , typename E >

priority_queue<tuple<S, T, E, double, double, double>, vector<tuple<S, T, E, double, double, double> >, Compare<S, T, E> > SJF< S, T, E >::schedule

private

Priority queue of schedules(stored as tuples) of processes. In each tuple

Template Parameters

1st	element: Process ID
2nd	element: Arrival Time
3rd	element: Burst time
4th	element: Completion time
5th	element: Turnaround time
6th	element: Waiting time

Definition at line 110 of file non_preemptive_sjf_scheduling.cpp.

---

The documentation for this class was generated from the following file:

• cpu_scheduling_algorithms/non_preemptive_sjf_scheduling.cpp