机载多分区系统可调度性分析算法研究

张旻, 武君胜, 崔西宁, 孙景昌

1.西北工业大学软件学院， 陕西 西安 710072；2.中国航空工业集团有限公司西安航空计算技术研究所， 陕西 西安 710065

实时系统主要分为2类:①软实时系统;②硬实时系统。软实时系统是指少数事件/进程的截止期允许被违反,尤其是当系统负载较高时,允许发生少数事件处理错过截止期。硬实时系统则不允许任何进程的周期和截止期被违反,系统必须及时地对事件做出响应,不允许发生错过事件处理时机或超出截止期的情况。例如,飞机飞行控制、导弹/火箭发射、飞船太空飞行等系统,如果没有对突发故障做出及时处理,将造成巨大的损失或灾难。

硬实时系统不仅在传统的航空、航天领域,而且在民用飞机、智能汽车等领域也逐步得到广泛应用[1]。例如在机载嵌入式安全关键系统中,其可用性和可靠性不仅仅取决于软件功能的正确性,在某些应用场景(如飞行控制)下更加依赖于软件运行的实时性。机载嵌入式硬实时系统一个重要特征就是必须在给定的时限和周期内,对规定事件进行及时响应和处理。

美国航空电子工程委员会制定的航空应用软件接口标准ARINC653(avionics application software standard interface)[2-4],定义了综合化航空电子系统(IMA)架构下分区实时操作系统的行为逻辑、调度机制和应用软件接口规范。分区是ARINC653规范的核心概念,它实现了应用程序的时空隔离。在机载软件领域应用程序是一组计算任务的集合,部署和运行在一组资源分区之上。这些计算任务在分区内进行本地调度,与其他分区内的任务调度相互独立;同时,若干个分区之间进行分区间调度以共享处理器的计算时间资源。针对ARINC653的任务调度方法,已有大量深入的研究[5-7]。

分区操作系统是面向机载综合化航空电子系统、满足ARINC653标准,且具备时空隔离能力的嵌入式实时操作系统[8]。为了防止个别分区出现故障影响到其他分区的运行,分配给一个分区的执行时间不会由于其他分区的超时运行而有所改变。另外,分区实时操作系统采用两级层次调度模型[9],分别对分区间和分区内进程进行调度。第一级是分区间调度,将分区作为调度的单位,各个分区按照固定的时间片分配计算资源;第二级是分区内进程调度,各个进程按照固定优先级进行抢占式调度。分区按固定时间序列,即用户配置的调度表进行调度。为避免在试飞阶段才发现分区或进程不可调度的情况,进而造成系统失效、事故以及经济损失,在系统开发和集成阶段事先针对调度表进行可调度性分析就显得至关重要。

很多学者针对可调度性分析进行了研究,采用的方法包括时间依赖结构模型[10]、时间约束着色Petri网[11]、多项式时间线性松弛[12]、基于主副版本混合关键任务优先级划分[13]、基于优先级控制的系统分解[14]、函数图像分析[15]、DAG(directed acyclic graph)模型[16-17]、PFP(artitioned fifixed-priority)调度策略[18]、基于挂起的协议LPP[19]等技术和方法对可调度性分析进行了研究和探索。上述研究工作针对实时系统、并发系统、任务关键系统、混合关键系统等对时间约束具备较高要求的任务系统从理论角度进行了可调度性分析,相关研究理论严谨,学术价值高。区别于上述研究,机载领域应用场景不仅具备实时特征,同时具备多分区时空隔离特征,并且采用多级调度机制,此类领域特征使得上述研究很难直接应用于指导机载分区系统在综合化条件下的可调度性分析。因此,有必要结合机载分区、实时、多级调度等特征,研究具备领域特点的可调度性分析算法。

