Name
Abstract | ||
|---|---|---|
This paper is devoted to automatic competitive analysis of real-time scheduling algorithms for firm-deadline tasksets, where only completed tasks contribute some utility to the system. Given such a taskset , the competitive ratio of an on-line scheduling algorithm for is the worst-case utility ratio of over the utility achieved by a clairvoyant algorithm. We leverage the theory of quantitative graph games to address the and problems. For the competitive analysis case, given any taskset and any finite-memory on-line scheduling algorithm , we show that the competitive ratio of in can be computed in polynomial time in the size of the state space of . Our approach is flexible as it also provides ways to model meaningful constraints on the released task sequences that determine the competitive ratio. We provide an experimental study of many well-known on-line scheduling algorithms, which demonstrates the feasibility of our competitive analysis approach that effectively replaces human ingenuity (required for finding worst-case scenarios) by computing power. For the competitive synthesis case, we are just given a taskset , and the goal is to automatically synthesize an optimal on-line scheduling algorithm , i.e., one that guarantees the largest competitive ratio possible for . We show how the competitive synthesis problem can be reduced to a two-player graph game with partial information, and establish that the computational complexity of solving this game is -complete. The competitive synthesis problem is hence in in the size of the state space of the non-deterministic labeled transition system encoding the taskset. Overall, the proposed framework assists in the selection of suitable scheduling algorithms for a taskset, which is in fact the most common situation in real-time systems design. |
Year | DOI | Venue |
|---|---|---|
2018 | https://doi.org/10.1007/s11241-017-9293-4 | Real-Time Systems |
Keywords | Field | DocType |
Real-time scheduling,Firm-deadline tasks,Competitive analysis,Quantitative graph games | Graph,Scheduling (computing),Computer science,Real-time computing,Labeled transition system,Time complexity,State space,Competitive analysis,Distributed computing,Computational complexity theory | Journal |
Volume | Issue | ISSN |
54 | 1 | 0922-6443 |
Citations | PageRank | References |
0 | 0.34 | 28 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Krishnendu Chatterjee | 1 | 2179 | 162.09 |
| Andreas Pavlogiannis | 2 | 79 | 13.21 |
| Alexander Kößler | 3 | 8 | 1.85 |
| Ulrich Schmid | 4 | 127 | 17.24 |