王文乐,龚 俊,曹重华,曹远龙,陈洪琪,柯胜男,涂 珍

1(江西师范大学 软件学院,南昌 330022)2(江西财经大学 软件与通信工程学院,南昌 330032)3(江西科技师范大学 数学与计算机科学学院,南昌 330038)

1 引 言

实时应用环境中,系统首先保证任务的成功率,从而获得较好的资源利用率.传统的实时系统研究对象大都是硬实时任务,即任务错过其截止期即无效.而现实中许多实时应用,如多媒体、网络传输和大数据处理等,其任务具备软实时特性,即:错过截止期之后一段时间,仍然能够带来系统收益.Anderson[1]等提出的调度方法,获得较好的调度性能与任务延迟率.Ma等[2]分析内核可靠性和温度之间的关系,提出一种调节内核频率/电压的启发式算法以控制内核利用率,提高了软实时系统的生命期.Y.Du 等[3]研究云计算环境,在可行的服务质量(QoS)区域开发非空白资源分配的一般外界,并通过有利于具有最大QoS缺陷实时任务、动态优化其内在约束,提高了资源分配效率.Barbieru[4]基于Hadoop大数据环境设计了一个实时作业调度程序,能够处理需要实时执行的小任务,并解决了长任务完成时间不确定的问题.Palopoli等[5]提出一种利用无限状态离散时间马尔可夫链的调度算法,通过封闭形式的保守约束,降低了软实时系统中周期性任务的截止期错失率.孙景昊等[6]针对伪多项式时间判定算法的局限性,提出同/异步实时系统上EDF可调度性分析问题统一的多项式时间线性松弛求解方法,提高了可调度性任务的比例.郭锐锋等[7]针对不同类型的实时任务,提出了一种分层框架进行相应调度,降低了任务的截止期错失率.综上,现有的软实时调度研究,首先考虑系统任务的成功率,而未充分考虑其价值收益.

实时调度策略按照是否抢占分为非抢占式调度和抢占式调度两种.非抢占式调度策略可能造成高优先级任务被低优先级者阻塞而降低系统的可调度性.抢占式调度策略中,正在执行的任务随时可能被高优先级任务抢占,直到该高优先级任务完成.不过,由于任务抢占时,系统需要上下文切换、总线和缓冲区等相关资源代价,过多的抢占也会消耗系统资源而影响调度性.因此,需要限制系统中的抢占行为,而设置抢占阈值是一个好的选择,它具有较低的实施代价和较高的执行效率.Bertogna等[8]提出一种单核平台上的有限抢占动态调度策略,具有良好的调度性能和低的系统开销.李琦等[9]提出基于EDF思想的动态模糊阈值软实时调度策略,获得了较好的CPU利用率和系统成功率.夏家莉等[10]对硬实时环境,提出针基于任务执行紧迫度的调度方法,能够有效提高任务的成功率和收益.

本文以软实时任务为主要研究对象,采用基于抢占阈值的动态调度思想,综合考虑实时任务的紧迫性和价值,提出一种采用抢占阈值的动态调度策略(Preemption Threshold in Soft real-time Task Dynamic Scheduling strategy,简称 PT-STDS).

2 任务模型

2.1 软实时任务模型

系统中实时任务集合记为T={T1,T2,…,Tn},对于每一个任务Ti,它具有如下属性,如表1所示.

表1 任务Ti的属性列表Table 1 Properties list of task Ti

●Ti的价值函数:Vi(t).软实时任务Ti满足:Vi(t)>0,其中t∈[di,cri).任务的价值函数Vi(t)将在2.2节详细分析.

● 价值密度函数:VDi(t).在t0时刻,满足:VDi(t)=Vi(t)/rti.VDi(t)会随着rti数值的减少而不断增长.

定义1.任务Ti的软剩余可执行时间:slti.在t0时刻,满足:slti=cri-t0.

为了明确本文的研究内容,做出如下假设:

假设1.仅考虑系统中的CPU时间资源,不考虑空间、I/O或数据等资源;

假设2.任务之间除了存在CPU竞争外,不存在其它的触发、嵌套等依赖关系;

假设3.文中不考虑任务间上下文切换所造成的时间代价;