为解决现有可调度性分析算法未考虑机载分区特征的问题,本文针对机载分区系统高安全、强实时、高可靠等特点,提出一种基于虚拟进程的多分区多进程的调度可行性判定算法。该算法根据给定调度表和分区进程时间约束条件,判定所有进程的可调度性。与现有判别技术不同,针对机载分区系统多级调度分析难的问题,本文提出了基于虚拟进程的可调度性方法,该方法在判断某一分区中进程的截止期是否能被满足时,将其他分区对应的时间窗口作为一个虚拟进程来看待,将复杂的多分区多进程的调度可行性判断问题,转化为一组单分区多进程的调度可行性判断问题,从而降低了多分区多进程可行性判断的难度及算法在工程实践中应用的难度。最后通过正反例调度实例验证了本文提出可调度性分析算法的正确性。

1 多分区系统调度模型

为简洁、准确地表述算法设计过程,本节针对问题模型进行一些参数符号的定义,并基于相关定义描述多分区系统的调度规则。

1.1 分区调度参数

假设操作系统配置K个分区,分区Pk(1≤k≤K)由nk个进程组成,进程优先级由高到低排列。

本文所使用的主要符号见表1。

表1 分区调度参数

周期进程必须满足Ck,i≤Dk,i≤Tk,i;非周期进程无周期参数;对某些进程,不存在截止期限制,此时截止期值为空。

1.2 分区调度规则

分区调度表的核心属性为时间窗口,关键参数包括时间窗口所对应的分区和持续时间。依据ARINC653标准,分区调度表应满足以下约束条件:

1) 调度表由一组时间窗口的集合组成,可在一个调度表中多次调用一个分区,但不必在一个调度表中调度所有分区;

2) 一个调度表里可以有多个时间窗口,可以有空闲时间窗口;

3) 同一时刻处理器仅能运行一个时间窗口;

4) 每个分区内的进程及进程的时间属性都是静态配置的,一个进程只能属于一个分区;

5) 主时间框架是调度表的循环周期;

6) 某一分区的分区循环时长等于该分区内所有周期进程的周期与主时间框架的最小公倍数。

本文以时间窗口作为主时间框架内调度主体,一个调度表即为一组时间窗口的排列。假设主时间框架内有M个时间窗口(M≥K),记Ti=(Zi,Si,Yi,Fi),i=1,2,…,M,其中:

1)Zi表示时间窗口的周期;

2)Si表示时间窗口的开始运行时间;

3)Yi表示时间窗口的运行时长;

4)Fi表示时间窗口对应的分区。

分区调度规则示例如图1所示。

处理器上运行P1,P2,P33个分区。主时间框架包含T1,T2,…,T12共12个时间窗口。时间窗口属性见表2。

表2 多分区调度表时间窗口属性

对于单核处理器,时间窗口是串行排列的,其中可能包括空闲的时间窗口。每个时间窗口处理且仅处理一个分区的调度。调度表按照就绪时间依次运行各个时间窗口。每个时间窗口内对应分区内的所有进程,按优先级依次串行运行。

1.3 进程调度规则

进程具有固定的优先级,高优先级的进程优先获得处理器资源。机载分区操作系统在管理分区内进程时,按照优先级维护一个就绪队列,每次从就绪队列中选择优先级最高的进程,将处理器分配给它。

在优先级调度算法中,进程分为可被抢占和不可被抢占2种类型。可抢占进程在运行过程中允许被更高优先级进程抢占处理器;不可抢占进程则反之,不允许被更高优先级进程抢占处理器。

按照ARINC653标准的定义,进程的优先级是静态配置的,即在创建进程前事先确定,在进程的整个运行期间优先级保持不变。

2 可调度性分析算法设计

在机载软件工程实践中,要求调度表中每个分区都必须可调度,每个进程的时间约束都必须被满足。因此,可调度性分析算法采取的总体策略是:先分别计算每个分区的可调度性,再得出调度表的整体可调度性分析结论。

首先,给出计算单个分区时将其他分区视为虚拟进程的算法1,然后再分别针对非周期进程和周期进程设计可调度性分析算法2和3,最后,基于算法1～3设计总体可调度性分析算法。

2.1 确定分区循环时长

调度表的可行性判定必须涵盖所有分区,而某一分区调度方案的可行性需判断在分区循环时长内,所有进程的可调度性。因此,确定分区循环时长是进行可调度性分析的前提。由前述1.2节分区调度规则及图1多分区的调度过程示意图可知,为满足多分区内多进程调度需求,某一分区的分区循环时长等于该分区内所有周期进程的周期与主时间框架的最小公倍数。如果无法满足这一要求,该分区的部分进程可能无法在一个分区循环时长内执行完毕。依据最小公倍数的结合律性质[20],记a和b的最小公倍数为[a,b],则[a,b,c]=[[a,b],c],因此分区的循环时长等于该分区内所有周期进程的周期与主时间框架的最小公倍数。

2.2 虚拟进程生成算法

对于分区操作系统,通常采用两级层次调度模型,分别对分区和分区内进程进行调度。第一级是对各个分区的调度,将分区作为调度的单位,各个分区按照固定的时间片分配计算资源;第二级是对各个分区内的进程进行调度,各个进程按照固定优先级进行抢占计算资源。多分区多进程调度可行性分析是一个NP-Hard问题,但从分区运行行为考虑,当某一分区占有处理器时,其余分区处于停止状态,因此可以从宏观角度将处于停止状态的分区中的多个进程视为一个虚拟进程,反之亦然。因此,本文基于虚拟进程,将多分区多进程的调度可行性分析转换为单分区多进程调度可行性问题。

以图1为例说明虚拟进程的生成算法。

基于图1的调度表和表2给出的调度表,将所有时间窗口视为虚拟进程,描述见表3。

表3 时间窗口对应的虚拟进程

判断各个分区内所有进程的可调度性。以第一个分区为例,假设分区P1包含3个进程,见表4。

表4 分区P1所有进程的属性

为判断分区P1所有进程的可调度性,将除P1外其他分区对应的时间窗口转化成虚拟进程,并为时间窗口对应的虚拟进程分配适当的优先级。由于时间窗口不可被打断,同样也不可被抢占,所以可将这些时间窗口所对应的虚拟进程的优先级设置成比P1内所有进程的优先级都要高,以保证虚拟进程不会被真实进程抢占,而虚拟进程可以抢占真实进程。考虑最极端的情况,即虚拟进程的WCET和截止期相等,以此保证虚拟进程可以在规定的时间结束。另一方面,假设虚拟进程的周期等于主时间框架的长度,保证虚拟进程在整个分区循环时长里可以正常运行。判断分区P1的可调度性时,所生成的除分区P1外所有时间窗口对应的虚拟进程见表5。

表5 除P1外所有时间窗口对应的虚拟进程

虚拟进程生成算法构建虚拟进程并将其加入到当前所需检验分区Pi的进程列表中,输出需要检验的分区Pi的最终进程列表。为了防止其他分区所对应的时间窗口影响运行分区内进程,需要将时间窗口作为进程考虑。将时间窗口Ti虚拟进程化,令其属性为:

1) 最恶劣情况下的执行时间:Ck,i=Yi;

2) 截止期:Dk,i=Yi;

3) 优先级:高于运行分区内所有进程;

4) 就绪时间:该虚拟进程还差多长时间可以就绪,在0时刻等于时间窗口的开始时间Sk;

5) 周期:等于主时间框架。

算法1虚拟进程生成算法

输入:调度表(包括所有时间窗口的属性);所有分区的进程列表(包括所有进程的属性)

具体执行步骤如下:

step1 初始化:j=1;

step2 对j=1,…,M,判断Tj是否对应于Pi

step3 若否,将虚拟进程Tj加入Pi的进程列表,Ck,i=Yi,Dk,i=Yi,优先级为运行的分区中所有进程的最高优先级+j,还差多长时间可以就绪为Sj,周期为主时间框架长度。若是,则跳过该时间窗口。输出最终需要检验的进程列表。

