开放式数控系统的低能耗和可靠性调度算法

邓昌义，郭锐锋，段立明，王　帅，杜少华

(1.中国科学院 沈阳计算技术研究所,辽宁 沈阳　110168;2.中国科学院大学,北京　100049；3.沈阳高精数控智能技术股份有限公司,辽宁 沈阳　110168)

0　引言

基于PC的开放式数控系统主要分为NC嵌入PC型、PC嵌入NC型和全软件型NC这三种类型结构[1]。嵌入式的PC数控系统使得开放式数控系统能随着PC技术的发展而升级。开放式数控系统作为一种典型的实时系统，是数控机床的核心部件。数控系统采用编程指令实时控制数控机床的运动位置，通过伺服系统内的位置闭环、速度环和电流环的调节，完成程序规定的加工任务[2]。数控系统不仅要求在截止期限内完成任务，而且要保证任务的正确执行。随着多核平台以其强大的计算能力被广泛应用在实时系统[3](例如AMD APU, Intel Haswell,龙芯3B1500和ARM11 MPCore等处理器)，尽管多处理器系统级芯片(Multicore System-on-chip, MPSOC)的多核架构已被用于开方式数控系统中，但带来的系统能耗越来越高，高能耗带来的高温会导致系统发生故障的可能性增加，进而降低数控系统的可靠性[4]。因此,设计满足高可靠低能耗的开放式数控系统成为一个非常重要的问题。

在开放式数控系统方面，为方便快捷地开发出专用控制器,允许系统进行二次开发。文献[5]提出开放式专用数控系统的核心模型包括：功能模型、数据模型、结构模型和行为模型,该模型采用嵌入式和多CPU架构实现了专用数控系统的分布式操作。文献[6]提出面向开放式数控系统的一种基于预分配的空闲挪用算法，算法开始前,采用预分配算法为实时周期任务预留处理器时间,使得在调度周期任务时空闲时间尽可能提前。在调度非周期任务上,采用最大的可用空闲时间机制,实现以较小的计算和较低存储开销获得最短的非周期任务响应时间。

在降低能耗方面，动态电压调节(Dynamic Voltage Scaling, DVS)和动态电源管理(Dynamic Power Management, DPM)被应用于能耗优化。DVS通过调整处理器的电压降低能耗，DPM通过利用空闲时间的处理器和关闭电源，以减少静电能耗的产生[7]。多核处理器通过权衡空闲时间长短，选择利用DVS调整电压或者使用DPM关闭空闲处理器。文献[8]提出一种能耗感知调度技术，在最小化能耗的同时满足吞吐量和响应时间的要求。文献[9]提出一种能耗管理算法，以探索在单处理器系统中使用流水线和并行处理技术。但这种基于单处理器的技术不能直接应用于多核系统。

要实现对瞬态故障的容错，需要故障检测机制[10-11]。然而，常见的故障检测机制不能满足数控系统高可靠性的需要，作为一种故障检测机制，N模块冗余不需要额外硬件检测故障，该方法使用多数投票的方式进行故障检测和容错[10]。由于所有任务不可能同时出现相同的错误结果，多数投票的方式可以实现对系统故障的检测和容错[10]。但N模块冗余需要消耗更多的能耗来实现容错[11]。

为解决基于嵌入式数控系统的可靠性和低能耗之间的协同调度问题，本文首先对依赖任务的有向无环图(Directed Acyclic Graph, DAG)进行建模，使其成为不具有依赖的任务，消除有向无环图任务的优先关系，然后执行协同优化算法以获得更好的能耗结果。该算法利用N模块冗余技术，在多个处理单元对每个任务执行相同的副本，并对其结果以投票方式输出。若多个备份任务执行的结果相同，则任务执行正确，并回收容错阶段备份任务的空闲时间，否则，执行容错阶段的剩余副本完成容错。算法充分利用多核架构优势，采用流水线并行执行任务，在任务时序约束下，实现多核处理器系统上的低能耗和高可靠的目标。

1　系统模型与能耗模型

1.1　实时任务模型

