LJF and HRRN CPU Scheduling: Worked Gantt Charts, Formula and Exam Traps

Solve one five-process data set under non-preemptive LJF and HRRN, then compare every completion, turnaround, and waiting time.

KnowledgeGate Team

Exam prep & CS education

Updated 4 Nov 20266 min read
LJF and HRRN CPU Scheduling: Worked Gantt Charts, Formula and Exam Traps

LJF looks like a one-line rule, and HRRN like a one-line formula. The difficulty is rebuilding the ready queue only at dispatch times, using current waiting time, and separating arrival, burst, completion, turnaround, and waiting time. In the five-process workload below, LJF postpones a short job while HRRN changes the dispatch order as waiting grows. For context, review the wider CPU scheduling algorithm family.

LJF and HRRN: define the scheduling decisions precisely

Assume one CPU, non-preemptive execution, zero context-switch cost, and known arrival AT and burst BT. At completion, the ready set includes only processes with AT <= current time. The selection runs to completion.

Longest Job First (LJF) chooses the largest original burst among ready processes. Highest Response Ratio Next (HRRN) chooses the largest

RR = (waiting time + burst time) / burst time = 1 + waiting time / burst time.

Recompute HRRN at every dispatch. Break ties by earlier arrival, then smaller process ID.

Policy

Selection key

Preemptive here?

What changes while waiting?

Main risk or benefit

LJF

Largest BT

No

Nothing in the key

Short jobs can be postponed

HRRN

Largest 1 + W/BT

No

W and therefore RR rise

Ageing reduces starvation risk

LRTF or LRJF is different: it makes preemptive decisions using remaining time.

LJF worked example: schedule the longest ready burst

The process set is:

Process

AT

BT

P1

0

4

P2

1

8

P3

2

2

P4

3

6

P5

5

3

Keep the assumptions and tie rule. After scheduling, use CT = completion time, TAT = CT - AT, and WT = TAT - BT.

  • t=0: only P1 is ready. Run it from 0 to 4.

  • t=4: ready P2(8), P3(2), P4(6). Run P2 from 4 to 12.

  • t=12: ready P3(2), P4(6), P5(3). Run P4 from 12 to 18.

  • Run P5 from 18 to 21, then P3 from 21 to 23.

The LJF Gantt order is 0 | P1 | 4 | P2 | 12 | P4 | 18 | P5 | 21 | P3 | 23.

Process

CT

TAT

WT

P1

4

4 - 0 = 4

4 - 4 = 0

P2

12

12 - 1 = 11

11 - 8 = 3

P3

23

23 - 2 = 21

21 - 2 = 19

P4

18

18 - 3 = 15

15 - 6 = 9

P5

21

21 - 5 = 16

16 - 3 = 13

Sum WT = 0 + 3 + 19 + 9 + 13 = 44; average WT is 44/5 = 8.8. Sum TAT = 4 + 11 + 21 + 15 + 16 = 67; average TAT is 67/5 = 13.4.

Gantt chart of LJF scheduling for five processes, with sequence P1, P2, P4, P5, P3 and results including P3 waiting 19 units and average WT 8.8.

HRRN worked example: recompute at every dispatch

At t=0, only P1 is ready, so it runs from 0 to 4.

At t=4:

  • P2: W = 4 - 1 = 3, so RR = (3 + 8)/8 = 11/8 = 1.375.

  • P3: W = 4 - 2 = 2, so RR = (2 + 2)/2 = 2.

  • P4: W = 4 - 3 = 1, so RR = (1 + 6)/6 = 7/6, about 1.167.

P3 runs from 4 to 6. At t=6, recompute: P2 has W=5, RR=13/8=1.625; P4 has W=3, RR=9/6=1.5; P5 has W=1, RR=4/3, about 1.333. Select P2 for 6 to 14.

At t=14, P4 has W=11, RR=17/6, about 2.833; P5 has W=9, RR=12/3=4. Run P5 from 14 to 17. At t=17, only P4 remains, with W=14, RR=20/6, about 3.333; run it to 23.

The HRRN order is 0 | P1 | 4 | P3 | 6 | P2 | 14 | P5 | 17 | P4 | 23. Longer bursts do not automatically win because waiting changes each ratio.

LJF versus HRRN: compare the completed schedules

Process

HRRN CT

HRRN TAT

HRRN WT

P1

4

