@Deepak Kumar 12 Yes the execution completes when we reach 13ms i.e. at the end of 12ms

Dark Mode

29,092 views

90 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.

$intervals$ | $priority$ | $burst-time$ | |

$T1$ | $3$ | $\dfrac{1}{3}(highest)$ | $1$ |

$T2$ | $7$ | $\dfrac{1}{7}$ | $2$ |

$T3$ | $20$ | $\dfrac{1}{20}(lowest)$ | $4$ |

$0-1=T1$

$1-2=T2$

$2-3=T2$

$3-4=T1(second-instance)$

$4-5=T3$

$5-6=T3$

$6-7=T1(third-instance\ \&\ T3\ is\ prempted )$

$7-8=T2(second-instance)$

$8-9=T2$

$9-10=T1(fourth-instance)$

$10-11=T3$

$11-12=T3(first-instance\ completed\ of\ T3)$

$Ans:12ms$

9

I don’t understand why is there so much confusion about beginning and end. Suppose you consider beginning of 1st millisecond as all processes arrive at 0, then execution of T3 will be over at the range 11 to 12 so by your definition 11 is the beginning of 12th millisecond and 12 is the end of 12th millisecond.

And if suppose you belong to the other category which defines beginning of 1st millisecond as all processes arrive at 1, then execution of T3 will be over at the range 12 to 13 so by your definition 12 is beginning of 12th millisecond and 13 is the end of 12th millisecond.

And if suppose you belong to the other category which defines beginning of 1st millisecond as all processes arrive at 1, then execution of T3 will be over at the range 12 to 13 so by your definition 12 is beginning of 12th millisecond and 13 is the end of 12th millisecond.

3

105 votes

Best answer

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})$

- Priority of $T_1 = \frac{1}{3}$
- Priority of $T_2 = \frac{1}{7}$
- 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}$

0

0

@Geekster in the solution its written,

$Now\ for\ timing\ purpose\ we\ consider\ t\ for\ the\ end\ of\ cycle\ number\ t.$

That's why there is confusion.

I have considered the beginning of cycle number, so T1 repeats at 1,4,7,… i.e T1 is present at 1^{st} , 4^{th} , 7^{th} ,..millisecond, even if we consider this, T3 is completed at the end of 12^{th} cycle

0

37 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

edited
Nov 4, 2016
by pC

@arjun sir ,

What I understood is

BT | AT | Priority | |

T1 | 1 | 1 | high |

T2 | 2 | 1 | |

T3 | 4 | 1 | low |

ach of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 milliseconds, respectively.

Didn't understand this part correctly . Is this mean each instance of task has to be scheduled at 3 , 7 , 20 ? DO all the instance will have same BT as of Task . ?

Tasks composed of infinte instance

Does this mean the entire BT of each tasks also get divided to instances ? if so what is the BT of each instance ?

If each instance of task exactly same as that of the Task . ie taking BT for each istance of task equal to BT of the Task itself and scheduling at instance arrival times ( 3,7,20)

**At Time =1**

- 1st instance of T 1
- 1st instance of T 2
- 1st instance of T 3

**At Time =3**

- 2nd instance of T 1
- 2nd instance of T 2
- 2nd instance of T 3

**At Time =7**

- 3rd instance of T 1
- 3rd instance of T 2
- 3rd instance of T 3

IDLE | T1 | T2 | T2 | T1 | T2 | T2 | T1 | T2 | T2 | T1 | T3 | T3 | T3 | T3 |

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

T1 and T2 will be getting priority and its instances will keep on executed .SO T3 will complete at Time Clock 14 .

**What is the reason for scheduling T3 at clock 5 and 6 ?**

0

23 votes

0