Question

Part1: Write a program in Java to simulate CPU scheduling using (i) Shortest Job First (both preemptive and non-preemptive) and (ii)Priority scheduling Go through the related text and implement each of these CPU algorithms. Consider arrival time, CPU burst time and priority given for each of the processes. Show the results of different steps of your implementation. Part2: Draw the Gantt Chart and compute Average Waiting Time and Average Turn Around Time in each case

Answer 1

Shortest Job First Sheduling:

This is an approch which consider the next CPU burst.

Each process posses its next CPU burst when cpu is avaliable the process having smallest next. CPU burst is allocated CPU.

Now it may happen that two or more processes have the same next CPU burst.Then which process to allocate will be decided as per FCFS scheduling.

There are two schemas with this type of scheduling:

i. Non-pre-emptive: Once the CPU is allocated to the process it can be pre-empted until it

complets its CPU burst.

Working of non-pre-emptive SJF:

Consider the following set of processes and their respective CPU burst time.   

Process	Arrival Time	Burst Time
p1	0.0	7
p2	2.0	4
p3	4.0	1
p4	5.0	4

Initially at a time 0 ,only one process p1 is in ready queue.so we get scheduled and start execution .

As it non-pre-empted scheduling it will finish its CPU burst and then only terminate.

Now this time there are p2,p3,p4 processes are present in the ready queue After process p1 is finished ,next process is to be scheduled.

If FCFS would have been used process p2 was next one to be scheduled But in SJF the process having least CPU burst will be get scheduled i.e process p3 get scheduled.

After it get finished now there are two processes p2 and p4 having the same next burst time now to break this tie ,FCFS used

Process p2 has arrival time 2.0 and p4 has 5.0 so p2 has arrived first it will get scheduled first then after its completion ,p4 will get scheduled

After draw gannt chart.

To calculate waiting time for processes arriving at different time:  Start time- Arrival Time

waiting time of p1=(0-0)=0

waiting time of p2=(8-2)=6

waiting time of p3=(7-4)=3

waiting time of p4=(12-5)=7

Average Waiting Time:(0+6+3+7)/4=4

Finish time=Start time+Burst time

TurnAround time =Finish time-Arrival time

Average turnaround time =sum of turnaround time of all processes/n;

Non - Preemptive

import java.util.*;
class SJF
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n,BT[],WT[],TAT[], OUT[]; //BT=burst time WT=waitinng time,TAT=turn arount time OUT=otput
System.out.println("Enter no of process");
n=sc.nextInt();
BT=new int[n+1];
WT=new int[n+1];
TAT=new int[n+1];
OUT=new int[n+1];
float AWT=0;//Average Waiting time
float ATAT=0; // Average Total Turn around time

System.out.println("Enter Burst time for each process");
for(int i=0;i<n;i++)
{
System.out.println("Enter BT for process "+(i+1));
BT[i]=sc.nextInt();
OUT[i]=i+1;
}

for(int i=0;i<n;i++)
{
WT[i]=0; TAT[i]=0;
}
int temp;
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-1;j++)
{
if(BT[j]>BT[j+1])
{
temp=BT[j];
BT[j]=BT[j+1];
BT[j+1]=temp;
temp=OUT[j];
OUT[j]=OUT[j+1];
OUT[j+1]=temp;
}
}
}

for(int i=0;i<n;i++)
{
TAT[i]=BT[i]+WT[i];
WT[i+1]=TAT[i];
}
TAT[n]=WT[n]+BT[n];

for(int j=0;j<n;j++) {
TAT[j]=WT[j]+BT[j];
AWT+=WT[j];
}



System.out.println(" PROCESS BT WT TAT ");
for(int i=0;i<n;i++)
System.out.println(" "+ OUT[i] + " "+BT[i]+" "+WT[i]+" "+TAT[i]);

AWT=AWT/n;
System.out.println("***********************************************");
System.out.println("Avg waiting time="+AWT+"\n***********************************************");

for(int i=0;i<n;i++)
{
TAT[i]=WT[i]+BT[i];
ATAT=ATAT+TAT[i];
}

ATAT=ATAT/n;
System.out.println("***********************************************");
System.out.println("Avg turn around time="+ATAT+"\n***********************************************");
}
}


