The Gateway to Computer Science Excellence
+61 votes
11k views

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 1st millisecond and task preemptions are allowed, the first instance of $T_{3}$ completes its execution at the end of_____________________milliseconds.

in Operating System by Boss (30.8k points)
edited by | 11k views
+7

@Bikram sir pls see where I m wrong

+16

set2018

it is clearly given in question:

Given that all tasks initially arrive at the beginning of the 1st millisecond

means in the range of 0 to 1 all tasks initially arrive.

so arriving time  in Gnatt starts from 0 .

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.

periodically they arive as T1 then T2 next T3. so 

for T1 , priority is = 1/1 = 1

T2 , priority is = 1/2 = 0.5

T3, priority is = 1/3= 0.33

so order of priority is T1 , T2, T3. 

T1 is executing first.

 Each instance of T1,T2 and T3 requires an execution time of 1, 2 and 4 milliseconds, respectively.

that means one instance of T1 = 1 

one instance of T2=2 

one instance of T3 = 4  and it is uniprocessor system so at any point of time only one task is running. in each box in Gnatt chart shoudl represent T1 for 1 msec only or T2 for 1 msecs only..

T1 repeat after 3 , 7 and 10 when start at 1 .( means after start at 0 , T1 come again at 0+3=3, 3+3=6 and 6+3=9)

( T2 repeats after 7 msecs means  start at 0, then again come at  0+7 = 7 )

so the chart looks like :

0T1 1 | 1 T2  2 | 2 T2   3| 3 T1   4| 4  T3  5| 5 T3  6|6  T1  7| 7  T2  8| 8 T2 9| 9 T1 10|10  T3  11| 11  T3  12 |

T2 burst time = 2 so that's why after first T1, 2 times T2 occur. 

so first instance of T3 completes at 12 milliseconds.( each instance of T3 takes 4 unit of time , so T3 appear 4 times in chart )

+4
We are taking time from 1 so actually 12 seconds have elapsed at t=13, so end of 12 ms
+1
That question of "scheduling" makes us to "ponder"
+7
Moral of the question
Read question carefully .
0
when t2's first instance is starting at 1ms the how the second instance of t2 is starting at 7 ms i.e 1+7 should be 8ms.
0
This question is simply based on RATE-MONOTONIC algorithm.
+1
In the grant chart we generally consider the start of timeline from 0....so in the question it is given that begining of 1st millisecond...so 1st millisecond starts from timeline 0 in grantchart....
0
@utpal CPU shouldn't remain idle from 0 to 1?
0

Can someone please explain what does that mean

Given that all tasks initially arrive at the beginning of the 1st millisecond

+1

@Mk Utkarsh @Balaji Jegan Why not 13? Why at the end of "13th" ms is wrong? :(

+5

@Utkarsh Joshi Because 13th ms is STARTING and 12th ms is ENDING....and question is asking about AT THE END OF______ ms..

+1
how to get 12 msec ? if all process arrives at 1ms then we start 1st instance of  process p1( due to higher priority )from 1 ms  and  1st instance of P3 complete its execution  at 13 ms .

 why  Gantt chart start from 0 ?but in question all process arrives at 1 msec.
0
Beginning of 1st milisecond. Means the time period between 0-1.
0

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

10 Answers

+64 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}$
 

by Veteran (63k points)
edited by
+1

@pC check this. Hope now its clear.

+14

@Anirudh

 beginning of the 1st millisecond means start from 0 isn't it ??

+7
@Anirudh, Although your solution is well explained, could you please rectify the small mistakes in your solution? Gantt Chart is correct, but the sequence given for T1, T2, T3 incorrect.

T1 should be (1, 4, 7, 10, ...) OR (0, 3, 6, 9, ...) depending on what you interpret as the "beginning of the first millisecond". Similarly for T2 and T3.

Also, priority for the tasks is the inverse of the "period" of tasks, not their burst times. So priority of T1=1/3, T2 = 1/7, T3 = 1/20.

@Gabbar: That interpretation will not affect the answer. If you assume that beginning of the 1st millisecond is 0 then tasks will also start from t=0, but if you interpret it as t=1 then tasks will start from t=1. T3 will complete its execution at the end of the 12th millisecond.
+13
@Gabbar....one correction here

As stated priority is inverse of period so they would be (1/3),(1/7) and (1/20) respectively.You have done with respect to burst time.Though that doesnot effect their priority.
0
@pC:

"Which" refers to the task. Let's look at $T_1$. $T_1$ is composed of $J_1, J_2, J_3,....$

Let's assume $T_1$ arrives in ready queue at $t_1$. But since $T_1$'s first instance (or first part) is $J_1$ so actually $J_1$ arrived at $t_1$. So now  $J_1$ is done and after 3 seconds  $T_1$ comes in ready queue again. This time  $J_2$ arrived and so on.

So  task $T_1$ arrives periodically at interval of 3 seconds. So first it comes at  $t_1$ then  $t_1+3$,  $t_1+6$ and so on. You can also look at  $J_1$ arriving at  $t_1$,  $J_2$ arriving at  $t_1+3$ and so on. They mean the same thing.

Similarly for other tasks.

So your second interpretation of "which" is what question means.
+2

Consider a uniprocessor system executing three tasks T1,T2 and T3 each of which is composed of an infinite sequence of jobs which arrive periodically at intervals of 3, 7 and 20 milliseconds, respectively.

What does the which in the above sentence refer to ?

  • When which refer to each job instances of T1 then it should be T1(0,3,7,20,23) T2(0,3,7,20,23) T3(0,3,7,20,23) etc
  • When which refer to each job instances of 3 tasks then T1 should be T1(0,3,6,9,12...) T2(0,7,14,21,28...) T3(0,20,40,60,80) etc.
