GATE CSE 2015 | Set 1 | Question: 46

Question

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.

Comments

@ashish_ranjan 1Beginning of 1ms ka matlab 0 and 1 ke bich me i.e interval [0,1).In this 0 is included and 1 is excluded.You can do Google, Gemini, chatgpt or whatever.

---

i attempted and got it right name the processes p11 , p21, p31 ,p12,p22,p32 .. it will be a lot easier to understand

---

@Rohit_Singh 9 this understanding is wrong "Beginning of 1ms ka matlab 0 and 1 ke bich me i.e interval [0,1).In this 0 is included and 1 is excluded.You can do Google, Gemini, chatgpt or whatever"

Let me explain what is happening here. @ashish_ranjan 1 see this answer:

 

Answer 1

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

Comments

@pC check this. Hope now its clear.

---

@Anirudh

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

---

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

---

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

---

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

---

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.

---

@pratyush_madhukar

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

---

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.

---

Question says : all tasks initially arrive at the beginning of the 1^st 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?

---

Are task pre-emption allowed here?

---

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.

---

yes....allowed

---

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

---

@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

---

@soumayan bandhu See bikram sir's comment (above)

---

Is anyone getting the answer as 13?

---

The language of the question very clearly states "at the beginning of the first millisecond". This simply means that if you start counting from 0, you'll end up with the last instance of T3 at 12ms. If you start counting from 1, the last millisecond will be 13. Either way, 12 ms will have passed if you count correctly. So at the end of the 12th millisecond, the execution will be complete.

---

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.

---

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 .

---

@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

Answer 2

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.

Comments

answer is 13 i thinkk

---

arjun sir plz explain it clearly

---

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 ??

Answer 3

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

Comments

@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 ?

---

Nicely explained!!!. Thank you brother.

---

thank you, sir, for detailed solution

Answer 4

12 msec

Comments

the line all tasks intially arrive at the beginning of 1ms means before 1ms or you can also observe 

it as beginning of 1msec means before 1 has arrived i.e [0,1) means 0 included ,1 not included.

 

---

This solution is correct

---

This solution is correct with required explanation. Thanks!

Answer 5

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 .

Comments

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?

---

no ,we also started from 1ms

---

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.

---

i got 13

Answer 6

Ans is 12 ms.

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