中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
实时事务并发控制算法优化
作者: 王永炎
答辩日期: 2004
专业: 计算机应用技术
授予单位: 中国科学院中国科学软件研究所
授予地点: 中国科学软件研究所
学位: 博士
关键词: 实时数据库 ; 截止期 ; 错失率 ; 并发控制 ; 可串行性
其他题名: Optimization of Concurrency Control Algorithms in Real-Time Database Systems
摘要: 实时数据库系统处理具有时间约束的实时事务,其性能指标是错失截止期的事务所占的比率,即错失率。错失率越低,系统性能越好。实时事务按照截止期和价值确定的优先级进行调度,而传统数据库中的并发控制并没有考虑优先级。近年来很多研究人员致力于设计适合实时数据库系统的并发控制算法。实时事务并发控制算法不但需要保证数据库的一致性,同时还要尽量满足实时事务的截止期来降低系统的错失率。然而,现有的实时事务并发控制算法依然存在浪费的重启、浪费的等待、浪费的执行和不必要的重启等问题。针对这些资源浪费问题,本文着重研究了实时事务并发控制算法的优化问题。本文的主要工作体现在:1、提出了牺牲重启事务策略来减少浪费的执行。该方法能够提高实时数据库系统在负载较高时的性能。在系统负载较高时,牺牲重启事务策略能够让更有可能满足截止期的未重启过的事务优先执行,提高实时事务满足截止期的机会。模拟实验结果表明,基于牺牲重启事务策略的OCC-CLRTP算法能够有效地减少浪费的执行,降低系统的错失率。2、提出了动态调整执行顺序方法来避免不必要的重启,减少重启事务的个数,降低系统错失率。动态调整执行顺序方法能够动态地调整串行化顺序和读写顺序来寻找可串行化的调度,有效地避免不必要的重启。3、提出了基于提交范围(CommitSpace)的OCC-CS算法来实现动态调整执行顺序方法,并对OCC-CS算法进行了复杂度分析。限制半提交事务缓冲区大小方法可以减少OCC-CS算法额外消耗的系统内存,而且不会影响系统的性能。根据半提交选择法的不同,OCC-CS算法被分为CS-LEFT、CS-RIGHT、CS-ALT和CS-LRC算法。模拟实验结果表明,CS-ALT算法能够比基于动态调整串行化顺序方法的OCC一DATI算法更有效地避免不必要的重启,减少重启个数,提高实时数据库系统的性能。4、还提出了结合牺牲重启事务策略和动态调整执行顺序方法的CS-ALT-CLRTP算法来进一步提高实时数据库系统的性能。该算法不但能够减少系统负载较高时浪费的执行,同时还能够有效地避免不必要的重启,因此能够更大限度地降低系统的错失率,改进实时数据库系统的性能。模拟实验结果表明,CS-AUpCLRTP算法能够在所有系统负载下表现出最好的性能。5、设计并开发了一个具有很好的可扩展性和可配置性的实时数据库测试平台来分析和比较实时事务并发控制算法的性能。论文详细介绍了实时一数据库测试平台的系统框架,重点描述了系统中的实时事务并发控制的框架和实现,并月,深入论述了如何在基本框架下实现牺牲重启事务策略和动态调整执行顺序方法。
英文摘要: A Real-Time Database System (RTDBS) is a database system designed to process transactions with timing constraints, i.e. deadlines. In RTDBSs, the primary criterion is the percentage of the transactions that miss their deadlines, i.e. miss ratio. Lower the miss ratio, better the performance of RTDBSs. The transactions are scheduled by their priorities assigned according to their deadlines and values, but the concurrency control algorithms for traditional database systems are not priority-cognizant. In recent years, many researches have been devoted to designing appropriate concurrency control algorithms for RTDBSs, which need not only satisfy consistency requirements but also meet transaction timing constraints as much as possible to minimize the percentage of late transactions. There are still some problems in concurrency control algorithms for RTDBSs, such as wasted restart, wasted wait, wasted execution, unnecessary restart. In this thesis, the studies emphasize on optimization of concurrency control algorithms for real-time database systems. The main works are shown below: First, a new method, called sacrifice of restarted transactions which can improve the performance of RTDBSs under high load condition, is proposed to resolve wasted execution problem. Sacrifice of restarted transactions can give the transactions never restarted higher priorities under high load condition for the possibility of satisfying the deadlines of restarted transactions is lower than that of satisfying the deadlines of the transactions never restarted. The simulation results show that the algorithm based on sacrifice of the restarted transactions, called OCC-CLRTP, outperforms the previous algorithms. Second, a new method, called dynamic adjustment of execution order which can reduce the number of transaction restarts and minimize the miss ratio of RTDBSs, is proposed to resolve unnecessary restart problem. Dynamic adjustment of execution order can not only adjust the serialization order dynamically but also adjust the execution order of read and write operations dynamically to avoid the unnecessary restarts efficiently. Third, a new optimistic concurrency control algorithm based on dynamic adjustment of execution order using commit space in RTDBSs, called OCC-CS, is introduced and the complexity of this algorithm is analyzed. The extra memory spent in OCC-CS can be reduced by restricting the size of the semi-committed set which doesn't impact the performance of OCC-CS. Four algorithms are presented to implement the OCC-CS algorithm, including CS-LEFT, CS-RIGHT, CS-ALT and CS-LRC. The simulation results show that the CS-ALT algorithm can avoid more unnecessary restarts than the OCC-DATI algorithm based on dynamic adjustment of serialization order and outperforms OCC-DATI. Fourth, a new algorithm integrating sacrifice of restarted transactions and dynamic adjustment of execution order, called CS-ALT-CLRTP, is proposed to optimize the performance of RTDBSs. This algorithm can not only decrease the wasted execution under high load condition but also reduce the number of transaction restarts to improve the performance of RTDBSs. The simulation results show that the CS-ALT-CLRTP algorithm behaves the best under all load conditions. Finally, a real-time database test platform which is extensible and configurable is designed and developed to analysis and compare the concurrency control algorithms for RTDBSs. The architecture of the test platform is introduced and the architecture and implementation of concurrency control are discussed. Furthermore, how to implement sacrifice of restarted transactions and dynamic adjustment of execution order over the basic concurrency control architecture is discussed in this thesis.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6470
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
LW013939.pdf(2165KB)----限制开放-- 联系获取全文

Recommended Citation:
王永炎. 实时事务并发控制算法优化[D]. 中国科学软件研究所. 中国科学院中国科学软件研究所. 2004-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[王永炎]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[王永炎]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace