Longest remaining time first problem

aryan123's Avatar
Go4Expert Member
Consider three processes (process id 0, 1, 2 respectively) with compute time bursts 2, 4 and 8 time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the process with the lowest process id. The average turn around time is: [2 marks]
(A) 13 units
(B) 14 units
(C) 15 units
(D) 16 units

Ans= (A) 13 units

Can anyone please help me to solve this..
0
ManzZup's Avatar, Join Date: May 2009
Skilled contributor
well you may need to go through the algo first
if i understand this correct, you need to for the processing of the algo by the processor
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
It's clearer if you do it on a spreadsheet. Set B1-D1 to the process IDs 1-3 and B3-D3 to the time remaining for each (2,4,8). The vertical axis represents time. Row 3 corresponds to time zero.

A4 is the process chosen by the scheduler. By the rules this has to be process 3. So set D4 to 7 to show P3 now has 7 time units remaining (and if you like, C4 to 2 and B4 to 2 to show that they haven't changed).

What goes in A5? 2, as P2 still has 7. So set D5=6. A6-A7 are the same, and D7 is now 4.

So now P1 and P2 have 4 remaining. The lowest process ID has priority, so the next one to schedule is P1. Put a 1 in A8 and a 3 in C8.

P2 is next, so A9=2 and D9=3.

You should have enough info now to get you to the end of the spreadsheet. See how many lines you've got, remember that the first line is T=0, the second T=1 etc, so if you have 27 lines (you don't) then the answer would be 26.

Other ways to work this thing out are in your head if you can remember all those numbers, or on paper if you can't.

Incidentally if the processes have 8,4 and 2 time units then the minimum compute time on a single processor will be 14 TUs, not 13. However this also depends on what exactly is meant by "turn around time" - is this from the scheduler's point of view? At the end of T=13 when the scheduler has made its last decision, P2 still has 1TU to run. So from a scheduler point of view A might be the correct answer. But if it means "time to complete the work" then it has to be 8+4+2=14=B.