Question

Project objective: To learn more about OS scheduling through a hands-on simulation programming experience

Implement the following 3 CPU scheduling algorithms

• Simulate and evaluate each with the set of eight processes below.
• Use any programming language. The program listing should be submitted with the report.

1. FCFS non-preemptive (partial results provided)
2. SJF non-preemptive
3. MLFQ

Multilevel Feedback Queue (absolute priority in higher queues)

            Queue 1 uses RR scheduling with Tq = 5

            Queue 2 uses RR scheduling with Tq = 10

            Queue 3 uses FCFS

All processes enter first queue 1. If time quantum (Tq) expires before CPU burst is complete, the process is downgraded to next lower priority queue. Processes are not downgraded when preempted by a higher queue level process. Once a process has been downgraded, it will not be upgraded.

Assumptions:

1. All processes are activated at time 0
2. Assume that no process waits on I/O devices.
3. After completing an I/O event, a process is transferred to the ready queue.
4. Waiting time is accumulated while a process waits in the ready queue.
5. Turnaround time is a total of (Waiting time) + (CPU burst time) + (I/O time)
6. Response time is the first measure of waiting time from arrival at time 0 until the first time on the CPU.

Process Data:

process goes {CPU burst, I/O time, CPU burst, I/O time, CPU burst, I/O time,…….., last CPU burst}

P1 {5, 27, 3, 31, 5, 43, 4, 18, 6, 22, 4, 26, 3, 24, 4}

P2 {4, 48, 5, 44, 7, 42, 12, 37, 9, 76, 4, 41, 9, 31, 7, 43, 8}

P3 {8, 33, 12, 41, 18, 65, 14, 21, 4, 61, 15, 18, 14, 26, 5, 31, 6}

P4 {3, 35, 4, 41, 5, 45, 3, 51, 4, 61, 5, 54, 6, 82, 5, 77, 3}

P5 {16, 24, 17, 21, 5, 36, 16, 26, 7, 31, 13, 28, 11, 21, 6, 13, 3, 11, 4}

P6 {11, 22, 4, 8, 5, 10, 6, 12, 7, 14, 9, 18, 12, 24, 15, 30, 8}

P7 {14, 46, 17, 41, 11, 42, 15, 21, 4, 32, 7, 19, 16, 33, 10}

P8 {4, 14, 5, 33, 6, 51, 14, 73, 16, 87, 6}

PLEASE CODE IN C++ FOR ALL 3

Answer 1

C++ code for 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 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 findavgTime( 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\n";     // 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 << "\t\t" << bt[i] <<"\t    "             << wt[i] <<"\t\t " << tat[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[] = {10, 5, 8};     findavgTime(processes, n, burst_time);     return 0; }

C++ code for SJF:

// C++ program to implement Shortest Job first with Arrival Time
#include<iostream>
using namespace std;
void swap(int *a, int *b) {
   int temp = *a;
   *a = *b;
   *b = temp;
}
void arrangeArrival(int num, int mat[][3]) {
   for(int i=0; i<num; i++) {
      for(int j=0; j<num-i-1; j++) {
         if(mat[1][j] > mat[1][j+1]) {
            for(int k=0; k<5; k++) {
               swap(mat[k][j], mat[k][j+1]);
            }
         }
      }
   }
}
void completionTime(int num, int mat[][3]) {
   int temp, val;
   mat[3][0] = mat[1][0] + mat[2][0];
   mat[5][0] = mat[3][0] - mat[1][0];
   mat[4][0] = mat[5][0] - mat[2][0];
    for(int i=1; i<num; i++) {
      temp = mat[3][i-1];
      int low = mat[2][i];
      for(int j=i; j<num; j++) {
         if(temp >= mat[1][j] && low >= mat[2][j]) {
            low = mat[2][j];
            val = j;
         }
      }
      mat[3][val] = temp + mat[2][val];
      mat[5][val] = mat[3][val] - mat[1][val];
      mat[4][val] = mat[5][val] - mat[2][val];
      for(int k=0; k<6; k++) {
         swap(mat[k][val], mat[k][i]);
      }
   }
}
int main() {
   int num = 3, temp;
   int mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4};
   cout<<"Before Arrange...\n";
   cout<<"Process ID\tArrival Time\tBurst Time\n";
   for(int i=0; i<num; i++) {
      cout<<mat[0][i]<<"\t\t"<<mat[1][i]<<"\t\t"<<mat[2][i]<<"\n";
   }
   arrangeArrival(num, mat);
   completionTime(num, mat);
   cout<<"Final Result...\n";
   cout<<"Process ID\tArrival Time\tBurst Time\tWaiting Time\tTurnaround Time\n";
   for(int i=0; i<num; i++) {
      cout<<mat[0][i]<<"\t\t"<<mat[1][i]<<"\t\t"<<mat[2][i]<<"\t\t"<<mat[4][i]<<"\t\t"<<mat[5][i]<<"\n";
   }
}

