一种基于QoS的事务工作流并发调度算法  

A QoS-Based Scheduling Algorithm for Concurrent Transactional Workflows

作　　者：任怡[1] 吴泉源[1] 戴华东[1] 吴庆波[1] 

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410073

出　　处：《电子学报》2007年第4期621-628,共8页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60603063);国家863高技术研究发展计划基金(No.2004AA1Z2240)

摘　　要：并发冲突引起的连锁夭折会降低系统性能,提出了一种基于QoS的事务工作流调度算法,该算法适应异构环境需求,支持基于QoS的延迟调度优化策略和SAFE集合扩充优化策略,可根据QoS参数调整相应的调度决策,在保证分布异构环境中复杂事务工作流并发正确性的同时减少连锁夭折.证明了算法不会引起循环等待和饿死现象,可保证调度的可串行性和可恢复性,性能模拟表明该算法适用于长期运行的事务工作流的并发调度,可有效减少连锁夭折,从而减少由此带来的性能损失.Data consistency must be kept to ensure correct concurrency when there are conflicts between concurrent transactional workflows. Cascading aborts caused by those conflicts will increase execution costs, especially for long running and heavypriced workflow instances. For complex transactional workflow applications in heterogeneous distributed environment, traditional concurrency control techniques can not reduce cascading aborts when the concurrency correctness is guaranteed. In this paper, we proposed a QoS-based dynamic schednling algorithm for transactional workflows. Matching requirements of heterogeneous environment,the algorithm allows different recovery policies for scheduled activities. Furthermore, it supports QoS-based deferred-scheduling policy and SAFE-set-enlarging policy.It can adjust scheduling decisions according to the reliability,execution time or price of an activity.It is proved that the proposed algorithm produces serializing and recoverable schedules;moreover,it will not lead to starvation. Performance analysis shows that the algorithm can reduce cascading aborts, thus can provide a high degree of concurrency.

关 键 词：事务工作流 并发控制和恢复 调度算法 QOS 连锁夭折 

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