软件学报  2014, Vol.25 Issue (2): 284-297   PDF    
多处理器混合关键性系统中的划分调度策略
谷传才, 关楠, 于金铭, 王义, 邓庆绪    
东北大学 信息科学与工程学院,辽宁 沈阳 110819
摘要:多核处理器正越发广泛地应用到现代嵌入式系统的设计与实现当中,其强大的计算能力为将多个不同关键性级别的功能子系统集成到统一的共享资源平台提供了支持.混合关键性系统的调度问题即便在单处理器平台中都极具挑战性,在多处理器平台则更为困难.将目前资源利用率最高的单处理器混合关键性调度算法EY-VD扩展到多处理器平台中.首先,结合传统的划分调度策略提出了适用于多处理器混合关键性系统的MC-PEDF(mixedcriticality partitioned earliest deadline first)划分调度算法.尽管比之前的算法有更好的可调度性能,但传统的划分策略不能有效地平衡不同关键性级别下的负载,故其不完全适用于混合关键性系统.为了克服传统策略的不足,提出了划分调度策略OCOP(one criticality one partition).OCOP允许系统在关键性模式切换时对实时任务集进行重新划分,进而更好地平衡各个处理器在不同关键性模式中的资源利用率.基于OCOP,提出了第2种划分调度算法MC-MP-EDF(mixed-criticality multi-partitioned EDF).基于随机生成任务集的仿真实验结果表明,与MC-PEDF和已有的算法相比,MC-MP-EDF能够显著地提高系统的可调度性,尤其是在处理器数量较多的系统中.
关键词混合关键性系统     多处理器     划分调度     EDF(earliest deadline first)    
Partitioned Scheduling Policies on Multi-Processor Mixed-Criticality Systems
GU Chuan-Cai, GUAN Nan, YU Jin-Ming, WANG Yi, DENG Qing-Xu    
School of Information Science and Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: DENG Qing-Xu, E-mail: dengqx@mail.neu.edu.cn
Abstract: Multi-Core processors are more and more widely used in embedded systems as they provide great computing capacities to integrate multiple functionalities with different criticality levels into a shared platform. The scheduling problem of mixed-criticality systems appears to be challenging, even on single-processor platforms. This work extends the state-of-the-art single-processor mixedcriticality scheduling algorithm EY-VD to multi-processor systems. To begin with, it integrates EY-VD into traditional workload partitioning schemes to get a multiprocessor mixed-criticality scheduling algorithm MC-PEDF (mixed-criticality partitioned earliest deadline first). Although MC-PEDF performs better than previous solutions, the study finds that the traditional workload partitioning schemes are not suitable for mixed-criticality systems as it does not explore the asymmetricity of workload on different criticality levels. To overcome this problem, a workload partitioning policy OCOP (one criticality one partition) is proposed. OCOP allows tasks to be reassigned to a different processor when criticality mode switch occurs, thus can better balance the resource utilization among processors on different criticality levels. Based on OCOP, the second partitioned scheduling algorithm MC-MP-EDF (mixed-criticality multi-partitioned EDF) is constructed. Experiments with randomly generated workload show that MC-MP-EDF can drastically improve the system schedulability comparing with MC-PEDF and other previous algorithms, especially for systems with more processors.
Key words: mixed-criticality system     multi-processor     partitioned scheduling     EDF (earliest deadline first)    

随着信息技术日新月异的发展,现代嵌入式实时系统中集成功能的规模和复杂性也呈现爆炸式增长的趋势.例如,当今汽车电子系统中已经集成了数十个甚至上百个微处理器,而航空电子系统中微处理器的数量则更为庞大.为了适应未来日益复杂、庞大的系统功能需求,以及满足嵌入式实时系统硬件本身体积、成本、能耗等诸多方面的约束,将多个在传统设计中部署在独立子系统中的不同关键性功能应用集成到共享处理器资源的单一硬件平台,成为当今嵌入式实时系统设计的趋势和发展方向.而多处理器平台的出现及其迅猛发展,在极大地提升了处理器性能的同时,也为嵌入式系统功能集中化的设计方案提供了硬件性能的保障.然而,与传统的实时调度问题相比,混合关键性系统中的实时调度和可靠性认证等问题更为复杂和困难,而传统的经典调度算法(如EDF)在混合关键性系统中的资源利用率十分低下,不能直接应用于系统设计.

2007年,Vestal在文献[1]中首先形式化定义了混合关键性系统(mixed-criticality system)中的实时调度问题.之后,混合关键性系统的研究迅速成为近年来实时系统领域的热点问题,并引起了大量知名学者的关注.然而,大量的工作都集中于单处理器平台上的混合关键性系统调度问题.近年来,多处理器平台中的混合关键性系统调度问题受到了广泛的关注.

根据是否允许相同任务释放的作业在运行时执行在不同的处理器上,传统的(单关键性)多处理器调度算法通常被分为全局调度和划分调度.文献[2]证明:在强实时系统中,划分调度具有更好的可调度性.Kelly等人在文献[3]中首次提出了可抢占多处理器平台中基于固定优先级算法的划分调度问题,并分别对比了采用资源利用率降序排列(decreasing utilization,简称DU)和关键性降序排列(decreasing criticality,简称DC)这两种实时任务集排序策略以及首次适应降序(first-fit decreasing,简称FFD)、最差适应降序(worst-fit decreasing,简称WFD)等启发式划分策略对划分调度性能的影响.Baruah等人在文献[4]中提出了基于非固定优先级算法EDF-VD(EDF with virtual deadlines)[5],并采用基于DC策略的混合关键性划分调度算法MC-Partition.

