一种动态传感器事务调度算法

白 天, 杨志和, 曾涤凡

(湖南理工学院 计算机学院, 湖南 岳阳 414006)

一种动态传感器事务调度算法

白 天, 杨志和, 曾涤凡

(湖南理工学院 计算机学院, 湖南 岳阳 414006)

实时数据库系统必须合理调度执行传感器事务以维护实时数据对象的有效性. 现有算法不能很好地解决最坏执行时间远大于平均执行时间时的事务调度. 提出一种动态传感器调度算法DS-FP-DA. 算法预先确定各事务在DS-FP调度下的预留时间. 在系统运行过程中, 算法通过接纳控制机制来选择合适的实例执行. 实验表明, 算法能有效降低数据的加权平均无效时间.

实时数据库; 传感器事务; 加权平均无效时间

实时数据库领域的一项重要研究内容是时态数据(又称实时数据)的有效性维护. 时态对象记录了现实世界实体的当前状态, 其值会随着时间的推移而变得无效. 数据的时态一致性约束要求时态对象的再采样更新必须在其当前值所对应的时态有效期结束前完成, 以保证系统对外部环境变化的及时响应[1,2].

通常时态对象的值由传感器事务更新. 现有的传感器事务调度算法主要包括 Half-Half(HH)、More-Less(ML)与DS-FP[3～6]. HH与ML采用周期性任务模型来调度传感器事务. ML设置事务的周期大于或等于其截止期, 且两者之和等于数据的时态有效期. HH可视为规定周期等于截止期时的ML. DS-FP通过延迟事务实例的开始时间来减小系统的更新负载. 这几种算法的主要问题在于使用事务最坏情况下的执行时间(WCET)来进行处理机资源分配. 在许多应用中, 事务的WCET远大于其平均执行时间, 使用上述算法将导致较低的调度成功率. 即使能成功调度, 使用WCET也将造成处理机资源的浪费, 且难以适应系统运行模式的动态变化. 文[7]提出基于服务质量的动态实例调度算法以解决此问题. 但其中给出的模型和算法均是针对ML而设计, 没有考虑到DS-FP的特点, 不适用于DS-FP. 相比ML, DS-FP具有更高的可调度性且产生更小的更新负载, 因此有必要研究适用于DS-FP的动态调度算法. 本文针对DS-FP的特点, 提出一种基于加权数据无效期的动态DS-FP调度算法.

1 系统模型

设定实时数据库系统运行在单处理机平台上, 且所有实时数据对象均存放在内存中.考虑传感器事务集与数据对象集Γ由 DS-FP算法调度,负责对Oi进行更新.可表示为三元组实例的执行时间在内变化,给出其分布. Vi为Oi的有效期, Vi保持不变.

若所有事务都采用WCET时Г无法被DS-FP调度, 则用户将在某些时刻访问到无效数据. 实时数据对象的重要程度越高, 其无效期就应该越短. Oi的重要程度由权重wi给出. 假定系统为的任一实例预留的时间片个数不超过cif, 且将Γ中所有事务的执行时间设定为相应的预留时间时Γ可被DS-FP调度, 则此时O总的加权无效期可由式(1)来表示:

其中ri,j为实例的开始时间, Nj为使用DS-FP时生成调度的首个重复调度段[8]中最迟开始实例的下标.算出. 减小有利于提高用户事务在某一时刻访问到有效数据的概率, 从而有利于系统的正常运行.

2 动态调度算法DS-FP-DA

根据式(1), cif越大越小,平均来说也越小. 因此为了减小必须充分提高事务的预留时间. 但预留时间过大可能造成 Г无法被调度. 在一些应用中(例如视频监控), 实时数据对象的重要程度可能会发生改变, 数据更新时间的分布也会出现变化, 因此系统必须周期性地或根据工作环境的变化来重新计算事务的预留时间. 以下给出一种计算事务预留时间的方法:

(t)来近似其理论分布. 采用后者时, τk,l在内占据时间的平均值由式(4)给出:

3 实验模拟

本节实验评价提出的动态调度算法的性能. 与之比较的方法为DS-FP-SA. DS-FP-SA采用简单的接纳策略, 即当时, 系统不接纳. 实验的评价指标有三项: 数据加权无效时间 IVT, 数据更新负载DW 与事务绝对有效率 AVR., IVTi为数据对象 Oi在时间区间 T内的加权无效时间., 其中Ti为事务在T内的总执行时间., N与Nv分别为T内用户发起的事务个数及T内满足事务绝对一致性条件(即事务读取的时态对象在提交时有效)的事务个数.

实验所用数据库系统为自行研制的 ARTs-EDB系统. 我们对其接纳控制与事务调度模块进行修改以支持文中提出的算法. 所用机器 CPU为 Intel P4 2G, 512M内存. 操作系统为QNX实时操作系统. 表1给出了实验主要参数. 表中所有分布都为均匀分布. 传感器事务的更新时间满足正态分布μ的均值为15, σ为 0.01. 用户事务的到达率满足泊松分布. 传感器事务由DS-FP调度, 用户事务由EDF调度. 用户事务的优先级低于传感器事务. 用户事务 T的截止期d( T)设置为其中a( T)为T进入系统的时间,e( T)为T的计算时间. 所有实验的运行时间均为5 min.

