Question

(Python or C++)

We are going to implement the following scheduling algorithms that we discussed in class:

1. First-Come First-Served (FCFS)

2. Shortest Remaining Time First (SRTF)

3. Highest Response Ratio Next (HRRN)

4. Round Robin, with different quantum values (RR)

We are interested to compute the following metrics, for each experiment:

_ The average turnaround time

_ The total throughput (number of processes done per unit time)

_ The CPU utilization

_ The average number of processes in the ready queue

we need to generate its arrival time and its requested service time. We can assume that processes arrive with an average rate _ that follows a Poisson process

We will vary lambda to simulate different loads while keeping the average service time fixed. Then simulator should stop after processing 10,000 processes to completion (without stopping the arrival process), then it should output the statistics

An event que shall be made and update the current state after events. A priority que shall be made to make sure that events are kept in the right order and named event queue and keeps a time of the first event. The simulator should take few command-line arguments. The first is to indicate the scheduler, a 1

through 4 value based on the list above.

Also, it should take other arguments such as the average arrival

rate, the average service time, and the quantum interval (for RR). Running the simulator with no arguments,

should display the parameters usage.

We will vary the average arrival rate, _, of processes from 10 process per second to 30 processes per second

(based on a Poisson process). The service time is chosen according to an exponential distribution with an

average service time of 0.04 sec.

The output should also be printed into a seperate file for easy interpretation.

Answer 1

1. First-Come First-Served (FCFS)

// C++ program for implementation of FCFS 
// scheduling 
#include<iostream> 
using namespace std; 

// Function to find the waiting time for all 
// processes 
void findWaitingTime(int processes[], int n, 
                                                int BurstTime[], int WaitingTime[]) 
{ 
        // waiting time for first process is 0 
        WaitingTime[0] = 0; 

        // calculating waiting time 
        for (int i = 1; i < n ; i++ ) 
                WaitingTime[i] = BurstTime[i-1] + WaitingTime[i-1] ; 
} 

// Function to calculate turn around time 
void findTurnAroundTime( int processes[], int n, 
                                int BurstTime[], int WaitingTime[], int TurnAroundTime[]) 
{ 
        // calculating turnaround time by adding 
        // BurstTime[i] + WaitingTime[i] 
        for (int i = 0; i < n ; i++) 
                TurnAroundTime[i] = BurstTime[i] + WaitingTime[i]; 
} 

//Function to calculate average time 
void findavgTime( int processes[], int n, int BurstTime[]) 
{ 
        int WaitingTime[n], TurnAroundTime[n], total_waitingtime = 0, total_turnaroundtime = 0; 

        //Function to find waiting time of all processes 
        findWaitingTime(processes, n, BurstTime, WaitingTime); 

        //Function to find turn around time for all processes 
        findTurnAroundTime(processes, n, BurstTime, WaitingTime, TurnAroundTime); 

        //Display processes along with all details 
        cout << "Processes "<< " Burst time "
                << " Waiting time " << " Turn around time\n"; 

        // Calculate total waiting time and total turn 
        // around time 
        for (int i=0; i<n; i++) 
        { 
                total_waitingtime = total_waitingtime + WaitingTime[i]; 
                total_turnaroundtime = total_turnaroundtime + TurnAroundTime[i]; 
                cout << " " << i+1 << "\t\t" << BurstTime[i] <<"\t "
                        << WaitingTime[i] <<"\t\t " << TurnAroundTime[i] <<endl; 
        } 

        cout << "Average waiting time = "
                << (float)total_waitingtime / (float)n; 
        cout << "\nAverage turn around time = "
                << (float)total_turnaroundtime / (float)n; 
} 

// Driver code 
int main() 
{ 
        //process id's 
        int processes[] = { 2, 4, 6}; 
        int n = sizeof processes / sizeof processes[0]; 

        //Burst time of all processes 
        int burst_time[] = {3, 7, 3}; 

        findavgTime(processes, n, burst_time); 
        return 0; 
} 

Output