C++ code for MLFQ:

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

struct Process_Data
{
        int Num;
        int Pid;  //Process Id
        int A_time; //Process Arrival Time
        int B_time; //Process Bruest Time
        int Priority; //Process Priority
        int F_time; //Process Finish Time
        int R_time; //Process Remaining  Time During Execution
        int W_time; //Waiting Time
        int S_time; //Process start Time
        int Res_time;

};

struct Process_Data current;
typedef struct Process_Data P_d ;

bool idsort(const P_d& x , const P_d& y)
{
        return x.Pid < y.Pid;
}
/** Sorting on the base of arrival time if that match then on Priority of Priority also  match than on the base of Process Id**/
bool arrivalsort( const P_d& x ,const P_d& y)
{
        if(x.A_time < y.A_time)
                return true;
        else if(x.A_time > y.A_time)
                return false;
        if(x.Priority < y.Priority)
                return true;
        else if(x.Priority > y.Priority)
                return false;
        if(x.Pid < y.Pid)
                return true;

        return false;
}


bool Numsort( const P_d& x ,const P_d& y)
{
        return x.Num < y.Num;
}
/*Sorting on the base of Priority if that same then on the base of PID*/
struct comPare
{
        bool operator()(const P_d& x ,const P_d& y)
        {
                if( x.Priority > y.Priority )
                        return true;
                else if( x.Priority < y.Priority )
                        return false;
                if( x.Pid > y.Pid )
                        return true;

                return false;
                
        }
        
};

/**To check the Input **/
void my_check(vector<P_d> mv)
{
        for(unsigned int i= 0; i < mv.size() ;i++)
        {
                cout<<" Pid :"<<mv[i].Pid<<" _time : "<<mv[i].A_time<<" B_time : "<<mv[i].B_time<<" Priority : "<<mv[i].Priority<<endl;
        }

}

