Consider the set of processes with arrival time (in milliseconds), CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time. The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is _________.

We can trace the execution using a Gantt chart with preemptive priority scheduling (lower priority value means higher priority):

• At $t = 0$: $P_1$ arrives (priority 2) and starts execution.

• At $t = 2$: $P_4$ arrives (priority 1). Since priority $1 > 2$, $P_4$ preempts $P_1$. Remaining burst of $P_1 = 11 - 2 = 9$ ms.

• At $t = 5$: $P_2$ arrives (priority 0). Since priority $0 > 1$, $P_2$ preempts $P_4$. Remaining burst of $P_4 = 10 - 3 = 7$ ms.

• From $t = 5$ to $t = 33$: $P_2$ executes continuously until completion as it has the highest priority (0).

• At $t = 33$: The ready queue contains $P_4$ (remaining burst 7, priority 1), $P_1$ (remaining burst 9, priority 2), $P_3$ (burst 2, priority 3), and $P_5$ (burst 16, priority 4). $P_4$ has the highest priority, so it executes from $t = 33$ to $t = 40$.

• At $t = 40$: $P_1$ has the next highest priority (2), executing from $t = 40$ to $t = 49$.

• At $t = 49$: $P_3$ executes (priority 3) from $t = 49$ to $t = 51$.

• At $t = 51$: $P_5$ executes (priority 4) from $t = 51$ to $t = 67$.

Process Completion Times (CT), Turnaround Times (TAT = CT − AT), and Waiting Times (WT = TAT − BT):

• $P_1$: $\text{CT} = 49$, $\text{TAT} = 49 - 0 = 49$, $\text{WT} = 49 - 11 = 38$ ms

• $P_2$: $\text{CT} = 33$, $\text{TAT} = 33 - 5 = 28$, $\text{WT} = 28 - 28 = 0$ ms

• $P_3$: $\text{CT} = 51$, $\text{TAT} = 51 - 12 = 39$, $\text{WT} = 39 - 2 = 37$ ms

• $P_4$: $\text{CT} = 40$, $\text{TAT} = 40 - 2 = 38$, $\text{WT} = 38 - 10 = 28$ ms

• $P_5$: $\text{CT} = 67$, $\text{TAT} = 67 - 9 = 58$, $\text{WT} = 58 - 16 = 42$ ms