GATE CS 2017 Set 2 Q51 — CPU Scheduling

We use the preemptive priority scheduling algorithm where $0$ represents the highest priority. Let's trace the execution of the processes chronologically:

• At $t = 0$: Only $P_1$ (Priority 2) is available. It starts execution.
• At $t = 2$: $P_4$ (Priority 1) arrives. Since $P_4$ has a higher priority than $P_1$, $P_1$ is preempted.
  Remaining burst of $P_1 = 9$.
• At $t = 5$: $P_2$ (Priority 0) arrives. Since $P_2$ has the highest priority, it preempts $P_4$.
  Remaining burst of $P_4 = 7$.
• At $t = 5$ to $33$: $P_2$ runs to completion because it has the highest possible priority ($0$). It finishes at $t = 33$.
• At $t = 33$: Among the ready processes ($P_1, P_3, P_4, P_5$), $P_4$ (Priority 1) is executed next. It finishes at $t = 33 + 7 = 40$.
• At $t = 40$: Among the remaining processes ($P_1, P_3, P_5$), $P_1$ (Priority 2) is executed. It finishes at $t = 40 + 9 = 49$.
• At $t = 49$: Between $P_3$ (Priority 3) and $P_5$ (Priority 4), $P_3$ is executed. It finishes at $t = 49 + 2 = 51$.
• At $t = 51$: $P_5$ is executed. It finishes at $t = 51 + 16 = 67$.

We can now construct the scheduling table to find the waiting time ($\text{WT} = \text{Completion Time} - \text{Arrival Time} - \text{Burst Time}$):

The average waiting time is calculated as: