多核环境下基于图模型的实时规则调度方法∗

王娟娟,乔 颖,熊金泉,王宏安

1(中国科学院 软件研究所,北京 100190)

2(中国科学院大学,北京 100049)

3(南昌师范学院 数学与计算机科学系,江西 南昌 330032)

实时反应式系统[1]被广泛应用在医疗、工业、军事、通信、交通等安全攸关领域.这类系统有主动行为,其运行受外部事件驱动.系统通过一系列传感器采集外部环境数据,对连续不断的事件流进行监视,从中识别出需要关注的场景(该场景是由一系列事件的发生所喻示的),实时地对识别出的场景做出响应.随着实时反应式系统应用环境的日趋复杂,人们对这类系统智能化的需求也越来越高,这就要求复杂反应式系统必须具有强大的推理能力,能够根据外部环境中发生的事件,自动决策如何对这些事件进行响应.因此,将规则推理系统应用于实时反应式系统就成为必然趋势.

实时反应式系统通常是安全攸关系统,具有硬实时约束.即当某些需要关注的事件发生后,系统必须在给定截止期内完成相应的动作,对这些事件进行响应;否则会产生严重后果.这就要求规则推理需要具有时间约束.学者们为此提出了实时推理方法,如迭代推理[2](如Anytime算法)、多重方法推理[3](如Design-to-Time算法)和渐进式推理[4,5](如GREAT算法和PRIMES算法).这些方法为整个推理过程定义了截止期约束,通过对推理运行时间与推理结果质量进行折中来满足这个截止期约束.此外,学者们还通过改进传统规则匹配算法 RETE缩短了OPS5产生式系统的匹配时间,从而降低了整个专家系统的响应时间[6,7].同时,李想等人[8,9]提出了估算实时规则推理程序最大响应时间的方法.李娜等人[10,11]针对实时感知数据流,为复杂事件检测的整个过程引入了截止期,并提出启发式调度算法对检测过程进行调度,缩短了复杂事件检测的平均时间.由于上述研究忽略了各规则不同的紧迫度与资源需求,很可能会在资源受限的情况下获得不可接受的推理结果质量.

为此,我们在前期工作中提出了一种新的实时推理模式[12]:实时规则推理.在实时规则推理中,我们为每条规则(规则的形式为:IF 〈EVENTPATTERN〉 THEN 〈ACTION〉.其语义为:若〈EVENTPATTERN〉定义的目标事件发生,则执行〈ACTION〉定义的动作)引入了截止期(规则截止期为该规则响应时间的上界(规则响应时间是指从与规则相关的所有原子事件实例到达系统开始到响应动作执行完毕为止的时间间隔)),并提出了软实时规则调度算法[13,14].但这些方法只是尽可能地使规则在其截止期前执行完毕,无法预测实时规则推理对资源的动态需求,也就难以保证各规则的截止期,从而无法满足安全攸关系统的硬实时约束.规则调度是保证规则截止期的关键.因此,本文将对该问题进行研究.具体来说,规则调度问题(rule scheduling problem,简称RSP)是找到一种实时调度策略,能够合理安排各规则的匹配与执行顺序,使得每条规则的响应时间不超过其截止期.

由于处理数据规模的不断增大和计算复杂度的持续上升,安全攸关系统需要运行在计算能力更强、更有弹性的多核环境下.多核计算具有更强的并行处理能力、更高的计算密度,同时具有更低的时钟频率,减少散热和功耗,因此,研究在多核环境下安全攸关系统的规则调度问题十分必要(多核环境是指“单机多核”,也就是说,安全攸关系统运行在单机上,只有1个处理器,但该处理器包括了多个处理器核).为了解决多核环境下安全攸关系统中的规则调度问题,本文提出了一种基于图模型的实时规则调度(graph-based real-time rule scheduling,简称GBRRS)方法.该方法首先对基于事件图的推理过程进行建模,将规则调度问题转化成基于图的端到端推理任务调度.并给出了多核环境下端到端推理任务的调度算法,一方面通过调度端到端推理任务来合理安排规则匹配与执行的顺序;另一方面,通过提出准入控制算法,对推理过程所需资源进行预测,以保证每一条触发规则都在其截止期之前完成(若规则〈EVENTPATTERN〉部分所定义的目标事件发生,则该规则被称为触发规则),从而保障了多核环境下规则推理的实时性,进而保证了安全攸关系统的硬实时约束.

