@Bikram sir pls see where I m wrong

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

20

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

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.

why Gantt chart start from 0 ?but in question all process arrives at 1 msec.

5

$intervals$ | $priority$ | $burst-time$ | |

$T1$ | $3$ | $\dfrac{1}{3}(highest)$ | $1$ |

$T2$ | $7$ | $\dfrac{1}{7}$ | $2$ |

$T3$ | $20$ | $\dfrac{1}{20}(lowest)$ | $4$ |

$0-1=T1$

$1-2=T2$

$2-3=T2$

$3-4=T1(second-instance)$

$4-5=T3$

$5-6=T3$

$6-7=T1(third-instance\ \&\ T3\ is\ prempted )$

$7-8=T2(second-instance)$

$8-9=T2$

$9-10=T1(fourth-instance)$

$10-11=T3$

$11-12=T3(first-instance\ completed\ of\ T3)$

$Ans:12ms$

0

I don’t understand why is there so much confusion about beginning and end. Suppose you consider beginning of 1st millisecond as all processes arrive at 0, then execution of T3 will be over at the range 11 to 12 so by your definition 11 is the beginning of 12th millisecond and 12 is the end of 12th millisecond.

And if suppose you belong to the other category which defines beginning of 1st millisecond as all processes arrive at 1, then execution of T3 will be over at the range 12 to 13 so by your definition 12 is beginning of 12th millisecond and 13 is the end of 12th millisecond.

And if suppose you belong to the other category which defines beginning of 1st millisecond as all processes arrive at 1, then execution of T3 will be over at the range 12 to 13 so by your definition 12 is beginning of 12th millisecond and 13 is the end of 12th millisecond.

0 votes

0 votes

For those who are getting answers as 13 please note that its 13 units on Gantt chart and all process arrive at 1ms. Hence final result of 13 has to be subtracted by 1.

Hence completion time of T3(in ms) is 13-1=12 ms

**Hence answer is 12 ms. **

**For clear understanding see the solution below where I have showed 1ms on Gantt chart. **

0 votes

0 votes

video starts at 36:43 NPTEL IIT KHARAGPUR RATE MONOTONIC SCHEDULER (EMBEDDED SYSTEMS)

I think this is out of the league question, as it is not taught in computer science branches.

Still it is a kind of scheduling, so after watching this video

You will be able to answer this question more clearly and fastly

0 votes

Let me clear the "beginning of the 1st millisecond".

Gate exam is of 3hr. So when your exam starts , it's the beginning of 1st hr i.e., 0-1 is 1st hour and begining of 1st hour is 0 and end of 1st hour is 1.

Similarly beginning of the 1st millisecond will start from 0 in our Gantt Chart.

0-1: T1 (0 is beg and 1 is end of 1st millisecond)

1-2: T2

2-3: T2

3-4: T1

4-5: T3

5-6: T3

6-7: T1

7-8: T2

8-9: T2

9-10: T1

10-11: T3

11-12: T3 (11 is beg and 12 is end)

Gate exam is of 3hr. So when your exam starts , it's the beginning of 1st hr i.e., 0-1 is 1st hour and begining of 1st hour is 0 and end of 1st hour is 1.

Similarly beginning of the 1st millisecond will start from 0 in our Gantt Chart.

0-1: T1 (0 is beg and 1 is end of 1st millisecond)

1-2: T2

2-3: T2

3-4: T1

4-5: T3

5-6: T3

6-7: T1

7-8: T2

8-9: T2

9-10: T1

10-11: T3

11-12: T3 (11 is beg and 12 is end)