Question

Urgent!!

What is the waiting time and Turnaround time of each process for each of the scheduling algorithms? [12 Marks] Job Arrival Time Burst(msec) Priority A 0 6 3 (Silver) B 1 2 1 (Diamond) C 3 5 3 (Silver) D 5 3 4 (Bronze) E 7 2 2 (Gold) (a) First-Come-First-Served (FCFS) scheduling [2 Marks] (b) Preemptive PRIORITY scheduling [2 Marks] (c) Highest Response Ratio Next (HRRN) scheduling [2 Marks] (d) Round Robin (RR) (quantum = 4) scheduling [2 Marks] (e) Which of the foregoing scheduling policies provides the lowest waiting time for this set of jobs? What is the waiting time with this policy? (Show your work) [4 Marks]

Answer 1

Waiting Time(WT): The time process spent in the ready queue and for I/O completion.It is also considered as the Time Difference between turn around time and burst time.
Waiting Time = Turn Around Time – Burst Time

TurnAroundTime(TAT): The time since the process entered into ready queue for execution till the process completed it’s execution.It is also considered as Time Difference between completion time and arrival time.
Turn Around Time = Completion Time – Arrival Time

a)FCFS :

Process	Arrival Time	Burst Time	Completion Time(CT)	Turn Around Time(TAT)	Waiting Time(WT)
A	0	6	6	0	6
B	1	2	8	6	2
C	3	5	13	8	5
D	5	3	16	13	3
E	7	2	18	16	2

Waiting Time = Turn Around Time – Burst Time

   Turn Around Time = Completion Time – Arrival Time

In FCFS the first arrived process will have the first priority. So, the Gantt Chart is as follows:

Gantt Chart:

A

B

C

D

E

0 6 8 13 16 18

AverageTurn Around Time =   = 8.6 milli sec

Average Waiting Time = = 3.6 milli sec

b) Priority Scheduling (Pre-emptive):

Process	Arrival Time	Burst Time	Priority	Completion Time(CT)	Turn Around Time(TAT)	Waiting Time(WT)
A	0	6	3	10	10	0
B	1	2	1(L)	3	2	1
C	3	5	3	15	12	3
D	5	3	4(H)	18	13	5
E	7	2	2	9	2	7

      Waiting Time = Turn Around Time – Burst Time

Turn Around Time = Completion Time – Arrival Time

Here the lowest priority numbered process will have the highest priority i.e.., B is having the priority 1(L) which have the highest priority out of all and D having the priority 4(H) will have the lowest priority.

Gantt Chart:

Since no other process is available hence this will be scheduled till next job arrives or its completion (whichever is lesser).

A

0 1

• At time 1, B arrives. The priority of B is higher to A.
• Hence the execution of A will be stopped and B will be scheduled on the CPU.

A

B

0 1 3

• B has completed its execution and no other process is available at this time hence the Operating system has to schedule it regardless of the priority assigned to it.
• The Next process C arrives at time unit 3. During the execution of B, one more processes A becomes available. Out of A and C the priorities of both are same. So, by considering the arrival time A starts scheduling.

A

B

A

0 1 3 7

• At time 5, D arrives and At 7 E arrives. Now A,C,D and E becomes available.
• Out of all E is having the highest priority. So, A stops excution and E starts scheduling.

A

B

A

E

0 1 3 7 9

• During the execution of E, three more processes A, C and D becomes available.
• E will complete its execution and then A will be scheduled with the priority highest among the available processes.

A

B

A

E

A

0 1 3 7 9 10

• At time 10, A complete its execution.During the execution of A, two process becomes C and D becomes available. C having the highest priority executes first and then D.

A

B

A

E

A

C

D

0 1    3   7 9    10 15 18

Average TAT =   = 7.8 milli sec

Average WT =       = 3.2 milli sec

C) Highest Response Ratio Next (HRRN) scheduling:

Response Ratio (RR) for any process is calculated by using the formula

   Response Ratio (RR) =

Process	Arrival Time	Burst Time	Completion Time(CT)	Turn Around Time(TAT)	Waiting Time(WT)
A	0	6	6	6	0
B	1	2	8	7	1
C	3	5	13	10	3
D	5	3	18	13	5
E	7	2	15	8	7

• At t = 0, only the process A is available in the ready queue.
• So, process A executes till its completion.

A

0 6

• At t = 6, the processes B,C and D are available in the ready queue.
• The process having the highest response ratio will be executed next.

The response ratio are-

• Response Ratio for process B = [(6-1) + 2] / 2 = 7 / 2 = 3.5
• Response Ratio for process C = [(6-3) + 5] / 5 = 8 / 5 = 1.6
• Response Ratio for process D = [(6-5) + 3] / 3 = 4 / 3 = 1.33

Since process B has the highest response ratio, so process B executes till completion.

A

B

0 6 8

• At t = 8, the processes C, D and E are available in the ready queue.
• The process having the highest response ratio will be executed next.

The response ratio are-

• Response Ratio for process C = [(8-3) + 5] / 5 = 10 / 5 = 2
• Response Ratio for process D = [(8-5) + 3] / 3 = 6 / 3 = 2
• Response Ratio for process E = [(8-7) + 2] / 2 = 3 / 2 = 1.5

Since process C and D have the same response ratio.

• In case of a tie, it is broken by FCFS Scheduling.
• so process C executes till completion.

A

B

C

0    6    8 13

• At t = 13, the processes D and E are available in the ready queue.
• The process having the highest response ratio will be executed next.

The response ratio are-

• Response Ratio for process D = [(13-5) + 3] / 3 = 11 / 3 = 3.67
• Response Ratio for process E = [(13-7) + 2] / 2 =  8 / 2 = 4

Since process E has the highest response ratio, so process E executes till completion.After that D executes till completion.

A

B

C

E

D

0   6    8     13     15    18

Avg TAT = = 8.8 milli sec

Average WT =       = 3.2 milli sec

D) Round Robin (RR):

Process	Arrival Time	Burst Time	Completion Time(CT)	Turn Around Time(TAT)	Waiting Time(WT)
A	0	6	12	12	0
B	1	2	6	5	1
C	3	5	18	15	3
D	5	3	15	10	5
E	7	2	17	10	7

CPU scheduling policy is Round Robin with time quantum = 4 unit

Gantt chart:

A

B

C

A

D

E

C

0 4 6 10 12 15 17 18

Ready queue:

A

B

C

A

D

E

C

Avg TAT =    = 10.4 milli sec

Average WT =       = 3.2 milli sec

E) Out of foregoing scheduling policies Priority scheduling, Highest Response Ratio Next (HRRN) scheduling and Round Robin Scheduling provides the lowest waiting time for this set of jobs with 3.2 milli secs. The entire work is attached while solving each policy.