黄迎春, 邓庆绪
东北大学 信息科学与工程学院，辽宁 沈阳 110819
收稿日期：2015-07-28
基金项目：国家自然科学基金资助项目 (61472072)；国家重点基础研究发展计划项目 (2014CB360509)。
作者简介：黄迎春 (1976-), 男, 辽宁瓦房店人, 东北大学博士研究生;
邓庆绪 (1970-), 男, 河南南阳人, 东北大学教授, 博士生导师。

摘要：传统实时系统性能分析以最差情况下执行时间 (worst-case execution time, WCET) 作为主要输入，导致分析过于保守.针对实时系统设计时预留冗余过大的问题，建立了以到达事件类型、数量和分布为决策变量，包括工作量曲线 (workload curves)、逆工作量曲线 (inverse workload curves)、工作量比率曲线 (workload ratio curves) 在内的实时系统可变工作量模型，给出了相关计算方法.基于可变工作量模型分析了其在混合调度中的应用，结果表明：采用可变工作量模型和算法可显著减少任务所需的执行工作量，降低了实时系统的资源需求.
关键词：可变工作量模型实时系统形式化方法工作量曲线最差情况下执行时间
A Variable Workload Model and Algorithm for Real-Time Systems
HUANG Ying-chun, DENG Qing-xu
School of Information Science & Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: HUANG Ying-chun, E-mail: welcomspring@163.com
Abstract: The traditional performance analysis of real-time systems relied on the input variable of worst-case execution time, which turned to be too pessimistic.Aiming at the problem of remarkably redundant design in real-time, a new model to characterize variable workload was created including workload curves, inverse workload curves and workload ratio curves. In the proposed model, event type, number and distribution were used as decision-variable, and relevant algorithm was proposed to solve the above model. In addition, the realistic applications were analyzed in mix scheduling based on VWM (variable workload model). The result indicates that the VWM can remarkably reduce execution workload of tasks, thus reducing the resource requirement of real-time systems.
Key Words: variable workload modelreal-time systemformal methodworkload curveworst-case execution time
在传统的实时系统形式化性能分析过程中，为了能够估计出系统的最差性能，从而作为系统设计的依据，往往采用最差情况下执行时间 (worst-case execution time, WCET) 作为周期任务 (periodic task)、非周期任务 (aperiodic task) 的执行时间度量.使用WCET进行实时系统性能分析的优点，一是简化了性能分析问题的形式化建模与求解，二是能够保证系统的硬实时性 (hard real time)；其缺点是过分悲观估计了实时系统性能分析的计算与存储能力，使得系统设计过程中所需的计算资源 (如处理器主频)、通信资源 (如网络带宽) 以及存储资源 (如cache尺寸) 冗余过大，提高了系统成本.由于最差情况下的执行需求几乎不可能在实际运行中发生^[1]，因此使用基于WCET的单调速率调度策略导致大量的剩余时间^[2].
为了解决上述问题，一些研究者^[3-4]提出了采用随机变量表示任务执行时间，但这种方法往往由于错过时间限而无法应用于硬实时系统.文献[5]首先提出了系统属性间隔 (system properties interval，SPI) 的建模方法，针对不同的任务采用不同的模型计算资源消耗，文献[6-10]进一步提出了可变执行需求的建模方法.本文正是在此基础上以事件数量作为自变量改进了可变工作量建模方法：首先给出了包括工作量函数、工作量曲线和逆工作量曲线在内的可变工作量建模方法，并详细分析论述了模型的相关原理与性质；其次给出了工作量曲线和逆工作量曲线的计算方法和混合调度模式下的可变工作量计算方法.与基于仿真的随机性方法相比，本文给出的方法由于采用了确定性的建模方法，既可保证分析的硬实时性，又引入了可变工作量的概念，改进了传统硬实时分析中仅考虑WCET分析方法的局限.
1 可变工作量建模1.1 工作量函数定义1?工作量函数：设τ是在单处理器上执行的任务，{E₁, E₂, …}是其中包括的事件序列，T(E_i) 代表事件E_i的类型，B(t), W(t) 分别代表类型为t的事件在最好情况下的执行时间和最差情况下的执行时间，则最好情况下的工作量函数定义为

(1)

式 (1) 表示从第j个事件开始的连续k个事件所消耗的处理器资源下限；定义当k=0时，γ^b(j, 0)=0.同理，最差情况下的工作量函数定义为

(2)

式 (2) 表示从第j个事件开始的连续k个事件所消耗的处理器资源上限；定义当k=0时，γ^w(j, 0)=0.
定理1?最好情况下工作量函数的最大值：
最小值：
定理2?最差情况下工作量函数的最大值：
最小值：
定义2?工作量函数的确界：由定理1和定理2，任意连续k个事件所需处理器资源的下确界定义为

