支持移动合作实时事务的一种新的协同检验点算法

现有的协同检验点方法在移动环境中会带来较大的检验点过程延时 ,不能很好地支持实时事务处理 .提出了一种新的协同并行检验点方法 ,在正常的消息传输过程中 ,通过一点额外的带宽传送事务间检验点依赖关系 ;在某一事务记检验点时 ,尽可能地同时通知相关的事务记检验点 .实验表明 ,该算法对网络带宽没有明显的增加 ,而能大大降低事务记检验点的延时 ,使系统中超截止期的事务比例大大降低     

支持分布式合作实时事务处理的协同检验点方法

在实时事务执行时,事务故障或数据竞争会导致事务重启,为减少事务重启损失的工作量,可以采用检验点技术保证事务的时间正确性．在一类分布式实时数据库应用中,不同结点的事务通过消息交换形成合作关系,为保证合作事务间的全局一致性,当某一事务记检验点时,相关事务也要记检验点．传统协同检验点方法没有考虑应用的定时约束,不能很好地支持分布式合作实时事务处理．该文提出了一种基于图论的协同检验点方法,利用在每个计算结点上为每个合作事务集维护的局部有向图,使用一个基于图论的计算过程标识出应记检验点的事务,该方法既具有最小协同检验点特性,又使全局检验点的时延最小．实验表明该算法减少了全局检验点时延,有利于实时事务截止期的满足．     

分布式实时事务提交协议

在分布式实时数据库系统中,保证事务原子性的唯一途径是研究和开发出一个实时的原子提交协议．首先详细分析了事务因数据访问冲突而形成的各种依赖关系,在此基础上提出了实时的原子乐观提交协议——2SC协议,该协议减少了事务的等待时间,提高了事务的并发度,且能无缝地和现有的并发控制协议集成在一起,保证事务的可串行化和原子性．通过模拟实验研究表明,采用该协议能够减少超过截止期的事务数目。     

一种分布式实时事务调度算法

传统的乐观并发控制策略利用了一些不必要的事务重启来保证数据的一致性，事务重启能够极大的增加系统载荷以及加强资源和数据的竞争，在分布式环境下，由于系统的复杂性和较高的通讯开销加剧了该问题．针对该问题本文提出了一种靳的乐观并发控制策略，通过动态调整事务串行化执行顺序来避免不必要的事务重启．当把这种新的并发控制策略在分布式实时环境中实现时，考虑到分布式事务的实时性要求，本文提出把写阶段从临界区中分离出来的方法，并用顺序加锁的策略来保证分布式事务执行的正确性，最后给出了该实现方法的正确性证明．     

基于时间戳的并行实时事务调度策略

传统并行事务处理方法不适用于实时数据库,对几种相关事务调度策略进行比较,提出一种基于时间戳的并行实时事务调度策略TS-PRTTS(Timestamp based Parallel Real-Time Transaction Scheduling),采用M／G／1队列模型,利用时间戳控制子事务同步．实验证明,该策略能较好协调同步控制与通信代价矛盾,在系统负荷较重以及数据倾斜、访问倾斜问题较突出时具有良好的性能。     

分布式实时事务提交处理

由于提交处理的复杂性,分布式实时事务很难满足其截止期.提出了一种新的提交协议A2SC(主动的双空间提交),它适合于分布式实时事务提交处理的需要.分析了由于数据冲突访问而形成的各种依赖关系.当处于准备状态的事务和处于提交状态的事务发生数据冲突访问时,A2SC允许处于执行状态的事务在一种控制的方式下乐观地访问锁住的数据.当处于准备状态的事务夭折时,仅仅只有其夭折依赖集中的事务夭折.进一步提出了\"没有结果的运行\"的观念.当一个事务发现它是没有结果的允许时,它将主动夭折.进行了广泛的模拟实验比较A2SC和其它协议比如基准协议、PROMPT和DDCR的性能.模拟结果表明A2SC在最小化错过截止期的事务数方面较成功,因此A2SC适合于高性能分布式实时事务.     

一种易于并行实现的全局运动估计算法

提出一种新的全局运动匹配算法,该算法可高效地将匹配任务分配在多个处理器上,通过协处理器并行工作,最终实现高质量的编码视频。     

MDBS中一种改进的并发事务调度算法

