Objective In this assignment, you will be writing a program that reads a list of
ID: 3919080 • Letter: O
Question
Objective
In this assignment, you will be writing a program that reads a list of process start times and durations from stdin. That list will be used four times to run through the following CPU scheduling algorithms:
• First Come, First Served
• Shortest Job First
• Shortest Remaining Time First
• Round Robin
Your program will show three statistics: the average process response time, the average process wait time, and the average process turnaround time for each scheduling algorithm. The time quantum for the Round Robin scheduler is 100ms. Your program only needs to work with a maximum of 25 processes.
Output
With this process list, the output of your program should look like this:
$ ./p5 < process-list.txt
First Come, First Served
Avg. Resp.: 276.40, Avg. T.A.: 448.90, Avg. Wait: 276.40
Shortest Job First Avg.
Resp.: 202.90, Avg. T.A.: 375.40, Avg. Wait: 202.90
Shortest Remaining Time First Avg.
Resp.: 148.30, Avg. T.A.: 353.30, Avg. Wait: 180.80
Round Robin with Time Quantum of 100
Avg. Resp.: 133.90, Avg. T.A.: 555.90, Avg. Wait: 383.40
Here's a smaller example of an input file. When you turn your program in it should use a time quantum of 100, but for this example you'll want to make it shorter. The Round Robin stats in the output are for a time quantum of 5.
5 8
8 10
15 3
17 2
Here's the output:
$ ./p5 < ex1.txt
First Come, First Served
Avg. Resp.:5.50, Avg. T.A.:11.25, Avg. Wait:5.50
Shortest Job First
Avg. Resp.:5.25, Avg. T.A.:11.00, Avg. Wait:5.25
Shortest Remaining Time First Avg.
Resp.:1.50, Avg. T.A.:8.50, Avg. Wait:2.75
Round Robin with Time Quantum of 5
Avg. Resp.:3.50, Avg. T.A.:12.00, Avg. Wait:6.25
Notes
• Make four functions, one for each scheduling mechanism. Pass the input data to each function as a parameter. Do not modify your original arrays as you will be reusing the data in those arrays multiple times.
• This program is simply an adder of process run times to a clock. Use the value of the clock to determine if new processes need to be added to your queue. Some students have tried to write a program that increments the clock one tick at a time. This is the difficult way to do it and is also incorrect.
• Think about how to make good use of structs (structures) and functions. Even though C doesn't have classes and objects you can still use some of the same design concepts. Keep in mind that it's possible to pass a struct to a function by value, but if the function needs to change an element of the struct it will need a pointer to the struct.
• The context switch cost is negligible and is not figured into this assignment.
• Response time can be calculated by subtracting the process's arrival time from the clock time when the process first starts running. The waiting time is the total of all of the time intervals when the process is not running, after its arrival time and before it finishes. Turnaround time is calculated by subtracting the process's arrival time from the clock time when it finishes.
• For round robin, new processes should be added to the ready queue before the process whose quantum just ended. For example, if P2 arrives at time 16 and P1's quantum ends at time 16, then P2 should be ahead of P1 in the ready queue.
• You can assume that the process arrival times will be in order from smallest to largest in the input.
• To avoid having to type in a lot of numbers every time you run the program you can use input redirection. Use a command like this:
$ ./p5 < numbers.txt
where numbers.txt is a plain-text file that has numbers separated by white space (spaces, newlines, or tabs).
You can use the fscanf function to read in numbers, like this:
int num; while (fscanf(stdin, "%d", &num) == 1) { // Copy the number from num to an array ... }
Read in file:
Explanation / Answer
#include <bits/stdc++.h>
using namespace std;
struct Process {
int pid; // Process ID
int bt; // Burst Time
int art; // Arrival Time
};
// Function to find the waiting time for all
// processes
void findWaitingTimeSRTF(Process proc[], int n,
int wt[])
{
int rt[n];
// Copy the burst time into rt[]
for (int i = 0; i < n; i++)
rt[i] = proc[i].bt;
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++;
// Find finish time of current
// process
finish_time = t + 1;
// Calculate waiting time
wt[shortest] = finish_time -
proc[shortest].bt -
proc[shortest].art;
if (wt[shortest] < 0)
wt[shortest] = 0;
}
// Increment time
t++;
}
}
// Function to calculate turn around time
void findTurnAroundTimeSRTF(Process proc[], int n,
int wt[], int tat[])
{
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n; i++)
tat[i] = proc[i].bt + wt[i];
}
// Function to calculate average time
void findavgTimeSRTF(Process proc[], int n)
{
int wt[n], tat[n], total_wt = 0,
total_tat = 0;
// Function to find waiting time of all
// processes
findWaitingTimeSRTF(proc, n, wt);
// Function to find turn around time for
// all processes
findTurnAroundTimeSRTF(proc, n, wt, tat);
// Display processes along with all
// details
cout << " Processes "
<< " Burst time "
<< " Waiting time "
<< " Turn around time ";
// Calculate total waiting time and
// total turnaround time
for (int i = 0; i < n; i++) {
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << proc[i].pid << " "
<< proc[i].bt << " " << wt[i]
<< " " << tat[i] << endl;
}
cout << " Average waiting time = "
<< (float)total_wt / (float)n;
cout << " Average turn around time = "
<< (float)total_tat / (float)n;
}
// This function is used for sorting all
// processes in increasing order of burst
// time
bool comparisonSJF(Process a, Process b)
{
return (a.bt < b.bt);
}
// Function to find the waiting time for all
// processes
void findWaitingTimeSJF(Process proc[], int n, int wt[])
{
// waiting time for first process is 0
wt[0] = 0;
// calculating waiting time
for (int i = 1; i < n ; i++ )
wt[i] = proc[i-1].bt + wt[i-1] ;
}
// Function to calculate turn around time
void findTurnAroundTimeSJF(Process proc[], int n,
int wt[], int tat[])
{
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n ; i++)
tat[i] = proc[i].bt + wt[i];
}
//Function to calculate average time
void findavgTimeSJF(Process proc[], int n)
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;
// Function to find waiting time of all processes
findWaitingTimeSJF(proc, n, wt);
// Function to find turn around time for all processes
findTurnAroundTimeSJF(proc, n, wt, tat);
// Display processes along with all details
cout << " Processes "<< " Burst time "
<< " Waiting time " << " Turn around time ";
// Calculate total waiting time and total turn
// around time
for (int i = 0; i < n; i++)
{
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << proc[i].pid << " "
<< proc[i].bt << " " << wt[i]
<< " " << tat[i] <<endl;
}
cout << " Average waiting time = "
<< (float)total_wt / (float)n;
cout << " Average turn around time = "
<< (float)total_tat / (float)n;
}
// Function to find the waiting time for all
// processes
void findWaitingTimeFCFS(Process proc[], int n, int wt[])
{
// waiting time for first process is 0
wt[0] = 0;
// calculating waiting time
for (int i = 1; i < n ; i++ )
wt[i] = proc[i-1].bt + wt[i-1] ;
}
// Function to calculate turn around time
void findTurnAroundTimeFCFS(Process proc[], int n, int wt[], int tat[])
{
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n ; i++)
tat[i] = proc[i].bt + wt[i];
}
//Function to calculate average time
void findavgTimeFCFS( Process proc[], int n)
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;
//Function to find waiting time of all processes
findWaitingTimeFCFS(proc, n, wt);
//Function to find turn around time for all processes
findTurnAroundTimeFCFS(proc, n, wt, tat);
//Display processes along with all details
cout << " Processes "<< " Burst time "
<< " Waiting time " << " Turn around time ";
// Calculate total waiting time and total turn
// around time
for (int i=0; i<n; i++)
{
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << i+1 << " " << proc[i].bt <<" "
<< wt[i] <<" " << tat[i] <<endl;
}
cout << " Average waiting time = "
<< (float)total_wt / (float)n;
cout << " Average turn around time = "
<< (float)total_tat / (float)n;
}
// Function to find the waiting time for all
// processes
void findWaitingTimeRR(Process proc[], int n, int wt[], int quantum)
{
// Make a copy of burst times bt[] to store remaining
// burst times.
int rem_bt[n];
for (int i = 0 ; i < n ; i++)
rem_bt[i] = proc[i].bt;
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_bt[i] > 0)
{
done = false; // There is a pending process
if (rem_bt[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_bt[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_bt[i];
// Waiting time is current time minus time
// used by this process
wt[i] = t - proc[i].bt;
// As the process gets fully executed
// make its remaining burst time = 0
rem_bt[i] = 0;
}
}
}
// If all processes are done
if (done == true)
break;
}
}
// Function to calculate turn around time
void findTurnAroundTimeRR(Process proc[], int n, int wt[], int tat[])
{
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n ; i++)
tat[i] = proc[i].bt + wt[i];
}
// Function to calculate average time
void findavgTimeRR(Process proc[], int n, int quantum)
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;
// Function to find waiting time of all processes
findWaitingTimeRR(proc, n, wt, quantum);
// Function to find turn around time for all processes
findTurnAroundTimeRR(proc, n, wt, tat);
// Display processes along with all details
cout << " Processes "<< " Burst time "
<< " Waiting time " << " Turn around time ";
// Calculate total waiting time and total turn
// around time
for (int i=0; i<n; i++)
{
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << i+1 << " " << proc[i].bt <<" "
<< wt[i] <<" " << tat[i] <<endl;
}
cout << " Average waiting time = "
<< (float)total_wt / (float)n;
cout << " Average turn around time = "
<< (float)total_tat / (float)n;
}
// Function to calculate Average response time
void findAverageResponseTime(Process proc[], int n)
{
int tat=0;
// calculating Average response time by adding
// bt[i] and dividd it by n
for (int i = 0; i < n ; i++)
tat += proc[i].bt ;
cout<< " Average response time = " << (tat/n) <<endl;
}
// Driver code
int main()
{
Process proc[] = { { 1, 6, 1 }, { 2, 8, 1 },
{ 3, 7, 2 }, { 4, 3, 3 } };
int n = sizeof(proc) / sizeof(proc[0]);
cout<<" Shortest Remaining Time First ";
findavgTimeSRTF(proc, n);
cout<<" Shortest Job First ";
// Sorting processes by burst time.
sort(proc, proc + n, comparisonSJF);
cout << " Order in which process gets executed ";
for (int i = 0 ; i < n; i++)
cout << proc[i].pid <<" ";
findavgTimeSJF(proc, n);
cout<<" First Come, First Served ";
findavgTimeFCFS(proc, n );
cout<<" Round Robin ";
// Time quantum
int quantum = 5;
findavgTimeRR(proc, n, quantum);
findAverageResponseTime(proc, n);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.