作为数控机床的控制核心，数控系统的加工任务不是独立的而是相互依赖，需要处理轨迹插补、位置控制、运动控制等周期性任务，后续任务的完成需要前一个任务的数据。因此本文研究数控系统中的实时周期性依赖任务的调度。

定义1DAG表示一组周期性轨迹插补任务的依赖关系，是数据流图(DFG)的一种特殊情况。DAG可以表示为G=V,Ed,ρ,CM，是节点加权和边加权的有向图[12]，其中V是节点集，每个节点表示迭代中的任务，Ed是连接两个节点的有向边集合，ρ是有向边集合E的映射函数，表示两个相邻节点之间的延迟，CM(u)(u∈V)是用于计算节点u的时间函数。

定义2DAG的循环周期指计算无延迟有向边所组成的最长路径需要的时间。同一次循环的相关性使用无延迟边表示，不同次循环间的相关性用延迟边表示。带延迟边Ed(u→v)，G(E)表示节点V依赖第i次循环产生的数据，而节点u的依赖数据在第(i-G(Ed))次循环产生。每个节点上的数字表示任务执行需要的时间，“|”表示节点间需要1次延迟，“‖”表示需要2次延迟。

定义3一个任务集合有n个可并发执行的DAG任务{G1，G2，G3,,Gn}，系统中存在M个可用的并行处理器。每个DAG任务都包含若干个子任务集σk={J1，J2，J3,,Jk}，Ji=(Ci,Ti),i=1,2,,k,同一任务的多个子任务具有一定的时序依赖关系，执行存在先后关系。

任务在每个执行周期内，必须在截至时限D要求下执行结束。n为周期任务的数目,Ti为任务的周期,任务的周期都等于其截至期限,Ci为任务在处理器最大速度下的执行时间,即最坏情况下的执行时间。表1描述了一个周期任务流的执行时间和对应的能耗。图1是基于表1的DAG模型实例,其中每个节点代表一个任务，两个节点之间的边表示任务优先级关系。

表1　数控系统周期任务流的时间和对应能耗实例

重定时技术(retiming)利用平均分配DFG的延迟实现最小的循环周期[13]。在DAG中将节点V的每条输入边的延迟通过节点V在其每条边上进行标记，通过仅改变节点初始分配值的方式，保持节点间的相关性，而初始分配可以通过装入来实现[13]。实际上，每一次的重定时等同于一次软件流水操作。

1.2　能耗模型和可靠性模型

假设处理器速度频率或速度可以连续调节。当任务Ji在速度Si下执行时，任务实际执行时间为Ci/Si。对于整个任务集合对应的速度可以表示为S={S1,S2,S3,,Sn},这里Si是任务Ji运行时对应的速度。本文采用文献[14]的功耗模型，系统的功耗

P=Ps+h(Pind+Pdep)=Ps+

h(Pind+Ccf·Sm)。

(1)

式中：Ps表示系统静态功耗，当整个系统处于关闭状态时Ps=0，静态功耗主要包括维持系统主存和I/O设备在睡眠状态下的功耗；Pind表示和处理器频率无关的功耗；Pdep是依赖于处理器频率的动态功耗，包括CPU功耗，以及其他依赖于处理器速度产生的功耗；Cef表示系统有效的负载电容；m表示动态指数(2≤m≤3)；h表示系统状态，当系统处于活动状态时h=1，当系统处于睡眠状态时h=0。当系统处于活跃状态，一个任务在N/2个备份下的能耗表示为：

(2)

式中：Etr表示处理器状态转换开销，Ecom表示处理器间通信能耗开销。

定义4任务的可靠性即任务被成功执行的概率。瞬时任务出错概率符合泊松分布[14]。对于支持动态电压调节的实时系统，由瞬时错误引起的任务平均出错率和处理器调整频率f(对应电压V)之间的关系，可以表示为：

(3)

式中λ0表示在频率fmax最大情况下任务平均出错率，当f取最大值时g(fmax=1)。低频率或者低电压将导致由瞬时错误引起的任务错误率增加。由于f1，d(d>0)是一个常量，表示任务出错对DVS的敏感度。即当处理器处于最低的频率工作时，具有最高的失效率λmax=λ0·10d。

