满 立，朱瑞龙

(1.红塔辽宁烟草有限责任公司营口卷烟厂，辽宁 营口 115002;2.中国科学院沈阳自动化研究所，辽宁 沈阳 110016)

0 引言

实时调度算法作为目前的一个研究热点，已经广泛地应用到各个领域，同时也取得了很多研究成果。根据调度对象的时间规律，可以分为周期性调度和非周期性调度;根据任务截止时间的要求，可以分为硬实时调度和软实时调度;根据任务的优先分配方法，可以分为静态优先级调度、动态优先级调度和混合优先级调度。其中比较典型的是静态优先级调度算法中的RM 调度算法(Rate-Monotonic Scheduling)［1］和动态优先级调度算法中的EDF(Earliest Deadline First)调度算法［2］，它们都是最优调度算法，并且具有很高的应用价值。RM 调度算法根据任务执行的周期决定调度的优先级，执行周期小的任务分配给较高的优先级。为了提高RM 调度算法的处理器利用率，人们继续对其进行研究，提出了一些改进算法，例如DM 调度算法［3］。DM 调度算法假设所有任务具有确定的截止期和周期，而且截止期不大于周期，任务按照截止期确定优先级，截止期越小，优先级越高。当截止期等于周期，则DM 调度算法退化为RM 调度算法。EDF 调度算法对队列中的任务优先级进行比较，优先级最高的任务获得资源进行处理，距离截止期最近的任务被分配最高优先级，具有较小的调度开销。作为最优的动态调度算法，也有很多人展开了更深入的研究，为了提高它的性能。例如LST(Least Slack Time)调度算法［4］，它计算松弛时间，就是当前时刻距离截止期的时间与任务执行时间之差，并按照时间的大小排序，最短时间具有最高优先级。……