面向复杂任务集的任务调度算法*

高阳，盛德卫，文海

(北京电子工程总体研究所，北京 100854)

0 引言

测控地检设备需要对测控应答机进行全方位的测试验证，在显控软件中既存在遥测帧解析、测量解算和遥测数据存储等硬实时周期任务，也存在数传帧和遥测帧显示等软实时周期任务[1-4]。在常规的任务调度算法中，显控软件采用基于固定优先级的可抢占式时间片轮转技术对任务集进行调度，该技术在任务调度之初就给各个任务分配了固定优先级，高优先级的任务可以抢占低优先级的任务，同等优先级的任务采用时间片轮转执行[5-8]。由于该算法无法根据任务当前状态更改优先级，所以具有高优先级但截止期较长的任务将持续占据CPU资源，而具有低优先级但截止期较短的任务由于无法抢占CPU资源将会夭折。本文在基于优先级的可抢占式时间片轮转技术的基础之上，综合考虑了任务周期、相对截止期和空闲时间3个因素动态计算任务优先级，并引入抢占阈值的思想，提出了一种面向复杂任务集的动态双优先级任务调度策略，旨在提高硬实时周期任务满足截止期的概率，减小软实时周期任务的平均响应时间[9-11]。

1 传统的任务调度策略分析

基于Windows CE操作系统的显控软件对于多任务的调度采用基于固定优先级的可抢占式时间片轮转技术，可以将任务调度的时机总结如下：

(1) 显控软件为当前任务分配的时间片耗尽，当前任务让出CPU资源并进入队尾，调度模块调度就绪队列中下一个就绪的任务执行。

(2) 在当前任务执行过程中，具有更高优先级的任务准备就绪，立即保存当前任务的上下文并将其状态设置为阻塞态，高优先级的任务获得CPU资源开始执行。

(3) 显控软件当前执行任务的状态发生改变，如被阻塞或挂起[12-13]。

下面针对相同优先级的任务按照时间片轮转和高优先级任务抢占低优先级任务两种情况对显控软件中任务调度策略进行分析。本文将基于测控地检设备显控软件中的任务抽象为2种模型：硬实时周期任务和软实时周期任务。硬实时周期任务为

软实时周期任务为

(1) 相同优先级任务按照时间片轮转

如图1所示，任务τH1，τH2和τH3具有相同的优先级。其中任务τH1先于τH2先于τH3处于就绪状态。显控软件调度模块首先调度任务τH1执行，在执行完一个时间片后，任务τH1未执行完毕，则将τH1的上下文保存，τH1进入就绪队列的队尾，等待显控软件下一次调度。然后，调度模块调度任务τH2开始执行，与τH1相似，τH2在执行完一个时间片后，将上下文状态保存并进入队尾。同理τH3在执行完一个时间片后，显控软件将重新调度就绪队列中的任务τH1，τH2和τH3，将状态恢复并继续执行完成。

(2) 高优先级任务抢占低优先级任务

如图2所示，任务τS1和τS2具有同等的低优先级，任务τH3具有较高优先级。其中任务τS1和任务τS2首先处于就绪状态。由于任务τS1和τS2具有相同的优先级，2个任务将按照时间片轮转交替执行，任务τS1在执行完一个时间片后，将状态保存并进入队尾，任务τS2获取CPU使用权开始执行，在τS2执行过程中，具有更高优先级的任务τH3处于就绪状态，则τH3立即抢占CPU资源开始执行，τS2将上下文状态保存并进入队尾，具有更高优先级的任务τH3将持续占据CPU资源直至其执行完毕，然后任务τS1和τS2被唤醒继续按照时间片轮转交替执行。

这种调度策略保证了显控软件中价值高的任务具有较高的优先级，从而优先获取资源来执行，实现了任务执行的轻重缓急，同时时间片轮转技术保证了相同优先级的任务可以平等的使用CPU资源。而这种调度策略的劣势在于任务的优先级在任务执行之初就已固定，由于无法根据任务的当前状态动态地改变优先级，高优先级的任务持续占据CPU资源，而剩余空闲时间较小的低优先级任务由于无法获取CPU资源而错失截止期。

