硬实时任务调度IO抖动与延迟的建模优化及算法实现
|
摘要
嵌入式实时系统越来越多的应用于工业控制等行业中,实时调度一直是其核心理论问题。但是,调度产生的硬实时任务抖动与延迟直接影响到系统的稳定性和可靠性,甚至导致系统崩溃。因此,如何控制硬实时任务的抖动与延迟已成当前实时调度理论研究的热点问题。
针对任务的延迟和抖动问题,本文在引入了实时系统中任务的抖动和延迟评价体系的基础上提出了一种基于任务分割的可抢占阈值调度模型。该模型可以在不影响系统的可调度性前提下,减少任务调度所带来的任务的抖动和延迟。利用该模型对任务的IO抖动进行分析,结果表明任务的IO抖动会随可抢占阂值的减小而降低。通过最小化可抢占阈值调度模型中的阈值,可以减少硬实时任务的抖动和延迟,控制调度对系统稳定性带来的负面影响。本文依据RM调度算法充要条件为RM算法提出了复杂度为O(|Tn/T1|·n2)的最优化阈值分配算法,并依据EDF调度算法充分条件为EDF调度算法提出了复杂度为O(n)的次优化阈值分配算法。为了测试模型在不同的调度情况下的表现,本文在1matlab上利用TORSCHE工具箱搭建仿真测试环境,对可抢占阈值调度模型进行仿真。从仿真结果可知,基于任务分割的可抢占阈值调度模型可以在典型的调度方法中有效的降低调度程序所带来的任务的延迟和抖动。为了衡量该模型理论与该模型实现后的差距,本文在Atmel mega128硬件平台上,通过对现有的WORIX操作系统内核的修改,硬件模拟了该调度算法。通过对比硬件模拟测试结果与仿真结果可知,该模型的仿真结果与实际情况比较吻合,即该模型在实际应用中可以有效的降低任务的抖动和延迟。
Embedded real-time system is more and more being used in the industrial control field and real-time scheduling has always been the core theory issue. But the jitter and latency of hard real-time task caused by scheduling directly influences the stability and reliability of systems, even leads to the collapse of systems. Therefore, how to control the jitter and latency of hard real-time task has become the hot issue in the current real-time scheduling theory research.
In view of the task jitter and latency question, this thesis provide a preemptable threshold scheduling model which divides the task. This model can reduce the task jitter and latency caused by task scheduling when it does not affect the system scheduling. Using this model to analyze IO jitter of the task, the results showed that the IO jitter of the task reduced along with decrease of the preemptable threshold. By the way of minimizing threshold of the preemptable threshold scheduling model, it can reduce the jitter and latency of hard real-time task and control the negative influence of the system stability caused by the control scheduling. According as the necessary and sufficient Conditions of RM Scheduling Algorithm, this paper presents an optimal threshold value allocation algorithm by the complexity of O(|Tn/T1|·n2) and according as sufficient Conditions of EDF Scheduling Algorithm presents a better threshold value allocation algorithm with complexity of O(n). To test the performance of the model in different scheduling circumstances, this paper structured a simulation testing environment on the TORSCHE toolbox of Matlab and carried on the simulation to the preemptable threshold scheduling algorithm. From the simulation results, it can be easily seen that the preemptable threshold scheduling model based on the division of tasks can effectively reduce the jitter and latency of tasks caused by scheduler in the typical scheduling algorithm. In order to measure the difference between the model theory and the model after the realization, this paper carried on a hardware simulation to the scheduling algorithm in Atmel megal28 hardware platforms, through modifications to the existing WORIX OS kernel. By comparing the hardware test results with the simulation results, the author found that the model simulation results accord with the actual situation, that is, the model can effectively reduce the jitter and latency of tasks in the practical application.
针对任务的延迟和抖动问题,本文在引入了实时系统中任务的抖动和延迟评价体系的基础上提出了一种基于任务分割的可抢占阈值调度模型。该模型可以在不影响系统的可调度性前提下,减少任务调度所带来的任务的抖动和延迟。利用该模型对任务的IO抖动进行分析,结果表明任务的IO抖动会随可抢占阂值的减小而降低。通过最小化可抢占阈值调度模型中的阈值,可以减少硬实时任务的抖动和延迟,控制调度对系统稳定性带来的负面影响。本文依据RM调度算法充要条件为RM算法提出了复杂度为O(|Tn/T1|·n2)的最优化阈值分配算法,并依据EDF调度算法充分条件为EDF调度算法提出了复杂度为O(n)的次优化阈值分配算法。为了测试模型在不同的调度情况下的表现,本文在1matlab上利用TORSCHE工具箱搭建仿真测试环境,对可抢占阈值调度模型进行仿真。从仿真结果可知,基于任务分割的可抢占阈值调度模型可以在典型的调度方法中有效的降低调度程序所带来的任务的延迟和抖动。为了衡量该模型理论与该模型实现后的差距,本文在Atmel mega128硬件平台上,通过对现有的WORIX操作系统内核的修改,硬件模拟了该调度算法。通过对比硬件模拟测试结果与仿真结果可知,该模型的仿真结果与实际情况比较吻合,即该模型在实际应用中可以有效的降低任务的抖动和延迟。
Embedded real-time system is more and more being used in the industrial control field and real-time scheduling has always been the core theory issue. But the jitter and latency of hard real-time task caused by scheduling directly influences the stability and reliability of systems, even leads to the collapse of systems. Therefore, how to control the jitter and latency of hard real-time task has become the hot issue in the current real-time scheduling theory research.
In view of the task jitter and latency question, this thesis provide a preemptable threshold scheduling model which divides the task. This model can reduce the task jitter and latency caused by task scheduling when it does not affect the system scheduling. Using this model to analyze IO jitter of the task, the results showed that the IO jitter of the task reduced along with decrease of the preemptable threshold. By the way of minimizing threshold of the preemptable threshold scheduling model, it can reduce the jitter and latency of hard real-time task and control the negative influence of the system stability caused by the control scheduling. According as the necessary and sufficient Conditions of RM Scheduling Algorithm, this paper presents an optimal threshold value allocation algorithm by the complexity of O(|Tn/T1|·n2) and according as sufficient Conditions of EDF Scheduling Algorithm presents a better threshold value allocation algorithm with complexity of O(n). To test the performance of the model in different scheduling circumstances, this paper structured a simulation testing environment on the TORSCHE toolbox of Matlab and carried on the simulation to the preemptable threshold scheduling algorithm. From the simulation results, it can be easily seen that the preemptable threshold scheduling model based on the division of tasks can effectively reduce the jitter and latency of tasks caused by scheduler in the typical scheduling algorithm. In order to measure the difference between the model theory and the model after the realization, this paper carried on a hardware simulation to the scheduling algorithm in Atmel megal28 hardware platforms, through modifications to the existing WORIX OS kernel. By comparing the hardware test results with the simulation results, the author found that the model simulation results accord with the actual situation, that is, the model can effectively reduce the jitter and latency of tasks in the practical application.
引文
1. Deng Z L J W S. Scheduling real-time applications in open environment[A]. Proceedings of the 18th IEEE Real-Time Systems Symposium[C]. Los Alamitos, CA:IEEE Computer Society Press,1997.
2. Deng Z, Liu J W S S J. A scheme for scheduling hard-real-time applications in open environment[A].Proceedings of the 9th Euromicro Workshop on Real-Time Systems[C]. Los Alamitos,CA:IEEE Computer Society Press,1997.
3. Abeni L B G. Integrating multimedia applications in hard real-time systems[A].Proceedings of the 19th IEEE Real-Time Systems Symposium[C]. Los Alamitos, CA:IEEE Computer Society Press,1998.
4. Zou Y, Li M W Q. Analysis for Scheduling Theory and Approach of Open Real-Time System[J]. Journal of Software.2003,14(1):83-90.
5. Lipari G B S K. Greedy reclaimation of unused bandwidth in constant bandwidth servers [A].IEEE Proceedings of the 12th Euromicro Conference on Real-Time Systems (ECRTS 2000)[C]. Stokholm, Sweden:2000.
6. Bernat G B A. Multiple Servers and Capacity Sharing for Implementing Flexible Scheduling[J].2002,22:49-75.
7. Caccamo M, Buttazzo G T D C. Efficient Reclaiming in Reservation-Based Real-Time Systems with Variable Execution Times[J]. IEEE Transactions on Computers.2005,54(2):198-213.
8. Lipari G B S K. Efficient Scheduling of Multi-Task Applications in Open Systems[A].IEEE Proceedings of the 6th Real-Time Systems and Applications Symposium(RTAS 2000)[C]. Washington DC:2000.
9. Buttazzo G, Lipari G, Abeni L E A. Soft Real-Time Systems:Predictability vs. Efficiency [J]. Springer.2005.
10.651 A. Design Guidance for Integrated Modular Avionics [J].
11. Mok A, Feng X C D. Resource Partition for Real-Time Systems [A].Proceedings of the 7th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2001)[C]. Taipei, Taiwan:2001.
12. Grenier M N N. New On-Line Preemptive Scheduling Policies for Improving Real-Time Behavior [A].Proceedings of the 10th IEEE International Conference on Emerging Technologies and Factory Automation[C]. Catania, Italy:IEEE Press, 2005.
13. Cervin A, Lincoln B, Eker J E A. The Jitter Margin and Its Application in the Design of Real-Time Control Systems [A].Proceedings of the 10th International Conference on Real-Time and Embedded Computing Systems and Applications [C]. Gothenburg, Sweden:2004.
14. Hoang H, Buttazzo G, Jonsson M E A. Computing the Minimum EDF Feasible Deadline in Periodic Systems[A].Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications[C]. Sydney, Australia:2006.
15. Balbastre P, Ripoll I C A. Optimal Deadline Assignment for Periodic Real-Time Tasks in Dynamic Priority Systems [A].Proceedings of the 18th Euromicro Conference on Real-Time Systems (ECRTS 2004)[C]. Dresden, Germany:2006.
16.王建辉顾树生.自动控制原理(第四版)[M].高等教育出版社,2005.
17. P M. Analysis and Design of Real-Time Control Systems with Varying Control Timing Constraints[D]. Barcelona, Spain:Technical University of Catalonia,2002.
18. A C. Integrated Control and Real-Time Scheduling[D]. Lund, Sweden:2003.
19. Ana Antunes, Fernando Morgado Diasl A M M. Improving the Control Preformance of a Real-Time Distributed Control System Under Variable Sampling to Actuation Delay[A].Proceeding of the 25th IASTED International Conference[C]. Lanzarote,Canary Islands,Spain:2006.
20. Buttazzo G C A. Comparative Assessment and Evaluation of Jitter Control Methods[A].Proceedings of the 15th International Conference on Real-Time and Network Systems(RTNS2007)[C]. Nancy, France:2007.
21. Balakrishnan A. On the Problem of Time Jitter in Sampling[J]. Information Theory, IEEE Transactions on.1962,8(3):226-236.
22. Nilsson J, Bernhardsson B W B. Stochastic Analysis and Control of Real-Time Systems with Random Time Delays[A].Automatica:1998.
23. Marti P, Fohler G, Ramamritham K E A. Jitter Compensation for Real-time Control Systems[A].Proceedings of the 22rd IEEE Real-Time System Symposium[C]. London, UK:2001.
24. Crespo A, Ripoll I A P. Reducing delays in RT control:the control action interval[A].Proceedings of the 14th IFAC World Congress[C].1999.
25. Liu C L L J W. Scheduling algorithms for multiprogramming in a hard-real-time environment[J]. Journal of the ACM.1973,20(1):46-61.
26. S L J W. Real-time System[M]. Personal Education,2000.
27.宋丽华.实时系统(影印版)[M].哈尔滨工业大学出版社,2003.
28. Lehoczky J.p. S L. Performance of real-time bus scheduling algorithms [J]. ACM Performance Evluation Review.1986,14(1):44-53.
29. Lehoczky J.p., Sha L. S J. Aperiodic scheduling in a hard real-time environment[A].Proceedings of 8th IEEE Real-Time System Symposium[C].1987.
30. Ramamrithamk S J R. Deadline Scheduling for Real-Time Systems-EDF and Related Algorithms[M]. Kluwer Academic Publishers,1998.
31. George L, Rivierre N S M. Preemptive and nonpreemptivereal-time uniprocessor scheduling[M]. Technical Report2966,1996.
32. Giorgio Buttazzo A C. Comparative Assessment and Evaluation of Jitter Control Methods[A].Conference on Real-Time and Networik Systems(RTNS 2007)[C]. Nancy,France:2007.
33. Redell O M T. Exact best-case response time analysis of fixed priority scheduled tasks[A].The IEEE 14th'Euromicro Conference on Real-Time Systems (ECRTS'02)[C]. Vienna, Austria:IEEE Computer Society,2002.
34. Michal Kutil, Premysl Sucha M S A Z H. TORSCHE Scheduling User's Guide(Release 0.3.5betal)[EB/OL]. Prague:Centre for Applied Cybernetics, Department of Control Engineering Czech Technical University in Prague,2007.
35.[英]波恩斯(burnsa)[英]威林斯(wellingsa)著王振宇等译.实时系统与编程语言：原书第3版[M].机械工业出版社,2004.
2. Deng Z, Liu J W S S J. A scheme for scheduling hard-real-time applications in open environment[A].Proceedings of the 9th Euromicro Workshop on Real-Time Systems[C]. Los Alamitos,CA:IEEE Computer Society Press,1997.
3. Abeni L B G. Integrating multimedia applications in hard real-time systems[A].Proceedings of the 19th IEEE Real-Time Systems Symposium[C]. Los Alamitos, CA:IEEE Computer Society Press,1998.
4. Zou Y, Li M W Q. Analysis for Scheduling Theory and Approach of Open Real-Time System[J]. Journal of Software.2003,14(1):83-90.
5. Lipari G B S K. Greedy reclaimation of unused bandwidth in constant bandwidth servers [A].IEEE Proceedings of the 12th Euromicro Conference on Real-Time Systems (ECRTS 2000)[C]. Stokholm, Sweden:2000.
6. Bernat G B A. Multiple Servers and Capacity Sharing for Implementing Flexible Scheduling[J].2002,22:49-75.
7. Caccamo M, Buttazzo G T D C. Efficient Reclaiming in Reservation-Based Real-Time Systems with Variable Execution Times[J]. IEEE Transactions on Computers.2005,54(2):198-213.
8. Lipari G B S K. Efficient Scheduling of Multi-Task Applications in Open Systems[A].IEEE Proceedings of the 6th Real-Time Systems and Applications Symposium(RTAS 2000)[C]. Washington DC:2000.
9. Buttazzo G, Lipari G, Abeni L E A. Soft Real-Time Systems:Predictability vs. Efficiency [J]. Springer.2005.
10.651 A. Design Guidance for Integrated Modular Avionics [J].
11. Mok A, Feng X C D. Resource Partition for Real-Time Systems [A].Proceedings of the 7th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2001)[C]. Taipei, Taiwan:2001.
12. Grenier M N N. New On-Line Preemptive Scheduling Policies for Improving Real-Time Behavior [A].Proceedings of the 10th IEEE International Conference on Emerging Technologies and Factory Automation[C]. Catania, Italy:IEEE Press, 2005.
13. Cervin A, Lincoln B, Eker J E A. The Jitter Margin and Its Application in the Design of Real-Time Control Systems [A].Proceedings of the 10th International Conference on Real-Time and Embedded Computing Systems and Applications [C]. Gothenburg, Sweden:2004.
14. Hoang H, Buttazzo G, Jonsson M E A. Computing the Minimum EDF Feasible Deadline in Periodic Systems[A].Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications[C]. Sydney, Australia:2006.
15. Balbastre P, Ripoll I C A. Optimal Deadline Assignment for Periodic Real-Time Tasks in Dynamic Priority Systems [A].Proceedings of the 18th Euromicro Conference on Real-Time Systems (ECRTS 2004)[C]. Dresden, Germany:2006.
16.王建辉顾树生.自动控制原理(第四版)[M].高等教育出版社,2005.
17. P M. Analysis and Design of Real-Time Control Systems with Varying Control Timing Constraints[D]. Barcelona, Spain:Technical University of Catalonia,2002.
18. A C. Integrated Control and Real-Time Scheduling[D]. Lund, Sweden:2003.
19. Ana Antunes, Fernando Morgado Diasl A M M. Improving the Control Preformance of a Real-Time Distributed Control System Under Variable Sampling to Actuation Delay[A].Proceeding of the 25th IASTED International Conference[C]. Lanzarote,Canary Islands,Spain:2006.
20. Buttazzo G C A. Comparative Assessment and Evaluation of Jitter Control Methods[A].Proceedings of the 15th International Conference on Real-Time and Network Systems(RTNS2007)[C]. Nancy, France:2007.
21. Balakrishnan A. On the Problem of Time Jitter in Sampling[J]. Information Theory, IEEE Transactions on.1962,8(3):226-236.
22. Nilsson J, Bernhardsson B W B. Stochastic Analysis and Control of Real-Time Systems with Random Time Delays[A].Automatica:1998.
23. Marti P, Fohler G, Ramamritham K E A. Jitter Compensation for Real-time Control Systems[A].Proceedings of the 22rd IEEE Real-Time System Symposium[C]. London, UK:2001.
24. Crespo A, Ripoll I A P. Reducing delays in RT control:the control action interval[A].Proceedings of the 14th IFAC World Congress[C].1999.
25. Liu C L L J W. Scheduling algorithms for multiprogramming in a hard-real-time environment[J]. Journal of the ACM.1973,20(1):46-61.
26. S L J W. Real-time System[M]. Personal Education,2000.
27.宋丽华.实时系统(影印版)[M].哈尔滨工业大学出版社,2003.
28. Lehoczky J.p. S L. Performance of real-time bus scheduling algorithms [J]. ACM Performance Evluation Review.1986,14(1):44-53.
29. Lehoczky J.p., Sha L. S J. Aperiodic scheduling in a hard real-time environment[A].Proceedings of 8th IEEE Real-Time System Symposium[C].1987.
30. Ramamrithamk S J R. Deadline Scheduling for Real-Time Systems-EDF and Related Algorithms[M]. Kluwer Academic Publishers,1998.
31. George L, Rivierre N S M. Preemptive and nonpreemptivereal-time uniprocessor scheduling[M]. Technical Report2966,1996.
32. Giorgio Buttazzo A C. Comparative Assessment and Evaluation of Jitter Control Methods[A].Conference on Real-Time and Networik Systems(RTNS 2007)[C]. Nancy,France:2007.
33. Redell O M T. Exact best-case response time analysis of fixed priority scheduled tasks[A].The IEEE 14th'Euromicro Conference on Real-Time Systems (ECRTS'02)[C]. Vienna, Austria:IEEE Computer Society,2002.
34. Michal Kutil, Premysl Sucha M S A Z H. TORSCHE Scheduling User's Guide(Release 0.3.5betal)[EB/OL]. Prague:Centre for Applied Cybernetics, Department of Control Engineering Czech Technical University in Prague,2007.
35.[英]波恩斯(burnsa)[英]威林斯(wellingsa)著王振宇等译.实时系统与编程语言：原书第3版[M].机械工业出版社,2004.