基于TAO的任务端到端响应时间可预测性研究
|
摘要
随着计算机网络迅速发展,基于分布式应用的实时系统越来越普遍,在信息家电、医疗仪器、智能汽车、工业控制以及通信设备等各个领域,实时需求无处不在,如何提供满足要求的实时服务质量(RT-QoS)已成为人们关注的一个热点。实时任务响应时间是影响系统设计、任务调度和资源分配的一个重要因素,预测实时任务响应时间使其满足定时约束,是非常有实际意义的。但由于任务对资源存在竞争、任务抢占、定时器中断、I/O冲突以及某些实时任务行为的随机性等因素的存在,使得系统难以用传统方法来确定实时任务响应时间。
本文的目的是通过预测实时任务端到端响应时间为系统设计提供指导、为系统调度提供依据、为任务执行提供保障。实时CORBA在原有CORBA框架的基础上,对实时所需的组件进行了扩充,以支持系统端到端可预测性操作,保证应用的实时性。本文着眼于这一事实,针对各种类型的实时任务:周期性任务、非周期性任务和偶发任务,提出了一系列策略和机制来保证这些任务端到端响应时间的可预测性。
本文从实时CORBA应用代码出发,根据端到端的调度方法,把分布式实时系统中任务的端到端响应时间预测分析局部化,通过建立节点模型,把响应时间分解成几部分,然后采用两层调度方案、时间需求分析和排队论等方法和手段预测分析每部分时间,并对实时任务端到端响应时间的预测结果与基于TAO环境下的实测结果进行比较分析,分析结果说明所做工作的正确性,该结果对于实时CORBA应用系统设计及其任务调度有较好参考意义。
With rapid development of computer network, the applications of distributed real-time systems become more and more popular. Real-time requirement exists in many fields such as information appliance, medical instrument, intelligent vehicle, process control in industry and communication device. How to meet the demands of the real-time quality of service (RT-QoS) becomes a hot spot which researchers concern. The response time of real-time tasks is an important factor which affects system design, task scheduling and resource allocation. It has much practical significance to know it in advance and make it to satisfy timing constraint. But since there are the factors such as task preemption, resource competition, timer interrupt, I/O collision, some real-time tasks with random behavior and so on, it is very difficult for the systems to predict the response time of the tasks by traditional methods.The purpose of the paper provides the guide for system design, the basis for system scheduling and the guarantee for task execution by predicting end-to-end response time of real-time tasks. Real-time CORBA extends the components which meet the real-time requirement in the original CORBA frame, so that it supports the operation of end-to-end predictability of the system, and guarantees the real-time application. Based on this real situation, the paper presents a series of strategies and mechanisms to guarantee the predictability of the response time of these tasks, including periodic tasks, aperiodic tasks and sporadic tasks.Research on end-to-end response time is started from the presumed code of real-time CORBA application. According to the end-to-end scheduling method, the prediction analysis of end-to-end response time of the tasks in the distributed real-time systems is localized, and through establishing a node model, the response time is decomposed into several parts, and then using the methods, such as two levels' scheduling scheme, time-demand analysis, queuing theory and so on, each part of the response time is analyzed. Finally, the predicting result based on the above is compared with the real result based on the TAO, the comparing result shows the
lightness of the work, the result has the good reference significance for the design and the task scheduling of real-time CORBA application system.
本文的目的是通过预测实时任务端到端响应时间为系统设计提供指导、为系统调度提供依据、为任务执行提供保障。实时CORBA在原有CORBA框架的基础上,对实时所需的组件进行了扩充,以支持系统端到端可预测性操作,保证应用的实时性。本文着眼于这一事实,针对各种类型的实时任务:周期性任务、非周期性任务和偶发任务,提出了一系列策略和机制来保证这些任务端到端响应时间的可预测性。
本文从实时CORBA应用代码出发,根据端到端的调度方法,把分布式实时系统中任务的端到端响应时间预测分析局部化,通过建立节点模型,把响应时间分解成几部分,然后采用两层调度方案、时间需求分析和排队论等方法和手段预测分析每部分时间,并对实时任务端到端响应时间的预测结果与基于TAO环境下的实测结果进行比较分析,分析结果说明所做工作的正确性,该结果对于实时CORBA应用系统设计及其任务调度有较好参考意义。
With rapid development of computer network, the applications of distributed real-time systems become more and more popular. Real-time requirement exists in many fields such as information appliance, medical instrument, intelligent vehicle, process control in industry and communication device. How to meet the demands of the real-time quality of service (RT-QoS) becomes a hot spot which researchers concern. The response time of real-time tasks is an important factor which affects system design, task scheduling and resource allocation. It has much practical significance to know it in advance and make it to satisfy timing constraint. But since there are the factors such as task preemption, resource competition, timer interrupt, I/O collision, some real-time tasks with random behavior and so on, it is very difficult for the systems to predict the response time of the tasks by traditional methods.The purpose of the paper provides the guide for system design, the basis for system scheduling and the guarantee for task execution by predicting end-to-end response time of real-time tasks. Real-time CORBA extends the components which meet the real-time requirement in the original CORBA frame, so that it supports the operation of end-to-end predictability of the system, and guarantees the real-time application. Based on this real situation, the paper presents a series of strategies and mechanisms to guarantee the predictability of the response time of these tasks, including periodic tasks, aperiodic tasks and sporadic tasks.Research on end-to-end response time is started from the presumed code of real-time CORBA application. According to the end-to-end scheduling method, the prediction analysis of end-to-end response time of the tasks in the distributed real-time systems is localized, and through establishing a node model, the response time is decomposed into several parts, and then using the methods, such as two levels' scheduling scheme, time-demand analysis, queuing theory and so on, each part of the response time is analyzed. Finally, the predicting result based on the above is compared with the real result based on the TAO, the comparing result shows the
lightness of the work, the result has the good reference significance for the design and the task scheduling of real-time CORBA application system.
引文
[1] J. Stankovic, M. Spuri, K. Ramamritham, and G. Buttazzo. Deadline Scheduling for Real-Time Systems-EDF and Related Algorithms[M]. Kluwer Academic Publishers, Boston, Massachusetts, USA, 1998.
[2] http://www.cs.wustl.edu/～schmidt/
[3] Object Management Group. Realtime CORBA2.0 [S]. 2003.11.
[4] C. L. Liu, and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment[J]. Journal of the Association for Computing Machinery, 1973.1, 20(1): 46-61.
[5] J. Lehoczky, L. Sha, and Y. Ding. The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior. In Proceedings of the IEEE Real-Time System Symposium, 1989: 166-171.
[6] N. Audsley, A. Bums, K. Tindell, M. Richardson, and A. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling[J]. Software Engineering Journal, 1993, 8(5): 284-292.
[7] DI. Katcher, H. Arakawa, and JK. Strosnider. Engineering and analysis of fixed priority schedulers[J]. IEEE Transaction on Software Engineering, 1993, 19(9): 920-934.
[8] L. Sha, R. Rajkumar, and JP. Lehoczky. Priority inheritance protocols: An apporoach to realtime synchronization[J]. IEEE aansaction on Computers, 1990, 39(9): 1175-1185.
[9] JB. Goodenough, and L. Sha. The priority ceiling protocol: A method for minimizing the blocking of high priority ada tasks[J]. ACM Ada Letters, 1998, 8(7):20-31.
[10] K. Tindell, and J. Clark. Holistic Schedulability Analysis for Distributed Hard Real-Time Systems[J]. Microprocessing & Microprogramming, 1994.4, 50(2-3):117-134.
[11] K. Tindell. Adding Time-Offsets to Schedulability Analysis[R]. Technical Report YCS 221, Dept. of Computer Science, University of York, England, 1994.1.
[12] J.C. Palencia, and M. Gonzalez Harbour. Schedulability Analysis for Tasks with Static and Dynamic Offsets. Proceedings of the 19th IEEE Real-Time Systems Symposium, 1998.
[13] J.C. Palencia Gutierrez, J. J. Gutierrez Garcia, and M. Gonzalez Harbour. Best-Case Analysis for Improving the Worst-Case Schedulability Test for Distributed Hard Real-Time Systems. 10th Euromicro Workshop on Real-Time Systems, Berlin, Germany, 1998.6.
[14] J.C. Palencia, and M. Gonzalez Harbour. Response time analysis of EDF distributed real-time systems[J]. Journal of Embedded Computing, IOS Press, Vol. 1, Issue2, 2005.11.
[15] C. Li, R. Bettati, and W. Zhao. Response Time Analysis for Distributed Real-Time Systems with Bursty Job Arrivals. Proceeding of ICPP, 1998.
[16] R. Bettati. End-to-end scheduling to meet deadlines in distributed systems[D]. Ph.D.thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, 1994.
[17] 毛羽刚,金士尧,张拥军,胡华平.分布强实时系统的可预测性研究[J].计算机研究与发展,2000.6,Vol.37,No.6:661-667.
[18] 宾雪莲,金士尧,杨玉海.周期多帧任务模型的响应时间分析[J].计算机工程与科学,2003,Vol.25,No.6:104-108.
[19] 宾雪莲,杨玉海,金士尧,宾亚.基于EDF抢占式调度的周期任务最小响应时间分析[J].计算机科学,2004,Vol.31,No.9:114-116.
[20] 侯爽,宋颖慧.一种实时系统中的多任务可预测调度算法[J].计算机工程, 2004,Vol.30,No.16:67-69.
[21] Jane W.S.Liu(著).姬孟洛等(译).实时系统[M].高等教育出版社,2003.12.
[22] L. Sha, R. Rajkumar, and J. Lehoczky. Real-time synchronization protocol for multiprocessors. Proceedings of IEEE Real-Time Systems Symposium, 1988.
[23] J. Sun, and J. W. S. Liu. End-to-end synchronization protocols of fixed priority periodic tasks. Proceedings of the 16th IEEE International Conference on Distributed Computing Systems, Hong Kong, 1996.6.
[24] Arezou Mohammadi, and Selim G.. Akl. Scheduling Algorithms for Real-Time Systems[R], Technical Report No.2005-499, 2005.7.
[25] 汪芸,谢俊清,沈卓炜,顾冠群.实时CORBA技术综述[J].东南大学学报 (自然科学版),2002.5,Vol32,No.3:311-317.
[26] J.Y.-T. Leung, and J. Whitehead. On the Complexity of Fixed-Priority Scheduling of Periodic Real-Time Tasks[J]. Performance Evaluation, 1982, vol.2: 237-250.
[27] Locke C D. Fundamentals of real-time presentation[R]. OMG Document: realtime/98-05-03, 1998.
[28] Object Management Group. Real-time CORBA1.0: Request for Proposal[R]. OMG, 1997.
[29] Object Management Group. Realtime CORBA1.0[S]. 1999.3.
[30] Object Management Group. The Common Object Request Broker: Architecture and Specification[S], 2.4ed, 2000.10.
[31] Object Management Group. CORBA Messaging Specification[S]. OMG Document orbos/98-05-058ed, 1998.5.
[32] 俞岭.端到端系统的实时CORBA的研究[D].电子科技大学,2003.
[33] 杨鹏,杜庆伟,顾冠群.实时CORBA规范分析与评述[J].计算机工程与应用,2002,Vol.38,No.13:88-90.
[34] 王晓东,彭兵,张艳.实时CORBA及应用研究[J].计算机应用研究,2002,Vol19.No1:96-98.
[35] I. Pyarali, D. C. Schmidt, and R. Cytron. Achieving End-to-End Predictability of the TAO Real-time CORBA ORB. Presented at Proceedings of the 8th IEEE Real-Time Technology and Applications Symposium, San Jose, CA, USA, 2002.
[36] Jianfan Zou, David Levy, and Anna Liu. Evaluating Overhead and Predictability of a Real-Time CORBA System. Hicss, p. 90276a, Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04) - Track 9, 2004.
[37] 汪芸,沈卓炜.实时CORBA系统调度模型的分析和比较[J].微机发展,2005.1,Vol.15,No.1:8-10,47.
[38] Douglas C.Schmidt(著).马维达(译).ACE应用实例,2003.
[39] 胡贯荣,谢美意.实时应用的可预测性研究和分析[J].华中理工大学学报, 1999, Vol.27, No.4: 18-19.
[40] R. Ha. Validating timing constraints in multiprocessor and distributed systems[D].Ph.D.thesis, Department of Computer Science, University of IIinois at Urbana-Champaign, 1995.
[41] J. Lehoczky. Fixed priority scheduling of periodic task sets with arbitrary deadlines. In Proceedings Real-Time Systems Symposiom, 1990.12:201-209.
[42] 谭浩,骆志刚,刘锦德.实时CORBA端到端调度的研究[J].小型微型计算机系统,2003.7,Vol.24,No.7:1165-1168.
[2] http://www.cs.wustl.edu/～schmidt/
[3] Object Management Group. Realtime CORBA2.0 [S]. 2003.11.
[4] C. L. Liu, and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment[J]. Journal of the Association for Computing Machinery, 1973.1, 20(1): 46-61.
[5] J. Lehoczky, L. Sha, and Y. Ding. The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior. In Proceedings of the IEEE Real-Time System Symposium, 1989: 166-171.
[6] N. Audsley, A. Bums, K. Tindell, M. Richardson, and A. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling[J]. Software Engineering Journal, 1993, 8(5): 284-292.
[7] DI. Katcher, H. Arakawa, and JK. Strosnider. Engineering and analysis of fixed priority schedulers[J]. IEEE Transaction on Software Engineering, 1993, 19(9): 920-934.
[8] L. Sha, R. Rajkumar, and JP. Lehoczky. Priority inheritance protocols: An apporoach to realtime synchronization[J]. IEEE aansaction on Computers, 1990, 39(9): 1175-1185.
[9] JB. Goodenough, and L. Sha. The priority ceiling protocol: A method for minimizing the blocking of high priority ada tasks[J]. ACM Ada Letters, 1998, 8(7):20-31.
[10] K. Tindell, and J. Clark. Holistic Schedulability Analysis for Distributed Hard Real-Time Systems[J]. Microprocessing & Microprogramming, 1994.4, 50(2-3):117-134.
[11] K. Tindell. Adding Time-Offsets to Schedulability Analysis[R]. Technical Report YCS 221, Dept. of Computer Science, University of York, England, 1994.1.
[12] J.C. Palencia, and M. Gonzalez Harbour. Schedulability Analysis for Tasks with Static and Dynamic Offsets. Proceedings of the 19th IEEE Real-Time Systems Symposium, 1998.
[13] J.C. Palencia Gutierrez, J. J. Gutierrez Garcia, and M. Gonzalez Harbour. Best-Case Analysis for Improving the Worst-Case Schedulability Test for Distributed Hard Real-Time Systems. 10th Euromicro Workshop on Real-Time Systems, Berlin, Germany, 1998.6.
[14] J.C. Palencia, and M. Gonzalez Harbour. Response time analysis of EDF distributed real-time systems[J]. Journal of Embedded Computing, IOS Press, Vol. 1, Issue2, 2005.11.
[15] C. Li, R. Bettati, and W. Zhao. Response Time Analysis for Distributed Real-Time Systems with Bursty Job Arrivals. Proceeding of ICPP, 1998.
[16] R. Bettati. End-to-end scheduling to meet deadlines in distributed systems[D]. Ph.D.thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, 1994.
[17] 毛羽刚,金士尧,张拥军,胡华平.分布强实时系统的可预测性研究[J].计算机研究与发展,2000.6,Vol.37,No.6:661-667.
[18] 宾雪莲,金士尧,杨玉海.周期多帧任务模型的响应时间分析[J].计算机工程与科学,2003,Vol.25,No.6:104-108.
[19] 宾雪莲,杨玉海,金士尧,宾亚.基于EDF抢占式调度的周期任务最小响应时间分析[J].计算机科学,2004,Vol.31,No.9:114-116.
[20] 侯爽,宋颖慧.一种实时系统中的多任务可预测调度算法[J].计算机工程, 2004,Vol.30,No.16:67-69.
[21] Jane W.S.Liu(著).姬孟洛等(译).实时系统[M].高等教育出版社,2003.12.
[22] L. Sha, R. Rajkumar, and J. Lehoczky. Real-time synchronization protocol for multiprocessors. Proceedings of IEEE Real-Time Systems Symposium, 1988.
[23] J. Sun, and J. W. S. Liu. End-to-end synchronization protocols of fixed priority periodic tasks. Proceedings of the 16th IEEE International Conference on Distributed Computing Systems, Hong Kong, 1996.6.
[24] Arezou Mohammadi, and Selim G.. Akl. Scheduling Algorithms for Real-Time Systems[R], Technical Report No.2005-499, 2005.7.
[25] 汪芸,谢俊清,沈卓炜,顾冠群.实时CORBA技术综述[J].东南大学学报 (自然科学版),2002.5,Vol32,No.3:311-317.
[26] J.Y.-T. Leung, and J. Whitehead. On the Complexity of Fixed-Priority Scheduling of Periodic Real-Time Tasks[J]. Performance Evaluation, 1982, vol.2: 237-250.
[27] Locke C D. Fundamentals of real-time presentation[R]. OMG Document: realtime/98-05-03, 1998.
[28] Object Management Group. Real-time CORBA1.0: Request for Proposal[R]. OMG, 1997.
[29] Object Management Group. Realtime CORBA1.0[S]. 1999.3.
[30] Object Management Group. The Common Object Request Broker: Architecture and Specification[S], 2.4ed, 2000.10.
[31] Object Management Group. CORBA Messaging Specification[S]. OMG Document orbos/98-05-058ed, 1998.5.
[32] 俞岭.端到端系统的实时CORBA的研究[D].电子科技大学,2003.
[33] 杨鹏,杜庆伟,顾冠群.实时CORBA规范分析与评述[J].计算机工程与应用,2002,Vol.38,No.13:88-90.
[34] 王晓东,彭兵,张艳.实时CORBA及应用研究[J].计算机应用研究,2002,Vol19.No1:96-98.
[35] I. Pyarali, D. C. Schmidt, and R. Cytron. Achieving End-to-End Predictability of the TAO Real-time CORBA ORB. Presented at Proceedings of the 8th IEEE Real-Time Technology and Applications Symposium, San Jose, CA, USA, 2002.
[36] Jianfan Zou, David Levy, and Anna Liu. Evaluating Overhead and Predictability of a Real-Time CORBA System. Hicss, p. 90276a, Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04) - Track 9, 2004.
[37] 汪芸,沈卓炜.实时CORBA系统调度模型的分析和比较[J].微机发展,2005.1,Vol.15,No.1:8-10,47.
[38] Douglas C.Schmidt(著).马维达(译).ACE应用实例,2003.
[39] 胡贯荣,谢美意.实时应用的可预测性研究和分析[J].华中理工大学学报, 1999, Vol.27, No.4: 18-19.
[40] R. Ha. Validating timing constraints in multiprocessor and distributed systems[D].Ph.D.thesis, Department of Computer Science, University of IIinois at Urbana-Champaign, 1995.
[41] J. Lehoczky. Fixed priority scheduling of periodic task sets with arbitrary deadlines. In Proceedings Real-Time Systems Symposiom, 1990.12:201-209.
[42] 谭浩,骆志刚,刘锦德.实时CORBA端到端调度的研究[J].小型微型计算机系统,2003.7,Vol.24,No.7:1165-1168.