信息物理系统中基于保护阈值的实时调度算法研究*

周本海，姚大鹏

(沈阳工程学院计算机基础教学部,辽宁 沈阳 110136 )

1 引言

信息物理融合系统CPS(Cyber-Physical Systems)是一个以时间为关键属性的系统，实时性是重要的系统属性，CPS必须在限定时间内完成消息的发送和接收[1]。系统输出结果的正确性不仅取决于计算所形成的逻辑结果，还要取决于结果产生的时间。因此，对实时信息物理融合系统进行研究，进而增强它在事先定义的时间范围内识别和处理离散事件的能力、增强其处理和储存控制系统所需要的大量数据的能力，具有很大的研究意义。

目前，CPS中普遍采用基于优先级的抢占式调度方式，因为它在提高资源利用率和及时响应高优先级任务方面具有很强的优势。但是，在CPS系统中的某些特定的应用背景下，非抢占调度性能要优于抢占式调度，原因在于抢占式系统容易导致较低的系统吞吐率。而且，抢占式调度方式中高优先级任务抢占运行，不考虑当前任务的运行状态。如果被抢占任务即将完成，由于高优先级任务无条件地抢占，会导致低优先级任务被延期或者错过截止期，更重要的是，频繁的任务切换增加了系统的抖动，严重影响了CPS的实时性能。

所以，CPS特别需要一种抢占与非抢占结合的调度方式，进行合理而有效的实时任务调度。据此，本文建立了任务集的松弛时间与保护时间模型，提出了保护阈值的实时调度算法，有效地抑制了任务频繁切换产生的抖动对系统性能的影响，提高了系统的利用率与实时性能。

2 研究背景

CPS在医疗、智能交通以及军事等多个关键领域发挥着极其重要的作用，该类系统的典型特征是实时性，是指CPS必须保证所有实时任务在其截止期内完成。由于CPS对系统资源的限制非常严格，单纯的抢占式调度会造成任务切换次数过多，增大系统开销的问题，这将严重影响CPS的实时性能。如何在不降低系统可调度性的前提下尽量减少任务切换次数，已成为CPS环境下新的研究热点问题。

文献[2]给出了抢占阈值的实时调度模型,以离线的方式降低任务调度中抢占的次数。文献[3]在此基础上提出了一个优化标准，用来减少固定优先级调度的抢占开销。文献[4]通过为任务的抢占建立一个模型,将任务的启动时间作为一个调度参数,降低了任务的抢占次数,但模型的计算时间复杂度具有不确定性。文献[5]提出了针对就绪的周期任务队列的调度算法,优化了动态调度算法的抢占次数,但对于动态调度算法的时间复杂度较高,系统开销很大。文献[6]提出了抢占阈值的方法，适用于任务集不确定、优先级动态变化的实时系统。文献[7]提出一种按比例确定阈值的方法。文献[8]提出将优先级继承协议集成到抢占阈值调度中，优化了最坏情况下任务切换次数。文献[9]提出由任务特征参数决定的抢占阈值调度算法，并用云模型理论进行优化。文献[10]提出了基于DVS(Dynamic Voltage Scaling)的抢占阈值算法。然而，以上设计的阈值确定算法未能很好地解决系统的抖动现象，上下文切换次数仍然较多，任务截止错失率比较高，影响了系统的实时性能。

本文提出的基于保护阈值的CPS实时调度算法，能够有效地减少任务切换次数，有效地提高了系统的利用率与实时性能。

3 相关技术

3.1 CPS中实时任务模型

为了方便描述具体任务模型，下面给出讨论中将涉及到的任务及其有关参数的定义与表示。设一个有n个任务的任务集τ=(τ1,τ2,…,τi,…,τn)，它们的周期分别为T1,T2,…,Tn，每个周期内的最坏情况执行时间分别为C1,C2,…,Cn，相对截止期为D1,D2,…,Dn,对于第i(1≤i≤n)个周期任务taskpi，必须满足Ci≤Di≤Ti。处理机利用率表示任务集对处理器资源的占用程度，任务集τ的处理器利用率可以用如下公式可表示：

Figure 1 Task switching in three situations图1 三种情况下的任务切换

3.2 任务切换

