Question

Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

Process	burst Time	Priority
P1	10	3
P2	1	1
P3	2	3
P4	1	4
P5	5	2

For each of the scheduling algorithms, FCFS, Shortest-Job-First (SJF, non-preemptive), Priority (smaller priority number implies higher scheduling priority), and RR (quantum = 1) do the following.

1. Draw a Gantt chart to show how these processes would be scheduled.

2. Give the turnaround time (total time from the first arrival into ready state until CPU-burst is completed) of each process.

3. Give the waiting time (total time spent in the Ready state) of each process.

4. Give the average waiting time of all the processes.

Which of these scheduling algorithm gives the smallest average waiting time?

Answer 1

Answer: a. Gantt charts

(The processes are assumed to have arrived in the order 
P1, P2, P3, P4, P5, all at time 0.)

a. The four Gantt charts are


  _______________________________________________________
  |           P1            | P2|  P3  |P4 |     P5      | FCFS
  |_________________________|___|______|___|_____________|
  0                        10  11     13  14            19
  _______________________________________________________
  |P2| P4|  P3  |      P5     |            P1            | SJF
  |__|___|______|_____________|__________________________|
  0  1   2      4             9                         19

There is a tie between the priorities of P1 and P3. If P1 is scheduled 
first:
  _______________________________________________________
  |P2|      P5      |           P1            |  P3  | P4| Priority13
  |__|______________|_________________________|______|___|
  0  1              6                        16     18  19

or if for the tie between P1 and P3 priorities, P3 is scheduled first:

  _______________________________________________________
  |P2|      P5      |  P3  |           P1            | P4| Priority31
  |__|______________|______|_________________________|___|
  0  1              6      8                        18  19

  ____________________________________________________________________
  |P1| P2| P3| P4| P5| P1| P3| P5| P1| P5| P1| P5| P1| P5|     P1     |RR
  |__|___|___|___|___|___|___|___|___|___|___|___|___|___|____________|
  0  1   2   3   4   5   6   7   8   9  10  11  12  13  14           19

Answer: b. Turnaround Times

b. The turnaround time of each process for each of the
scheduling algorithms in part a:

Turnaround_time = Finish_time - Arrival_time 

        FCFS   SJF     Priority1  Priority3  RR
P1      10     19      16         18         19
P2      11      1       1          1          2
P3      13      4      18          8          7
P4      14      2      19         19          4
P5      19      9       6          6         14

Answer: c. Waiting Times

c. The waiting time of each process for each of the scheduling
algorithms in part a:

Waiting time (turnaround time minus burst time) =
	Finish_time - Arrival_time - Burst_time

        FCFS    SJF     Priority13 Priority31 RR     
P1       0       9        6          8        9     
P2      10       0        0          0        1     
P3      11       2       16          6        5     
P4      13       1       18         18        3     
P5      14       4        1          1        9

Answer: d. Smallest Average Waiting Time

d. The schedule in part that results in the minimal average
waiting time (over all processes):


	           FCFS     SJF    Priority1  Priority3  RR     
Ave. wait      	    9.6     3.2      8.2        6.6      5.4 

So the answer is Shortest Job First.