定义5系统的可靠性为所有任务成功正确执行的概率。第i个任务按最坏时间Ci执行，在处理器频率fi下的正确执行的概率为[15]：

(4)

定理1Rj(J1,,Jn)表示系统的可靠性，即每一个任务成功执行的可能性。若任务出错，使用空闲时间恢复第j个出错的任务。规定Rg表示系统要保证的稳定性。当整个系统存在j个出错任务，此时可靠性为：

Rj(J1,,Jn)=R1(f1)·Rj·(J2,,Jn)+

(1-R1(f1))·R1(fmax·Rj-1·(J2,,Jn))。

(5)

R1(J1,,Jn)=R1(f1)·R1·(J2,,Jn)+

(1-R1(f1))·R1(fmax)·R0·(J2,,Jn)。

(6)

推广到一般模型，当有j个任务需要容错，此时系统的可靠性为式(5)。式中加号前半部分表示任务J1成功执行，余下的j个备份任务可以给后续任务使用；加号的后半部分表示J1执行失败，后续任务需要j-1个备份任务容错。

问题描述在保证系统可靠性前提下找到最优的处理器频率，使得总能耗E最小：

(7)

s.t.

Rj(J1,,Jn)>Rg;

(8)

(9)

式中D′=D-BJ，其中BJ是容错任务所需总空闲时间，D是最坏截止期限。

2　低能耗与可靠性协同优化调度算法

2.1　非依赖有向无环图算法

非依赖有向无环图算法(Non-Dependent Directed Acyclic Graph Algorithm, DPDAGA)用于将周期性DAG变换成仅具有数据交互的非依赖性任务。根据重定时的定义，为了将周期性相关的DAG变换为一组独立任务，DPDAGA在初始DAG的每个边上添加一个延迟。同时，避免在每个边上添加不必要的冗余延迟，任务非依赖算法为每个节点采用最小重定时值的办法实现消除冗余。基于该规则，式(10)用于计算每个节点的重定时值。

r(v)=

(10)

式中，r[v]和r[u]表示节点v和节点u的重定时值。DPDAGA算法中将每个节点的初始重定时值初始化为0。找出所有叶节点并将它们放入队列Q中。Q的当前尾部元素存储在名为e_value的变量中。计算以广度优先的方式进行。当判断节点u的父节点v是当前队列Q的尾部元素，则不需要将节点v放入Q，因为它会产生不必要的冗余计算。所以e_value变量是非常有用的。在获得每个节点的重定时值之后，生成仅具有独立任务关系的重定时任务图Gr。算法的时间复杂度为O(n)，主要来自对节点的出队入队操作。

步骤1DPDAGA算法以周期性依赖任务图G为输入，对G各个节点进行遍历，并赋值r(u)←0；

步骤2遍历G的所有节点，若其中一个节点u是叶子节点，则将u加入队列Q，若u是尾部元素，则e_value←u；

步骤3若每个u的父节点v存在，则根据式(10)计算：r(v)←max{r(v)，r(u)+1}，若e_value ≠v，则将u加入队列Q,e_value←v；

步骤4重复以上遍历，直到G遍历完。输出每个任务重定时值r和它的任务图Gr

2.2　低能耗与可靠性协同优化调度算法

为了保证数控系统的可靠性，在多核平台上结合DVS技术采用具有低能耗的N模块冗余技术实现系统的可靠性和低能耗。为此，提出了低能耗与可靠性协同优化调度算法(Co-optimal Scheduling Algorithm for Low Power and Reliability on Multicore, CSALPRM)。所提出的N模块冗余算法分为两个阶段：

(2)容错阶段系统执行剩余备份任务部分，剩余的副本以独占模式执行完成投票。由于任务的N/2副本已经在无错阶段中被执行，因此在容错阶段中，执行相同任务的剩余N/2副本，一个任务执行完整投票过程至少需要2个任务备份。

任务容错模式下，如图2a每个处理器最多可以和其他处理器上的一个任务并行执行。而图2b(1)中，J2在处理器P1执行期间和处理器P2上的J3，J5与J2发生了重叠并行，当任务在容错模式执行完J2后，再返回到无错模式下执行，多核任务重叠将引起多处理器间的任务不能同步。因此，需要对容错阶段任务并行执行这种方式做出调整。如图2b中所示，J2和任务J3在空间上发生重叠，移动J3及其后续任务，直到J2和J3之间没有重叠，移动的时间量为Δα，即J2任务的完成时间和J3任务的开始执行时间之差。基于该规则，在容错模式下实现出错任务独占处理器，同时空间上和其他处理器最多实现一个任务并行执行。如图2b，经过4步实现容错模式下独占处理器。

当任务成功执行，容错模式将丢弃备份任务，释放空闲时间以降低能耗。如图3所示，容错阶段可以被回收的空闲时间有3种情况：

(1)情况Ⅰ(图3a)若除了Ji外没有任务，则从调度表中丢弃Ji时，释放的空闲是Ci+Comi，其中Ci是Ji最坏情况下的执行时间，Comi是比较结果(多数投票)或保存结果所需的能耗开销。

(2)情况Ⅱ(图3b)若Ji是执行时间最长的任务,释放的空闲时间:Ci-max{Cn}，则从调度中丢弃Ji之后，被回收空闲时间为：Ci-max{Cn}+Comi。

(3)情况Ⅲ(图3c)若存在大于Ji的一个任务Jn，则在从调度中移除Ji之后，将无空闲时间。因此空闲时间计算公式表示为：

(11)

算法的时间复杂度是O(N×M),主要来自函数Tolerance_task(Ji)对调度序列任务中出错任务的查找，以及出错任务Ji独占处理器移动其他处理器重叠任务所需要的操作。其中N是调度序列SQ的任务数，M是处理器数目。CSALPRM算法如下:

输入:独立重定向图Gr；D(任务截止期限);

M(处理器个数);每个任务设置N/2个任务备份数

输出:调度序列和系统能耗

1.初始化调度序列SQ=∅和当前调度时间长度L←0.

2.每个任务分配初始电压，按照任务处理时间降序排列.

3.每个任务分配N个并行拷贝

5.If(L≤D)，

6.则新的SQ序列是可调度的，break；

7.Else

8.转向步骤10

9. End if

10.While(True)

11.If(L>D)

12.选择调度序列中执行任务时间最长的任务JL，计算通信开销，增加该任务的电压，获得新调度序列和当前调度时间长度L

13.Else

14.选择调度序列中执行任务时间最短的任务Js，计算通信开销，降低执行该任务的电压，增加任务执行时间Δt

15.If(L+Δt≤D)

16.更新调度序列SQ和当前调度时间长度L=L+Δt

17. Else

18.获得新调度序列SQ，break

19.EndIf

20.EndIf

21. EndWhile

22. 任务执行阶段，在不同处理器上同时得到一个任务Ji的N个不同备份任务的执行结果

24.Ji执行正确，break

25.根据式(11)回收容错阶段BJi备份任务的空闲时间

26.else

27.无错模式中断，标记中断位置IR

28.启动容错模式，出错任务独占处理器，调用Tolerance_task(Ji)

29.If SQ=∅&Slack_time>t。

30.处理器进入睡眠模式

31.Else

32.保持当前处理器速度运行

33.EndIF

34.EndIF

Function Tolerance_task(Ji)

1. For(Jiin SQ)