本文第 1节对面向安全攸关反应式系统的实时规则推理系统和基于事件图的实时规则推理过程加以描述.第2节给出多核环境下基于图模型的实时规则调度方法.第3节的模拟实验对GBRRS方法的性能进行验证.第4节对全文进行总结,介绍下一步的研究工作.

1 实时规则推理系统

本节将描述面向安全攸关反应式系统的实时规则推理系统,重点介绍其系统结构与实时规则推理引擎所采用的实时规则推理过程.

1.1 实时规则推理系统结构

面向安全攸关反应式系统的实时规则推理系统为S=(R,E,I),其系统结构[15]如图1所示.其中,R是规则库,存放可描述专家知识的规则集R={R1,R2,…,Rn},每条规则Ri(1≤i≤n)具有截止期Di;E是由外部环境产生并进入实时规则推理系统的原子事件实例所形成的事件流,E={e1,e2,…,ek,…}.事件检测器将事件流中被规则Ri(1≤i≤n)涉及的原子事件实例输入实时规则推理引擎I.

Fig.1 Real-time rule reasoning system图1 实时规则推理系统

实时规则推理引擎I根据输入的事件流,从规则库中匹配出相应的规则(规则匹配:给定规则集R={R1,…,Rn},根据到达系统的原子事件流,对R中每条规则Ri,判断其所定义的目标事件是否发生),并在其截止期前执行该规则所定义的响应动作指令(简称为规则执行),其核心包括规则调度器与规则执行器.规则调度器运行相应的规则调度方法将基于事件图的实时规则推理过程转化为一组并发的实时推理任务,并对这组推理任务进行调度;规则执行器负责执行被调度器选中的推理任务.这样,实时规则推理引擎即可通过合理安排规则匹配与执行的顺序来保证规则的截止期,使安全攸关反应式系统可以在截止期前对其所关注的场景做出响应.本文将对规则调度器所运行的规则调度方法进行研究.第1.2节将介绍基于事件图的实时规则推理过程.

1.2 基于事件图的实时规则推理过程

在基于事件图的推理过程[16]中,规则集R={R1,R2,…,Rn}可用有向无环图(directed acyclic graph,简称DAG)来描述.该有向无环图称为规则图GR.GR=(V,A,E),其中,V表示事件节点(包括原子事件和复合事件),A表示响应动作指令的节点(简称为动作节点),E表示节点间时序关系(方向代表了时序先后)的有向边.

若存在规则集R={R1,R2,R3},其中,

则R所对应的规则图GR如图2(a)所示,其中,没有直接前驱的节点是源节点,表示原子事件(如e1,…,e11),也称原子节点;没有直接后继的节点是终节点,表示响应动作指令(如A1、A2、A3),也称动作节点;其他节点为中间节点,表示复合事件;原子节点和中间节点都表示事件,也称事件节点;动作节点的父节点表示目标事件(如E1、E2、E3),称为目标节点.

在规则图GR中,事件节点的入度表示了组成该节点的事件个数.如图2(a),事件节点b=e3∧e4∧e5,即e3～e5通过事件复合形成了b,则b的入度是3;事件节点e=a→b,则e的入度是2.目标节点以外的事件节点,其出度表示了该节点参与生成复合事件的次数.若A是GR中的动作节点,且表示规则Ri(1≤i≤n)所定义的动作,那么规则Ri的规则子图是A可达的所有节点(包括A在内)组成的子图,如图2(b)～图2(d)所示.规则的高度是其规则子图从原子节点到动作节点的最大层数,如图2所示,R1、R2和R3的高度分别为5、4和6.

Fig.2 Rule graph图2 规则图

基于事件图的推理过程是以到达系统的原子事件实例为依据,通过对规则图的搜索及规则子图的匹配来完成的.该推理过程的具体步骤如下.

