实时数据库事务模型及处理技术要点探讨

实时数据库事务模型及处理技术要点探讨 实时数据库事务模型及处理技术要点探讨 实时数据库事务模型及处理技术要点探讨 文章来自

关键词:嵌入式;实时数据库;模型

摘要:论文概述了嵌入式实时数据库(ERTDBMS)及事务特点的研究现状,分析了ERTDBMS事务与分析、代替/补偿、基于价值函数和面向对象框架的事务模型,探讨了ERTDBMS事务调度策略和并发控制,阐明了该问题的研究意义。

中图分类号:TP393 文献标志码:A

1 引言

目前,数字化产品继PC之后成为信息处理的又一个主要工具,在这些嵌入式设备中,需要具备成熟的数据管理能力,所需的功能非常复杂,以至于文件系统不足以处理和操纵这些数据,这就促进了对嵌入式数据库系统的需求。嵌入式数据库系统的设计目的是在最小系统影响下进行数据存储和恢复。由于常常需要对环境做出实时反应,此概念建立在实时或近似实时的嵌入式计算机中,准确地讲更多的需求是嵌入式实时数据库系统[1]。

2 ERTDBMS事务的特点及研究现状

2.1 ERTDBMS事务的特点

嵌入式实时数据库系统模型的操作也是以事务的形式出现,系统以事务为单位分配CPU、数据等资源,进行优先级的分配、调度处理等。同时,ERTDBMS中的事务与传统事务又有所不同,其事务可以有定时限制,系统追求的目标是单个事务定时限制的满足,以使满足定时限制的事务比率最大,要求采用“识时”机制来处理事务的调度或并发控制,而不是传统的先来先服务方式。

ERTDBMS中事务与传统事务的根本性区别表现在: 2.2 ERTDBMS及其事务模型的研究现状

目前的嵌入式实时数据库系统可分为两大类:一类是商用级的嵌入式实时数据库系统(如美国McObject公司提供的eXtremeDB内存式实时数据库);另一类是用户针对具体的应用对象而自行设计开发的嵌入式实时数据库系统。

Kim建立了一个实时数据库事务模型,而Braoudakis采取不同方法,将事务与一个价值函数关联,Zhou,Rundensteiner和Shin将面向对象的观点结合到实时数据库系统中,提出了ROMPP,用面向对象的框架探讨了时态和逻辑的一致性和正确性。目前嵌入式实时数据库系统的事务模型以华中科技大学刘云生教授及其博士生夏家莉教授的基于功能替代/补偿的实时事务模型最为成熟[3]。

基于功能替代的实时事务模型以替代作为并发控制和调度的基本单位,可以提高事务的成功率。在支持补偿的实时事务模型中,替代提高了事务的成功率,但不能保证事务的绝对成功,当所有替代都失败或在其截止期前不能成功执行替代时,需要采取补偿措施,特别是某些不具备替代性的实时事务在失败时需要补偿。

3 ERTDBMS事务模型及处理的技术要点

3.1 ERTDBMS事务预分析

ERTDBMS中的实时应用包含了丰富的数据、事务语义及复杂结构,具有许多与传统应用不同的特征,在事务处理时必须考虑到数据和资源的冲突、事务间的相互依赖性、新活动(事务)的动态“产生”以及事务的夭折因素[4],事务的实际执行时间和估算的最坏情况下执行时间的误差很大,所以系统必须要有一定的预测和处理能力,能进行“可调度性”分析和预测,事先知道一个事务满足其定时限制特别是截止时间的可能性,是否有“危险”性而采取专门措施,以便保证它正常完成。

BRTDBMS事务的预分析至少包含以下四方面的内容:

(1)在事务到达系统或在系统生成时对其进行预分析,提取关于事务的替代集、数据集、操作逻辑(类型和顺序)、定时性要求、紧迫性与关键性、运行时间估算、可能触发的活动/事务等的信息,以及各事务间在结构、行为、数据和定时等方面的相关性信息。

(2)在系统运行时的适当时机,采用一定的算法对当前活跃事务进行相关性分析,以支持和辅助调度算法与并发控制策略的实施。

(3)在执行调度与并发控制前,动态地进行“可调度性”预测,确定它们能正常完成的可能性或程度,以便采取相应的措施来尽可能保证其实现。

(4)必要时采取相应措施,如动态调整优先级与调度算法、执行“功能替代”或“补偿”等活动。

截止期是ERTDBMS事务的一个重要特性,确定事务的截止期是事务预分析的首要工作。从确定方式来说,主要有赋值截止期、演绎截止期和隐式截止期等。在ERTDBMS中,精确的事务调度策略涉及事务的截止期和执行时间。与截止期一样,程序的执行时间成为事务预分析要解决的又一个重要难题。文献中提出了一种程序执行时间的估算方法,将其分为两步:一是静态地WCET (Worst Case Execution Time)估算,说明程序的执行在X秒内完成,调度的精确性依赖于此区间的紧密性;二是利用灰色系统理论,通过分析灰色信息找出规律,从而预测事务的执行事件,得到动态的时间估算[5]。