该算法基本运算在于判断Tj是否对应于Pi并进行相应赋值操作,因此其时间复杂度取决于参数j的值,为o(n)。

2.3 可调度性分析算法

对第k个分区进行判断,定义下述4个列表:

1) 剩余列表Sj:后续还需运行的进程列表;

2) 完成列表Wj:已经完成至少一次运行的进程列表;

4) 未就绪列表WJj:还未准备就绪的进程列表(包含未就绪的进程i以及进程i还差dji可以就绪,进程tk,i的优先级Pk,i等信息)。

特别说明:由于在后续的可调度性分析算法中,上述4个列表均需要不断更新,所以上述列表中的所有下角标j表示第j次更新。

算法运行过程中所涉及的判据及更新规则如下:

进程截止期满足的定义分为2种情况:

在判据2和判据3中,进程tk,m∈Jj描述了针对第j次更新的截止期可满足,列表更新后,进程tk,m有可能会被违反。因此,需要在每次列表更新后进行判断。

针对进程的相关属性以及上述相关列表的更新规则分3种情况进行讨论:

1)Jj为非空,Jj中优先级最高的进程tk,i能在不被更高优先级进程抢占情况下完成运行:

2)Jj为非空,Jj中优先级最高的进程tk,i不能在不被更高优先级进程抢占情况下完成运行:

如果某个分区内的进程都是非周期进程,所加入的虚拟时间窗口进程都为非周期性,则需运行这里的算法2。为此,定义以下3个列表:

1) 完成列表Wj:已经完成运行的进程列表;

2) 就绪列表Jj:已经准备就绪的进程列表(包括已准备就绪的进程tk,i,进程的优先级Pk,i进程最恶劣情况下执行时间Ck,i,以及进程的截止期Dk,i等信息);

3) 未就绪列表WJj:还未准备就绪的进程列表(包含未就绪的进程i以及进程i还差dji可以就绪,进程tk,i优先级Pk,i等信息)。

算法2非周期进程的可调度性分析算法

具体执行步骤如下:

step1 第k个分区的进程运行时间Tk=0,

j=0;

step2 若j≤nk

Pk,i>Pk,m,∀tk,m≠tk,i且tk,i,tk,m∈Jj,则令

Tk=Tk+Ck,i;

j=j+1;

step2.1 截止期判断

若∀tk,m∈Jj,Dk,m

输出由于进程tk,m的截止期未被满足(注:此处截止期未被满足的进程不唯一),该分区不可行,转step3;

否则:

Wj=完成列表Wj-1中加入进程tk,i;

Jj=就绪列表Jj-1中删除进程tk,i;

继续执行;

否则

输出:该分区可调度,转step3;

step3 终止

该算法基本运算在于比较j与nk,并进行赋值运算,其时间复杂度取决于参数j与参数k的值,为o(n2)。

对某个分区,如果分区内存在一个周期进程,或至少加入了一个周期的虚拟时间窗口,则需运行算法3。在给定分区调度表以及相应的分区循环时长的情况下,判断进程在运行的过程中,进程的截止期属性是否能够得到满足。为了方便后续算法的设计,首先定义4个列表:

1) 剩余列表Sj:后续还需运行的进程列表;

2) 完成列表Wj:已经完成至少一次运行的进程列表;

4) 未就绪列表WJj:还未准备就绪的进程列表(包含未就绪的进程i以及进程i还差dji可以就绪,进程tk,i优先级Pk,i等信息)。

算法3的循环次数应为最坏情况下进程的切换次数,而分区循环时长除以sysClkRateHz是其理论上的一个上界(sysClkRateHz由用户给出,通常为100或1 000),可使用这个上界作为算法3中运行步骤的上界Nk。

算法3周期进程的可调度性分析算法

具体执行步骤如下:

step1 第k个分区的进程运行时间Tk=0,运行步骤的上界Nk,j=1

step2 若j≤Nk

判断Jj中优先级最高的进程tk,i能否在不被更高优先级进程抢占情况下完成运行;

step2.1 若Jj中优先级最高的进程tk,i能在不被更高优先级进程抢占情况下完成运行:

step2.1.1 判断进程截止期是否满足

若满足:

执行step2.1.2;

否则

输出由于进程tk,m的截止期未被满足,分区不可行。转step3;

step2.1.2 更新进程的相关属性及列表;

step2.2 若Jj中优先级最高的进程tk,i不能在不被更高优先级进程抢占情况下完成运行:

step2.2.1 进程截止期Dk,i等是否满足:

若满足:

执行step2.2.2;

否则

输出由于进程tk,m的截止期未被满足,分区不可行。转step3;

step2.2.2 更新进程的相关属性以及相关列表;

step2.3.1 更新进程的相关属性以及相关列表;

step 2.4.1j=j+1;

否则

输出:该分区可调度,转step3;

step3 终止

该算法基本运算在于比较j与nk,并进行赋值运算,其时间复杂度取决于参数j与参数k的值,为o(n2)。

基于算法1～3,给出多分区调度表的总体可调度性分析算法。该算法的关键是对每个分区均进行一次进程可调度性分析。具体地,针对每个分区的情况,首先执行虚拟进程生成算法(算法1)将时间窗口转化为虚拟进程,进而分非周期进程和周期进程2种情况分别调用相应的单个分区调度表可行性检验算法(算法2或算法3)来判别这个分区内进程和其他时间窗口的相容性,也就是这个分区的可调度性。通过依次对所有分区均进行一遍检查,就形成了多分区调度表的总体可调度性检查算法。

算法4多分区调度表的总体可调度性分析算法

输入:分区的调度表(所有时间窗口的属性),所有分区的进程列表,分区个数K

具体执行步骤如下:

step1 对i=1:K

step1.1 调用算法1,生成虚拟进程列表;

step1.2 将虚拟进程列表和分区Pi的所有进程组合到一起,形成总进程列表;

step1.3 如果总进程列表均为非周期进程,则调用算法2判断分区Pi是否可调度。

step1.3.1 判断某个进程截止期等属性是否满足:

若满足:

若后续还有进程,则判断下一个进程, 否则转step1.5;

若不满足:

输出:不可调度及截止期不满足的进程,转step3;

step1.4 如果总进程列表包括周期进程,则调用算法3判断各个分区Pi是否可调度。

step 1.4.1 判断某个进程截止期等属性是否满足:

若满足:

若后续还有进程;则判断下一个进程, 否则转step1.5;

若不满足:

输出:不可调度及截止期不满足的进程,转step3;

step1.5i=i+1;

step2 若所有分区均可调度;

输出:调度表可调度,转step3;

step3 终止

该算法基本运算在于对算法1、算法2、算法3的调用,其时间复杂度取决于3个算法的时间复杂度以及K的值,为o(n3)。

针对给定调度表和所有分区内全部进程的属性,算法4需首先从数据文件载入全部进程的序号、WCET、截止期、周期、优先级,以及载入全部时间窗口的序号、对应分区、周期、开始时间、运行时间;然后调用算法1,对每个分区生成包括时间窗口虚拟进程在内的全部总进程列表;如果总进程列表内全部为非周期进程,算法2可判断这些进程是否可调度,如果算法输出可调度,则可保证在实际运行时,主时间框架内该分区的所有非周期进程和该分区外的所有时间窗口均可运行一次;如果总进程列表包括周期进程,算法3判断这些进程是否可调度,如果算法输出可调度,则在实际运行时,保证该分区的所有非周期进程和该分区外的所有时间窗口均可运行一次,且该分区的所有进程和该分区外的所有时间窗口的周期性和截止期等要求均可得到满足。

