OPERATION SYSTEM CONCEPTS Uniprocessor Scheduling Write a program to simulate FC
ID: 3741969 • Letter: O
Question
OPERATION SYSTEM CONCEPTS
Uniprocessor Scheduling
Write a program to simulate FCFS, RR (q=1), SPN, and SRT. Run at 1,000 simulations. Each simulation needs to include 20 processes which require a randomly determined amount of execution time in the range of [1,10]. The each job becomes available at the time of twice its index (i.e., job 0 is available at time 0, job 17 is available at time 34).
Draw a conclusion as to which of these scheduling algorithms are best under these circumstances
Relative Turnaround Time
13.4411
Note: use the slide bar to see the complete table. Write the program in C++
Process 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Arrival Time 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 Service Time 6 9 9 9 2 4 9 6 7 9 5 2 9 1 7 4 10 3 9 7 FCFS Finish Time 6 15 24 33 35 39 48 54 61 70 75 77 86 87 94 98 108 111 120 127 Turnaround Time 6 14 22 30 31 34 42 47 53 61 65 66 74 74 80 83 92 94 102 108 58.9 Relative Turnaround Time 1 1.555556 2.444444 3.333333 15.5 8.5 4.666667 7.833333 7.571429 6.777778 13 33 8.222222 74 11.42857 20.75 9.2 31.33333 11.33333 15.42857 14.34393 Process 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Arrival Time 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 Service Time 6 1 6 1 4 5 9 2 10 8 4 3 3 3 4 9 5 6 6 3 FCFS Finish Time 6 7 13 14 18 23 32 34 44 52 56 59 62 65 69 78 83 89 95 98 Turnaround Time 6 6 11 11 14 18 26 27 36 43 46 48 50 52 55 63 67 72 77 79 40.35 Relative Turnaround Time 1 6 1.833333 11 3.5 3.6 2.888889 13.5 3.6 5.375 11.5 16 16.66667 17.33333 13.75 7 13.4 12 12.83333 26.33333 9.955694 Process 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Arrival Time 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 Service Time 5 10 3 10 4 2 10 10 4 10 4 8 5 4 1 8 3 6 7 9 FCFS Finish Time 5 16 19 29 33 35 45 55 59 69 73 81 86 90 91 99 102 108 115 124 Turnaround Time 5 15 17 26 29 30 39 48 51 60 63 70 74 77 77 84 86 91 97 105 57.2 Relative Turnaround Time 1 1.5 5.666667 2.6 7.25 15 3.9 4.8 12.75 6 15.75 8.75 14.8 19.25 77 10.5 28.66667 15.16667 13.85714 11.66667 13.79369 Process 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Arrival Time 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 Service Time 5 7 7 6 2 7 3 10 1 10 3 8 7 6 8 2 4 10 1 7 FCFS Finish Time 5 13 20 26 28 35 38 48 49 59 62 70 77 83 91 93 97 107 108 115 Turnaround Time 5 12 18 23 24 30 32 41 41 50 52 59 65 70 77 78 81 90 90 96 51.7 Relative Turnaround Time 1 1.714286 2.571429 3.833333 12 4.285714 10.66667 4.1 41 5 17.33333 7.375 9.285714 11.66667 9.625 39 20.25 9 90 13.71429 15.67107 Report Turnaround Time 52.0375Relative Turnaround Time
13.4411
Explanation / Answer
// C++ program for implementation of FCFS
// scheduling
#include<iostream>
#include<cstdlib>
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 findWaitingTime(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 findTurnAroundTime(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 SRT(Process proc[], int n)
{
int wt[n], tat[n], total_wt = 0,
total_tat = 0;
// Function to find waiting time of all
// processes
findWaitingTime(proc, n, wt);
// Function to find turn around time for
// all processes
findTurnAroundTime(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;
}
// Function to find the waiting time for all
// processes
void findWaitingTime(int processes[], int n,
int bt[], int wt[])
{
// waiting time for first process is 0
wt[0] = 0;
// calculating waiting time
for (int i = 1; i < n ; i++ )
wt[i] = bt[i-1] + wt[i-1] ;
}
// Function to calculate turn around time
void findTurnAroundTime( int processes[], int n,
int bt[], int wt[], int tat[])
{
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n ; i++)
tat[i] = bt[i] + wt[i];
}
//Function to calculate average time
void FCFS( int processes[], int n, int bt[])
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;
//Function to find waiting time of all processes
findWaitingTime(processes, n, bt, wt);
//Function to find turn around time for all processes
findTurnAroundTime(processes, n, bt, 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 << " " << bt[i] <<" "
<< wt[i] <<" " << tat[i] <<endl;
}
cout << "Average waiting time = "
<< (float)total_wt / (float)n;
cout << " Average turn around time = "
<< (float)total_tat / (float)n;
}
int main()
{
//process id's
int *processes,i,j;
Process *proc;
proc=new Process[1000];
processes=new int[1000];
for(i=0;i<1000;i++)
{
proc[i].pid=i;
proc[i].art=rand()%100;
}
int n = 1000;
//Burst time of all processes
int *burst_time;
burst_time=new int[1000];
for(i=0;i<1000;i++)
{
for(j=0;j<1000;j++)
{
burst_time[j]=rand()%50+1;
proc[i].bt=burst_time[j];
}
cout<<" FCFS: ";
FCFS(processes, n, burst_time);
cout<<" SRT: ";
SRT(proc,n);
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.