GATE CS 2024 Set 2 Q27 — CPU Scheduling

We can find the average waiting times by simulating both scheduling algorithms using Gantt charts.

At any scheduling point, the process with the shortest remaining CPU burst time is executed:

• At $t = 0$: Only $\text{A}$ is available (remaining burst = 10). $\text{A}$ runs.
• At $t = 2$: $\text{B}$ arrives (burst = 6). Remaining burst of $\text{A}$ is 8. Since $6 < 8$, $\text{B}$ preempts $\text{A}$.
• At $t = 4$: $\text{C}$ arrives (burst = 3). Remaining burst of $\text{B}$ is 4. Since $3 < 4$, $\text{C}$ preempts $\text{B}$.
• At $t = 6$: $\text{D}$ arrives (burst = 7). Remaining burst of $\text{C}$ is 1. Since $1$ is the shortest, $\text{C}$ continues.
• At $t = 7$: $\text{C}$ finishes. Remaining bursts: $\text{B}(4), \text{D}(7), \text{A}(8)$. $\text{B}$ runs.
• At $t = 11$: $\text{B}$ finishes. Remaining bursts: $\text{D}(7), \text{A}(8)$. $\text{D}$ runs.
• At $t = 18$: $\text{D}$ finishes. $\text{A}$ runs.
• At $t = 26$: $\text{A}$ finishes.

SRTF Gantt Chart:

Waiting Time (WT = Completion Time - Arrival Time - Burst Time):

• $\text{WT(A)} = 26 - 0 - 10 = 16$
• $\text{WT(B)} = 11 - 2 - 6 = 3$
• $\text{WT(C)} = 7 - 4 - 3 = 0$
• $\text{WT(D)} = 18 - 6 - 7 = 5$

$$\text{Average WT (SRTF)} = \frac{16 + 3 + 0 + 5}{4} = \frac{24}{4} = 6$$

Processes run to completion without preemption. At each completion point, the available process with the shortest burst time is selected:

• At $t = 0$: Only $\text{A}$ is available. $\text{A}$ runs to completion (0 to 10).
• At $t = 10$: $\text{B}(6), \text{C}(3),$ and $\text{D}(7)$ have all arrived. $\text{C}$ has the shortest burst. $\text{C}$ runs (10 to 13).
• At $t = 13$: $\text{B}(6)$ and $\text{D}(7)$ are available. $\text{B}$ runs (13 to 19).
• At $t = 19$: $\text{D}$ runs (19 to 26).

NP-SJF Gantt Chart:

Waiting Time (WT = Start Time - Arrival Time):

• $\text{WT(A)} = 0 - 0 = 0$
• $\text{WT(C)} = 10 - 4 = 6$
• $\text{WT(B)} = 13 - 2 = 11$
• $\text{WT(D)} = 19 - 6 = 13$

$$\text{Average WT (NP-SJF)} = \frac{0 + 6 + 11 + 13}{4} = \frac{30}{4} = 7.5$$