GATE CS 2015 Set 1 Q.56 (CS Q.46): CPU Scheduling

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.

Your answer

Official answer and solution

Official answer: 12
From: Official GATE 2015 answer key

Solution

Trace rate-monotonic scheduling cycle-by-cycle using static priorities assigned inversely to task periods.

Task parameters and priorities:
- Task $T_1$ : period $P_1 = 3\text{ ms}$ , computation time $C_1 = 1\text{ ms}$ . Priority: Highest.
- Task $T_2$ : period $P_2 = 7\text{ ms}$ , computation time $C_2 = 2\text{ ms}$ . Priority: Medium.
- Task $T_3$ : period $P_3 = 20\text{ ms}$ , computation time $C_3 = 4\text{ ms}$ . Priority: Lowest.
  All three tasks arrive at $t = 0\text{ ms}$ .
Execution timeline:
- Time $[0, 1]$ : $T_1$ runs for $1\text{ ms}$ and completes its first instance. (Remaining: $T_2$ needs $2\text{ ms}$ , $T_3$ needs $4\text{ ms}$ .)
- Time $[1, 3]$ : $T_2$ runs for $2\text{ ms}$ and completes its first instance. (Remaining: $T_3$ needs $4\text{ ms}$ .)
- At $t = 3$ : $T_1$ arrives (instance 2). Priority $T_1 > T_3$ .
- Time $[3, 4]$ : $T_1$ runs for $1\text{ ms}$ and completes instance 2.
- Time $[4, 6]$ : $T_3$ runs for $2\text{ ms}$ . ( $T_3$ has $2\text{ ms}$ execution remaining.)
- At $t = 6$ : $T_1$ arrives (instance 3). Preempts $T_3$ .
- Time $[6, 7]$ : $T_1$ runs for $1\text{ ms}$ and completes instance 3.
- At $t = 7$ : $T_2$ arrives (instance 2). Priority $T_2 > T_3$ .
- Time $[7, 9]$ : $T_2$ runs for $2\text{ ms}$ and completes instance 2.
- At $t = 9$ : $T_1$ arrives (instance 4). Priority $T_1 > T_3$ .
- Time $[9, 10]$ : $T_1$ runs for $1\text{ ms}$ and completes instance 4.
- At $t = 10$ : No higher priority tasks are pending. Next arrival is $T_1$ at $t = 12$ .
- Time $[10, 12]$ : $T_3$ resumes and executes its remaining $2\text{ ms}$ , finishing at $t = 12\text{ ms}$ .

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

Final answer

Common trap

Forgetting the preemption by T2 at t = 7 ms when tracing the timeline.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 1
Question: 56 of 65, printed as CS Q.46
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source