3.2 ERTDBMS的替代/补偿事务

一个具有时间限制的应用为一个实时事务,它有若干个任务组成,某些任务可以完成实时事务的功能。实时事务具有功能替代的特性,一个实时事务包含有多个任务集,它们是功能等价的,称为任务替代集。每个任务又包含了一组功能等价的子事务。在实时事务的一个任务替代集中,由每一个任务中的一个成员所组成的集合称为该事务的一个功能替代集。实时事务有多个功能替代集组成,在每次调度到该事务时,该实时事务中挑选一个合适的功能替代集,一旦此功能替代集夭折而事务的截止期未到,系统将试图选取该实时事务的另一个功能替代集继续投入调度,如果能使系统有意识地选取成功率高的功能替代集,就能提高系统的执行效率。

基于功能替代的实时事务模型(Function Alternative Transaction Model,FATM)的建立,充分表明一个实时事务实际上具有复杂的三维结构。从而在预分析时采取三个步骤:分解事务得到其所有功能替代集;逐个分析提取与运行有关的信息和知识;考察调度性能并排序为调度提供直接信息。功能替代集的预分析过程如图1所示。系统调度时,首先从强调度树中选取一个对象,若无强调度树,则从弱调度树中选取一个对象,在软实时环境下,有可能从普通调度树中选取一个对象。

图1 实时事务功能替代集预分析图解

基于功能替代的ERTDBMS事务模型有利于对事务的预分析,作为调度的先期调度,直接关系到其执行成功率,从而节省系统的运行时间。同时,事务的可替代性使事务的执行具有多条路径,提高了事务的成功率。但是,如果事务的所有替代集都不能(或者时间不允许)成功执行,则其依然要夭折。为了避免因此引起的系统灾难,有必要对FATM进行扩充,使之支持补偿性,即事务有主任务和补偿任务组成,当主任务不能成功执行时,由补偿任务使之安全结束(当然并非每个事务都是可补偿的)。

3.3 基于价值函数的实时事务模型

具有功能替代的事务模型具有定时性、功能等价性、同构性等特点[6]。用一致的观点看待系统中的实时和非实时事务,将事务的价值函数引入事务模型中,使实时事务模型满足更好的特性。实时事务的价值函数如图2所示。

图2 实时事务的价值函数

非实时事务可视为实时事务的一种特列(没有Di的要求),其价值不随时间的变化而变化,恒为Vi。实时事务的价值函数分情况讨论如下:

(1)t<Di 时,VTi∈RT,有V(Ti)=Vi(Vi为常数);

(2)t>Di时,VTi∈HT,有V(Ti)=-P(P为常数);

VTi∈FT,有V(Ti)=0;VTi∈ST ,有V(Ti)=0(TZi-t)tanɑ。

3.4 ERTDBMS事务调度策略与并发控制

在ERTDBMS事务调度中,主要利用两方面的因素:事务到达时间和事务截止期。调度策略中大部分采用优先级调度法,如最早放行最优先(Earliest Release First,ERF)、截止期最早最优先(Earliest Deadline First,EDF)、可达截止期最早优先(Earliest Feasible-Deadline First,EFDF)、最小松弛时间最优先(Minimum Slack First,MSF)、价值最高优先(Highest-Value First,HVF)等[7]。并由此派生出一些新策略,如自适应最早最终时间(AED)协议,它是基于EDF分配策略的,把事务分成两组,根据预先设定的控制变量,进行关键性值的排序,按照列表中的关键值排序进行调度。

并发控制是要控制并发事务之间的相互作用(或者协调调度),使数据库一致性(ERTDBMS中特别是事务的时间一致性)不被破坏。ERTDBMS的并发控制是在传统数据库基础上考虑时间因素,提出有悲观并发控制、乐观并发控制以及多版本并发控制协议等。阶段锁定是最大众化的悲观并发控制协议,使用此方法,事务在获得锁之前禁止访问数据库目标,事务执行由获得锁和释放锁两部分组成。包括优先级中止、优先级继承和有条件优先级继承等。乐观并发控制协议允许事务无障碍执行直到全部操作完成,然后在提交时验证,如果通过就提交否则重启。在多版本并发控制协议中,每个数据由多个版本,读操作中事务可以读取没有被覆盖的旧版本来保证调度的可串行性,从而增加并发度,减少拒绝操作。

4 结束语

本文主要讨论了嵌入式实时数据库的特点和其事务模型及其处理的有关理论、技术和实现方法等,包括ERTDBMS的特点、ERTDBMS事务模型的特点和研究现状、基于替代/补偿的事务模型、基于价值函数的事务模型、基于面向对象的事务模型以及ERTDBMS事务的调度策略和并发控制。嵌入式实时数据库系统作为嵌入式实时操作系统的一个用户进程,其事务执行在时间和