实时操作系统中实时调度算法及其资源管理的研究
|
摘要
实时系统主要面向现实世界中与时间因素相关的应用需求。它所关注的不仅是计算结果在逻辑上的正确性，而且还有输出结果时间的及时性。相应的处理过程必须在规定的时间限制内完成，否则系统将崩溃。此外，实时系统中，多任务共享资源时很容易出现无限优先级反转现象，最终导致系统崩溃。因此，任务调度与资源管理是实时系统最重要的组成部分。
本文选择μC／OS-Ⅱ实时内核作为研究对象。μC／OS-Ⅱ实时内核以抢占的方式调度任务，并且是开放源代码的。它为每个任务分配唯一的优先级，不支持相同优先级任务的调度。而在实际应用中，为相同功能的任务分配不同的优先级不是一个很好的逻辑设计。因此本文扩展了μC／OS-Ⅱ实时内核，使其支持相同优先级的轮转调度，从而实现了μC／OS-Ⅱ中固定优先级抢占和同优先级轮转调度方式相结合的一种混合调度策略。通过实验验证，扩展后的μC／OS-Ⅱ实时内核能够支持相同优先级任务的轮转调度，并且仍然能够保持μC／OS-Ⅱ抢占式内核的特点。
基于优先级抢占调度策略的实时内核中，优先级反转是涉及多任务共享资源时最容易出现的现象，此现象是实时应用系统产生不可预知错误的重要因素。本文阐述了μC／OS-Ⅱ实时内核中优先级反转问题产生的原因和对系统实时性的影响，提出了调度器加锁、优先级置顶和优先级继承三种抑制μC／OS-Ⅱ优先级反转的实现方法。通过实验验证，这三种方法能够有效地抑制μC／OS-Ⅱ中的优先级反转。最后对三种实现方法的性能进行了分析、比较。
Real-time systems are mainly designed to satisfy the timing requirements from the real word application. A real-time system concerns not only the logic correctness of the computing results, but also the time when the results come out. The process must be completed before deadline, or the system will failed. Otherwise, in real-time system, priority inversion phenomenon may occur frequently under the condition of multiple tasks share resource, and it will lead to system failure. So task scheduling and resource management is the most important part.
This paper useμC/OS-II as the reaserch object.μC/OS-II has a preemptive scheduling and free code kernel.μC/OS-II assigns each task for an unique priority, but it does not allow the kernel to have multiple tasks at the same priority. In practical application, it is not a good logical design. Aiming at this problem, by modifying the real time kernelμC/OS-II, this paper advanced round-robin scheduling to deal with the same priority tasks. By experiment verification, the modified kernel can support the tasks at the same priority, and it can remainμC/OS-II's preemptive property.
For real-time kernel adopting preemptive priority policy, priority inversion phenomenon may occur frequently under the condition of multiple tasks share resource. Some unpredictable errors of real-time application system perhaps derive from this phenomenon. This paper expounds the cause of priority inversion problem and the effect for real-time system performance firstly, and then, three approaches named as scheduler lock , priority ceiling protocol and priority inheritance protocol are proposed to be used inμC/OS- II for reducing the priority inversion phenomenon. By experiment verification, the three methods reduce priority inversion effectively inμC/OS- II. Finally, the performance of the three methods had been compared and analyzed.
本文选择μC／OS-Ⅱ实时内核作为研究对象。μC／OS-Ⅱ实时内核以抢占的方式调度任务，并且是开放源代码的。它为每个任务分配唯一的优先级，不支持相同优先级任务的调度。而在实际应用中，为相同功能的任务分配不同的优先级不是一个很好的逻辑设计。因此本文扩展了μC／OS-Ⅱ实时内核，使其支持相同优先级的轮转调度，从而实现了μC／OS-Ⅱ中固定优先级抢占和同优先级轮转调度方式相结合的一种混合调度策略。通过实验验证，扩展后的μC／OS-Ⅱ实时内核能够支持相同优先级任务的轮转调度，并且仍然能够保持μC／OS-Ⅱ抢占式内核的特点。
基于优先级抢占调度策略的实时内核中，优先级反转是涉及多任务共享资源时最容易出现的现象，此现象是实时应用系统产生不可预知错误的重要因素。本文阐述了μC／OS-Ⅱ实时内核中优先级反转问题产生的原因和对系统实时性的影响，提出了调度器加锁、优先级置顶和优先级继承三种抑制μC／OS-Ⅱ优先级反转的实现方法。通过实验验证，这三种方法能够有效地抑制μC／OS-Ⅱ中的优先级反转。最后对三种实现方法的性能进行了分析、比较。
Real-time systems are mainly designed to satisfy the timing requirements from the real word application. A real-time system concerns not only the logic correctness of the computing results, but also the time when the results come out. The process must be completed before deadline, or the system will failed. Otherwise, in real-time system, priority inversion phenomenon may occur frequently under the condition of multiple tasks share resource, and it will lead to system failure. So task scheduling and resource management is the most important part.
This paper useμC/OS-II as the reaserch object.μC/OS-II has a preemptive scheduling and free code kernel.μC/OS-II assigns each task for an unique priority, but it does not allow the kernel to have multiple tasks at the same priority. In practical application, it is not a good logical design. Aiming at this problem, by modifying the real time kernelμC/OS-II, this paper advanced round-robin scheduling to deal with the same priority tasks. By experiment verification, the modified kernel can support the tasks at the same priority, and it can remainμC/OS-II's preemptive property.
For real-time kernel adopting preemptive priority policy, priority inversion phenomenon may occur frequently under the condition of multiple tasks share resource. Some unpredictable errors of real-time application system perhaps derive from this phenomenon. This paper expounds the cause of priority inversion problem and the effect for real-time system performance firstly, and then, three approaches named as scheduler lock , priority ceiling protocol and priority inheritance protocol are proposed to be used inμC/OS- II for reducing the priority inversion phenomenon. By experiment verification, the three methods reduce priority inversion effectively inμC/OS- II. Finally, the performance of the three methods had been compared and analyzed.
引文
[1]Alan Burns，Andy Wellings．实时系统与编程语言．王振宇，陈利等译．北京：中国机械出版社，2004．
[2]J A Stankovic. Misconceptions about Real-Time Computing: A Serious Problem For Next-Generation Systems. IEEE Computer, 2003 (10): 10-19.
[3]汤子瀛，杨承忠，哲凤屏．计算机操作系统．西安：西安电子科技大学出版社，1996
[4]Alan C Shaw. Real-Time Systems and Software. New York:John Wiley and Sons, 2001
[5]王金刚．基于Vxworks的嵌入式实时系统设计．北京：清华大学出版社，2004：
[6]董晓霞．基于QNX实时操作系统的编程应用．雷达科学与技术，2000，(3)：34-39
[7]陈向群．Windows CE．NET系统分析及实验教程．北京：机械工业出版社，2003
[8]Jean J．Labrosse．嵌入式实时操作系统μC/OS-Ⅱ(第2版)．邵贝贝等译．北京：北京航空航天大学出版社，2003
[9]A S Tancnbaum. Modern Operating Systems. Upper Saddle River:Prentice Hall, 1999
[10]C L Liu, J W Layland. Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment. Journal of the Association for Computing Machinery, 2001,20(1):116-128
[11]A K Arekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks. Massachusetts Institute of Technology, 2001
[12]Kuo Tei-wei, Yang Wang-ru, Lin Kwei-jay. EGPS:A Class of Real-Time Scheduling Algorithms Based on Processor Sharing. In:Proc of the 10th Euromicro Workshop on Real Time Systems. Los Alamitos, California:IEEE Computer Society Press, 1998: 27-34
[13]J P Lehoczky, L Sha, J K Stronsnider. Enganced Aperiodic Responsiveness in Hard Real Time Environments. In: Proc of the 8th IEEE Real Time System Symposium. San Jose, California: IEEE Computer Society Press, 2004: 210-217
[14]T M Ghazalie, T P Baker. A periodic Servers in a Deadline Scheduling Environment[J]. Journal of Real Time Systems, 2005,9(1): 31-67
[15]J P Lehoczky, S Ramos-Thuel. An Optimal Algorithm for Scheduling Soft Aperiodic Tasks in Fixed Priority Preemptive Systems. In: Proc of the 13th IEEE Real Time Systems Symposium. Phoenix, Arizona: IEEE Computer Society Press, 2002:110-123
[16]Gerhard Fohler. Joint Scheduling of Distributed Complex Periodic and Hard Aperiodic Tasks in Statically Scheduled Systems. In: Proc of the 16th IEEE Real Time Systems Symposium. Pisa, Italy: IEEE Computer Society Press, 2002:152-161
[17]Robert Davis. Dual Priority Scheduling:A Means of Providing Flexibility in Hard Real Time Systems. Department of Computer Science, University of York, Tech Rep: YCS-230,1994:101-122
[18]Robert Davis, Andy Wellings. Dual Priority Scheduling. In: Proc of the 16th IEEE Real Time Systems Symposium. Pisa, Italy: IEEE Computer Society Press, 1995:lO0-109
[19]王济勇，林涛，王金东等．EDF调度算法抢占行为的研究及其改进．电子学报，2004，32(1)：64-68
[20]金宏，王宏安，王强等．改进的最小空闲时间优先调度算法．软件学报，2004，15(8)：1117-1123
[21]张惠娟，周利华．一种基于EDF算法的多处理器实时调度算法．计算机工程与应用，2003，30：16-17
[22]魏立峰，于海斌．一种基于自适应控制的软实时调度算法研究．系统仿真学报，2004，16(4)：760-771
[23]Robert Love．Linux内核设计与实现．陈莉君，康华等译．北京：机械工业出版社，2004
[24]金宏，王强，王宏安等．基于动态抢占阈值的实时调度．计算机研究与发展，2004，41(3)：393-398
[25]J A Stankovic, M Spuri, K Ramamritham, G C Buttazo. Deadline Scheduling for Real-Time Systems-EDF and Related Algorithms. Boston: Kluwer Academic Publishers, 1998
[26]B. Andersson, J. Jonsson. Fixed-priority preemptive multiprocessor scheduling: To partition or not to partition. In: Proc. of the International Conference on Real-Time Computing Systems and Applications, Cheju Island, Korea, 2000:337-346
[27]邢群科，温天江．时钟驱动的原理和实现．微计算机信息，2005，21(7)：136-138
[28]张惠娟，翟鸿鸣．一种固定优先级实时调度算法的可行性测定．微机发展，2003，13(9)：65-67
[29]何军．实时调度算法研究．北京：中国社会科学院软件研究院，1997
[30]翟鸿鸣．单处理器系统的实时调度算法研究．微机发展，2003，13(10)：99-101
[31]王强，王宏安，金宏等．实时系统中的非定期任务调度算法综述．计算机研究与发展，2004，41(3)：385-391
[32]M Spuri and G Buttazzo. Scheduling Aperiodic Tasks in Dynamic Priority Systems. Journal of Real-Time Systems, 1996,10(2):179-210
[33]B Sprunt, L Sha, J P Lehoczky. Aperiodic Task Scheduling for Hard Real Time Systems. Journal of Real Time Systems, 2000,1(1):27-60
[34]L Abeni, G Buttazo. Integrating Multimedia Applications in Hard Real Time Systems. In: Proc of the 19th IEEE Real Time Systems Symposium. Los Alzmitos, IEEE Computer Society Press, 1998:4-13
[35]郑宗汉．实时系统软件基础．北京：清华大学出版社，2003
[36]Ismael Ripoll. Real-Time Linux(RT-Linux). http://www.linuxfoeus.org/ChineseGB/May2000/article44.shtml 2000-5-4
[37]MicroC/OS-Ⅱ Official website. Empowering embedded system, http://www.micrium.com 2004-10-18
[38]谢长生，马进德，黄浩．基于μ C/OS-Ⅱ的任务调度策略研究．计算机工程与科学，2004，26(8)：70-73
[39]D. Kalinsky and M. Barr. Introduction to priority inversion. http://www.embedded.com/story/OEG20020321S0023. 2002-9-21
[40]J.B. Goodenough and L. Sha. The priority ceiling protocol: A method for minimizing the blocking of high priority Ada tasks. ACM SIGAda Ada Lett, 1998,8(7):20-31.
[41]L Sha, R. Rajkumar, J.P. Lehoczky. Priority Inheritance Protocols: An Approach to Real-Time Synchronization. IEEE Transactions On Computers, 1999,39(9):1175-1185
[2]J A Stankovic. Misconceptions about Real-Time Computing: A Serious Problem For Next-Generation Systems. IEEE Computer, 2003 (10): 10-19.
[3]汤子瀛，杨承忠，哲凤屏．计算机操作系统．西安：西安电子科技大学出版社，1996
[4]Alan C Shaw. Real-Time Systems and Software. New York:John Wiley and Sons, 2001
[5]王金刚．基于Vxworks的嵌入式实时系统设计．北京：清华大学出版社，2004：
[6]董晓霞．基于QNX实时操作系统的编程应用．雷达科学与技术，2000，(3)：34-39
[7]陈向群．Windows CE．NET系统分析及实验教程．北京：机械工业出版社，2003
[8]Jean J．Labrosse．嵌入式实时操作系统μC/OS-Ⅱ(第2版)．邵贝贝等译．北京：北京航空航天大学出版社，2003
[9]A S Tancnbaum. Modern Operating Systems. Upper Saddle River:Prentice Hall, 1999
[10]C L Liu, J W Layland. Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment. Journal of the Association for Computing Machinery, 2001,20(1):116-128
[11]A K Arekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks. Massachusetts Institute of Technology, 2001
[12]Kuo Tei-wei, Yang Wang-ru, Lin Kwei-jay. EGPS:A Class of Real-Time Scheduling Algorithms Based on Processor Sharing. In:Proc of the 10th Euromicro Workshop on Real Time Systems. Los Alamitos, California:IEEE Computer Society Press, 1998: 27-34
[13]J P Lehoczky, L Sha, J K Stronsnider. Enganced Aperiodic Responsiveness in Hard Real Time Environments. In: Proc of the 8th IEEE Real Time System Symposium. San Jose, California: IEEE Computer Society Press, 2004: 210-217
[14]T M Ghazalie, T P Baker. A periodic Servers in a Deadline Scheduling Environment[J]. Journal of Real Time Systems, 2005,9(1): 31-67
[15]J P Lehoczky, S Ramos-Thuel. An Optimal Algorithm for Scheduling Soft Aperiodic Tasks in Fixed Priority Preemptive Systems. In: Proc of the 13th IEEE Real Time Systems Symposium. Phoenix, Arizona: IEEE Computer Society Press, 2002:110-123
[16]Gerhard Fohler. Joint Scheduling of Distributed Complex Periodic and Hard Aperiodic Tasks in Statically Scheduled Systems. In: Proc of the 16th IEEE Real Time Systems Symposium. Pisa, Italy: IEEE Computer Society Press, 2002:152-161
[17]Robert Davis. Dual Priority Scheduling:A Means of Providing Flexibility in Hard Real Time Systems. Department of Computer Science, University of York, Tech Rep: YCS-230,1994:101-122
[18]Robert Davis, Andy Wellings. Dual Priority Scheduling. In: Proc of the 16th IEEE Real Time Systems Symposium. Pisa, Italy: IEEE Computer Society Press, 1995:lO0-109
[19]王济勇，林涛，王金东等．EDF调度算法抢占行为的研究及其改进．电子学报，2004，32(1)：64-68
[20]金宏，王宏安，王强等．改进的最小空闲时间优先调度算法．软件学报，2004，15(8)：1117-1123
[21]张惠娟，周利华．一种基于EDF算法的多处理器实时调度算法．计算机工程与应用，2003，30：16-17
[22]魏立峰，于海斌．一种基于自适应控制的软实时调度算法研究．系统仿真学报，2004，16(4)：760-771
[23]Robert Love．Linux内核设计与实现．陈莉君，康华等译．北京：机械工业出版社，2004
[24]金宏，王强，王宏安等．基于动态抢占阈值的实时调度．计算机研究与发展，2004，41(3)：393-398
[25]J A Stankovic, M Spuri, K Ramamritham, G C Buttazo. Deadline Scheduling for Real-Time Systems-EDF and Related Algorithms. Boston: Kluwer Academic Publishers, 1998
[26]B. Andersson, J. Jonsson. Fixed-priority preemptive multiprocessor scheduling: To partition or not to partition. In: Proc. of the International Conference on Real-Time Computing Systems and Applications, Cheju Island, Korea, 2000:337-346
[27]邢群科，温天江．时钟驱动的原理和实现．微计算机信息，2005，21(7)：136-138
[28]张惠娟，翟鸿鸣．一种固定优先级实时调度算法的可行性测定．微机发展，2003，13(9)：65-67
[29]何军．实时调度算法研究．北京：中国社会科学院软件研究院，1997
[30]翟鸿鸣．单处理器系统的实时调度算法研究．微机发展，2003，13(10)：99-101
[31]王强，王宏安，金宏等．实时系统中的非定期任务调度算法综述．计算机研究与发展，2004，41(3)：385-391
[32]M Spuri and G Buttazzo. Scheduling Aperiodic Tasks in Dynamic Priority Systems. Journal of Real-Time Systems, 1996,10(2):179-210
[33]B Sprunt, L Sha, J P Lehoczky. Aperiodic Task Scheduling for Hard Real Time Systems. Journal of Real Time Systems, 2000,1(1):27-60
[34]L Abeni, G Buttazo. Integrating Multimedia Applications in Hard Real Time Systems. In: Proc of the 19th IEEE Real Time Systems Symposium. Los Alzmitos, IEEE Computer Society Press, 1998:4-13
[35]郑宗汉．实时系统软件基础．北京：清华大学出版社，2003
[36]Ismael Ripoll. Real-Time Linux(RT-Linux). http://www.linuxfoeus.org/ChineseGB/May2000/article44.shtml 2000-5-4
[37]MicroC/OS-Ⅱ Official website. Empowering embedded system, http://www.micrium.com 2004-10-18
[38]谢长生，马进德，黄浩．基于μ C/OS-Ⅱ的任务调度策略研究．计算机工程与科学，2004，26(8)：70-73
[39]D. Kalinsky and M. Barr. Introduction to priority inversion. http://www.embedded.com/story/OEG20020321S0023. 2002-9-21
[40]J.B. Goodenough and L. Sha. The priority ceiling protocol: A method for minimizing the blocking of high priority Ada tasks. ACM SIGAda Ada Lett, 1998,8(7):20-31.
[41]L Sha, R. Rajkumar, J.P. Lehoczky. Priority Inheritance Protocols: An Approach to Real-Time Synchronization. IEEE Transactions On Computers, 1999,39(9):1175-1185