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

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

how come T2 occurs at an interval of 5sec instead of 7 sec ! plz explain

---

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.

---

okay yeaaa i got the point now. thanks

---

the sequence is wrong ,T2 will occur at 10 ms for second time bcoz there is period of 7 ms for T2

---

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.

---

please elaborate in words what is happening

---

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

---

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

---

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

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 4

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