然而据我们所知,目前在单处理器平台下,Ekberg等人在文献[6]中提出的算法(本文简称EY-VD)的资源利用率远高于其他已有的混合关键性算法,但仍未有基于该算法的混合关键性划分调度问题的研究.而已有的划分调度算法均基于传统非混合关键性多处理器系统中的划分策略,尚未有特别针对混合关键性系统优化的划分调度策略的研究.因此,本文首先将单处理器平台中的非固定优先级混合关键性调度算法EY-VD扩展至多处理器平台,并基于传统划分策略提出了第1种划分调度算法MC-PEDF(mixed-criticality partitioned earliest deadline first).然后,通过对传统划分策略可能导致混合关键性系统在不同关键性模式中处理器间资源利用率不平衡问题的研究,我们提出了针对多处理器平台混合关键性系统优化的划分调度策略OCOP(one criticality one partition).OCOP划分策略允许混合关键性实时任务在不同的系统关键性模式下被分配到不同的处理上执行.该方法较好地平衡了系统在不同关键性模式中各个处理器间的资源利用率,进而提升了划分调度算法的性能.基于OCOP划分策略,我们提出了第2种划分调度算法MC-MP-EDF(mixed-criticality multi-partitioned EDF).

本文第1节具体介绍系统模型和相关工作.第2节详细描述基于传统划分策略的MC-PEDF算法及其理论分析和证明.第3节讨论传统划分策略在多处理器混合关键性系统中的缺陷与局限性,并提出针对混合关键性系统优化的新型划分策略OCOP和基于该划分策略的划分调度算法MC-MP-EDF.第4节通过仿真实验对比本文提出的两种算法与之前算法的性能以及OCOP划分策略的优化效果.第5节对全文做简要的总结.

1 研究基础
1.1 系统模型与定义

在本节,我们对本文所用的混合关键性实时任务系统模型给出形式化的定义,并阐述一些相关的基本术语和概念.与传统的偶发任务模型类似,我们将混合关键性偶发实时任务系统定义为由一组有限数量且相互独立的混合关键性偶发实时任务构成的集合,其中,每个偶发实时任务都将产生任意可能次序的无限数量混合关键性作业序列.

1.1.1 混合关键性任务和混合关键性作业

我们将每个混合关键性任务定义为一个四元组:ti=(Ti,Di,Ci,zi).其中元素的具体含义描述如下:

TiR+,偶发任务的周期,表示任意两个连续释放作业间的最小时间间隔(不同于周期任务的固定周期).

DiR+,表示任务的相对截止期.

CiN+®N+,为任务的最差执行时间(WCET)函数,返回任务在某个特定关键性级别下的评估WCET 取值.例如,Ci(l)表示任务在关键性级别为l时的WCET.

zi∈{1,2,…,L},表示任务的关键性级别,约定该值越大,表示的关键性级别越高.L为该混合关键性系统中关键性级别的最大值.

需要注意的是,任意任务的相对截止期与周期之间没有任何约束关系,即,相对截止期可以小于、等于甚至大于周期.

混合关键性任务ti释放的第j个作业记为释放时间绝对截止期完成时间其中,三者大小关系为另外规定任务ti中释放的所有作业都具有相同的Ci和关键性级别zi.

为了简化系统的描述和算法分析,本文只研究包含两个关键性(即L=2)的双关键性模型.特别地,用LO表示低关键性级别,用HI表示高关键性级别.本文的结论都可以扩展到任意关键性个数的情况.

1.1.2 混合关键性偶发性实时任务系统的运行时行为

混合关键性作业在时刻由任务ti释放,需要执行单位时间.在被标志完成运行之前,准确地值无法确定.通过测量作业,运行过程中值可以用来判定混合关键性系统的运行时行为.当整个系统满足公式(1)的约束时,称系统的运行时行为是l关键性级别:

特别地,任何作业运行时间超过Ci(L)而未结束执行的运行时行为被定义为错误运行行为.本文接下来的部分,假定系统不会经历错误运行行为.公式(1)暗含每个运行中的作业的执行时间越长,将导致系统经历更高关键级别运行时行为的可能性越大.所有作业中的最高关键性运行时行为决定系统的运行时行为.

1.1.3 混合关键性任务系统的可调度性

混合关键性任务系统被要求对每个关键性级别进行独立的运行时可调度性认证.依据以上原则,本文给出调度算法A对于混合关键性任务系统p可调度的定义.

定义1(混合关键性任务系统的可调度性). 给定一种调度算法A,混合关键性任务系统可调度的充分必要条件是:当系统经历任意可能的l关键性运行时行为时,都能够满足公式(2)的约束条件:

通过以上定义可知:当系统显示l关键性级别行为时,所有关键性级别低于l的实时任务释放的作业直接被放弃执行不需要满足截止期的约束;混合关键性系统的正确性原则仅要求设计者保证系统中所有关键性大于等于当前系统运行时关键性级别l的作业执行时间不超过其截止期,并不需要保证任务ti释放的作业在系统经历更高关键性行为时满足截止期的约束.

1.1.4 需求上界函数DBF

需求上界函数(demand-bound function,简称DBF)[7]描述任意指定长度时间间隔内,系统产生的最大执行时间需求上界,即系统所需提供的能够保证实时性约束的最小处理器资源数量.

定义2(需求上界函数——DBF). 一个需求上界函数dbf(ti,Δ)表示一个实时任务ti在给定长度为D的时间间隔内,可能产生的最大执行时间需求的上界.其中,执行时间的需求为所有由实时任务ti释放,且调度窗口完全包含在长度为Δ的时间间隔内的作业所需要的最大执行时间(即WCET)之和.

DBF是传统实时任务模型下分析实时系统工作量可调度性(schedulability)的有效方法,并且针对诸多主流的实时任务模型,都有精确的计算方法.例如,在偶发实时任务模型中,DBF可以通过文献[7]中的算法求得. Ekberg等人在文献[6]中将其应用扩展到单处理器混合关键性偶发实时任务系统模型中,并给出了基于EY- VD[6]算法的混合关键性实时任务分别在低关键性和高关键性下的DBF计算方法.下面我们将对该方法进行简要介绍.

