《计算机应用研究》|Application Research of Computers

全局EDZL实时调度算法的可调度性判定

Schedulability test of global EDZL real-time scheduling algorithm

免费全文下载 (已被下载 次)  
获取PDF全文
作者 梁浩,晏立,沈项军
机构 江苏大学 a.研究生院;b.计算机科学与通信工程学院,江苏 镇江 212013
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2018)08-2347-04
DOI 10.3969/j.issn.1001-3695.2018.08.026
摘要 可调度性判定就是离线验证实时系统中所有任务是否可调度。通过可调度性判定,能够更好地保证实时系统的可靠性。分析在多处理器实时系统中全局EDZL算法的任务需求,考虑了带入作业和带出作业对处理器资源的需求。引入最大连续忙区间的概念,以确定带入作业的最大个数,得到了多处理器实时系统中全局EDZL算法的可调度性判定算法。通过构造大量实时任务集,对不同的判定方法进行了实验,检查通过可调度性判定的任务集数量。实验结果表明,这种方法在多处理器实时系统中是一种更为紧密的可调度性判断方法。
关键词 实时系统;多处理器;全局EDZL算法;可调度性判定;最大连续忙区间
基金项目 国家自然科学基金资助项目(61572240)
本文URL http://www.arocmag.com/article/01-2018-08-026.html
英文标题 Schedulability test of global EDZL real-time scheduling algorithm
作者英文名 Liang Hao, Yan Li, Shen Xiangjun
机构英文名 a.GraduateSchool,b.SchoolofComputerScience&TelecommunicationEngineering,ZhenjiangJiangsu212013,China
英文摘要 The schedulability test is to verify whether all the tasks in the real-time system can be scheduled off-line.It can better guarantee the reliability of real-time system through the schedulability test.This paper considered the processor resource demands of the carry-in jobs and the carry-out jobs based on the requirement analysis of the global EDZL algorithm in the multiprocessor real-time system.It introduced the concept of maximal continuous busy interval to determine the maximum number of the carry-in jobs, and presented the schedulability test algorithm of global EDZL algorithm.By constructing a large number of real-time task sets, it carried out experiments on different test methods, and checked the number of task sets that can be passed by schedulability test.Experimental results show that this method is a more close schedulability test method in multiprocessor real-time system.
英文关键词 real-time system; multiprocessor; global EDZL algorithm; schedulability test; maximal continuous busy interval
参考文献 查看稿件参考文献
  [1] Baker T P. Multiprocessor EDF and deadline monotonic schedulability analysis[C] //Proc of the 24th Real-Time Systems Symposium. Piscataway, NJ:IEEE Press, 2003:120-129.
[2] Lpez J M, Diaz J L, Garcia D F. Utilization bounds for EDF scheduling on real-time multiprocessor systems[J] . Real-Time Systems, 2004, 28(1):39-68.
[3] Park M, Han S, Kim H, et al. Comparison of deadline-based scheduling algorithms for periodic real-time tasks on multiprocessor[J] . IEICE Trans on Information & System, 2005, E88-D(3):658-661.
[4] Cho S, Lee S K, Ahn S, et al. Efficient real-time scheduling algorithms for multiprocessor systems[J] . IEICE Trans on Communications, 2002, E85-B(12):2859-2867.
[5] Davis R I, Burns A. A survey of hard real-time scheduling for multiprocessor systems[J] . ACM Computing Surveys, 2011, 43(4):88-129.
[6] Bertogna M, Cirinei M, Lipari G. Schedulability analysis of global scheduling algorithms on multiprocessor platforms[J] . IEEE Trans on Parallel and Distributed Systems, 2009, 20(4):553-566.
[7] Lee J, Shin I. EDZL Schedulability analysis in real-time multicore scheduling[J] . IEEE Trans on Software Engineering, 2013, 39(7):910-916.
[8] Lee J, Shin I. Demand-based schedulability analysis for real-time multi-core scheduling[J] . Journal of Systems and Software, 2014, 89(7):99-108.
[9] Sun Youcheng, Lipari G. Response time analysis with limited carry-in for global earliest deadline first scheduling[C] //Proc of IEEE Real-Time Systems Symposium. Piscataway, NJ:IEEE Press, 2015:1-23.
[10] Lee J. Time-reversibility of schedulability tests[C] //Proc of IEEE Real-Time Systems Symposium. Washington DC:IEEE Computer Society, 2014:294-303.
[11] Baruah S. Techniques for multiprocessor global schedulability analysis[C] //Proc of the 28th IEEE International Real-Time Systems Symposium. Washington DC:IEEE Computer Society, 2007:119-128.
[12] Baker T P, Cirinei M. A necessary and sometimes suffcient condition for the feasibility of sets of sporadic hard-deadline tasks[C] //Proc of the 27th IEEE International Real-Time Systems Symposium. Piscataway, NJ:IEEE Press, 2006:178-190.
[13] 梁浩, 晏立. 实时调度 EDZL 算法的可调度性判定[J] . 计算机工程与应用, 2011, 47(2):60-61, 152.
收稿日期 2017/4/5
修回日期 2017/6/1
页码 2347-2350
中图分类号 TP316.2
文献标志码 A