一种基于数据质量的多处理器平台实时更新事务调度算法

白天，李国徽，申丽平



一种基于数据质量的多处理器平台实时更新事务调度算法

白天1, 2，李国徽1，申丽平2

(1. 华中科技大学计算机科学与技术学院，湖北武汉，430074；2. 湖南理工学院计算机学院，湖南岳阳，414000)

提出一种多处理器平台上基于数据质量的实时更新事务全局调度算法(MU-DA)。数据质量根据时态对象的无效程度来定义。算法通过合理地预分配各事务执行所需处理器资源以及动态控制更新实例的接纳和执行使系统数据质量最大化。研究结果表明：MU-DA算法在各种事务集负载下均能保证较高的数据质量；在高负载设置下，MU-DA算法的系统数据质量与用户事务质量均远比基准算法MU-D与MU-SA的高，能够很好地满足用户事务在数据实时性方面的要求。

信息物理融合系统；实时更新事务；数据质量；多处理器调度

信息物理融合系统(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 数据质量模型

考虑在(≥2) 个同构处理器上调度更新事务集。其中，事务负责更新实时数据对象O，可表示为(g(), V, w)；概率密度函数g()描述了执行时间的分布情况；V为O的时态有效期；w为O的权重，满足，w越大，O的重要程度越高。w可根据O在控制决策中所起的作用来定义。

定义1 实时数据对象O是有效的，或称为时态一致的，(其中，c为系统的当前时间，为O当前值的采样时间[13])。

多处理器平台上的调度策略可分为3类：基于任务分派的调度方法、全局调度方法与混合调度方法[11]。基于任务分派的调度方法预先为每个任务指定1个处理器，任务只能在指定的处理器上执行。全局调度方法允许任务在执行过程中从处理器1转移到处理器2上。混合调度方法通常使用某种策略将部分任务划分为子任务，并将子任务分配到多个处理器上执行。混合调度方法可视为基于任务分派的调度方法与全局调度方法的综合，但实现起来要比这2种方法复杂。本文使用全局方法来调度更新事务。

系统中的用户事务通常根据一部分时态对象的值来进行决策，系统应充分保证这些数据对象的有效性。令()表示用户事务(，为用户事务集)读取的时态对象集，Y表示()中的失效对象个数。给定失效对象数量阈值K与失效概率阈值P，聚集失效约束要求失效对象个数不少于K的概率应小于或等于P，即

2 基于数据质量的多处理器调度算法(MU-DA)

2.1 多处理器平台上的事务预分配时间确定

根据数据质量的定义，MU−DA算法需要确定各个事务的预分配执行时间。预分配时间的设置首先必须满足数据的时态一致性约束。即对于给定的，，能够为找到相对截止期D与周期T，满足以下条件：

算法1 temporal validity test for

Input: sensor transaction set

Output:DandTfor each

for=2 to

whileR≤V/2

D=R;

computeW(R);

endfor

computeRusing condition 2;

ifD=R

T=V−R, break;

endif

endwhile

ifR＞V/2

is unschedulable, return failure;

endif

endfor

事务预分配时间的设置还需要满足聚集失效约束(式(2))。式(2)涉及的计算。通常(即()中所含时态对象的数目)较小，可以直接计算。令表示的前个数据对象中至少有个失效的概率，则可得如下递推式：

在确保算法1执行成功和聚集失效约束得到满足的前提下，预分配时间的设置应使得尽可能地小。由于问题中的约束均非凸且约束的导数也难以获取，因此，基于梯度的优化方法难以奏效。这里利用模拟退火算法进行优化。传统的模拟退火算法只能处理无约束优化问题，为此，利用双序列方法[15]来处理约束。在具体进行优化之前，首先使用算法1判断在WCET下是否可行，若可行，则为1，无需进一步处理。令表示算法生成的解序列中最近的可行解所对应的，表示此解序列中最近的不可行解的总约束违反量。由下式给出：

在第次迭代中，算法根据当前解生成至多个新解。当生成的新解优于当前解(即新解可行且其对应的小于)时，此解被接受；否则，新解将以概率被接受。当新解可行时，设置为此解的与之差，否则，设置为此解的总约束违反量()与之差。当算法所接受的新解为可行解时，设置为新解的；否则，设置为。

2.2 接纳与执行控制策略

3 实验评价

这里通过实验对所提出的算法进行评价。现有的调度算法均为单处理器平台上的算法，与它们比较没有意义，为此，给出2种多处理器上的基准事务调度算法。第1种算法(MU-D)直接用WCET调度事务，通过将算法1中的替换为WCET即可实现。第2种算法(MU-SA)仍然采用文中方法确定事务的预分配时间，但系统在运行时不会接纳任何实际执行时间大于预分配时间的实例。

算法的主要性能指标包括系统数据质量(SD)与用户事务质量(UT)。若O在时间区间内的有效时间为L，则。若用户事务读取的所有时态对象均有效，则认为也是有效的。(其中，为成功执行的用户事务个数，M为有效事务个数)。此外，算法产生的更新负载也将在实验中进行比较。

实验的主要参数及设置见表1。更新实例的计算时间满足正态分布，其均值在[15, 25]内随机选取。在实验中，系统负载的变化通过更新事务数量的变化来实现。假定所有更新事务的权重均相同，用户事务的数目设置为3。以泊松分布来生成用户事务，每个事务均在中随机选取。K设定为，在[0.1,0.25]内随机选取。P设置为0.25，参数V与N都满足均匀分布。系统使用EDF策略来调度用户事务。

表1 主要参数及设置

处理器个数为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—MU−D；2—MU−SA；3—MU−DA。

为了进一步说明MU−DA接纳和执行控制策略的有效性，记录实验中MU−DA与MU−SA在截止期之前完成的实例数量，由此可得到相应的实例完成率。图2所示为两者完成率之差的变化情况。由图2可知：大于零且随事务数量的增加呈上升趋势。其原因是事务预分配时间将随事务数量的增加而减小，从而使得更多的实例被MU−SA拒绝，而MU−DA通过合理的选择进入系统的实例和控制当前实例的运行能够保证这些实例中的大部分在截止期前完成。

图2 n=2时完成率之差∆C

图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。

图3 n=2时用户事务质量QUT比较

图4所示为MU−SA与MU−DA产生的更新负载比较结果。由于当事务数量不大于140个时可使用WCET来调度事务集，因此，这2种算法的负载完全相同，故不在图中给出。由图4可知：MU−DA生成的负载在不同事务数量下均不比MU−SA的低；随着事务数量增加，这2种算法生成的负载均会增加。其原因是MU−DA接纳了更多的实例，从而使得其更新负载也相应增加。需要注意的是：MU−DA相对更高的负载也带来了更高的系统数据质量，从提高数据质量的角度来说MU−DA产生的负载是合理的。

图4 n=2时更新负载比较

当处理器数量为4和8个时，系统数据质量比较结果分别如图5(a)与5(b)所示。从图5可见：当处理器个数增加时，算法所支持的事务个数也随之增加，但这3种算法之间的相对性能并不改变；在中、低负载下(处理器个数为4时，事务数量不超过290个；处理器个数为8时，事务数量不超过580个)，3种算法均能确保SD为1；在高负载下，MU−DA的SD要比MU−SA的高。此外，处理器个数的增加使得MU−DA与MU−SA的SD下降速度变慢。上述设置下算法的用户事务质量数据与更新负载数据也分别与图3和图4所示的类似。除此之外，还考察了算法在处理器个数为16时的性能，结果也与上述实验结果类似。

(a) n=4; (b) 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,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.

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)

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.

cyber physical systems; real-time update transactions; quality of data; multiprocessor scheduling

10.11817/j.issn.1672-7207.2016.09.021

TP311

A

1672−7207(2016)09−3066−06

2015−11−12；

2016−01−25

国家自然科学基金资助项目(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

(编辑 陈灿华)