2. For(i=0;i

3. If处理器上的备份任务BJi，有其他处理器上多个任务与其并行重叠执行比如Ji+1和Ji+2

4. Then

5.Δα=BJi的完成时间-Ji+2的开始执行时间(Ji+2是其中最长执行时间任务)

6.Ji+2以及其处理器上的后续任务向右移动Δα

7.End if

8.Endfor

9.Endfor

10.处理器以最大速度独占处理器执行备份任务BJi，得到执行结果RT(BJi)

11.Return RT(BJi)and IR

3　能耗与可靠性实例分析

3.1　能耗实例分析

本节考虑调度一个有依赖关系的应用程序流，对其进行能耗优化。采用表1的任务实例，假设有4个处理器，每个处理器都支持动态电压调节。功耗为：P=Cef·S2[14]，不失一般性，假设Cef=1 nF，电压和频率对应关系为(2 V，1 GHz)和(1 V，0.5 GHz)。每个任务的执行时间和对应的高电压低电压能耗如表1所示。为了更好地阐明问题。假设处理器睡眠模式下能耗为0.1 W，通过总线的读写通信能耗为0.5W，每个任务之间的通信时间是1 ms，所有任务完成的最坏截止时间是17 ms。如图4a所示，该调度过程采用每个任务2个备份策略，所有处理器执行任务使用高电压。执行完毕后，对比结果，若相同则该任务正确执行。此时执行图4b的任务，总能耗为：E=2×20×5+2×12×3+2×12×3+2×4×1+2×0.5×4×1+2×0.5×1+2×0.5×1+2×4×1+2×0.1×7+2×0.1×5=368.4 mJ。

图4b是利用DVS和DPM算法以及软件并行技术。首先根据非依赖算法将图1a转化为图1b。之后使用CSALPRM算法重新调度任务，调度结果如图4b所示。为了尽可能降低系统能耗，该算法使用软件并行技术，则数据依赖迭代产生的空闲时间可以被回收，用于降低处理器速度。但是需要考虑处理器内部通信开销，如J1与J2和J3与J5之间的通信开销。基于此DVS和DPM回收空闲时间降低系统能耗。所有任务在15 ms调度后，在处理器P3和P4剩下空闲时间，由于空闲时间不够长，不足以补偿关闭或转换处理器状态开销，本文所提出的算法将分配与任务J3相同的电压。整个能耗消耗为：E=2×6×3+2×6×2+2×2×1+2×5×10+2×1×2+2×1×3+2×0.5×3+2×0.5×1+2×0.5×2=180 mJ。CSALPRM算法调度任务比按正常顺序调度任务节约51.14%能耗。可见，经过并行优化的算法能够大幅降低系统能耗。以上实例只考虑任务不出错情形下的能耗，而真实的执行过程任务会出现错误，此时调度实例见3.2节。

3.2　可靠性实例分析

本文提出的N模块冗余技术在任务出错时的工作流程如图5所示。当任务发生某些故障时所提算法如图5a所示进行容错。假设任务J2出现故障，当比较J2的结果时，它们不匹配，因此系统暂时切换到容错阶段。在容错阶段中，J2的备份任务BJ2调度执行。然后对J2的2个副本J2，和BJ2的结果进行多数投票以容错故障。在容错阶段，BJ2独占处理器阶段时不执行J3，因为在检测J2中的故障之前它已经成功完成，因此不需要执行。当在容错阶段执行BJ2时，J4并行执行，其结果保存在内存中，以便用于以后的投票。在执行BJ2之后，系统切换回无错阶段，并从其被中断的点继续执行调度。在切换无错阶段之后，考虑关于任务J4的两种可能的执行情况：

(1)如果在无错阶段(如图5b)中执行J4期间一个备份发生故障，当对其进行投票时，系统不需要切换到容错阶段，因为作为2个副本，一个副本的结果在无错阶段中被获得，另一个副本的结果已经存在于内部存储器中。

(2)如果在无错阶段(如图5a)中执行J4期间没有发生故障，则不再需要在先前的容错阶段中预先执行J4的备份。

1)在容错阶段并行执行，预先执行不会施加任何时间开销。例如，在图5中可以看出，当系统必须在容错阶段中执行BJ2时，与其并行的BJ4预先执行。由于BJ2在独占处理器期间相对其他处理器在同一时间具有最长的执行时间，这意味着BJ4的预先执行会延长BJ2。事实上，如果没有使用预先执行，在容错阶段期间将浪费处理器资源，因此使用事先执行有助于为容错阶段保留相对较少的空闲时间，从而更多的空闲可用于能耗管理。

2)如果J4在后续的无错阶段没有发生错误，在容错阶段的预先执行可能变得无用，但是它对平均能耗的影响可忽略不计。这是因为仅当在无错阶段中发生故障时才预先执行。

