Thursday 26 November 2015

Shortest Job First [SJF] Process Scheduling Program with Gantt Chart

Another type of process scheduling algorithm is the Shortest Job First [SJF] process scheduling algorithm, In SJF the CPU is allocated to the process which has the smallest CPU burst time out of all the processes and so on. If two or more than two processes share the same CPU burst time then First Come First Serve [FCFS] scheduling is used to solve the conflict between those processes.

SJF scheduling can be done in both ways,
  • Nonpreemptive -
    In Nonpreemptive SJF scheduling algorithm, Once the CPU has been allocated to a process It cannot jump from current process to another. Firstly it must completely finish the execution of the current process then only it can be allocated to some other processes.
  • Preemptive -
    In Preemptive SJF, Even if the CPU is allocated to a process say "A", It can jump from "A" to some other process "B" if the CPU burst time of "B" is smaller than that of the process "A".
Shortest Job First [SJF] process scheduling algorithm is much more Optimal and gives the Minimum Average Waiting Time as compared to FCFS and other process scheduling algorithms. Because executing a smaller process before the larger one decreases the waiting time for smaller process much more than it increases the waiting time of larger process. Hence, the average waiting time decreases.
In this article we will be only sharing Nonpreemptive SJF program.

Shortest Job First Process Scheduling Program

Below is the program for SJF process scheduling with Gantt Chart in C,

//This is a Program for Shortest Job First Process Scheduling by [C] Lectures.
#include<stdio.h>
#include<graphics.h>
#include<dos.h>
#include<conio.h>
void main()
{
    int no,i,j,sum=0,position,temp,temp1=0,temp2=0,temp_tat=0,temp_wt=0;
    int cpuburst[10],process[10],avg_waiting_time=0,avg_turnaround_time=0;
    int gdriver = DETECT, gmode;
    initgraph(&gdriver,&gmode,"C:\\TC\\BGI ");
    clrscr();
    printf("\nShortest Job First Process Scheduling : ");
    printf("\nEnter the number of Processes : ");
    scanf("%d",&no);
    for(i=1;i<=no;i++)
    {
        process[i]=i;
        printf("\nEnter CPU Burst time for process P%d : ",i);
        scanf("%d",&cpuburst[i]);
    }
    cpuburst[0]=0;
    for(i=1;i<=no;i++)
    {
        position=i;
        for(j=i+1;j<=no;j++)
        {
            if(cpuburst[j]<cpuburst[position])
                position=j;
        }
        temp=cpuburst[i];
        cpuburst[i]=cpuburst[position];
        cpuburst[position]=temp;
        temp=process[i];
        process[i]=process[position];
        process[position]=temp;
    }
    for(i=1;i<=no;i++)
    {
        sum += cpuburst[i];
        avg_waiting_time += cpuburst[i-1];
        avg_turnaround_time += cpuburst[i];
        temp_wt=0;
        temp_tat=0;
        for(j=1;j<i;j++)
        {
            temp_tat += cpuburst[j];
            temp_wt += cpuburst[j-1];
        }
        printf("\nWaiting time for process P%d : %d",process[i],cpuburst[i-1]+temp_wt);
        printf("\nTurn around time for process P%d : %d \n",process[i],cpuburst[i]+temp_tat);
        avg_turnaround_time += temp_tat;
        avg_waiting_time += temp_wt;
    }
    printf("\n\nAverage waiting time : %d",avg_waiting_time/no);
    printf("\nAverage turn around time : %d",avg_turnaround_time/no);
    outtextxy(80,460,"Do Not Press Any Key! This screen will be cleared automatically in 10s.");
    delay(10000);
    cleardevice();
    line(100,100,100,150);
    line(100,100,100+(sum*10),100);
    line(100+(sum*10),100,100+(sum*10),150);
    line(100,150,100+(sum*10),150);
    for(i=1;i<no;i++)
    {
        temp1 = cpuburst[i];
        temp2 += temp1;
        line(100+(temp2*10),100,100+(temp2*10),150);
    }
    getch();
    closegraph();
}

Output of the Program

There will be two output screens for our program, In first screen we will give our inputs to the program and it will print out the waiting time & turn around time for all the process individually and also the average waiting time and average turnaround time of the processes. And in the second output screen we will get the Gantt chart of our inputs.

