GATE CS 2006 Q64 — CPU Scheduling

Longest Remaining Time First (LRTF) is a preemptive scheduling algorithm. At any time instant, the process with the longest remaining burst time is scheduled. Ties are broken by choosing the process with the lowest process ID.

Let the processes be $P_0$, $P_1$, and $P_2$ with initial burst times $2$, $4$, and $8$ respectively, arriving at $t = 0$. We trace the execution step-by-step:

• Interval $[0, 4]$: $P_2$ has the longest remaining time ($8$). It runs for $4$ units.
  Remaining times at $t = 4$: $P_0 = 2$, $P_1 = 4$, $P_2 = 4$.
• Interval $[4, 5]$: $P_1$ and $P_2$ are tied at $4$. $P_1$ runs (lower ID).
  Remaining times at $t = 5$: $P_0 = 2$, $P_1 = 3$, $P_2 = 4$.
• Interval $[5, 6]$: $P_2$ runs.
  Remaining times at $t = 6$: $P_0 = 2$, $P_1 = 3$, $P_2 = 3$.
• Interval $[6, 7]$: $P_1$ and $P_2$ are tied at $3$. $P_1$ runs.
  Remaining times at $t = 7$: $P_0 = 2$, $P_1 = 2$, $P_2 = 3$.
• Interval $[7, 8]$: $P_2$ runs.
  Remaining times at $t = 8$: $P_0 = 2$, $P_1 = 2$, $P_2 = 2$.
• Interval $[8, 9]$: All are tied at $2$. $P_0$ runs.
  Remaining times at $t = 9$: $P_0 = 1$, $P_1 = 2$, $P_2 = 2$.
• Interval $[9, 10]$: $P_1$ and $P_2$ are tied at $2$. $P_1$ runs.
  Remaining times at $t = 10$: $P_0 = 1$, $P_1 = 1$, $P_2 = 2$.
• Interval $[10, 11]$: $P_2$ runs.
  Remaining times at $t = 11$: $P_0 = 1$, $P_1 = 1$, $P_2 = 1$.
• Interval $[11, 12]$: All are tied at $1$. $P_0$ runs and completes.
  Remaining times at $t = 12$: $P_0 = 0$, $P_1 = 1$, $P_2 = 1$.
• Interval $[12, 13]$: $P_1$ and $P_2$ are tied at $1$. $P_1$ runs and completes.
  Remaining times at $t = 13$: $P_1 = 0$, $P_2 = 1$.
• Interval $[13, 14]$: $P_2$ runs and completes.

The completion times ($CT$) for the processes are:

• $CT(P_0) = 12$
• $CT(P_1) = 13$
• $CT(P_2) = 14$

Since all processes arrive at $t = 0$, the turnaround time ($TAT = CT - AT$) for each process is equal to its completion time.