MDBS中并发事务的调度策略必须满足可串行化准则,论文主要分析以事务提交图为中心的调度算法TM2,虽然保证了全局事务提交顺序的可串行化,但在提交时才进行冲突检测方式存在缺点,提出改进后的事务调度算法TM3不仅保证了全局事务的可串行化和防止了全局死锁的发生,还提高了全局事务执行的并发度。最后通过实验在数据库加速引擎中进行模拟,对比了两种调度算法的性能。     

移动分布式实时事务实时原子提交

形式地给出了移动分布式实时事务实时原子提交协议的定义,在此基础上提出了适合于移动分布式实时事务的实时原子提交协议：一阶段实时原子提交协议(1PRACP)。1PRACP通过参与者与协调者的一次消息交换,在一个阶段完成移动分布式实时事务提交活动;结合超时恢复处理协议,1PRACP能避免由于站点故障或网络通信链路故障而导致的阻塞。对1PRACP进行了性能比较和评测,显示了它在各方面的优越性。     

一种新的实时事务并发控制方法

本文提出一种新的实时事务并发控制方法，并对其性能进行了模拟评测；与锁式协议，乐观协议，基于时间戳的协议相比，它可以获得更新的并发度，与诸如ε－可串行比、△－可串行化等一致性的放松可串行化并发控制技术相比，它维护强一致性，保证严格可串行化。     

Linux中检查点(Checkpoint)的核心支持——ckpt文件系统的设计

检查点(Checkpoint)是一种软件容错机制,它的目的是提高系统可靠性、减少运算损失,同时检查点机制也是并行系统中进程迁移和负载平衡的基础。在一些检查点系统中,由于对进程的状态检查/状态恢复只具有用户级支持,所以有许多局限性,比如不能完成进程外部状态检查。而在作者的设计与实现中由于具有了核心级的支持,所以能够充分地克服这些局限性。     

一种优化的分布式系统的失效恢复策略

本文对确定性进程组的分布式系统的失效恢复策略做了深入的研究,独到地提出了应用数据流分析来静态地计算进程的最小备查点数据集的方法。     

基于检测点设置依赖图和属性表的卷回恢复算法

为了解决检测点设置过程中的Domino效应问题及卷回恢复过程中的活锁问题,并最大限度地减小时间开销,提出了基于检测点设置依赖图和属性表的卷回恢复算法。同以前的算法相比较,该算法一方面节省了用于进程之间同步的时间开销,另一方面检测点设置及卷回过程中涉及少量的相关进程。对该算法的正确性进行了证明。     

主动实时嵌套事务的正确性

传统数据库通过并发控制协议及事务的恢复机制来保证事务的正确性。在主动实时数据库系统中,为了更好地支持应用,人们提出并实现了嵌套事务模型。主动实时嵌套事务的正确性比传统的原子事务更复杂。本文详细分析了主动实时嵌套事务的正确性,包括逻辑正确性、时间正确性、结构相关(正确)性及事务的行为正确性,基于事务的经历模型给出这些正确性的定义,为主动实时嵌套事务的正确性实现提供了理论基础。     

实时分布系统中Out-Tree任务的调度与检查点策略

针对实时分布系统中的Out-Tree任务,提出了一种启发式的调度算（HSA-OT）,并开发了一种多处理机上的最优检查点策略。该调度算法能够保证任务的调度长度最小,所需处理器数目尽量少,没有处理机间通信开销。该检查点策略没有检查点全局一致性开销,可保证各处理机的失效率最低。     

An environment for integrated development and evaluation of real-time distributed database systems

Real-time database systems must maintain consistency while minimizing the number of transactions that miss the deadline. To satisfy both the consistency and real-time constraints, there is the need to integrate synchronization protocols with real-time priority scheduling protocols. One of the reasons for the difficulty in developing and evaluating database synchronization techniques is that it takes a long time to develop a system, and evaluation is complicated because it involves a large number of system parameters that may change dynamically. This paper describes an environment for investigating distributed real-time database systems. The environment is based on a concurrent programming kernel that supports the creation, blocking, and termination of processes, as well as scheduling and interprocess communication. The contribution of the paper is the introduction of a new approach to system development that utilizes a module library of reusable components to satisfy three major goals: modularity, flexibility, and extensibility. In addition, experiments for real-time concurrency control techniques are presented to illustrate the effectiveness of the environment.This work was supported in part by ONR contract # NOOO14-88-K-0245, by DOE contract # DEFG05-88-ER25063, by CIT contract # CIT-INF-90-011, and by IBM Federal Systems Division.