采用下述模型对显控软件中更为复杂的任务集进行分析：假设显控软件中存在2个硬实时周期任务和1个软实时周期任务，硬实时任务模型可以表示为THi=(Ti,Di,di,Pi,tslot,ei,tarriv)，软实时任务表示为TSi=(Ti,Di,di,Pi,tslot,ei,tarriv)，2个硬实时任务分别为TH1=(80,80,80,253,100,20,0)，TH2=(90,90,90,248,100,30,0)，软实时任务为TS1=(110,100,100,251,100,40,0)，如果采用常规的基于固定优先级的调度策略，显控软件对此任务集的调度如图3所示。

在上述模型中，3个任务在0时刻同时达到，由于TH2优先级高于TS1高于TH1，所以TH2优先执行，TH2执行了30 ms后执行完毕，交出CPU使用权，显控软件的调度模块调度具有第2优先级的TS1开始执行，TS1在40 ms后执行完毕，调度模块调度TH1开始执行，TH1执行了10 ms便到达其截止期，此时TH1还未执行完毕，由于TH1是硬实时任务，所以实际上TH1在这次任务调度中已经夭折了。TH1继续执行了10 ms后TH2到来，由于TH2具有更高的优先级，因此立即抢占CPU资源开始执行，TH1保存上下文状态进入队尾。在后续任务调度中，可以发现TH1由于优先级较小且无法动态改变而多次夭折。这种任务调度对于地检设备显控软件而言显然是不合理的。

2 面向复杂任务集的动态双优先级任务调度算法

2.1 动态优先级任务调度策略分析

针对显控软件中硬实时周期任务和软实时周期任务本身不同的特点，提出2种不同的优先级计算公式，对于硬实时周期任务，主要考虑相对截止期和剩余空闲时间2种因素，对于软实时周期任务，主要考虑任务周期和剩余空闲时间2种因素。

(1) 硬实时周期任务

硬实时周期任务的优先级计算结合剩余空闲时间、相对截止期和系统时间片3方面因素。由于相对截止期对于硬实时周期任务具有重要意义，故将其作为优先级计算的因素，可如果只考虑相对截止期，会使截止期较长的任务由于优先级较低而迟迟得不到响应，从而错过截止期，故引入剩余空闲时间这一因素，通过相对截止期和剩余空闲时间共同作用计算优先级。硬实时周期任务的优先级计算公式为

PHi=Pinit+(di-t-eri+Di)/n/tslot·Prange，

(1)

式中：Pinit设置为显控软件中用户应用程序的最高级，取值248，由于优先级最小等于255，故优先级变化范围Prange取值7；(di-t-eri+Di)/n/tslot为优先级变化系数Ki，显然Ki要在0至1之间变化，下面给出证明如下。周期任务的相对截止期Di小于任务周期Ti，而剩余空闲时间di-t-eri

(2) 软实时周期任务

软实时周期任务的优先级计算结合任务周期、剩余空闲时间和系统时间片3方面因素。优先级计算公式为

PSi=Pinit+(di-t-eri+Ti)/n/tsolt·Prange，(2)

式中:Pinit取值248；Prange取值7；系数Ki=(di-t-eri+Ti)/n/tslot，下面对系数0

2.2 动态双优先级任务调度算法分析

计算动态优先级时引入了剩余空闲时间，会产生“颠簸”现象。下面通过建立一个模型分析一下“颠簸”现象给任务调度带来的影响。

建立如下模型Ti=(di,ei,eri,tslot,tarriv)，显控软件任务集中存在3个任务T1=(12,5,5,1,0)，T2=(13,5,5,1,0)和T3=(14,7,7,1,0)，为了方便分析，系统时间片tslot取值1，任务到达时刻tarriv取值0。采用基于剩余空闲时间的调度策略对此任务集的调度如图4所示。

由于当前正在执行的任务剩余空闲时间不变，而处于就绪队列中的任务剩余空闲时间随时间不断减小，当任务集中存在多个剩余空闲时间相近的任务时，任务的优先级将会不断进行翻转，产生频繁的任务切换，降低软件的调度性能。在对上面的任务集进行调度的过程中，只有任务1在截止期内执行完毕，其余任务均夭折。由于3个任务均分CPU资源，使得CPU利用率非常低。解决“颠簸”现象的方法是在任务调度时引入抢占阈值，形成双优先级策略。本文在动态优先级的算法基础之上提出了一种基于剩余空闲时间的抢占阈值算法，有效降低了任务的切换次数，提高了CPU利用率。

