云环境下周期和非周期混合实时任务双容错调度算法

　　云计算作为下一代并行与分布式计算，它聚合了各种不同的离散资源。由于云计算系统所使用的计算资源具有高度的动态性和异构性，不同类型的计算资源性能差异巨大，以及资源的动态加入和退出，软硬件故障、运行维护、安全保护、系统升级等原因可能导致云环境中的资源无法继续使用，因此，云计算环境出现故障是难免的。

　　主版本/副版本（PrimaryBackup， PB技术是目前最重要的软件容错方法。目前，已有很多采用PB方法进行容错调度的文献。Manimaran等[1]考虑了任务之间的资源限制，同时将处理器划分为若干组，从而保证在多个处理器出错的情况下能够实现容错。AlOmari等[2]研究了一种PB重叠方法，允许一项任务的主版本和其他任务的副版本进行重叠，从而提高了任务的调度成功率。Liu等[3]在假定任务的截止时限等于其周期的情况下，在单处理机环境下引入单调速率（RateMonotonic， RM的周期任务抢占调度算法。Dhall等[4]将RM推广到多处理机系统，提出速率单调首次满足 （RateMonotonic FirstFit，RMFF调度算法。文献[5]对传统的RMFF算法进行容错扩充为速率单调首次满足的容错 （FaultTolerant RateMonotonic FirstFit， FTRMF调度算法，根据主版本的最坏响应时间（WorstCase Response Time， WCRT来确定副版本的执行类型，与传统的双备份调度算法相比，该算法有效地降低了所需要的处理机的个数。朱晓敏等[6]考虑到任务的服务质量（Quality of Service， QoS需求问题，提出异构集群系统中具有QoS需求的实时任务容错调度算法。罗威等[7]提出一种基于固定优先级调度算法的延迟主动副版本备份技术， 通过尽量向后调度主动方式的副版本， 并在主版本成功执行时终止副版本的执行来减少备份的冗余度。

　　在云计算环境下，云用户实时任务请求的类型多种多样，周期实时任务和非周期实时任务往往共同存在。当前，实时系统中周期任务和非周期任务的同时调度普遍采取的方法是建立周期性服务器，按设定的周期，在设定的服务容量内定时执行非周期任务，如文献[8]。文献[9]的空闲时间挪用（Slack Stealing， SS算法通过建立一种被动任务来窃取未被周期任务使用的有效处理机时间来执行非周期任务，然而SS是利用一种试凑的递推方法来寻找最优方案，这往往造成很大的计算时间开销。阳春华等[10]提出一种混合实时任务容错调度算法，采用主/副版本备份技术确保系统的容错能力，副版本采用主动和被动两种形式，该算法采用RM算法完成周期任务的静态调度，采用预订处理机时间方法和最早截止时间优先（Earliest Deadline First， EDF算法动态调度非周期任务，然而该算法在m个处理机上调度n个周期任务，在最坏情况下其计算复杂度高达O（nm2，这将耗费大量的检测是否满足调度条件的测试时间。

　　可见上述混合容错调度算法随着处理机数的增加需要更多的容错调度测试时间，导致调度效率不高，或难以恰当确定建立的周期性服务器的周期和服务容量，以致不能对非周期任务作出及时的响应；上述容错调度算法通常假设周期任务提前已知，可提前预处理调度周期任务，而在云环境下，周期任务也是随机到达的，提高周期任务容错调度的效率对保证任务的实时性至关重要。针对上述问题，本文提出主副版本分组的周期任务容错调度算法、非周期任务容错调度算法以及周期任务和非周期任务混合的容错调度算法。同时，本文还给出任务副版本可重叠执行的判断方法和符合本文调度模型的任务最坏响应时间的计算公式。

　　1混合任务在云环境中执行的前提假设

　　1.1云任务描述

　　周期实时任务是指按一定周期到达并请求运行，并在截止时限之前完成，每次请求称为周期任务的一个任务实例。非周期实时任务是指随机到达系统的任务，并在截止时限之前完成。周期实时任务和非周期实时任务同时并存的任务集称为混合实时任务。

　　定义1任务主版本。基于主副版本的容错技术中，系统首先运行的任务版本称为任务主版本。

　　周期任务的任务主版本τi可描述为一个四元组，τi=（Ci，Ti，Di，Ui，Ci为任务主版本τi的最大执行时间，Ti为任务主版本τi的周期，Di表示任务主版本τi的截止期限，本文假设Di等于Ti；Ui表示任务主版本τi的CPU利用率，定义为Ui=Ci/Ti。

　　非周期任务的任务主版本σi也可描述为一个四元组，σi=（ai，Ci，Di，di，ai是指非周期任务到达系统的时间；Ci为非周期任务i的最大执行时间；Di为相对截止时限；di=ai+Di为绝对截止时限。

　　定义2任务副版本。基于主副版本的容错技术中，运行任务主版本的处理机失效时，作为任务主版本备份执行的任务称为任务副版本。

　　周期任务的任务主版本τi的任务副版本αi描述为一个四元组，即αi=（Bi，Ti，Di，Ui，Bi为αi的最大执行时间，一般来说Bi≤Ci，因为副版本可以是主版本的完全备份，实现主版本需要完成的所有功能，也可以是简体版本，只保证故障状态下主版本中必不可少的功能，本文假定Bi=Ci；Ti为αi的周期，与τi的周期相同；假定主版本任务和副版本任务具有相同的Di和Ui。