(3)

上确界定义为

(4)

1.2 工作量曲线定义3?工作量曲线：任意连续k个事件所需的处理器资源的最小工作量曲线定义为

(5)

同理可定义任意连续k个事件所需的处理器资源的最大工作量曲线为

(6)

以下两个定理给出工作量曲线的性质.
定理3?工作量曲线是严格递增函数.
定理4?最好情况下单事件执行工作量BCET (1)=γ^l(1)，最差情况下单事件执行工作量BCET (1)=γ^u(1).
定义4?工作量比率曲线：由定义2和定义3，任意连续k个事件的最小工作量比率曲线定义为

(7)

最大工作量比率曲线定义为

(8)

工作量比率曲线反映了工作量函数确界与工作量曲线之间的比率关系，它们反映了实时系统实际所需的处理器资源与形式化分析所需的最小处理器资源及最大处理器资源之间的关系，0 < ρ^l(k), ρ^u(k)≤1.
1.3 逆工作量曲线定义5?逆工作量曲线：工作量曲线的反函数.最小逆工作量曲线定义为

(9)

表示当工作量不小于e时，事件所发生的最少数量.同理，最大逆工作量曲线定义为

(10)

表示当工作量不大于e时，事件所发生的最多数量.
逆工作量曲线的性质如下：
性质1? γ^u(k)≤e≡γ^u-1(e)≥k;
性质2? γ^l(k)≥e≡γ^l-1(e)≤k;
性质3? γ^l-1(γ^l(k))=k;
性质4? γ^u-1(γ^u(k))=k;
性质5? γ^l(γ^l-1(e))≥e;
性质6? γ^u(γ^u-1(e))≤e;
性质7? γ^l-1(e)≥γ^u-1(e).
性质1~6的证明从略，这里只证明性质7.
证明?采用反证法.
首先假设γ^l-1(e) < γ^u-1(e) 成立.令
k₁=γ^l-1(e), k₂=γ^u-1(e)，则k₁ < k₂；进一步，由定理3可知γ^l(k₁) < γ^l(k₂)≤γ^u(k₂).
以下根据逆工作量曲线的定义推理.根据γ^l-1(e) 的定义，可得
根据γ^u-1(e) 的定义，可得
所以γ^l(k₁)≥γ^u(k₂).
至此可见由逆工作量曲线定义得出的结论与反证法最初假设推出的结论矛盾，因此性质7得证.
2 工作量曲线与逆工作量曲线的算法2.1 算法1——工作量曲线计算方法算法1的流程图如图 1所示.
图 1(Fig. 1)

图 1 工作量曲线算法Fig.1 Workload curves algorithm

算法1基于定义1、定义3、定理1、定理2得出.算法1的时间复杂度为O(k×(n-k+1))，若k?n，则算法时间复杂度退化成O(n).
2.2 算法2——逆工作量曲线计算方法算法2的流程图如图 2所示.
图 2(Fig. 2)

图 2 逆工作量曲线算法Fig.2 Inverse workload curves algorithm

算法的时间复杂度为O(n×k×(n-k+1))，若k?n，则退化成O(n²).算法2是在算法1的基础上基于定义5及其性质得出.
算法1和算法2中事件到达模型一般有两种确定方法，一种是根据实际系统的经验数据，另一种是根据系统严格的形式化说明^[7-8].
2.3 仿真计算针对上述建模及计算方法，给出仿真计算示例.图 3给出一个长度为10的三种类型事件到达序列，以及各类型事件的WCET和BCET.
图 3(Fig. 3)

图 3 具有不同类型的事件序列Fig.3 Event sequence with different types of events

针对图 3所示的事件序列，采用算法1和算法2分别计算相应的工作量曲线和逆工作量曲线，如图 4所示.可以看出：由于γ^l(10)=14，所以当工作量e≥15时，不存在最小工作量曲线的逆，算法返回值为-1；由于γ^u(10)=37，所以当工作量e≥37时，最大工作量曲线的逆等于10.
图 4(Fig. 4)

图 4 工作量曲线和逆工作量曲线Fig.4 Workload curves and inverse workload curves (a)—工作量曲线；(b)—逆工作量曲线.

3 应用分析如图 5所示，假设一个单处理器系统同时处理3个任务，其中：任务1为周期性任务，周期为1 ms，输入事件类型为A，B，C；任务2为周期性任务，周期为2 ms，输入事件类型为D，E；任务3为非周期任务，采用选举服务器 (polling server) 进行调度，选举周期为4 ms，非周期任务的到达时间t∈[3,5]，输入事件类型为F；该处理器针对上述3个任务整体采用RMS (rate-monotonic scheduler) 调度.应用本文建立的可变工作量模型及计算方法可计算所需的处理资源数量.
图 5(Fig. 5)