当混合关键性系统运行在低关键性级别时,每个混合关键性任务ti可视为普通的单关键性实时任务(Ci(LO),Di(LO),T).其中,Di(LO)是实时任务ti在低关键性级别下的相对截止期,当ti为低关键性实时任务时, Di(LO)=Di;当ti为高关键性实时任务时,Di(LO)≤Di(HI)=Di.可以得到:

当系统运行时切换到高关键性级别时,这里面可能包含一个遗留作业.而从高关键性任务ti释放的遗留作业的调度窗口最小可能为Di(HI)-Di(LO).据此,可以得到高关键性任务DBF的最大值:

函数full(ti,t)的计算过程中没有考虑遗留作业在系统的关键性变化前已经执行的时间.公式(5)用于计算该时间,其中,n=t mod Ti.

根据公式(4)和公式(5),可以得到高关键性实时任务ti在高关键性模式下的需求上界函数为

dbfLOdbfHI的计算复杂性均是伪多项式的.

1.2 相关工作

在混合关键性调度问题的研究中,很多文献对由有限个混合关键性作业组成之集合的调度问题进行了研究[8, 9].Baruah等人在文献[10]中已证明:用最优的算法判断一个给定的作业集合是否可以被调度,是强NP难问题.因此,对于混合关键性任务实时调度的研究重点集中在找到在实践中有很好性能的次最优调度算法.

Baruah等人在文献[5]中提出一种基于适用于混合关键性系统的改进型EDF算法EDF-VD.该算法提出了一个虚拟截止期(virtual deadline)的概念,每个高关键性任务有两个虚拟相对截止期(均不大于真实的相对截止期),其中一个被视为系统处于低关键性模式时高关键性任务的相对截止期,另一个是系统处于高关键性模式时高关键性任务的相对截止期.当实时任务系统的资源利用率满足一定条件时,可以利用此EDF算法调度.Ekberg等人在文献[6]中提出了用于计算采用虚拟相对截止期的实时任务在不同关键性模式下DBF的方法,并基于该方法提出了一种有效的为混合关键性实时任务系统的高关键性任务计算虚拟相对截止期的贪心算法EY-VD.本文提出的算法在每个处理器上的调度行为与EY-VD算法类似,高关键性任务释放的作业在不同的关键性模式下使用不同的相对截止期.另外,本文在进行算法分析时也使用了文献[6]中的一些结论.

针对多处理器平台中混合关键性实时系统的调度问题,Mollison等人在文献[11]中将不同关键性级别的任务封装在一起,然后在多核系统中用关键性单调优先级分配策略调度这些分组.在文献[12]中,Pathan将多处理器系统中传统的全局调度算法扩展到混合关键性系统中.在文献[4, 13]中,Baruah和Li等人研究了EDF-VD算法在多处理器系统中的扩展,并提出了全局调度算法Global-fpEDF和划分调度算法MC-Partition.在文献[3]中,Kelly等人研究了固定优先级调度算法在多处理器混合关键性系统中的划分调度问题.

另外,De Niz等人在文献[14]中提出了用于调度偶发性混合关键性任务的零松弛时间算法.这种算法的关键点在于,通过动态地调整作业优先级来避免低关键性作业对高关键性作业造成的运行时调度干扰.这种方法已经被扩展到用于不可抢占共享资源平台[15]和分布式平台.在这些平台上,混合关键性任务需要被分配到不同的执行单元[16].在文献[17]中,Li等人将OCBP(own criticality based priority)算法[8]扩展到偶发实时任务模型,提出了伪多项式复杂度的在线算法.

2 基于传统划分策略的混合关键性划分实时调度算法

在众多的单处理器混合关键性实时调度算法中,EY-VD算法[6]拥有比RMS(rate-monotonic scheduling)[19], OPA(optimal priority assignment)[20],EDF-VD[5]等其他已知的混合关键性调度算法更高的资源利用率.现有多处理器平台下的混合关键性实时调度算法的研究还十分有限.本文研究EY-VD算法在混合关键性多处理器平台上的扩展,并提出了一种基于划分调度的算法.

2.1 多处理器划分调度的基本方法

传统的隐式截止期(实时任务的相对截止期严格等于周期)周期性实时任务集在可抢占多处理器平台中的划分调度问题是强NP难的(经典的强NP-难问题Bin-Packing[21]可以转换成该问题),而该问题的计算复杂性很容易扩展到更加一般化的混合关键性偶发实时任务模型,因此,多处理器平台中混合关键性偶发实时任务系统的划分调度问题也是强NP难的.

在传统(非混合关键性)实时任务模型下,关于可抢占多处理器平台中的划分调度问题已经存在广泛的研究成果,而这些成果所采用的启发式划分策略大多可以分解为如下3个典型的步骤:

(1) 实时任务排序.通常,在将实时任务分配到特定处理器之前都会遵从某种策略将待分配的实时任务集排序,再依次进行分配处理器的操作.

(2) 处理器选择.按照第1步的排序结果,依次为实时任务集中的任务使用某种启发式策略分配处理器.

(3) 划分检验.检验分配到某处理器中的实时任务子集能否被某种单处理上的实时调度算法所调度.

对于划分检验,通常是采用单处理器下实时调度算法的可调度性测试方法对分配到该处理器上的实时任务子集进行可调度性分析.在此步骤中,不需要考虑多处理器的资源分配问题,而且存在大量单处理器上十分成熟的调度算法及其可调度性测试方法可以选择,因此,传统的多处理器实时任务划分调度问题的研究很多都集中在实时任务的排序及划分处理器的选择策略上.

处理器的选择策略和Bin-Packing问题的启发式策略十分类似,主要包括:

首次适应(first fit,简称FF).每次为实时任务选处理器时,按照固定的处理器顺序选择第1个满足划分检测条件的处理器,并将该实时任务分配到此处理器中.

最好适应(best fit,简称BF).每次将实时任务分配到满足划分检测条件,且剩余资源最少的处理器中.

最坏适应(worst fit,简称WF).与BF相反,WF每次选择满足划分检测条件,但剩余资源最多的处理器.