· 步骤1:原子事件实例到达系统后按照时间先后被送往规则图中的原子节点.

· 步骤2:原子节点接收原子事件实例后,将对其事件类型进行匹配,而后将匹配结果送往其所有直接后继的事件节点.

· 步骤3:目标节点以外的事件节点在接收到送来的事件实例后,将根据事件复合的算法[17-19]处理这些事件实例并进行匹配,以判断当前节点的事件实例是否生成:若匹配成功,将生成新的事件实例,并把该实例送往其直接后继的事件节点;若匹配失败,则转到步骤2接收新的原子事件实例进行匹配.

· 步骤4:若当前的事件节点是目标节点,且该节点的事件实例复合并匹配成功,则将生成的事件实例送往动作节点;若匹配失败,则转到步骤2接收新的原子事件实例进行匹配.

· 步骤5:如果动作节点成功接收到目标节点送来的事件实例,则输出响应动作指令,表明以该目标节点为终节点的规则子图已匹配完成;否则,转到步骤2接收新的原子事件实例进行匹配.

· 步骤6:重复步骤2～步骤5,直至所有的原子事件实例都被处理完毕.

可以看出,规则图GR中每个节点上的推理操作是接收一次事件实例,对其进行匹配并向其直接后继节点传输;每条规则上的推理操作是对规则图GR中相应规则子图的一次匹配.

2 多核环境下基于图模型的实时规则调度方法

本节将重点描述如何解决多核环境下规则调度问题的难点:(1)如何对基于事件图的推理过程对规则调度问题进行建模,即如何将实时规则推理过程转化成基于图的端到端推理任务;(2)如何为推理任务合理安排执行顺序,并提出准入控制算法,对推理过程中所需资源进行预测,保证每条规则一旦被处理都能在其截止期前完成,从而保障了安全攸关系统中规则的实时性.

为此,本节将给出一种基于图模型的实时规则调度方法.该方法首先通过图映射方法为规则调度建立基于图的端到端推理任务模型,并提出多核环境下的推理任务调度算法,从而解决多核环境下的规则调度问题.

2.1 实时规则推理过程建模

实现规则上的推理操作与推理任务之间的映射有两种方法:一是直接映射,简称 DM;二是图映射(graph-based mapping),简称 GM.

在DM方法中,把每条规则Ri(Ri∈R)上的推理操作直接映射成推理任务τi,规则集的推理过程就转化成推理任务集τ={τ1,…,τn},τi=(ri,Ci,Di).其中,τi的参数如下.

ri是τi的就绪时间,即Ri相关联的所有原子事件实例均到达系统的时间;Ci是τi的执行时间,其数值可通过规则匹配的最坏执行时间分析技术来获得[20];Di是τi的相对截止期,等于Ri的相对截止期(可由应用给定).

此外,si是τi开始执行的时间;Ci(t)是t时刻τi的剩余执行时间;fi是τi的完成时间,fi=min{t|Ci(t)=0};RSi是τi的响应时间,RSi=fi-ri,RSi≤Di;di是τi的绝对截止期,di=ri+Di,fi≤di.

从第 1.2节可知,基于事件图的实时规则推理过程是动态的.一条规则的匹配有可能因为其规则子图上的任一节点匹配不成功而终止,其运行时间无法事先预测.而DM方法中,只能使用规则匹配的最坏执行时间作为推理任务的执行时间,这过度估计了推理任务所需资源,从而降低了推理任务的调度成功率,导致了规则调度成功率的下降.为了更为精确地对动态的实时规则推理过程进行描述,本文提出了GM方法,将实时规则推理过程转化为一组基于图的端到端推理任务(end-to-end reasoning task graph,简称E2ERTG).

在GM方法中,把每条规则Ri(Ri∈R)上的推理操作映射成一个端到端推理任务τi,把规则子图中每个节点上的推理操作定义成τi的子任务{τi,1,…,τi,j,…},则规则集的推理过程就转化成推理任务集τ.如图3所示,R1～R3所对应的端到端推理任务为τ1～τ3,其中,τ1={τ1,1,…,τ1,13},τ2={τ2,1,…,τ2,7},τ3={τ3,1,…,τ3,12}.

