论文部分内容阅读
随着互联网的发展,网速在不断提升,接入互联网的机器越来越多,人们对大容量、高密度计算的需求在不断上升,价格低廉而具备超级计算能力和高效资源利用率的云计算应运而生。基于云计算平台的应用通常需要同时使用众多计算资源和存储资源来完成其计算任务,为此,系统容错能力的研究变得越来越重要。针对这一领域,本文研究基于主从备份任务的云计算容错调度算法。本文的主要工作包括以下几个方面：(1)首先介绍了一种新的划分任务的方法,为每个刚到的任务赋予关键度,把任务分为紧急任务和非紧急任务,对紧急任务采用尽可能早算法ASAP (as soon as possible)调度主任务,而对非紧急任务采用尽可能迟算法ALAP (as later as possible)调度主任务。在分析上述两个算法特点的基础上得出新的算法CAS-AL调度算法。(2)针对某一时间段可能出现两个或两个以上的处理机故障问题,为了降低这种情况对任务执行的影响,提出一种新的备份任务调度技术——同步错位调度,在同步错位调度中同时考虑了当前任务的所有前置任务和与它同步进行的任务对它的备份任务所能映射的处理机限制。并把同步错位调度的方法运用到独立任务、依赖任务和通信延迟的依赖任务当中。(3)在同步调度错位技术限制备份任务所能映射的处理机基础上,运用边界调度概念得出两个改进的算法：最小备份成本调度算法MRCA和备份任务最早完成时间算法BOSA。它们分别以备份成本最小化和备份任务最早完成为主要目标。(4)使用新的通信模型进行处理机之间通信,在备份成本最小化和备份任务最早完成之间寻求平衡点,得到备份任务优化调度算法。该算法弥补了最小备份成本调度算法和备份任务最早完成时间算法只单方面考虑成本或时间的缺陷。最后通过模拟实验将上述算法与传统算法ASAP、ALAP和eFRD分别从任务拒绝率、备份成本、响应时间三方面进行比较。在任务拒绝率方面,算法CAS-AL比传统算法ASAP和ALAP都低；算法MRCA在独立任务调度中比eFRD和ASAP的拒绝率更低；算法BFFA在调度依赖任务中比算法eFRD和ASAP的接受率更高；而算法BOSA比所有算法都有更高的接受率。在备份成本方面,算法MRCA、BFFA和BOSA都比eFRD和ASAP需更少的备份成本。在响应时间方面,对独立任务而言,本文中的三个算法都比eFRD和ASAP有更短的响应时间,但对依赖任务而言,除了算法eFRD,其它所有算法都有相似结果。