为了使启发式分配策略达到更好的可划分性能,在实时任务选择处理器划分之前,采用合适的策略对实时任务集进行预排序是必要的.

特别地,文献[3, 4]中提出的各种混合关键性实时任务系统的划分调度算法也基本上遵从上述的原则.

2.2 MC-PEDF算法描述

本节介绍本文提出的可抢占多处理器平台中,基于可调虚拟截止期EY-VD算法且采用传统划分策略的混合关键性偶发实时任务系统划分调度算法MC-PEDF.

假设一个混合关键性偶发实时任务实时系统包含一个混合关键性实时任务集合p(由n个相互独立的偶发性实时任务t1,t2,…,tn组成)和一个多处理器系统P(包含m个单位速率的同质处理器p1,p2,...,pm).MC-PEDF是Bin-Packing问题中FF-Decreasing启发式策略的一个变种(经过仿真实验的分析我们发现:在采用EY-VD作为划分处理器调度算法时,FF启发式策略要优于BF以及WF等启发式策略.但对比这些启发式策略不是本文的重点,故在此不做详细的分析),该算法的伪代码描述如图 1所示.

在算法的第1行,将混合关键性实时任务集p按照关键性降序排序,而对于相同关键性的任务按平均利用率降序排列.算法的第3行~第10行将按照第1行的排序结果依次为每个实时任务分配处理器;在分配处理器时, MC-PEDF会按第5行~第9行的方法,找到满足划分检测条件并且指标值最小的处理器,并将当前任务分配给它(第7行).

如果在某一次的迭代中,所有的处理器都不能满足分配当前任务的划分检测条件,则算法会在第3行因t等于None而退出循环,并在第12行返回“FAILURE”.

如果对于所有的实时任务都能被正确的分配处理器,则算法会在第3行因待分配实时任务集合p为空集而退出循环,最后在第13行返回“SUCCESS”.

Fig. 1Pseudo code of MC-PEDF algorithm 图 1MC-PEDF算法的伪代码

MC-PEDF第6行的CheckSchedulablityWithDBF函数基于Ekberg等人提出的基于虚拟截止期的DBF-LO和DBF-HI方法(如公式(3)、公式(6)所示)来检测划分实时任务子集的可调度性.该方法也是目前在混合关键性实时任务集可调度比率评价标准下,可抢占单处理器平台中混合关键性偶发实时任务调度性能最好的算法.

MC-PEDF的运行时调度算法如下:

如果MC-PEDF算法返回SUCCESS,则系统遵守如下的原则约束进行运行时调度:

(1) 系统启动时,将所有实时任务按MC-PEDF的划分结果分配到各处理器中,且系统进入低关键性模式.

(2) 对于每个处理器,均保证在任意时刻占用处理器执行的作业之优先级不低于其就绪队列中任何其他作业的优先级(优先级的取值越小,所表示的优先级越高).即,任何时刻处理器只允许分配到其中的任务所释放的优先级最高的未完成作业占用处理器执行,当更高优先级作业到来时,会抢占当前执行的作业.

(3) 当系统运行在低关键性模式时,所有低关键性任务和高关键性任务释放的作业均采用其释放时间与低关键性下的虚拟相对截止期(注意,本文约定低关键性任务的虚拟相对截止期等于其低关键性下相对截止期)之和作为其运行时优先级,并被插入其所分配处理器的就绪队列等待调度执行.

(4) 当系统因正在执行作业的执行时间超过低关键性下的最差执行时间而未发出执行完成信号时,系统将进行模式切换,并进入高关键性模式.在模式切换时,所有低关键性任务释放的作业将被终止执行并被清除出就绪队列,而高关键性任务释放作业的优先级将被调整为该作业的释放时间与高关键性下相对截止期之和,然后,系统按照第2条约束的原则继续运行时调度.

(5) 当系统运行在高关键性模式时,所有低关键性任务释放的作业将不被添加到就绪队列而是直接终止执行;而高关键性任务释放的作业将采用其释放时间与高关键性下的相对截止期之和作为其运行时优先级,并被插入其所分配处理器的就绪队列等待调度执行.

2.3 MC-PEDF划分算法的时间复杂性和正确性分析

对于算法的时间复杂度,易知:第1行的排序算法复杂度不会超过O(n2),其中,n为实时任务集中的任务数量.另外在第6行,分配到处理器pi上的实时任务子集(其包含任务的数量小于等于n)的可调度性判定和第12行对各个划分处理器内已分配的实时任务子集中的高关键性任务设置低关键性下的虚拟相对截止期的操作均为伪多项式时间复杂度(文献[6]中的结论).由于第12行for each循环的次数为划分处理器的个数m,故第12行的时间复杂度亦为伪多项式级别.现在我们分析第3行~第10行的嵌套循环,其中,外层循环次数不超过实时任务集的任务数量n,内层for each循环次数不超过处理器的数量m.结合对第6行操作的分析,该嵌套循环的时间复杂度为伪多项式级别.综上所述,MC-PEDF算法的时间复杂度为伪多项式级别.

下面我们讨论MC-PEDF算法的正确性.

定理1. 假设任意的混合关键性偶发实时任务集p{t1,t2,…,tn}和单位速率同质多处理器系统P{p1,p2,…, pm}.如果MC-PEDF算法返回SUCCESS,且该混合关键性系统采用MC-PEDF的运行时调度算法,则该混合关键性系统在低关键性和高关键性模式下都是可调度的.

证明:我们采用反证法证明该定理.如果MC-PEDF算法返回SUCCESS,则所有实时任务一定都分配到了某个特定处理器中.我们假设存在pP在算法返回SUCCESS时,该混合关键性系统不可调度.不失一般性地,一定存在处理器pk,满足分配在pk中的非空实时任务子集在运行时不可调度.

