【作者】 郑美光；

【导师】 胡志刚；

【作者基本信息】 中南大学 ， 计算机应用技术， 2011， 博士

【摘要】 随着网格系统逐步从科研领域走向更加广泛的商业领域,面向服务的网格已成为主流趋势,网格任务调度的研究重点是“提供非凡的服务质量保证(Non-trivial QoS Guarantee)"。网格系统提供QoS保证能力时明确区分了应用QOS指标和系统QoS指标,当前面向QoS的调度策略通常单独考虑网格应用的QoS需求或仅仅优化网格系统的目标,亟需一个既能保障应用QoS指标又能适应网格系统内在需求的合理、高效和公平的调度决策机制。因此,面向QoS的网格应用—系统平衡型优化调度研究具有良好理论价值和实用意义。网格系统和网格应用从各自的角度提出不同的QoS指标,之间不存在简单直接映射关系,优化系统QoS指标的策略在实际中可能无法满足用户所提出的QOS需求,优化应用QoS指标则可能损害系统性能参数。基于对应用与系统双方QoS指标之间关联特性的深入分析,本文开展平衡应用与系统QoS指标的网格优化调度研究,重点考虑的应用QoS指标包括用户通常最关注的应用完成时间和执行费用,系统QoS指标则包括系统负载均衡程度与计算经济理论中最常用的系统目标—系统总收益,以期实现用户QoS保障并满足网格系统的内在需求。论文的主要工作和创新如下：(1)面向通用网格应用的平衡型优化调度策略针对网格应用和网格系统双方的QoS需求存在一定冲突,提出了一种基于序贯博弈的平衡型优化策略SGPUBO。 SGPUBO以应用完成时间和系统的负载均衡程度为优化目标,将调度过程分为活动分发和处理器分配两个阶段,首先按照资源性能进行活动分发,之后基于已接纳活动的执行情况在资源内部实施处理器分配,通过两个阶段相互迭代求解获得最终分配方案。通过大量实验分析可知：SGPUBO具有集中分配特性,基于该特性,通过采用站点一活动队列的截尾处理方案,提出了可进一步优化应用完成时间的SGPUBOwTM算法。实验结果表明,与经典调度算法Min-Min和Sufferage相比,SGPUBOwTM可在短时间内求解处理大规模网格应用调度问题,并且在网格应用的完成时间和网格系统的负载均衡等方面都有更好的表现。(2)面向工作流应用的平衡型优化调度策略针对经典的工作流逆向分层方案中均匀分配截止期宽裕时间将造成宽裕时间浪费这一缺陷,提出了一个非均匀浮差的工作流截止期分配预处理方案DBL_UnevenExt。为了优化截止期分配的活动选择,DBL_UnevenExt基于“服务级差性价比”实施截止期分配,并参考“服务级差”中“时间性能差”的分配需求,以非均匀方式分配工作流截止期宽裕时间。实验表明,DBL_UnevenExt的截止期分配方案可将截止期宽裕时间分配给更适当的活动,扩展了工作流应用子任务的费用优化区间。在采用DBL_UnevenExt实施工作流预处理的基础上,对每一个子工作流以实时模式进行基于序贯博弈的平衡型优化,进而研究提出了一个费用目标下工作流应用的平衡型优化算法DBLUCUBO。实验结果表明：DBLUCUBO在工作流执行费用和网格系统的负载均衡程度方面的性能表现显著优于同类经典工作流调度算法。(3)面向全局收益优化的管理域内平衡型调度策略针对当前管理域内的调度大多沿用传统分布式系统的本地调度器、不能很好地适应商业应用环境中对公平性和合理性的新需求这一问题,提出了一种最大化管理域全局收益的域内调度策略CGBMA。该策略在建立管理域内的合作博弈模型并定义管理域的“平衡状态”基础上,通过理论分析得出管理域系统处于平衡状态时可以实现全局收益最大的结论。据此,将管理域内的调度问题转化为任务零售价、任务市场价和任务分配量的更新迭代过程。实验结果表明：与Proportional Share、Double Auction算法相比,CGBMA可实现管理域的最大全局收益。针对上述实验分析同时发现,当任务规模增大时,CGBMA的市场淘汰特性将愈加明显而致使负载不均衡加剧。为此,在CGBMA算法的基础上进一步实施负载均衡优化,依据资源的负载情况来动态调整合作博弈模型的关键参数,并提出了一个全局收益优化的负载平衡调度算法CGBMAFI。通过大量实验表明,管理域采用CGBMAFI进行调度时,本身可实现全局收益的优化,而用户则可以获得更优的应用执行时间和性价比。更多还原

