0 引言
信息物理系统(cyber-physical systems，CPS)由计算机算法控制或监控物理实体，是一种计算资源和物理资源的统一体[1]，在实际生活和工程中具有非常广泛的应用前景[2-5].关于CPS的研究进展有助于让我们的世界变得更加快速(如自主避免碰撞)、更加精确(如机器人手术和纳米容忍制造)、更加高效(例如医疗监护和交付)[6-7].
许多现代的CPS系统，尤其是工业自动化系统，要求多个计算系统的动作以较高的速率执行，并且与特定的设计更紧密地同步.时间是CPS中计算机和物理系统共享的共同实体，正确地连接它对于CPS的完美功能是至关重要的[8]. CPS中计算机与物理系统之间的交互是通过任务作为中间件实现的[9]，是一种任务驱动的应用.当前大多数系统的处理是在任务发生时间确定的基础上进行的，一般都假设任务流中任务的发生时间是精确的.下一代信息物理系统需要提供信息组件(软件和硬件)的无缝协调，以实现能够动态响应系统需求的自主应用.在监控时，由检测到的任务来触发系统相对应的动作，数据的时间准确性和及时性直接影响系统结果的准确性.然而在此过程中，由于数据的漏读、监控系统采样时间粒度不匹配、分布式系统任务采集时间戳时钟不同步等原因，会使得任务发生时间不确定[10].文[11]针对不确定任务流采用了一种复杂任务处理方法USCEP(uncertain stream complex event processing)，文[12]对时间不确定任务流进行剪枝操作，简化执行顺序概率的计算，但它们在对任务进行实时调度时没有考虑任务优先级.
实时性是CPS系统中一个极其重要的特征，实时任务处理的首要目标是执行任务调度，以期在任务截止时间前完成尽可能多的任务，并实现最佳的系统性能[13].文[14]改进了EDF(earliest dealine first)调度算法，通过缩短和延长任务截止期，提出了两种改进的EDF软实时动态调度算法.文[15]考虑到LSF(least slack first)算法会导致任务之间频繁切换而增大系统开销的问题，提出了基于抢占阈值分配的LSF调度算法.文[16]根据任务的截止期和空余执行时间分析任务执行的紧迫性，以任务执行的紧迫性，确定实时任务优先级动态分派策略.文[17]提出了一种CPS中基于保护阈值的实时调度算法，针对分布式环境中的抢占调度方式，建立保护阈值模型，解决了抢占式调度容易影响系统实时性的问题.文[18]提出了一种周期/非周期事件混合容错调度算法，针对开放网络的环境，基于PTIDES(programming temporally-integrated distributed embedded systems)语义解决了CPS内部周期事件和非周期事件共存的混合优先级调度问题.但它们都没有解决任务发生时间不确定的问题.由于发生时间不确定，任务到达的准确时间就不能确定，由此也无法确定任务的调度顺序.
目前，针对时间不确定任务调度算法的研究成果很少.为了满足系统结果的准确性和系统执行效率，本文综合考虑CPS系统中任务发生时间点区间、截止时间与空余时间三个参数，提出了一种针对时间不确定任务流的动态实时调度算法.首先生成时间不确定任务流所有可能的执行顺序，然后用剪枝算法对时间不确定任务流的时间点区间进行简化，同时根据任务截止时间和空余时间得到任务执行的紧迫度，以任务执行紧迫度分派优先级进行动态实时调度，保证了发生时间不确定任务的准确调度及尽可能的确保系统执行效率.
1 模型描述假设CPS实时任务系统的实时任务集合表示为T，Ti表示集合中第i个任务.
定义1 时间不确定任务(time uncertain task，TUT).本文的时间不确定任务特指发生时间不确定的任务，任务的格式表示为(ES，EI，TPC：[lower，upper]，p：TPC→[0, 1])，其中ES表示任务的来源；EI表示任务的ID号；TPC：[lower，upper]表示时间点的区间，是任务有可能发生的时间，lower代表任务的最早发生时间，upper代表任务的最晚发生时间；(p：TPC→[0, 1])是时间点区间内任务在各个时刻可能发生的概率区间[19].
时间不确定任务流(time uncertain task flow，TUTF).由一系列定义1中的时间不确定任务组合而成的任务序列，表示为TUTF=(T1，T2，…，Tn)，其下标也即定义1任务格式中的任务ID号EI.
定义2 概率任务(probability task，PT).它是由时间不确定任务依据其所有可能发生的时刻结合其概率转化而成的任务，概率任务的格式表示为(EI，T，p).其中，p表示不确定任务在T时刻发生的概率.例如，不确定任务(A，[8:08，8:10]，UD)，其中UD(uniform distribution)代表任务在时间点区间内均匀分布，可将该时间不确定任务转换为3个概率任务，分别为(A，8:08，1/3)、(A，8:09，1/3)和(A，8:10，1/3)，概率任务也可用小写字母u表示.
概率任务流(probability task flow，PTF).由一系列定义2中的概率任务组合而成的序列，表示为PTF=(u1，u2，…，un)，下标也即任务格式中任务ID号EI.
| 符号 | 含义 |
| (1) Ei | 表示任务Ti的执行周期 |
| (2) Hi | 表示任务Ti的理论执行时间 |
| (3) Si | 表示任务Ti发生时间，是任务发生时间点区间内的一个取值 |
| (4) RDi | 表示任务Ti的相对截止时间，RDi＜Ei且Hi＜RDi |
| (5) Ri | 表示任务Ti放行并准备执行的时间 |
| (6) Fi | 表示任务Ti执行完成的时间 |
| (7) ADi | 表示任务Ti的绝对截止期，ADi=Ri+RDi |
| (8) ti | 表示系统的当前时刻 |
| (9) t | 表示任务已执行时间 |
| (10) Tiub(task initial upper bound) | 表示任务的初始上界，即任务可能发生的最晚的时刻，也即TPC：[lower，upper]中的upper |
| (11) Tilb(task initial lower bound) | 表示任务的初始下界，即任务可能发生的最早的时刻，也即TPC：[lower，upper]中的lower |
| (12) Tvub(task va-lid upper bound) | 表示任务的有效上界，即对任务进行剪枝处理后任务的上界.对于一组时间点不确定任务流，如果任务组合顺序不同，有效上界的值也会相应的变化，但其仍代表某一组合顺序下，允许该任务发生的最晚的时刻 |
| (13) Tvlb(task va-lid lower bound) | 表示任务的有效下界，即对任务进行剪枝处理后任务的下界.对于一组时间点不确定任务流，如果任务组合顺序不同，有效下界的值也会相应的变化，但其仍代表某一组合顺序下，允许该任务发生的最早的时刻 |
时间不确定任务流在某个时间区间内，会存在不同的任务执行顺序.可将这一时间区间内的任务组合序列全部排列出来，经剪枝处理后将较长的时间区间缩短，简化对任务流不同组合序列的概率计算.
2.1.1 剪枝算法本文处理的对象是发生时间不确定的任务流，运用剪枝算法对发生时间不确定任务进行剪枝，其目的是为了简化某个组合序列的概率求解.通过对任务发生时间区间剪枝的方法，可以减去该组合序列中每个任务不可能发生的时间点，从而将长时间区间减为短时间区间.对于全体任务所有可能的组合序列而言，对每种组合序列都进行剪枝操作，能够有效地缩短时间区间，为概率的计算提供很大的便捷.
时间不确定任务的发生时间是一个集合，假设每个任务在时间点区间内发生的概率满足均匀分布.即任务Ti在某时刻发生的概率表示为
|
(1) |
在实时系统中，当一个任务到达时，若其到达时间不确定，是一个区间内的取值，则该任务的发生时间区间就会与其它任务的发生时间区间有重叠的区域.所有任务组合排列形成所有可能的执行顺序后，要计算每种顺序可能的执行概率，由于每个任务的发生时间区间各不相同，有长有短，这就加大了概率计算的复杂性.因此，在概率计算前，对每种可能的执行顺序进行剪枝处理，从而可以达到简化求解概率的复杂性.
对于一个可能的组合序列p(u1，u2，…，un)，Ti是该序列下的一个任务，其中i指的是这个任务在此序列下的序列号，若以此组合序列作为执行顺序，用剪枝算法对该顺序进行处理，需要对此顺序遍历2次.
第1次遍历，确定任务的有效下界Tvlb.如果Ti是这个组合序列中的第一个任务，也即i=1，那么该任务的有效下界表示为
|
(2) |
如果Ti不是这个组合序列中的第1个任务，那么该任务的有效下界表示为
|
(3) |
第2次遍历，确定任务的有效上Tvub.如果Ti是这个组合序列中的最后一个任务，也即i=n，那么该任务的有效上界表示为
|
(4) |
如果Ti不是这个组合序列中的最后一个任务，那么该任务的有效上界表示为
|
(5) |
若一个任务的Tvub小于该任务的Tvlb，则可以排除该组合序列，此执行顺序不可能发生，概率为0.
任务a(a，[1, 5])、b(b，[2, 5])、c(c，[2, 4])、d(d，[2, 6])、e(e，[4, 7])，假设这组任务流按照a、b、c、d、e的顺序执行，图 1~图 3为在该执行顺序下对任务时间点区间的剪枝过程，图中横坐标表示任务可能发生时刻，纵坐标表示各任务名称，其中图 1表示任务有效下界Tvlb的确定，图 2表示任务有效上界Tvub的确定，图 3表示任务新的时间点区间.
|
| 图 1 任务有效下界的确定 Figure 1 Determine the valid lower bound of task |
|
| 图 2 任务有效上界的确定 Figure 2 Determine the valid upper bound of task |
|
| 图 3 任务新的时间点区间 Figure 3 Task new time interval |
对任务流可能执行顺序的剪枝过程如算法1所示.
算法1 任务流执行顺序的剪枝算法PruneProcess(ScheduleSeq SS，TimeInter TI，Time[])
输入：时间不确定任务流ScheduleSeq SS=(u1，u2，…，un)，任务的时间点区间TimeInter TI=[lower，upper]，系统当前时间Time[].t=ti.
输出：确定新的时间点区间的不确定任务流SS.
1. for each task Ti in SS do//确定每个任务的有效下界
2.{
3. TimeInter TI=Ti. [lower，upper]；
4. Time[].t=new Time[]；
5. if(i=1) //如果该任务是组合序列中的第1个任务
6. TI.lower=Ti.lower；
7. else
8. TI.lower=max(Ti-1.lower+1，Ti.lower)；
9. Ti.lower=TI.lower；
10.}
11.for each task Ti in SS do//确定任务的有效上界
12.{
13. TimeInter TI=Ti.[lower，upper]；
14. Time[].t=new Time[]；
15. if(i=n) //如果该任务是组合序列中的最后一个任务
16. TI.upper=Ti.upper；
17. else
18. TI.upper=max(Ti+1.upper-1，Ti.upper)；
19.Ti.upper=TI.upper；
20.}
21.Return SS；
2.1.2 概率求解对任务流所有组合序列得到的执行顺序都进行剪枝处理后计算每个顺序的执行概率，找出任务流中概率最大的任务，作为初始执行序列里最先执行的任务，以此类推，按概率递减的形式生成任务调度的初始执行顺序.如在一个时间区间内，实时系统里到达a、b、c三个任务，那么这3个任务可能的执行序列有6种：abc、acb、bac、bca、cab、cba，分别对所有的序列都进行剪枝处理.若有序列在剪枝过程中存在Tvub＜Tvlb，这种情况是不可能发生的，概率直接取0；若没有这种情况，则计算所有可能序列的执行概率Pabc、Pacb、Pbac、Pbca、Pcab、Pcba.因此，对于这3个任务，任务a先被执行的概率为Pa=Pabc+Pacb，任务b先被执行的概率为Pb=Pbac+Pbca，任务c先被执行的概率为Pc=Pcab+Pcba.比较a、b、c的执行概率，按概率从大到下排序得到的就是这组任务流的初始执行顺序.假设Pb>Pa>Pc，那么这个由3个任务组成的时间不确定任务流的初始执行顺序为bac.
针对2.1.1节中的5个任务，一共有A55=120种可能的执行序列，现计算abcde这种执行序列的概率，剪枝处理后任务表示为a(a，[1, 2])、b(b，[2, 3])、c(c，[3, 4])、d(d，[4, 6])、e(e，[5, 7]). 图 4表示任务流各时间点概率，假设概率满足平均分布.这组任务流必须在时间点1~7之间完成执行，若任务e发生在时刻7，那么其余4个任务要在时刻7以前以abcd的顺序发生，若任务d发生在时刻6，那么其余3个任务要在时刻5以前以abc的顺序发生，以此类推，直至只有一个任务a发生.计算过程是一个迭代过程，即：
|
|
| 图 4 任务流各时间点概率 Figure 4 Probability of each time of task flow |
其中，
|
按照这个流程，求解其余各个顺序在某时刻前发生的概率，这是一个循环的递归过程.
2.2 优先级分派方法CPS实时系统中，任务调度一个重要的目标是在任务截止时间前，系统能尽可能多地让任务完成执行，这就要求在CPS实时系统中能有一个好的调度方法.目前，大多数基于任务时间约束的调度方法，一般都是在任务发生时间确定的情况下进行的.本节分析任务的发生时间不确定、任务截止时间及空闲时间来确定任务执行的紧迫性，从而确定优先级分派.
定义3 执行价值(execution value，EV).任务执行完成需要的时间与任务空闲时间(任务等待服务的时间)之比定义为任务的执行价值，记为ϑi.
任务Ti的执行价值表示为
|
(6) |
其中，
|
(7) |
|
(8) |
为了确保任务Ti在截止时间前完成执行，任务Ti需即刻执行的紧迫程度被称作Ti执行的紧迫性[21]，记为μi.若任务Ti在ti时刻已经执行了时间t，那么此时任务Ti的执行紧迫性μi(t)表示为
|
(9) |
其中，q为影响执行价值ϑi对执行紧迫性μi的因子.若q的值取1，那么此时任务执行的紧迫性是一个常数.若q的值取大于1，那么由幂函数的性质，μi的值会随任务空闲时间的增加而增加.
假设在ti时刻，任务Ti已执行了t个单位时间.其Ti放行后的累积等待时间为x.
因为ADi-ti=RDi-x-t(0≤x＜RDi-t，0≤t＜Hi)，其中ADi-ti表示Ti的空余时间，所以式(9)可以改写为
令
当实时任务Ti开始放行时，其已执行时间t=0，空闲时间为RDi，此时Ti执行的紧迫性最小，取值为
在CPS实时系统中，有运行(running)、就绪(ready)、挂起(suspended)、休眠(dormant)四种状态的任务.运行任务(running task)表示在目前执行周期内开始执行但尚未执行完成的任务；就绪任务(ready task)表示在目前执行周期内没有得到系统执行权因而处于就绪等待的任务；挂起任务(suspended task)表示在目前执行周期内已经开始执行，但由于被其它高优先级任务抢占而处于就绪等待的任务；休眠任务(dormant task)表示已执行完成或因错误被清除的任务，正在等待下一个执行周期，在目前执行周期内不会被执行.处于运行状态的任务，其执行紧迫性为开始执行时的紧迫性，执行期间维持恒定值.处于就绪或挂起的任务，其执行紧迫性会随任务等待时间的增加而增加.而休眠任务，其不在执行周期内，因此不考虑紧迫性.
在一组时间不确定任务流中，若任务Ti在ti时刻处于运行状态，且已执行t个单位时间.那么此时任务Ti在ti时刻的动态优先级(dynamic priority)称为DP(Ti)，表示为
|
(10) |
CPS实时任务系统中，休眠(dormant)任务的执行周期还没有开始，故基于动态优先级的时间不确定任务流的实时调度，仅仅考虑运行(running)任务、就绪(ready)任务、挂起(suspended)任务.
本文基于任务发生时间不确定、任务截止时间和任务空闲时间提出了一种针对时间不确定任务流的动态实时调度算法.对于一组发生时间不确定的任务流，对其所有可能执行的组合序列进行剪枝简化后计算出所有组合序列的可能执行概率，由此得出每个任务的执行概率，按概率由大到小依次递减的顺序得到的便是这组任务流初始的执行顺序.对初始的执行顺序以任务执行的紧迫性作为动态优先级进行调度.
当任务调度时，首先基于任务发生时间计算每个任务的动态优先级，然后找出处于就绪状态和挂起状态任务中优先级最大的任务，将此任务的优先级与处于运行状态任务的优先级进行比较，并做出相应调度.
若在ti时刻，任务T1在其发生时间区间TPC:[lower，upper]内的时刻S1开始执行，且已经运行了t1个单位时间，其中0≤t1＜H1，H1为任务T1的理论执行时间，由于任务T1是运行状态的任务，在ti时刻其优先级为开始执行时的优先级，影响因子q取1.因此，T1的优先级为
综上分析，对时间不确定任务流的动态实时调度过程如算法2所示.
算法2 时间不确定任务流动态调度算法DynamicSchedule(int n，TaskSet T，int q)
输入：任务流个数n，任务流集合T，动态优先级的影响因子q.
输出：任务流调度成功.
1. T=[T1，T2，…，Tn]；
2. A=perms(T)； //获取完整的任务流组
3. for each sequence Ai in A do
//剪枝并计算每种序列的概率
4. {
5. PruneProcess(Ai，TimeInter TI，Time[])；
6. PAi←Calculate the execution probability of the Ai；}
7. for each task Ti in T do
//计算每个任务的执行概率
8. {P(i)←Calculation the execution probability of Ti through the all PAi；}
9. for l=1:n
//将所有任务按概率从大到小排序
10.{
11.for m=2:n
12.{
13. if P(m)>P(m-1)
14. Temp=Tm；
15. Tm=Tm-1；
16. Tm-1=Temp；}}
17.After shorting，the initial execution order is T′；
18.for at regular intervals do
19.{
20. DP(T′1)=q^((H1-t)/(S1+H1+R1-ti))；
21. for each T′i in T′ do
22. {Calculate the DP(T′i)；}
23. DP(max)←Find the maximum in DP；
24. if DP(max)≥DP(T′1)
25. T′1 stop running，the biggest priority is to get executive power；
26. else
27. T′1 continue to run；}
28.return 0；
该动态调度算法将剪枝策略和动态优先级策略相结合，对发生时间不确定任务流通过剪枝概率法得到初始执行顺序，这样可以保证将无法调度的不确定任务流的调度确定化.在此基础上，实时考虑各个任务执行的紧迫性，动态地对任务运行进行调度.该算法有效地解决了发生时间不确定任务流的调度，并且考虑到各个任务的执行紧迫性，给予各个任务优先级指派，从而有效提高系统调度结果的准确性和执行效率.
例如有任务流N(N，[1, 6])、M(M，[2, 6])、L(L，[4, 8])，图 5为任务流时间点区间.由3个任务组成的任务流共有6种可能的执行序列MNL、MLN、NML、NLM、LMN、LNM，分别对这6种执行序列进行剪枝处理同时计算每种序列的可能执行概率. MNL序列下，M.Tvlb=2，M.Tvub=4，N.Tvlb=3，N.Tvub=5，L.Tvlb=4，L.Tvub=8，每个任务的有效下界都小于有效上界，因此，该任务是有可能发生的，经计算该序列的发生概率为p(MNL)=0.526，同理可得p(MLN)=0.051，p(NML)=0.015，p(NLM)=0.147，p(LMN)=0(任务的有效下界大于有效上界，这种情况是不可能发生的)，p(LNM)=0.003.知道了每种可能执行序列的概率，由此可求出每个任务的概率. pM=p(MNL)+p(MLN)=0.577，pN=p(NML)+p(NLM)=0.162，pL=p(LMN)+p(LNM)=0.003，pM>pN>pL，所以这组任务流的初始执行顺序为MNL.
|
| 图 5 任务流时间点区间 Figure 5 Time interval of task flow |
在计算任务优先级时，固定因子q=1，这组任务流的各参数取值如表 2所示.假设在系统时间ti=2时刻，任务M发生，按初始执行顺序开始运行，当M运行2个单位时间，ti=4时，计算M的优先级为DP(M)=1，此时处于就绪状态的2个任务N和L，任务N在ti=2时刻发生，任务L在ti=4时刻发生，在当前系统时间为ti=4时计算这两个任务的优先级，此时任务N准备执行时间RN=2，任务L准备执行时间为0.计算N和L的优先级得DP(N)=1.2，DP(L)=0.8，将优先级更大的任务N与任务M的优先级进行比较.显然DP(N)>DP(M)，因此任务N满足抢占任务M的要求，任务N获得执行权开始运行，而任务M则记录下当前已运行的各个数据后处于挂起状态，等到任务N运行完后继续运行.
| 任务 | TCP:[lower，upper] | Hi | RDi |
| N | [1, 6] | 3 | 9 |
| M | [2, 6] | 3 | 7 |
| L | [4, 8] | 4 | 12 |
本文实验基于Matlab语言实现，实验中的任务是通过一个任务流产生器产生的，发生任务的时间区间是随机的[22]且满足lower＜upper，任务的H、RD和E等时间参数也是随机产生的且要求H＜RD＜E.
实验1 文[12]对时间不确定任务流用剪枝简化后进行概率求解，以此确定任务初始执行顺序.为比较本文提出的任务流动态实时调度算法，另外提出一种基于任务流中间值排序的调度方法进行对比，中间值排序方法，也即，取任务发生时间区间的中间值
|
| 图 6 任务流数量不同时的调度准确率 Figure 6 Accuracy in different task flow amount |
固定任务动态优先级的影响因子q=1，任务流不确定时间区间稳定在时间段长度为5的情况下，任务流发生时间区间中各个时刻的概率分布为均匀分布.
从图 6可分析得到，在2种处理方法下，任务调度的准确率随任务流数量的增多呈下降趋势，最终趋于一个相对稳定的值.很明显可以看到，用剪枝概率法结合动态优先级的调度准确率要高于中间值排序法结合动态优先级的调度准确率，且调度准确率的差值达到了60%左右.当任务流数量比较大的时候，剪枝概率法处理时间不确定任务流结合动态优先级的实时调度算法的准确率可以稳定在87%上下.
实验2 基于实验1中两种对时间不确定任务流处理方法，图 7表示，任务流不确定时间区间长度不同时，算法动态调度任务的准确率.
|
| 图 7 时间区间长度不同时的调度准确率 Figure 7 Accuracy in different time interval length |
固定任务动态优先级的影响因子q=1，任务流数量取500，任务流发生时间区间中各个时刻的概率分布为均匀分布.
从图 7分析得到，两种处理方法下，任务调度的准确率随时间区间长度的增大而降低，因为时间区间长度越小，任务在不确定时间区间内发生时刻越集中，因而调度的准确率也就越高，同样，用剪枝概率法结合动态优先级的算法调度准确率仍然较高，系统调度结果的准确性越好.
实验3 固定任务动态优先级的影响因子q=1，任务流不确定时间区间稳定在时间段长度为5的情况下，任务流发生时间区间中各个时刻的概率分布为均匀分布.
图 8表示任务流数量不同时，采用和不采用剪枝概率法处理时间不确定任务后再进行动态调度对CPU处理时间的影响.采用剪枝概率法时，CPU处理时间包含对不确定任务流进行剪枝操作以及概率求解的时间.分析可得，任务流数量越大，CPU处理时间会越长，但是当任务流数量比较大时，采用了剪枝概率法，CPU处理时间明显要比不采用该方法少很多，由此验证剪枝概率法对于发生时间不确定任务流的调度效果比较好.
|
| 图 8 剪枝概率法对CPU处理时间的影响 Figure 8 The effect of pruning probability method on CPU processing time |
实验4 由任务优先级的计算公式(10)可知，任务发生时间不确定对任务的优先级也会产生影响.固定任务动态优先级影响因子q=1，图 9表示任务流不确定时间区间长度对任务优先级的影响.
|
| 图 9 时间区间长度对优先级的影响 Figure 9 Effect of time interval length on priority |
分析可得，当任务的发生时间区间长度越大时，任务在区间内取值的范围就大，从而使得任务执行紧迫性会越小，导致任务的优先级也会越小，因此任务发生时间区间长度与任务优先级呈反比关系.
实验5 任务流不确定时间区间稳定在时间段长度为5的情况下，任务流发生时间区间中各个时刻的概率分布为均匀分布，任务流数量取500个，图 10表示任务动态优先级影响因子q在不同取值时对系统性能影响的分析.
|
| 图 10 因子q变化时系统性能分析 Figure 10 System performance analysis of factor q change |
图 10(a)所示，基于任务执行紧迫性来分派任务优先级，从而调度任务时，运行任务与非运行任务可能会发生交替，哪个任务的优先级大就运行哪个任务，若目前正在运行任务的优先级小于非运行状态下某个任务的优先级，则非运行状态下的任务将抢占运行任务，获得系统执行权.由实验数据可得，当任务优先级影响因子q的取值增大时，任务抢占的次数会增加，最终会趋于一个相对恒定值.同时，由于运行任务与非运行任务频繁切换，极易使某些任务不能得到充足的CPU运行时间而错过截止时间，如图 10(b)所示，当任务优先级影响因子q的取值增大时，任务截止时间错失率也会随之增大，同样最终也会趋于一个相对恒定的值.
4 结论CPS实时系统中的任务，存在发生时间不确定的特性，在任务调度时，应保证系统效益，考虑任务动态的执行紧迫性.本文综合考虑任务发生时间区间、截止时间和空闲时间三个因素，提出了面向信息物理系统发生时间不确定任务流的动态实时调度算法.通过仿真实验对比，验证了本文提出的算法与其它方法相比，在不同情况下进行任务调度时能够实现比较高的准确率，且CPU处理时间相对较短，同时减少任务截止时间的错失率，有效确保系统调度结果的准确性以及系统执行效率.
| [1] | Lee E A. Cyber-physical systems: Design challenges[C]//Proceedings of the 200811th IEEE Symposium on Object Oriented Real-Time Distributed Computing. Piscataway, N. J. USA, IEEE, 2008: 363-369. |
| [2] |
汪德星.
关于CPS应用的学术讨论[J]. 电力系统自动化, 2012, 36(15): 73–77, 82.
Wang D X. Academic discussion on CPS applications[J]. Automation of Electric Power Systems, 2012, 36(15): 73–77, 82. |
| [3] |
施陈博, 苗权, 陈启鑫.
基于CPS的能源互联网关键技术与应用[J]. 清华大学学报:自然科学版, 2016, 56(9): 930–936, 941.
Shi C B, Miao Q, Chen Q X. Key technologies and applications of energy internet based on CPS[J]. Journal of Tsinghua University:Natural Science Edition, 2016, 56(9): 930–936, 941. |
| [4] |
巴宇, 刘娆, 李卫东, 等.
CPS及其考核在北美与国内的应用比较[J]. 电力系统自动化, 2012, 36(15): 63–72.
Ba Y, Liu R, Li W D. CPS and its assessment are compared in north america with domestic applications[J]. Automation of Electric Power Systems, 2012, 36(15): 63–72. |
| [5] |
张雨, 董云卫, 冯文龙, 等.
一种面向CPS的控制应用程序协同验证方法[J]. 软件学报, 2017, 28(5): 1144–1166.
Zhang Y, Dong Y W, Feng W L, et al. Co-verification approach to control software program for CPS[J]. Journal of Software, 2017, 28(5): 1144–1166. |
| [6] | 温景容, 武穆清, 宿景芳. 信息物理融合系统[J]. 自动化学报, 2012, 38(4): 507–517. |
| [7] | Baheti R, Gill H. Cyber-physical systems[M]//The Impact of Control Technology. Piscataway, NJ, USA:IEEE, 2011:161-166. |
| [8] | Dimitriadou K, Papaemmanouil O, Diao Y. Explore-by-example: An automatic query steering framework for interactive data exploration[C]//ACM SIGMOD International Conference on Management of Data. New York, NJ, USA: the ACM, 2014: 517-528. |
| [9] | Talcott C. Cyber-physical systems and events[M]//Software-Intensive Systems, LNCS 5380. Berlin, Germany:Springer, 2008:101-115. |
| [10] | Zhang H, Diao Y, Immerman N. Recognizing patterns in streams with imprecise timestamps[J]. Proceedings of the VLDB Endowment, 2010, 3(1): 244–255. |
| [11] |
曹科宁, 李仁发, 张小明, 等.
面向CPS复杂任务流的不确定性研究[J]. 计算机工程与科学, 2015, 37(3): 415–421.
Cao K N, Li R F, Zhang X M, et al. Research on uncertain CEP for CPS[J]. Computer Engineering & Science, 2015, 37(3): 415–421. |
| [12] |
刘红蕾, 李芳芳, 谷峪, 等.
面向时间不确定事件流的嵌套查询处理技术[J]. 计算机学报, 2017, 40(10): 2271–2285.
Liu H L, Li F F, Gu Y, et al. Processing nested query over event streams with uncertain timestamps[J]. Chinese Journal of Computers, 2017, 40(10): 2271–2285. DOI:10.11897/SP.J.1016.2017.02271 |
| [13] | Haritsa J R, Carey M J, Livny M. Value-based scheduling in real-time database systems[J]. Vldb Journal, 1993, 2(2): 117–152. DOI:10.1007/BF01232184 |
| [14] |
李琦, 巴巍.
两种改进的EDF软实时动态调度算法[J]. 计算机学报, 2011, 34(5): 943–950.
Li Q, Ba W. Two improved EDF dynamic scheduling algorithms in soft real-time systems[J]. Chinese Journal of Computers, 2011, 34(5): 943–950. |
| [15] |
金宏, 王宏安, 王强, 等.
改进的最小空闲时间优先调度算法[J]. 软件学报, 2004, 15(8): 1116–1123.
Jin H, Wang H A, Wang Q. An improved least-slack-first scheduling algorithm[J]. Journal of Software, 2004, 15(8): 1116–1123. |
| [16] |
夏家莉, 陈辉, 杨兵.
一种动态优先级实时任务调度算法[J]. 计算机学报, 2012, 15(12): 2685–2694.
Xia J L, Chen H, Yang B. A real-time tasks scheduling algorithm based on dynamic priority[J]. Chinese Journal of Computers, 2012, 15(12): 2685–2694. |
| [17] |
周本海, 姚大鹏.
信息物理系统中基于保护阈值的实时调度算法研究[J]. 计算机工程与科学, 2015, 37(2): 226–230.
Zhou B H, Yao D P. A real-time scheduling algorithm based on protection threshold for CPS[J]. Computer Engineering & Science, 2015, 37(2): 226–230. |
| [18] |
高鹏. 基于PTIDES的信息物理系统事件调度算法研究[D]. 徐州: 中国矿业大学, 2016. Gao P. Study on the scheduling algorithm of CPS events based on PTIDES[D]. Xuzhou: China University of Mining and Technology, 2016. |
| [19] | Li F F, Liu C, Yu G. Scheduling algorithm of events with imprecise timestamps for CPS[J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(6): 887–896. |
| [20] | Fohler G, Lennvall T, Buttazzo G. Improved handling of soft a periodic tasks in offline scheduled real-time systems using total bandwidth server[C]//Proceedings of the 8th IEEE International Conference on Emerging Technologies and Factory Automation. Piscataway, NJ, USA: IEEE, 2001: 151-157. |
| [21] | Haritsa J R, Livny M, Carey M J. Earliest deadline scheduling for real-time database systems[C]//Proceedings of the 12th IEEE Real-time Systems Symposium. Piscataway, NJ, USA: IEEE, 1991: 232-243. |
| [22] | Zhang H, Diao Y, Immerman N. Recognizing patterns instreams with imprecise timestamps[J]. Information Systems, 2013, 38(3): 1187–1211. |