假设4.系统中进入调度的任务Ti都满足slti>rti,即任务在任何时刻都保证有足够时间完成.

假设5.任务Ti价值函数Vi(t)在[di,cri)区间呈线性下降;

假设6.当任务Ti执行在[di,cri)区间执行时,为了保护该类任务的执行,Ti不允许被抢占.

2.2 软实时任务的价值函数和价值密度

根据假设4,软实时任务Ti在t时刻的价值函数Vi(t)满足(1)式:

(1)

如(1)式中,当t

价值密度函数VDi(t)=Vi(t)/rti,根据(1)式可得(2)式:

(2)

从(2)式可知,VDi(t)不仅与Vi(t)有关,而且与rti有关.根据任务模型定义可知,rti=eti-hti.显然,当任务Ti保持运行时,rti会随时间t增长而减小;而当Ti被挂起(阻塞)时,rti则保持不变.下面讨论价值密度函数VDi(t):

①t

(3)

当di≤t

II.当di≤t

综上,可得到定理1.

定理1.在任务Ti保持执行过程中,VDi(t)随时间增长而递增.

2.3 任务的紧迫性

任务Ti的紧迫性数值越大，意味着该任务越需要尽早执行.

从定义2可知,Ugi(t)受sti的变化影响,具体讨论如下:

● 当Ti保持执行时,随着时间t的增长sti保持不变,Ugi(t)也保持不变;

● 当Ti被抢占挂起时,随着t的增长sti不断减小,使得Ugi(t)增长.

3 软实时任务的优先级和阈值

本文用系统调度基于任务优先级驱动,而任务的优先级函数结合价值密度和紧迫性.

3.1 任务的优先级分派函数构造

根据任务调度的目的,在保证任务执行的基础上优先考虑任务带来的系统收益.因此,本文的任务优先级分派函数如下:

pri=Ugi(t)*VDi(t)

(4)

任务需要完成才能获得价值,任务的紧迫性相对其价值密度更加重要.基于此,将(4)式设计成(5)式:

pri=Ugi(t)*ln[1+VDi(t)]

(5)

根据第2章分别对价值密度VDi(t)和紧迫性Ugi(t)的分析之后,继续讨论在t时刻任务Ti的优先级pri变化:

● 当Ti在t

(6)

■ 当Ti保持执行时,根据定理1可知,ln[1+Vi/rti]随着t的增长而递增,而sti则保持不变,可知(6)式保持递增;

因此,在t

● 当Ti在di≤t

(7)

当Ti再执行Δt时间后,有:

3.2 任务的抢占阈值选取

抢占阈值的选取直接影响调度算法的性能.当系统中任务的阈值设置为无限时,调度策略变成了非抢占式策略;因此,任务抢占阈值的选择会直接影响任务的执行.下面将通过分析任务的响应时间来选取抢占阈值.

定义3.任务Ti的影响任务集EJSi(Effect Job Set).在任务Ti的执行过程内,能够抢占其执行的所有任务集合,称为Ti的影响作业集EJSi,满足:

EJSi={Tm|(prim>prii)∧(Dm>Ai)∧(Am

(8)

任务Ti的响应时间Rti应该包括两个部分:估算执行时间和影响任务集的剩余执行时间之和,满足(9)式:

(9)

通过分析任务Ti的响应时间Rti,在保证Ti可调度情况下获得阈值θi的取值,选取阈值的过程如算法1所示.

明显地,算法1中有一个while循环结构,其计算复杂度为O(n).该算法在保证任务集可调度情况下,找到一个阈值的最优解.

4 基于抢占阈值的调度策略

本文调度策略是基于阈值的有限抢占调度策略,通过限制抢占次数以减少任务的阻塞时间.

定义4.pri>θj的充分必要条件是：任务Ti能够抢占任务Tj.

根据定义4,任务Ti抢占任务Tj,则必然有:pri>prj.

定理2.如果任务Ti和任务Tj互不抢占,则它们满足:(pri≤θj)∧(prj≤θi)

证明:反证法.假设存在互不抢占的两个任务:Tp和Tq,满足((prp≤θq)∧(prq≤θp))

⟹(prp>θq)∨(prq>θp),则根据定义4,现在对该式可能的两种情况进行讨论:

● 若prp>θq,任务Tp能够抢占任务Tq;

● 若prq>θp,任务Tq能够抢占任务Tp;

显然地,任务Tp与任务Tq可能相互抢占,与定义4矛盾.因此,定理2得证.

4.1 基于抢占阈值的调度算法

本文抢占阈值的动态调度算法PT-STDS调用算法1确定抢占阈值,并且确定动态抢占的调度队列,具体如算法2所示.

例1.假设系统中现有以下4个任务,它们具有的属性如表2所示.

表2 系统任务集合属性Table 2 Properties of task set

现对以上任务集采用PT-STDS算法进行调度,调度过程如下:

● t=0时,T1到达.T1执行;

● t=2时,T2到达,T1已执行2(ht1=2).此时,根据(6)式计算任务优先级:pr1

● t=3.5时,T1完成.根据算法2第2行,T2执行;

● t=4时,T3到达,T2已执行0.5(ht2=0.5).此时,根据(6)式计算任务优先级:pr2>pr3,T2继续执行;

● t=6时,T2完成.T3执行;

● t=7时,T4到达,T3已执行1(ht3=1).根据(6)式计算任务优先级:pr4>pr3,根据算法1计算θ3,得:pr4>θ3.根据算法2的第13行,T4抢占T3,T3被阻塞;

● t=9时,T4完成.T3执行;

● t=12时,T3错过截止期,延迟2单位至完成;

以上调度过程,相对于LSF算法或EDF算法,减少了任务间的抢占,从而减少了任务延迟率.

4.2 算法复杂性分析

对4.1节中基于抢占阈值的调度算法分析可知,算法2中只有1个循环,即第11步是长度等于就绪队列中任务数num的循环.第13步计算阈值的复杂都为O(n),可知整个调度算法的计算复杂度为O(n*m).

5 实验仿真与性能分析

5.1 实验环境及性能指标

实验平台为Inter Core i5 2.5GHz、内存为4GB的机器,系统为Ubuntu Linux系统,所有实验程序采用C语言编写.

本实验考虑系统中的非周期性任务,任意任务Ti的到达时间服从泊松分布(λ=4),其估算执行时间eti服从[5,20]平均分布,其截止期di取值为[1.2,1.5] *eti内平均分布,其临界点cri取值为[1.2,1.5] *di,其价值Vi在[10,50]间随机选取.

本系统实验选取2000个时间单位内的任务,所有的性能取100次独立实验的结果平均值.

性能指标包括以下3个.

1.系统成功率SSR(System Success Ratio):所有成功任务的数量/系统总任务数量;

2.平均任务延迟率ATDR(Average Tasks Delay Ratio):所有任务延迟率的平均值,其中 任务延迟率= (执行延迟时间/成功任务的执行时间);

3.系统累积价值TV(Total Value):所有成功任务所获得的价值之和.

5.2 性能结果分析

基于软实时环境下的抢占阈值调度策略PT-STDS,与EDF策略和LSF策略进行对照实验,仿真的结果及性能分析如下.

1)系统成功率SSR.如图1中所示,横轴表示系统负载Load,纵轴为SSR.随着系统负载增加,任务之间的抢占加剧,造成SSR不断降低.SSR性能按从高到低的顺序依次为:PT-STDS > LSF > EDF.因为SSR的动态抢占能够适应系统环境,而其具有的抢占阈值减少了无效抢占;LSF算法虽然总是动态选择空闲时间最短的任务,但其无限制的抢占会造成系统资源浪费,导致任务错过临界点;EDF算法则选择任务的截止期最短而非最紧迫的任务执行,会造成许多任务失败,其带来的SSR最低.

2)总任务延迟率ATDR.如图2所示,ATDR随系统负载Load加剧呈增加最后下降的趋势,这是由于负载越大任务间的资源竞争越剧烈,导致任务延迟率加重;当系统负载太大时,系统会根据响应时间丢开部分不能完成的任务，从而减少了任务延迟.ATDR性能最优的是PT-STDS算法,而EDF算法导致的ATDR最高.因为PT-STDS选择紧迫性高者执行,

图1 SSR性能比较结果Fig.1 SSR performance results

