多特征协调的实时调度算法

满 立，朱瑞龙

(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］，它计算松弛时间，就是当前时刻距离截止期的时间与任务执行时间之差，并按照时间的大小排序，最短时间具有最高优先级。这种调度算法被证明也是最优动态优先级算法。但是EDF调度算法存在一个严重缺陷，一个错过时限的迟到作业具有比时限未到的作业更高的优先级。所以，当系统处于超载状态时，EDF 调度算法的性能将出现明显的下滑。针对这一问题，Jensen 等提出了HVF(Highest Value First)调度算法［5］，将最高优先级分配给价值最高的任务，面对系统超载时，相对EDF 调度算法有更好表现。在此基础上，HVDF(Highest Value Density First)调度算法也被提出［6］，在系统超载时它的性能好于HVF 调度算法。但是HVDF 调度算法是一种贪婪算法，在系统没有超载时，系统消耗较大，容易导致任务错过截止期，调度性差。

在对生产过程进行控制的实时系统中，需要处理各种类型的任务，其中报警类事件和某些周期性事件需要具有较高的优先级，并且不被其他的任务抢占。这类调度对象具有混合特性，在设计调度算法时需要综合考虑多方因素的影响［7-14］。现有的实时调度算法并不能完全满足系统调度的需要，所以本文提出一种基于多特征协调(Multi-Feature Synthesis，MFS)的实时调度算法，来解决目前存在的问题。

1 调度策略

多特征协调的实时调度算法主要针对实际生产中对生产过程控制过程中所产生的任务，所以它的调度对象与一般的实时调度算法并不一样，具有自己的特点。在生产过程中产生的事件处理任务并不会因为错过截止期而对系统的性能产生较大影响，但是有一类事件除外，那就是报警事件。如果在生产过程中出现了报警事件，那就必须在尽量短的时间内进行处理，所以这一类事件应该赋予固定的最高优先级，排在任务队列的最前端优先处理［15］。

多特征协调的实时调度算法的目标是在调度任务时满足固定最高优先级的任务能够随时被调度，而且不影响其他任务得的调度效率。其中固定最高优先级的任务是一类特殊任务，是需要尽快被处理的任务，且越快越好。剩余的任务综合考虑任务的相对截止期和系统的负载情况后，确定优先级并进行调度。

2 多特征协调调度算法

多特征协调，主要体现在调度对象特征复杂上。因为在实际生产过程中，调度的对象是生产过程事件，具有不确定性，以及实时性非实时性要求共存。任务属性具有多种特征，并且需要协调不同实时性要求和优先级要求。例如，加工工序完成时生成的事件，需要与其他没有实时性要求的事件一同被调度，当出现报警事件这类具有实时性要求的事件时，需要让出资源，使报警事件优先处理。这个过程体现了调度任务具有的多特征这一特性，同时需要协调其处理顺序。协调不同任务之间的调度顺序，制定调度策略是本算法需要解决的主要问题。

2.1 任务建模

针对生产过程中的任务调度处理问题，假设系统中存在N 个独立的任务T 组成的任务集TA，TA={T1，T2，T3，…，Tn}，其中任务集中的任务同时存在周期任务和非周期任务。每一个任务都由一个五元组Ti(ai，di，wi，hi，ui)构成。ai为任务已经等待时间，di为任务距离截止期的时间，wi为任务执行需要的时间，hi为任务的价值系数，ui为任务综合优先级。(di-wi)为任务松弛时间。如果di＜wi，则任务没有足够的剩余时间完成，任务失败。

为了便于确定调度算法的调度对象和范围，作出如下假设:

1)任务是独立的，不因为资源共享而阻塞，也不会自动挂起;

2)任务之间可以抢占，并且抢占的代价可以忽略;

3)任务为随机生成的非周期任务;

4)处理器只响应任务调度请求。

2.2 算法设计

多特征协调的实时调度算法的设计目标:

1)优先保证关键任务的运行;

2)尽量控制截止期错失率DMR。

因为本文设计的算法面向的是生产过程事件所生成的调度任务，所以不同类型任务的实时性要求已经被确定下来，已经被分为关键任务和非关键任务。如生产过程中的开工完工事件就是非关键任务，即使被延迟一段时间处理也不会有问题，但是报警事件就需要被即时处理，具有实时性要求，保证生产的安全。

本算法的调度体系框架如图1 所示。

图1 多特征协调算法的调度体系框架

多特征协调调度算法的调度规则如下:

1)任务到达后首先进行判断，如果为关键任务队列，则进入关键任务队列H，否则进入非关键任务队列L;

2)调度时首先判断关键任务队列H 是否为空，如果非空，对H 中按照FIFO(First In First Out)规则调度;如果为空，则选择非关键任务队列L 中优先级最高的任务进行处理;

3)在对非关键任务队列L 中的任务进行调度时，监控负载情况，并根据结果调整调度算法。

2.3 调度策略的选择和设计

在进行调度时，负载监视器对非关键任务队列L中的队列进行监控，并将结果传给调度策略选择器，对调度策略进行简单调整。定义监视器返回结果为K，K 的值为:

假设非关键任务Ti按照EDF 算法调度时的优先级系数为ei，按照HVF 算法调度时的价值系数为hi，则Ti在队列L 中的优先级系数ui为，

K 作为一个平衡因子，当系统负载没有达到超载时，K=1，则ui=ei;若系统负载达到超载，则K=0，ui=hi。因为EDF 调度算法在系统超载时性能下降太快，而在这种情况下HVF 算法的性能优于EDF 算法，所以，综合2 种算法的优点，可以较好地提高系统处理效率。

算法的调度策略选择规则如下:

1)通过监视器判断非关键任务队列L 是否超载，如果超载跳至2)执行，否则跳至3);

2)按照EDF 算法计算队列L 中任务的优先级;

3)按照HVF 算法计算队列L 中的任务优先级;

4)按照优先级排序执行任务。

3 算法验证和比较

Cheddar 是一个免费实时调度仿真软件，用来查看实时系统任务的时限。所分析的系统可以用AADL(Architecture Analysis and Design Language，一种基于模型工程的语言标准)或为Cheddar 专门的语言描述［16］。该软件可以快速为实时调度建模。本文采用实时调度仿真工具Cheddar 进行仿真实验，其中Task1 任务为需要优先处理的关键任务，在测试结果中，如图2 所示，即使其他任务出现延期，Task1 的任务也被保证执行，实现了本算法设计的目的。对比测试中，Task1 为非关键队列。通过对比可以得出结论，关键队列的调度对其他队列没有明显影响。

图2 仿真测试结果

图3 截止期错失率的对比

在保证关键任务执行的情况下，也要保证非关键任务的执行。对此笔者也进行了仿真测试。

在保证了关键任务不会对抢占资源，对其余任务的执行造成影响后，还需要测试算法的性能，这一点主要从截止期错失率(MDP，Missed Deadline Percentage)来考虑［17］。MDP 越低，能够得到及时响应的任务和操作就越多，主要对比EDF 算法、HVF 算法和MFS 算法，如图3 所示。

图3 中的纵坐标为截止期错失率MDP，横坐标为系统负载。从图中可以看出，MFS 算法在系统没有超载时，同EDF 有几乎一样的性能，显示出最优性;当系统超载时，具有比EDF 算法更低的MDP，很好地避免了EDF 算法的多米诺效应，性能有明显提高。

实现价值率HVR 是指调度算法调度执行任务满足截止期所实现的积累价值与所有提交任务价值总和的比率［18］:

图4 给出EDF、HVF 和MFS 算法的HVR 在不同负载情况下的变化。其中横坐标是负载，纵坐标是HVR 的值。

图4 HVR 的对比

4 结束语

生产过程管理中的事件处理系统不同于一般的实时任务使系统，具有软实时的特性，现有的实时操作系统的调度算法不能直接使用。本文通过对实时调度算法的研究，提出了一种多特征综合的实时调度算法，并且进行了测试和比较。通过实验结果的对比，本算法很好地实现了设计的初衷，关键任务没有抢占过多的系统资源，对其余任务没有影响，具有应用价值。

［1］Burchard A，Liebeherr J，Oh Y F，et al.New strategies for assigning real-time tasks to multiprocessor systems［J］.IEEE Transactions on Computers，1995，44(12):1429-1442.

［2］Kieckhafer R M，Walter C J，Finn A M，et al.The MAFT architecture for distributed fault tolerance［J］.IEEE Transactions on Computers，1988，37(4):398-405.

［3］庞丽萍.操作系统原理［M］.第3 版.武汉:华中科技大学出版社，2000:110-150.

［4］Gopalan K.Real-Time Support in General Purpose Operating Systems［R］.ECSL Technical Report TR92，State University of New York at Stony Brook，2001:63-71.

［5］韩忠华，史海波，刘昶，等.客车生产中可重入倒排产应用研究［J］.沈阳建筑大学学报(自然科学版)，2010，26(6):1219-1224.

［6］Isovic D，Fohler G.Efficient scheduling of sporadic，aperiodic，and periodic tasks with complex constraints［C］//Proceedings of the 21st IEEE Real-Time Systems Symposium.Florida，USA，2000:1153-1161.

［7］Liu C L，Layland J W.Scheduling algorithms for multiprogramming in a hard-real-time environment［J］.Journal of ACM，1973，20(1):46-61.

［8］刘怀，费树岷.基于EDF 的分布式控制系统容错调度算法［J］.软件学报，2003，14(8):1371-1378.

［9］张拥军，张怡，彭宇行，等.一种基于多处理机的容错实时任务调度算法［J］.计算机研究与发展，2000，37(4):425-429.

［10］Hamdaoui M，Ramanathan P.A dynamic priority assignment technique for streams with (m，k)-firm deadlines［J］.IEEE Transactions on Computers，1995，44(12):1443-1451.

［11］Cen Shanwei，Pu C，Staehli R，et al.A distributed realtime MPEG video audio player［C］// Proceedings of the 5th International Workshop on Network and Operating System Support of Digital Audio and Video.Durham，New Hampshire，USA，1995，1018:142-153.

［12］Yau D K Y，Lam S S.Adaptive rate-controlled scheduling for multimedia applications［J］.IEEE/ACM Transactions on Networking，1997，5(4):475-488.

［13］Nieh J，Lam M S.Integrated processor scheduling for multimedia［C］// Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video.1995:215-218.

［14］何军，孙玉方.提高软非周期任务相应性能的调度算法［J］.软件学报，1998，9(10):721-727.

［15］涂刚，阳富明，卢炎生.基于动态优先级策略的最优软非周期任务调度算法［J］.计算机研究与发展，2004，41(11):2026-2034.

［16］Bernat G，Burns A.Combining (n，m)-hard deadlines with dual priority scheduling［C］// Proceedings of the 18th IEEE Real-Time Systems Symposium.San Francisco USA，1997:46-57.

［17］Guillem Bernat Nicolau.Specification and Analysis of Weakly Hard Real-Time Systems［D］.Universitat de les Illes Balears，Spain，1998.

［18］Damir Isovic.Handling Sporadic Tasks in Real-time Systems-CombinedOffline and Online Approach［D］.Malardalen University，Sweden，2001.