龙 泓，向 勇

（清华大学 计算机科学与技术系，北京100084）

0 引 言

传统工作流系统是server/client架构，优点是容易实现和管理，但其中心节点是性能瓶颈；且在跨地区的机构中部署这类工作流系统将无法分享各节点间的资源。由于这些缺陷，各种分布式工作流系统被设计实现出来，包括：网格 工 作 流 系 统 （GW）［1－2］、 多 代 理 工 作 流 系 统（MAW）［3－5］和 P2P工作流系统 （P2PW）［6］。这些系统的调度算法各有侧重。GW侧重于寻找恰当的业务流程拆分方法来尽可能发挥网格中间件并行处理优势。MAW的调度目标是实现多个代理平台间的负载均衡。这两者都是多中心架构，由若干中心节点来负责流程定义的解析和流程实例的调度。P2PW是完全分布式的，比前两者更稳定和具有扩展性，是云计算未来发展的方向。P2PW的调度算法会考虑各节点的自治性和P2P网络拓扑的动态性。本文提出的一个P2PW上的易扩展且支持多算法的流程实例调度框架。

1 相关工作

当前和分布式工作流调度算法相关的有：SwinDeW［7］、ADEPT［8－9］、BOINC［10］、WaitQueue［11］、PeerComp［12］和操作系统内核调度［13－14］的算法。首先，它们按调度依据可分为5类：优先级、活动的通信量、节点负载、时间量和参与者特征。使用优先级的有内核和 WaitQueue。例如Solaris内核对不同调度类线程使用的调度算法都基于多优先级反馈队列。而WaitQueue的Job Pool对活动按其rank值来排序，也是优先级调度。考虑活动通信量的有Wait－Queue和ADEPT。前者在计算活动的rank值时使用了活动的时限。基于节点负载调度的是SwinDeW、WaitQueue和PeerComp。PeerComp使用的是每个执行节点的可用计算时间；WaitQueue使用的是任务在集群队列的等待时间，其实就是每个集群的队列长度。……