令在MC-PEDF算法划分过程中最后一个分配到pk中的任务为te,则一定有CheckSchedulablityWithDBF返回真,即,分配到pk中的实时任务子集在低关键性和高关键性下都是运行时可调度的.这与假设相矛盾,也证明了该定理的正确性. □

3 针对混合关键性系统的多次划分实时调度策略

上一节,我们基于传统的划分调度原则提出了MC-PEDF算法.本节将分析多处理器平台中混合关键性实时任务运行时的一些特性,并以此来改进传统的划分策略,提出一种针对混合关键性系统更有效的多处理器划分策略OCOP.最后,提出一种基于OCOP的改进型MC-PEDF算法MC-MP-EDF.

3.1 传统划分策略的局限性

在传统的多处理器偶发实时任务模型中,因为只有一种运行时模式,所有任务的主要调度参数(最差执行时间、截止期等)都是恒定的,因此,传统的划分算法可以通过优化的排序和分配策略来平衡各个处理器上分配的负载,以达到较高的资源利用效率.

与传统的多处理器实时调度模型不同,混合关键性系统在运行时会因为运行时系统关键性级别的不同而处于不同的关键性模式.而在不同的模式下,系统中需要调度的实时任务规模和特征参数都有差异.例如,当系统运行在低关键性模式时,所有低关键性任务和高关键性任务释放的作业都存在于就绪队列中,并按照各自的优先级等待调度;而当系统切换到高关键性级别时,系统需要保障高关键性任务释放的作业在更悲观的调度参数(高关键性下更长的评估最差执行时间等)下依然满足截止期约束,故,强行终止所有低关键性任务释放的作业并将其从就绪队列中移除.这种差异性导致某些处理器在不同运行时模式时的资源利用率相差较大.

正因多处理器混合关键性实时任务系统中实时任务调度参数的可变性,使得传统的划分策略很难平衡各个关键性模式中的资源利用率.这使得在划分实时任务时,待划分处理器尽管已分配的实时任务子集在大多数模式下的资源利用率很低,却因为在个别模式下的利用率过高而不能接受新的任务,从而导致资源利用率降低,甚至是实时任务集的不可调度,最终降低了总体的系统资源利用效率.

例1:考虑将表 1所示的实时任务集分配到2个单位速率处理器P1P2的情况.容易验证,无论采用DU还是DC的预排序策略,排序结果都和表中的指标顺序一致;而且容易验证,按照FFD的启发式划分策略,实时任务t1t2将被分配到处理器p1,而实时任务t3,t4t5将被分配到处理器p2,且p1,p2都满足可调度性判定条件.当分配实时任务t6时,处理器P1上的低关键性模式的资源利用率为80%,高关键性模式下的资源利用率为100%.如果将t6分配到p1,虽然低关键性下的资源利用率增至92.5%仍小于100%,但是在高关键性模式下不能通过CheckSchedulablityWithDBF的可调度性检验,故t6不能被分配到p1.而p2上低关键性模式下的资源利用率已经为100%,故t6也不能被分配到处理器p2上.因此,我们得出表 1所示的混合关键性实时任务集在2个单位速率处理器上不可被MC-PEDF划分的结论.但是由于p2上没有被分配任何高关键性任务,因此在系统进入高关键性模式时,该处理器上的资源利用率为0.这就造成了p2在不同关键性模式下处理器资源利用率的极度不平衡,同时造成高关键性模式下处理器p1p2之间的资源利用率相差极大.

Table 1 An example of dual-criticality task set 表 1 双关键性任务集实例

综上所述,传统的划分策略难以平衡混合关键性系统在各个关键性模式下的资源利用率,从而限制了划分调度算法在混合关键性系统中性能的提升空间.因此,如何充分利用高关键性模式下某些处理器中的空闲资源来满足高关键性实时任务的可调度性,并保障更多的低关键性实时任务在低关键性模式下可调度,从而平衡划分处理器在各个关键性模式下的资源利用率,成为本文改进混合关键性实时任务划分策略的主要目标.

3.2 混合关键性模型中的新型划分策略OCOP

观察1:通过对例1的进一步分析我们发现:如果将t6分配到p1,则容易验证p1在低关键性下是可调度的;而当系统切换到高关键性模式时,由于p2上没有被分配高关键性的实时任务,因此p2会一直处于空闲状态,造成资源的极大浪费;而如果在系统关键性模式切换时将p1中的一个高关键性任务迁移到p2中继续执行,则很容易验证高关键实时任务t1t2在各自独立的处理器中都可以在高关键性模式下满足截止期约束.由此可见,如果允许系统在关键性模式切换时将高关键性任务重新划分,将有助于提高多处理器平台的资源利用率.

基于前文对传统划分策略的分析和观察1的启发,我们针对混合关键性实时任务模型提出了新的多处理器划分策略OCOP.其核心思想是:允许混合关键性实时任务在不同的系统关键性模式下被划分到不同的处理上执行,而系统运行在特定关键性级别时,仍要求每个实时任务释放的作业必须在同一处理器中执行.由于放松了传统划分策略下实时任务释放的作业不能在处理器间迁移的约束,混合关键性系统在模式切换时可以通过更加灵活的模式切换策略来保证更高关键性模式下的可调度性.

对于任意混合关键性实时任务集合p,系统在不同运行时关键性模式下需要保证截止期约束的实时任务是不同的.在低关键性模式下,系统必须保证所有低关键性和高关键性实时任务(即p中的所有任务)的可调度性.我们将所有这些实时任务构成的集合称为低关键性模式调度任务集.类似地,系统在高关键性模式下只需要保证所有高关键性实时任务的可调度性,我们将这些高关键性实时任务构成的集合称为高关键性模式调度任 务集.

本文将混合关键性系统的运行时调度分为两种时期:1) 普通时期,即,系统持续运行于某个特定关键性模式的一段时间间隔;2) 模式切换时期,即,从系统监测到当前关键性模式下的过度执行开始,到完成模式切换进入到下一个关键性模式的调度为止的一段连续时间间隔.

