Overview
Least Slack Time scheduling computes each task's slack as deadline minus current time minus remaining work. The task with the smallest slack runs first, making the policy responsive to both deadlines and remaining processing time.
CoreSource checked
Least Slack Time Scheduling
Prioritizes the ready task with the least time cushion before its deadline.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Scheduling
- Difficulty
- Intermediate
- Family
- Real-Time Scheduling
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
real-time schedulingscheduling
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when both deadline proximity and remaining execution time should drive priority.
- Use when preemption and frequent priority recomputation are acceptable.
When Not to Use
- Avoid when remaining execution time estimates are unreliable.
- Avoid when preemption overhead would dominate the workload.
What It Does
- Computes dynamic slack for each ready task
- Runs the task with the smallest slack
- Updates priorities as time and remaining work change
Use Cases
- Real-time scheduling with changing urgency
- Preemptive task schedulers
- Deadline-sensitive workloads with variable remaining work
Inputs
- Ready task set with release times r_i, remaining execution times c_i, and deadlines d_i
- Current system clock t
Outputs
- Preemptive task dispatch schedule
- Computed slack time s_i = (d_i - t) - c_i per task
Pseudocode
- 1.At each decision point, collect ready tasks
- 2.For each task, compute slack = deadline - current time - remaining work
- 3.Select the task with the smallest slack
- 4.Run it until completion, arrival, or preemption point
- 5.Update current time and remaining work
Canonical Example
- Input
- time=2, A(remaining=3, deadline=8), B(remaining=1, deadline=5)
- Output
- run B
- Explanation
- A has slack 3 and B has slack 2, so B is more urgent.
Implementation Notes
- Recompute slack after arrivals, completions, and preemptions.
- Represent negative slack explicitly so missed deadlines are visible.
- Use deterministic tie-breaking to avoid scheduler oscillation.
Common Pitfalls
- Using original duration instead of remaining duration gives stale slack values.
- Ignoring release times can select tasks that are not ready.
- Frequent preemption can reduce throughput if switching cost is high.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow choosing the job with the least remaining slack before deadline on a small real-time scheduling example.
Step 1 of 5: At each decision point, collect ready tasks
scheduling-mechanismNotes
Least Slack Time depends heavily on accurate remaining-time estimates.
Sources (1)
What each reference supports for this entry.
Scheduling: Theory, Algorithms, and Systems
BookScheduling reference for Least Slack Time Scheduling precedence, due-date, lateness, or project-schedule optimization.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toEarliest Deadline First
Scheduling · Core
Least Slack Time accounts for remaining work, while EDF only orders by deadline.
Compare with thisConceptual neighborShortest Remaining Time First
Scheduling · Core
Both policies update priorities as remaining work changes.
Compare with thisRelationships
View full relationship pageAlternative toEarliest Deadline First
Least Slack Time accounts for remaining work, while EDF only orders by deadline.
Conceptual neighborShortest Remaining Time First
Both policies update priorities as remaining work changes.
Related Algorithms
Tags
Scheduling