实时系统中单处理器调度算法的优化设计研究

运筹学学报 ›› 2013, Vol. 17 ›› Issue (2): 27-34.

实时系统中单处理器调度算法的优化设计研究

段渊^1,*

1. 广东科技学院，广东东莞 523083

收稿日期:2012-05-02 出版日期:2013-06-15 发布日期:2013-06-15
通讯作者: 段渊 E-mail:dy_01155@126. com

The study of design optimization about single-processor scheduling algorithm in real-time system

DUAN Yuan^1,*

1. Guangdong University of Science and Technology, Dongguan 523083, Guangdong, China

Received:2012-05-02 Online:2013-06-15 Published:2013-06-15

摘要/Abstract

摘要： 研究实时系统的建模与调度问题是运筹与控制领域研究的热点问题, 对实时系统中的单处理器的调度算法进行了分析与研究, 特别是对其中的单调速率算法和最早时间限优先算法进行了深入的研究, 指出单调速率算法是一种典型的静态调度算法, 并且证明了单调速率算法是单处理器最优的静态优先级调度算法, 同时还指出最早时间限优先算法是一种典型的动态优先级调度算法,证明了最早时间限优先算法是单处理器的最优的动态优先级调度算法. 最后, 为了更好地进行实时系统的建模与调度, 引入了一种新的对任务执行行为进行抽象的方法--T-LET平面方法, 利用这种方法建立了单处理器流调度模型和BLREF调度算法, 并指出这种模型和算法都具有很强的几何背景.

关键词: 实时系统, 单处理器, 静态调度算法, 动态调度算法

Abstract: The study of modelling and scheduling problem in real-time system is research focus of operations research and control theory. This paper studies a scheduling algorithm of single-processor in real-time system, especially Rate Monotonic (RM) and Earliest Deadline First (EDF), and show that RM is a typical static scheduling algorithm and EDF is a typical dynamic scheduling algorithm. Moreover, the paper prove that RM is the best in static priority scheduling algorithm of single-processor and EDF is the best dynamic priority one's. At last, in order to make the modelling and scheduling better for real-time system, a new abstracting means of task processing action is put forward: Time and Local remaining Execution-Time plane (T-LET plane). Based on this method, the paper set up single-processor flow model and BLREF scheduling algorithm, and point out their background of geometry.

Key words: real-time system, single-processor, static scheduling algorithm, dynamic scheduling algorithm

段渊. 实时系统中单处理器调度算法的优化设计研究[J]. 运筹学学报, 2013, 17(2): 27-34.

DUAN Yuan. The study of design optimization about single-processor scheduling algorithm in real-time system[J]. Operations Research Transactions, 2013, 17(2): 27-34.

参考文献

Philip Holman, James H. Anderson. Adapting pair scheduling for symmetric multi-processors [J]. Journal of Embedded Computing, 2005, 1(4): 543-564.
Krishna C M, Shin K G. Real-Time Systems [M]. McGraw-Hill Companies, Inc, 1997.
冯艳红, 张玉明. 实时调度算法分类研究 [J]. 微型电脑应用, 2005, 29(2): 205-208.
刘怀, 胡继峰. 实时系统的多任务调度 [J]. 计算机工程, 2002, 28(3):43-45.
翟鸿鸣. 单处理器系统的实时调度算法研究 [J]. 微机发展, 2003, 13(10): 99-101.
高立娥, 同爱丽. 实时多处理器动态调度算法的研究与应用 [J]. 计算机工程与应用, 2005, 41(34): 196-199.
Krishna C M, Shin K G. Real-Time Systems [M]. McGraw-Hill Companies, Inc, 1997.
Krishna C M, Shin K G. Real-Time Systems [M]. McGraw-Hill Companies, Inc, 1997.
MICHAEL L. Dertouzos. Multi-processor on-line scheduling of hard-real-time tasks [J]. IEEE Transactions on Software Engineering, 1989, 15(12): 1497-1506.
Yubin Zhong. The FHSE model of software system for synthetic evaluating enterprising [J]. Journal of Guangzhou University, 2005, 4(4): 316-320.
Yubin Zhong. The design and research of controller in fuzzy petri net [J]. Advance in Soft Computer, 2007, 40: 41-49.
Yubin Zhong. The optimization for location for large commodity's RD center [J]. Advance in Soft Computer, 2007, 40: 969-979.
Yubin Zhong. Honghai Mi, Huoxuan Chen. Design and optimization algorithm of VCS under security protection [J]. IEEE of International Conference on Web Information Systems and Mining, 2009, 552-556.
Yubin Zhong, Hepu Deng, Huoxuan Chen. A fuzzy logic based mobile intelligent system for effectively evaluating and selecting hotels in tourism [J]. IEEE of International Conference on Web Information Systems and Mining, 2009, 733-737.