从可靠性的角度来看，这种机制增强了系统的可靠性。从平均能耗的角度分析，考虑图5中的J2和J4。假设任务执行出现故障的概率为10-4，J2和J4的能耗均为12 mJ。当发生故障时，系统只在无错阶段执行J2，消耗2×12 = 24 mJ。如果在无错阶段中执行J2期间发生故障，系统将在容错阶段执行BJ2和BJ4，消耗(12+12)= 24 mJ。因此，执行J2和J4的平均能耗是(1-10-4)24+10-4(24+24)= 24.002 8 mJ，这和没有故障发生(24 mJ)时的能耗非常接近，平均能耗与无故障能耗相差小于0.01%。因此预先执行对能耗影响极小，可忽略不计。

3.3　任务集的可调度性分析

定理2给出了任务集是否可调度的判断方法。

定理2故障情况下，若σk是在处理机Pk上的任务集，σk最大执行时间ΔCmax由式(12)计算,δk的容错截止期FD的由式(14)计算。若σk满足ΔCmax≤FD,则任务集可调度σk;否则σk不可被调度。

(12)

此时,

(13)

(14)

证明由于任务的优先级是由高到低进行分配的,所以Jmax是当前分配的任务,且δk-{Jmax}已经是可调度的,只需保证Jmax的Ci小于其截止期即可,Jmax是δk中执行最长的任务且其Ci应等于在时间ΔCmax(Jmax)内δk所需要的计算量。在出现处理机故障时,δk上的任务仅有容错阶段任务:

(1)任务在无错阶段每个周期Ti内都执行一次,根据式(13)，在时间t内共需执行t/Ti次,当任务在处理机Pk上，所需的计算时间量为t/Ti×Ci，这部分时间为式(12)等号后的第一部分。

(2)在容错阶段,第一个请求必须在恢复时间BJi内完成,而后续请求的周期都为Ti,因此若t≤BJi,则仅第一个请求在时间[0,t]被执行,即φ=t/Ti，否则在时间[0,BJi]内请求执行一次，在[BJi,t]内请求执行(t-BJi)/Ti，此时根据式(13)，φ=t-BJi/Ti+1。

综上所述,可由式(12)计算得到Jmax的Ci。对于Jmax的容错截止期,Jmax为在无错阶段的任务时，FD(Jmax)为Jmax的周期Tmax。当Jmax为容错阶段的任务时,由于Tmax>BJmax，只需保证Jmax的第一个任务的Ci小于BJmax，则Jmax在以后的周期中均可调度，故此时FD(Jmax)为BJmax。显然若ΔCmax≤FD(Jmax)，则任务集δk可调度。证毕.

4　实验结果与分析

本文实验采用沈阳蓝天数控GJ400,系统处理器采用支持动态电压调节的低功耗64位龙芯3B-1 500处理器，该处理器允许调整的电压范围为:1.0—1.3 V，对应可变的处理器频率为1.0 GHz～1.5 GHz[17]。蓝天数控GJ400的核心功能模块如图6所示,其中运动控制器和PLC控制器负责进给驱动控制、主轴驱动控制及开关量控制，实现任务严格的实时性要求。任务管理器作为整个系统的管理中心，可以实现用户界面的操作信息，并为运动控制器与PLC控制器传递处理后的任务信息。在实验中，修改操作系统内核，以便在创建线程之前，系统调用可以将获得的任务信息发送到内核中。当任务调用Pthread_create()创建线程时，它会依次调用一系列系统调用函数，包括Sys_clone(),Do_fork()和Copy_process()函数。要调度新创建的线程，系统调度程序使用Sched_fork()函数。修改后，Copy_process()和Sched_fork()函数将收集到的任务执行信息反馈到本文的能耗模型和可靠性模型,用于分析所提出算法的能耗和可靠性。

