Schedulability Test for Strictly Periodic Tasks on Uniprocessor Platform

doi:10.3969/j.issn.1000-3428.2016.05.050

Abstract

Abstract:

Aiming at the problem of schedulability test for strictly periodic tasks in theoretical study of system scheduling,this paper researches the interference relationship between strictly periodic tasks in a real-time system,and presents an eigentask-based schedulability test method.It analyzes the time constraints of strictly periodic tasks running on a uniprocessor platform,calculates all free time,and provides a sufficient and necessary schedulability test condition by determining whether enough continuous free time is available for the task’s execution.Experimental results show that,compared with Eigen-mapping Task Assignment(EMTA) method,the proposed method can reduce the time consumption required for the test and improve the success ratio.It has better schedulability test performance.

Key words: strictly periodic task, schedulability test, uniprocessor, eigentask, real-time system, free time

摘要：

针对系统调度理论研究中的严格周期任务可调度性判定问题,从研究实时系统中严格周期任务之间的相互干涉关系出发,提出一种基于特征任务的可调度性判定方法。分析严格周期任务在单一处理器平台下无冲突运行的时间约束,计算任务所能使用的全部空余时间,进而界定连续空余时间是否满足任务执行的需要,得到一个可调度性判定的充要条件。实验结果表明,与特征映射任务分配方法相比,该方法能够减少判定时间,提高判定成功率,具有更优的可调度判定性能。

关键词: 严格周期任务, 可调度性判定, 单处理器, 特征任务, 实时系统, 空余时间

CLC Number:

TP316.2

CHEN Jinchao,DU Chenglie. Schedulability Test for Strictly Periodic Tasks on Uniprocessor Platform[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2016.05.050.

陈进朝,杜承烈. 单处理器平台下的严格周期任务可调度性判定[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2016.05.050.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2016.05.050

http://www.ecice06.com/EN/Y2016/V42/I5/288

References

参考文献［1］Jeffay K,Stanat D,Martel C.On Non-preemptive Scheduling of Period and Sporadic Tasks［C］//Proceedings of the 12th Real-time Systems Symposium.Washington D.C.,USA:IEEE Computer Society,1991:129-139. ［2］Kermia O,Sorel Y.Schedulability Analysis for Non-preemptive Tasks Under Strict Periodicity Constraints［C］//Proceedings of the 14th IEEE International Conference on Embedded and Real-time Computing Systems and Appli- cations.Washington D.C.,USA:IEEE Press,2008:25-32. ［3］张永悦,孙瑜,李允,等.复杂实时系统可调度性判定工具的研究与实现［J］.计算机工程,2013,39(1):270-274. ［4］毛羽刚,张拥军,金士尧,等.一种改进的分布强实时系统可调度性分析算法［J］.软件学报,2001,12(2):298-302. ［5］王永吉,陈秋萍.单调速率及其扩展算法的可调度性判定［J］.软件学报,2004,15(6):799-814. ［6］徐建华,李允.基于单调速率的可调度性判定改进算法［J］.计算机工程,2011,37(22):45-47. ［7］Korst J.Periodic Multiprocessor Scheduling［D］.Eindhoven,the Netherlands:Eindhoven University of Tech-nology,1991. ［8］Baruah S,Chakraborty S.Schedulability Analysis of Non-preemptive Recurring Real-time Tasks［C］//Proceedings of the 20th International Parallel and Distributed Processing Symposium.Washington D.C.,USA:IEEE Computer Society,2006. ［9］Chen Jinchao,Du Chenglie,Xie Fei,et al.Schedulability Analysis of Non-preemptive Strictly Periodic Tasks in Multi-core Real-time Systems［J］.Real-Time Systems,2015,51(1):1-33. ［10］Marouf M,Sorel Y.Scheduling Analysis for Non-preemptive Hard Real-time Tasks with Strict Period［C］//Proceedings of the 16th International Conference on Emerging Technologies and Factory Automation.Washington D.C.,USA:IEEE Press,2011:1-8. ［11］Al-Sheikh A,Brun O,Hladik P E,et al.Strictly Periodic Scheduling in IMA-based Architectures［J］.Real-Time Systems,2012,48(4):359-386. ［12］Korst J,Aarts E,Lenstra J,et al.Periodic Multiprocessor Scheduling［M］//Aarts E H L,van Leeuwen J,Rem M.PARLE’91 Parallel Architectures and Languages Europe.Berlin,Germany:Springer-Verlag,1991. ［13］Kunth D E.The Art of Computer Programming［M］.New York,USA:Addison-Wesley Educational Publishers Inc.,1973. ［14］Pira C,Artigues C.Line Search Method for Solving a Non-preemptive Strictly Periodic Scheduling Problem［J］.Journal of Scheduling,2014,31(6):1-17. ［15］Al-Sheikh A,Brun O,Hladik P E,et al.A Best-response Algorithm for Multiprocessor Periodic Scheduling［C］//Proceedings of the 23rd Euromicro Conference on Real-time Systems.Washington D.C.,USA:IEEE Press,2011:228-237. 编辑金胡考

[1]	CUI Liqun,GUO Xiangzhuo,GUO Jun,HUANG Diwen. Overload control strategy for sporadic real-time system [J]. Computer Engineering, 2019, 45(6): 108-114.
[2]	LIANG Hao,YAN Li,SHEN Xiangjun. Analysis of Real-time Scheduling Algorithm with Global Fixed Priority [J]. Computer Engineering, 2017, 43(12): 65-68.
[3]	QIAN Guangming,LIANG Liwen. Research on Transient Process for Bandwidth Transfer of Real-time Multitask [J]. Computer Engineering, 2017, 43(12): 292-295,302.
[4]	MA Li,ZHONG Yong,HUO Yin-yu. Formal Study of Soft Realtime System Based on Obligation Policy [J]. Computer Engineering, 2014, 40(8): 302-309.
[5]	ZHANG Xiao-long,GUO Rui-feng,TAO Yao-dong,LIU Sheng. Research of Linux Real-time Preemption Patch and Real-time Performance Measure [J]. Computer Engineering, 2014, 40(10): 304-307,313.
[6]	GUO Ming-kun, CHAI Zhi-lei. Method Call Mechanism of Embedded Java Processor [J]. Computer Engineering, 2014, 40(1): 68-71.
[7]	LUAN Tian-jiao, CHEN Yi-xiang, WANG Jiang-tao. Maude Rewriting System of Specification Language STeC for Real-time System [J]. Computer Engineering, 2013, 39(10): 57-62,67.
[8]	ZHANG Yong-Yue, SUN Yu, LI Yuan, XU Jian-Hua. Research and Implementation of Schedulability Determination Tools in Complex Real-time System [J]. Computer Engineering, 2013, 39(1): 270-274.
[9]	XU Miao, LI Yuan, GUI Cheng-Lin, LUO Lei. Schedule Analysis Tool for Embedded System Based on Timed Automata [J]. Computer Engineering, 2012, 38(3): 290-292.
[10]	JIANG Jian-Chun, LIU Chao. Design and Realization of Communication Middleware for Distributed Real-time System [J]. Computer Engineering, 2012, 38(21): 249-252,256.
[11]	ZHANG Jie, CHEN Xiang-Ning, XU Chao-Yong. A Management Model for Peripherals of Priority Inversion Inhibition [J]. Computer Engineering, 2012, 38(20): 272-274.
[12]	ZHANG Yu-Dong, XU Cheng, YANG Zhi-Bang. Real-time Schedule Algorithm Based on Feedback Control [J]. Computer Engineering, 2012, 38(2): 279-281.
[13]	SHU Xue-Qiang, XU Cheng, LIU Pan, YANG Zhi-Bang. Adaptive Elastic Schedule Algorithm Based on Feedback Mechanism [J]. Computer Engineering, 2012, 38(2): 276-278.
[14]	XU Jian-Hua, LI Yuan. Task Set Schedulability Test Tools Based on Simulation Method [J]. Computer Engineering, 2012, 38(2): 237-239.
[15]	YUAN Shu, YAN Li. Global EDF Judgment Method for Multiprocessor Based on Workload Calculation [J]. Computer Engineering, 2012, 38(12): 287-290.

Please choose a citation manager

Content to export