表1 主要参数及设置

两种算法的IVT比较如图1所示. 这里Г的资源利用率为60%, Г的大小在40到200之间变化. 每步生成 300个事务集, 分别计算出 IVT后取平均值. 由图可知, DS-FP-DA的平均加权有效时间一直大于DS-FP-SA. 例如, 当事务集大小为120时, 前者高出后者约2.5%. 此外, 两者的差距随着事务数目的增加而增加. 主要原因在于DS-FP-DA能合理接纳一部分实际执行时间超出预留时间的实例, 而DS-FP-SA将所有此类事务均抛弃. 当事务数目增加时, 事务预留时间将减少, 通过接纳执行时间较长的实例能更有效地降低无效时间.

图2给出两种算法的DW比较. 这里Г的大小为120, Г的资源利用率在65%到85%间变化, 每步生成 300个事务集. 由图, DS-FP-DA生成的 DW 比采用简单接纳策略的 DS-FP-SA略高. 其原因是DS-FP-DA的接纳策略使得更多事务进入系统之中执行, 故造成了更新负载的增加.

图1 加权无效时间比较

图2 更新负载比较

两种算法在Г的资源利用率为65%时的AVR比较如图3所示. 这里Г的大小在40到200之间变化, 每步生成300个事务集. 由图 3可知, 在 DS-FP-DA下的 AVR高于DS-FP-SA. 例如当 Г的大小为 160时, DS-FP-DA高出DS-FP-SA约 2%. 其主要原因在于前者的 AVR高于后者,而两种算法产生的更新负载比较接近.

图3 事务绝对有效率比较

4 结论

实时数据库系统必须合理调度执行传感器事务以维护实时数据对象的有效性. 许多应用中事务的执行时间处于动态变化之中, 且其最坏情况下的执行时间远大于其平均执行时间. 现有算法难以处理这种情况. 为此文中提出一种动态传感器调度算法 DS-FP-DA.算法预先确定各个事务在 DS-FP调度下的预留时间. 在系统运行过程中, 算法根据实例的具体执行时间与当前系统中实例的运行情况来选择合适的实例执行. 实验表明, 算法能有效降低数据的加权平均无效时间, 使得用户事务能访问到有效数据的机会增加, 有利于系统的正常运行.

[1] Xiong M, Sivasankaran R, Stankovic J A et al. Scheduling Transactions with Temporal Constraints: Exploiting Data Semantics[J].IEEE Transactions on Knowledge and Data Engineering, 2002, 14(5): 1155～1166

[2] RAMAMRITHAM K. Real-time databases[J].Distributed and Parallel Databases,1993, 1(2): 199～226

[3] HO Shao-juen, KUO Tei-wei, MOK A K. Similarity-Based Load Adjustment for Real-Time Data-Intensive Applications[C]. in: Proceedings of the 18th IEEE Real-Time Systems Symp. Washington DC: IEEE Computer Society Press, 1997. 144～153

[4] XIONG M, RAMAMRITHAM K. Deriving deadlines and periods for real-time update transactions[J].IEEE Transactions on Computers, 2004, 53(5): 567～583

[5] Wang Jiantao, Lam Kam-Yiu, Han Song et al. On Co-Scheduling of Periodic Update and Application Transactions with Fixed Priority Assignment for Real-Time Monitoring[C]. in: IEEE 26th International Conference on Advanced Information Networking and Applications (AINA): 2012. 253～260

[6] XIONG Ming, HAN Song, LAM Kam-yiu et al. Deferrable scheduling for maintaining real-time data freshness: Algorithms, analysis, and results[J].IEEE Transactions on Computers, 2008,57(7): 952～964

[7] Xiong Ming, Liang Biyu, Lam Kam-Yiu 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

[8] Han Song, Chen Deji, Xiong Ming. A Schedulability Analysis of Deferrable Scheduling Using Patterns[C]. In: Proceedings of the 2008 Euromicro Conference on Real-Time Systems. Washington DC: IEEE Computer Society Press, 2008. 47～56

A Dynamic Sensor Transaction Scheduling Algorithm

BAI Tian, YANG Zhi-he, ZENG Di-fan
(College of Computer Science, Hunan Institute of Science and Technology, Yueyang 414006, China)

In real-time database systems, sensor transactions should be effectively scheduled to maintain the temporal validity of real-time data objects. The algorithms proposed so far are not suitable for the cases in which the worst case execution time is much larger than the average execution time. A dynamic scheduling algorithm called DS-FP-DA is proposed to solve the problem. The CPU time preserved for each instance in the DS-FP schedule is computed at first, and then an admission control scheme is used at running time to choose the incoming instances for execution. Experiments show that DS-FP-DA can significantly reduce the weighted average invalid time of real-time data objects.

real-time databases; sensor transactions; weighted average invalid time

TP311

A

1672-5298(2014)04-0013-04

2014-09-12

湖南理工学院科研资助项目(2014Y18)

白 天(1983− ), 男, 湖南岳阳人, 博士，湖南理工学院计算机学院讲师. 主要研究方向: 实时数据库, 信息物理融合系统