支持缓存划分的全局EDF实时系统调度策略

林宇晗, 严 健, 王侃侃, 邓庆绪

(东北大学 计算机科学与工程学院, 辽宁 沈阳 110819)

近年来,现代多核处理器技术日趋成熟,其在实时嵌入式系统领域的应用也逐渐普及.为了提高系统平均性能,大部分多核处理器都支持共享缓存(Cache)技术.然而由于多核处理器对共享缓存的争用,在各个核上并行执行的实时任务可能会显著延迟[1].特别是在缓存资源紧张的嵌入式系统中,缓存争用导致的延迟发生的时刻,次数和持续时间都是不确定的,因此严重影响了实时系统的时间可预测性.传统上,为了保证调度的时间正确性,系统设计人员通常假设所有实时任务都受到最大的争用延迟作为最差执行时间(WCET)的一部分从而为任务预留足够的系统资源.但是这种基于悲观假设的方法不仅造成极大的系统资源浪费,而且抵消甚至降低了共享缓存对系统性能的提升.

解决多核处理器间缓存干扰的一种有效方法是缓存划分(cache partition)技术[2],通过页着色(page coloring)[3]或通路划分(way partitioning)[4]的方法将缓存划分成多个缓存分区,并将任务映射到这些分区上执行,比如ARM的LbM技术[5-6],Intel的CAT技术[1，7]等.这样并行执行的任务总是可使用不同的分区,实现了对共享缓存的隔离.由于并行执行的任务无法访问别的任务的缓存分区,因此避免了并发的缓存访问造成的缓存干扰,从而降低了处理器核之间的互相干扰导致的额外开销并减少了任务的最坏响应时间[2].然而在实时系统中,这种技术需要根据不同任务的实际需求分配缓存分区,而且由于缓存空间有限,还需要保证任意时刻没有缓存分区重叠.这种约束可能导致任务因缓存空间不足而被阻塞.因此,传统的实时调度算法与分析方法无法有效地应对缓存共享带来的难题.

最近研究者们提出了一种缓存敏感的全局调度策略.这种策略允许在系统运行时根据任务的需求将共享缓存动态地分配给各个处理器核,同时还能允许任务在各个核上迁移以充分利用系统资源.文献[2]提出了一种缓存敏感的不可抢占全局固定优先级调度策略(FPca)和分析方法.由于不允许任务抢占,这种策略虽然避免了抢占带来的开销,但是可能导致优先级反转使得高优先级任务受到过长的阻塞而错失截止期.在此基础上,文献[1]提出了一种缓存敏感的可抢占全局固定优先级调度策略(gFPca)并分析了抢占造成的开销.然而,以上工作都是基于固定优先级的调度(即任务的优先级是静态分配的),并不适用于动态优先级调度,特别是全局EDF(earliest deadline first)调度.

可抢占全局EDF调度策略允许系统在运行中根据最早截止期优先的规则动态生成任务的优先级.因此这种调度策略相比于固定优先级更适用于开放系统(open system).文献[8-11]针对可抢占全局EDF调度研究了基于时间窗口和干涉量估计相结合的分析方法.然而这些方法都没有考虑缓存划分技术带来挑战.

本文针对可抢占全局EDF采用缓存划分技术的问题进行研究.结合已有的缓存敏感全局调度及分析的思想[2,5，12],本文提出了一种支持缓存划分技术的可抢占全局EDF调度算法(gEDFca)及其可调度性分析方法.不同于现有的工作，本文首先提出了一种新的缓存敏感调度算法；在此基础上分别讨论了只考虑处理器和只考虑缓存的可调度条件；并且针对现有分析的缺陷,提出了一个优化算法；综合以上提出了一个基于线性规划的可调度条件；最后通过实验验证了调度分析的有效性.

1 系统模型

本文研究一个支持共享缓存划分的多核处理器.这种处理器包含M个相互独立的同构处理器核(以下简称核)以及A个大小相等相互独立的缓存分区.所有核都可以访问这些缓存分区.

