GATE CS 2006 Q06 — CPU Scheduling

To find the number of context switches, we trace the execution of the processes using the Shortest Remaining Time First (SRTF) scheduling algorithm, which is a preemptive version of Shortest Job First (SJF).

Let the three processes be $P_1, P_2,$ and $P_3$ with their respective arrival times ($A_i$) and burst times ($B_i$):

• $P_1$: $A_1 = 0$, $B_1 = 10$
• $P_2$: $A_2 = 2$, $B_2 = 20$
• $P_3$: $A_3 = 6$, $B_3 = 30$

Execution Trace:

1. At $t = 0$: Only $P_1$ has arrived. $P_1$ starts execution.
   Remaining time: $P_1 = 10$.
2. At $t = 2$: $P_2$ arrives.
   Remaining times: $P_1 = 8$, $P_2 = 20$.
   Since $P_1$ has the shorter remaining time ($8 < 20$), $P_1$ continues execution. No context switch occurs.
3. At $t = 6$: $P_3$ arrives.
   Remaining times: $P_1 = 4$, $P_2 = 20$, $P_3 = 30$.
   Since $P_1$ still has the shortest remaining time ($4 < 20 < 30$), $P_1$ continues execution. No context switch occurs.
4. At $t = 10$: $P_1$ finishes execution.
   The scheduler selects the process with the shortest remaining time among the ready processes ($P_2$ and $P_3$).
   Since $P_2$ ($20$) is shorter than $P_3$ ($30$), $P_2$ is scheduled.
   Context Switch 1: $P_1 \to P_2$.
5. At $t = 30$: $P_2$ finishes execution.
   Only $P_3$ remains in the queue, so $P_3$ is scheduled.
   Context Switch 2: $P_2 \to P_3$.
6. At $t = 60$: $P_3$ finishes execution.

As specified, we do not count the context switches at time $t = 0$ (start) and at $t = 60$ (end). Therefore, the total number of context switches is 2.