Question

in C++

We are going to implement the following scheduling algorithms

1. First-Come First-Served (FCFS)

2. Shortest Remaining Time First (SRTF)

3. Highest Response Ratio Next (HRRN)

4. Round Robin, with di_erent 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

The simulator needs to generate a list of processes. For each process, 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 (hence exponential inter-arrival times). The service times are generated according to an exponential

distribution. We will vary _ to simulate di_erent loads while keeping the average service time _xed. The

simulator should stop after processing 10,000 processes to completion (without stopping the arrival process),

then it should output the statistics (i.e., the metrics above).

Events (e.g., process arrival, process completion, time-slice) that occur causes the simulator to update its

current state (e.g., cpu busy/idle, number of processes in the ready queue, etc.) To keep track and process

events in the right order, we keep events in a priority queue (called \Event Queue") that describes the future

events and is kept sorted by the time of each event. The simulator keeps a clock the represents the current

time which takes the time of the _rst event in the Event Queue. Notice that when an event is processed

at its assigned time, one or more future events may be added to the Event Queue. For example, when a

process gets serviced by the CPU, another process can start executing (if one is waiting in the ready queue)

and under FCFS, we know exactly when this process would _nish (since FCFS is non-preeptive), so we can

schedule a departure event in the future and place it in the event queue. Notice that time hops between

events, so you would need to update your simulator clock accordingly.

The simulator should take few command-line arguments. The _rst 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.

Each scheduler would need to maintain a queue (the \Process Ready Queue") for the ready processes

that are waiting for the CPU. A scheduler will select a process to run next based on the scheduling policy.

Clearly, this queue should not be confused with the Event Queue that is used to hold events to be processed

in the future.

3 The Runs

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.

For each value of _, we need to compare the performance of each scheduler, based on the metrics above.

It is recommended (but not required) that you write a simple batch _le that would run those experiments

and put the results in a _le (that you can later import into a spread sheet and plot the values).

#!/bin/bash

rm sim.data

for ((i = 10; i < 31; i++)); do

./sim 1 $i 0.04 0.01

cp sim.data /data/1-$i-004.data

done

This will run the simulator using FCFS (indicated by the value 1 in the _rst argument) for 20 di_erent

values of _ using 0.04 as the average service time and a quantum value of 0.01 (which is ignored in all

algorithms, except round robin). Then, the script will move the sim.data _le to a safe place.

With the Round Robin algorithm, an argument is supplied to indicate the quantum used. Use 2 di_erent

values of quantum; 0.01 and 0.2. If a process _nishes before its quantum expires, the CPU will schedule the

next process right away.

Answer 1

1) FCFS

#include <iostream>
#include <algorithm> 
#include <iomanip> 
using namespace std;

struct process {
    int pid;
    int arrival_time;
    int burst_time;
    int start_time;
    int completion_time;
    int turnaround_time;
    int waiting_time;
    int response_time;
};

bool compareArrival(process p1, process p2) 
{ 
    return p1.arrival_time < p2.arrival_time;
}

bool compareID(process p1, process p2) 
{  
    return p1.pid < p2.pid;
}

int main() {

    int n;
    struct process p[100];
    float avg_turnaround_time;
    float avg_waiting_time;
    float avg_response_time;
    float cpu_utilisation;
    int total_turnaround_time = 0;
    int total_waiting_time = 0;
    int total_response_time = 0;
    int total_idle_time = 0;
    float throughput;

    cout << setprecision(2) << fixed;

    cout<<"Enter the number of processes: ";
    cin>>n;

    for(int i = 0; i < n; i++) {
        cout<<"Enter arrival time of process "<<i+1<<": ";
        cin>>p[i].arrival_time;
        cout<<"Enter burst time of process "<<i+1<<": ";
        cin>>p[i].burst_time;
        p[i].pid = i+1;
        cout<<endl;
    }

    sort(p,p+n,compareArrival);

    for(int i = 0; i < n; i++) {
        p[i].start_time = (i == 0)?p[i].arrival_time:max(p[i-1].completion_time,p[i].arrival_time);
        p[i].completion_time = p[i].start_time + p[i].burst_time;
        p[i].turnaround_time = p[i].completion_time - p[i].arrival_time;
        p[i].waiting_time = p[i].turnaround_time - p[i].burst_time;
        p[i].response_time = p[i].start_time - p[i].arrival_time;

        total_turnaround_time += p[i].turnaround_time;
        total_waiting_time += p[i].waiting_time;
        total_response_time += p[i].response_time;
        total_idle_time += (i == 0)?(p[i].arrival_time):(p[i].start_time - p[i-1].completion_time);
    }

    avg_turnaround_time = (float) total_turnaround_time / n;
    avg_waiting_time = (float) total_waiting_time / n;
    avg_response_time = (float) total_response_time / n;
    cpu_utilisation = ((p[n-1].completion_time - total_idle_time) / (float) p[n-1].completion_time)*100;
    throughput = float(n) / (p[n-1].completion_time - p[0].arrival_time);

    sort(p,p+n,compareID);

    cout<<endl;
    cout<<"#P\t"<<"AT\t"<<"BT\t"<<"ST\t"<<"CT\t"<<"TAT\t"<<"WT\t"<<"RT\t"<<"\n"<<endl;

    for(int i = 0; i < n; i++) {
        cout<<p[i].pid<<"\t"<<p[i].arrival_time<<"\t"<<p[i].burst_time<<"\t"<<p[i].start_time<<"\t"<<p[i].completion_time<<"\t"<<p[i].turnaround_time<<"\t"<<p[i].waiting_time<<"\t"<<p[i].response_time<<"\t"<<"\n"<<endl;
    }
    cout<<"Average Turnaround Time = "<<avg_turnaround_time<<endl;
    cout<<"Average Waiting Time = "<<avg_waiting_time<<endl;
    cout<<"Average Response Time = "<<avg_response_time<<endl;
    cout<<"CPU Utilization = "<<cpu_utilisation<<"%"<<endl;
    cout<<"Throughput = "<<throughput<<" process/unit time"<<endl;


}