0

@pratyush_madhukar

Some extended discussion on this going on here :
Stack Exchange Link

0
I agree that the question is little ambiguous about it. But I think the meaning assumed in answer makes the most sense. I also got confused in these two meanings when I tried to solve this question first, but then realized that we can't go ahead with the other meaning.
0

Question says : all tasks initially arrive at the beginning of the 1st millisecond, and repeat after intervals of 3,7,20 period. So shouldn't it be 1,4,7,... for $T_1$ and so on for others?

0
Are task pre-emption allowed here?
+1
Why downvote?? At least give a valid reason so that I can improve over it.Or discuss what's the point you don't get it.
+1
yes....allowed
0
T2 should repeat after 7 ms. But T2 has came on 2 ms and after that it should come onl at 9 ms, but in the gantchart it is shown that it came at 8ms. Please clear my doubt
0

@Ayush Upadhyaya @Prashant. Sir where am I getting wrong?

In above question T1 appears after 2unit of time instead of 3unit.Also T2 after 6 unit of time instead of 7, please clear this doubt

0

@ See bikram sir's comment (above)

0
Is anyone getting the answer as 13?
+44 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 Veteran (431k points)
0
how come T2 occurs at an interval of 5sec instead of 7 sec ! plz explain
+4
Given all tasks arrive initially. So, first instance of T2 arrives at time 0. And its periodicity being 7, next one arrives at time 7- it won't wait till the prev instance of T2 to finish and then add 7 ms to that time.
+1
okay yeaaa i got the point now. thanks
0
the sequence is wrong ,T2 will occur at 10 ms for second time bcoz there is period of 7 ms for T2
0
First instance of T2 is arriving at T1, so second instance at 1+7 = T8. Now, if finishes at T9 and next arrival is only at T15.
0
please elaborate in words what is happening
+2

@Arjun Sir.....Shouldn't the processes start from 1, then T3 completes at 13(since 2 bursts remaining)

T1 T2 T1 T3 T1 T2 T1 T3  

1              2                4                 5                7                8               10              11             13     

Please explain.

+18

It is "beginning of 1st millisecond". Since 1st millisecond in the interval 0 - 1, so the beginning should be 0.

0
answer is 13 i thinkk
0
arjun sir plz explain it clearly
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 ??
+34 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

by Boss (30.8k points)
0

Here @ 8 & 9th unit of  Time in Gantt chart both T2 and T3 have 2 unit of execution work to do..and so according to question both have equal priority bcz ...priority is inverse of Time period.. And if u see at this time Arrival time of T3 is first compare to T2 in Ready queue...then why not we are scheduling T3..at 8 and 9 th unit of time rather than T2???

Plz [email protected] Respected Sir/ Mam...

+2

it is given that : "the priority of each task is the inverse of its period, and the available tasks are scheduled in order of priority"

It talks time period, which is a constant. Not remaining time.

+1
Could someone explain in words what is happening . Im not able to follow. It seems very difficult to digest the question itself.
0
Explain plzz... Not able to follow
0
1st how to impliment a question in  a table form  (i am not understand the question

)
0
figure 1 of in the answer shows when the processes are arriving,
There are infinite many process instances of process 1, process 2 and process 3. BUT, they arrive only at specific time intervals. in figure process 1 arrives at $(1, 4, 7, 10)^{th}$ millisecond coz its given that process 1 instance arrives after every 3rd millisecond.

How to assign priority is given in the question. Which makes it now a simple problem of priority scheduling with preemption allowed.
0

here dont u think that T2  reappears on grantt chart only after 6 unit interval ??

0

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

12 msec

by Boss (19.8k points)
0
@sudhso

somewhere we take interval from 0-1

somewhere we take like 1

what is meant by 0-1

and 1 ?
0
@sudhso
u missed that t2 has 2 BT nd priority higher than T3
0
its the arrival time
0
no arrival time of t2 is 7 jumps each
0
ya u r right.
can u tell why u take here from 0?
when they stated it will 1 ms?
0
0 is AT of first instane of all of them
0
its given in the ques that they have arrived at the beginning of 1st ms
0
ohhh god i lost my marks....as such

tie
0
thanks nice answer ...wasted my time in best answers..cudn't understand there..finally dis is clear explanation.
0
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
Here i got this question. Thanks !
+6 votes
sequence should be 1 T1 ,2 T2,3 T2,4 T1,5 T3, 6 T3, 7 T1 ,8 T3 ,9 T2, 10 T1, 11 T2 , 12 T3 .,13 T1  so  ans is 12 .
by Boss (17.1k points)
0
Arjun sir given in question is that all tasks initially arrive at the end of 1ms millisecond? Then how you are starting execution from t=0?
+2
no ,we also started from 1ms
–3
does not matter,as they have asked end of - ms..whether you start from 0 or 1,it will be end of 12th( note th) ms.
0
i got 13
+4 votes

Ans is 12 ms.

after end of 12 ms all the 4 units of T3 will be completed.

by Active (3.9k points)
+3 votes
answer is 12
by Active (1.4k points)
0
Greater value of priority is higher or lesser value of priority is higher?, I mean number in some numericals the more value of number the priority is lesser!
+2

@smartmeet

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.

periodically they arive as T1 then T2 next T3. so 

for T1 , priority is = 1/1 = 1

T2 , priority is = 1/2 = 0.5

T3, priority is = 1/3= 0.33

so order of priority is T1 , T2, T3. 

T1 is executing first.

0 votes
I think those who started with 1 ms are correct. The question asks "the first instance of T3 completes its execution at the  END of which millisecond and thus 12 is the right answer.
by (295 points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,302 answers
198,306 comments
105,008 users