论文部分内容阅读
摘要：本文从实时数据库的研究意义与发展现状出发，对实时数据库技术所采用的主要技术以及各自的优缺点加以论述，最终从个人的角度阐述了对实时数据库的研究方向。
关键字：实时数据库；RTDB；时间一致性
一、研究实时数据库的目的和意义
１．实时数据库简介
实时数据库系统是数据库与实时系统相结合的一种新型数据库。与传统的数据库相比有着不同的特征：一方面，数据库系统要维护大量的共享数据；另一方面，系统的事务处理有很强的时间限制，要求在规定时间内完成任务。RTDB（Real-Time Data Base）并非是实时系统和数据库系统两者的概念、机构、工具等的简单集成，需要对：数据和数据库的结构与组织；事务的截止时间的软硬性；事务的优先级分派、调度和并发控制的协议与算法；I/O调度、恢复、通信的协议与算法；查询处理算法；数据和事务特性的语义及其与一致性、正确性的关系等问题进行综合研究与决策。
二、国内外研究的技术现状分析
１．实时数据特点
在RTDB中，数据值随外部环境状态变化而频繁地改变。不能只考虑数据库内部状态的一致性，还必须考虑外部状态与内部状态之间的一致性；也不能认为使用数据时，简单地提供其最新值就是最合适的，还必须考虑它与其它被使用数据间的“时间一致性”，这些就是RTDB的数据特征。
２．索引技术分析
RTDB一般的索引方法有以下几种：
（１）数组。采用数组做索引结构，它的致命缺点是不能动态维护。（２）AVL树。AVL树具有较高的存取性能，但其突出的缺点是其内存的有效利用率很低，每个结点只有一个数据元素，却有两个指针和有关控制信息。（３）B树和B+树。B树删除操作比较繁琐，对于实时数据库系统不适合。（４）Hash索引。首先构造一个散列函数，查找键，为参数并计算出一个介于0到B-1的整数，其中B是散列桶的数目。Hash算法的每个桶中保存的是属性值等于某一特定值的所有元组的集合。目前各种实时数据库的实现中，都基本采用这些索引方法并在这些方法上结合及改进，来进行数据组织以满足高效访问性。
３．并发控制协议分析
并发控制就是要控制并发事务间的相互作用使数据库的一致性不被破坏。优先级反转是传统的并发控制协议应用于实时数据库所表现出的主要问题。目前，许多面向实时数据库的并发控制协议，这些协议可以归结为基于锁的和乐观并发控制协议。（1）两阶段锁协议：在每个事务中，所有封锁请求先于所有解锁请求。两段式锁协议中规定：在对任何数据进行读、写操作之前，事务首先要获得对该数据的锁，而且在释放一个锁之后，事务不能再获得任何其它的锁。（2）乐观并发控制协议，将事务执行的步骤分为读取、验证、写入阶段。事务执行过程中对数据的操作在自己的独立工作区完成，其所有操作进入验证阶段。可串行化问题在验证阶段进行检测，一旦出现冲突，将会有任务被迫重启；如果通过了验证，那么事务对事务的操作将会从独立工作区落实到原始数据上。
４．锁的并发控制的现有算法及优缺点分析
为了解决优先级倒置和死锁问题，在基于锁的并发控制算法中引入了优先级继承、优先级顶等机制。若请求者TR的优先级比占有者TH的优先级高，按协议在解决冲突时发生高优先级事务等待低优先级事务完成的情况，称为“优先级倒置”。
“优先级倒置”的解决方法有：
（1）优先级夭折。此算法通过结合确保高优先级事务不会被低优先级事务延迟的冲突解决方案对基本两阶段加锁进行修改而形成。发生优先级倒置时，夭折低优先级的TH而让高优先级的TR执行。该策略可消除死锁，但是对那些已执行的时间很长而还需执行的时间很短的TH夭折的代价太大。（2）优先级继承。优先级继承考虑的是实际冲突，因而灵活地解决了优先级倒置问题。发生优先权颠倒时，把占有者TH的优先级提高到与TR的一样，TH继续执行直到结束，减少了被阻塞的高优先级事务等待时间。（3）条件优先级继承。根据事务的估算执行时间，只有TH接近完成时才能继承TR的优先级，否则夭折TH。条件优先级继承是优先级继承和优先级夭折两种策略的折衷。但是，CPI策略一是仍存在PI策略中阻塞链问题；二是要使TR不超过截止期，TR的空闲时间应大于TH阻塞链中所有事务还需执行时间的最大值，可当时却还没有链，这样使TR在等待中不觉地就超过了截止期；还有一难题是TR的空余时间和TH需执行时间的可准确性，它决定CPI算法的成功率。（4）优先级顶置。它是优先级继承协议的一个改进协议，主要思想是为发生冲突的数据标识出所能访问它的事务的优先级最高限度，从而对事务的抢占提出准入要求。当数据被加以写锁的时候，不允许被其它事务进行读或写，直至写完毕释放锁；当数据被加以读锁的时候，所有写事务均不许进入，而比所有写事务优先级都高的读事务可以进入。
５．乐观的并发控制（OCC）的现有算法及优缺点分析
（1）基于广播提交的乐观并发控制。利用优先级解决事务间冲突。当查出冲突时就对冲突事务的优先级进行检查。如果提交事务优先级高过所有与它产生冲突的事务优先级，执行事务被中止；如果正处于冲突的执行事务有更高优先级，提交事务等待直到执行事务提交。（2）OCC-WAIT及OCC-W50算法。前者是如果一个验证阶段事务的优先级比冲突事务的低，那么该事务应该等待直到高优先级事务完成为止。这种做法使得高优先级事务有机会首先在其截止时间内完成。在OCC-W50方法中，除了等待方案，还结合了优先级来提高解决冲突的决定方案。如果与提交事务T存在冲突的一半或以上的事务优先级高于此提交事务，提交事务T则必须等到高优先级事务的完成。否则T被提交，同时冲突事务被中止。研究表明，OCC-W50的表现要远远好于OCC-WAIT。在软实时系统下，如果物理资源有限，则锁协议优于乐观并发控制协议。当可利用资源数量很丰富，并且系统性能主要由并发控制而不是其它资源调度决定时，则乐观协议优于锁协议。
三、综述
OCC乐观的本质使它能够提高系统并发度，而且避免了死锁的发生。另外，由于冲突检测是在验证阶段进行，OCC可以得到较多的信息来决定解决冲突的方法，因此对于RTDB更为适用。但是，较晚的冲突检测会造成事务重启的次数增加，频繁的重启对RTDB来说是个沉重的负担。加锁并发控制能够节约系统资源，不过并发度不高，当争夺数据资源的情况较少发生时，乐观的优势更为明显。由于回滚操作可能频繁进行，乐观算法在处理时间限制比较严格的硬实时事务时，表现不如加锁。混合算法的提出，正是为了最大限度的利用多方面的优点。因此怎样针对混合算法进行合理有效设计才是我们应该着重研究的关键问题。
【参考文献】
[1]李昭原.数据库技术新进展第二版.清华出版社，2007.
[2]张禹.大流量实时数据库架构分析与实现.电子科技大学. 2007.
[3]Jisu Oh and Kyoung-Don Kang，An Approach for Real-Time Database Modeling and Performance Management， the 13th IEEE Real Time and Embedded Technology and Applications，2007.
关键字：实时数据库；RTDB；时间一致性
一、研究实时数据库的目的和意义
１．实时数据库简介
实时数据库系统是数据库与实时系统相结合的一种新型数据库。与传统的数据库相比有着不同的特征：一方面，数据库系统要维护大量的共享数据；另一方面，系统的事务处理有很强的时间限制，要求在规定时间内完成任务。RTDB（Real-Time Data Base）并非是实时系统和数据库系统两者的概念、机构、工具等的简单集成，需要对：数据和数据库的结构与组织；事务的截止时间的软硬性；事务的优先级分派、调度和并发控制的协议与算法；I/O调度、恢复、通信的协议与算法；查询处理算法；数据和事务特性的语义及其与一致性、正确性的关系等问题进行综合研究与决策。
二、国内外研究的技术现状分析
１．实时数据特点
在RTDB中，数据值随外部环境状态变化而频繁地改变。不能只考虑数据库内部状态的一致性，还必须考虑外部状态与内部状态之间的一致性；也不能认为使用数据时，简单地提供其最新值就是最合适的，还必须考虑它与其它被使用数据间的“时间一致性”，这些就是RTDB的数据特征。
２．索引技术分析
RTDB一般的索引方法有以下几种：
（１）数组。采用数组做索引结构，它的致命缺点是不能动态维护。（２）AVL树。AVL树具有较高的存取性能，但其突出的缺点是其内存的有效利用率很低，每个结点只有一个数据元素，却有两个指针和有关控制信息。（３）B树和B+树。B树删除操作比较繁琐，对于实时数据库系统不适合。（４）Hash索引。首先构造一个散列函数，查找键，为参数并计算出一个介于0到B-1的整数，其中B是散列桶的数目。Hash算法的每个桶中保存的是属性值等于某一特定值的所有元组的集合。目前各种实时数据库的实现中，都基本采用这些索引方法并在这些方法上结合及改进，来进行数据组织以满足高效访问性。
３．并发控制协议分析
并发控制就是要控制并发事务间的相互作用使数据库的一致性不被破坏。优先级反转是传统的并发控制协议应用于实时数据库所表现出的主要问题。目前，许多面向实时数据库的并发控制协议，这些协议可以归结为基于锁的和乐观并发控制协议。（1）两阶段锁协议：在每个事务中，所有封锁请求先于所有解锁请求。两段式锁协议中规定：在对任何数据进行读、写操作之前，事务首先要获得对该数据的锁，而且在释放一个锁之后，事务不能再获得任何其它的锁。（2）乐观并发控制协议，将事务执行的步骤分为读取、验证、写入阶段。事务执行过程中对数据的操作在自己的独立工作区完成，其所有操作进入验证阶段。可串行化问题在验证阶段进行检测，一旦出现冲突，将会有任务被迫重启；如果通过了验证，那么事务对事务的操作将会从独立工作区落实到原始数据上。
４．锁的并发控制的现有算法及优缺点分析
为了解决优先级倒置和死锁问题，在基于锁的并发控制算法中引入了优先级继承、优先级顶等机制。若请求者TR的优先级比占有者TH的优先级高，按协议在解决冲突时发生高优先级事务等待低优先级事务完成的情况，称为“优先级倒置”。
“优先级倒置”的解决方法有：
（1）优先级夭折。此算法通过结合确保高优先级事务不会被低优先级事务延迟的冲突解决方案对基本两阶段加锁进行修改而形成。发生优先级倒置时，夭折低优先级的TH而让高优先级的TR执行。该策略可消除死锁，但是对那些已执行的时间很长而还需执行的时间很短的TH夭折的代价太大。（2）优先级继承。优先级继承考虑的是实际冲突，因而灵活地解决了优先级倒置问题。发生优先权颠倒时，把占有者TH的优先级提高到与TR的一样，TH继续执行直到结束，减少了被阻塞的高优先级事务等待时间。（3）条件优先级继承。根据事务的估算执行时间，只有TH接近完成时才能继承TR的优先级，否则夭折TH。条件优先级继承是优先级继承和优先级夭折两种策略的折衷。但是，CPI策略一是仍存在PI策略中阻塞链问题；二是要使TR不超过截止期，TR的空闲时间应大于TH阻塞链中所有事务还需执行时间的最大值，可当时却还没有链，这样使TR在等待中不觉地就超过了截止期；还有一难题是TR的空余时间和TH需执行时间的可准确性，它决定CPI算法的成功率。（4）优先级顶置。它是优先级继承协议的一个改进协议，主要思想是为发生冲突的数据标识出所能访问它的事务的优先级最高限度，从而对事务的抢占提出准入要求。当数据被加以写锁的时候，不允许被其它事务进行读或写，直至写完毕释放锁；当数据被加以读锁的时候，所有写事务均不许进入，而比所有写事务优先级都高的读事务可以进入。
５．乐观的并发控制（OCC）的现有算法及优缺点分析
（1）基于广播提交的乐观并发控制。利用优先级解决事务间冲突。当查出冲突时就对冲突事务的优先级进行检查。如果提交事务优先级高过所有与它产生冲突的事务优先级，执行事务被中止；如果正处于冲突的执行事务有更高优先级，提交事务等待直到执行事务提交。（2）OCC-WAIT及OCC-W50算法。前者是如果一个验证阶段事务的优先级比冲突事务的低，那么该事务应该等待直到高优先级事务完成为止。这种做法使得高优先级事务有机会首先在其截止时间内完成。在OCC-W50方法中，除了等待方案，还结合了优先级来提高解决冲突的决定方案。如果与提交事务T存在冲突的一半或以上的事务优先级高于此提交事务，提交事务T则必须等到高优先级事务的完成。否则T被提交，同时冲突事务被中止。研究表明，OCC-W50的表现要远远好于OCC-WAIT。在软实时系统下，如果物理资源有限，则锁协议优于乐观并发控制协议。当可利用资源数量很丰富，并且系统性能主要由并发控制而不是其它资源调度决定时，则乐观协议优于锁协议。
三、综述
OCC乐观的本质使它能够提高系统并发度，而且避免了死锁的发生。另外，由于冲突检测是在验证阶段进行，OCC可以得到较多的信息来决定解决冲突的方法，因此对于RTDB更为适用。但是，较晚的冲突检测会造成事务重启的次数增加，频繁的重启对RTDB来说是个沉重的负担。加锁并发控制能够节约系统资源，不过并发度不高，当争夺数据资源的情况较少发生时，乐观的优势更为明显。由于回滚操作可能频繁进行，乐观算法在处理时间限制比较严格的硬实时事务时，表现不如加锁。混合算法的提出，正是为了最大限度的利用多方面的优点。因此怎样针对混合算法进行合理有效设计才是我们应该着重研究的关键问题。
【参考文献】
[1]李昭原.数据库技术新进展第二版.清华出版社，2007.
[2]张禹.大流量实时数据库架构分析与实现.电子科技大学. 2007.
[3]Jisu Oh and Kyoung-Don Kang，An Approach for Real-Time Database Modeling and Performance Management， the 13th IEEE Real Time and Embedded Technology and Applications，2007.