# GATE2015-1-46

18.6k views

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

edited
11

@Bikram sir pls see where I m wrong

20

it is clearly given in question:

Given that all tasks initially arrive at the beginning of the 1st 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 :

0T1 1 | 1 T2  2 | 2 T2   3| 3 T1   4| 4  T3  5| 5 T3  6|6  T1  7| 7  T2  8| 8 T2 9| 9 T1 10|10  T3  11| 11  T3  12 |

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 )

6
We are taking time from 1 so actually 12 seconds have elapsed at t=13, so end of 12 ms
1
That question of "scheduling" makes us to "ponder"
9
Moral of the question
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.
2
This question is simply based on RATE-MONOTONIC algorithm.
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
@utpal CPU shouldn't remain idle from 0 to 1?
0

Can someone please explain what does that mean

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

1

@Mk Utkarsh @Balaji Jegan Why not 13? Why at the end of "13th" ms is wrong? :(

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.
0
Beginning of 1st milisecond. Means the time period between 0-1.
0

@Deepak Kumar 12 Yes the execution completes when we reach 13ms i.e. at the end of 12ms

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.

Solution:-

edited
0
"arriving at beginning of 1ms"

it means 0th millisecond has already over & going to begin 1ms.

so, all jobs are executed from 1ms as the jobs are coming from 1ms.

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

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

Tried to explain in simplest manner possible:-

simple & step by step

0
I've tried to explain each step in GANTT CHART according to burst & arrival time of Task 1,2,3

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

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)

## Related questions

1
10.6k views
Consider a disk pack with a seek time of $4$ milliseconds and rotational speed of $10000$ rotations per minute (RPM). It has $600$ sectors per track and each sector can store $512$ bytes of data. Consider a file stored in the disk. The file ... accessing each sector is half of the time for one complete rotation. The total time (in milliseconds) needed to read the entire file is__________________
Suppose the following disk request sequence (track numbers) for a disk with $100$ tracks is given: $45, 20, 90, 10, 50, 60, 80, 25, 70.$ Assume that the initial position of the R/W head is on track $50$. The additional distance ... SSTF) algorithm is used compared to the SCAN (Elevator) algorithm (assuming that SCAN algorithm moves towards $100$ when it starts execution) is________________tracks.
The following two functions $P1$ and $P2$ that share a variable $B$ with an initial value of $2$ ... $B$ can possibly take after the execution is______________________.
Consider a system with byte-addressable memory, $32-bit$ logical addresses, $4$ $kilobyte$ page size and page table entries of $4$ $bytes$ each. The size of the page table in the system in $megabytes$ is_________________.