An optimal resource sharing protocol for generalized multiframe tasks

Pontus Ekberg, Nan Guan, Martin Stigge, Wang YiJ. Log. Algebraic Methods Program 2015 · DOI

TL;DR

This paper introduces EDF+RDP, an optimal scheduling algorithm for real-time systems with generalized multiframe (GMF) tasks that share resources. It also provides a necessary and sufficient feasibility test for such systems, addressing a critical gap in scheduling complex real-time workloads.

What Problem Does This Paper Address?

Real-time systems often involve tasks that need to access shared resources (like peripherals or data structures) exclusively. While scheduling algorithms and feasibility tests exist for simpler task models (like sporadic tasks), they become suboptimal or inapplicable for more flexible models like Generalized Multiframe (GMF) tasks. GMF tasks allow for more complex job-release patterns, making them suitable for a wider range of systems but also significantly complicating resource sharing analysis. The challenge is to develop an optimal scheduling strategy and a precise feasibility test that can handle the intricate interactions between flexible task behaviors and shared resource contention.

Methods

The core contribution is the EDF+RDP (Earliest Deadline First + Resource Deadline Protocol) algorithm. This algorithm extends the standard EDF by introducing "virtual deadlines" for jobs. These virtual deadlines incorporate not only the job's absolute deadline but also the urgency of releasing resources it holds. This urgency is quantified by a novel concept called Resource Deadline, which estimates the earliest possible deadline of a future job that might need a specific resource.

The paper also proposes a feasibility test for GMF-R (GMF tasks with Resources) task sets. This test is based on demand-bound functions (dbf), a standard technique for analyzing task workloads. It introduces a resource-constrained demand-bound function to account for jobs that might be blocked by resource contention. The feasibility test consists of two conditions:

  • Condition A: Ensures that the total workload of tasks within any time interval doesn't exceed the interval's length, assuming no resource waits.
  • Condition B: Addresses scenarios where resource waiting is involved, considering the impact of a task holding a resource on other tasks needing it.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithm design, using example task sets for illustration rather than large-scale datasets.

Key Insights and Ideas

  • Virtual Deadlines for Resource Urgency: The key insight is that a job's priority shouldn't just depend on its own deadline but also on the potential impact of it holding a resource that others might need. Virtual deadlines elegantly capture this combined urgency.
  • Resource Deadlines as Predictors: The concept of a resource deadline provides a crucial mechanism to predict future resource contention and inform scheduling decisions. It allows the system to proactively manage resource access.
  • Optimality for Complex Tasks: Achieving optimality for GMF tasks with resources is a significant breakthrough, as previous methods were either suboptimal or limited to simpler task models.
  • Feasibility Test Complexity: The proposed feasibility test is shown to be both necessary and sufficient, and its complexity is pseudo-polynomial for bounded-utilization task sets, making it practical.
  • Implicit Mutual Exclusion: The EDF+RDP algorithm inherently prevents direct blocking on resources, meaning explicit locking mechanisms might not be strictly necessary, simplifying implementation.

Key Results

  • EDF+RDP Optimality: The paper proves that EDF+RDP is an optimal scheduling algorithm for GMF-R task sets. This means if a task set is schedulable, EDF+RDP will schedule it.
  • Necessary and Sufficient Feasibility Test: The developed feasibility test is proven to be both necessary and sufficient for GMF-R task sets.
  • Bounded Preemptions and Stack Sharing: The algorithm guarantees at most one preemption per job release and allows all jobs to share a common run-time stack, simplifying implementation and reducing memory overhead.
  • Deadlock Freedom: The EDF+RDP algorithm is proven to be deadlock-free.

Limitations and Future Work

  • Optimality Loss for More General Models: While EDF+RDP is optimal for GMF-R tasks, the paper notes that its optimality is lost if applied to more general task models with arbitrary directed graphs (like the digraph real-time task model) due to non-deterministic branching.
  • Nested Resource Accesses: The paper mentions that the absolute-time ceiling protocol by Guan et al. restricts itself to systems without nested resource accesses, implying this might be a limitation for some applications of EDF+RDP, though the protocol itself handles nesting.
  • Future Work: The paper suggests that the developed framework can be used in hierarchical scheduling and compositional analysis. It also mentions that the feasibility test can be extended to scenarios with multiple virtual servers by replacing the processor supply bound with a supply-bound function. The authors also note that while their bound for checking feasibility values of 'l' is correct, a tighter bound could further speed up implementations.

Summary updated

BibTeX
@article{ekberg2015optimal,
  author = {Pontus Ekberg and Nan Guan and Martin Stigge and Wang Yi},
  title = {{An optimal resource sharing protocol for generalized multiframe tasks}},
  journal = {J. Log. Algebraic Methods Program.},
  year = {2015},
  doi = {10.1016/j.jlamp.2014.10.001},
}
Figure