并且限制了任务间抢占次数,从而减少任务的延迟.LCF算法选择空闲时间最短者时,负载较轻时ATDR性能与PT-STDS方法相当,不过当系统负载较大时,其无效抢占造成CPU资源浪费，而使得ATDR急剧增加.EDF算法选择截止期最短者执行,而截止期最短并非空闲时间最短,从而造成系统ATDR最高.

图2 ATDR性能比较结果Fig.2 ATDR performance results

3)系统累积价值TV.如图3所示,各种调度策略下TV随系统负载加剧的变化呈逐渐减少的趋势.PT-STDS算法获得了最高的TV,因为PT-STDS倾向于选择高价值密度的任务,然后依次是LSF算法与EDF算法.同种负载情况下,LSF算法获得的TV优于EDF,因为LSF总能获得更好的SSR,从而带来更高的TV性能.

图3 TV性能结果Fig.3 TV performance results

6 总 结

本文考虑软实时环境,首先,综合考虑任务的空闲时间和价值密度因素组合,给出其优先级构造函数;通过任务之间的抢占关系,确定任务被抢占的阈值.并且,提出基于抢占阈值的动态调度策略PT-STDS.实验结果显示,相对于经典的LSF或EDF方法,PT-STDS策略能够获得更好的系统性能.

下一步,我们将考虑在诸如物联网等实时约束环境,研究相关的任务处理技术.

：

[1] James H.Anderson,Jeremy P.Erickson,UmaMaheswari C.Devi,et al.Optimal semi-partitioned scheduling in soft real-time systems[C].Proceedings of the 20th International Conference on Embedded and Real-Time Computing Systems and Applications(RTCSA),Chongqing,2014:1-21.

[2] Ma Y,Chantem T,Hu X S,et al.Improving lifetime of multicore soft real-time systems through global utilization control[C].Proceedings of the 25th Edition on Great Lakes Symposium on VLSI,Pittsburgh,PA.ACM,2015:79-82.

[3] Du Y,G.de Veciana.Scheduling for cloud-based computing systems to support soft real-time applications[C].Proceedings of the 35th Annual IEEE International Conference on Computer Communications(INFOCOM),San Francisco,CA,2016:1-9.

[4] Barbieru C,Pop F.Soft real-time hadoop scheduler for big data processing in smart cities[C].Proceedings of the IEEE 30th International Conference on Advanced Information Networking and Applications(AINA),Crans-Montana，Swofzerland,2016:863-870.

[5] Palopoli L,Fontanelli D,Abeni L,et al.An analytical solution for probabilistic guarantees of reservation based soft real-time systems[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(3):640-653.

[6] Sun Jing-hao,Sun Jing-chang,Guan Nan,et al.Integer programming approach for schedulability of sporadic real-time systems[J].Journal of Software,2017,28(2):411-428.

[7] Guo Rui-feng,Peng A-zhen,Deng Chang-yi,et al.Adaptive scheduling strategy oriented to hybrid tasks[J].Journal of Chinese Computer Systems,2016,37(1):61-64.

[8] Bertogna M,Baruah S.Limited preemption EDF scheduling of sporadic task systems[J].IEEE Transactions on Industrial Informatics,2010,6(4):579-591.

[9] Li Qi,Ba Wei.Two improved EDF dynamic scheduling algorithms in soft real-time systems[J].Chinese Journal of Computers,2011,34(5):943-950.

[10] Xia Jia-li,Cao Chong-hua,Wang Wen-le,et al.Real-time task scheduling strategy based on load execution urgency[J].Computer Science,2014,41(2):215-218.

附中文参考文献：

[6] 孙景昊,孙景昶,关 楠,等.偶发实时系统可调度性分析问题的整数规划方法[J].软件学报,2017,28(2):411-428.

[7] 郭锐锋,彭阿珍,邓昌义,等.面向混合任务的自适应调度策略研究[J].小型微型计算机系统,2016,37(1):61-64.

[9] 李 琦,巴 巍.两种改进的EDF软实时动态调度算法[J].计算机学报,2011,34(5):943-950.

[10] 夏家莉,曹重华,王文乐,等.基于负载执行紧迫度的实时补偿任务调度策略TSCTTL[J].计算机科学,2014,41(2):215-218.