2. Shortest Remaining Time First (SRTF)

// C++ program to implement Shortest Remaining Time First 
// Shortest Remaining Time First (SRTF) 

#include <bits/stdc++.h> 
using namespace std; 

struct Process { 
        int pid; // Process ID 
        int BurstTime; // Burst Time 
        int art; // Arrival Time 
}; 

// Function to find the waiting time for all 
// processes 
void findWaitingTime(Process proc[], int n, 
                                                                int WaitingTime[]) 
{ 
        int rt[n]; 

        // Copy the burst time into rt[] 
        for (int i = 0; i < n; i++) 
                rt[i] = proc[i].BurstTime; 

        int complete = 0, t = 0, minm = INT_MAX; 
        int shortest = 0, finish_time; 
        bool check = false; 

        // Process until all processes gets 
        // completed 
        while (complete != n) { 

                // Find process with minimum 
                // remaining time among the 
                // processes that arrives till the 
                // current time` 
                for (int j = 0; j < n; j++) { 
                        if ((proc[j].art <= t) && 
                        (rt[j] < minm) && rt[j] > 0) { 
                                minm = rt[j]; 
                                shortest = j; 
                                check = true; 
                        } 
                } 

                if (check == false) { 
                        t++; 
                        continue; 
                } 

                // Reduce remaining time by one 
                rt[shortest]--; 

                // Update minimum 
                minm = rt[shortest]; 
                if (minm == 0) 
                        minm = INT_MAX; 

                // If a process gets completely 
                // executed 
                if (rt[shortest] == 0) { 

                        // Increment complete 
                        complete++; 
                        check = false; 

                        // Find finish time of current 
                        // process 
                        finish_time = t + 1; 

                        // Calculate waiting time 
                        WaitingTime[shortest] = finish_time - 
                                                proc[shortest].BurstTime - 
                                                proc[shortest].art; 

                        if (WaitingTime[shortest] < 0) 
                                WaitingTime[shortest] = 0; 
                } 
                // Increment time 
                t++; 
        } 
} 

// Function to calculate turn around time 
void findTurnAroundTime(Process proc[], int n, 
                                                int WaitingTime[], int TurnAroundTime[]) 
{ 
        // calculating turnaround time by adding 
        // BurstTime[i] + WaitingTime[i] 
        for (int i = 0; i < n; i++) 
                TurnAroundTime[i] = proc[i].BurstTime + WaitingTime[i]; 
} 

// Function to calculate average time 
void findAverageTime(Process proc[], int n) 
{ 
        int WaitingTime[n], TurnAroundTime[n], total_waitingtime = 0, 
                                        total_turnaroundtime = 0; 

        // Function to find waiting time of all 
        // processes 
        findWaitingTime(proc, n, WaitingTime); 

        // Function to find turn around time for 
        // all processes 
        findTurnAroundTime(proc, n, WaitingTime, TurnAroundTime); 

        // Display processes along with all 
        // details 
        cout << "Processes "
                << " Burst time "
                << " Waiting time "
                << " Turn around time\n"; 

        // Calculate total waiting time and 
        // total turnaround time 
        for (int i = 0; i < n; i++) { 
                total_waitingtime = total_waitingtime + WaitingTime[i]; 
                total_turnaroundtime = total_turnaroundtime + TurnAroundTime[i]; 
                cout << " " << proc[i].pid << "\t\t"
                        << proc[i].BurstTime << "\t\t " << WaitingTime[i] 
                        << "\t\t " << TurnAroundTime[i] << endl; 
        } 

        cout << "\nAverage waiting time = "
                << (float)total_waitingtime / (float)n; 
        cout << "\nAverage turn around time = "
                << (float)total_turnaroundtime / (float)n; 
} 

// Driver code 
int main() 
{ 
        Process proc[] = { { 1, 7, 2 }, { 2, 7, 3 }, 
                                        { 3, 5, 3 }, { 4, 5, 7 } }; 
        int n = sizeof(proc) / sizeof(proc[0]); 

        findAverageTime(proc, n); 
        return 0; 
} 

