Project ForgeConsider a uniprocessor system executing three tasks T1, T2 and T3, each composed of an infinite sequence of periodic jobs that arrive at intervals of 3, 7, and 20 milliseconds respectively. Priority is the inverse of period (rate-monotonic), so T1 has the highest priority, then T2, then T3; the highest-priority ready task is always scheduled, with preemption allowed. Each instance of T1, T2, T3 needs 1, 2, and 4 milliseconds of execution respectively. All three tasks' first instances arrive together at time 0. At what time does the first instance of T3 complete its execution?
- A6 ms
- B10 ms
- 12 ms
- D16 ms
Explanation
Trace by priority (T1 > T2 > T3), all preemptible: [0,1) T1 runs (its only ready job). [1,3) T2 runs (2ms, finishes exactly at 3). [3,4) T1's new instance (arrived at t=3) preempts and runs. [4,6) no T1/T2 due yet (T2 next at t=7), so T3 runs, completing 2 of its needed 4ms. [6,7) T1's next instance (t=6) preempts, runs. [7,9) T2's next instance (t=7) preempts, runs 2ms. [9,10) T1's next instance (t=9) preempts, runs. [10,12) T3 resumes and finishes its remaining 2ms — completing at t=12.
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.