基于空间时间冗余的替代主版本冗余调度算法

目的 研究空间冗余与时间冗余各自的特点,提出一种将时间冗余与空间冗余方式的优点相结合的容错调度算法,提高调度算法的处理器利用率.方法 将每个任务分为主版本、副版本和替代主版本.根据任务利用率将任务集分为高频任务集和低频任务集两类.分别采用空间冗余和时间冗余策略实现容错.采用EDF算法为任务分配动态优先级,且在主版本任务频繁发生错误的情况下激活替代主版本.结果 所提算法将空间冗余与时间冗余相结合,满足任务的实时与容错需求,且避免系统因频繁执行一个易出错的主版本任务而造成资源的浪费.结论 该算法降低了任务集对系统处理器数量的需求,提高了系统资源利用率.     

分布式实时系统的容错调度算法

现有的分布式实时系统的容错调度算法要求系统中所有任务的周期相同且等于其时限，而实际中任务的周期常常是互不相同的,将任务分配算法与单处理器的调度算法相结合，提出基于基版本／副版本技术和非抢占式EDF算法的容错调度算法，给出了基版本／副版本任务时限的设置方法，并对任务集的可调度性进行了分析，给出了任务集在给定处理器集上可调度性的判定方法.     

多处理器实时系统中的非精确轮转式调度算法

目的研究基于多处理器实时系统中具有截止期和容错需求任务的非精确轮转式调度算法,使强实时系统在发生故障的情况下,任务也能在其截止期内完成,不至产生灾难性后果.方法将非精确计算模型引入到轮转式调度算法中.结果仿真实例表明,非精确轮转式调度算法具有更低的任务拒绝率,同时能更为有效地利用系统资源.结论该算法扩展了轮转式调度算法的允许调度定理,使得主/副版本任务在执行时间上可以重叠,提高了任务的可调度性,使整个系统负载均衡,并减少了系统搜索时间.     

基于非精确计算模型的OSL算法

目的研究多处理机系统任务分配的启发式策略和容错调度算法,设计一种高效实时调度算法．方法只对任务强制部分进行复制,将任务分为强制执行部分主版本PTMi、强制执行部分副版本BkMi．和选择执行部分Oi,采用可选择部分后调度．结果提出了可选择部分后调度（Optional Scheduling Later,OSL）算法,通过实例与ICDM算法进行了仿真比较,说明了该算法的有效性．结论该算法使任务的完成时间提前,提高了处理机的利用率,便于广泛应用．     

分布嵌入式实时系统容错调度算法

目的 提出一种针对分布嵌入式异构系统的容错调度算法,以保障系统的实时要求.方法 将每个任务复制为Ncf 1个版本,并在不同处理器及通信链路上来调度,优先调度关键路径上的任务.结果 通过任务复制方法 提高了系统可靠性,减小了调度长度,使任务满足容错要求,最多可以容忍Ncf个故障.结论 通过实例表明该算法满足实时需求,且既可容忍处理器故障.又能容忍通信链路故障.     

任务级动态冗余

任务级动态冗余是作者为某容错计算机系统设计的处理实时运行故障的新方法。该方法的基本原理是:在实时多任务环境下,充分利用操作系统提供的功能,为系统中的关键任务建立后备任务作为冗余资源,并用容错调度算法动态地利用后备任务,以实现容错的目的,克服瞬时故障,保证关键任务正确执行,从而提高系统工作的可靠性。任何容错系统都要投入冗余资源,任务级动态冗余的冗余资源既不是硬件模块,也不是不同版本的软件,而是操作系统的调度单位──任务,因此不需要增加昂贵的成本,在系统     

多处理器实时系统容错ICDM调度算法

目的提出一种针对多处理器实时系统中具有时间、资源和容错需求任务的调度算法来满足硬实时系统实时性及可靠性要求．使硬实时系统在发生故障的情况下，任务也能在其截止期内完成，不致产生灾难性后果．方法将非精确计算模型引入到Distance Myopic算法中，通过非精确计算模型与Distance Myopic算法的有效结合，提出ICDM算法．结果任务分为主副两个版本，每个任务都由两部分组成：强制执行部分和选择执行部分；当任务强制执行部分不能达到截止期时．通过调用MOPT算法减小前序任务选择部分的执行时间，使其满足截止期要求．ICDM算法使任务在保证结果可接受的情况下，在其截止期内完成，提高了任务的可调度性．结论通过引入非精确计算模型，使算法的可调度性增强了，也提高了硬实时系统的实时性及可靠性．     

基于回卷恢复的数控系统实时容错调度策略