/* O/P for Shortest job first(sjf) scheduling algorithm is :
Enter no of process
3
Enter Burst time for each process
Enter BT for process 1
24
Enter BT for process 2
3
Enter BT for process 3
3
PROCESS BT WT TAT   
2 3 0 3
3 3 3 6
1 24 6 30
***********************************************
Avg waiting time=3.0
***********************************************
***********************************************
Avg turn around time=13.0
***********************************************
BUILD SUCCESSFUL (total time: 8 seconds)

ii. pre-emptive:

Consider the following set of processes and their respective CPU burst time.   

Process	Arrival Time	Burst Time
p1	0.0	7
p2	2.0	4
p3	4.0	1
p4	5.0	4

Initially at a time 0 ,only one process p1 is in ready queue.so we get scheduled and start execution .

Then at 2.0 millisecond process p2 arrives by by this time process p1 has completed its 2 units and remaining time is 5 and the burst time for newly arrived process is 4 which is less than the currently scheduled process p1 so process p1 is pre-empted and process p2 is scheduled

process p2 is executing after more 2 millisecond its remaining time is 2 millisecond and at this time process p3 is arrive with burst time 1 which is less than current process p2 so p2 is pre-empted and process p3 is scheduled.

now at a time 5 process p4 arrives by this time process p3 is finished its CPU burst so CPU is free.

The remaining processes are

process	Arrival Time	Burst Time
p1	0.0	5
p2	2.0	2
p4	5.0	4

Now the smallest next burst time among the processes is 2 pf process p2,so it get scheduled All 2 units of it will be finished and then among processes p1 and p4 smallest next burst time scheduled and then after its completion process p1 is scheduled

Draw the gant chart

After To calculating times for the pre-emptive processes

waiting time of process = (Strat time-Arrival Time)-(New start time- Old finish time )

Waiting time of p1=(0-0)-(11-2)=9

Waiting time of p2=(2-2)-(5-4)=1

Waiting time of p3=(4-4)=0 p3 has got scheduled and finished and not scheduled for second time.

Waiting time of p4=(7-5)=0 p34has got scheduled and finished and not scheduled for second time.

So Average waiting time (9+1+0+2)/4=3

Finish time=Start time+Burst time

TurnAround time =Finish time-Arrival time

Average turnaround time =sum of turnaround time of all processes/n;

class Process {     int pid; // Process ID     int bt; // Burst Time     int art; // Arrival Time           public Process(int pid, int bt, int art)     {         this.pid = pid;         this.bt = bt;         this.art = art;     } } public class GFG {     // Method to find the waiting time for all     // processes     static void findWaitingTime(Process proc[], int n,                                      int wt[])     {         int rt[] = new int[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 = Integer.MAX_VALUE;         int shortest = 0, finish_time;         boolean 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 = Integer.MAX_VALUE;                    // If a process gets completely             // executed             if (rt[shortest] == 0) {                        // Increment complete                 complete++;                 check = false;                        // 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++;         }     }            // Method to calculate turn around time     static 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];     }            // Method to calculate average time     static void findavgTime(Process proc[], int n)     {         int wt[] = new int[n], tat[] = new int[n];         int 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         System.out.println("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];             System.out.println(" " + proc[i].pid + "\t\t"                              + proc[i].bt + "\t\t " + wt[i]                              + "\t\t" + tat[i]);         }                System.out.println("Average waiting time = " +                           (float)total_wt / (float)n);         System.out.println("Average turn around time = " +                            (float)total_tat / (float)n);     }           // Driver Method     public static void main(String[] args)     {          Process proc[] = { new Process(1, 6, 1),                             new Process(2, 8, 1),                             new Process(3, 7, 2),                             new Process(4, 3, 3)};                    findavgTime(proc, proc.length); Output:      Processes Burst time Waiting time Turn around time 1 6 3 9 2 8 16 24 3 7 8 15 4 3 0 3 Average waiting time = 6.75 Average turn around time = 12.75

Priority Scheduling:

In this type of scheduling prority is assigned to every process and CPU is alloacated to the process having highst prority priorities can be defined in Internally and exsternally,

Working of non-pre-emptive sheduling:

Steps to solve the example:

i. Calculate start time of each depending on the arrival time and the burst time of each process

ii.Create Gantt chart as follows:

a. Select the process whose arrival time is 0 if two or more processes have arrival time 0 then select the process having higher priority.

b.Keep the selecting the processes having hightest prority among the remaining processes and add those to gannt chart in case two or more processes have the same busrt time then process having arrival time is less selected

iii. Calculate wait time using following formula:

Wait time= Start time-Arrival time

Average Wait time= (sum of wait time of all processes )/n

iv.Calculate Finish time for all the processes

v.Calculate turnaround time for all proceses

Turnaround time = Finish time -Arrival time

Average turnaround time=   (sum ofTurnaround time of all processes )/n

import java.util.*; class Process {     int at, bt, pri, pno;     Process(int pno, int at, int bt, int pri)     {         this.pno = pno;         this.pri = pri;         this.at = at;         this.bt = bt;     } } /// Gantt chart structure class GChart {     // process number, start time, complete time,     // turn around time, waiting time     int pno, stime, ctime, wtime, ttime; } // user define comparative method (first arrival first serve, // if arrival time same then heigh priority first) class MyComparator implements Comparator {     public int compare(Object o1, Object o2)     {         Process p1 = (Process)o1;         Process p2 = (Process)o2;         if (p1.at < p2.at)             return (-1);         else if (p1.at == p2.at && p1.pri > p2.pri)             return (-1);         else             return (1);     } } // class to find Gantt chart class FindGantChart {     void findGc(LinkedList queue)     {         // initial time = 0         int time = 0;         // priority Queue sort data according         // to arrival time or priority (ready queue)         TreeSet prique = new TreeSet(new MyComparator());         // link list for store processes data         LinkedList result = new LinkedList();         // process in ready queue from new state queue         while (queue.size() > 0)             prique.add((Process)queue.removeFirst());         Iterator it = prique.iterator();         // time set to according to first process         time = ((Process)prique.first()).at;         // scheduling process         while (it.hasNext()) {             // dispatcher dispatch the             // process ready to running state             Process obj = (Process)it.next();             GChart gc1 = new GChart();             gc1.pno = obj.pno;             gc1.stime = time;             time += obj.bt;             gc1.ctime = time;             gc1.ttime = gc1.ctime - obj.at;             gc1.wtime = gc1.ttime - obj.bt;             /// store the exxtreted process             result.add(gc1);         }         // create object of output class and call method         new ResultOutput(result);     } }

pre-emptive priority scheduling:

Steps to solve the Example:

i. Calculate start time of each depending on the arrival time and the burst time of each process

ii.Create Gantt chart as follows:

a. Select the process whose arrival time is 0 if two or more processes have arrival time 0 then select the process having higher priority.

b.At every time interval keep on checking new process has arrived while previously process is running campare the priority of both processes if newly arrived process priority is greater than currently running process preempt the process and schedule new process.

c.keep selecting process having maximum priority and add those to gannt chart in case two or more processes have the same priority then the process having less time selected .

iii. Calculate wait time using following formula:

Wait time= (Start time-Arrival time)+(New time-old finish time )

Average Wait time= (sum of wait time of all processes )/n

iv.Calculate Finish time for all the processes

v.Calculate turnaround time for all proceses

Turnaround time = Finish time -Arrival time

Average turnaround time=   (sum ofTurnaround time of all processes )/n

import java.util.Scanner;
 
public class priority{
        
    public static void main(String args[]) {
            Scanner s = new Scanner(System.in);
 
            int x,n,p[],pp[],bt[],w[],t[],awt,atat,i;
 
            p = new int[10];
            pp = new int[10];
            bt = new int[10];
            w = new int[10];
            t = new int[10];
 
   //n is number of process
   //p is process
   //pp is process priority
   //bt is process burst time
   //w is wait time
   // t is turnaround time
   //awt is average waiting time
   //atat is average turnaround time
 
 
   System.out.print("Enter the number of process : ");
   n = s.nextInt();
    System.out.print("\n\t Enter burst time : time priorities \n");
 
   for(i=0;i<n;i++)
    {
       System.out.print("\nProcess["+(i+1)+"]:");
      bt[i] = s.nextInt();
      pp[i] = s.nextInt();
      p[i]=i+1;
    }
 
//sorting on the basis of priority
  for(i=0;i<n-1;i++)
   {
     for(int j=i+1;j<n;j++)
     {
       if(pp[i]>pp[j])
       {
     x=pp[i];
     pp[i]=pp[j];
     pp[j]=x;
     x=bt[i];
     bt[i]=bt[j];
     bt[j]=x;
     x=p[i];
     p[i]=p[j];
     p[j]=x;
      }
   }
}
w[0]=0;
awt=0;
t[0]=bt[0];
atat=t[0];
for(i=1;i<n;i++)
 {
   w[i]=t[i-1];
   awt+=w[i];
   t[i]=w[i]+bt[i];
   atat+=t[i];
 }
 
//Displaying the process
 
  System.out.print("\n\nProcess \t Burst Time \t Wait Time \t Turn Around Time   Priority \n");
for(i=0;i<n;i++)
  System.out.print("\n   "+p[i]+"\t\t   "+bt[i]+"\t\t     "+w[i]+"\t\t     "+t[i]+"\t\t     "+pp[i]+"\n");
awt/=n;
atat/=n;
  System.out.print("\n Average Wait Time : "+awt);
  System.out.print("\n Average Turn Around Time : "+atat);
 
        }
}


/*******OUTPUT********

Enter the number of process : 5

  Enter burst time : time priorities 

Process[1]:7 2

Process[2]:6 4

Process[3]:4 1

Process[4]:5 3

Process[5]:1 0


Process   Burst Time   Wait Time   Turn Around Time   Priority 

   5     1       0       1       0

   3     4       1       5       1

   1     7       5       12       2

   4     5       12       17       3

   2     6       17       23       4

 Average Wait Time : 7
 Average Turn Around Time : 11