本文是一篇计算机论文，本文提出了面向云环境下不确定数据密集型工作流的动态分配框架及工作流执行前的调度预处理方法。基于进程代数表达式 E 以及数据依赖关系 D 给出了待调度的工作流模型，通过 CSi 和 TSp 给出了服务商和任务的候选关系，并进而形式化给出云工作流的调度问题描述和目标函数，最终提出了以工作流数据传输总量更少为优化目标的动态分配框架，以期通过执行前的预处理和执行期间的动态分配确定更优分配方案。
第一章 绪论
1.1研究背景和意义
工作流被定义为一种用于在计算机科学实验背景下对连贯性活动的抽象建模[1]。在日常研究中，工作流可以将复杂应用程序中对研究数据的收集、处理、分析以及可视化等一系列流程及其子流程的一些操作，按照研究数据之间的依赖关系和流程之间的逻辑关系进行抽象地描述，并让计算机可以在指定的约束条件下完成各流程以及子流程的自动或半自动过程[2]。数据密集型工作流作为一种辅助科学家进行科学研究的手段，实现了对研究工作中复杂任务及各任务间依赖关系的建模，能够在时间和空间等约束条件下完成数据的分析处理过程[3]。数据密集型工作流往往要获取、处理和传输大量的数据，目前在天气预报、高能物理、生物技术等领域，日常观测研究产生的数据量可能达到 T 量级甚至 P 量级，这些工作流程都是数据密集型的。数据密集型工作流的特点是在处理时需要对大规模数据进行信息获取、共享、更新和存储，涉及海量信息的处理和大规模计算[4]。
云计算为数据密集型工作流的高效执行提供了新的途径和方法。云计算可对海量的计算资源提供按需网络访问，可以通过较少的交互服务或工作上的管理支出来快速配置和发布[5]。这种计算模式，能够为小型到大型企业提供一系列交付解决方案，其灵活的模型允许以最小的成本为大容量数据提供计算能力和存储空间[6]。在云环境中，服务的提供商可以以弹性方式将其服务在云服务器上开展部署，而不是以更高的价格维护自己的服务器。也由于按需网络访问和易于共享的优势，云计算在工作流研究领域中日益流行。当工作流在不同数据中心组成的云环境下执行时，需要一种能够减少数据传输大小和降低执行成本的调度策略[7]，从而快速、有效的建立并运行工作流流程。
1.2国内外研究现状
为了解决复杂科学研究中计算的流程管理问题，工作流管理系统（Workflow Management Systems，WfMS）已成为辅助科学家进行科学探索的重要手段[10]。工作流管理系统伴随着云计算的发展拥有了更多的计算资源，设计优秀的调度算法更合理地利用这些计算资源是提高云工作流管理系统调度能力的核心问题[11]。
作为工作流管理系统的核心任务之一[12]，合理调度是解决执行效率、降低执行成本的重要解决方案。随着云环境中出现的服务越来越丰富，许多数据密集型工作流已在云服务器上执行[13,14]。为了在云环境中高效执行数据密集型工作流，重要的是将工作流中的任务合理地安排到合适的服务器[15]。许多研究人员一直在努力解决这个问题[16,17]。Moghadam 等人[18]提出了一种多目标优化模型和三级实现结构，以减少工作流完成时间，包括数据通信成本，等待时间和任务处理时间。Kumar 等人[19]提出了两种负载均衡的工作流调度算法，以最小化完工时间并最大化平均云利用率。Topcuoglu 等人[20,21]提出 HEFT 算法，主要的做法是将具有数据相关的任务都分配至能够最早执行完的服务商上，降低完成时间。田佳等人[22]提出了一种基于粒子群多线程算法，验证了该算法可以减少整体完成时间且效果较明显。Mirobi 等人[23]提出了基于工作流任务的数据相关性和虚拟机执行响应时间的动态调度，优化了执行时长。Rodriguez 等人[24]提出了一种粒子群优化算法，在最后期限约束条件下使总体执行成本最小化。崔等人[25]提出了一种数据局部感知工作流调度方法，其中考虑了数据传输时间和任务并行性，以改善执行时间。
第二章 相关背景知识介绍
2.1云计算
云计算利用互联网和虚拟机技术，以虚拟化形式提供随时可用、可重新配置和无处不在的计算资源，在这种范例中，用户利用互联网和远程数据中心来存储数据、执行应用。云计算模式可使用户享受到高效可扩展的计算服务，消除了用户硬件配置维护成本，目前已发展成为一种流行且高效的计算范例[33]。
云计算继承了网格计算和并行计算的优点并发扬了传统的计算模式。自从云计算面世以来，它便赢得了全球研究结构、政府单位的密切关注。同期，影响世界的众多科技公司也加入到云计算研究的队伍中，在 2007 年 8 月 IBM 发布了“蓝云”研究计划。谷歌则致力于推动云计算的发展，同年 10 月“全球云”发展计划问世，开启了同 IBM 一起推动云计算发展的新篇章。国际上众多的科研院校也纷纷加入进来，致力于云计算更好地服务 21 世纪。硅谷的其他科创公司也投身其中，至此，全球科技从事者都加入到研究云计算的热潮中。
虽然云计算已经成为目前国内外的研究热点，但是现在关于云计算却没有一个公认的、统一的定义。
Fosterl 等人[34]提出了一种新的观点，他们认为云计算是一个由规模经济驱动的大规模分布式计算范例。与传统意义上的分布式计算不同之处在于：（1）处理规模大、可扩展性强；（2）通过虚拟化和抽象化技术将存储、计算资源封装为一个抽象的实体，向客户提供不同级别的服务，服务可以动态配置和交付；（3）它受自由市场和经济发展的影响。
Vaquero 和 Caceres 等人[35]认为云计算是一种易于使用和访问的虚拟化计算资源，其中的资源可以动态配置，适应可变的负载，达到最佳的资源利用。它的特性是可伸缩性、按使用付费和虚拟性。这样的操作模式可以大大提高资源的重复利用率。
2.2工作流
2.2.1 工作流相关概念
工作流管理联盟 (workflow management coalition，简称 WfMC) 对工作流以及工作流管理系统参考模型进行了明确定义[43,44]。工作流定义为可以完全或部分自动化的业务流程。根据流程和业务规则，任务可以在不同的用户之间传递，文本和信息也可以在流通过程中执行[45]。这样，可以自动执行由这些任务组成的部分或全部业务流程，并可以提高工作的执行效率。
工作流中的任务是具有一定的相互关联性的，工作流本身是由这些任务组成的过程，它是一种业务过程[46]。工作流技术起源于 1980 年初期，已拥有三十多年的发展历史，先后经历了办公自动化、工作流管理、业务流管理、分布式工作流这几个阶段。
数据密集型工作流、计算密集型工作流、实例密集型工作流这三类工作流共同组成了分布式工作流。计算密集型模式是通过堆积尽可能多的处理器并且以峰值运算的速度为一定参考标准从而达到提高数据处理的峰值运算处理速度的一种计算模式。数据密集型模式则是一种以任务数据为核心的模式，在其执行的过程中，需要不断地获取、共享、更新、存储大规模的数据，也支持对这些数据进行处理的各种计算。数据密集型工作流和计算密集型工作流的处理对象通常都是针对复杂且巨型的单工作流的应用软件或科学实验。而实例密集型工作流更多的则是应用在能够同时拥有数量巨大的工作流实例并且每个实例相对来说都是比较简单的商业化应用中。
在云计算这一特殊的平台之上，云工作流会根据一定的标准和规则部分或者整体进行自动执行相关业务流程的建模、执行和资源的调度等工作。由于运行平台的差异，云工作流具有传统工作流所不具有的特点，其主要有以下几点：
（1）虚拟性：云计算资源是具有虚拟性的。云计算环境里的资源十分丰富，这些资源由计算性能、接口标准等不同软件资源构成，云工作流可以调度、查找、执行这些资源，这样也降低了用户访问资源的难度和复杂度。
（2）弹性：这里的弹性表现为以下两点：首先，用户可以实时获取所需资源。其次，资源被使用完毕后，用户可以无需等待整个业务流程的执行顺序直接释放掉资源。这也就是说，弹性是指云环境中资源具有按需分配的特点。
第三章 云环境下数据密集型工作流调度框架及预处理操作 ............................ 13
3.1引言.......................... 13
3.2云工作流调度模型 ..................................... 13
第四章 基于预处理结果的动态任务分配和实验分析 ................... 24
4.1基于冲突任务集和极大数据通路集的动态任务分配 .......................... 24
4.2实例验证 ................................... 26
第五章 系统设计与实现 ......................... 36
5.1系统分析与设计 ...................... 36
5.1.1 系统分析 ............................. 36
5.1.2 系统开发环境 ............................ 37
第五章 系统设计与实现
5.1系统分析与设计
5.1.1 系统分析
基于本文的研究，将工作流实现随机化生成，这样就可以保证输入数据的随机性，为了让随机生成的工作流进程代数具有正确性、可行性和合理性，可以通过限制选择分支的迭代次数，且并行分支的迭代次数也有一定的限制，使用该随机化生成的方法进行随机工作流的生成；将第三章的冲突任务集和极大数据通路的求取作为动态分配前的预处理操作应用于第四章的动态任务分配中，实现本文的分配方法，同时实现三种对比方法进行结果比对。结合上述两个部分设计并实现了本章的工作流调度系统。
为了展示本文研究结果，我们将调度的结果用用户界面显式地表现出来，做一个可视化展示。整个系统设计的应用环境是云环境下的计算场景，因此我们将系统部署在云服务器上。
图 5.1 给出了系统的物理结构，人们可以从终端访问工作流调度系统页面。在这个访问过程中，工作流调度系统所部署的云服务器会向数据库请求数据资源，服务器接收到数据后会计算并统计信息，然后，云服务器将用户所需信息返回给终端。
第六章 总结与展望
6.1总结
云环境可以向不同地点的使用者直接提供按需付费的服务，这样能够大大减少资源的浪费，节省了社会运行成本，为工作流的运行提供了良好支持。对于在云环境中运行的一些不确定数据密集型工作流，各任务之间往往存在海量数据传输，这将导致工作流执行时间和成本的急剧上升。尽管现有云工作流调度方法提供了很多有价值的研究成果，然而其对数据传输总量的优化操作大多需要提前准确预估各个任务之间的数据传输量。现有部分数据密集型工作流中涉及的具体传输量往往难以在执行前予以准确预估，仅凭任务之间存在但无明确定量的数据依赖关系完成工作流中各个任务的合理调度以减少数据传输总量存在着一定挑战。为此，本文提出了一种面向云环境下这类不确定数据密集型工作流的动态分配方法，主要工作有：
（1）提出了面向云环境下不确定数据密集型工作流的动态分配框架及工作流执行前的调度预处理方法。基于进程代数表达式 E 以及数据依赖关系 D 给出了待调度的工作流模型，通过 CSi 和 TSp 给出了服务商和任务的候选关系，并进而形式化给出云工作流的调度问题描述和目标函数，最终提出了以工作流数据传输总量更少为优化目标的动态分配框架，以期通过执行前的预处理和执行期间的动态分配确定更优分配方案。通过对进程代数表达式 E 转化而得的二叉树进行遍历以获取并行分支中各个任务的冲突任务集，以确保并行任务分属不同服务商执行，避免了同一服务商上的排队现象。提出了改进的 Warshall 算法对数据依赖关系 D进行遍历以获取各个任务的极大数据通路集合，以用于执行期间更优服务商的选择。
（2）提出了工作流执行期间基于冲突任务集和极大数据通路集的动态分配方法。根据三个基本原则从当前可触发执行的多个任务中确定任务的分配顺序，然后针对每个该待分配任务，结合执行期间实时生成的待传入数据量以及该任务的极大数据通路集合，从基于冲突任务集筛选过的候选服务商中择优选择一个最能减少数据传输的服务商，以最终获得整体更少的数据传输总量。设计并实现了比较实验以通过和三个方法的对比调度结果验证本文方法的有效性。以基于任务数 n、数据量差异度 δ、数据依赖边密度 ρ 这三组参数随机生成的工作流作为输入，获取本文方法和三种对比方法的不同调度结果并计算其各自的工作流数据传输总量，实验数据表明本文方法在减少数据总传输量上具有较大优势，能获得更优的调度方案。
参考文献（略）