Shortest Job First [SJF] process scheduling algorithm is Optimal and gives the Minimum Average Waiting Time. In this article we will be sharing SJF process scheduling program in C/C++ programming language.
Shortest Job First [SJF] process scheduling algorithm is Optimal and gives the Minimum Average Waiting Time. In this article we will be sharing SJF process scheduling program with Gantt chart in C/C++ programming language.

Now let us check the validity of our program to see if the output calculated by our program is same as the manually calculated output,
Suppose there are 4 processes P1, P2, P3 and P4.
Assuming that all the four process arrived at 0ms, So the Arrival time for all the process is 0ms.

The CPU burst time for process P1 is 9ms,
The CPU burst time for process P2 is 3ms,
The CPU burst time for process P3 is 6ms,
The CPU burst time for process P4 is 5ms.

As the CPU burst time of process P2 is smaller than that of all the other processes, the CPU will be allocated to P2. Hence, the Waiting time for process P2 will be 0ms

After the process P2 has been completely executed then the CPU will be allocated to the next smallest process P4 which has CPU burst time of 5ms. Hence, the Waiting time for process P4 will be 3ms

After executing process P2 and P4 the CPU will be then allocated to the next smallest process P3 which has the CPU burst time of 6ms. Hence, the Waiting time for process P3 will be equals to 3ms + 5ms = 8ms

Now at last the CPU will be allocated to process P1 which has the largest CPU burst time of all the other process. The Waiting time for process P1 will be 3ms + 5ms + 6ms = 14ms

The Average Waiting Time = (0ms + 3ms + 8ms + 14ms)/4 = 6ms

Now for Turn around time, As we know that the process P2 has the smallest CPU burst time i.e 3ms so the CPU will be allocated to process P2. Hence, the Turn around time for P2 = 3ms

After the process P2 as been executed completely, the CPU will be then allocated to process P4 which has the CPU burst time of 5ms. So, the Turn around time for process P4 = 3ms + 5ms = 8ms

Now the CPU will be allocated to process P3 as it has the smallest CPU burst time i.e 6ms as compared to P1. So, the Turn around time for P3 = 3ms + 5ms + 6ms = 14ms

At last the CPU will be allocated to process P1 which has the largest CPU burst time of all the process i.e 9ms. So, the Turn around time for process P1 = 3ms + 5ms + 6ms + 9ms = 23ms

The Average Turn Around Time = (3ms + 8ms + 14ms + 23ms)/4 = 12ms

Download Source Code from Here.

Tuesday 24 November 2015

First Come First Serve [FCFS] Process Scheduling Program with Gantt Chart

First Come First Serve [FCFS] process scheduling is the simplest type of process scheduling algorithm. FCFS can be easily implemented using the First In First Out [FIFO] queue, arriving jobs are inserted in the tail of ready queue and process to be executed next is removed from the head of the queue.

FCFS scheduling is Nonpreemptive type of scheduling i.e CPU can not jump from one process to another before it's completion. Once the CPU is allocated to a process, that process keeps the CPU until it is executed completely and only then after CPU can be allocated to another process.

In General, the average waiting time for FCFS algorithm is often quite long. The average waiting time for FCFS algorithm may vary depending upon the CPU burst times of the processes.

First Come First Serve Process Scheduling Program 


Below is the program for FCFS process scheduling with Gantt chart in c,

//This is a program for First Come First Serve Process Scheduling by [C] Lectures.
#include<stdio.h>
#include<graphics.h>
#include<conio.h>
void main()
{
    int temp1=0,temp2=0,i,j,no,temp_tat,temp_wt,sum=0;
    int cpuburst[10],avg_waiting_time=0,avg_turnaround_time=0;
    int gdriver = DETECT, gmode;
    initgraph(&gdriver,&gmode,"C:\\TC\\BGI ");
    clrscr();
    printf("\nFirst Come First Serve Process Scheduling : \n");
    printf("\nEnter number of processes : ");
    scanf("%d",&no);
    for(i=1;i<=no;i++)
    {
        printf("\nEnter CPU burst for process P%d : ",i);
        scanf("%d",&cpuburst[i]);
    }
    cpuburst[0]=0;
    for(i=1;i<=no;i++)
    {
        sum += cpuburst[i];
        avg_waiting_time += cpuburst[i-1];
        avg_turnaround_time += cpuburst[i];
        temp_wt=0;
        temp_tat=0;
        for(j=1;j<i;j++)
        {
            temp_tat += cpuburst[j];
            temp_wt += cpuburst[j-1];
        }
        printf("\nWaiting time for process P%d : %d",i,cpuburst[i-1]+temp_wt);
        printf("\nTurn around time for process P%d : %d \n",i,cpuburst[i]+temp_tat);
        avg_turnaround_time += temp_tat;
        avg_waiting_time += temp_wt;
    }
    printf("\n\nAverage waiting time : %d",avg_waiting_time/no);
    printf("\nAverage turn around time : %d",avg_turnaround_time/no);
    outtextxy(80,460,"Do Not Press Any Key! This screen will be cleared automatically in 10s.");
    delay(10000);
    cleardevice();
    line(100,100,100,150);
    line(100,100,100+(sum*15),100);
    line(100+(sum*15),100,100+(sum*15),150);
    line(100,150,100+(sum*15),150);
    for(i=1;i<no;i++)
    {
        temp1 = cpuburst[i];
        temp2 += temp1;
        line(100+(temp2*15),100,100+(temp2*15),150);
    }
    getch();
    closegraph();
}

Output of the Program


There will be two output screens for our program, In first screen we will give our inputs to the program and it will print out the waiting time & turn around time for all the process individually and also the average waiting time and average turnaround time of the processes. And in the second output screen we will get the Gantt chart of our inputs.

First Come First Serve [FCFS] is simplest, nonpreemptive type of process scheduling algorithm & can be implemented using First In First Out [FIFO] queue and can be represented using Gantt chart.
First Come First Serve [FCFS] is simplest, nonpreemptive type of process scheduling algorithm & can be implemented using First In First Out [FIFO] queue and can be represented using Gantt chart.

Now let us check the validity of our program to see if the output calculated by our program is same as the manually calculated output,
Suppose there are 4 processes P1, P2, P3 and P4.
Assuming that all the four process arrived at 0ms, So the Arrival time for all the process is 0ms.

The CPU burst time for process P1 is 7ms,
The CPU burst time for process P2 is 9ms,
The CPU burst time for process P3 is 3ms,
The CPU burst time for process P4 is 5ms.

Now, the waiting time for process P1 will be 0ms because P1 arrived at 0ms and didn't have to wait for any other processes to execute first. So, Waiting time for process P1 = 0ms

The waiting time for process P2 will be 7ms because P2 have to wait for process P1 to complete its execution then only CPU will be allocated to P2. So, Waiting time for process P2 = 7ms

The waiting time for process P3 will be 7ms + 9ms because P3 will have to wait for both process P1 and P2 to complete their execution then only the CPU will be allocated to process P3. So, Waiting time for process P3 = 16ms

The waiting time for process P4 will be 7ms + 9ms + 3ms because P3 will have to wait for process P1, P2 and P3 to complete their execution then only the CPU will be allocated to process P4. So, Waiting time for process P4 = 19ms

The Average Waiting time = (0ms + 7ms + 16ms + 19ms)/4 = 10ms

Now, the turn around time for process P1 will be 7ms because P1 arrived at 0ms and didn't have to wait for any other processes to execute first and completed its execution at 7ms. So, Turn around time for process P1 = 7ms

The turn around time for process P2 will be 7ms + 9ms because P2 arrived at 0ms and had to wait for process P1 to execute first. So, Turn around time for process P2 = 16ms

The turn around time for process P3 will be 7ms + 9ms + 3ms because P3 arrived at 0ms and had to wait for process P1 and P2 to execute first. So, Turn around time for P3 = 19ms

The turn around time for process P4 will be 7ms + 9ms + 3ms + 5ms because P4 arrived at 0ms and had to wait for process P1, P2 and P3 to complete their execution first. So, Turn around time for P4 = 24ms

The Average Turn Around Time = (7ms + 16ms + 19ms + 24ms)/4 = 16ms

Download Source code from Here.