Output:

3. Highest Response Ratio Next (HRRN)

// CPP program for Highest Response Ratio Next (HRRN) Scheduling 
#include <bits/stdc++.h> 
using namespace std; 
// Defining process details 
struct process { 
        char name; 
        int arrivaltime, bursttime, ct, waitingtime, tt; 
        int completed; 
        float nturnaroundtime; 
} p[10]; 
        
int n; 
        
// Sorting Processes by Arrival Time 
void sortByArrival() 
{ 
        struct process temp; 
        int i, j; 
        
        // Selection Sort applied 
        for (i = 0; i < n - 1; i++) { 
                for (j = i + 1; j < n; j++) { 
        
                        // Check for lesser arrival time 
                        if (p[i].arrivaltime > p[j].arrivaltime) { 
        
                                // Swap earlier process to front 
                                temp = p[i]; 
                                p[i] = p[j]; 
                                p[j] = temp; 
                        } 
                } 
        } 
} 
        
int main() 
{ 
        int i, j, t, sum_bt = 0; 
        char c; 
        float averagewaitingtime = 0, averagettime = 0; 
        n = 5; 
        
        // predefined arrival times 
        int arriv[] = { 0, 2, 4, 6, 8 }; 
        
        // predefined burst times 
        int burst[] = { 3, 6, 4, 5, 2 }; 
        
        // Initializing the structure variables 
        for (i = 0, c = 'A'; i < n; i++, c++) { 
                p[i].name = c; 
                p[i].arrivaltime = arriv[i]; 
                p[i].bursttime = burst[i]; 
        
                // Variable for Completion status 
                // Pending = 0 
                // Completed = 1 
                p[i].completed = 0; 
        
                // Variable for sum of all Burst Times 
                sum_bt += p[i].bursttime; 
        } 
        
        // Sorting the structure by arrival times 
        sortByArrival(); 
        cout << "Name " << " Arrival Time " << " Burst Time " << " Waiting Time "
        << " TurnAround Time " << " Normalized TT" ; 
        for (t = p[0].arrivaltime; t < sum_bt;) { 
        
                // Set lower limit to response ratio 
                float hrr = -9999; 
        
                // Response Ratio Variable 
                float temp; 
        
                // Variable to store next processs selected 
                int loc; 
                for (i = 0; i < n; i++) { 
        
                        // Checking if process has arrived and is Incomplete 
                        if (p[i].arrivaltime <= t && p[i].completed != 1) { 
        
                                // Calculating Response Ratio 
                                temp = (p[i].bursttime + (t - p[i].arrivaltime)) / p[i].bursttime; 
        
                                // Checking for Highest Response Ratio 
                                if (hrr < temp) { 
        
                                        // Storing Response Ratio 
                                        hrr = temp; 
        
                                        // Storing Location 
                                        loc = i; 
                                } 
                        } 
                } 
        
                // Updating time value 
                t += p[loc].bursttime; 
        
                // Calculation of waiting time 
                p[loc].waitingtime = t - p[loc].arrivaltime - p[loc].bursttime; 
        
                // Calculation of Turn Around Time 
                p[loc].tt = t - p[loc].arrivaltime; 
        
                // Sum Turn Around Time for average 
                averagettime += p[loc].tt; 
        
                // Calculation of Normalized Turn Around Time 
                p[loc].nturnaroundtime = ((float)p[loc].tt / p[loc].bursttime); 
        
                // Updating Completion Status 
                p[loc].completed = 1; 
        
                // Sum Waiting Time for average 
                averagewaitingtime += p[loc].waitingtime; 
                cout<< "\n" << p[loc].name <<"\t" << p[loc].arrivaltime; 
                cout << "\t\t" << p[loc].bursttime <<"\t\t"<< p[loc].waitingtime; 
                cout <<"\t\t"<< p[loc].tt <<"\t\t"<< p[loc].nturnaroundtime; 
        } 
        cout << "\nAverage waiting time: " << averagewaitingtime / n << endl; 
        cout <<"Average Turn Around time:"<< averagettime / n; 
} 

