硬实时调度抢占开销的在线优化策略及仿真实现
|
摘要
嵌入式系统已广泛地应用到人们的生产生活领域。在硬实时嵌入式系统中,任务间的抢占不仅导致操作系统上下文切换的时间开销,而且还会造成存储设备、网络设备、外界环境等资源带宽的降低以及能源消耗的浪费。如何在保证系统实时性的同时,对硬实时任务调度中的抢占开销进行优化,提高系统性能是本文研究的主要问题。
本文在实时系统通用的周期性任务模型基础上分析了固定优先级以及动态优先级实时调度的时序关系及任务间的抢占关系。分别对RM调度和EDF调度抢占行为的可推迟时间进行了量化分析,推导出受低优先级任务阻塞而造成的受阻任务集,以及在任意抢占时刻,推迟高优先级硬实时任务的执行来避免抢占发生的判定条件。提出了一种硬实时任务调度抢占开销的在线优化策略。通过在Matlab中的TORSCHE工具箱搭建仿真测试环境,对该优化策略进行了仿真实验。并与标准RM,EDF调度模型以及抢占阈值静态模型的仿真实验数据进行了对比。
仿真实验数据结果表明,本文提出的硬实时任务调度中抢占开销在线优化策略可以有效地减少系统运行中的抢占次数。能够在保证任务的可调度性的同时,有效减少不同调度算法下任务抢占发生的次数,降低抢占开销。
The embedded system has been widely applied to people's lives and production areas. In the hard real-time embedded systems, the preemptions of tasks not only lead to the context-switching time spending of the operating system, and other resources to reduce bandwidth and waste energy consumption. How to guarantee the real-time character of system, optimize the preemption overhead of hard real-time task scheduling and improve the system performance are the main issue in this paper.
In this paper, under the universal periodic task model of real-time systems, the author analyzes the timing relationship of fixed priority and dynamic priority scheduling and the preemption relationship among tasks. While respectively doing the quantitative analysis to the suspending time of the RM and EDF scheduling preemption action, export the blocked task set obstructed by low priority tasks and the determinant condition to avoid the preemption in the arbitrary preemption moment by postponing high-priority tasks in hard real-time system.This paper presents an online optimization strategy of hard real-time task scheduling preemption spending. By the TORSCHE toolbox of Matlab, the author build a simulation test environment and conduct the simulation test to the Optimization Strategies. And the data compared with the simulation data of the standard RM, EDF scheduling model and the preemption threshold model.
The Simulation experimental results show that, the hard real-time task scheduling seizing the online optimization strategy presented by this paper can effectively reduce the number of preemptions in the system operation. While to ensure the task scheduling, effectively reduce the number of task preemptions in the different scheduling algorithms and the preemption overhead.
本文在实时系统通用的周期性任务模型基础上分析了固定优先级以及动态优先级实时调度的时序关系及任务间的抢占关系。分别对RM调度和EDF调度抢占行为的可推迟时间进行了量化分析,推导出受低优先级任务阻塞而造成的受阻任务集,以及在任意抢占时刻,推迟高优先级硬实时任务的执行来避免抢占发生的判定条件。提出了一种硬实时任务调度抢占开销的在线优化策略。通过在Matlab中的TORSCHE工具箱搭建仿真测试环境,对该优化策略进行了仿真实验。并与标准RM,EDF调度模型以及抢占阈值静态模型的仿真实验数据进行了对比。
仿真实验数据结果表明,本文提出的硬实时任务调度中抢占开销在线优化策略可以有效地减少系统运行中的抢占次数。能够在保证任务的可调度性的同时,有效减少不同调度算法下任务抢占发生的次数,降低抢占开销。
The embedded system has been widely applied to people's lives and production areas. In the hard real-time embedded systems, the preemptions of tasks not only lead to the context-switching time spending of the operating system, and other resources to reduce bandwidth and waste energy consumption. How to guarantee the real-time character of system, optimize the preemption overhead of hard real-time task scheduling and improve the system performance are the main issue in this paper.
In this paper, under the universal periodic task model of real-time systems, the author analyzes the timing relationship of fixed priority and dynamic priority scheduling and the preemption relationship among tasks. While respectively doing the quantitative analysis to the suspending time of the RM and EDF scheduling preemption action, export the blocked task set obstructed by low priority tasks and the determinant condition to avoid the preemption in the arbitrary preemption moment by postponing high-priority tasks in hard real-time system.This paper presents an online optimization strategy of hard real-time task scheduling preemption spending. By the TORSCHE toolbox of Matlab, the author build a simulation test environment and conduct the simulation test to the Optimization Strategies. And the data compared with the simulation data of the standard RM, EDF scheduling model and the preemption threshold model.
The Simulation experimental results show that, the hard real-time task scheduling seizing the online optimization strategy presented by this paper can effectively reduce the number of preemptions in the system operation. While to ensure the task scheduling, effectively reduce the number of task preemptions in the different scheduling algorithms and the preemption overhead.
引文
1. Wolf W, High-Performance Embedded Computing:Architectures, Applications and Methodologies[M], Morgan Kaufmann,2006.
2. Noergaard T, Embedded Systems Architecture:A Comprehensive Guide for Engineers and Programmers[M], Newnes,2005.
3.夏玮玮,沈连丰,肖婕,毛宇斌.嵌入式系统关键技术分析与开发应用[M], 单片机与嵌入式系统应用,2003,2：45-49.
4. Ramamritham K, Stankovic J A, Schdeuling Algrithms and OperatingSystems Suport for Real-time Systems. Proceeding of the IEEE,1994,83 (1):55-67.
5. Liu J W S, Real-time Systems[M], Prentice Hall,2000.
6. C.L.Liu.J.W. Layland, Scheduling algorithms for multiprogramming in a hard real-time environment, J ACM,1973,20(1):46-61.
7. 王志平,熊光泽.实时调度算法,电子科技大学学报,2000,29(2)：205-208.
8.庞丽萍,吕文安,韩宗芬.DRT-UNIX系统中的任务调度,软件学报,1999,10(9)：1003-1008.
9. 翟鸿鸣.单处理器系统的实时调度算法研究,微机发展,2003,13(10)：99-101
10.许建峰,朱晴波,胡宁等.分布式实时系统中的预测调度算法,软件学报,2000,11(1)：95-103.
11. Williams R, Real-Time Systems Development[M], Butterworth-Heinemann,2005
12. Lehoczky J.P., Sha L, Performance of real-time bus scheduling algorithms [J], ACM Performance Evluation Review,1986,14(1):44-53.
13. Leung J Y T, Whitehead J, On the complexity of fixed-priority scheduling of periodic real-time tasks[J], Performance Evaluation,1982,2(4):237-250.
14. Audsley N., Bruns A, Richardson M., Wellings, A. Hard real-time scheduling:the deadline monotonic approach [A], Proceedings of 8th IEEE Workshop on Real-Time Operating Systems and Software[C],1991.127-132.
15. Zhu H., Hansen J. P., Lehoczky J. P., Rajkumar R, Optimal partitioning for quantized EDF scheduling [A], Proceedings of the 23rd IEEE Real-Time Systems Symposium[C], IEEE Computer Society,2002.
16. Natale M. D., Meschi A, Scheduling messages with earliest deadline techniques [J], The Journal of Real-Time System,2001,20(3):255-285.
17. Lamie W. Preemption-threshold [EB/OL]. White Paper, Express Logic Inc. Available at http://www.threadx.com/preemption.html.
18. Tokuda H., Wendorf J. W., Wang H. Y, Implementation of a time-driven scheduler for real-time operating systems[A], Proceedings of the 8th Real-Time Systems Symposium[C], IEEE Press, December,1987.271-280.
19. Labrosse J J, MicroC/OS-Ⅱ, The Real-Time Kernel, second edition[M], Lawrence, Kan: CMP Books,2002.
20.张希元,赵海,孙佩刚,et al. WebitOS内核的实现机制及性能分析[J],东北大学学报(自然科学版),2006,27(4)：394-397.
21.孔祥营,柏桂枝.嵌入式实时操作系统VxWorks及其开发环境Tornado[M],中国电力出版社,2002.
22. Burns A., Wellings A, Effective analysis for engineering real-time fixed priority schedulers [J], IEEE Transactions on Software Engineering,1995,21(5):475-480.
23. Lee C. G., Hahn J. Seo Y. M., Min S. L., Ha R., Hong S., Park C. Y., Lee M., Kim C. S, Bounding cache-related preemption delay for real-time systems [J],IEEE Transactions on Software Engineering,2001,27(9):805-826.
24. Ramaprasad H, Mueller F, Bounding Preemption Delay within Data Cache Reference Patterns for Real-Time Tasks,Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium,2006.71-80.
25. Ramaprasad H, Mueller F, Bounding Worst-Case Data Cache Behavior by Analytically Deriving Cache Reference Patterns [A],Proceedings of the Real-Time and Embedded Technology and Applications Symposium (RTAS)[C],2005.148-157.
26.王济勇,赵海,林涛.定时器驱动的RM调度机制建模及其性能优化[J],计算机学报,2005,28(2).
27.王济勇,林涛,王金东.EDF调度算法抢占行为的研究及其改进[J],电子学报,2004,32(1)：64-68.
28.韩光洁,赵海,王金东.et al. Embedded Internet环境下Webit2.0体系结构的研究与实现[J],通信学报,2004,25(9)：62-68.
29.金欢,阮冠春,徐凌宇,et al.基于嵌入式Internet技术的Webit体系结构研究与实现[J],控制与决策,2002,17(5)：541-544.
30.陈英革,王小英.任务调度过程中就绪队列的优化研究[J],系统仿真学报,2006, 18(4)：877-882.
31. 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.
32. Tindell K., Burns A., Wellings A. An extendible approach for analysing fixed priority hard real-time tasks [J], The Journal of Real-Time Systems,1994,6(2):133-152.
33. Wang Y, Saksena M, Scheduling fixed-priority tasks with preemption threshold [A], In Proc. of 6th IEEE Real Time Computing Systems and Applications Symposium, IEEE Computer Society Press,1999.328-335.
34.贾智平.嵌入式分布系统通信实时性问题[D],山东大学,2007.
35.俞亚平.嵌入式系统节能模型研究[D],浙江大学,2007.
36.石鹏程.嵌入式系统操作移植与应用开发研究[D],哈尔滨工程大学,2007.
37.周本海.实时操作系统中实时调度算法及其资源管理的研究[D],沈阳工业大学,2007
38.郑红.基于嵌入式系统的应用程序设计研究[D],西安电子科技大学,2007
2. Noergaard T, Embedded Systems Architecture:A Comprehensive Guide for Engineers and Programmers[M], Newnes,2005.
3.夏玮玮,沈连丰,肖婕,毛宇斌.嵌入式系统关键技术分析与开发应用[M], 单片机与嵌入式系统应用,2003,2：45-49.
4. Ramamritham K, Stankovic J A, Schdeuling Algrithms and OperatingSystems Suport for Real-time Systems. Proceeding of the IEEE,1994,83 (1):55-67.
5. Liu J W S, Real-time Systems[M], Prentice Hall,2000.
6. C.L.Liu.J.W. Layland, Scheduling algorithms for multiprogramming in a hard real-time environment, J ACM,1973,20(1):46-61.
7. 王志平,熊光泽.实时调度算法,电子科技大学学报,2000,29(2)：205-208.
8.庞丽萍,吕文安,韩宗芬.DRT-UNIX系统中的任务调度,软件学报,1999,10(9)：1003-1008.
9. 翟鸿鸣.单处理器系统的实时调度算法研究,微机发展,2003,13(10)：99-101
10.许建峰,朱晴波,胡宁等.分布式实时系统中的预测调度算法,软件学报,2000,11(1)：95-103.
11. Williams R, Real-Time Systems Development[M], Butterworth-Heinemann,2005
12. Lehoczky J.P., Sha L, Performance of real-time bus scheduling algorithms [J], ACM Performance Evluation Review,1986,14(1):44-53.
13. Leung J Y T, Whitehead J, On the complexity of fixed-priority scheduling of periodic real-time tasks[J], Performance Evaluation,1982,2(4):237-250.
14. Audsley N., Bruns A, Richardson M., Wellings, A. Hard real-time scheduling:the deadline monotonic approach [A], Proceedings of 8th IEEE Workshop on Real-Time Operating Systems and Software[C],1991.127-132.
15. Zhu H., Hansen J. P., Lehoczky J. P., Rajkumar R, Optimal partitioning for quantized EDF scheduling [A], Proceedings of the 23rd IEEE Real-Time Systems Symposium[C], IEEE Computer Society,2002.
16. Natale M. D., Meschi A, Scheduling messages with earliest deadline techniques [J], The Journal of Real-Time System,2001,20(3):255-285.
17. Lamie W. Preemption-threshold [EB/OL]. White Paper, Express Logic Inc. Available at http://www.threadx.com/preemption.html.
18. Tokuda H., Wendorf J. W., Wang H. Y, Implementation of a time-driven scheduler for real-time operating systems[A], Proceedings of the 8th Real-Time Systems Symposium[C], IEEE Press, December,1987.271-280.
19. Labrosse J J, MicroC/OS-Ⅱ, The Real-Time Kernel, second edition[M], Lawrence, Kan: CMP Books,2002.
20.张希元,赵海,孙佩刚,et al. WebitOS内核的实现机制及性能分析[J],东北大学学报(自然科学版),2006,27(4)：394-397.
21.孔祥营,柏桂枝.嵌入式实时操作系统VxWorks及其开发环境Tornado[M],中国电力出版社,2002.
22. Burns A., Wellings A, Effective analysis for engineering real-time fixed priority schedulers [J], IEEE Transactions on Software Engineering,1995,21(5):475-480.
23. Lee C. G., Hahn J. Seo Y. M., Min S. L., Ha R., Hong S., Park C. Y., Lee M., Kim C. S, Bounding cache-related preemption delay for real-time systems [J],IEEE Transactions on Software Engineering,2001,27(9):805-826.
24. Ramaprasad H, Mueller F, Bounding Preemption Delay within Data Cache Reference Patterns for Real-Time Tasks,Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium,2006.71-80.
25. Ramaprasad H, Mueller F, Bounding Worst-Case Data Cache Behavior by Analytically Deriving Cache Reference Patterns [A],Proceedings of the Real-Time and Embedded Technology and Applications Symposium (RTAS)[C],2005.148-157.
26.王济勇,赵海,林涛.定时器驱动的RM调度机制建模及其性能优化[J],计算机学报,2005,28(2).
27.王济勇,林涛,王金东.EDF调度算法抢占行为的研究及其改进[J],电子学报,2004,32(1)：64-68.
28.韩光洁,赵海,王金东.et al. Embedded Internet环境下Webit2.0体系结构的研究与实现[J],通信学报,2004,25(9)：62-68.
29.金欢,阮冠春,徐凌宇,et al.基于嵌入式Internet技术的Webit体系结构研究与实现[J],控制与决策,2002,17(5)：541-544.
30.陈英革,王小英.任务调度过程中就绪队列的优化研究[J],系统仿真学报,2006, 18(4)：877-882.
31. 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.
32. Tindell K., Burns A., Wellings A. An extendible approach for analysing fixed priority hard real-time tasks [J], The Journal of Real-Time Systems,1994,6(2):133-152.
33. Wang Y, Saksena M, Scheduling fixed-priority tasks with preemption threshold [A], In Proc. of 6th IEEE Real Time Computing Systems and Applications Symposium, IEEE Computer Society Press,1999.328-335.
34.贾智平.嵌入式分布系统通信实时性问题[D],山东大学,2007.
35.俞亚平.嵌入式系统节能模型研究[D],浙江大学,2007.
36.石鹏程.嵌入式系统操作移植与应用开发研究[D],哈尔滨工程大学,2007.
37.周本海.实时操作系统中实时调度算法及其资源管理的研究[D],沈阳工业大学,2007
38.郑红.基于嵌入式系统的应用程序设计研究[D],西安电子科技大学,2007