Handling Transients of Dynamic Real-Time Workload Under EDF Scheduling

被引:13
作者
Casini, Daniel [1 ]
Biondi, Alessandro [1 ]
Buttazzo, Giorgio [1 ]
机构
[1] Scuola Super Sant Anna, TeCIP Inst, I-56124 Pisa, Italy
关键词
Real-time systems; scheduling transients; dynamic workload; mode change; schedulability analysis; deadline-based scheduling; SYSTEMS;
D O I
10.1109/TC.2018.2882451
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Real-time dynamic workload consists of tasks that can arbitrarily join and leave the system at run-time. To avoid incurring deadline misses, tasks that request to join the system must pass an admission test, which has to cope with potential scheduling transients originated by the residual effect of the tasks that previously left the system. This phenomenon may require some tasks to suffer an admission delay before being accepted for execution. This paper focuses on uniprocessor earliest-deadline first (EDF) scheduling with constrained deadlines and explicitly considers methods for handling scheduling transients in the presence of dynamic real-time workload. A generalized analysis framework is first presented to overcome several limitations of the existing approaches (including the support for overlapping transients), and is then used to derive methods for computing bounds on the admission delays incurred by tasks. Building on such results, an on-line protocol is proposed to handle the admission control of a dynamic workload, which also comes with a variant that can execute in polynomial time to favor its practical application. Furthermore, the paper shows how the presented analysis can be used off-line for analyzing mode-changes among static task sets. Experimental results are finally presented to evaluate the proposed algorithms.
引用
收藏
页码:820 / 835
页数:16
相关论文
共 39 条
[1]  
Ahmed M., 2012, 2012 IEEE 18th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2012), P154, DOI 10.1109/RTCSA.2012.49
[2]  
Andersson B, 2005, RTAS 2005: 11TH IEEE REAL TIME AND EMBEDDED TECHNOLOGY AND APPLICATIONS SYMPOSIUM, PROCEEDINGS, P76
[3]  
Andersson B, 2008, LECT NOTES COMPUT SC, V5401, P572, DOI 10.1007/978-3-540-92221-6_43
[4]  
[Anonymous], 2015, AUTOSAR 4 2 OS SPECI
[5]   Preemptive Uniprocessor Scheduling of Mixed-Criticality Sporadic Task Systems [J].
Baruah, Sanjoy ;
Bonifaci, Vincenzo ;
D'Angelo, Gianlorenzo ;
Li, Haohan ;
Marchetti-Spaccamela, Alberto ;
van der Ster, Suzanne ;
Stougie, Leen .
JOURNAL OF THE ACM, 2015, 62 (02)
[6]   ALGORITHMS AND COMPLEXITY CONCERNING THE PREEMPTIVE SCHEDULING OF PERIODIC, REAL-TIME TASKS ON ONE PROCESSOR [J].
BARUAH, SK ;
ROSIER, LE ;
HOWELL, RR .
REAL-TIME SYSTEMS, 1990, 2 (04) :301-324
[7]   Schedulability Analysis of Global Scheduling Algorithms on Multiprocessor Platforms [J].
Bertogna, Marko ;
Cirinei, Michele ;
Lipari, Giuseppe .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2009, 20 (04) :553-566
[8]   Measuring the performance of schedulability tests [J].
Bini, E ;
Buttazzo, GC .
REAL-TIME SYSTEMS, 2005, 30 (1-2) :129-153
[9]   Fine-grained task reweighting on multiprocessors [J].
Block, A ;
Anderson, JH ;
Bishop, G .
11TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS, PROCEEDINGS, 2005, :429-435
[10]  
Block A., 2006, P 12 INT C PARALLEL, P355