Fig.3 Graph-based mapping图3 图映射

推理任务τi=(Di,{τi,j|1≤j≤ni},Gi)有以下参数:Di是τi的相对截止期;{τi,j|1≤j≤ni}是τi的子任务集合;Gi是τi的子任务图,是个有向无环图,代表了ni个子任务之间的偏序关系.

在Gi中,若存在有向边从τi,u指向τi,v,则τi,v是τi,u的直接后继,τi,u是τi,v的直接前驱.τi,j的直接前驱集合记为preddt(τi,j),其直接后继集合记为succdt(τi,j).若存在τi,u到τi,v的路径,则τi,v称为τi,u的后继,τi,u称为τi,v的前驱.τi,j的前驱集合记为pred(τi,j),其后继集合记为succ(τi,j).在Gi中,没有直接前驱的节点是源节点,其代表的子任务称为源任务;没有直接后继的节点是终节点,其代表的子任务称为终任务;其余节点是中间节点,其代表的子任务称为中间任务.

值得注意的是,不同端到端推理任务的子任务可能执行相同的操作.如图3所示,τ1的子任务τ1,3和τ2的子任务τ2,1都执行的是对事件e3的推理操作;τ1的子任务τ1,9和τ2的子任务τ2,5均执行的是对事件b的推理操作.

定义1.设τi,τi+1,…,τj为一组端到端推理任务,若其子任务τi,p,τi+1,l,…,τj,q所执行的推理操作相同且任务参数也相同,则称τi,p,τi+1,l,…,τj,q互为关联的子任务.

显然,根据第 1.2节的实时规则推理过程,在一组互为关联的子任务中,若其中任一子任务执行完毕并获得计算结果,则其余子任务便可获得相同的执行结果.因此,在调度中只需为其中任意一个子任务分配处理器资源即可.为此,本文引入关联节点来表示互为关联的所有子任务,形成了推理任务集τ的推理任务图Gτ,如图4所示.

定义2(关联子任务集Ψ).设V是Gτ中的关联节点集合(节点个数是c),Vr(1≤r≤c)是V中的关联节点,则ψ(r)是Vr所表示的推理子任务集合,且.

如图4 所示,Vr={e3,e4,e5,b,e6,e7,c,e8},其中,ψ(1)={τ1,3,τ2,1},ψ(2)={τ1,4,τ2,2},ψ(3)={τ1,5,τ2,3},ψ(4)={τ1,9,τ2,5},ψ(5)={τ1,6,τ3,1},ψ(6)={τ1,7,τ3,2},ψ(7)={τ1,10,τ3,7},ψ(8)={τ3,3,τ2,4},则

Fig.4 Reasoning task graph图4 推理任务图

在推理任务图Gτ中,每个推理任务∀τi(i≥1)及其子任务的参数见表1.其中可参见DM方法中的相关定义.的定义与和Ci(t)的定义类似.在此不再赘述.

Table 1 Parameters of tasks and sub-tasks表1 任务及子任务参数

若τi,k是源任务,则ri,k是原子事件实例到达其相应源节点的时间(即原子事件实例到达系统的时间);否则,ri,k是其所有直接前驱任务的最晚完成时间,即ri,k=max{fi,j},∀τi,j∈preddt(τi,k).ri是所有源任务的最晚就绪时间,即ri=max{ri,k},τi,k是源任务.Ci,k是τi,k在Gτ中相应节点上推理操作的执行时间;Ci是τi的最坏执行时间,即τi所有推理子任务的最坏执行时间之和:.若τi,k为终任务,则有.

显然,通过GM方法建立基于图的端到端推理任务模型E2ERTG,可将多核环境下的规则调度问题RSP转化为基于图的端到端推理任务调度问题,即:

给定m个处理器核P={P1,P2,…,Pm}及推理任务集τ={τ1,τ2,…,τn},其中,τi=(Di,{τi,j|1≤j≤ni},Gi);任意子任务τi,j(τi,j∈τi,τi∈τ)可被分配到任意的处理器核Pi(Pi∈P)上执行,并允许其在处理器核之间迁移.找到一种实时调度方法,使∀τi(τi∈τ),fi≤di,i∈{1,2,…,n};其中,fi是端到端推理任务τi的完成时间,di是τi的绝对截止期.

