高利用率集合Sporadic实时任务调度方法研究
2021-08-04黄姝娟曹子建
黄姝娟,肖 锋,曹子建
(西安工业大学计算机与工程学院 西安 710021)
当前嵌入式多核平台对具有严格时间限制的复杂应用提供了强有力的计算执行能力[1]。然而随着嵌入式系统复杂性的攀升,实时调度也更具挑战性[2]。在嵌入式多核平台下,大部分算法基于Partitioned[3]或Global[4-5]调度方法,近年来Semipartitioned[6-7]调度方法逐渐获得大家的重视。该类调度算法吸取了前两者的优点,即在Partitioned调度算法的基础上允许少部分任务迁移,被建议用在支持暗含时限的软实时Sporadic任务系统中[8]。此后,还被应用于混合关键系统中[9-12]。然而,无论哪种应用,该类调度算法始终要求在一定的时限延迟的基础上进行讨论,而且任务迁移仅在job的边界上进行,否则系统开销太大。但随着当前多核能力的提高,嵌入式系统的集成度越来越高,导致高利用率的任务也越来越集中,系统运行的负荷增大,因此Semi-partitioned调度算法划分方案的精确性以及减少迁移和系统运行开销就成为研究热点。
目前针对高利率集合的semi-partitioned调度算法,如EDF-fm[13](earliest-deadline- first-based fixed and migrating)和 EDF-os[14](earliest-deadline-firstbased optimal semi-partitioned),都存在迁移次数较多和上下文切换开销较大的问题。本文在这两种调度算法的基础上,提出一种基于最少迁移度和分割度(earliest-deadline-first-based migrating and splitting tasks least, EDF-MSTL)的调度方法,旨在提高系统效率的同时,减少分割任务的数量和不必要的迁移和任务切换开销。
1 Sporadic实时系统任务调度模型
假设一个实时系统 τ由n个周期性任务组成,记为 τ ={τ1,τ2,···,τn}。每个周期任务都包含4个参数。即 τi(ri,ei,pi,di)(1≤i≤n), 其中ri表示发布时刻(release time),即处理器核响应的时刻,ei表示任务Ti最坏情况下的执行时间(worst-case execution time, WCET),pi是 τi的 周 期 时 间,di表 示 时 限(deadline),ei≤di≤pi。 若di=pi,称该系统为隐含时限系统(implicit deadlines),将其任务称为隐含时限任务。如果di<pi,称该系统为包含时限系统(constrained deadline system),将其任务称为包含时限任务。如果两者没有强制性的约束条件则称为任意时限系统(arbitrary deadline system)。用τi(ri,ei,pi,di)表示包含或任意时限系统, τi(ri,ei,pi)表示暗含时限系统。τi的 第j(j≥1)个 job,用Ji,j表示。一个任务的第一个job可以在任何时刻被发布。将Ji,j的发布时间记为ri,j, 将其绝对时限di,j定 义为ri,j+di,Ji,j的 执行时间记为ei,j。
Sporadic任务模型指n个重复发生的任务τ={τ1,τ2,···,τn}, 每个 τi具 有3个参数特征:ei(ei≥0)指示WCET;周期pi>ei, 指示一个 τi连续两次job之间的最小间隔。时限di≥ei, 指示τi的每个job在它发布之后到其完成时的最大时间间隔。τi是顺序执行的,在同一个时间只有一个job在执行。Sporadic任务模型与周期模型不同之处在于两个连续job发布的时间间隔不固定,其中最小的时间间隔成为该任务的周期。周期型任务模型可以视为Sporadic任务模型的一个特殊情况,即该任务中连续job发布是由固定pi时间单元分割的。本文着重讨论隐含时限的周期任务和Sporadic任务都存在的系统。
多核模型:P={P1,P2,···,PM}为含有M个具有相同处理能力的处理器集合。在某个时间段内,分配到某个处理器Pm上 的任务 τi的 第j次job被激活,那么在该处理器上执行该任务的第j次job的时间片段记为Ti,j,m。
由以上可知,实时系统中的周期任务具有4个重要属性:发布时间ri、 时限di、 最坏执行时间ei和周期pi。
2 相关定义、定理和结论
定义5 如果存在高利用率系统SH,在某种调度算法S下,定义该系统迁移度 migrat_λs为所有任务需要迁移的次数之和与所有任务利用率因子总和的比值。迁移度越小说明需要迁移的次数也越少,系统迁移开销也就越少。定义该系统任务的分割度 split_λs为被分割的任务数量与系统任务总数量的比值。任务分割度越少,说明需要被迁移的任务数量越少,系统的执行效率就越好。
3 高利用率任务集合
将具有6个暗含时限的实时周期任务 τ1(4,6)、τ2(2,3)、 τ3(5,6)、 τ4(2,3)、 τ5(1,2)、 τ6(2,3)分配到4个处理器上,从0时刻发布,按照GEDF调度方法会得到调度图序列如图1所示。可以看出, τ2和 τ4在3个处理器上来回迁移, τ5也在两个处理器上迁移, τ3和 τ6仍然有丢失时限发生。可以看出这种调度迁移开销太大且仍有时限丢失现象。而semipartitioned算法将调度过程分为两个阶段:离线分配阶段和执行阶段。在分配阶段只允许少部分任务为迁移任务,其他任务不允许迁移。EDF-fm算法、EDF-os算法和EDF-MSTL算法区别在于离线分配阶段:EDF-fm算法类似深度优先分配,即将一个处理器份额全部占用完之后再分配下一个处理器,如图2所示,所以任务最多在两个处理器上迁移。EDF-os算法类似广度优先遍历,先将任务按照利用率从高到低降序排列,然后将和处理器数量相同的任务依次分配到处理器上作为非迁移任务,再从第一个处理器上依次分配该处理器的剩余份额,如图3所示。
图1 GEDF算法执行12个时间片结果
图2 EDF-fm算法任务分配的份额
图3 EDF-os算法任务分配的份额
这两种算法中的迁移任务都会按照一定的比例将不同数量的job分配到指定的处理器上,比例计算方法为:
式中,fi,j为第i个任务分配到第j个处理上job数量的比例;si,j为该第i个任务在第j个处理器上获得的份额。本例中EDF-fm算法分配给任务对应的份额矩阵为:
EDF-fm算法任务对应的job比例矩阵为:
从这里可以看到τ2(2,3)被分配到处理器P1和P2上,分配的job比例为1∶1;那么调度时就会将奇数项job配到P1,偶数项job分配到P2。τ3(5,6)在P2和P3分配的job的比例为4∶1,那么5个job中就有一个job被分配到P3处理器上。 τ5(1,2)在P3和P4处理器上job分配的比例为1∶2。同理,可以得到EDF-os算法的分配份额和任务job的执行比例。
这两种算法在执行阶段,迁移任务要比非迁移任务优先级高,而当某处理器执行两个迁移任务时,该处理器为非第一次分配处理器的迁移任务优先级最高。
EDF-os算法分配给任务对应的份额矩阵为:
EDF-os算法任务对应的job比例矩阵为:EDF-fm和EDF-os具体执行结果如图4和图5所示。
图4 EDF-fm算法执行12个时间片结果
图5 EDF-os算法执行12个时间片结果
EDF-MSTL算法任务对应的job比例矩阵为:
图6 EDF-MSTL算法执行12个时间片结果
4 算法实现
EDF-MSTL调度方法描述如下:
1) 首先将n个任务的利用率因子按照从大到小顺序排列放入集合SH,m个处理器顺序放入集合P中,初始化矩阵sn,n,si,i=ui,其他值为0。
2) 找到具有最小利用率因子的任务un,将其拆分为两部分un=ui+uj, 其中ui与第一个具有最大利用率因子任务的利用率之和为1,即ui+u1=1,设置sn,k=ui,sn,n=uj,并将这两个利用率因子从集合SH中删除,如果uj为0,则也将其从SH中删除,将处理器k从集合P中删除。
3) 在剩下的SH集合中继续重复步骤1)的工作,直到处理器集合为空为止。得到sn,m即为所分配份额。根据该份额通过式(1)计算fn,m。利用fn,m中的值,在调度执行过程中进行按比例分配相应的任务job,可以得到相依的执行序列。具体计算任务份额的算法流程图如图7所示。
图7 EDF-MSTL计算任务份额的流程图
5 实验结果
本文测试的环境是在一个Intel®Core™2 Quad Q8400多核平台上。分别采用EDF-fm,EDF-os,EDF-MSTL这3种调度方法进行比较。测试方法随机产生1 000个任务集,每个任务集中产生50个参数不等的Sporadic软实时周期任务,所有周期任务都满足利用率大于0.5,执行时间小于时限,时限小于或等于周期。在整个仿真实验过程中,为了描述算法之间的性能差异,采用多次模拟求平均值的方法得到某时间段内的系统吞吐率以及任务切换job数量所占总job数的比例,如表1所示。
表1 3种算法的系统利用率和丢失时限任务数所占总任务的比例
另外,选择对应这10个任务集的平均任务迁移度和任务分割度两个方面进行性能对比。从表1、图8和图9可以看出,EDF-算法和EDF-MSTL算法在系统吞吐率、任务切换job数、任务迁移度和任务分割度方面,后者算法明显占据优势。
图8 3种算法任务迁移度
图9 3种算法的任务分割度
6 结 束 语
本文的目的是为了解决在嵌入式多核平台下,任务全部属于高利用率因子集合的软实时系统中的实时周期任务的调度问题。在EDF-fm和EDF-os算法的基础上,提供一种基于最少迁移度的多核实时调度方法,减少了现有技术中存在由于迁移带来的过多开销以及上下文切换次数,在任务量很大的情况下可以大大提高系统的整体效率。