IEEE Transactions on Computers · 2018 · 60 citations · 30 references
ComputingComputer EngineeringComputer SystemsOptimizationReal-time SystemsSchedulingCpu SchedulingEarliest Deadline First SchedulingReal-time SchedulingResource-constrained SchedulingSchedulability AnalysisTask SchedulingEarliest Deadline First SchedulabilityMixed-criticality SchedulingProcessor Utilization BoundsReal-time Task Set AnalysisScheduling With DeadlinesUniprocessor Earliest Deadline First SchedulingUniprocessor Mixed-criticality SystemsUtilization-based Tests
In this paper, we study the scheduling problem of the imprecise mixed-criticality model (IMC) under earliest deadline first with virtual deadline (EDF-VD) scheduling upon uniprocessor systems. Two schedulability tests are presented. The first test is a concise utilization-based test which can be applied to the implicit deadline IMC task set. The suboptimality of the proposed utilization-based test is evaluated via a widely-used scheduling metric, speedup factors. The second test is a more effective test but with higher complexity which is based on the concept of demand bound function (DBF). The proposed DBF-based test is more generic and can apply to constrained deadline IMC task set. Moreover, in order to address the high time cost of the existing deadline tuning algorithm, we propose a novel algorithm which significantly improve the efficiency of the deadline tuning procedure. Experimental results show the effectiveness of our proposed schedulability tests, confirm the theoretical suboptimality results with respect to speedup factor, and demonstrate the efficiency of our proposed algorithm over the existing deadline tunning algorithm. In addition, issues related to the implementation of the IMC model under EDF-VD are discussed.
30
Techniques for Multiprocessor Global Schedulability Analysis
Sanjoy Baruah · 2007 · 695 citations
Algorithms for scheduling imprecise computations
J.W.S. Liu, Kuo-Yi Lin, Wen-Chieh Shih et al. · Computer · 1991 · 528 citations