OCOP划分策略对混合关键性多处理器系统的运行时调度存在如下的约束条件:

(1) 规定系统刚启动时处于模式切换时期,完成在低关键性模式下运行的准备工作.

(2) 系统在模式切换时期,允许对实时任务作业进行处理器间迁移操作,将下一个关键性模式调度任务集中的实时任务迁移至下一个关键性模式下的目标处理器中,并终止全部非下一个关键性模式调度任务集中的实时任务作业的执行.

(3) 系统在普通时期不允许任何实时任务作业的处理器间迁移操作,当前关键性模式调度任务集中的实时任务只能将其作业释放到该模式下分配的目标处理器中调度执行.

我们基于双关键性多处理器系统模型对OCOP划分策略的主要思想给出如下具体的非形式化描述,而OCOP也很容易扩展至多关键性多处理器系统模型中:

(1) 低(高)关键性模式调度任务集排序.排序的目的与算法与传统划分策略中的排序类似,区别在于OCOP需要针对不同关键性模式调度任务集使用不同的算法进行排序,以优化不同关键性模式下划分的性能.

(2) 低(高)关键性模式调度任务集的划分.OCOP使用与传统划分类似的启发式策略对不同关键性模式的调度任务集分别进行划分,不同模式中调度任务集的划分算法可以不同.特别地,由于在高关键模式中存在低关键性模式中没有执行完的高关键性遗留作业,因此,对高关键性模式调度任务集的划分策略比低关键性模式调度任务集的划分策略难度更高.

(3) 低(高)关键性模式的划分检验.OCOP同样需要对不同模式中的划分任务进行不同关键性级别的可调度性检验.特别地,由于高关键性遗留作业的影响,高关键性模式划分检验也颇具挑战性.

(4) 划分失败的调整策略.对于传统的划分策略,划分失败直接导致算法结束.OCOP在某个关键性模式下划分失败时会尝试对实时任务集的一些调度参数进行调整,并重新对各个关键性模式调度任务集进行划分,直至所有关键性模式调度任务集都被正确划分(划分成功),或调度参数的调整空间耗尽(划分失败).

在OCOP划分策略下,低关键性模式调度任务集与高关键性模式调度任务集的划分是在两个独立的阶段进行的,这就降低了混合关键性任务在不同运行时关键性模式下调度参数的改变对划分检验造成的干扰,并且能够平衡各个划分处理在不同关键性模式下的资源率,从而提高整个系统的资源利用率和划分性能.在每个关键性模式下,划分失败时的实时任务调度参数调整策略又降低了初始调度参数选择不当对划分性能的影响.

3.3 MC-MP-EDF算法描述

本节我们基于前文提出的OCOP策略,提出新的多处理器平台混合关键性系统划分调度算法MC-MP-EDF.该算法在双关键性模型中的算法描述如图 2所示,算法中CheckSchedulable子函数的伪代码描述如图 3所示.

Fig. 2 Pseudo code of MC-MP-EDF algorithm图 2MC-MP-EDF算法的伪代码

Fig. 3Pseudo code of CheckSchedulable algorithm图 3CheckSchedulable算法的伪代码

运行时调度算法:

如果MC-MP-EDF算法返回SUCCESS,则系统遵从如下的约束进行运行时调度:

(1) 系统启动时,将所有实时任务按照MC-MP-EDF的低关键性划分结果PLO分配到各处理器中,且系统进入低关键性模式.

(2) 每个处理器均保证:任意时刻,占用处理器执行的作业的优先级不低于其就绪队列中任何作业的优先级.

(3) 当系统运行在低关键性模式时,所有低关键性任务和高关键性任务释放的作业均采用其释放时间与低关键性下的虚拟相对截止期之和作为其运行时优先级,并被插入其低关键性下所分配处理器的就绪队列中等待调度执行.

(4) 当系统发生低关键性模式向高关键性模式切换时,所有低关键性任务释放的作业将被终止执行并被清除出就绪队列,高关键性任务释放作业的优先级将被调整为该作业的释放时间与高关键性下相对截止期之和,并将该作业插入其高关键性下所分配的处理器的就绪队列,同时,从原有就绪队列中移除该作业(对于在两种关键性下分配相同处理器的作业不进行此操作).当所有高关键性任务释放的未完成作业都完成就绪队列迁移之后,系统继续按照第2条约束的原则进行调度.

当系统运行在高关键性模式时,所有低关键性任务释放的作业将不被添加到就绪队列而是直接终止执行;而高关键性任务释放的作业将采用其释放时间与高关键性下的相对截止期之和作为其运行时优先级,并被插入其在高关键性下所分配处理器的就绪队列等待调度执行.

3.4 算法正确性分析

引理1. 假设任意的混合关键性偶发实时任务集p{t1,t2,…,tn}和单位速率同质多处理器系统P{p1,p2,…, pm}.如果MC-MP-EDF算法返回SUCCESS,且该任务集采用MC-MP-EDF的运行时调度算法,则任意被分配到特定处理器的实时任务释放的作业在低关键性模式下都是可调度的.

证明:由MC-MP-EDF的划分算法流程可知,该算法只在第11行才会返回SUCCESS.而在每次外层for each循环的迭代过程中,只有在第5行的判定条件为假时才可能执行到第11行,即,算法返回SUCCESS的前提条件是:在所有实时任务使用当前的低关键性虚拟截止期取值时,可以通过第5行的低关键性DBF判定条件.而第5行的判定条件保证所有高关键性和低关键性的实时任务释放的作业,都可以在虚拟截止期之前执行完低关键性下评估的最差执行时间.

又因为对于所有的低关键性实时任务,其虚拟截止期等于低关键性下的截止期,而所有高关键性任务的虚拟截止期又小于等于其低关键性截止期,因此,对于实时任务集里的所有实时任务所释放的作业,在低关键性模式下都可以保证在其真实截止期之前执行完毕.引理证毕. □

