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

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

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 help...@ Respected Sir/ Mam...

---

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.

---

Could someone explain in words what is happening . Im not able to follow. It seems very difficult to digest the question itself.

---

Explain plzz... Not able to follow

---

1st how to impliment a question in  a table form  (i am not understand the question

)

---

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.

---

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

---

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