数控系统每执行一次轨迹插补任务的周期为6 ms，每次插补计算的结果通过命令寄存器分若干次传送到伺服控制单元以控制机床各个坐标轴的位移，位置控制任务的周期为3 ms;每执行一次运动控制处理任务的时间为15 ms[6]。为了比较CSALPRM算法的效果，实验使用合成应用任务图。为此，使用任务图生成器(Task Graphs for Free,TGFF)[17]。TGFF基准套件包含合成任务图，每个任务的周期按照数控系统的实际周期产生，任务类型包括插补任务，加减速任务和运动控制任务。当处理器长时间没有任务调度时便进入睡眠模式并仅消耗空闲能耗。将上述TGFF生产的任务进行系统可靠性试验，其中可靠性通过式(6)计算任务出错率POF=(1-R(fi))。使用式(3)的参数λ0=10-6个故障/s和d=3对故障率进行建模[14]。因此，对应于最大和最小电压，故障率在10-6个故障/s至10-3个故障/s之间变化。为了考虑故障检测机制对能耗和可靠性的影响，使用文献中实现的两种类型的软件故障检测机制进行检测：

1)重度故障检测机制(称为+HFT)具有高故障检测开销和相对高的故障覆盖。对于这种情况，假设系统使用基于代码和数据冗余、一致性检查和控制流检查等多种故障检测机制[10-11]，为不同故障类型实现高故障覆盖。

2)轻故障检测机制(称为-LFT)具有相对低的故障检测开销以及低故障覆盖。对于这种情况假设系统使用较少的机制来减少检测覆盖，以降低故障检测开销的成本[18]。

4.1　能耗和可靠性分析

表2和图7分别显示了在八核处理器上执行每种类型任务的实验结果。从图中可知：CSALPRM不仅比+HFT更节能(平均15.18%)，还具有更少的任务出错率，即CSALPRM更可靠。与-LFT相比，CSALPRM虽然提供相对较少的节能(平均10.13%)，但CSALPRM可靠性更好。这是因为CSALPRM算法采用并行流水线技术，充分利用了多核处理器的优势，而且在保证可靠性上采用N模块冗余，相对+HFT和-LFT的错误检测机制更具优势，不但能够最大限度保证系统可靠性，而且在系统无错时回收多余的空闲时间降低能耗。

表2　不同任务下三种算法的出错率对比

4.2　处理器个数对能耗和可靠性的影响

从图8可以看出，在任务数不变的情况下，随着处理器个数的增加，3个算法的能耗均降低，这是因为处理器个数多，处理器处于空闲的机率增大，用于DVS调节处理器速度的空闲时间就多，因而消耗的能耗少，但CSALPRM算法的能耗始终最小，这是因为CSALPRM算法将周期性依赖任务转化为独立任务，可以实现更高层级的任务并行。并且充分利用了处理器的空闲时间用于降低能耗，同时对于长时间处于空闲的处理器采用DPM技术使其进入睡眠模式，进一步降低能耗。从图9可以看出，随着处理器个数的增加，任务出错率降低，系统可靠性增加，这是因为处理器个数越多，处理器用于容错阶段的时间就越多，从而增强了系统的可靠性。但所提出的CSALPRM算法，始终保持了较低的出错率，说明所提出的算法使用N模块冗余的优越性。

5　结束语

本文面向开放式数控系统研究基于国产CPU数控系统的低能耗和可靠性，提出一种两阶段调度算法来解决数控系统在多处理器上调度具有严格时序约束的周期性依赖任务，同时考虑了转换开销和通信开销。实现国产处理器下数控系统的高可靠性与低能耗的协同优化。提出基于粗粒度任务级软件流水线技术的DPDAGA算法，用于将定期依赖任务转换为基于重新定时技术的一组独立任务，该算法可以充分利用多核处理器的优势，将任务调度并行化，增强系统调度效率。考虑数控系统中任务加工过程可能出现的错误，基于DPDAGA算法基础上，提出了低能耗与可靠性协同优化调度算法CSALPRM。在CSALPRM中首先采用N模块冗余技术,实现系统的高可靠性，同一任务执行不同副本，并将执行结果进行多数投票，决定任务是否需要容错。其次使用DVS和DPM技术管理容错阶段所产生的空闲时间，并在运行时为任务分配动态空闲。该算法实现了数控系统的低能耗和可靠性之间的协同，增强了数控系统的整体可靠性，并且可以在支持DVS的多核处理器上使用，而不需要增加额外的硬件。下一步基于开放式数控系统，研究数控系统在多核处理器上的的混合任务低功耗调度算法。