引理2. 假设任意的混合关键性偶发实时任务集p{t1,t2,…,tn}和单位速率同质多处理器系统P{p1,p2,…, pm}.如果MC-MP-EDF算法返回SUCCESS,且该任务集采用采用MC-MP-EDF的运行时调度算法,则任意高关键性实时任务释放的作业在高关键性模式下是可调度的.

证明:与引理1的证明类似,当算法返回SUCCESS时,第11行的判定条件可以保证在所有实时任务使用当前的低关键性虚拟截止期取值时,系统中所有的高关键性实时任务都可被划分到某个处理器中,并且划分到同一处理器中的高关键实时任务满足DBF-HI的判定条件.虽然在系统切换到高关键性模式时,高关键性的实时任务会进行处理器间迁移,但第5行的判定条件保障了所有的高关键性实时任务释放的作业在其虚拟截止期之前可以执行完低关键性下的最差执行时间,因此,迁移操作不会影响DBF-HI判定的准确性.而DBF-HI判定条件也可以保证每个划分处理器上分配的高关键性实时任务所释放的作业都能满足各自高关键性下的截止期约束.引理证毕. □

定理2. 在m个单位速率同质处理器系统中,任何可以被MC-MP-EDF算法正确划分的混合关键性偶发实时任务集,在MC-MP-EDF的运行时调度算法下均满足在低关键性模式和高关键性模式下都是可调度的.

证明:由算法描述易知,仅当所有的实时任务都能在低关键性下分配到特定的处理中,同时所有的高关键性任务在高关键性下也都能被分配成功的情况下,算法才可能返回SUCCESS.再综合引理1和引理2的结论,可以证明定理2的正确性. □

3.5 算法复杂性分析

通过MC-MP-EDF的算法描述易知,外层for each循环进行下一次迭代的必要条件是在第12行集合HS不为空.又因为每次迭代都会使得HS中某个高关键性的实时任务tiDi(LO)减1或者直接退出循环算法终止,而高关键性任务tiDi(LO)减至Ci(LO)时,该任务将从HS中移除,因此,外层for each循环的最大迭代次数为

通过与算法MC-PEDF类似的复杂性分析易知,第5行和第11行操作具有伪多项式的时间复杂性.综上分析,MC-MP-EDF的总体时间复杂性是伪多项式的.

4 实验仿真与结果分析

本节将通过仿真实验来比较本文提出的两种多处理器平台中混合关键性实时任务系统的划分调度算法,以及现有划分调度算法的可调度性能.实验针对双关键性隐式截止期偶发实时任务模型和单位速率的同质多处理器平台.本文的实验实现了Kelly等人在文献[2]中提出的两个资源利用率比较高的算法DC-RM和DC- Audsley,并以此为参照,比较本文提出MC-PEDF在随机任务集可调度比率评价标准中的性能;并通过观察采用OCOP划分策略的算法MC-MP-EDF的性能改进效果来评价OCOP的有效性.

4.1 随机任务集生成算法

我们采用与文献[6]中类似的生成混合关键性随机任务集的方法,并将其扩展到多处理器平台中.一个随机实时任务集初始时被设置为空集p=Æ,然后逐次添加新的随机混合关键性实时任务.随机任务的生成主要受5个参数的控制:随机任务为高关键性任务的最大概率PHI、高关键性任务的高关键性下的最差执行时间与低关键性下最差执行时间的最大比例RHI、所有任务在低关键性下最差执行时间的最大值、最大的实时任务周期Tmax和单位速率处理器的个数m.每个新的随机实时任务按照如下步骤生成:

1. zi服从PHI的概率取值HI,否则取值LO.

2. Ci(LO)的取值在{1,2,...,}范围内服从均匀分布.

3. 如果该随机任务为低关键性任务,则Ci(HI)=Ci(LO);否则,Ci(HI)的取值在{Ci(LO),Ci(LO)+1,…, RHI×Ci(LO)}范围内均匀分布.

4. Ti的取值在{Ci(zi),Ci(zi)+1,…,Tmax}范围内服从均匀分布.

5. 由于我们采用隐式截止期的模型,所以有Di=Ti.

我们定义一个双关键性实时任务集p的平均利用率为

每个任务集在生成时都有一个平均资源利用率基准U.由于产生拥有准确资源利用率的随机任务集比较困难,所以我们允许任务集的平均利用率有一个可接受的误差范围:若满足就继续产生更多的任务,并将它们添加到任务集p;如果将一个任务加入p后导致,则随机任务集生成算法将整个任务集抛弃,并从一个空的任务集重新开始生成;如果将一个随机任务加入p后,满足则一个随机任务集生成完毕,除非任务集中的所有任务都有相同的关键性或者ULO(p)>0.99xmUHI(p)>0.99xm.在这种情况下,此任务集也将被抛弃.在每次实验中,生成随机任务集的各个参数设置分别为:

4.2 实验结果分析

图 4图 5分别比较了4个处理器(m=4)和8个处理(m=8)平台下,已有划分调度算法DC-RM[3],DC- Audsley[3],MC-Partition[4]与本文提出的MC-PEDF,MC-MP-EDF的随机任务集可调度比率.图中各点数据均基于至少1 000个随机任务集样本(图 4中各点随机任务集平均任务数量为16~31,图 5中为31~63).其中,x轴是随机任务集的规范化平均资源利用率,y轴表示可被调度任务集数量与总样本数量的百分比.例如,图 4中的曲线MC-MP-EDF上的点(0.80625,85)表示在多于1 000组规范化平均资源利用率在(0.80125,0.81125)范围内的随机任务集样本中,可被MC-MP-EDF算法调度的样本数量占总体样本数量的百分比为85%.

Fig. 4 Acceptance comparison on 4-processor platform图 4 4个处理器系统中的接受率比较

Fig. 5Acceptance comparison on 8-processor platform图 5 8个处理器系统中的接受率比较

