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 $1^{\text{st}}$ millisecond and task preemptions are allowed, the first instance of $T_3$ completes its execution at the end of _________ milliseconds.

We are given three periodic tasks under Rate Monotonic Scheduling (priority $\propto \frac{1}{\text{period}}$):

• Task $T_1$: Period $P_1 = 3\text{ ms}$, Execution time $C_1 = 1\text{ ms}$ (Highest Priority)

• Task $T_2$: Period $P_2 = 7\text{ ms}$, Execution time $C_2 = 2\text{ ms}$ (Medium Priority)

• Task $T_3$: Period $P_3 = 20\text{ ms}$, Execution time $C_3 = 4\text{ ms}$ (Lowest Priority)

All tasks arrive at $t = 0$.

Let us trace the execution timeline from $t = 0$:

1. $t = 0$ to $1$: $T_1$ (Instance 1) runs for $1\text{ ms}$ and finishes at $t = 1$.

2. $t = 1$ to $3$: $T_2$ (Instance 1) runs for $2\text{ ms}$ and finishes at $t = 3$.

3. $t = 3$ to $4$: $T_1$ (Instance 2 arrives at $t = 3$) preempts, runs for $1\text{ ms}$, and finishes at $t = 4$.

4. $t = 4$ to $6$: $T_3$ (Instance 1) runs for $2\text{ ms}$ ($2\text{ ms}$ remaining).

5. $t = 6$ to $7$: $T_1$ (Instance 3 arrives at $t = 6$) preempts, runs for $1\text{ ms}$, and finishes at $t = 7$.

6. $t = 7$ to $9$: $T_2$ (Instance 2 arrives at $t = 7$) runs for $2\text{ ms}$ and finishes at $t = 9$.

7. $t = 9$ to $10$: $T_1$ (Instance 4 arrives at $t = 9$) runs for $1\text{ ms}$ and finishes at $t = 10$.

8. $t = 10$ to $12$: $T_3$ (Instance 1) resumes and executes its remaining $2\text{ ms}$, finishing at $t = 12$.

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