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

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

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

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.