CPS系统中的节点若采用非抢占式调度，则任务切换发生在当前任务运行结束时，其优势是避免了不必要的任务切换，系统开销小。缺点是高优先级任务有时被阻塞，直到低优先级任务运行结束。图1a中表示了非抢占的调度方式。相反，抢占式调度方式是当高优先级任务就绪时，立刻得到运行，剥夺正在执行的低优先级任务的运行时间(如图1b所示)。抢占式调度的优势是能够增强系统的可预测性，最小化任务的响应时延。但是，由于抢占导致的频繁任务切换，造成严重的系统资源浪费，影响实时性能。图1c表示了一种改进的抢占式调度方式，在保障高优先级任务的时限的基础上，最大化低优先级任务的执行时间，该种方式可以有效地减少任务切换次数，提高系统的可调度率。

4 保护阈值模型建立

在一组可调度的任务集中，我们采用RM调度方法对所有周期任务按优先级从高至低排序，即在任务集τ中，任务τi的优先级大于任务τj(1≤i

(1)

经整理得，

(2)

由此可知，如果一个任务集是可调度的，则Sp≥0，反之，Sp<0。

任务集τ中，按照任务的优先级排列，当任务数量大于或等于两个时，保护阈值模型如公式(3)所示：

Thresholdp=min({S2,…,Sp})

(3)

Thresholdp为被抢占任务的最大可继续执行时间，即高优先级任务的延迟时间[0,Thresholdp]内，任务集是可调度的。

5 基于保护阈值的CPS实时调度算法描述

根据松弛时间模型与保护阈值模型计算当前任务的剩余时间、高优先级任务的松弛时间以及保护阈值。当系统中有高优先级任务就绪时，判断低优先级任务是否可以继续执行。测试方法是：如果低优先级任务的剩余时间大于松弛时间，则不进行提升优先级的操作，高优先级任务进行抢占调度，任务切换次数加1；反之，提升当前任务的优先级至最高，直至执行完毕，恢复优先级，高优先级任务开始运行。通过上述描述，下面给出基于保护阈值的CPS实时调度算法。

算法基于保护阈值的CPS实时调度算法

初始化：CreateTasks( );//创建任务集

功能函数：Schedule( ) //任务调度

1. {if (τpis ready) //如果高优先级任务集就绪

2. {Compute (Thresholdp,Sp,Ri)

3. /*计算就绪高优先级任务的保护阈值，松弛时间，剩余时间*/

4. if(Ri

5. {{riseτipriority to CELLPRIO;

6. executeτp;}

7. else executeτp;

8. //剩余时间超过保护阈值，则运行高优先级任务

}}

9. else executeπi;/*无高优先级任务，则直接运行当前任务*/}

该算法使用的是固定任务集，即任务集的超周期长度取决于任务的个数。所以，松弛时间模型为静态模型。在计算任务的剩余时间与保护阈值的差值时，算法复杂度与高优先任务集的任务数量无关。即本文提出的基于预留的调度算法的执行时间不随问题规模n的增加而增长，创建任务集算法的时间复杂度为O(1)。

6 实验结果与分析

本文采用调度模拟器RTSIM(Real Time Simulation)[11]对本文提出的理论方法进行仿真验证，该模拟器可以仿真目前大多数的处理器结构，如单处理器、多处理器、CMP等多种体系结构。利用该模拟器，将本文的保护阈值实时调度算法在多处理器环境中进行仿真验证。在RTSIM上将本文的算法与目前较为流行的比例阈值和以继承协议为手段的降低任务切换次数的算法进行仿真比较。并且将上述三种方法应用在最优化的RM(Rate Monotonic)调度算法上，比较三种方法在CPS节点上在一个超周期内产生的任务抢占次数。如图2与图3所示，图中各点的值是100组任务集合的均值。

Figure 2 Effect of system utilization on task switch图2 系统利用率对任务切换次数的影响

Figure 3 Task swith comparison of the three algorithms图3 三种算法任务切换次数的比较

从图2可以看出，在任务数量固定的情况下，三种算法的任务切换次数均低于未做改进的调度方法，并且任务切换的均值也要低于原来方法。本文的算法在可调度的前提下，在[0.1，0.9]的利用率范围内，任务切换次数都要小于RM算法，平均值比RM算法低37.8%。图3表示本文的保护阈值的方法与比例阈值以及优先级继承协议算法的任务切换次数比较。可以得出，本文算法的任务切换次数要低于其他两种方法，并且任务切换的平均值分别低于22.7%与29.8%。

Figure 4 Task switches when task number equals to 20图4 任务数为20时的任务切换次数变化

Figure 5 Task switch comparison of the three algorithms when task number equals to 20图5 任务数为20时的三种算法任务切换次数的比较

将每组任务数量设置为20，在[0.1，0.9]的利用率范围内，图4表示任务切换次数都要小于RM算法，平均值比RM算法低35.9%。图5是本文的保护阈值的方法与比例阈值以及优先级继承协议算法的任务切换次数的比较。从图5可以得出，本文算法的任务切换次数要低于其他两种方法，并且任务切换的平均值分别低于18.7%与33.1%。

7 结束语

CPS中的关键属性为实时性，大多数算法采用了抢占式调度模式，而单纯的抢占方式容易导致频繁的任务切换，严重影响了CPS的实时特性。本文将抢占与非抢占的调度方式相结合，提出了一种基于保护阈值的实时调度算法。通过建立任务集的松弛时间与保护阈值模型，在可调度的前提下，最大化被抢占任务的执行时间，降低了任务切换频率。通过仿真实验结果表明，与抢占式调度的RM算法相比，本文算法有效地降低了任务的切换次数，增强了系统的实时性与可靠性。

[1] Wang Zhong-jie,Xie Lu-lu.Cyber-physical systems:A survey[J]. ACTA Automatica SINICA，2011,37(10):1157-1167.(in Chinese)

[2] MinSeong K,Andy W.Applying fixed-priority preemptive scheduling with preemption threshold to asynchronous event handling in the RTSJ [J].Concurrency and Computation:Practice and Experience, 2011,23(14):1609-1622.

[3] Ding Wan-fu, Guo Rui-feng, Qin Cheng-gang, et al. Preemption threshold scheduling algorithm with higher fault-tolerant priority[J].Journal of Software, 2011,22(12):2894-2904.(in Chinese)

[4] Keskin U.Exact response-time analysis for fixed-priority preemption-threshold scheduling[C]∥Proc of Emerging Technologies and Factory Automation (ETFA),2010:1-4.

[5] Chen Ying-ge,Wang Xiao-ying,Zhao Hai,et al.Ready queue optimization research in task scheduling[J]. Journal of System Simulation, 2006,18(4):877-882. (in Chinese)

[6] Evans B G, Baughan K. Vision of 4G[J]. Electronics and Communication Engineering Journal, 2000, 12(6):293-303.

[7] Wu Wei, Qian Liang,Xu You-yun. Sampling frequency compensation algorithm for OFDM systems and its FPGA implementation[J]. Telecommunication Engineering, 2007, 47(4):32-36.(in Chinese)

[8] Chen Xiu-ping,Zeng Xiao-yang.Optimal synchronization scheme for CMMB receivers[J]. Computer Engineering, 2010, 36(21):95-97.(in Chinese)

[9] Stefan A. OFDM carrier and sampling frequency synchronization and its performance on stationary and mobile channels[J]. IEEE Transactions on Consumer Electronics, 2000, 46(3):438-441.

[10] Liu Yang. Integrating preemption threshold to fixed priority DVS scheduling algorithms[C]∥Proc of Embedded and Real-Time Computing Systems and Applications, 2009:165-171.

[11] http://rtsim.sssup.it/.

附中文参考文献：

[1] 王中杰，谢璐璐.信息物理融合系统研究综述[J]. 自动化学报, 2011, 37(10):1157-1167.

[3] 丁万夫，郭锐锋，秦承刚，等.容错优先级提升的抢占阈值容错调度算法[J].软件学报，2011,22(12):2894-2904.

[5] 陈英革,王小英，赵海，等.任务调度过程中就绪队列的优化研究[J].系统仿真学报, 2006,18(4):877-882.

[7] 吴炜, 钱良, 徐友云. OFDM 系统采样中补偿算法及其FPGA 实现[J]. 电讯技术, 2007, 47(4):32-36.

[8] 陈秀平, 曾晓洋. CMMB 接收机同步优化方案[J]. 计算机工程,2010, 36(21):95-97.