抢占阈值算法采用双优先级调度策略，即显控软件中每个任务除了拥有一个根据其参数状态计算的动态优先级外，还会在任务执行时被赋予第2优先级，称之为抢占阈值。规定如果显控软件中其余任务要抢占当前任务，其动态优先级不仅要比当前任务的动态优先级高，还要比当前任务的抢占阈值高，否则抢占失败，当前任务继续执行。

抢占阈值算法是抢占算法和非抢占算法的结合。当抢占阈值比动态优先级小或与之相等时，可以看做是抢占算法；当抢占阈值很大时，可以看做是非抢占算法。抢占算法的优势在于能够对紧急任务做出及时响应，但容易造成过多的任务切换。非抢占算法的优势在于能够降低任务截止期的错失率，但对于紧急任务的响应不够及时。抢占阈值算法结合了2种算法的优势，通过对阈值的合理取值，既能保证对紧急任务的及时响应，又能降低任务错过截止期的概率。

本文提出的基于剩余空闲时间的抢占阈值计算方法如式(3)所示：

(3)

式中：Pinit为显控软件中用户应用程序的最高级；Prange为优先级的取值范围，取值7；Li为任务当前的剩余空闲时间；Lmax为剩余空闲时间的最大值，可以表示为任务的相对截止期与任务执行时间之差，即Lmax=Di-ei；u为临界参数，取值Lmax/4。

式(3)的含义为，当剩余空闲时间在[0,u]范围内时，认为当前任务剩余空闲时间较小，设置当前任务的抢占阈值为最高优先级，禁止其他任务抢占该任务，从而有效提高了任务完成截止期的概率。当剩余空闲时间较大时，通过剩余空闲时间所占的比例动态计算抢占阈值，降低了任务的切换次数，提高了显控软件性能。

3 实测结果验证及分析

测试平台选用基于OMAP3530芯片的Devikit8000硬件平台，Windows CE6.0操作系统。显控软件任务集包括测量解算和遥测数据解析2个硬实时周期任务及遥测数据显示和网络通信2个软实时周期任务，使用如下模型对任务集进行描述。

(4)

采用原始算法和动态双优先级调度算法分别对显控软件任务集进行调度。通过设置定时器任务的数量调整系统的负载值，采集2种算法在不同负载下运行2 500 ms后的执行情况，重点关注硬实时周期任务调度成功率、软实时周期任务平均响应时间和任务切换次数3个性能指标。对5次实验的测试结果取平均值，记录如表1所示。

为了更加直观地分析原始算法和改进算法各类性能指标随负载变化的情况，将表1绘制成图5、图6和图7。分析图5可知，对于测量解算等硬实时周期任务而言，采用动态双优先级调度算法比原始算法获得更高的调度成功率，随着显控软件负载增加，动态双优先级调度算法的优越性也更加明显，这是因为硬实时周期任务优先级的计算结合了相对截止期和剩余空闲时间2种任务属性，优先级分配更加合理。分析图6可知，对于遥测数据显示等软实时周期任务而言，由于其优先级的计算结合了剩余空闲时间，改进算法比原始算法获得更低的平均响应时间，同样随着显控软件负载增加，改进算法的优势也更加明显。

表1 调度算法优化前后各类性能指标对比Table 1 Comparison of various performance indexes before and after the optimization of scheduling algorithm

分析图7可知，改进算法和原始算法的任务切换次数随负载的变化趋势相似，均在负载等于一附近达到峰值，改进算法通过引入抢占阈值的概念，改善了由于剩余空闲时间带来的“颠簸”现象，有效降低了任务切换次数。

4 结束语

本文针对常规任务调度算法无法根据任务状态实时更改优先级，高优先级任务持续占据CPU资源，而截止期较短但优先级较低的任务由于无法抢占CPU资源而夭折的问题，提出了一种面向复杂任务集的动态双优先级任务调度算法，在时间片轮转技术的基础上，综合考虑任务的当前状态，针对硬实时周期任务和软实时周期任务采用不同的优先级计算策略，并针对引入剩余空闲时间导致的“颠簸”现象，提出了一种抢占阈值的计算方法。理论分析和实测数据均证明了动态双优先级任务调度算法的优越性，改进算法提高了硬实时周期任务的调度成功率，减小了软实时周期任务的平均响应时间，降低了任务切换次数，理论分析和实测数据均证明了该算法的优越性。