DOI: 10.11817/j.issn.1672-7207.2016.09.021
一种基于数据质量的多处理器平台实时更新事务调度算法
白天1, 2，李国徽1，申丽平2
(1. 华中科技大学 计算机科学与技术学院，湖北 武汉，430074；
2. 湖南理工学院 计算机学院，湖南 岳阳，414000)
摘要：提出一种多处理器平台上基于数据质量的实时更新事务全局调度算法(MU-DA)。数据质量根据时态对象的无效程度来定义。算法通过合理地预分配各事务执行所需处理器资源以及动态控制更新实例的接纳和执行使系统数据质量最大化。研究结果表明：MU-DA算法在各种事务集负载下均能保证较高的数据质量；在高负载设置下，MU-DA算法的系统数据质量与用户事务质量均远比基准算法MU-D与MU-SA的高，能够很好地满足用户事务在数据实时性方面的要求。
关键词：信息物理融合系统；实时更新事务；数据质量；多处理器调度
中图分类号：TP311 文献标志码：A 文章编号：1672-7207(2016)09-3066-06
Quality of data based scheduling for real-time update transactions on multiprocessor platforms
BAI Tian1, 2, LI Guohui1, SHEN Liping2
(1. College of Computer Science and Technology, Huazhong University of Science and Technology,
Wuhan 430074, China;
2. College of Computer Science, Hunan Institute of Science and Technology, Yueyang 414000, China)
Abstract: A quality of data (QoD) aware algorithm MU-DA was proposed to globally schedule the real-time update transactions on multiprocessors. The QoD measures the degree of invalidity of temporal data objects. To maximize the QoD, the algorithm pre-allocates resources of processors to update transactions, and then judiciously admits and schedules the update instances in the runtime. The results show that the proposed algorithm can guarantee high data quality under different system workloads. In particular, the system’s QoD and user transactions’ quality are much better than those of the baseline algorithms (MU-D and MU-SA) under high workloads, thus it can satisfy the data timeliness requirements of user transactions.
Key words: cyber physical systems; real-time update transactions; quality of data; multiprocessor scheduling
信息物理融合系统(cyber physical system,CPS)是在环境感知的基础上，通过计算、通信和控制能力的紧密结合来实现物理与计算过程深度融合的智能系统[1-2]。在CPS中，受监控的外部环境实体由实时数据对象(又称时态对象)来表示。数据对象反映了实体的当前状态，其采样和更新由实时更新事务负责。系统应使用合理的策略来调度执行更新事务以保证数据对象的有效性，否则外部物理过程的变化将无法得到及时响应。现有的更新事务调度算法主要包括More-Less(ML)，DS-FP与基于早期截止期优先策略(EDF)的算法[3-10]。这些算法都是基于单处理器平台来设计的，且采用了确定性的调度策略。其中，ML与基于EDF的算法采用周期性任务模型，两者分别使用截止期单调策略(DM)与EDF策略来调度事务。DS-FP采用非周期性任务模型，在确保数据时态一致性的基础上尽量推迟实例的开始时间。鉴于多核处理器在性能、功耗、可靠性等方面的优势，研究多核(多处理器)平台上的更新事务调度问题十分必要。尽管多处理器实时任务调度问题在近年来得到了广泛研究[11]，但这些研究均没有考虑数据的有效性约束，因此，不能直接用于更新事务的调度。另一方面，在视频监控等CPS中，事务的最坏执行时间(WCET)一般比较长(远超过大多数实例的实际执行时间)，采用确定性的调度策略将降低算法的调度成功率，使得算法在许多环境下无法有效地维护数据的时态一致性。确定性的调度策略也会造成资源过量分配，从而给系统中其他类型事务的执行带来不利影响。XIONG等[12]提出了基于服务质量的调度算法来解决此问题。但该算法只是针对ML而设计的，因此，只能用于单处理器平台，且算法没有考虑用户事务所读取数据的聚集失效约束。本文首先给出一种综合考虑单个数据对象的有效性及数据集上聚集失效约束的数据质量模型，然后，在此模型基础上给出一种多处理器平台上的事务调度算法。
1 数据质量模型
考虑在n (n≥2) 个同构处理器上调度更新事务集
。其中，事务
负责更新实时数据对象Oi，可表示为(gi(t), Vi, wi)；概率密度函数gi(t)描述了执行时间的分布情况；Vi为Oi的时态有效期；wi为Oi的权重，满足
，wi越大，Oi的重要程度越高。wi可根据Oi在控制决策中所起的作用来定义。
定义1 实时数据对象Oi是有效的，或称为时态一致的，
(其中，tc为系统的当前时间，
为Oi当前值的采样时间[13])。
多处理器平台上的调度策略可分为3类：基于任务分派的调度方法、全局调度方法与混合调度方 法[11]。基于任务分派的调度方法预先为每个任务指定1个处理器，任务只能在指定的处理器上执行。全局调度方法允许任务在执行过程中从处理器P1转移到处理器P2上。混合调度方法通常使用某种策略将部分任务划分为子任务，并将子任务分配到多个处理器上执行。混合调度方法可视为基于任务分派的调度方法与全局调度方法的综合，但实现起来要比这2种方法复杂。本文使用全局方法来调度更新事务。
若使用WCET时
可被算法A调度，则用户在任何时刻都能访问到有效的数据。否则，考虑为中事务的执行预先分配CPU资源，其中的预分配执行时间为
。假定此时可被A调度，
表示实例
无法成功执行时给Oi带来的失效时间，
为
的实际执行时间，
为
的开始时间。令
，为不小于的概率。则为
的概率为
，其值为0的概率为
。这里假定当
超过时系统不接纳。在实际运行过程中，根据当前的事务执行情况，系统可能会选择接纳并执行。
给定时间窗口W，事务在W内的最长可能数据失效时间为
(其中，
与
分
别为在W之前开始的最后1个和W之内开始的最后1个实例的序号)。为了提高用户事务在W内访问到有效Oi的概率，
的期望值
应尽量减小。此外，还需考虑不同对象的重要程度。为此，定义系统的数据质量
如下：
(1)
系统中的用户事务通常根据一部分时态对象的值来进行决策，系统应充分保证这些数据对象的有效性。令R (T)表示用户事务T(
，
为用户事务集)读取的时态对象集，YT表示R(T)中的失效对象个数。给定失效对象数量阈值KT与失效概率阈值PT，聚集失效约束要求失效对象个数不少于KT的概率
应小于或等于PT，即
(2)
2 基于数据质量的多处理器调度算法(MU-DA)
2.1 多处理器平台上的事务预分配时间确定
根据数据质量的定义，MU-DA算法需要确定各个事务的预分配执行时间。预分配时间的设置首先必须满足数据的时态一致性约束。即对于给定的
，
，能够为
找到相对截止期Dk与周期Tk，满足以下条件：
1) 
且
；
2) 
。
条件1)确保了所维护数据对象Ok的时态一致性，条件2)确保了多处理器平台上的可调度性[14], 其中
为的响应时间，
为
在长度为的区间内的负载上界。可由文献[14]中的式(4)计算得到。增大Di将导致增大，不利于找到的有效截止期；此外，Di增大也会导致与低优先级事务更新负载增大，不利于系统中用户事务的有效执行。因此，Di的取值应可能地小。算法1给出了事务截止期和周期的计算方法。当算法1返回失败时，无法满足时态一致性约束。
算法1 temporal validity test for
Input: sensor transaction set Г
Output: Dk and Tk for each 
, 
;
for k=2 to m
;
while Rk≤Vk/2
Dk=Rk;
for each 
compute Wi(Rk);
endfor
compute Rk using condition 2;
if Dk=Rk
Tk=Vk-Rk, break;
endif
endwhile
if Rk＞Vk/2
Г is unschedulable, return failure;
endif
endfor
事务预分配时间的设置还需要满足聚集失效约束(式(2))。式(2)涉及
的计算。通常
(即R(T)中所含时态对象的数目)较小，可以直接计算。令
表示T的前i个数据对象中至少有j个失效的概率，则可得如下递推式：
(3)
当i＜j时，
。
， 
。由此可得到
，即，共需计算
个概率。当较大时，根据马尔可夫不等式，有
。故当
时，解必然满足聚集失效约束，无需计算，否则，利用式(3)计算，由此可减小计算开销。
在确保算法1执行成功和聚集失效约束得到满足的前提下，预分配时间的设置应使得
尽可能地小。由于问题中的约束均非凸且约束的导数也难以获取，因此，基于梯度的优化方法难以奏效。这里利用模拟退火算法进行优化。传统的模拟退火算法只能处理无约束优化问题，为此，利用双序列方法[15]来处理约束。在具体进行优化之前，首先使用算法1判断在WCET下是否可行，若可行，则为1，无需进一步处理。令
表示算法生成的解序列中最近的可行解所对应的，
表示此解序列中最近的不可行解的总约束违反量。由下式给出：
(4)
当不可调度时，及比优先级低的事务的周期与截止期均无法由算法1获得，因此，这些事务的约束违反量也无法获取。为此，给这些事务分别赋予1个虚拟的约束违反量。为了充分体现的不可调度性，对于
(l≥k)，设置其截止期与周期均为Vl/2，并根据条件2) 计算Ri。的虚拟约束违反量为
。
在第k次迭代中，算法根据当前解生成至多N个新解。当生成的新解优于当前解(即新解可行且其对应的小于)时，此解被接受；否则，新解将以概率
被接受。当新解可行时，设置
为此解的与之差，否则，设置为此解的总约束违反量(
)与之差。当算法所接受的新解为可行解时，设置为新解的；否则，设置为。
2.2 接纳与执行控制策略
确定后，系统将进行事务实例的接纳控制和调度执行。事务
(k＜i)相对于实例的平均抢占时间
为
(5)
其中：
为
内完整的实例个数；这里
为实例的绝对截止期；
为单个完整实例的平均执行时间；
为内最后1个实例的平均执行时间。此实例可能有一部分在之后执行。
(6)
(7)
(8)
其中：
；
与
分别为
在
和
内的概率。在
中用
代替L即得到
。
。为了减小运行时间，可在调度开始前计算。由于调度序列的周期性，只需计算
个即可。令
表示的实例
在t时刻的剩余执行时间。若的实际执行时间大于，则只考虑的剩余时间。多处理器平台上的接纳条件为
当用完后，将被挂起。系统使用1个队列来管理所有挂起实例。实例按
由大到小排列。当系统空闲时，位于队列头的实例将被唤醒继续执行。此外，当
未知时，可在系统运行初期使用WCET来调度事务并记录下各实例的实际执行时间，据此可构造出相应的直方图来近似表示。
3 实验评价
这里通过实验对所提出的算法进行评价。现有的调度算法均为单处理器平台上的算法，与它们比较没有意义，为此，给出2种多处理器上的基准事务调度算法。第1种算法(MU-D)直接用WCET调度事务，通过将算法1中的替换为WCET即可实现。第2种算法(MU-SA)仍然采用文中方法确定事务的预分配时间，但系统在运行时不会接纳任何实际执行时间大于预分配时间的实例。
算法的主要性能指标包括系统数据质量(QSD)与用户事务质量(QUT)。若Oi在时间区间L内的有效时间为Li，则
。若用户事务T读取的所有时态对象均有效，则认为T也是有效的。
(其中，M为成功执行的用户事务个数，Mv为有效事务个数)。此外，算法产生的更新负载也将在实验中进行比较。
实验的主要参数及设置见表1。更新实例的计算时间满足正态分布，其均值
在[15, 25]内随机选取。在实验中，系统负载的变化通过更新事务数量的变化来实现。假定所有更新事务的权重均相同，用户事务的数目设置为3。以泊松分布来生成用户事务，每个事务均在中随机选取。KT设定为
，
在 [0.1,0.25]内随机选取。PT设置为0.25，参数Vi与NT都满足均匀分布。系统使用EDF策略来调度用户事务。
表1 主要参数及设置
Table 1 Parameters and settings
处理器个数为2时3种算法的系统数据质量比较见图1。由图1可知：当事务个数不超过140时，3种算法的系统数据质量都为1，其原因是在此设置下，直接使用WCET就能够成功调度事务集，因此，数据在任何时刻都是有效的；当事务个数超过140时，事务集的负载也较高，此时，MU-D几乎无法调度任何事务集，因此，其系统数据质量也不再存在，而MU-SA与MU-DA使用较小的预分配时间来调度事务集，因此，仍然能保证一定的系统数据质量。这2种算法的系统数据质量都随事务数量的增加而下降，但MU-SA的下降幅度远比MU-DA的大，这使得MU-DA的系统数据质量一直比MU-SA的高。例如，当事务个数为240时，前者比后者高约0.14。原因是MU-DA的接纳和执行控制策略使得系统能够成功地执行一部分在MU-SA中被拒绝的实例，从而使得MU-DA的数据有效性时间比MU-SA的长。
图1 n=2时系统数据质量QSD比较
Fig. 1 Comparison of system data quality QSD when n=2
为了进一步说明MU-DA接纳和执行控制策略的有效性，记录实验中MU-DA与MU-SA在截止期之前完成的实例数量，由此可得到相应的实例完成率。图2所示为两者完成率之差
的变化情况。由图2可知：大于零且随事务数量的增加呈上升趋势。其原因是事务预分配时间将随事务数量的增加而减小，从而使得更多的实例被MU-SA拒绝，而MU-DA通过合理的选择进入系统的实例和控制当前实例的运行能够保证这些实例中的大部分在截止期前完成。
图2 n=2时完成率之差△C
Fig. 2 Difference of completion ratio △C when n=2
图3所示为分别使用MU-SA与MU-DA调度更新事务时用户事务质量的比较结果。从图3可以看出：MU-DA下的用户事务质量在不同的事务数量下均要比MU-SA的高，例如，当事务数量为200个时，前者比后者高约0.2；随着事务数量增加，这2种算法下的用户事务质量也随之降低，且MU-SA的下降幅度要比MU-DA的大。其原因在于当事务数量超过140个时，MU-DA的系统数据质量一直要比MU-SA的高(见图1)。系统数据质量越高，用户事务在某一时刻访问到有效数据的概率越大，因而，用户事务本身有效的概率也会越高。当事务数量不到140个时，2种算法的系统数据质量都为1(见图1)，因此，2种算法下的用户事务质量也都为1。
图4所示为MU-SA与MU-DA产生的更新负载比较结果。由于当事务数量不大于140个时可使用WCET来调度事务集，因此，这2种算法的负载完全相同，故不在图中给出。由图4可知：MU-DA生成的负载在不同事务数量下均不比MU-SA的低；随着事务数量增加，这2种算法生成的负载均会增加。其原因是MU-DA接纳了更多的实例，从而使得其更新负载也相应增加。需要注意的是：MU-DA相对更高的负载也带来了更高的系统数据质量，从提高数据质量的角度来说MU-DA产生的负载是合理的。
图3 n=2时用户事务质量QUT比较
Fig. 3 Comparison of user transaction quality QUT when n=2
图4 n=2时更新负载比较
Fig. 4 Comparison of update workload when n=2
当处理器数量为4和8个时，系统数据质量比较结果分别如图5(a)与5(b)所示。从图5可见：当处理器个数增加时，算法所支持的事务个数也随之增加，但这3种算法之间的相对性能并不改变；在中、低负载下(处理器个数为4时，事务数量不超过290个；处理器个数为8时，事务数量不超过580个)，3种算法均能确保QSD为1；在高负载下，MU-DA的QSD要比MU-SA的高。此外，处理器个数的增加使得MU-DA与MU-SA的QSD下降速度变慢。上述设置下算法的用户事务质量数据与更新负载数据也分别与图3和图4所示的类似。除此之外，还考察了算法在处理器个数为16时的性能，结果也与上述实验结果类似。
图5 n=4与n=8时系统数据质量QSD比较
Fig. 5 Comparison of system data quality QSD when n=4 and n=8
4 结论
1) 给出了一种数据质量模型。在模型中不仅考虑了单个时态对象的有效性，而且考虑了用户事务读取的时态对象集上的聚集失效约束。
2) 提出了一种基于全局方法的多处理器更新事务调度算法。该算法通过处理器资源的预先分配和事务实例的动态接纳执行控制来最大化数据质量。算法在不同的事务集负载下都能提供较高的数据质量，能够很好地满足用户事务对于数据实时性的要求。
3) 多处理器平台上的实时任务调度算法除全局方法外，还包括基于任务分派的方法与混合方法。如何利用这2类方法进行数据质量的维护有待进一步研究。
参考文献：
[1] RAJKUMAR R, LEE I, SHA L, et al. Cyber-physical systems: the next computing revolution[C]// Proceedings of the 47th ACM/IEEE Design Automation Conference (DAC). Anaheim, CA, USA: IEEE, 2010: 731-736.
[2] 何积丰. 信息物理融合系统[J]. 中国计算机学会通讯, 2010, 6(1): 25-29.
HE Jifeng. Cyber-physical systems[J]. Communications of the China Computer Federation, 2010, 6(1): 25-29.
[3] XIONG M, RAMAMRITHAM K. Deriving deadlines and periods for real-time update transactions[J]. IEEE Transactions on Computers, 2004, 53(5): 567-583.
[4] XIONG M, HAN S, LAM K Y, et al. Deferrable scheduling for maintaining real-time data freshness: algorithms, analysis, and results[J]. IEEE Transactions on Computers, 2008, 57(7): 952-964.
[5] HAN S, CHEN D J, XIONG M, et al. Schedulability analysis of deferrable scheduling algorithms for maintaining real-time data freshness[J]. IEEE Transactions on Computers, 2014, 63(4): 979-994.
[6] XIONG M, HAN S, CHEN D J, et al. DESH: overhead reduction algorithms for deferrable scheduling[J]. Real-Time Systems, 2010, 44(1/2/3): 1-25.
[7] LI J J, XIONG M, LEE V C S, et al. Workload-efficient deadline and period assignment for maintaining temporal consistency under EDF[J]. IEEE Transactions on Computers, 2013, 62(6): 1255-1268.
[8] WANG J T, HAN S, LAM K Y, et al. Maintaining data temporal consistency in distributed real-time systems[J]. Real-Time Systems, 2012, 48(4): 387-429.
[9] WANG J T, LAM K Y, HAN S, et al. On co-scheduling of periodic update and application transactions with fixed priority assignment for real-time monitoring[C]// IEEE 26th International Conference on Advanced Information Networking and Applications (AINA). Fukuoka, Japan: IEEE, 2012: 253-260.
[10] HAN S, LAM K Y, WANG J T, et al. On Co-scheduling of update and control transactions in real-time sensing and control systems: algorithms, analysis, and performance[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(10): 2325-2342.
[11] ROBERT I D, ALAN B. A survey of hard real-time scheduling for multiprocessor systems[J]. ACM Computing Surveys, 2011, 43(4): 1-44.
[12] XIONG M, LIANG B Y, LAM K Y, et al. Quality of service guarantee for temporal consistency of real-time transactions[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(8): 1097-1110.
[13] RAMAMRITHAM K. Real-time databases[J]. Distributed and Parallel Databases, 1993, 1(2): 199-226.
[14] BERTOGNA M, CIRINEI M. Response time analysis for global scheduled symmetric multiprocessor platforms[C]// Proceedings of the 28th IEEE International Real-Time Systems Symposium. Tucson, USA: IEEE, 2007: 149-160.
[15] OZDAMAR L. A dual sequence simulated annealing algorithm for constrained optimization[C]// Proceedings of the 10th WSEAS International Conference on Applied Mathematics. Dallas, Texas, USA, 2006: 557-564.
(编辑 陈灿华)
收稿日期：2015-11-12；修回日期：2016-01-25
基金项目(Foundation item)：国家自然科学基金资助项目(61173049)；湖南省自然科学基金资助项目(2015JJ6044) (Project(61173049) supported by the National Natural Science Foundation of China; Project(2015JJ6044) supported by the Natural Science Foundation of Hunan Province)
通信作者：白天，讲师，从事实时数据库及信息物理融合系统研究；E-mail: baitiannobel@163.com