int main()
{
        int i;
        vector< P_d > input;
        vector<P_d> input_copy;
        P_d temp;
        int pq_process = 0; // for PQ process
        int rq_process = 0; // for RQ process
        int A_time;
        int B_time;
        int Pid;
        int Priority;
        int n;
        int clock;
        int total_exection_time = 0;
        cin>>n;
        for( i= 0; i< n; i++ )
        {
                cin>>Pid>>A_time>>B_time>>Priority;
                temp.Num = i+1;
                temp.A_time = A_time;
                temp.B_time = B_time;
                temp.R_time = B_time;
                temp.Pid = Pid;
                temp.Priority = Priority;
                input.push_back(temp);
        }
        input_copy = input;
        sort( input.begin(), input.end(), arrivalsort );
    //cout<<"arrivalsort : "<<endl;
    //my_check( input ); // To check the sort unomment it
    total_exection_time = total_exection_time + input[0].A_time;
    for( i= 0 ;i< n; i++ )
    {
        if( total_exection_time >= input[i].A_time )
        {
                total_exection_time = total_exection_time +input[i].B_time;
        }
        else
        {
                int diff = (input[i].A_time - total_exection_time);
                total_exection_time = total_exection_time + diff + B_time;

        }
    }

        int Ghant[total_exection_time]={0}; //Ghant Chart
        for( i= 0; i< total_exection_time; i++ )
        {
                Ghant[i]=-1;
        }
        //cout<<"total_exection_time : "<<total_exection_time<<endl;

        priority_queue < P_d ,vector<Process_Data> ,comPare> pq; //Priority Queue PQ

        queue< P_d > rq; //Round Robin Queue RQ
        int cpu_state = 0; //idle if 0 then Idle if 1 the Busy
        int quantum = 4 ; //Time Quantum
        current.Pid = -2;
        current.Priority = 999999;

        for ( clock = 0; clock< total_exection_time; clock++ )
        {
                /**Insert the process with same Arrival time in Priority Queue**/
                for( int j = 0; j< n ; j++ )
                {
                        if(clock == input[j].A_time)
                        {
                                pq.push(input[j]);
                        }
                }
                

                if(cpu_state == 0) //If CPU idle
                {
                        if(!pq.empty())
                        {
                                current = pq.top();
                                cpu_state = 1;
                                pq_process = 1;
                                pq.pop();
                                quantum = 4; 
                        }
                        else if(!rq.empty())
                        {
                                current = rq.front();
                                cpu_state = 1;
                                rq_process = 1;
                                rq.pop();
                                quantum = 4;
                        }
                }
                else if(cpu_state == 1) //If cpu has any procss
                {
                        if(pq_process == 1 && (!pq.empty()))
                        {
                                if(pq.top().Priority < current.Priority ) //If new process has high priority
                                {
                                        rq.push(current); //push current in RQ
                                        current = pq.top();
                                        pq.pop();
                                        quantum = 4; 
                                }
                        }
                        else if(rq_process == 1 && (!pq.empty())) //If process is from RQ and new process come  in PQ
                        {
                                rq.push(current);
                                current = pq.top();
                                pq.pop();
                                rq_process = 0;
                                pq_process = 1;
                                quantum = 4 ;
                        }
                        

                }


                if(current.Pid != -2) // Process Execution
                {
                        current.R_time--;
                        quantum--;
                        Ghant[clock] = current.Pid;
                        if(current.R_time == 0) //If process Finish
                        {
                                cpu_state = 0 ;
                                quantum = 4 ;
                                current.Pid = -2;
                                current.Priority = 999999;
                                rq_process = 0;
                                pq_process = 0;
                        }
                        else if(quantum == 0 ) //If time Qunatum of a current running process Finish
                        {
                                rq.push(current);
                                current.Pid = -2;
                                current.Priority = 999999;
                                rq_process = 0;
                                pq_process = 0;
                                cpu_state=0;

                        }

                }
                
        }


        sort( input.begin(), input.end(), idsort );
        
        for(int i=0;i<n;i++)
        {
                for(int k=total_exection_time;k>=0;k--)
                {
                        if(Ghant[k]==i+1)
                        {
                                input[i].F_time=k+1;
                                break;

                        }
                }
        }
        for(int i=0;i<n;i++)
        {
                for(int k=0;k<total_exection_time;k++)
                {

                        if(Ghant[k]==i+1)
                        {
                                input[i].S_time=k;
                                break;
                        }
                }
        }
        
        sort( input.begin(), input.end(), Numsort );

        for(int i=0;i<n;i++)
        {
                input[i].Res_time=input[i].S_time-input[i].A_time;
                input[i].W_time=(input[i].F_time-input[i].A_time)-input[i].B_time;

        }
        
        for(int i=0;i<n;i++)
        {
                cout<<input[i].Pid<<" "<<input[i].Res_time<<" "<<input[i].F_time<<" "<<input[i].W_time<<endl;
                
        }       
        return 0;
}