论文部分内容阅读
近年来，云计算应用的高速发展和用户群体的不断扩大，导致云数据中心需要合理地对用户的各种应用任务进行管理，给数据中心的任务处理带来了巨大的压力，因此，如何对大量任务进行合理、高效的调度和管理，维持相对均衡的负载水平，是云计算急需解决的关键问题。
面对云计算虚拟化、高可伸缩性、以及需要满足用户需求兼顾服务提供商利益等特点，传统的任务调度方法已经无法为云数据中心提供准确的调度算法，因此，研究面向云计算的任务优化调度模型及算法具有重要的理论价值和现实意义。
在深入分析云计算环境下任务调度的特点以及面临的主要问题，本文从云计算任务优化调度体系架构、云数据中心基础层、应用层以及云工作流对于任务的调度问题展开深入研究，主要研究工作和研究成果如下:
由于云计算的节点难免会发生故障，为了提供良好的云计算环境，需要采取合适的容错措施，构建了新的任务优化调度体系架构，不同于其它云计算架构的设计，需要用户给定特定前提再进行调度研究，新的任务优化调度体系架构只需根据具体调度要求进行参数实例化;同时，在体系架构中引入了动态的数据副本机制，提出了具体的动态副本管理算法DRA(Dynamic Replica Algorithm，DRA)，随着副本数量和负载率的增加，提出的DRA算法与具有固定副本数量的复制算法FRN(Fix Replica Number, FRN)、局部动态的复制算法LD(Local Dynamic，LD)对比降低了系统延时和带宽消耗，且随着用户任务数量增加，DRA算法在保证较短平均任务完成时间基础上，减少了创建副本资源消耗。
针对云计算系统中单个数据中心在基础层任务优化调度时，用户对云计算资源的需求多样性和多指标约束问题，采用新的基于动态副本机制的云计算任务优化调度体系架构，以马尔可夫理论为研究基础，建立时间-费用模型，提出了遗传蚁群融合算法的任务优化调度算法。通过重新设计遗传算法中交叉因子，提升了算法在全局搜索时收敛效果，利用改进的遗传算法的全局搜索结果，作为下一步蚁群优化算法求解任务优化调度时的信息素初始值，产生最终的云数据中心基础层任务优化调度策略。实验结果表明，提出的基于遗传蚁群融合算法MGAA(Modified Genetic Ant Algorithm，MGAA)的任务调度策略较已有的改进的遗传算法LGA(Load Balancing Genetic Algorithm, LGA)、BIGA(Buffer Setting Improved Genetic Algorithm，BIGA)缩短了任务执行时间，降低任务执行费用，并且提高了CPU、磁盘和内存利用率。
在云计算系统单个数据中心的应用层中，因云服务的市场机制化，针对云服务提供商的降低云服务成本、提高云服务收益的迫切需求，提出基于拉格朗日乘数法优化解的任务调度算法MRA(Modified Resource Algorithm, MRA)。以纳什均衡理论、排队论作为研究的理论基础，通过建立服务响应时间的任务队列调度模型，对任务调度问题进行优化求解。同时，在单个数据中心的应用层中，兼顾用户的利益，为了保障资源分配更加合理、公平，建立了自适应的完成时间感知的任务分配模型，并提出应用梯度投影方法求得优化解的调度算法GP(Gradient Projection, GP)，考虑用户对于不同应用任务的执行顺序和执行时间的要求，利用纳什均衡理论求解具有优先级和完成时间限制的任务优化调度问题。实验结果表明，MRA算法可以收敛到均衡解，优化任务调度、资源的分配;提出的GP算法在面对不同优先级的任务执行时，其收敛性优于公平调度算法FS(Fair Schedule，FS)、随机调度算法RS(Random Schedule，RS)和最早-完成时间优先算法EDF(Earliest Deadline First, EDF)，系统的资源利用率提高，且任务的执行延迟明显降低。
针对任务具有关联关系的多数据中心任务调度统一规划和协调管理的问题，将多数据中心的任务调度分为两个阶段。第一阶段，根据任务的关联关系，结合工作流技术，并利用有向无环图DAG(Directed Acyclic Graph, DAG)进行任务的关联关系表示，提出了改进的粒子群算法MPSO(Modified Particle Swarm Optimization, MPSO)。在改进的粒子群算法中，微粒速度位移及权重参数进行了改进，促使微粒在小范围内进行挖掘全局最好位置，以转化为满足约束要求的多目标优化解;同时，引入Pareto多目标优化方法，进行具有约束条件的优化问题求解。在第二阶段，考虑多数据中心系统间的负载情况，提出具有负载感知的任务调度算法，算法中引入负载感知参数，以调整任务执行时的系统负载状况。实验结果表明，在系统中具有关联任务执行的情况下，利用DAG，结合工作流的任务调度，MPSO算法在任务执行过程中花费的时间、费用均小于最早结束时间算法HEFT(Earliest Finish Time，HEFT)、局部优化的模拟退火算法SAA(Simulate Anneal Algorithm，SAA)，而具有负载感知的任务调度算法较没有负载感知的调度算法提高了系统中CPU、内存和磁盘利用率，保证了任务按序高效执行。
面对云计算虚拟化、高可伸缩性、以及需要满足用户需求兼顾服务提供商利益等特点，传统的任务调度方法已经无法为云数据中心提供准确的调度算法，因此，研究面向云计算的任务优化调度模型及算法具有重要的理论价值和现实意义。
在深入分析云计算环境下任务调度的特点以及面临的主要问题，本文从云计算任务优化调度体系架构、云数据中心基础层、应用层以及云工作流对于任务的调度问题展开深入研究，主要研究工作和研究成果如下:
由于云计算的节点难免会发生故障，为了提供良好的云计算环境，需要采取合适的容错措施，构建了新的任务优化调度体系架构，不同于其它云计算架构的设计，需要用户给定特定前提再进行调度研究，新的任务优化调度体系架构只需根据具体调度要求进行参数实例化;同时，在体系架构中引入了动态的数据副本机制，提出了具体的动态副本管理算法DRA(Dynamic Replica Algorithm，DRA)，随着副本数量和负载率的增加，提出的DRA算法与具有固定副本数量的复制算法FRN(Fix Replica Number, FRN)、局部动态的复制算法LD(Local Dynamic，LD)对比降低了系统延时和带宽消耗，且随着用户任务数量增加，DRA算法在保证较短平均任务完成时间基础上，减少了创建副本资源消耗。
针对云计算系统中单个数据中心在基础层任务优化调度时，用户对云计算资源的需求多样性和多指标约束问题，采用新的基于动态副本机制的云计算任务优化调度体系架构，以马尔可夫理论为研究基础，建立时间-费用模型，提出了遗传蚁群融合算法的任务优化调度算法。通过重新设计遗传算法中交叉因子，提升了算法在全局搜索时收敛效果，利用改进的遗传算法的全局搜索结果，作为下一步蚁群优化算法求解任务优化调度时的信息素初始值，产生最终的云数据中心基础层任务优化调度策略。实验结果表明，提出的基于遗传蚁群融合算法MGAA(Modified Genetic Ant Algorithm，MGAA)的任务调度策略较已有的改进的遗传算法LGA(Load Balancing Genetic Algorithm, LGA)、BIGA(Buffer Setting Improved Genetic Algorithm，BIGA)缩短了任务执行时间，降低任务执行费用，并且提高了CPU、磁盘和内存利用率。
在云计算系统单个数据中心的应用层中，因云服务的市场机制化，针对云服务提供商的降低云服务成本、提高云服务收益的迫切需求，提出基于拉格朗日乘数法优化解的任务调度算法MRA(Modified Resource Algorithm, MRA)。以纳什均衡理论、排队论作为研究的理论基础，通过建立服务响应时间的任务队列调度模型，对任务调度问题进行优化求解。同时，在单个数据中心的应用层中，兼顾用户的利益，为了保障资源分配更加合理、公平，建立了自适应的完成时间感知的任务分配模型，并提出应用梯度投影方法求得优化解的调度算法GP(Gradient Projection, GP)，考虑用户对于不同应用任务的执行顺序和执行时间的要求，利用纳什均衡理论求解具有优先级和完成时间限制的任务优化调度问题。实验结果表明，MRA算法可以收敛到均衡解，优化任务调度、资源的分配;提出的GP算法在面对不同优先级的任务执行时，其收敛性优于公平调度算法FS(Fair Schedule，FS)、随机调度算法RS(Random Schedule，RS)和最早-完成时间优先算法EDF(Earliest Deadline First, EDF)，系统的资源利用率提高，且任务的执行延迟明显降低。
针对任务具有关联关系的多数据中心任务调度统一规划和协调管理的问题，将多数据中心的任务调度分为两个阶段。第一阶段，根据任务的关联关系，结合工作流技术，并利用有向无环图DAG(Directed Acyclic Graph, DAG)进行任务的关联关系表示，提出了改进的粒子群算法MPSO(Modified Particle Swarm Optimization, MPSO)。在改进的粒子群算法中，微粒速度位移及权重参数进行了改进，促使微粒在小范围内进行挖掘全局最好位置，以转化为满足约束要求的多目标优化解;同时，引入Pareto多目标优化方法，进行具有约束条件的优化问题求解。在第二阶段，考虑多数据中心系统间的负载情况，提出具有负载感知的任务调度算法，算法中引入负载感知参数，以调整任务执行时的系统负载状况。实验结果表明，在系统中具有关联任务执行的情况下，利用DAG，结合工作流的任务调度，MPSO算法在任务执行过程中花费的时间、费用均小于最早结束时间算法HEFT(Earliest Finish Time，HEFT)、局部优化的模拟退火算法SAA(Simulate Anneal Algorithm，SAA)，而具有负载感知的任务调度算法较没有负载感知的调度算法提高了系统中CPU、内存和磁盘利用率，保证了任务按序高效执行。