Question

Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below

Process	P1	P2	P3	P4
Arrival time	0	1	3	4
CPU burst time	3	1	3	Z

 

These processes are run on a single processor using preemptive Shortest Remaining Time First scheduling algorithm. If the average waiting time of the processes is 1 millisecond, then the value of Z is________.

Answer 1

Assume that: P4 < P3

Gantt chart:

P1

P2

P1

P1

P4

P3

0           1            2            3           4          4+Z        7+Z

Process Table1:

Process	Arrival Time (AT)	Burst Time (BT)	Completion time (CT)	Turnaround time TAT = CT - AT	Waiting time WT = TAT - BT
P1	0	3	4	4	1
P2	1	1	2	1	0
P3	3	3	7 + Z	4 + Z	1 + Z
P4	4	z	4 + Z	Z	0

 

Average waiting time = 1

\(\frac{{1 + 0 + \left( {1 + z} \right) + 0}}{4} = 1\)

The value of Z is 2.

Assume that: P4 ≥p3

Gantt chart:

P1

P2

P1

P1

P3

P4

0           1            2            3           4            7          7+Z

Process Table2:

Process	Arrival Time (AT)	Burst Time (BT)	Completion time (CT)	Turnaround time TAT = CT - AT	Waiting time WT = TAT - BT
P1	0	3	4	4	1
P2	1	1	2	1	0
P3	3	3	7	4	1
P4	4	Z	7 + Z	Z + 3	3

 

Given average waiting time = 1

\(But\;\frac{{1 + 0 + 1 + 3}}{4} \ne 1\)

\(\frac{5}{{4}} \ne 1\)

\(∴ p4 > p3\;is\;not\;possible\;\)

∴ Z = 2