Overview
Leaky Bucket Scheduling is a scheduling method that selects or admits work using a concrete priority, fairness, deadline, or capacity rule. It helps expose the policy tradeoff behind queue order, fairness, deadlines, or resource use.
CoreSource checked
Leaky Bucket Scheduling
Leaky Bucket Scheduling rate-limits work by accumulating or draining capacity over time.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Scheduling
- Difficulty
- Intermediate
- Family
- Scheduling
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
priority ruleresource allocationqueue disciplinetask order
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 Leaky Bucket Scheduling when queue order, resource assignment, or deadline policy must be explicit.
- Use it when comparing fairness, latency, throughput, or utilization policies matters.
When Not to Use
- Avoid when the policy would hide starvation, unfairness, or deadline misses.
- Avoid when task durations or priorities are too uncertain for the rule to be meaningful.
What It Does
- Ranks ready work with a scheduling rule
- Updates waiting time, deadlines, or capacity
- Returns an order, assignment, or admission decision
Use Cases
- CPU scheduling
- Network queue management
- Workflow and batch processing
Inputs
- Jobs or requests
- Timing constraints
- Resource limits
Outputs
- Execution order
- Resource assignment
- Timing decision
Key Formulas (1)
Bucket drain
queuenext = max(0, queue + arrivals − drainrate · δtime)
queue_next = max(0, queue + arrivals - drain_rate * delta_time)Smooths bursts by draining queued work at a fixed rate.
Pseudocode
- 1.Collect ready jobs, queues, or tasks
- 2.Compute the method's priority, fairness, or capacity score
- 3.Select the next job or resource assignment
- 4.Update waiting time, capacity, or completion state
- 5.Repeat until all work is scheduled or admitted
Canonical Example
- Input
- jobs = [{id:A, time:3}, {id:B, time:1}], resource = one worker
- Output
- ordered or assigned jobs according to the scheduling rule
- Explanation
- Leaky Bucket Scheduling computes the priority or capacity rule and chooses the next job from the ready set.
Implementation Notes
- Make tie-breaking deterministic and visible in tests.
- Track waiting time, service time, and resource state separately.
- State whether the policy is preemptive and what fairness, latency, or deadline objective it optimizes.
Common Pitfalls
- Forgetting tie-breaking rules makes schedules unstable across runs.
- Ignoring starvation and fairness edge cases can make good averages hide bad tail behavior.
- Ignoring preemption cost, release times, or starvation can make a schedule look correct only in toy cases.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow queued jobs moving onto processors, links, or time slots as the scheduling rule changes priorities.
Step 1 of 5: Collect ready jobs, queues, or tasks
schedulingNotes
Leaky Bucket Scheduling operates in O(n log n) time and O(n) space within the Scheduling family. Key governing relation: queue_next = max(0, queue + arrivals - drain_rate * delta_time). Often compared with Round Robin Scheduling and Priority Scheduling.
Sources (1)
What each reference supports for this entry.
Computer Networking: A Top-Down Approach
BookNetworking reference for Leaky Bucket Scheduling traffic shaping, rate smoothing, and queue drain behavior.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborRound Robin Scheduling
Leaky Bucket Scheduling and Round Robin Scheduling address nearby scheduling problems but make different implementation tradeoffs.
Related Algorithms
Tags
Scheduling