1、第第4章章 实时数据库技术实时数据库技术4.1 实时应用的数据处理实时应用的数据处理 随着计算机应用技术的发展，实时系统处理的数据信息量越来越大，对数据处理的功能要求也越来越高。这些应用有着与传统应用不同的特征，主要表现在两个方面：一方面，要维护大量共享数据和控制知识；另一方面，其应用活动(任务或事务)有很强的时间性，要求在规定的时刻和(或)一定的时间内完成其处理；所以，这种应用对数据库和实时处理两者的功能及特性均有需求，既需要数据库来支持大量数据的共享，维护其数据的一致性，又需要实时处理来支持其任务(事务)与数据的定时限制。但是，传统的数据库系统旨在处理永久、稳定的数据，强调维护数据的完整性
2、、一致性，其性能目标是高的系统吞吐量和低的代价，并不考虑有关数据及其处理的定时限制，所以，传统的数据库管理系统(DBMS)不能满足这种实时应用的需要。而传统的实时系统(RTS)虽然支持任务的定时限制，但它针对的是结构与关系很简单、稳定不变和可预报的数据，不涉及维护大量共享数据及它们的完整性和一致性，尤其是时间一致性。因此，只有将两者的概念、技术、方法与机制“无缝集成”(Seamless Integration)的实时数据库才能同时支持定时和一致性。4.2 实时数据库简介实时数据库简介4.2.1 实时数据库系统定义实时数据库系统定义 实时数据库技术是实时系统和数据库技术相结合的产物。概括地讲，实
3、时数据库(Real Time Database，RTDB)就是其数据和事务都有显式定时限制的数据库，系统的正确性不仅依赖于事务的逻辑结果，而且依赖于该逻辑结果所产生的时间。但是，必须注意的是：实时数据库并非实时系统和数据库技术在概念、结构和方法上的简单集成。它在概念、理论、技术、方法和机制方面具备自身特点。如：数据和数据库的结构与组织；数据处理的优先级控制、调度和并发控制协议与算法；数据和事务特性的语义及其与一致性、正确性的关系；数据查询/事务处理算法与优化；I/O调度、恢复和通信的协议与算法等，这些问题之间彼此高度相关。需要针对不同的应用需求和应用特点，对实时数据模型、实时事务调度与资源分配
4、策略、实时数据查询语言、实时数据通信等大量问题作深入的理论研究。4.2.2 实时系统的主要特性实时系统的主要特性 实时应用系统主要特性包括及时性、可预测性和可靠性等。1.及时性及时性 实时系统所产生的结果在时间上有着严格的要求，只有符合时间约束的结果才是正确的。在实时系统中，每个任务都有一个截止期，截止期内完成任务所得到的结果才是正确的结果。具体应用实现时必须落实到实时任务（事务）的各项定时特性：事务的松缓度、截止期的粒度和严格性（事务软、硬性）、优先顺序限制、起点到终点的定时限制、价值函数的形状（任务价值随时间的变化情况）等。这些都是定义和处理实时事务以及实现实时数据库系统的基本因素。2.可
5、预测性可预测性 实时系统的行为必须在一定的时间限度内，而这个限度是可以从系统的定义获得的。这意味着系统对来自于外部输入的反应必须全部是可预测的，就算在最坏的条件下，系统也必须严格遵守时间约束。因此，在出现过载时，系统必须要能以一种可预测的方式来降低它的性能级别。这就要求事先知道任务（事务）的最坏情况执行时间及所需的数据与资源，并要求这种最坏情况的预测与实际的的差别尽可能小。3.可靠性可靠性 实时系统的可靠性主要是系统的正确性，即系统所产生的结果不仅在值上是正确的，而且在时间上也是正确的。4.结构复杂性结构复杂性 实时任务（事务）往往具有各种结构上的相互联系，无结构的、原子和隔离的传统事务模型不
6、完全适用，而实时系统有时要求嵌套或层次结构事务，有时要求分裂和合并、通信与数据交换等，因此必须研究适应实时系统要求的具有复杂结构的事务模型。5.分布规律性分布规律性 实时任务（事务）通常是按一定周期执行的，但也有非周期或随机的，还有一些是长寿（循环或无终止事务）的。为了实现有效调度，必须事先知道各种任务（事务）的类型及其到达的分布规律。长寿事务和周期事务的实现比较容易，而非周期和随机事务则很困难。处理时可以将一个非周期事务的两次执行间的最小间隔时间视作其周期，从而将其当作周期事务来调度；而对于随机事务就只能由系统动态地进行处理。6.不可逆性不可逆性 实时应用中有很多活动是不可逆的，如过程控制的
7、器件加工、物料投放等活动，记录飞行体的位置、速度、方向的事务等，它们都是不可逆的。还原或重启动对于不可逆事务是毫无意义的，因此必须为实时事务的恢复开发新的概念、技术和方法。7.替代性替代性 当实时系统认定某个任务不能按时完成时，可以调用其它活动进行替代或补偿，这称为实时系统的应急计划，它可以提供虽非最佳但可用的结果。如何确定应急计划以及应急计划的选择评估及实施都是实时系统应该考虑的部分。4.2.3 实时数据库与传统数据库实时数据库与传统数据库 传统数据库的事务具有ACID（Atomaicity,Consistency,Isolation,Durability）特征，其特点如下：1强调一致性、可
8、恢复性和永久性；2事务无内部构造，是平坦的，彼此间无合作（交互作用、通信）；3事务执行时没有可预测性，其执行时间不可预测；4无“时间维”，更不显式地考虑时间。在传统数据库中，事务的原子性和可串行化是普遍接受的正确性和一致性标准。实时数据库系统和传统数据库有着根本性的不同，实时事务由以下特性确定：1可见性：事务执行时可以查看另一事务的操作结果的能力；2正确性：事务本身的正确性及提交事务所产生的数据库状态一致性；3可恢复性：发生故障时使数据库恢复到某种认为是正确状态的能力；4永久性：事务记录其结果到数据库及识别其中数据的有效期的能力；5可预报性：事先预测一个事务是否会满足其时限的能力。最根本的区别
9、在于数据与事务的定时限制。4.2.4 实时数据库与其它高级数据库的联系实时数据库与其它高级数据库的联系1.实时数据库与内存数据库实时数据库与内存数据库为了实现实时系统中数据和事务的实时（及时）性，必须尽可能加快实时数据库的响应和处理速度，同时实时数据库中的实时事务要求系统能较准确地预报事务的运行时间。但对磁盘数据库而言，由于磁盘存取、内外存的数据传递、缓冲区管理、排队等待及锁的延迟等使得事务实际平均执行时间与估算的最坏情况执行时间相差很大，不能满足部分实时系统的“及时性”要求。如果将整个数据库或其主要的“工作”部分放入内存;使每个事务在执行过程中没有磁盘I/O，则为系统较准确估算和安排事务的运
10、行时间，使之具有较好的动态可预报性提供了有力的支持，同时也为实现事务的定时限制打下了基础。内存数据库的设计应该打破传统磁盘数据库的设计观念，考虑内存直接快速存取的特点，以CPU和内存空间的高效利用为目标来重新设计开发各种策略与算法、技术、方法及机制。也可以说，内存数据库是在实际应用系统的实时性要求下而产生的。2.实时数据库与主动数据库实时数据库与主动数据库 今后，实时数据库的应用可能越来越复杂，为了满足各种复杂的应用要求，有必要使实时数据库系统具备高度的动态性、自适应性和智能行为。而主动数据库（ADB）技术与实时数据库（RTDBS）的结合为RTDBS的自适应性及智能性的实现创造了合理的机制。主
11、动数据库（ADB）技术现在已经在实时数据库（RTDBS）领域广泛应用。3.实时数据库与分布式数据库实时数据库与分布式数据库 随着Internet的迅速推广，实时系统应用范围和规模不断扩大，也对实时数据库系统提出了分布式计算的要求，因而有必要将分布式数据库技术运用于实时系统中。为了满足对数据的实时和分布的要求,分布式实时数据库(DRTDB)将具有执行期限的数据和事务分布在不同的结点上，由分布式实时数据库管理系统来统一管理、调度执行。国内的实时数据库产品与国外的产品相比，都有一定的差距,主要体现在其事务处理层并没有实现完全的分布式事务处理,与实时数据库的理论有一定的距离。实时数据库与内存数据库、主
12、动数据库、分布式数据库的有效集成才可以满足现代数据库的需求。4.实时数据库与时态数据库实时数据库与时态数据库与时态数据库相同之处是，实时数据库也涉及时间信息。但是，时态数据库与实时数据库存在区别，主要表现在：时态数据库目的在于处理包含随时间变化的信息，维护数据库中对象经历的历史变化；而实时数据库则更侧重考虑信息的“及时”性，它的查询与事务处理都有与之相联系的定时限制，结果产生的时间与结果本身一样重要。时态数据库保存数据库对象随着时间变化的特征，但缺乏维护数据有效性的机制，不显式考虑查询与事务有关的时间限制。在TDB中，随时间变化而改变的数据的处理是保留“历史”，增加新的数据项，可以查询某个过去
13、时间曾经有效的数据。RTDB则提供维护数据有效性和事务及时性的机制，一般只存取数据库当前“有效”的信息。事务必须维护数据库对象的“时间一致性”，所以有时间限制与之联系。时态数据库更多考虑“结构”，实时数据库则侧重考虑“行动”(控制实时)，有时“及时”性比正确性更重要。4.3 实时数据库的特征实时数据库的特征 一个典型的实时系统由三个紧密结合的子系统组成：被控系统、执行控制系统、数据系统。被控系统就是实际的应用过程，称为外部环境或物理世界，执行控制系统监视被控系统的状态，协调和控制它的活动，称为逻辑世界；数据系统有效地存储、操纵与管理实时(准确和及时)信息，称为内部世界；执行控制系统和数据系统统
14、称为控制系统。内部世界的状态是外部环境状态在控制系统中的映像，执行控制系统通过内部世界状态而感知外部环境状态，并在此基础上与被控系统交互作用，所有这些都与时间紧密相联。4.3.1 RTDB的数据特征的数据特征 RTDB中的一个数据对象D由3个分量组成(dv,dtp,devi)，它们分别为D的当前值、采样时间、外部有效期(外部现实对象状态变化的时间间隔)，外部有效期devi即自dtp算起dv有效的时间长度。对于RTDB中的每一个数据对象D，都有内部一致性、外部一致性和相互一致性特征。由定义可以看到，实时数据具有时间特征。实时数据给外部世界提供了一个真实和及时的表示，随着外部环境的变化，反映外部环
15、境状态的实时数据也随之变化.在实时数据库中，实时数据的时标dtp必须足够地接近真实时间，当前值dv只是在一定的时间devi内有效，在超过devi以前，数据一定要被最新的外部数据更新。内部一致性 dv满足预先定义的数据库内部状态的完整性和一致性限制。这就是传统意义下的数据正确性。数据库的变更都是以事务的形式进行的，因而事务操作的完整性校验和可串行化能提供内部一致性保证。外部一致性外部一致性（又称为绝对一致性）是指实时数据库中的数据应与外部数据(又称为环境数据)相一致，即要求数据库中的数据能及时地反映外部环境的状态。设tc为当前或检测时间，当且仅当(tcdtp)devi，则说D是外部一致的，即dv
16、和对应的外部现实对象的状态是一样的。数据的外部有效期dtp，可以通过足够的外部环境对应参数的取样来获取。外部一致性与时间限制紧密相关，它难以用可串行化的处理技术来实现，因为现有的确保可串行性的并发控制协议都是基于封锁或还原/重起动(Rollback/Restart)的。封锁可能导致优先级颠倒(低优先级的事务阻塞高优先级事务)；而还原/重起动除浪费系统资源从而引起事务超出时限外。实时系统有的事务根本不能还原/重启动，对于这种反映外部环境不可逆事件的事务，不能封锁或还原，必要时只有先牺牲内部一致性而确保外部一致性，然后再来恢复内部一致性。相互一致性 相互一致性用来决策或导出新数据的一组相关数据称为
17、一个相互一致集，记为R，其中的数据必须尽可能地在一个允许的公共时间期内被采取(或导出)，这个公共时间期就称为R的相互有效期，记为Rmvi，对于R中的任两个数据D和D，有|dtpdtp|Rmvi(即两个数据的采样时间在公共时间期间内)，则说R中的数据是相互一致的。相互一致性保证了用来作决策或导出新数据的一组数据是在允许的时间范围内彼此接近地产生的。Rmvi的获得不像devi那么简单，且它们之间存在着相互性，R中的各数据的devi的最小者对Rmvi起着决定作用。时间一致性 外部一致性和相互一致性都是关于时间的，故统称时间一致性。状态正确性 既是内部一致又是时间一致的数据才是正确的。4.3.2 RT
18、DB的事务特征的事务特征 RTDB标识性特征：定时性以及语义相关性。1.定时性定时性 定时性是RTDB事务的根本特点，定时可以是绝对、相对或周期时间。RTDB的定时性一方面由数据的时间一致性引起，此时它往往取周期或定期性限制的形式，如“每5秒取样一次”、“7:00启动机器人”等；定时性的另一根源是对现实世界施加于系统的反应时间的要求，这时它典型地取施加于非周期事务的截止时间限制的形式，如“若温度达到1000度，则在5秒内加冷却剂到反应堆”。定时性包含两方面的含义：(1)定时限制截止时间：实时事务完成的最后期限。它可以有硬、软之分，具有硬截止时间的事务(称为硬实时事务)，必须在其截止时间以前完成
19、，否则将带来灾难性的后果，故到达其截止时间还不能完成的硬实时事务必须夭折。具有软截止时间的事务(称为软实时事务)，应该在其截止期完成，但超过其截止时间也还有一定意义(尽管不断下降)，故软实时事务到达其截止时间后不必立即夭折它。到达时间：事务在系统中生成的时间。它可以是可预报的，也可以是不可预报的。可预报的到达时间可显式地给出或者作为一个导出函数，如周期事务的到达时间是可预报的。不可预报的到达时间是指当相应事务到达系统时才能知道，非周期事务的到达时间就是不可预报的。期望执行时间：估算的最坏情况执行时间。由于各种不可预报性因素，往往很难做到准确，估算的最坏情况执行时间可能与实际情况相差很大。然而，
20、为了合理地得到事务的截止时间及适当地调度以使其满足，又必须事先较准确地估算其执行时间。(2)定时正确性 即事务能按指定的时间要求正确执行，它要求权衡定时限制与数据一致性要求等多方面因素提供合适的调度与并发控制算法。2.语义相关性语义相关性(1)结构相关结构相关来自于复杂事务模型的结构特征，用来建模复杂事务内部并发事务行为的一种约束。不同的复杂事务模型有不同的结构相关性，但它们可以通过事务间的“执行依赖性”来定义，实时嵌套事务中基本的事务依赖有：子事务对父事务的开始依赖(BD)：子事务开始前父事务已经开始。父事务对子事务的提交依赖(CD)：父事务提交前子事务已经结束(提交或夭折)。子事务对父事务
21、的夭折依赖(AD)：父事务夭折则子事务一定夭折。(2)数据相关数据相关就是不同事务间的共享数据联系，但此“共享”概念比传统的具有更广的意义。实时嵌套事务中的子事务共享父事务数据，子事务提交时对数据库的更改委托给父事务，只有父事务提交时才能真正地写入数据库。(3)结果补偿一个实时应用常常由若干任务组成，而一个任务有时可以通过不同途径来实现。一个应用建模为一个事务，一个任务则建模为一组功能等价的子事务，称为该任务的替代集。若一个任务的替代集中的子事务之一能成功执行，则该任务是可完成的。若对应一个事务的所有任务可完成，则该事务是成功的(可提交)。功能替代导致了事务执行路径的不确定性，即一个事务成功执
22、行的路径依赖于执行过程中(子事务)失败的发生，且即使某些子事务失败了，事务仍可能顺利提交。这还体现了实时事务的健壮性要求，即有的事务(任务)不能失败。由于事务的结构复杂性和功能替代性，事务的执行经历是不确定，一个子事务的执行直到提交时还不能确定它是否需要。另一方面，一个实时事务可以物理改变现实世界的状态，换句话说，事务可以启动各种活动，这些活动在它提交前就已经影响了现实世界，因而当这种事务夭折时，不能进行传统意义下的“还原”(Undo)。所以，需要一种“补偿”活动来抵消它所有的影响，这种补偿活动也是事务。对于一个(子)事务，若存在能抵消它提交后所产生的所有影响的(子)事务，则称其为是可补偿的，
23、否则是不可补偿的。当然，不是每一个(子)事务都是可补偿的，不可补偿的(子)事务在知道它确实是需要的以前，一定不能提交。3.实时事务的正确性实时事务的正确性 在正确性概念及内涵方面，实时事务与传统事务的本质区别就在于其有定时限制。因此，事务处理必须同时满足一致性要求和定时限制。数据库状态正确性包含内部一致和时间一致，事务执行正确性则包含其结果正确性、行为正确性、结构正确性和时间正确性。传统数据库中的原子性和可串行化包含了事务正确性的所有概念。而实时嵌套事务正确性的内容更为丰富，实现的手段也就更为复杂。考虑一种新颖的准一致性可串行化并发控制策略，将事传统可串行化标准在实时环境下显得太严格，限制了系
24、统中事务执行的并发度，对于满足事务定时限制是不利的。所以，需要务执行给系统带来的不一致限定在一定的范围内，并在一定的时机恢复数据库到一致状态。而实时事务的时间正确性需要“识时”协议实现，结构正确性需要事务管理检查事务间的结构相关性来实现。4.4 实时数据库管理系统实时数据库管理系统 一个实时数据库管理系统(RTDBMS)也是一个数据库管理系统(DBMS)，但是有新的特性。4.4.1 实时数据库系统的主要问题实时数据库系统的主要问题 1数据模型及语言数据模型及语言 数据模型及其语言是RTDB领域首先要研究解决的主要问题之一。要开发实时数据模型，就必须设计好允许用户说明实时数据模型中所含的语义知识
25、的、使用户能以各种方式使用的实时数据定义和查询语言，以及能说明“复杂事务”的结构及相互作用的实时事务执行说明语言。2事务模型与特性事务模型与特性 具有ACID特性的传统事务模型在实时数据库系统中已不适用，必须进行扩展或开发新的“复杂事务”模型。与传统的事务是原子的、平淡的数据操作序列的概念相反，复杂事务为可以形成各种“内部结构”的数据操作集合，它可以具有嵌套或层次的内部结构、分裂或合并结构、交互合作或通信结构等，传统事务仅是其最简单的特例情况。3事务处理事务处理 RTDB系统中事务处理必须要满足事务的各种定时限制，并发控制是实时事务处理的另一个方面。4数据存储管理数据存储管理 数据库操作基本上
26、是I/O受限的，对于实时事务而言，传统数据库的磁盘存取延迟带来的影响是不能忍受的。RTDB系统必须考虑如何消除数据库操作中的磁盘存取延迟以满足实时事务的定时限制，这将要求“内存数据库”的支持。5I/O与缓冲区管理与缓冲区管理 除CPU与数据外，磁盘I/O和缓冲区对RTDB系统也是很重要的资源。I/O调度对实时系统是一个很重要的研究方面，RTDB系统需要“识时”的I/O调度算法，其目标是支持事务的定时限制。缓冲区是另一重要资源，缓冲区管理涉及在当前事务之间的存储空间分配问题，其目标是高优先级的执行不因此而受阻。6恢复问题恢复问题 恢复在传统数据库中已经是一个复杂的问题，而在RTDB系统中，会变得
27、更为复杂。必须要考虑到以下因素：恢复过程会影响正在进行的事务，使其超过截止期，这对硬实时事务是不可接受的。RTDB系统有时宁愿接受部分不一致的数据以确保其及时性。对于不可逆的事务、短暂的数据，数据库的恢复是没有意义的。4.4.2 实时数据库系统结构实时数据库系统结构RTDBMS的设计目标首先是对事务定时限制的满足，其基本原则是：宁要部分正确而及时的信息，也不要绝对正确但过时的信息。系统性能指标是满足定时限制的事务的比率，它要求必须确保硬实时事务的截止期，必要时宁肯牺牲数据的准确性与一致性。软实时事务满足截止期的比率相对较高，当然100满足截止期是非常困难的。因此，除了上述一般DBMS的功能外，
28、RTDBMS还具有以下功能特性：(1)数据库状态的最新性，即尽可能地保持数据库的状态为不断变化的现实世界当前最真实状态的映像。(2)数据值的时间一致性，即确保事务读取的数据是时间一致的。(3)事务处理的“识时”性，即确保事务的及时处理，使其定时限制尤其是执行的截止期得以满足。因此，RTDBMS是传统DBMS与实时处理两者功能特性的完善或无缝集成(Seamless Integration)。它与传统DBMS的根本区别就在于具有对数据与事务施加和处理“显式”定时限制的能力，即使用“识时协议”来进行有关数据事务的处理。数据库 实时资源管理 实时应用程序“识时”调度 实时事务管理“识时”并发控制 实时
29、数据管理 数据操作 恢复管理 日志管理 CPU 管理 缓冲区管理 实时 I/O 调度 (1)实时应用：是指具有定时限制的数据库任务，是实时事务产生源。(2)实时事务管理：管理实时事务的生存期，包括产生、执行和结束。(3)识时并发控制：实现识时的并法控制算法。(4)识时调度：实现识时的优先级调度算法。(5)实时资源管理：包括CPU管理、缓冲区管理、实时数据管理、实时数据管理又包括数据操作、存储和恢复管理等。(6)实时I/O调度：实现定时限制的磁盘调度算法。4.4.3 实时数据库执行模型实时数据库执行模型 1.任务任务/事务模型事务模型 传统的ACID(原子、一致、隔离和永久)性的事务模型对RTD
30、B已不适用，需要具有内部构造和/或彼此相关性的“复杂”事务模型，即嵌套、合并/分裂、通信和合作事务模型等。故RTDBMS必须支持这种复杂事务，处理事务间的结构、行为和时间相关性。2.资源模型资源模型 它确定系统资源的类型及其管理策略，包括分配、使用与回收策略。RTDBMS必须采用基于优先级和考虑定时限制尤其是截止期的分配策略；资源使用的“中断”策略也是优先级式的，即高优先级可抢占(中断)低优先级的资源，具体又可以有多种不同的抢占方式及其各方面的代价，需要RTDBMS仔细决策。3.负载模型负载模型 它规定各种类型事务的到达(或在系统中生成)、执行期限及频率的分布，包括周期、非周期及零星事务，软或
31、硬事务及其延迟的代价计算等。4.调度模型调度模型 它确定事务的优先级分配策略、调度算法、互相冲突的解决(并发控制)策略及其机制，控制事务正确、有效地执行。RTDBMS的调度模型还应有一定的“可调度性”预测能力及“应急处理”能力。5.执行的正确性执行的正确性 相对于传统数据库而言，RTDBMS执行的正确性在概念、内容与准则上都有根本性的不同，RTDBMS不但要确保事务执行结果(包括返回数据的状态及产生的数据库状态)的正确性，还要保证其执行在结构、行为、时间上的正确，即要正确实现事务间的结构、行为、时间相关性及执行依赖性。4.5 实时事务模型实时事务模型 RTDBMS与一般DBMS的根本性区别在于
32、数据和事务的定时限制，而数据的定时限制最终也要转嫁成事务的定时限制。因此，实时事务模型是RTDBMS需要解决的关键问题。4.5.1 实时事务的建模特性实时事务的建模特性 1.定时性定时性 定时限制：即事务的执行有显式的时限，如指定的开始时间、截止时间等，它要求RTDB必须有时间处理机制。实时事务的定时限制划分为：截止时间：事务完成的最后时间；到达时间：事务在系统中生成的时间；期望执行时间：估算的最坏执行时间。2.关键性关键性 实时事务的关键性指满足其截止时间的重要性，用价值函数表示。价值函数是“事务的完成对系统的价值”关于“完成时间”的函数。一个事务在t时刻的价值函数表示事务在t时刻完成对系统
33、所产生的价值，事务在截止时间前完成，价值函数取正值；否则，根据不同关键性逐渐减小，或取0、负数等。3.行为语义行为语义 行为语义包括了与事务相联的各种行为和它的发生时间。4.资源要求资源要求 实时事务所需资源的类型、数量、使用方式和时间决定了事务的功能、特性和处理方式。资源分为主动资源(可单独使用)和被动使用(一般使用时具有独占性和排他性)。5.相关性相关性 实时事务间的相关性是由事务在内部、结构、数据共享、同步通信和执行先后的限制引起的，一般分为结构相关性、数据相关性、行为相关性和时间相关性等。4.5.2 实时事务的分类实时事务的分类 1.按关键性分类按关键性分类 硬实时事务：用于安全紧急性
34、活动，超过截止期则价值函数取负值。硬实时事务在错失执行期限后将会导致灾难性的后果。因此，在系统发现事务具有很大的负值时，必须采取预定的紧急措施。软实时事务：这类事务在超截止期后，价值函数会不断下降，到被称为最终有效时间的某一时刻时，价值函数取0。软实时事务允许其执行有一定程度的超期。固实时事务：一旦到达截止时间，价值函数取0，但不为负值。图2中(a)(c)分别描述硬、软、固实时事务的典型例子。其中，v、t两坐标轴分别为价值函数和时间；d为截止期；e为“最终有效时间”；r为放行或启动时间，当tr时，v(t)=0，意思是在事务未准备好以前启动是无价值的。t d r v（c）固实时事务 e t d
35、r v（b）软实时事务 t d r v（a）硬实时事务 2.按功能分类按功能分类 控制事务：控制事务是引起现实中活动执行的有关事务。事务时间较短，属于硬实时，可以作为事务处理的子事务调用，本身也可触发子事务。数据接收事务：数据接收事务在数据库中记录了现实中的状态或发生事件，一般为简单的只写事务，较短并有周期性，这样能保持数据库的“外部一致”，属于硬实时。数据处理事务：数据处理事务类似传统数据库事务结构相关，可用来恢复数据库的一致性，可长可短。3.按时间分类按时间分类 周期事务：以一定周期循环到达并被执行。非周期事务：非周期事务由内外部事件动态驱动。离散事务：非预先安排、离散的、一次性执行的事务
36、。4.按数据方式分类按数据方式分类 只读事务：读取数据库中数据值并设置执行控制部件的参数，只读不写。只写事务：收集现实中的资料和信息并写入数据库。更新事务：可读可写，根据已有数据值导出新数据值。4.5.3 实时事务的特性实时事务的特性 1.功能替代性功能替代性 实时事务常由若干任务组成，对于单个任务可通过不同途径实现。对于一个应用可以将其建模为一个事务，而一个任务则建模为一组功能等价的子事务，称为该任务的替代集。任务是可完成的是指其替代集中的子事务之一能成功执行，一个事务是成功的，则对应该事务的所有任务可完成。功能替代导致了事务执行路径的不确定性，但增强了实时事务的健壮性。2.结构复杂性结构复
37、杂性 事务间及事务内部可能存在着多种结构，如嵌套、分层、合并、分裂和协同通信等。3.语义相关性语义相关性由于事务间存在着多种关系，使得事务间存在了各种相关性。如时间关系、行为关系、数据关系和结构关系等。结构相关：来源于事务模型的结构特征，作为约束用来建模事务内部并发事务行为的一种约束。数据相关：不同事务间共享数据的联系，包括嵌套事务模型中的通信事务模型的数据交换、数据继承、合并与分裂模型的数据委托。时间相关：为实时数据库事务所特有，表明事务的执行顺序和紧迫度，一般以“事务时间”来表示。行为相关：由事务的数据相关性及共享数据对象交互作用而引起。4.结果补偿性结果补偿性 由于事务的功能替代性和结构
38、复杂性导致了事务执行路径的不确定性。如果某个事务提交后，发现它是不需要的，该如何处理？同时实时事务不同于传统的数据库事务，它可以物理改变现实世界的状态，事务启动的某些活动在事务提交前可能已经影响了现实世界，因此当这种事务夭折时，不能进行传统意义上的“还原”，这就需要一种“补偿”活动来抵消它的影响。这种补偿活动也是事务。对于一个事务，若存在能抵消它提交后产生的所有影响的事务，则称其为是可补偿的，反之则称其为不可补偿的。不可补偿的事务在确定它是需要的之前一定不能提交。5.执行依赖性执行依赖性 执行依赖性是实时事务的结构复杂性和语义相关性引起的，事务(特别是嵌套父子事务)在执行时存在着各种依赖关系，
39、一般分为开始依赖、提交依赖、夭折依赖、传递夭折依赖、排他夭折依赖、传递提交依赖、成功依赖、失败依赖和外部依赖等。4.5.4 实时事务模型实时事务模型根据一般实时应用系统的活动（事务）特点，可以确定如下实时事务模型：General-Tran：一般事务(即传统意义的事务)Loop-Tran：循环事务，循环执行的一般事务或结构事务Endless-Tran：无终止事务，具有很长执行期的一般事务或结构事务Long-life-Tran：长寿事务，循环(Loop)或无终止(Endless)事务Nested-Tran：嵌套事务，由子事务以树形结构组成的事务Multilevel-Tran：多层事务，由子操作以树
40、形结构组成的事务Split-Tran：分裂事务，一个事务分枝出另一个事务Cooperative-Tran：合作事务Joint-Tran：合并事务Flat-Coop：平坦通信事务Hierarchical-Coop：层次间通信合作的事务Complex-Tran：复杂事务，可由上面列出的各事务构成4.5.5 嵌套实时事务模型嵌套实时事务模型 一个RTDBS可以抽象为一个三元组，D为实时数据对象的有限集；T为实时事务的有限集，T=T1,T2,Tn；C为预定义的关于D和T的限制的有限集，C=C1,C2,C3,Cm。RTDB按语义限制可分为两类，Ci，CiCCTC。CC为关于数据库的一致性限制，其包括外部
41、一致、内部一致和内外部相互一致性。TC为实时事务相连的限制，如：数据一致性限制所带来的限制(如时间一致性限制)、定时限制和触发限制等。从结构上说，实时事务为嵌套的复杂事务，其语义来源包括：(1)应用语义显式地要求结构上一个事务为另一个事务的子事务。(2)实时数据库环境中的事务在特定情形下触发一定的活动，其应用要求可以是触发它的事务的子事务。(3)在分布式应用环境中，一个事务可能要分出若干在不同结点上执行的代理事务，它们分工合作且均作为原事务的子事务。(4)在工程应用中，普遍存在的无终止事务或长时间事务。给出一种适应实时应用者的嵌套事务模型如下：定义一个嵌套事务为包含了子事务的事务，子事务还可以
42、包含子事务。包含有子事务的事务称为“父亲”，它包含的子事务就是它的“儿子”，根事务称为该系列事务的“开祖”，“叶子”事务称为其“末代”。自开祖至一个给定子事务的路径上的所有事务称为该子事务的“祖先”，反之该子事务则为“后代”。子事务共享父事务的资源，而父事务的执行时间包括了该后代的执行时间，父事务提交的数据包括了其后代的提交数据。因此，一个父事务要到所有后代结束才能提交，如果父亲事务一旦夭折，就算子事务已提交，也必须夭折。给出基本规则如下：(1)激励开祖事务以外部时间或内部时间作为启动的激励，子事务则以其父事务的显示命令作为启动的激励。一个父事务以下列两种方式调用子事务：同步方式：子事务立即启
43、动执行，而父亲事务同时被挂起直到子事务结束。异步方式：父亲事务不被子事务阻塞，它们并发地执行。子事务可以立即也可以推迟执行，但所有子事务必须在父事务提交前结束。兄弟间事务可顺序或独立并发地执行。(2)提交一个儿子事务成功地完成时，则向其父提交，因而其结果可被父亲存取。但这种提交对数据库来说是临时的，它随祖先事务的夭折而被“还原”，仅当开祖事务提交时，才有效。(3)夭折 一个父亲事务夭折，则不管其提交与否，所有“儿子”包括其“后代”都夭折，对于某个儿子事务的夭折，父亲事务可以做选择性操作如下：重启动该儿子事务。执行一个“替代”/“补偿”事务。不管该儿子事务的夭折。父亲自身夭折。(4)存取 一个“
44、儿子”的可存取数据集为其父亲可存取集的子集。4.6 实时事务调度与并发控制实时事务调度与并发控制4.6.1 实时事务调度实时事务调度 1.最早放行最优先最早放行最优先(Earliest Release First)该策略将最高优先级指派给具有最早“放行”(Release)时间的事务。所谓放行时间就是事务可以开始执行的最早时间，与此相联的有事务到达(Arrive)时间、事务接纳(Admission)时间。2.截止期最早最优先截止期最早最优先(Earliest Deadline First)即具有最早截止期者优先级最高。3.可达截止期最早最优先可达截止期最早最优先(Earliest Feasibl
45、e Deadline First)具有最早的可达截止期者优先级最高。所谓一个事务t的截止期是当前时间“可达到”的，乃指(EP)d。这里为当前时间，E、P分别为事务T的执行时间估算和已执行时间，d为其截止期。4.空余时间最短最优先空余时间最短最优先(Least Slack First)事务t的空余时间S=d(EP)，即推迟T的执行而仍然满足其截止期的可推迟时间量估算。5.价值最高最优先价值最高最优先(Highest Value First)每个事务都有价值函数，其值最大者最优先。问题是如何合理地构造价值函数，一个例子是：V(t)=c(w1(S)w2dw3Pw4S)其中、d、P和S的意义同上，c、
46、S分别为t的危急度、开始时间，wi为加权因子。6.价值密度最大最优先价值密度最大最优先(Greatest Value Density First)价值密度函数为：即事务完成时的期望价值与实现该价值所需计算量的比最大者优先级最高。显然，对于期望价值一样的事务，该策略偏向较短者，因为它每单位消耗时间所获得的价值更大。v(+c)v(+EP)VD=cEP4.6.2 实时事务的并发控制实时事务的并发控制 可串行化是并发控制的重要标准，其定义为：一个调度S是可串行的，当且仅当一个串行调度SS。1加锁的并发控制加锁的并发控制 这种并发控制方法是“悲观”的，它假定事务冲突经常发生。按事务使用数据的方式来分类，
47、实时数据库的事务通常可以分为只读、只写及更新等类型，它们分别对应锁的不同标识及控制策略，主要是共享锁和排斥锁，还有其它一些更精细的锁。常用的技术有三种:a、无条件执行 除非特别意外的紧急干扰，该事务一直占有主机直至其完成。b、无条件终止 一个事务若拥有锁且具有高于新到达事务的优先权，则其仍占有锁并继续执行。若一个拥有锁事务的优先权低于新到达者的优先权时，则被中止运行，新到达者投入运行。c、有条件终止 仅当拥有锁的低优先级事务不能在新到达的高优先级事务所允许等待的时间内执行完成时才去中止它。利用锁技术可以避免由于并发操作引起的数据错误，但又可能产生饥饿事务和死锁等问题。解决饥饿的一种简单方法是采
48、用先来者先执行的策略。死锁发生时，需要选择一个事务撤销。选择该事务应用考虑使尽量多的事务能满足时间限制要求。死锁解决策略为：撤销一个已经超过时间限制的事务，如有多个超过时间限制的事务，则撤销具有最长截止时间的事务。2乐观的并发控制乐观的并发控制 “乐观”并发控制（OPT，optimistic concurrency control）是一个无锁协议，它假定它以合理的事务性能为前提，假定任两个并发事务请求相同的数据区组（事务冲突）是最低概率事件，即“乐观”的，因此它让事务无阻碍地运行到全部操作完成，当然写申请并不立即更新分配的数据库，然后在提交时进行检验，看是否真的发生过冲突或违反了可串行化要求，
49、若通过检验则提交，否则就夭折。三个阶段：(l)读阶段：事务从数据库中读取数据，进行计算，并为写集合中的数据项确定新值，但这些新值暂时不写进数据库中。(2)验证阶段：检测事务对数据的修改是否失去相容性。(3)写阶段：如果验证阶段获得肯定的结果，则对数据库进行修改，否则该事务重启动。其中验证可按向前和向后两种方式进行。在向后有效方式下，有试图提交的事务读出一组项目，按正提交事务写入的项目逐个测试。在向前有效方式下，由正提交的事务写入的一组项目与任一当前执行的事务读出的项目比较，如有任何非空区组，则发生一个串行错误。3基于时标的并发控制基于时标的并发控制 时标(Timestamp)是另一种并发控制的
50、方法，它避免了使用锁，因此也不会产生死锁。每个事务在其进入系统时都被分配一个时标，那些提交的事务将按时标的顺序串行，即按它们开始时的顺序提交。一旦开始执行，任何违反顺序的读写请求都将失败。4.7 实时数据库应用实时数据库应用4.7.1 国内外实时数据库的发展现状国内外实时数据库的发展现状 目前市场上流行的实时数据库产品,主要有PI系统(适用于流程工业：国外)、Info Plus.21(主要在石油化工方面：国外)、力控系统(主要用于控制领域：国内)、SuperInfo(主要用于电力调度、石油、化工等领域：国内)等等。这些产品仅仅局限于某一领域的应用,尚未建立统一的通用型商业平台，实时数据库在不同
