Shortest Job First SJF non preemptive scheduling program in C

Shortest Job First (SJF) is a CPU process Scheduling algorithm in which a process with the shortest burst time is executed first by the CPU and then processes with increasing order of burst times. But in systems, different processes arrive at different times to the CPU for execution. How processes with different arrival times are handled gives rise to two types of Shortest Job First algorithm – Preemptive and Non-Preemptive SJF. Here we are discussing Non-Preemptive Shortest Job First. In this, a process with shorter burst time is executed first, but it is also possible that a process P2 with a shorter burst time will have to wait for a process P1 with a longer burst time to finish executing. This happens because the process P2 has arrived after P1 and as such, P1 has started executing and P2 will have to wait until P1 has finished executing. This is the concept of Non-Preemptive Shortest Job First.

Shortest Job First non preemptive scheduling program in C++

/* ******************************
AUTHOR: EXPLORING BITS
****************************** */
#include <iostream>
#include <iomanip>

using namespace std;
int pMat[100][6], n;

void displayInitial(){
    cout << "\nInitial Data: \n\n";
    cout << "+-----+--------------+------------+\n";
    cout << "| PID | ARRIVAL TIME | BURST TIME |\n";
    cout << "+-----+--------------+------------+\n";
    for (int i = 0; i < n; i++){
        cout << "| " << setw(2) << pMat[i][0] << "  ";
        cout << "|      " << setw(2) << pMat[i][1] << "      ";
        cout << "|     " << setw(2) << pMat[i][2] << "     |\n";
        cout << "+-----+--------------+------------+\n";
    }
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void arrangeArrival()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n-i-1; j++)
        {
            if(pMat[j][1] > pMat[j+1][1])
            {
                for(int k = 0; k < 5; k++)
                {
                    swap(pMat[j][k], pMat[j+1][k]);
                }
            }
            if (pMat[j][1] == pMat[j+1][1]){
                if(pMat[j][2] > pMat[j+1][2])
                {
                    for(int k = 0; k < 5; k++)
                    {
                        swap(pMat[j][k], pMat[j+1][k]);
                    }
                }
            }
        }
    }
}

void finalArrange()
{
    int temp, val;
    pMat[0][3] = pMat[0][1] + pMat[0][2];
    pMat[0][5] = pMat[0][3] - pMat[0][1];
    pMat[0][4] = pMat[0][5] - pMat[0][2];

    for(int i = 1; i < n; i++)
    {
        temp = pMat[i-1][3];
        int low = pMat[i][2];
        for(int j = i; j < n; j++)
        {
            if(temp >= pMat[j][1] && low >= pMat[j][2])
            {
                low = pMat[j][2];
                val = j;
            }
        }
        pMat[val][3] = temp + pMat[val][2];
        pMat[val][5] = pMat[val][3] - pMat[val][1];
        pMat[val][4] = pMat[val][5] - pMat[val][2];
        for(int k = 0; k < 6; k++)
        {
            swap(pMat[val][k], pMat[i][k]);
        }
    }
}

void displayGanttChart(){
    cout << "\nGantt Chart: \n";
    cout << "\n+";
    for (int i = 0; i < n; i++){
        for (int j = 0; j < pMat[i][2]*4; j++){
            cout << "-";
        }
        cout << "+";
    }
    cout << "\n";
    for (int i = 0; i < n; i++){
        cout << "|";
        for (int j = 0; j < pMat[i][2]*2-1; j++){
            cout << " ";
        }
        cout << pMat[i][0];
        for (int j = 0; j < pMat[i][2]*2; j++){
            cout << " ";
        }
    }
    cout << "|";
    cout << "\n";
    cout << "+";
    for (int i = 0; i < n; i++){
        for (int j = 0; j < pMat[i][2]*4; j++){
            cout << "-";
        }
        cout << "+";
    }
    cout << "\n";
    cout << 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < pMat[i][2]*4-1; j++){
            cout << " ";
        }
        cout << setw(2) << pMat[i][3];
    }
    cout << "\n";
}

void displayFinal(){
    double wt = 0.0, tat = 0.0;
    cout << "\nFinal Result: \n\n";
    cout << "+-----+------------+--------------+-----------------+\n";
    cout << "| PID | BURST TIME | WAITING TIME | TURNAROUND TIME |\n";
    cout << "+-----+------------+--------------+-----------------+\n";
    for (int i = 0; i < n; i++){
        cout << "| " << setw(2) << pMat[i][0] << "  ";
        cout << "|     " << setw(2) << pMat[i][2] << "     ";
        cout << "|      " << setw(2) << pMat[i][4] << "      ";
        cout << "|       " << setw(2) << pMat[i][5] << "        |\n";
        cout << "+-----+------------+--------------+-----------------+\n";
        wt = wt + pMat[i][4];
        tat = tat + pMat[i][5];
    }
    cout << "\nTotal Waiting Time: " << wt << endl;
    cout << "Average Waiting Time: " << wt/n << endl;
    cout << "Total Turnaround Time: " << tat << endl;
    cout << "Average Turnaround Time: " << tat/n << endl;
}

int main(){
    cout << "Enter the number of processes: ";
    cin >> n;
    cout << "Enter the details of the processes: \n";
    for (int i = 0; i < n; i++){
        cout << "\nProcess " << i+1 << "...\n";
        cout << "Enter Process ID: ";
        cin >> pMat[i][0];
        cout << "Enter Arrival Time: ";
        cin >> pMat[i][1];
        cout << "Enter Burst Time: ";
        cin >> pMat[i][2];
    }
    displayInitial();
    arrangeArrival();
    finalArrange();
    displayGanttChart();
    displayFinal();
}

 

Output of SJF non preemptive scheduling program in C++

Output for Shortest Job First non preemptive scheduling program in C++

In the above program, main () function is responsible for entering all the required data to perform SJF operation on into the respective arrays. These arrays are kept global so any function can access them anytime. The displayGanttChart () function is used to print the Gantt Chart. The displayFinal () function prints the final table.

1 thought on “Shortest Job First SJF non preemptive scheduling program in C”

Leave a Comment