为解决上述问题,下一节将给出基于图的端到端推理任务(E2ERTG)的调度算法,通过保证所有的推理任务都在其截止期之前完成执行,来保证规则的截止期.

2.2 推理任务调度算法

多核环境下,对基于图的端到端推理任务进行调度的关键点是:(1)如何实现推理子任务之间的同步,使其满足子任务间的时序约束;(2)如何分配推理子任务的全局动态优先级;(3)如何对新到达的推理子任务进行准入控制,以保证所有准入的推理任务一旦执行都将在其截止期前完成.为此,我们将提出基于图的端到端推理任务调度算法(end-to-end reasoning task graph-based scheduling,简称ERTGS).

2.2.1 同步协议

同步协议的目的是为了保证推理任务图中子任务之间由有向边指定的时序关系,其策略为:除源任务外的子任务就绪时间等于其直接前继任务的最晚完成时间.即

图5是实现同步协议的伪代码.对于推理任务图中除终任务外的其他子任务,将其就绪时间初始化为无穷大的整数值;邻接矩阵adj_G存储的是推理任务图中子任务之间的时序关系.从邻接矩阵adj_G获取所有子任务的直接后继和直接前驱任务列表(参见图5的第3行和第5行).当任意一个推理子任务完成时,通知该子任务的所有直接后继任务更新其直接前驱任务的完成情况(参见图5的第7行和第12行).τi,s的所有直接前驱任务均完成时,根据公式(1)更新τi,s的就绪时间(参见图5的第9行和第13行).

Fig.5 Synchronization protocol图5 同步协议

2.2.2 优先级分配

ERTGS根据紧迫度和影响度为每个就绪的推理子任务τi,k分配全局的动态优先级.

设τi,k的紧迫度为urgency(τi,k),其计算方法如下:

由公式(2)可见:对于推理任务图Gτ中非关联节点所代表的推理子任务τi,k,urgency(τi,k)是其所属推理任务τi绝对截止期di的倒数;对于Gτ中关联节点Vr所代表的任意τi,k,urgency(τi,k)是ψ(r)中任意τj,l所属推理任务τj绝对截止期的最小值之倒数(ψ(r)是Vr上所有互相关联的推理子任务集合).推理子任务的紧迫度越大,其优先级也越高.

当紧迫度相同时,按其影响度来决定优先级高低.影响度越大,优先级越高.设τi,k的影响度为effect(τi,k),对于Gτ中非关联节点所代表的τi,k,effect(τi,k)是τi,k在Gτ中的出度;对于Gτ中关联节点Vr所代表的任意τi,k,effect(τi,k)是ψ(r)中推理子任务的个数.effect(τi,k)的计算方法如下.

其中,cnt(A)是集合A中的元素个数.effect(τi,k)取值为τi,k出度和succ(τi,k)出度的最大值.

就绪的推理子任务根据公式(2)、公式(3)分配优先级,按照递减的顺序形成优先级队列.若处理器核出现空闲,则将队首的推理子任务从队列中移除,并分配到该处理器核上执行.若推理子任务执行完毕或者有新的推理任务被准入系统(准入控制的具体方法可参见下小节),则根据公式(2)、公式(3)重新分配各就绪推理子任务的优先级,并更新优先级队列.重复上述操作,直至优先级队列为空.

2.2.3 准入控制

当新的推理任务就绪时,ERTGS将对其进行准入控制来保证所有推理任务一旦被准入系统,必将在截止期前完成,即所有被准入的推理任务必定会被成功地调度,从而保证了规则集进行调度的安全性.

定义3(t时刻的活动任务).若τa已就绪,但在t时刻未完成且未到其截止期,则τa是t时刻的活动任务.

定义4(t时刻的活动任务集).在t时刻,所有的活动任务所组成的集合是t时刻的活动任务集.