考虑一个相互独立的偶发性(sporadic)任务集τ={τ1,τ2,…,τn}.任务τi由一个四元组(ei,di,pi,ai)表示,其中,ei表示任务的最差执行时间(worst-case execution time, WCET),di表示任务的相对截止期(relative deadline),即任务释放后必须完成的时间长度,pi表示任务的周期,即两个连续释放的任务实例之间的最小时间间隔,ai表示的是任务需要占用的缓存分区的个数.任务的松弛时间为Sk=dk-ek.需要注意的是,本文仅考虑限制截止期(constrained deadline)任务,即0

2 调度算法

上节讨论了系统的模型与定义,本节给出一种支持缓存划分的可抢占全局EDF调度算法(gEDFca).这种算法将EDF策略应用到缓存敏感的全局调度中:绝对截止期越早的作业被分配的优先级越高.与经典的全局EDF(gEDF)策略[11]不同,在gEDF中系统总是可以并行执行M个就绪任务,而在gEDFca中系统还需要考虑可用缓存分区数量的限制.

1) 除了高优先级的任务占用的,当前至少有一个处理器核可用；

2) 除了高优先级的任务占用的,当前至少有Ai个缓存空间可用；

由于本文只考虑限制截止期任务,即di≤pi,因此每个任务在任意时刻最多只有一个作业正在执行.算法的伪代码如下所示.

算法1 gEDFca算法.

输入:Qready

输出:Qrun

1:Qrun←∅;Qready←All ready tasks

2:whileQready≠∅do

3:τi←first(Qready)

4:if(1+|Qrun|≤M)∧(Ai+∑τk∈QrunAk≤A)then

5:Qrun←Qrun∪{τi}

6:endif

7:Qready←Qready{τi}

8:endwhile

9:returnschedule(Qrun)

算法1的输入为就绪任务队列Qready,该队列包含所有已释放但还未完成的任务,且按最早绝对截止期优先排序.算法的输出为执行队列Qrun.其中,函数first(Qready)返回的是队列Qready中优先级最高(绝对截止期最早)的任务.函数schedule(Qrun)表示的是让系统调度执行任务队列Qrun:如果当前正在执行的任务在队列Qrun,那么保持执行;如果当前正在执行的任务不在队列Qrun,那么释放所占用的核和缓存分区(即被抢占);最后让在队列Qrun中且当前不在执行的任务占用剩下的核和资源并开始执行.

算法的第1行首先初始化了队列Qrun和Qready.算法的第2～8行循环是算法生成执行队列Qrun的主要过程.在每次循环中,找到当前就绪任务中具有最早截止绝对期的任务(第3行),并检查是否满足当前核和缓存分区的约束(第4行),如果满足就将该任务加入执行队列Qrun中(第5行),循环最后将该任务从就绪队列Qready中移除(第7行).算法重复执行上述循环直到Qready为空.算法结束时就可以得到当前的执行队列.

需要注意,虽然算法采用了最早截止期优先的策略,有些缓存需求较大的高优先级任务可能会由于缓存空间的限制而被阻塞.为了减少系统资源的浪费,算法允许其他具有较晚截止期却满足缓存空间约束的任务在这种情况下利用空闲资源优先执行.

表1 一个任务集例子

图1 gEDFca调度实例示意图

3 可调度分析

结合gEDF和FPca调度分析方法的思想[2，12]对gEDFca的可调度性问题进行分析,并针对已有方法的缺陷,提出一种优化算法,最后结合优化算法提出一种基于线性规划的gEDFca的可调度条件.

3.1 问题窗口分析

在介绍关于gEDFca的问题窗口分析技术之前，需要引入几个有用的概念.

定义1在时间长度为t的时间段内,任务τi对任务τk的干涉Ii,k(t)表示为:任务τi在该时间段内使得τk就绪后无法执行所累积的最长执行时间.

定义2在时间长度为t的时间段内,任务的工作负载表示为:该任务在该时间段内需要的计算量.

引理1[2]不针对具体的调度算法,一个任务τi在长度为t的时间段内的工作负载上界为Wi(t):

