README
¶
Earliest Deadline First (EDF) Ordering Policy
Type: edf-ordering-policy
The Earliest Deadline First (EDF) ordering policy selects requests based on their absolute deadline, prioritizing requests that are closest to expiring.
Why Choose This Policy?
- SLO Awareness: Best suited for workloads with strict latency Service Level Objectives (SLOs) or Time-To-Live (TTL) requirements.
- Minimizes Timeout Rates: By prioritizing requests that are about to expire, it helps maximize the number of requests completed before their deadline.
- Graceful Degradation: Requests without a deadline are still processed but are yielded to time-sensitive requests.
What It Does
The EDF policy computes an absolute deadline for each request as:
Deadline = EnqueueTime + EffectiveTTL
- Requests with earlier absolute deadlines are prioritized.
- If two requests have the same deadline, FCFS (First-Come, First-Served) is used as a tie-breaker based on logical enqueue time.
- Requests without a valid TTL (i.e.,
EffectiveTTL <= 0) are treated as having no deadline and are assigned a far-future deadline, ensuring they are scheduled after all time-bound requests.
Inputs consumed
This policy inspects the following attributes of the request item:
- Logical Enqueue Time: Used as the arrival timestamp and as a tie-breaker.
- Effective TTL: Used to calculate the absolute deadline.
Behavior and Queue Pairing
Unlike FCFS, this policy requires specific queue capabilities to function correctly.
- Required Capability:
CapabilityPriorityConfigurable(e.g., a heap-based priority queue). - This policy cannot be paired with a simple FIFO list queue because it must maintain items in a sorted order that changes as new items arrive with different deadlines.
Configuration
This policy does not require any custom parameters.
orderingPolicyRef: edf-ordering-policy
Trade-offs
- Starvation Risk: If there is a continuous stream of requests with tight deadlines, requests with loose or no deadlines may be starved and never processed.
- Computational Overhead: Maintaining a priority heap incurs higher CPU overhead ($O(\log n)$ for insertions and deletions) compared to a simple FIFO list ($O(1)$).
Related Documentation
Documentation
¶
Overview ¶
Package edf implements an ordering policy that selects requests based on their absolute deadlines (Earliest Deadline First).
For detailed documentation, see README.md.
Index ¶
Constants ¶
const EDFOrderingPolicyType = "edf-ordering-policy"
EDFOrderingPolicyType is the registration type for the EDF ordering policy.
It selects the request with the earliest absolute deadline. For detailed documentation, see README.md.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type EDFPolicy ¶
type EDFPolicy struct {
// contains filtered or unexported fields
}
Requests with earlier absolute deadlines (EnqueueTime + EffectiveTTL) are dispatched first. See the documentation for the exported EDFOrderingPolicyType constant for detailed behavioral guarantees.
func (*EDFPolicy) Less ¶
func (p *EDFPolicy) Less(a, b flowcontrol.QueueItemAccessor) bool
Less returns true if item 'a' should be dispatched before item 'b'. EDF orders by deadline (earliest first), using FCFS as a tie-breaker.
func (*EDFPolicy) RequiredQueueCapabilities ¶
func (p *EDFPolicy) RequiredQueueCapabilities() []flowcontrol.QueueCapability
RequiredQueueCapabilities returns the queue capabilities required by this policy. It requires a priority-configurable queue (e.g., heap-based) to maintain items in deadline-sorted order.
Source Files