定义5.基于图的端到端推理任务集τ={τi|1≤i≤n}在推理任务调度算法 ERTGS下是可调度的任务集,当且仅当对于∀τi(τi∈τ)均有fi≤di,fi是τi的完成时间,di是τi的绝对截止期.

定理 1.基于图的端到端推理任务集τ={τi|1≤i≤n}在推理任务调度算法 ERTGS下是可调度的任务集,当且仅当对于∀τi,j(i∈[1,n],j∈[1,ni])均有fi,j≤di,fi,j是τi,j的完成时间.

证明:如果对于∀τi,j(i∈[1,n],j∈[1,ni])均有fi,j≤di,则根据第 2.1节中所述的推理任务模型,显然有fi,ni=fi;因此,∀τi(τi∈τ)均有fi≤di,根据定义3可知,基于图的端到端推理任务集τ在ERTGS下是可调度的任务集.

如果基于图的端到端推理任务集τ在ERTGS下是可调度的任务集,则根据定义3,对于∀τi(τi∈τ)均有fi≤di.根据第2.1节中所述的推理任务模型,显然有fi,j≤fi,那么fi,j≤di.

综上所述,基于图的端到端推理任务集τ={τi|1≤i≤n}在推理任务调度算法 ERTGS下是可调度的任务集,当且仅当对于∀τi,j(i∈[1,n],j∈[1,ni])均有fi,j≤di,fi,j是τi,j的完成时间. □

假设τ(t)={τ1,τ2,…,τu}是t时刻可调度的活动任务集,如果t时刻新任务τr就绪,则准入控制操作如下.

根据定理 1 判断:若{τ1,τ2,…,τu}∪{τr}为可调度任务集,则τr被准入;否则,τr被拒绝.

在此,τi的完成时间可如下计算:

不妨设{τ1,τ2,…,τv}是按当前优先级递减排序的活动任务集,处理器核个数为m,那么,

· 如果v

· 如果v≥m,则

其中,公式(5)的迭代计算方法可参见文献[21],在此不再赘述.

ERTGS的准入控制伪代码如图6所示.在此,假设τ为可调度的活动任务集,τnew为就绪的新任务.

Fig.6 Admission control图6 准入控制

若处理器核的个数为m,实时规则的个数为N,则端到端推理任务的类型也有N种,不妨设所需调度的推理任务实例个数是n(实时规则可被触发多次而产生多个规则推理任务的实例),基于图的端到端推理任务模型下,推理子任务实例个数总和为w,那么DM-EDF方法时序约束控制的复杂度是O(1)(DM-EDF方法是用DM方法把规则上的推理操作映射成推理任务后用全局EDF算法[22]对其进行调度),GBRRS方法虽然引入图模型,其时序约束控制的复杂度仍是O(1);DM-EDF方法优先级排序的复杂度是O(n×log2n),GBRRS方法优先级排序的复杂度是O(w×log2w);DM-EDF方法准入控制的复杂度是O(m×n2),GBRRS方法准入控制的复杂度是O(m×w2).于是,DM-EDF方法的复杂度是O(1)+O(n×log2n)+O(m×n2),而GBRRS方法的复杂度是O(1)+O(w×log2w)+O(m×w2).在此,由于处理器核的个数事先给定,m为常数;同时,由于规则也是事先给定的,规则图的结构及其所包含的节点数也是固定的,对于每个基于图的端到端推理任务实例来说,其子任务实例数都是它的常数倍,因此,w最多是n的常数倍,引入图后规则调度方法的复杂度并没有本质提高(引入图后规则调度方法能提高 10%以上的规则调度成功率,而这种程度的成功率提高在实际应用中的意义是比较大的,因此还是值得引入图来对推理任务进行建模).

2.3 调度举例

设处理器核的个数m=2,用DM-EDF方法和GBRRS方法来调度图2所示的规则集R(R={R1,R2,R3}).

DM-EDF方法将R转化成τ={τ1(3,40,42),τ2(3,19,43),τ3(4,39,43)}进行调度,τ中推理任务的执行顺序如图7(a)所示.其中,τ3因为完成时刻(为 61)错过其绝对截止期(为 47)而被拒绝进入系统,即其相应的规则R3在DMEDF方法调度下被系统拒绝执行规则匹配操作.