针对数控系统对时间确定性和可靠性的要求,建立混合关联任务集描述模型,提出了基于回卷恢复机制和最佳优先（BF）算法的容错调度策略.该策略对数控系统关键任务的执行过程进行周期性分段验证,通过保存正确的检查点状态,使得出现瞬时故障时任务可以从检查点开始继续执行,从而以较低的计算损失达到容错的效果.与传统的实时容错调度算法相比,基于回卷恢复机制的容错调度策略能很好地适用于数控系统多类型任务并存和任务间相互约束的特点,同时,通过降低错误恢复所需的时间开销,有效地提高了系统的资源利用率.该算法应用于数控系统的有效性在实例分析和算法模拟研究中得到验证.     

基于资源回收的容错单调比率调度

基于时间冗余的容错实时调度算法,其可调度条件是以任务的最坏执行时间和为任务预留容错操作的时间为分析基础,且任务拒绝率高,系统资源利用率低。该文提出的基于资源回收的容错单调比率调度,以容错实时调度算法FT-RM为基础,利用任务的实际执行时间低于最坏执行时间的特性,收集已完成任务释放的资源供等待任务使用,在保证系统容错要求的同时,提高了任务吞吐量和系统资源利用率,并通过模拟实验分析算法性能,研究了影响算法调度性能的若干因素。     

混合关键任务可靠调度方法与调度性分析

为了解决云计算环境下混合关键性任务的可靠调度问题,提出了一种基于主副版本两阶段的混合关键任务可靠调度方法．算法首先对需要调度的混合关键性任务进行优先级划分,按照调度截止期最短的原则将主版本任务调度到目标虚拟机上,对副版本任务按照复制成本最低的原则使用重叠方法进行调度;再对调度到不同虚拟机上的主副版本任务进行可调度分析,对于不能满足分析的任务启动更高关键性等级进行处理．实验结果表明了混合关键任务可靠调度方法具有较高的可靠性和负载平衡能力．     

面向Flink流处理框架的主动备份容错优化

针对Flink任务出现故障后因为全局卷回使流处理作业恢复效率低的问题,提出基于缓存队列的容错策略. 在作业中找出恢复时间最长的算子作为关键算子,将其处理过的数据存储到缓存队列中,并为其进行主动备份,备份算子同时接受来自上游的数据以达到在故障后作业可以瞬时恢复的效果. 为了解决主动备份带来的额外消耗,提出数据过滤算法,备份算子在每次处理数据前会到缓存组件中检索当前数据,以判断是否继续处理. 当Flink算子自身出现故障后,利用策略中的缓存队列与Flink的JobManager将故障发生时的数据信息发送给备份算子,在备份算子接收到数据后,实现即时恢复的效果. 利用4项评价指标对策略进行评估,结果表明,与Flink1.8的故障恢复模式相比,所提策略在Flink任务故障恢复速度上有显著提升,当故障次数分别为1、2、3、4时,恢复效率分别提高56.3%、51.3%、46.2%和45.8%;而在处理时延、CPU利用率以及内存使用率方面仅产生极小的代价.     

一种基于拟序的关联备份任务调度算法

为了减少存储备份任务的执行时间和提高整个存储系统的效率，提出了一种新的SAN体系结构——基于集群技术的SAN体系结构，并在其结构上提出并实现了关联备份任务的数学模型和实现该模型的核心调度算法。该算法的基本思想是对投入的关联备份任务找到一个最优的执行顺序，以便提高整个系统的性能。实验数据表明，对于关联备份任务的调度与执行，该算法可以有效提高整个系统的效率。     

Multiple DAGs dynamic workflow reliability scheduling algorithm in a cloud computing system

In order to solve the reliable scientific workflow scheduling problem for cloud computing, a dynamic of the RANK-Hierarchical algorithm is put forward which takes account of communication contention as well as supports task dependencies(CCRH). A communication contention model is first defined, as soon as the earliest completion of the primary and backup task is deduced. Besides, the executived processor is limited. We use the dynamic hierarchical method and calculate each DAG unfair degree factor for multiple DAGs scientific workflow. It can deal with the situation that multiple DAGs workflow comes at different times and there are various kinds of structure. Both the theory and experiments have proved that the algorithm can not only improve the scheduling fairness of multiple DAGs workflow but also shorten the average execution Makespan.     

非抢占式实时任务1次容错调度

面向非抢占式任务实时调度问题,根据不同的故障间隔,推导出任务集合需要满足的条件.根据任务的可重复执行次数,分别设计了非抢占式固定优先级容错(NP-FP-FT)以及动态优先级容错(NP-DP-FT)调度算法,并与非抢占式最早期限优先容错(NP-EDF-FT)、非抢占式单调速率容错(NP-RM-FT)调度算法进行了对比分析.结果显示,采用非抢占式固定优先级算法调度的任务集合具有最低的任务失效率.