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

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

主备份技术是目前软件错最重要的方法。目前，已有大量关于用PB法进行错调度的文献。Manimaran等人[1]考虑了任务之间的资源约束，同时将处理器分成几个组，从而保证了当多个处理器出现时错能够实现。错Alomari等人[2]研究了一种PB重叠方法，该方法允许一个任务的主要版本与其他任务的次要版本重叠，从而提高了任务调度的成功率。刘等人[3]在任务截止时间等于任务周期的假设下，提出了一种周期任务抢占调度算法。Dhall等人[4]将RM扩展到多处理器系统，并提出了一种速率单调优先(RMFF)调度算法。在文献[5]中，对的传统RMFF算法将容量错扩展为容错速率错调度算法，其速率首次得到单调满足。根据主要版本的最大案例响应时间(WCRT)，确定次要版本的执行类型。与传统的双备份调度算法相比，该算法有效地减少了所需的处理器数量。朱晓敏等人[6]考虑到任务的服务质量要求，提出了一种异构集群系统中具有服务质量要求的实时任务调度算法。罗威等人[7]提出了一种基于固定优先级调度算法的延迟主动版本备份技术，通过尽可能向后调度主动版本，并在主版本成功执行时终止版本的执行，减少了备份的冗余。在云计算环境中，云用户的实时任务请求有多种类型，周期性的实时任务和非周期性的实时任务经常并存。目前，在实时系统中调度周期性任务和非周期性任务的常用方法是建立周期性服务器，并根据设定的周期在设定的服务能力内定期执行非周期性任务，如文献[8]所示。在文献[9]中，松弛窃取算法通过建立一个被动任务来窃取周期任务未使用的有效处理器时间，从而执行非周期任务。然而，SS使用试错递归方法来寻找最优解，这经常导致大量的计算时间开销。阳春华等人[10]提出了一种具有错容量的混合实时任务调度算法，该算法采用主/次版本的备份技术来保证系统的错容量，次版本采用主动和被动两种形式。该算法利用RM算法完成周期性任务的静态调度。非周期任务通过处理器时间预留方法和最早截止时间优先算法进行动态调度。然而，该算法在M个处理器上调度N个周期任务，在最坏的情况下，其计算复杂度高达O(nm2)，这将消耗大量测试时间来测试调度条件是否满足。

可以看出，上述混合容量-错调度算法需要更多的容量-错调度测试时间随着处理器数量的增加而增加，导致调度效率较低，或者难以正确确定已建立的周期性服务器的周期和服务容量，使得对非周期性任务无法及时响应；上述错-tolerant调度算法通常假设周期性任务是预先已知的，并且可以预先进行预处理和调度。在云环，周期性任务也是随机到达的，因此提高错周期性任务调度的效率，保证任务的实时性是非常重要的。针对对，的上述问题，本文提出了错，周期任务与错非周期任务、错混合周期任务的调度算法，同时根据本文的调度模型给出了任务子版本重叠执行的判断方法和任务最差响应时间的计算公式。1在云环执行混合任务的前提假设

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

定义1个任务主要版本。在基于主版本和次版本的错技术中，系统运行的第一个任务版本称为主任务版本。periodic任务的主版本i可以描述为一个四元组，其中i=(Ci，ti，Di，Ui)，Ci是主版本i的最大执行时间，Ti是主版本i的周期，Di代表任务主版本i的截止时间。Ui表示任务主版本i的CPU利用率，定义为Ui=Ci/Ti。

非周期任务i的主版本也可以描述为四重，i=(ai，Ci，di，Di，ai指非周期任务到达系统的时间；Ci为非周期任务I的最大执行时间；Di是最后期限阶段的Di=是最后期限阶段的定义2任务子版本。在基于主要版本和次要版本的错技术中，当运行主要版本任务的处理器失败时，作为主要版本任务的备份执行的任务被称为次要版本任务。

perioDic任务主版本i的子版本i被描述为四重，即i=(Bi，Ti，di，Ui)，Bi是i的最大执行时间，一般来说，BiCi，因为子版本可以是主版本的完整备份，以实现主版本需要完成的所有功能，也可以是简化版本，仅保证主版本在故障情况下的基本功能。本文假设bi=ci Ti是i的周期，与i的周期相同；假设主版本任务和次版本任务具有相同的Di和Ui。