ExtendedSource checked

Least Laxity First

Runs the task with the least spare time before its deadline.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Scheduling
Difficulty: Intermediate
Family: Real-Time Scheduling
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 2
Code example: Ready
Visualization: Ready
Aliases: LLF

Overview

Least Laxity First calculates each task's remaining slack and chooses the one closest to missing its deadline.

Core Concepts

task orderingdeadline constraintdependency timingreal-time schedulingready queuetask priorityresource allocation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

When to Use

Use Least Laxity First when you need to compute task laxity from deadline and remaining work.
Use it for real-time scheduling with inputs like tasks with deadlines.
Use it when tasks, priorities, deadlines, or resource limits drive execution order.
Use it when the Real-Time Scheduling tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when worst-case timing cannot be bounded well enough.
Avoid it when fairness, latency, and throughput requirements conflict but are not prioritized.
Avoid it when the required output is not laxity-based schedule.

What It Does

Computes task laxity from deadline and remaining work
Prioritizes the smallest laxity

Use Cases

Real-time scheduling
Deadline-sensitive workloads
Dynamic priority examples

Inputs

Tasks with deadlines
Remaining execution times

Outputs

Laxity-based schedule

Key Formulas (1)

Laxity

laxity = deadline − current_time − remaining_work

laxity = deadline - current_time - remaining_work

Runs the task with the least remaining scheduling slack.

Pseudocode

1.For each ready task, compute deadline minus current time minus remaining work
2.Choose the task with least laxity
3.Run it until laxity changes or a new task arrives
4.Recompute priorities
5.Repeat until all jobs finish

Canonical Example

Input: tasks = A(4ms), B(2ms), C(1ms)
Output: execution order and completion times
Explanation: Least Laxity First: The scheduler chooses which task should run next according to its rule.

Implementation Notes

Keep the input contract explicit: Tasks with deadlines; Remaining execution times.
Use this step as the implementation spine: For each ready task, compute deadline minus current time minus remaining work.
Then preserve the next state change: Choose the task with least laxity.
Record arrival time, remaining work, and completion time so schedule metrics can be checked.

Common Pitfalls

Frequent priority changes can make LLF expensive in practice.
Ignoring starvation, preemption cost, or inaccurate duration estimates.
Returning laxity-based schedule without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show slack shrinking as deadlines approach.

Step 1 of 5: For each ready task, compute deadline minus current time minus remaining work

laxity-timeline

Notes

Least Laxity First operates in O(n log n) time and O(n) space within the Real-Time Scheduling family. Key governing relation: laxity = deadline - current_time - remaining_work. Often compared with Earliest Deadline First and Rate Monotonic Scheduling.