如算法4输出不可调度,则说明当前调度表不可调度。根据跳出循环的位置,可以判断是何原因导致调度不可行,如某个进程的截止期太短,或分区时间窗口过小等。用户可根据算法4的输出,相应地调整进程的截止期或分区的时间窗口属性,直至得到可行的调度表配置。

3 算法验证

本节通过2个具体的调度表,一个可行以及一个不可行的实例,从正反2个方面来检验所设计算法。由于本文中所采用调度表考虑了机载应用分区领域特征,无法与现有针对实时操作系统的调度算法进行直接对比,因此采用正反例方式对本文提出算法进行验证。

3.1 正例:可行的调度表分析结果

考虑表6中所述的进程属性和表7中所给的调度表属性,通过虚拟进程生成算法,周期进程的可调度性检查算法以及多分区调度表的总体可调度性检查算法进行可行性的判断。

表6 进程属性

表7 调度表属性

首先,由2.1节容易计算出各分区的分区循环时长:

1) 分区P1的分区循环时长:[[10,25],30]=[50,30]=150 ms。

2) 分区P2的分区循环时长:[[50,120], 30]=[600,30]=600 ms。

3) 分区P3的分区循环时长:[[30, 60],30]=[60,30]=60 ms。

然后,应用第2节的算法1～4,输入表6和表7中的信息,可输出“此调度表可行”。分区P1、P2、P3进程可调度判断如图2～4所示。为了方便展示,这里只展示了第一个主时间框架的示意图,而不是整个分区循环时长。

图4 分区P3的可调度性分析分析结果

在图2～4中,浅蓝色的竖线表示进程就绪时间,红色竖线表示进程的截止期时间。因此,进程必须在浅蓝色竖线和红色竖线所标定的时间区间内完成运行才可以满足截止期的要求。而在根据生成算法产生虚拟进程时,因为给其赋予了较高的优先级和特定的属性,所以虚拟进程在可调度判别过程中恒定满足截止期的要求,在每次可调度判断时,可以只关注相应分区包含的真实进程是否满足截止期的要求。从上述3张图形中可以看出:分区1～3的进程均可以在截止期内完成运行,因此不会造成截止期不被满足的情况。

3.2 反例:不可行的调度表分析结果

在表6中,将进程1的周期属性10改为9,可输出“此调度表不可行”。首先,根据2.1节可以计算出分区P1新的分区时长,其他2个分区的分区循环时长保持不变。分区P1新的分区循环时长为:[[9,25],30]=[225,30]=450 ms。

然后,调用算法4针对分区P1进行可调度性判断,如图5所示。

图5 分区P1的可调度性分析结果

从图5中可以看到:进程t1,1(A)的第二次就绪时间至截止期的时间区间刚好包含在虚拟进程T4的运行区间内。由于虚拟进程T4的优先级更高,进程t1,1(A)无法抢占计算资源进行运行,而只要等到虚拟进程T4完成运行之后才可以。但是,此时进程t1,1(A)的截止期将不满足。因此,分区P1内进程不可调度。

4 结 论

研究了机载多分区系统的调度规则,提出了一组调度分析算法,能够根据给定的调度参数和分区内进程时间属性,分析系统调度表的可调度性。经过正反2个方面的验证,该算法能够准确给出是否可调度的定性分析结论,为可调度性分析工具的设计实现提供了理论支撑。本文提出的算法适用于符合ARINC653标准的分区操作系统产品,与机载领域的工程需求吻合,具备较强的应用价值,已在某操作系统配套开发环境中得到工程应用。

随着多核处理器的广泛应用,可调度性分析将不再局限于单核处理器。在多核条件下,可调度性分析呈现出一些完全不同的特征,国内外已经有一些前瞻性的研究[21-25],本文的不足之处在于仅对单核处理器的场景进行了研究,后续还将继续针对多核处理器场景下的调度模型和调度算法开展相关研究。