实验结果表明:本文提出的基于传统划分策略和EY-VD算法的混合关键性多处理划分调度算法MC-PEDF的接受率性能要明显优于之前的算法;而使用针对混合关键性系统的OCOP划分策略的改进性划分调度算法MC-MP-EDF的性能也明显优于MC-PEDF算法.从图 4图 5的对比中我们可以发现:当混合关键性系统中处理器的数量从4增至8时,MC-MP-EDF相对于其他调度算法的优势更为突出,这也证明了OCOP划分策略对多处理器平台中混合关键性系统的有效性和实用性.

5 结束语

本文在基于传统多处理器划分调度策略实时调度算法的基础上,结合单处理器混合关键性系统中的EY- VD算法,提出了多处理器混合关键性系统中基于该算法的划分调度算法MC-PEDF,并进一步研究了混合关键性系统中划分调度的特殊性质,并在分析传统划分策略局限性的基础上,提出了针对多处理器平台的混合关键性系统划分策略OCOP.与传统的多处理器划分策略相比,OCOP能够有效利用混合关键性实时任务的运行时特征,更好地平衡不同处理器之间在各个运行时关键性模式中的资源利用率,以更为充分、有效地利用系统资源.仿真实验结果表明:MC-PEDF与先前的多处理器混合关键性实时调度算法相比,具有更高的可调度接受率;基于OCOP划分策略的新算法MC-MP-EDF又显著提升了MC-PEDF的性能;并且系统中处理器的数量越多,优化效果越明显.我们有理由相信,OCOP将会成为多处理器混合关键性划分实时调度的重要分支.

参考文献
[1] Vestal S. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: Proc. of the 28th IEEE Real-Time Systems Symp. (RTSS). IEEE, 2007.239-243 .
[2] Bastoni A, Brandenburg BB, Anderson JH. An empirical comparison of global, partitioned, and clustered multiprocessor EDF Schedulers. In: Proc. of the 31st IEEE Real-Time Systems Symp. (RTSS). IEEE, 2010.14-24 .
[3] Kelly OR, Aydin H, Zhao B. On partitioned scheduling of fixed-priority mixed-criticality task sets. In: Proc. of the 10th Int’l Conf. on Trust, Security and Privacy in Computing and Communications (TrustCom). IEEE, 2011.1051-1059 .
[4] Baruah SK, Chattopadhyay B, Li H, Shin I. Mixed-Criticality scheduling on multiprocessors. Real-Time Systems, 2014,50(1): 142-177 .
[5] Baruah SK, Bonifaci V, D’Angelo G, Marchetti-Spaccamela A, Van Der Ster S, Stougie L. Mixed-Criticality scheduling of sporadic task systems. In: Proc. of the 19th Annual European Symp. on Algorithms (ESA). Springer-Verlag, 2011.555-566 .
[6] Ekberg P, Yi W. Outstanding paper award: Bounding and shaping the demand of mixed-criticality sporadic tasks. In: Proc. of the 24th Euromicro Conf. on Real-Time Systems (ECRTS). IEEE, 2012. 135-144 .
[7] Baruah SK, Mok AK, Rosier LE. Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proc. of the 11th Real-Time Systems Symp. (RTSS). IEEE, 1990.182-190 .
[8] Baruah SK, Li H, Stougie L. Towards the design of certifiable mixed-criticality systems. In: Proc. of the Real-Time and Embedded Technology and Applications Symp. (RTAS). IEEE, 2010.13-22 .
[9] Baruah SK, Burns A, Davis RI. Response-Time analysis for mixed criticality systems. In: Proc. of the 32rd Real-Time Systems Symp. (RTSS). IEEE, 2011.34-43 .
[10] Baruah SK, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, Megow N, Stougie L. Scheduling real-time mixed-criticality jobs. IEEE Trans. on Computers, 2012,61(8):1140-1152 .
[11] Mollison MS, Erickson JP, Anderson JH, Baruah SK, Scoredos JA. Mixed-Criticality real-time scheduling for multicore systems. In: Proc. of the 10th Int’l Conf. on Computer and Information Technology (CIT). IEEE, 2010.1864-1871 .
[12] Pathan RM. Schedulability analysis of mixed-criticality systems on multiprocessors. In: Proc. of the 24th Euromicro Conf. on Real- Time Systems (ECRTS). IEEE, 2012.309-320 .
[13] Li H, Baruah SK. Outstanding paper award: Global mixed-criticality scheduling on multiprocessors. In: Proc. of the 24th Euromicro Conf. on Real-Time Systems (ECRTS). IEEE, 2012. 166-175 .
[14] De Niz D, Lakshmanan K, Rajkumar R. On the scheduling of mixed-criticality real-time task sets. In: Proc. of the 30th Real-Time Systems Symp. (RTSS). IEEE, 2009.291-300 .
[15] Lakshmanan K, de Niz D, Rajkumar R, Moreno G. Resource allocation in distributed mixed-criticality cyber-physical systems. In: Proc. of the 30th Int’l Conf. on Distributed Computing Systems (ICDCS). IEEE, 2010. 169-178 .
[16] Lakshmanan K, de Niz D, Rajkumar R. Mixed-Criticality task synchronization in zero-slack scheduling. In: Proc. of the 17th Real- Time and Embedded Technology and Applications Symp. (RTAS). IEEE, 2011.47-56 .
[17] Li H, Baruah SK. An algorithm for scheduling certifiable mixed-criticality sporadic task systems. In: Proc. of the 31th Real-Time Systems Symp. (RTSS). IEEE, 2010. 183-192 .
[18] Guan N, Ekberg P, Stigge M, Yi W. Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems. In: Proc. of the 32rd Real-Time Systems Symp. (RTSS). IEEE, 2011. 13-23 .
[19] Liu CL, Layland JW. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of ACM, 1973,20(1): 46-61 .
[20] Audsley NC. Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical Report, YCS 164, Department of Computer Science, University of York, 1991.
[21] Johnson DS. Near-Optimal bin packing algorithms [Ph.D. Thesis]. Boston: Massachusetts Institute of Technology, 1973.