【Abstract】 With Grid technologies progressing towards a commercial and service-oriented paradigam, research focus is shifted to investigate how to ensure Grid to provide non-trivial Quality of Service (QoS). QoS guarantee in Gird makes a clear distinction between user’s metrics and system’s metrics. The existing QoS-oriented scheduling approaches usually are dedicated to certain user’s criteria or only pursuit system-centric performance criteria. To this end, it is urgent to design a reasonable, effiecient and fair scheduling approach which could satisfy users’QoS demands and also meet systems’internal requirements. Therefore, QoS-based application-system balanced optimization scheduling in Grids becomes an important issue with theoretical and practical value.The characteristics of Grid QoS such as diversity and interplay bring up great challenge for QoS-oriented schechduling, especially sometimes QoS of user and system conflict. In order to guarantee and improve the QoS requirements of user and system in Grid environment, analyzing current user’s most concerned criteria including time and cost, and aiming at system’s criteria including workload fairness and global benefit which is usually the most important criteria in economy theory, this thesis deeply investigates efficient and effective Grid application-system balanced scheduling mechanisms. The main research content and contributions are as follows:1. Balanced-based optimization strategy for scheduling general Grid applicationAccording to the fact that QoS requirements of user and system usually remain conflicts, a sequential-game-based balanced optimization scheduling scheme which optimizes the criteria of application’s finishing time and Grid system’s workload fairness, is presented. SGPUBO gets scheduling solution in a sequential game, which is turned into an iteration of activity distribution and processor allocation. In the first phase, activities’exectuted performances are compared among different sites, and in the second phase, processors are allocated on the basis of the conditions of admitting activities at each site. The simulation experimental results show the allocation concentration tendency of SGPUBO. Applying Tail Migration strategy, SGPUBOwTM is proposed which could achieve better performance on makespan. Comparised with two traditional leading algorithms Min-Min and Sufferage on performance, SGPUBOwTM leads to better application time and system load fairness in an efficient way.2. Balanced-based Optimization strategy for scheduling workflow applicationConsidering the fact that traditional workflow preprocess scheme DBL, which allocates the total time float by an equal means, could lead to waste of Deadline Remaining, an uneven slack deadline assignment scheme based on DBL(DBL_UnevenExt) scheme is proposed. The DBL_UnevenExt algorithm makes choises of Deadline Remaining allocation based on Performance Cost Ratio Distance and Time Requirement Distance between Service Levels. The experimental results indicate that DBL_UnevenExt could enlarge cost optimization intervals of activities by allocating the Deadline Remaining to the more suitable activity. Based on workflow preprocess with DBL_UnevenExt, a novel approach called DBLUCUBO is proposed to realize workflow balanced optimization aiming of minimzing application cost and system workload fairness. The approach makes Full-ahead-planning for every subworkflow based on sequtial game scheme in Just-in-time mode. The experimantal results show that DBLUCUBO could optimize the cost of workflow application and improve fairness of grid system.3. Balanced-based Optimization scheme for intra-domain schedulingExsiting intra-domain scheduling solutions usually resort to traditional local scheduling scheme, which could not satisfy some new requirements of intra-domain scheuling in commercial grid. From this prospective, a Fair Global Benefit Maximization intra-site Allocation CGMBA is proposed. Based on the cooperative model of intra-domain and the definition admistrate domain’s’balanced state’, a theoretical proof that the system would gain maximal global benefit if and only if it was in a balanced state is presented. On the basis of this conclusion, Grid task-bundle allocation problem is turned into an iteration process involving retail price, market price and assignment amount of tasks in CGBMA. The experimental results indicate that CGBMA could provide an effective solution with global benefit optimization. Meanwhile, owing to CGBMA’s self-selection property which is inherited from market model, load unfairness condition turns worse with the scale of task bundle getting larger. A Cooperative-game-based Global Benefit Maximization Allocation with Fairness Improvement (CGBMAFI) is then presented. The experimental results indicate that administration domain could get better optimize global benefit and user could obtain better executing performance and Performance Cost Ratio with CGBMAFI.更多还原