A Framework for Automated Competitive Analysis of On-line Scheduling of Firm-Deadline Tasks

Krishnendu Chatterjee, Andreas Pavlogiannis, Alexander Kößler, Ulrich Schmid

Introduction

In real-time systems, "firm-deadline" tasks represent a unique challenge: they provide value if completed on time but zero value if they miss their deadline. Unlike hard-deadline tasks, missing a firm deadline does not result in system failure, but unlike soft-deadline tasks, there is no benefit to completing them late. The primary challenge for an on-line scheduler is making real-time decisions without knowledge of future task arrivals.

Traditionally, researchers evaluate these schedulers using competitive analysis, comparing the utility gained by an on-line algorithm against an "all-knowing" clairvoyant scheduler. However, determining the worst-case scenario to prove an algorithm's competitive ratio has historically required significant mathematical intuition and manual proof construction. This paper introduces an automated framework that replaces human ingenuity with algorithmic power, allowing engineers to analyze specific tasksets relevant to their unique applications.

Methodology: From Proofs to Computation

The core of the proposed framework is the reduction of the scheduling problem to a multi-objective graph analysis. This is achieved through several key components:

Labeled Transition Systems (LTSs)

Both the scheduling algorithms and the "adversary" (the process generating task sequences) are modeled as Labeled Transition Systems. This formal representation allows the framework to capture complex system behaviors, such as task states and available transitions, in a structured format.

Example of a Labeled Transition System (LTS) representing a scheduling state space.

Modeling Constraints and Adversaries

To reflect real-world conditions, the framework models constraints like sporadicity (minimum time between tasks) or limit-average load as automata. By restricting the adversary, researchers can see how an algorithm performs under specific environmental conditions rather than just the theoretical worst-case for all possible tasksets.

An automaton representing constraints on the task-generating adversary, used to model environmental restrictions.

Algorithmic Optimization

To combat the "state space explosion" inherent in combining multiple LTSs into a massive product graph, the authors introduced optimizations such as a specialized "ClairvoyantSuccessor" algorithm and "lazy dropping" to prune redundant states. To find the exact competitive ratio, the framework employs an adaptive binary search that exploits the graph structure for faster convergence.

Key Insights and Results

The framework was evaluated using several synthetic tasksets (Sets A, B, and C) designed to test scalability and performance under varying importance ratios and deadlines.

The Myth of the Universal Scheduler

One of the most significant findings is that no single algorithm is universally optimal. While certain algorithms like $D^{over}$ are theoretically optimal for general worst-case scenarios, the automated analysis revealed that simpler schedulers like FIFO (First-In-First-Out) or SRT (Shortest Remaining Time) actually performed better for many specific tasksets. In head-to-head comparisons of EDF, SRT, SP, FIFO, DSTAR, and DOVER, every single algorithm emerged as the "winner" for at least one specific configuration.

The Impact of Constraints

The research demonstrated that the "best" algorithm changes non-monotonically as system constraints are tightened. For instance, an algorithm might be optimal at 80% load but underperform at 60% load. This non-intuitive behavior underscores the necessity of automated tools, as human intuition often fails to predict these shifts in performance.

Conclusion and Future Work

By shifting the burden of proof from researchers to algorithms, this framework allows for a more nuanced understanding of on-line scheduling. The tool can handle tasksets with up to 5 tasks and deadlines of 44 slots, generating product graphs with over 16,000 nodes in minutes.

While currently focused on single-processor systems, future work aims to extend this framework to multi-processor environments and incorporate broader constraints such as energy consumption limits, further bridging the gap between theoretical scheduling models and modern embedded system requirements.

Summary updated

BibTeX
@inproceedings{chatterjee2014framework,
  author = {Krishnendu Chatterjee and Andreas Pavlogiannis and Alexander Kößler and Ulrich Schmid},
  title = {{A Framework for Automated Competitive Analysis of On-line Scheduling of Firm-Deadline Tasks}},
  booktitle = {RTSS},
  year = {2014},
  doi = {10.1109/rtss.2014.9},
}
Figure