GATE 2015 CS (CS1) – Question 52
Consider a uniprocessor system executing three tasks $T_1$, $T_2$ and $T_3$, each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 milliseconds, respectively. The priority of each task is the inverse of its period, and the available tasks are scheduled in order of priority, with the highest priority task scheduled first. Each instance of $T_1$, $T_2$ and $T_3$ requires an execution time of 1, 2 and 4 milliseconds, respectively. Given that all tasks initially arrive at the beginning of the 1st millisecond and task preemptions are allowed, the first instance of $T_3$ completes its execution at the end of ________ milliseconds.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 12
Explanation
Rate-monotonic priorities: the shorter the period, the higher the priority, so $T_1$ (period 3) $>$ $T_2$ (period 7) $>$ $T_3$ (period 20). Execution times: $T_1=1$, $T_2=2$, $T_3=4$. All jobs arrive at $t=0$; preemption is allowed. New jobs of $T_1$ arrive at $t=0,3,6,9,\dots$ and of $T_2$ at $t=0,7,14,\dots$.
| Time | Runs | Why |
|---|---|---|
| 0–1 | $T_1$ | highest priority |
| 1–3 | $T_2$ | $T_1$ finished, $T_2$ next |
| 3–4 | $T_1$ | new $T_1$ job arrives at 3 |
| 4–6 | $T_3$ | runs 2 of its 4 ms |
| 6–7 | $T_1$ | new $T_1$ job at 6 preempts $T_3$ |
| 7–9 | $T_2$ | new $T_2$ job at 7 (higher than $T_3$) |
| 9–10 | $T_1$ | new $T_1$ job at 9 |
| 10–12 | $T_3$ | runs its remaining 2 ms |
$T_3$ has received $2+2=4$ ms, so it finishes at the end of **12** ms.