动态调整串行化顺序算法的改进

论文摘要

随着实时数据库研究的逐步兴起，现实生活中对它的应用也越来越广泛，诸如电子商务、空中交通管制、程控电话交换、电力调度等应用都需要它的支持。然而，在实时数据库中还存在着许多仍未解决的问题，使得实时数据库如此难以实现的关键在于截止期和一致性这一对矛盾。实时数据库中最重要的特性就是实时性，而它的实时性能取决于很多因素，但对于一个给定的系统配置，决定实时性能的最基本因素是对数据存储进行调度的并发控制算法。近年来很多研究人员致力于设计适合实时数据库系统的并发控制算法。然而，现有的实时事务并发控制算法依然存在浪费的执行和不必要的重启等问题。本文着重研究了实时事务乐观并发控制算法的优化问题，在对动态调整串行化顺序的OCC-TI算法进行充分分析之后，给出了一个OCC-CPTI算法，该算法能解决一定程度上的不必要重启的问题。另外，以抛弃冲突事务策略为研究原型，根据其在不同的系统负载情况下表现出不同的性能，给出了一个条件虚抛弃策略，并将该策略与OCC-CPTI算法结合起来给出了OCC-CPTI-CVD算法，该算法可以有效地解决一些浪费的执行问题。最后通过仿真实验对改进后的算法进行了各方面的验证，从三种算法的错失率曲线图可以看出OCC-CPTI算法和OCC-CPTI-CVD算法的错失率的确少于OCC-TI算法，达到了优化的目的。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 国内外研究现状
• 1.3 实时数据库概述
• 1.3.1 时间特性
• 1.3.2 性能指标
• 1.4 实时数据库前沿课题与展望
• 1.5 课题的来源及主要工作
• 1.5.1 课题的来源及背景
• 1.5.2 论文主要工作
• 1.5.3 论文的组织
• 第2章 实时并发控制理论
• 2.1 并发控制理论
• 2.1.1 可串行化理论
• 2.1.2 可恢复性理论
• 2.2 并发控制协议
• 2.2.1 乐观并发控制
• 2.2.2 动态调整串行化顺序
• 2.3 实时事务并发控制
• 2.3.1 实时事务的性质
• 2.3.2 实时事务的属性及类别
• 2.3.3 实时事务并发执行的特点
• 2.3.4 实时事务的串行化规则
• 2.4 实时并发控制算法存在的问题
• 2.4.1 基于锁的并发控制算法存在的问题
• 2.4.2 乐观并发控制算法存在的问题
• 2.5 本章小结
• 第3章 乐观并发控制的冲突解决策略
• 3.1 OCC-TI算法描述
• 3.1.1 时间戳技术
• 3.1.2 算法基本思想
• 3.2 抛弃冲突事务策略
• 3.3 两种策略的适应条件
• 3.4 本章小结
• 第4章 动态调整串行化顺序算法的改进
• 4.1 OCC-TI算法的改进
• 4.1.1 OCC-TI算法缺点分析
• 4.1.2 OCC-CPTI算法思想
• 4.1.3 验证阶段算法描述
• 4.1.4 动态调整算法描述
• 4.1.5 实例说明
• 4.2 OCC-CPTI算法的优化
• 4.2.1 条件虚抛弃策略
• 4.2.2 OCC-CPTI-CVD算法
• 4.3 算法理论上的正确性
• 4.4 本章小结
• 第5章 实验结果及其分析
• 5.1 乐观实时并发控制模型
• 5.1.1 读写集合维护
• 5.1.2 冲突检测
• 5.1.3 冲突解决
• 5.1.4 验证队列管理
• 5.2 实验仿真模型
• 5.3 实验数据及参数
• 5.4 实验结果分析
• 5.5 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文和取得的科研成果
• 致谢