The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 votes

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:

  1. $13$ units
  2. $14$ units
  3. $15$ units
  4. $16$ units
asked in Operating System by Active (3.7k points)
edited by | 2.3k views
ye kahan diya hai> ki preemptive scheduling karni hai?

जब भी remaining time first वाली state होती है | तब preemptive scheduling होती है |

it maybe longest remaining or shortest remaining. Keyword is Remaining

"LRTF ties are broken by giving priority to the process with the lowest process id. " what it means?
whenever there is same B.T. then give priority

2 Answers

+24 votes
Best answer


Gantt Chart is as follows.

Gantt Chart
$P2$ $P2$ $P2$ $P2$ $P1$ $P2$ $P1$ $P2$ $P0$ $P1$ $P2$ $P0$ $P1$ $P2$
Scheduling Table
P.ID A.T B.T C.T T.A.T. W.T.
$P0$ $0$ $2$ $12$ $12$ $10$
$P1$ $0$ $4$ $13$ $13$ $9$
$P2$ $0$ $8$ $14$ $14$ $6$
TOTAL       $39$ $25$

A.T.$=$ Arrival Time

B.T.$=$ Burst Time

C.T$=$ Completion Time.

T.A.T.$=$ Turn Around Time

W.T= Waiting Time.

Average TAT $= 39/3 = 13$ units.

answered by Boss (19.7k points)
edited by
Why process with id 2 will execute for first four time unit? Why not it will get completed at one go?
this is preemptive based scheduling.....
Why the process id2 will execute for the first four time unit is , becoz it is LRTF algorithm.... at the same time process id1 burst time is 4 time units that is why process id2 will decrement each time as i time unit and it stops after the execution of 4 time unit and restarts process id1....
+7 votes


LRTF  means the process which has remaining time largest will run first and in case of same remaining time lowest process_id will be given priority to run. 

First 4 sec ,P2 will run . then P2 remaining time =4 ,p1=4,p0=2. 

Now P1 will get chance to run for 1 sec. P2=4,p1=3,p0=2.

Now p2 will get chance to run for 1 sec, P2=3,p1=3,p0=2.

This way if we do carefully, TAT of P1 will be 14 sec,p1=13 sec and p0= 12 sec.

Total TAT = 14+13+12= 39

Avg TAT= 39/3 =13 sec.

answered by Active (4.9k points)
Why longest remaining is checked after each time unit?

It must be checked when any process arrives or we usually do with srtf unless specified.

Plz help

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,941 questions
45,453 answers
48,210 users