in Operating System edited by
29,092 views
90 votes
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.
in Operating System edited by
29.1k views

4 Comments

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

0
0
  $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
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.
3
3

14 Answers

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

4 Comments

I Think Everyone will Lose Marks in this Question , so I dont think we lose rank , unless some topper actually decides to leave it without solving, which is rare, almost everyone tries to solve the scheduling numericals.
0
0
can anyone clear me why we are taking gap in multible of 3 when its written we have to take periodic interval of 3 ms in t1 ..and process is starting from t = 1 i.e., next time T1 must come at t= 4 and same logic for other two processes .
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 1st , 4th , 7th ,..millisecond, even if we consider this, T3 is completed at the end of 12th cycle

0
0
53 votes
53 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.
by

4 Comments

answer is 13 i thinkk
0
0
arjun sir plz explain it clearly
0
0
sir,..i get the complete question n solution but one thing as its mention t1 comes at 3 so on 3 we should execute na ?? you are taking as after 3 instance of running..??? and sir 1 instance ko hum 1-2 tak hi toh consider karenge ??
0
0
37 votes
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

4 Comments

edited by

@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
0
Nicely explained!!!. Thank you brother.
0
0
thank you, sir, for detailed solution
0
0
23 votes
23 votes

12 msec

4 Comments

All tasks initially arrive at the beginning of 1st millisecond and you are allocating cpu for T1 at 0 millisecond.. how is it possible???
0
0
Here i got this question. Thanks !
0
0
Thanks sudhso
0
0
Answer:

Related questions