GBRRS方法则将R转化为推理任务图GR如图4所示.根据第2.1节中基于图的端到端推理任务模型,可利用任务及其子任务的部分参数(表2中的非粗体数值)初始化它们的其余参数(表2中的粗体数值)并根据第2.2节中的推理任务调度算法对其进行调度,τ中推理任务的执行顺序如图7(b)所示.

Fig.7 DM-EDF and GBRRS scheduling examples图7 DM-EDF和GBRRS方法的调度实例

从图7(a)和图7(b)可以反推出规则R1(正斜线),R2(横线)和R3(反斜线)的执行顺序,由此可见,规则集R用DM-EDF方法不能被调度成功,而用 GBRRS方法则能够被调度成功.具体来说,图7的调度结果显示,R1和R3的完成时间在DM-EDF方法下比GBRRS方法下都提前了17个时间单元.这是因为GBRRS方法具有以下两个优点.

· 首先,GBRRS方法的调度单元是推理子任务τi,j,能够更充分地利用处理器的空闲资源.具体来说,

(1)GBRRS方法允许已就绪的子任务τi,j在τi就绪前开始执行,更好地利用了处理器的空闲时间,减少了τi的等待时间.如图7(b)中,τ1,5和τ1,6可利用τ1就绪前在t=1到t=3的时间段占用处理器运行.

(2)GBRRS方法可利用推理任务图的特点,将具有相同直接前继的多个推理子任务并行地占用处理器,提前了τi的完成时间.如图7(b)中,τ1,2和τ1,1可并行执行,τ3,6和τ3,5也可并行执行,则τ1和τ3的完成时间分别提前了14个和3个时间单元.

· 其次,GBRRS方法可以及时地反映推理任务τi执行时间的动态变化,从而反映规则对处理器资源需求的动态变化,提高了规则调度成功率.比如,GBRRS方法通过引入关联子任务集来减少关联子任务的重复执行,从而提前了推理任务的完成时间.如图7(b)中,子任务τ1,5执行完成,互为关联的τ2,3也执行完成.因此,τ2和τ3分别减少了11个和16个时间单元的重复执行,其完成时间也被提前.

Table 2 Parameter initialization of tasks and sub-tasks表2 任务和子任务的参数初始化

3 模拟实验

本节将通过模拟实验来验证GBRRS方法的性能,并将其与DM-EDF方法进行对比.

3.1 模拟实验设置与性能指标

为了保障测试集的合理性(本文的任务是基于安全攸关系统中规则推理过程建模而产生的,而多核环境下基于图的端到端实时任务调度并没有被研究,因此,已有的调度研究中没有相关的Benchmark实例集可用),本文通过泊松分布模拟安全攸关系统中的原子事件实例到达情况,从而模拟出推理任务的生成,并通过设定规则事件匹配子图相关的参数来随机生成规则图,从而模拟安全攸关系统的规则.实验中涉及的参数见表3.

Table 3 Parameters表3 参数

规则集的生成过程如下.

· 步骤1:随机生成penum个原子节点,为每个节点随机选取出度(不超过outdegreemax,规则子图中,每个节点的出度是该节点被用次数(即该节点上的事件被用于生成复合事件的次数)的最大值)、节点上推理操作的执行时间(范围为cminmax)以及节点上原子事件实例的到达时间(满足泊松分布,其参数在100～250范围内),那么初始候选节点集为这些原子节点(候选节点是被用次数小于出度的事件节点).

· 步骤2:随机选取当前规则子图的高度(不超过topdowndepthmax),当前规则子图是当前即将生成的规则所对应规则子图.

· 步骤3:随机选取当前事件节点的入度indegree(事件节点的入度是复合生成该节点上事件的候选节点的个数,不超过indegreemax),从当前的候选节点集中选取indegree个候选节点,通过随机的事件操作符复合生成当前节点上的事件,则当前事件节点生成完毕;更新当前规则子图的高度,事件节点的被用次数和当前的候选节点集.

