GATE CS 2015 Set 1 Q46 — CPU Scheduling

The priority of each task is inversely proportional to its period. Thus, the priority order (from highest to lowest) is:

$$\text{Priority}(T_1) > \text{Priority}(T_2) > \text{Priority}(T_3)$$

The task parameters are:

• $T_1$: Period $P_1 = 3$ ms, Execution time $C_1 = 1$ ms
• $T_2$: Period $P_2 = 7$ ms, Execution time $C_2 = 2$ ms
• $T_3$: Period $P_3 = 20$ ms, Execution time $C_3 = 4$ ms

Tracing the execution timeline from $t = 0$:

1. [0 to 1 ms]: $T_1$ (1st instance) runs and completes.
2. [1 to 3 ms]: $T_2$ (1st instance) runs and completes.
3. [3 to 4 ms]: $T_1$ (2nd instance) arrives at $t = 3$, preempts other tasks, runs, and completes.
4. [4 to 6 ms]: $T_3$ (1st instance) runs for $2$ ms (requires $2$ ms more).
5. [6 to 7 ms]: $T_1$ (3rd instance) arrives at $t = 6$, preempts $T_3$, runs, and completes.
6. [7 to 9 ms]: $T_2$ (2nd instance) arrives at $t = 7$, preempts $T_3$, runs, and completes.
7. [9 to 10 ms]: $T_1$ (4th instance) arrives at $t = 9$, preempts $T_3$, runs, and completes.
8. [10 to 12 ms]: $T_3$ resumes and runs for its remaining $2$ ms, completing at $t = 12$ ms.

Thus, the first instance of $T_3$ completes its execution at the end of 12 milliseconds.