4 - 0 = 4

4 - 4 = 0

P2

14

14 - 1 = 13

13 - 8 = 5

P3

6

6 - 2 = 4

4 - 2 = 2

P4

23

23 - 3 = 20

20 - 6 = 14

P5

17

17 - 5 = 12

12 - 3 = 9

For HRRN, sum WT = 0 + 5 + 2 + 14 + 9 = 30; average WT is 30/5 = 6.0. Sum TAT = 4 + 13 + 4 + 20 + 12 = 53; average TAT is 53/5 = 10.6.

Policy

Order

Average WT

Average TAT

LJF

P1, P2, P4, P5, P3

8.8

13.4

HRRN

P1, P3, P2, P5, P4

6.0

10.6

Here, HRRN lowers both averages by 2.8: 8.8 - 6.0 = 2.8 and 13.4 - 10.6 = 2.8. P3's WT falls from 19 to 2, while P4's rises from 9 to 14. It does not follow that HRRN always minimises either average.

Two-row scheduling comparison of LJF and HRRN, showing average waiting times 8.8 and 6.0, average turnaround times 13.4 and 10.6, and P3 waiting change from 19 to 2.

HRRN ageing and LJF starvation risk

The formula RR = 1 + W/BT explains ageing. A new job starts at ratio 1. As W grows, a short job's ratio rises faster because W is divided by BT.

Under LJF, P3 is ready at t=2 but loses at t=4 to P2(8), at t=12 to P4(6), and at t=18 to P5(3). It starts at t=21 and waits 21 - 2 = 19. Under HRRN, its ratio at t=4 is 2, above P2's 1.375 and P4's roughly 1.167, so it waits only 2.

Every process completes here. With continuing arrivals, LJF can postpone a short job. HRRN's ageing reduces that risk without guaranteeing fairness or optimal averages.

LJF and HRRN traps that change the answer

Wrong move

Correction

Choose the globally longest process

Choose the longest process already arrived

Recalculate LJF during a burst

This version is non-preemptive, so wait for completion

Treat LJF and LRTF as identical

LJF uses original burst at dispatch; LRTF uses remaining time preemptively

Use turnaround time in HRRN's numerator

Use current waiting time plus burst time

Compute each HRRN ratio once

Recompute at every dispatch

Use remaining time as HRRN service time

Use the original burst because an unselected process has not run

Include P5 at t=4

P5 arrives at t=5, so it first becomes eligible at t=6

Take CT from the chart, then use TAT=CT-AT and WT=TAT-BT. WT is not start time when arrival is non-zero. If no job is ready, show an idle interval until the next arrival. Zero context-switch cost is only an assumption here. With simultaneous arrivals, every initial HRRN ratio is 1, so the tie rule decides.

How exam-style questions test LJF and HRRN

Questions may ask for a Gantt chart, metrics, an HRRN dispatch, LJF versus LRTF, starvation, non-preemption, a tie, or an idle interval. For mixed scheduling practice, try Process Scheduling MCQs: 12 Solved.

Use this sequence: note time, exclude future arrivals, form the ready set, compute the key, apply the tie rule, append the burst, and repeat. Then derive metrics from CT. Check LJF with sum WT=44, sum TAT=67, and HRRN with sum WT=30, sum TAT=53.

At t=10, let A have AT=2, BT=4, B have AT=6, BT=2, and C have AT=9, BT=8. LJF selects C. For HRRN, A has W=8, RR=12/4=3; B has W=4, RR=6/2=3; C has W=1, RR=9/8=1.125. A and B tie, so earlier arrival selects A. Without a tie rule, the answer is ambiguous. Use the GATE Test Series for timed practice.

LJF and HRRN: the short version and next step

LJF selects the largest ready burst; HRRN selects the largest 1 + W/BT. Both are non-preemptive here. Filter arrivals before selecting and derive metrics after the chart. The schedules are P1-P2-P4-P5-P3 for LJF and P1-P3-P2-P5-P4 for HRRN.

Hide the tables, redraw both charts, and confirm that P3 waits 19 under LJF and 2 under HRRN. If not, inspect LJF at t=4, 12, 18, or recompute HRRN at t=4, 6, 14.

For a structured core-CS path, use GATE Guidance by Sanchit Sir. Browse GATE CS Exam Preparation for the broader catalogue, or use the GATE Test Series for timed practice.