· 步骤4:重复步骤3,直到当前规则子图的高度达到topdowndepth-1(此时,目标节点已生成完毕)时,则生成该规则子图的动作节点.至此,该规则子图生成完毕,随机选取该规则子图的相对截止期(范围为dminmax4rule),并更新规则集的总负载和平均负载.

· 步骤5:重复步骤2～步骤4,直到规则集的负载达到设定值.

实验的性能指标是规则调度成功率:

其中,NSR是在截止期前完成的规则个数,NR是被调度的规则总数.

3.2 实验结果分析

本节给出了规则调度成功率随规则集的平均负载UR而变化的情况,如图8(在保持m不变的前提下,通过SR递增使UR递增)和图9(在保持SR不变的前提下,通过m递增使UR递减)所示.令penum=1000,根据上一节所描述的方法来生成随机的规则集,并分别用DM-EDF方法和GBRRS方法对其进行调度.图8和图9中每个点的取值都是进行了5次实验取其平均值后的结果.

由图8可见,DM-EDF方法和GBRRS方法下的规则调度成功率都随UR的增加而逐渐减少.GBRRS的规则调度成功率比DM-EDF的规则调度成功率平均高出14.86%,这是因为GBRRS方法能够及时反映推理任务执行时间的动态变化,从而及时反映出规则对处理器资源需求的动态变化,减少了其响应时间,增加了规则调度成功率.当UR≤100%时,两种方法的规则调度成功率都是100%;但当UR≥100%时,随UR的增加,两者之间的差距先增大后减少,这是因为关联子任务集出现的概率随UR的增加而增加,因此,GBRRS方法的规则调度成功率下降较为平缓,两者差距逐渐增大;当UR≥350%时,关联子任务集在GBRRS方法中所产生的优势由于处理器资源的紧缺而逐渐不再突出,因而两者差距又逐渐减少了.可以看出,在UR较高,如350%时,GBRRS仍保持80%以上的规则调度成功率.

Fig.8 Average rule scheduling success ratio as a function ofURwhenm=8图8m=8时随UR变化的平均规则调度成功率

Fig.9 Average rule scheduling success ratio as a function ofmwhenSR=50图9SR=50时随m变化的平均规则调度成功率

图9表明,DM-EDF方法和GBRRS方法下的规则调度成功率都随m的增加而提高,也就是随UR减少而提高.GBRRS的规则调度成功率比DM-EDF的规则调度成功率平均高出13.05%,这是因为GBRRS方法的调度单元是推理子任务τi,j,能够更充分地利用处理器的空闲资源.随着处理器核的个数增加,两者的差距逐渐增大.这是因为随着处理器核的个数增加,GBRRS方法中推理任务并行占用处理器的几率增大,更容易被调度成功,因此,两者的差距逐渐增大.当m≥18时,GBRRS可以成功调度规则集里的所有规则,成功率达到100%.

综上,无论规则集的平均负载如何变化,GBRRS方法都比 DM-EDF方法在规则调度成功率上平均高出13%～ 15%;而且GBRRS方法在规则集的平均负载较高(如350%)时,仍保持着80%以上的规则调度成功率.

4 结束语

为了解决多核环境下的规则调度问题,本文提出了一种基于图的规则调度方法(GBRRS).

· 首先,GBRRS方法根据基于事件图的推理过程,用图映射方法对规则调度进行了建模,提出了基于图的端到端推理任务模型.

· 然后给出了推理任务的调度算法,通过调度这些推理任务来合理安排规则匹配与执行的顺序,从而保证了规则调度的安全性.

· 最后进行了模拟实验.实验结果表明,GBRRS方法在规则调度成功率上优于 DM-EDF方法,且在规则集的平均负载较高(如350%)时,其规则调度成功率仍保持在80%以上.

在下一步工作中,我们将考虑解决以下两个问题.

· 第一,在规则重要性不同的情况下,进行规则调度时,还需要考虑规则在不同重要性之间的切换以及在高重要性模式下截止期的优先满足.

· 第二,在异构的多处理器环境下为规则分配处理器核,还需要考虑不同处理器核上处理速率的差异性.