基于混合粒度冲突检测的事务工作流调度算法  

A Scheduling Protocol for Transactional Workflows Based on Mix-Grained Conflict Detection

作　　者：丁柯[1,2] 魏峻[1,2] 冯玉琳[1,2] 

机构地区：[1]中国科学院软件研究所计算机科学重点实验室,北京100080 [2]中国科学院软件研究所软件工程技术中心,北京100080

出　　处：《软件学报》2003年第3期369-375,共7页Journal of Software

基　　金：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

摘　　要：事务工作流由若干个平面事务组成,其执行满足松弛原子性.由于组成事务工作流的平面事务具有不同的完成特性,为了防止不可串行化的执行,现有的调度算法通常只允许一个活动工作流执行不可补偿事务,这大大限制了并发度.定义了基于事务类型和事务实例两种粒度的冲突关系,并提出了一种基于这两种粒度冲突检测的调度算法,保证了并发事务工作流的可串行化和可恢复执行.该算法从两个方面提高了并发度:一方面通过事务实例之间(细粒度)的冲突检测减少了工作流冲突的概率;另一方面通过事务类型之间(粗粒度)的冲突预测,允许多个将来不冲突的工作流执行不可补偿事务.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.

关 键 词：混合粒度冲突检测 事务工作流调度算法 计算机软件 并发控制 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]