Wi(t)=eiNi(t)+min(t+di-ei-piNi(t),ei) .

(1)

因此根据引理1,可以很容易得到干涉Ii,k(t)一个安全的上界:

Ii,k(t)=Wi(t) .

(2)

注意由于gEDFca允许任务间抢占,τk的问题窗口可能包含许多子区间,其总长度为Sk.根据缓存敏感调度的问题窗口分析框架理论[1-2],分析一个任务是否能被调度,首先可以讨论两种极端的情况:1)假设总是有足够的缓存空间;2)假设总是有足够的处理器核,然后放松上述约束综合出一个一般性的可调度条件.本文结合了类似文献 [1-2]中的思想,引入gEDFca问题窗口分析方法.

3.1.1 假设总是有足够的缓存空间

引理2 假设总是有足够的缓存空间,一个任务τk∈τ一定可调度如果满足:

(3)

3.1.2 假设总是有足够的处理器核

在这种情况下,只考虑缓存分区对任务的影响.根据gEDFca算法中作业被调度执行的三个条件,易得如下引理.

定义4在长度为t时间段内的任务τi缓存负载为:缓存分区数ai乘以时间段长度t.

引理3 假设总是有足够的处理器核,一个任务τk就绪后无法被gEDFca调度执行,仅当有至少A-ak+1个缓存分区被高优先级任务占用.

证明:假设一个任务τk无法执行,且存在最多A-ak个缓存分区被高优先级任务占用.那么存在至少有A-A+ak=ak个缓存分区空闲或被低优先级任务占用.由于有足够的处理器核,那么任务τk满足被gEDFca调度执行的条件而被调度执行,与假设矛盾.证毕.

引理4 假设总是有足够的处理器核,一个任务τk∈τ一定可调度如果满足:

第四，创设教师发展场域，能够凸显教学主体独立人格形成与完善的价值。教师教学自主性的生成过程也是逐渐摆脱权力场域的控制过程，是教师主体人格形成的过程，也是越来越拥有专业自信与专业自主的过程。

(4)

3.2 优化算法

根据观察发现,引理4的调度条件之所以能成立关键在于引理3的结论,即一个任务无法执行,仅当有至少A-ak+1个缓存分区被高优先级任务占用.虽然引理3的估计是安全的,但是却过于悲观.实际上,高优先级任务占用的缓存空间大于或等于1,所以由这些使得任务τk无法执行的高优先级任务占用缓存空间的组合之和的最小值大于或等于A-ak+1,即至少有A′个缓存被高优先级任务占用,其中A-ak+1≤A′≤A.直观上意味着在τk恰好满足截止期时系统实际可以利用更多的缓存空间.具体可以参考以下的例子.

输入:k,τ,A

1: ∀x∈[1,A],v[x]←False;v[0]←True;τ′←τ/{τk};

2:fori←0to|τ′|-1do

3:forj←Atoaido

4:v[j]←v[j]∨v[j-ai]

5:endfor

6:endfor

10:endif

11:endfor

算法2最多有二重循环,其中第2～6行的外层循环最多遍历n次,第3～5行的内层循环最多遍历A次,因此算法2的时间复杂度是O(An),其中处理器缓存分区总数A是常数,因此算法2是线性复杂度的.

引理5 假设总是有足够的处理器核,一个任务τk∈τ一定可调度如果满足:

(5)

3.3 可调度条件

在3.1节中将问题窗口分析技术分别应用在了两种极端的情况，并得出了相应的结论，之后在3.2节中进行了优化.本节将考虑综合上述结论，得出一般性的可调度条件.

定义6在某个时刻,处理器处于τk忙碌状态(非忙碌状态)如果所有(不是所有)M个处理器核都在执行τk的高优先级任务.在某个时间段内,如果该时间段内所有时刻处理器核都处于忙碌状态(非忙碌状态),那么这个时间段定义为忙碌期(非忙碌期).

根据定义6,易知对于任意时刻t要么处于忙碌状态,要么处于非忙碌状态,不存在其他中间状态或者t既处于忙碌状态又处于非忙碌状态.因此,可以安全地将τk问题窗口划分为两个部分:核忙碌区间和缓存忙碌区间.

定义7任务τk的核忙碌区间为τk问题窗口中的忙碌期,任务τk的缓存忙碌区间为τk问题窗口中的非忙碌期.

定义8任务τi在任务τk的核忙碌区间的工作负载为αi,k,在任务τk的缓存忙碌区间的工作负载为βi,k.

根据定义8,任务集τ在τk的核忙碌区间工作负载之和为∑τi∈ταi,k.根据定义6,在τk的核忙碌区间,所有的处理器都在忙碌,因此τk问题窗口中的忙碌期长度的上界Xk为

(6)

(7)

根据定义1与引理1,τi在问题窗口的工作负载不超过干涉Ii,k(t)的上界,即

αi,k+βi,k≤Ii,k(Sk) .

(8)

根据定义8,任务τi在任务τk的核忙碌区间的工作负载不大于忙碌期长度的上界Xk.同理,任务τi在任务τk的缓存忙碌区间的工作负载不大于忙碌期长度的上界Yk,结合式(6)和式(7),得

αi,k≤Xk,

(9)

βi,k≤Yk.

(10)

通过以上讨论,可得如下结论.

引理6τk的问题窗口长度上界为Bk,其中Bk是如下线性规划的最优解:

subject to ∀i:αi,k+βi,k≤Ii,k(Sk) ,

αi,k≤Xk,

βi,k≤Yk.

(11)

定理1任务集τ可被gEDFca调度,如果∀τk∈τ都满足:

Bk≤Sk.

(12)

证明:根据引理6,Bk是任务τk无法执行时间的上限.而且Sk=dk-ek是任务τk的松弛时间.因此,如果满足∀τk∈τ,Bk≤Sk,那么∀τk∈τ,ek+Bk≤dk,即任务集τ所有任务都在截止期内完成.证毕.

4 实 验

为验证本文提出的可调度分析方法的有效性与效率,使用随机生成数据集进行大量的仿真实验对分析方法的可调度性和可延展性进行评估.首先进行可调度性实验来评估可调度条件的性能，然后进行可延展性实验来评估方法的效率.

4.1 实验设置

本文采用随机生成的任务集,参数设置如下:首先设置任务集的任务周期均匀分布在[10,20]内,任务资源利用率(任务的最差执行时间与周期之比)根据任务类型分为三类:轻型任务,均匀分布在[0.05,0.1]内；中型任务,均匀分布在[0.1,0.2]内；重型任务，均匀分布在[0.2,0.4]内.任务的最差执行时间由利用率与任务周期的乘积求得.任务所需的缓存均匀分布在[8,10]内.处理器核的个数M设为4,处理器缓存分区的个数A设为20.任务集通过迭代的方式生成,将每次迭代生成1个满足设置的随机任务加入到任务集中直到任务集的利用率之和大于目标值为止.最后降低最后一个任务的利用率使得任务集利用率之和等于目标值.

实验采用开源的整数规划求解工具Python-MIP工具集进行求解.实验运行在Intel Xeon 4110处理器(2.6 GHz),32 GB主存的Linux PC上.

4.2 可调度性实验

图2 调度接受率结果

4.3 可延展性实验

图3中横坐标表示任务集中任务个数,纵坐标表示引理6中线性规划的求解时间.2 000个任务的求解时间为15 s,10 000个任务的求解时间为563 s.实验结果表明，在实验平台上,一个具有数千个任务的任务集也能在数分钟内求得解,具有较高的效率.

图3 求解时间结果

5 结 语

共享缓存划分技术提供了一种减少任务执行时间不确定性的手段.本文提出一种支持缓存划分的全局EDF调度算法,并针对该算法提出了一种可调度性分析技术.通过线性规划的方法判断任务集的可调度性来保证系统的可预测性.本文还提出了一种分析优化算法,进一步提高了可调度性.随机实验显示本文的分析方法具有较高的效率和性能.