Consider a uniprocessor system executing three tasks T1, T2 and T3, each of…
2015
Consider a uniprocessor system executing three tasks T1, T2 and T3, 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 T1, T2 and T3 requires an execution time of 1, 2 and 4 milliseconds, respectively. Given that all tasks initially arrive at the beginning of the 1st milliseconds and task preemptions are allowed, the first instance of T3 completes its execution at the end of ______________ milliseconds.
Attempted by 126 students.
Show answer & explanation
Correct answer: 12
Key idea: task priority is the inverse of period, so T1 has highest priority (period 3 ms), then T2 (7 ms), then T3 (20 ms). All first instances arrive at time 0. Execution times: T1 = 1 ms, T2 = 2 ms, T3 = 4 ms.
Time 0–1 ms: T1 runs (highest priority) and completes its 1 ms execution.
Time 1–3 ms: T2 runs (next highest) and completes its 2 ms execution by time 3 ms.
At time 3 ms: a new instance of T1 arrives and runs 3–4 ms, completing its instance.
Time 4–6 ms: T3 can run (lower priority), so it executes 2 ms of its 4 ms, leaving 2 ms remaining at time 6 ms.
At time 6 ms: a new T1 instance arrives and runs 6–7 ms (1 ms).
Time 7–9 ms: T2 (whose next instance arrived at 7 ms) runs for 2 ms and completes at 9 ms.
At time 9 ms: a new T1 instance arrives and runs 9–10 ms (preempting lower priority tasks).
Time 10–12 ms: the remaining 2 ms of T3 execute and complete at the end of 12 ms.
Conclusion: the first instance of T3 completes at the end of 12 milliseconds.
A video solution is available for this question — log in and enroll to watch it.