edited by
37,563 views
105 votes
105 votes
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, which is 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.
edited by

14 Answers

Best answer
115 votes
115 votes

Answer is 12

$T_1,T_2$ and $T_3$ have infinite instances, meaning infinite burst times. Here, problem say Run "$T_1$ for $1$ ms", "$T_2$ for $2$ ms", and "$T_3$ for $4$ ms". i.e., every task is run in parts. Now for timing purpose we consider $t$ for the end of cycle number $t.$

  • $T_1:0,3,6,9,12,\ldots \infty$ $\quad (T_1 \text{ repeats every $3$ ms})$
  • $T_2:0,7,14,21,\ldots \infty$ $\quad (T_2 \text{ repeats every $7$ ms})$
  • $T_3:0,20,40,60,\ldots \infty$ $\quad (T_3 \text{ repeats every $20$ ms})$
  1. Priority of $T_1 = \frac{1}{3}$
  2. Priority of $T_2 = \frac{1}{7}$
  3. Priority of $T_3 = \frac{1}{20}$

$
{\overset{\text{Gantt Chart}}{\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\underset{0}{}&\underset{1}{T_1}&\underset{2}{T_2}&\underset{3}{T_2}&\underset{4}{T_1}&\underset{5}{T_3}&\underset{6}{T_3}&\underset{7}{T_1}&\underset{8}{T_2}&\underset{9}{T_2}&\underset{10}{T_1}&\underset{11}{T_3}&\underset{12}{T_3}&\dots&\dots\dots\\
\hline
\end{array}}}$
$\text{At }t=0,\; \text{ No process is available}$
$\text{At }t=2,\; T_2 \text{ runs because it has higher priority than $T_3$ and no instance of $T_1$ present}$
$\text{At }t=4,\; \text{We have $T_1$ arrive again and $T_3$ waiting but $T_1$ runs because it has higher priority}$
$\text{At }t=5,\; T_3 \text{ runs because no instance of $T_1$ or $T_2$ is present}$
$\text{At }t=11,\; T_3 \text{ runs because no instance of $T_1$ or $T_2$ is present}$
$\text{At }t=12,\; T_3 \text{ continue run because no instance of $T_1$ or $T_2$ is present and first instance of $T_3$ completes}$
 

edited by
56 votes
56 votes
1: T1
2: T2
3: T2
4: T1
5: T3
6: T3
7: T1
8: T2
9: T2
10: T1
11: T3
12: T3 (First instance of T3 completes 4 ms and finished execution).

So, answer is 12.
39 votes
39 votes

There are $\infty$ instances of Tasks $\{ T_1, T_2, T_3\}$ which arrives at regular intervals, intervals starts from time 0.

so here's how processes arrives:

and here's the Gantt Chart:

answer = $T_3$ completes at the end of $12^{th}$millisecond

23 votes
23 votes

12 msec

Answer:

Related questions

48 votes
48 votes
6 answers
3
makhdoom ghaya asked Feb 12, 2015
12,171 views
The following two functions $P1$ and $P2$ that share a variable $B$ with an initial value of $2$ execute concurrently.$$\begin{array}{|l|l|}\hline \text{P1() \{ } & \tex...
31 votes
31 votes
2 answers
4