Output:

4. Round Robin, with different quantum values (RR)

// C++ program for implementation of RR scheduling 
#include<iostream> 
using namespace std; 

// Function to find the waiting time for all 
// processes 
void findWaitingTime(int processes[], int n, 
                        int bursttime[], int waitingtime[], int quantum) 
{ 
        // Make a copy of burst times bursttime[] to store remaining 
        // burst times. 
        int rem_bursttime[n]; 
        for (int i = 0 ; i < n ; i++) 
                rem_bursttime[i] = bursttime[i]; 

        int t = 0; // Current time 

        // Keep traversing processes in round robin manner 
        // until all of them are not done. 
        while (1) 
        { 
                bool done = true; 

                // Traverse all processes one by one repeatedly 
                for (int i = 0 ; i < n; i++) 
                { 
                        // If burst time of a process is greater than 0 
                        // then only need to process further 
                        if (rem_bursttime[i] > 0) 
                        { 
                                done = false; // There is a pending process 

                                if (rem_bursttime[i] > quantum) 
                                { 
                                        // Increase the value of t i.e. shows 
                                        // how much time a process has been processed 
                                        t += quantum; 

                                        // Decrease the burst_time of current process 
                                        // by quantum 
                                        rem_bursttime[i] -= quantum; 
                                } 

                                // If burst time is smaller than or equal to 
                                // quantum. Last cycle for this process 
                                else
                                { 
                                        // Increase the value of t i.e. shows 
                                        // how much time a process has been processed 
                                        t = t + rem_bursttime[i]; 

                                        // Waiting time is current time minus time 
                                        // used by this process 
                                        waitingtime[i] = t - bursttime[i]; 

                                        // As the process gets fully executed 
                                        // make its remaining burst time = 0 
                                        rem_bursttime[i] = 0; 
                                } 
                        } 
                } 

                // If all processes are done 
                if (done == true) 
                break; 
        } 
} 

// Function to calculate turn around time 
void findTurnAroundTime(int processes[], int n, 
                                                int bursttime[], int waitingtime[], int turnaroundtime[]) 
{ 
        // calculating turnaround time by adding 
        // bursttime[i] + waitingtime[i] 
        for (int i = 0; i < n ; i++) 
                turnaroundtime[i] = bursttime[i] + waitingtime[i]; 
} 

// Function to calculate average time 
void findavgTime(int processes[], int n, int bursttime[], 
                                                                        int quantum) 
{ 
        int waitingtime[n], turnaroundtime[n], total_wt = 0, total_tat = 0; 

        // Function to find waiting time of all processes 
        findWaitingTime(processes, n, bursttime, waitingtime, quantum); 

        // Function to find turn around time for all processes 
        findTurnAroundTime(processes, n, bursttime, waitingtime, turnaroundtime); 

        // Display processes along with all details 
        cout << "Processes "<< " Burst time "
                << " Waiting time " << " Turn around time\n"; 

        // Calculate total waiting time and total turn 
        // around time 
        for (int i=0; i<n; i++) 
        { 
                total_wt = total_wt + waitingtime[i]; 
                total_tat = total_tat + turnaroundtime[i]; 
                cout << " " << i+1 << "\t\t" << bursttime[i] <<"\t "
                        << waitingtime[i] <<"\t\t " << turnaroundtime[i] <<endl; 
        } 

        cout << "Average waiting time = "
                << (float)total_wt / (float)n; 
        cout << "\nAverage turn around time = "
                << (float)total_tat / (float)n; 
} 

// Driver code 
int main() 
{ 
        // process id's 
        int processes[] = { 1, 2, 3}; 
        int n = sizeof processes / sizeof processes[0]; 

        // Burst time of all processes 
        int burst_time[] = {5, 5, 3}; 

        // Time quantum 
        int quantum = 2; 
        findavgTime(processes, n, burst_time, quantum); 
        return 0; 
} 

Output: