实例密集型商务工作流任务调度与分配策略研究

摘要

随着电子商务的迅速发展，商业和政府机构通常需要处理大量的服务请求，这些服务请求通常是一个个较小的业务流程，需要在有限制的时间内完成处理，为有时序限制的实例密集型商务工作流。当前商业领域的数据量越来越大，如何确保在时序限制内大量实例密集型业务流程的实时完成已成为对服务质量具有挑战性的问题，因为任何的时间延误都会造成诸如用户满意度、经济损失甚至是处罚等严重的后果。云计算的迅速发展为商务工作流的处理带来了很大的机遇，然而，由于云服务的动态特性，缺少服务质量管理策略成为其大范围部署的严重障碍。对于当今利用云计算资源的软件系统来说，对有时序限制的大量处理过程提供满意的服务质量是一个关键的研究问题。考虑这些复杂的实例密集型商务流程，确保在有时间限制的范围内按时完成所有任务的调度对服务质量的提高有很大的影响;对所有任务的运行状况进行有效的监控，提高任务分配的效率和可靠性，对于商业应用来说则是个很重要的标准。
　　本文主要的研究工作概况如下：
　　(1)本文首先提出了几种调度模型，粗粒度、细粒度、资源池调度通用模型和理论最短执行时间调度模型。由于商业流程通常是一个较小的工作流实例，每个实例的执行时间通常在某一固定的区间内。对于不同的实例，其起始和结束时间通常有一定的要求，并且不同的实例有时序关系，因此提出使用区间调度的思想来处理上述特性。商业流程中，由于不同的任务存在着时序依赖关系，可以很好的利用区间调度方法将多个任务分配至不同处理器上执行，为商务工作流程的并行化调度提供基础。
　　(2)在区间调度基础上，利用有向无环图（Directed Acyclic Graph，DAG）模型，考虑任务各自的时序限制，本文深入研究有多个串行和并行子活动的DAG任务实时调度。给出了一种有效的DAG任务调度模型，将调度任务分成串行和可并行调度部分，提取DAG任务的有效主路径，然后对任务按有效主路径并行展开，根据任务的执行截止期限与其子活动的时序限制，提出DAG任务的拉伸调度策略，使多个任务调度时，尽可能减少对处理器资源的占用，保证其他任务能有效的进行调度，多个任务各自都可以满足时序限制的要求。
　　(3)针对无单个任务响应时限约束的流程，将商业任务完全拉伸后，本文提出一种动态优先权调度策略(DPS)。主要基于Min-Min启发式算法和贪心思想策略，将整个商务工作流的调度过程中的所有调度任务按使用的云处理器的数量进行分批处理，对每批调度任务所需的调度时间进行预测并排序，按任务所需的执行时间，将不同执行时长的任务赋予不同的优先级，在调度过程中，保持各云处理器执行状态的一致性。DPS算法的时间复杂度为O(m2n)，在效率上比Min-Min提高很多。通过与理论最短执行时间相比，二者的比值能够达到98.5％以上，特别是当调度的数据量达到1，000，000个任务时，该比值能到达接近99.9％，充分证明了DPS算法对于大量任务是一个可以获得接近最优的调度算法。
　　(4)为了实现对大量商业流程的调度过程进行监控，判断任务执行是否会出现时序冲突，本文提出一种商务工作流调度过程监控方案。沿着商务工作流执行的时间轴将整个调度过程分成若干等份，对设置的时间点进行检测保证工作流的正常运行，并提出一种动态时间检测点选择策略。该策略在选择时间检测点的时候，可以依据商务工作流前序检测的状态，判断调度过程时间冗余情况，尽可能的在保证时序一致性的前提下，减少检测点总体的数量，从而减少对工作流执行过程监听的开销。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 主要研究内容

1．3 主要创新点

1．4 论文结构

第2章 商务工作流程及其应用

2．1 引言

2．2 商务工作流程概述

2．2．1 相关概念

2．2．2 工作流的构成

2．3 基于云计算的商务工作流应用

2．4 典型商务工作流应用案例和问题分析

2．4．1 响应时间优先的证券交易调度过程

2．4．2 系统吞吐量优先的证券清算调度过程

2．4．3 问题分析

2．5 本章小结

第3章 商业流程多任务区间调度

3．1 引言

3．2 任务区间关系模型

3．3 多任务区间重叠与兼容性判定

3．4 最优化区间调度

3．4．1 完成任务最多的区间调度

3．4．2 完成任务量最大的区间调度

3．5 本章小结

第4章 基于有向无环图的实时任务拉伸调度

4．1 引言

4．2 基于并行调度的DAG任务模型

4．2．1 基于并行调度的DAG任务的通用模型

4．2．2 基于并行调度的DAG任务模型的实例

4．3 DAG任务的有效主路径提取策略

4．3．1 有效主路径提取策略

4．3．2 有效主路径提取实例

4．4 基于任务执行截止期限的拉伸调度策略

4．4．1 DAG任务执行完成时间计算

4．4．2 基于有效主路径的拉伸策略

4．4．3 拉伸调度应用

4．5 拉伸调度仿真与实例验证

4．5．1 拉伸调度实例验证

4．5．2 大规模拉伸调度仿真验证

4．6 本章小结

第5章 基于吞吐量优先的动态优先权策略

5．1 引言

5．2 商务工作流多步骤任务调度模型

5．2．1 基于任务的商务工作流通用调度模型

5．2．2 基于事件的商务工作流通用调度模型

5．2．3 基于事件资源池的通用调度模型

5．2．4 理论最短执行时间调度模型

5．2．5 各种调度模型的比较

5．3 商务工作流程调度策略

5．3．1 传统方法在商务工作流程调度中的应用

5．3．2 最短任务最早分配策略

5．3．3 动态优先权调度策略

5．4 不同调度策略的模拟与比较

5．4．1 一般情况下的仿真与比较

5．4．2 特定情况的仿真模拟

5．5 本章小结

第6章 基于动态检测点选择的调度任务监控策略

6．1 引言

6．2 商务工作流调度过程监控与相关概念

6．3 动态检测点选择策略

6．4 商业流程执行过程监控仿真

6．5 本章小结

第7章 总结与展望

7．1 总结

7．2 展望

参考文献

致谢

在读期间取得的研究成果