图 5 单处理器调度任务Fig.5 Single-processor scheduling task

在计算图 5所示的工作量过程中，由于各任务的周期不同，应用可变工作量曲线计算处理器的总工作量时，需将单位时间各任务到达的数量与所需的处理器资源之间的关系进行统一计算，否则由于各事件发生频率的不同导致无法进行工作量的累积.下面给出一种计算不同事件频率工作量的累积算法.
算法3 ?累积不同事件频率工作量.
符号说明：WCET_i，BCET_i分别为最坏、最好情况下任务i(i=1, 2, …, q) 的执行时间；P_i为任务i的周期 (任务i的优先级按照降序排列).
算法描述：
1)?采用算法1分别计算任务i的最小工作量曲线γ_i^l、最大工作量曲线γ_i^u；
2)?计算单事件累积的最小工作量BCET (k) 和最大工作量WCET (k)，计算公式为
3)?计算多任务累积的最小工作量曲线γ^l(k) 和最大工作量γ^u(k)，计算公式为
4)?计算多任务累积的最小工作量比率曲线ρ^l(k) 和最大工作量比率曲线ρ^u(k)，计算公式为
下面假设各个任务到达的事件类型服从均匀分布，给出了时间间隔为1 s (10 000个事件) 的仿真结果，如图 6所示.
图 6(Fig. 6)

图 6 混合调度工作量曲线和工作量比率曲线Fig.6 Workload curves and workload ratio curves in mix scheduling (a)—工作量曲线；(b)—工作量比率曲线.

从图 6中可以看出，实际所需的处理器资源明显小于最差情况下所需的处理器资源，ρ^u≈0.5，代表了实际所需的资源大约为最差情况下所需资源的一半，同理，在最好情况下可得出相似的结论.
4 结语本文以实时系统事件序列发生的类型、数量以及分布作为决策变量建立了可变工作量模型，给出了包括工作量曲线、逆工作量曲线、工作量比率曲线等相关定义，并推导出相关性质、定理和计算方法；进一步分析了选举服务器和单调速率混合调度下的资源需求.与传统的WCET模型相比，可变工作量模型更加复杂，但更符合离散事件系统的实际情况.计算与分析结果表明：可变工作量模型可显著减少对系统处理器资源的计算需求，对于实时系统、嵌入式系统的分析与设计具有指导意义.
参考文献

[1]	Shin Y, Choi K.Power conscious fixed priority scheduling for hard real-time systems[C]// The 36th ACM/IEEE Conference on Design Automation Conference.Singapore :IEEE, 1999:134-139.
[2]	Liu C, Layland J. Scheduling algorithms for multi-programming in hard real-time environment[J].Journal of the ACM, 1973, 20(1): 46–61.DOI:10.1145/321738.321743
[3]	Tia T, Deng Z, Shankar M, et al.Probabilistic performance guarantee for real-time tasks with varying computation times[C]//Real-Time Technology and Applications Symposium.Chicago, 1995:164-173.
[4]	Bernat G, Colin A, Petters S M.WCET analysis of probabilistic hard real-time systems[C]// IEEE Real-Time Systems Symposium.Tucson, 2002:279-288.
[5]	Ziegenbein D, Richter K, Ernst R, et al. SPI—a system model for heterogeneously specified embedded systems[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2002, 10(4): 379–389.DOI:10.1109/TVLSI.2002.807767
[6]	Maxiaguine A, Kunzli S, Thiele L.Workload characterization model for tasks with variable execution demand[C]// Design, Automation and Test in Europe Conference and Exhibition.Paris, 2004:1040-1045.
[7]	Wandeler E.Modular performance analysis and interface-based design for embedded real-time systems[D].Zurich:Swiss Federal Institute of Technology, 2006.
[8]	Wandeler E, Thiele L.Characterizing workload correlations in multi processor hard real-time systems[C]// Real-Time and Embedded Technology and Applications Symposium.San Francisco, 2005:46-55.
[9]	Hausmans J, Geuns S, Wiggers M, et al.Two parameter workload characterization for improved data flow analysis accuracy[C]// Real-Time and Embedded Technology and Applications Symposium.Philadelphia, 2013:117-126.
[10]	McKee D, Webster D, Xu J.Enabling decision support for the delivery of real-time services[C]// High Assurance Systems Engineering.Daytona Beach Shores, 2015:60-67.