@Bikram sir pls see where I m wrong

The Gateway to Computer Science Excellence

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

+16

@ set2018

it is clearly given in question:

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

^{st}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 :

0T_{1} 1 | 1 T_{2} 2 | 2 T_{2} 3| 3 T_{1} 4| 4 **T _{3} ** 5| 5

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 )

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.

+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

Can someone please explain what does that mean

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

+5

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

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

- Priority of $T_1 = \frac{1}{3}$
- Priority of $T_2 = \frac{1}{7}$
- 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}$

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

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.

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.

"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

whicharrive 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

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

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

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

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

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.

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

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.

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

+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

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

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.

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

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

+15 votes

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

+3 votes

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,302 answers

198,306 comments

105,008 users