GATE CS 2021 Set 1 Q25 — CPU Scheduling

To minimize the average waiting time of a set of processes, the optimal scheduling algorithm is Shortest Job First (SJF).

We are given three processes arriving at time $t = 0$ with the following CPU burst times:

• $P_1$: $16\text{ ms}$
• $P_2$: $20\text{ ms}$
• $P_3$: $10\text{ ms}$

Sorting these processes in ascending order of their burst times (SJF order):

$$\text{Execution Order: } P_3 \to P_1 \to P_2$$

Gantt Chart:

The execution timeline is as follows:

$$\begin{array}{|c|c|c|} \hline \quad P_3 \quad & \quad P_1 \quad & \quad P_2 \quad \\ \hline 0 \quad\quad\quad 10 & \quad\quad\quad\quad 26 & \quad\quad\quad\quad\quad 46 \\ \hline \end{array}$$

Waiting Time Calculation:

Since all processes arrive at time $t = 0$, the waiting time for each process is simply its start time:

• Waiting time of $P_3 = 0\text{ ms}$
• Waiting time of $P_1 = 10\text{ ms}$
• Waiting time of $P_2 = 26\text{ ms}$

$$\text{Average Waiting Time} = \frac{0 + 10 + 26}{3} = \frac{36}{3} = 12\text{ ms}$$