1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Longest remaining time first problem

Discussion in 'Engineering Concepts' started by aryan123, Jan 8, 2012.

  1. aryan123

    aryan123 New Member

    Joined:
    Jan 9, 2011
    Messages:
    22
    Likes Received:
    0
    Trophy Points:
    0
    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..
     
  2. ManzZup

    ManzZup New Member

    Joined:
    May 9, 2009
    Messages:
    278
    Likes Received:
    43
    Trophy Points:
    0
    Occupation:
    Production Manager:Software @ ZONTEK
    Location:
    Sri Lanka
    Home Page:
    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
     
  3. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    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.
     

Share This Page