| 本文已被：浏览 4613次 下载 6188次 |
码上扫一扫！ |
|
|
| 基于混合粒度冲突检测的事务工作流调度算法 |
|
丁柯1,2, 魏峻1,2, 冯玉琳1,2
|
|
1.中国科学院软件研究所软件工程技术中心,北京,100080;2.中国科学院软件研究所计算机科学重点实验室,北京,100080
|
|
| 摘要: |
| 事务工作流由若干个平面事务组成,其执行满足松弛原子性.由于组成事务工作流的平面事务具有不同的完成特性,为了防止不可串行化的执行,现有的调度算法通常只允许一个活动工作流执行不可补偿事务,这大大限制了并发度.定义了基于事务类型和事务实例两种粒度的冲突关系,并提出了一种基于这两种粒度冲突检测的调度算法,保证了并发事务工作流的可串行化和可恢复执行.该算法从两个方面提高了并发度:一方面通过事务实例之间(细粒度)的冲突检测减少了工作流冲突的概率;另一方面通过事务类型之间(粗粒度)的冲突预测,允许多个将来不冲突的工作流执行不可补偿事务. |
| 关键词: 事务工作流 并发控制 恢复 调度算法 锁粒度 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant No.69833030 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant Nos.2001AA113010, 2001AA414020 (国家高技术研究发展计划); the National High Technology Development 973 Program of China under Grant No.G1999035807(国家重点基础研究发展规划(973)) |
|
| A Scheduling Protocol for Transactional Workflows Based on Mix-Grained Conflict Detection |
|
DING Ke,WEI Jun,FENG Yu-Lin
|
| Abstract: |
| A transactional workflow is composed of traditional flat transactions, and its execution has relaxed transactional atomicity. Due to different termination characteristics of transactions, only one workflow is allowed to execute non-compensatable transactions with current scheduling protocols. In this paper, two granularities of conflict based on transaction classes and transaction instances are defined, and a scheduling protocol by using both granularities of conflict detection is proposed. Besides generating serializable and recoverable schedules, this method provides a higher degree of concurrency in following two ways. On the one hand, the fine-grained locking mechanism based on transaction instances is used to reduce conflict possibility among concurrent workflows. On the other hand, the coarse-grained conflict mechanism based on transaction classes is used to predict future conflict among workflows, multiple workflows are therefore allowed to execute non-compensatable transactions if they will not conflict in predicated future execution. |
| Key words: transactional workflow concurrency control recovery scheduling protocol locking granularity |
