边缘计算中基于能耗感知的容错协同任务执行算法

边缘计算已被设想成为增强资源贫乏的智能设备计算能力的有效解决方案.通过任务卸载用户可以将计算复杂的任务卸载到边缘云端执行来满足其对资源的需求.然而,其仍然需要解决能量消耗、可靠性和延时的问题.文中提出了一种基于能耗感知的容错协同任务执行算法,以在减少设备能耗的同时保证卸载到边缘云上的任务成功执行.具体地,首先设计了一种具有容错能力的能耗感知协同任务执行模型,该模型通过将计算卸载模型和容错模型相结合,从而在应用程序的截止完成时间内减少设备能耗.然后,提出了一种基于能耗感知的容错协同任务执行调度算法,该算法包括协同任务执行、初始化调度和在线调度.协同任务执行是通过部分关键路径分析和one-climb策略来确定任务的执行决策;初始化调度是从副本和重新提交中为在边缘端执行的任务选择容错策略,以在发生故障时可针对任务采取相应容错措施;在线调度是在发生故障时实时调整容错策略以确保任务成功处理.最后,在3种具有代表性的任务拓扑上进行了广泛的仿真实验,评估了3种不同方案在任务完成率、能耗比方面的性能差异.结果表明,无论是截止完成时间、传输速率还是容错率的变化,该方法都可以保证任务在截止时间内顺利完成,相比协同任务执行更可靠,而且相比本地执行设备消耗的能量可至少减少30％.     

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

云环境中的处理机故障已成为云计算不可忽视的问题,容错成为设计和发展云计算系统的关键需求。针对一些容错调度算法在任务调度过程中调度效率低下以及任务类型单一的问题,提出一种处理机和任务主副版本分组的容错调度方法;并给出了副版本可重叠执行的判定方法,以及任务最坏响应时间的计算公式。通过实验和分析表明,和以前算法相比,将处理机分成两组分别执行任务主版本和任务副版本,减少了任务调度所需进行可调度测试的时间,增加了副版本重叠执行的机会,减少了所需的处理机个数,对提高系统处理机的利用率和容错调度的效率具有重要的意义。     

一种支持容错的任务并行程序设计模型

任务并行程序设计模型已成为并行程序设计的主流,其通过发掘任务并行性来提高并行计算机的系统性能.提出一种支持容错的任务并行程序设计模型,将容错技术融入到任务并行程序设计模型中,在保证性能的同时提高系统可靠性.该模型以任务为调度、执行、错误检测与恢复的基本单位,在应用级实现容错支持.采用一种Buffer-Commit计算模型支持瞬时错误的检测与恢复;采用应用级无盘检查点实现节点故障类型永久错误的恢复;采用一种支持容错的工作窃取任务调度策略获得动态负载均衡.实验结果表明,该模型以较低的性能开销提供了对硬件错误的容错支持.     

硬实时系统中基于软件容错的动态调度算法

在硬实时系统中,由于任务超时完成将会导致灾难性后果,因而硬实时系统具有严格的时间及可靠性限制条件.目前实时容错调度算法大部分针对硬件的容错,很少考虑软件运行的故障.提出了两种类似EDF(earliest deadline first)的软件容错的动态实时调度算法:PKSA(probing K-step algorithm)和CUBA(changing utilization-based algorithm).两种算法在任务执行过程中,通过若干试探性检测步骤,提高了任务可执行性的预测,尽可能地避免了任务早期的失败对后续任务的影响,因此提高了任务的完成率,同时也有效地减少了浪费的CPU时间片数量.通过实验测试,与目前所知的同类算法相比,具有更佳的调度性能--调度成本平衡性.     

异构集群系统中具有QoS 需求的实时任务容错调度

容错调度是调度问题中一个重要的研究内容,是提高系统可靠性的有效手段.目前已有很多集群系统中实时任务的容错调度算法,但是这些算法都没有考虑到任务的QoS需求问题.提出了一种异构集群系统中具有QoS需求的实时任务容错调度算法FTQ(fault-tolerant QoS-based scheduling).该算法采用主版本/副版本(primary/backup,简称PB)技术,综合考虑了任务的时间限制、任务的QoS需求、系统的可靠性和系统资源的利用率,能够自适应地根据系统负载情况动态地调整任务的QoS级别和副版本的执行模式,从而提高了系统的灵活性、可靠性、可调度性和资源的利用率.对系统的可靠性进行了定量分析,并将其引入到容错调度算法中,提高了系统的可靠性.同时,在调度过程中尽量提前主版本的开始时间,推迟副版本的开始时间,以使任务的副版本采用被动执行模式或者使任务主版本和副版本的重叠部分尽量少,提高了资源的利用率.此外,采用了副版本重叠技术,并分析了副版本的最晚开始时间及其约束条件,提高了任务的调度成功率.通过大量的模拟实验,对FTQ,NOFTQ和DYFARS算法进行了比较.实验结果表明,FTQ算法的性能优于其他方法,具有更好的调度质量.     

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

提出了两种分布式实时容错调度算法：副版本后调度算法（ＢＫＣＬ）及无容错需求后调度算法（ＮＦＲＬ）,并研究了算法的时间复杂度,这两种容雕工算法能同时调度具有容错需求的实时任务和无容错需求的实时任务,ＢＫＣＬ和ＮＦＲＬ所产生的调度可保证：在分布式系统中一个节点机失效的情况下,具有容错需求的实时任务仍然可在截止时间内完成,在描述了两个实时容错调度算法之后,分别证明了这两个算法的容错调度正确性。接着,阐述     

多处理机系统的一种实时容错调度算法

实时容错调度算法是实时系统容错研究中的重要问题.提出了一种多处理机系统的实时任务容错调度算法.该算法结合了基版本/副版本(Primary/Backup)方法和三模冗余(TMR)方法,以保证在一个节点机失效时,任务可以在其截止时限内完成.     

混合型实时容错调度算法的设计和性能分析

以往文献中研究的实时容错调度算法都只能调度单一的具有容错需求的任务.该文建立了一个混合型实时容错调度模型,提出一种静态实时容错调度算法.该算法能同时调度具有容错需求的实时任务和无容错需求的实时任务.该文还提出了一个求解最小处理机个数的算法,用于对静态实时容错调度算法的性能进行模拟分析.为了提高静态调度算法的调度性能,提出了一种动态调度算法.最后,通过模拟实验分析了静态和动态调度算法的性能.实验表明,调度算法的性能与实时任务的个数、任务的计算时间、周期和处理机个数等系统参数相关.     

异构分布式实时系统中对具有前后依赖关系任务的基于动态可变调度距离容错调度算法

目前的主副版本容错调度算法大多没有考虑任务间的前后依赖关系,但实际中很多任务是具有前后依赖关系的。本文提出了一种基于主副版本动态可变调度距离的任务容错调度算法,该技术通过比较任务间的最晚开始执行时间与最早开始执行时间的差值,安排任务副版本的调度,并且基于此设计了可用于具有前后依赖关系任务调度可重叠技术。本文提出的基于动态可变调度距离的容错调度算法在尽可能让任务最早完成的情况下,提高系统的可靠性,并且优先调度关键路径任务,降低了系统的容错开销。最后通过实验证明本文算法的有效性和优异性。     

异构分布式实时系统中对具有前后依赖关系任务的基于动态可变调度距离容错调度算法

目前的主副版本容错调度算法大多没有考虑任务间的前后依赖关系,但实际中很多任务是具有前后依赖关系的。本文提出了一种基于主副版本动态可变调度距离的任务容错调度算法,该技术通过比较任务间的最晚开始执行时间与最早开始执行时间的差值,安排任务副版本的调度,并且基于此设计了可用于具有前后依赖关系任务调度可重叠技术。本文提出的基于动态可变调度距离的容错调度算法在尽可能让任务最早完成的情况下,提高系统的可靠性,并且优先调度关键路径任务,降低了系统的容错开销。最后通过实验证明本文算法的有效性和优异性。     

实时异构系统中的积极复制容错调度算法

在设计实时异构系统中的容错调度算法时,既要考虑到实时性的约束,又要最大化系统的可靠性.此外,异构系统中的并行应用调度问题已经被证明了是NP完全问题.现有的容错调度算法大多采用复制技术来提升系统的可靠性,但是任务的多次执行会导致应用执行时间变长,系统实时性下降.为此,提出了一个基于积极复制技术的容错调度算法,该算法连续的复制任务集中对当前系统实时性影响最小的任务,然后将任务集中的所有任务调度至最早完成的处理器,用以在满足实时性约束的同时,提升系统的可靠性.实验表明,相比于同样着眼于实时异构系统的DB-FTSA算法,该算法在实时性约束严格的情况下,可靠性有较大提升.     

A design fix to supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks

In the article ‘Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks’, Park and Cho presented a systematic way of computing a largest fault-tolerant and schedulable language that provides information on whether the scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. The computation of such a language is mainly dependent on the task execution model presented in their paper. However, the task execution model is unable to capture the situation when the fault of a processor occurs even before the task has arrived. Consequently, a task execution model that does not capture this fact may possibly be assigned for execution on a faulty processor. This problem has been illustrated with an appropriate example. Then, the task execution model of Park and Cho has been modified to strengthen the requirement that none of the tasks are assigned for execution on a faulty processor.     

基于EDF的分布式控制系统容错调度算法

现有的分布式实时系统的容错调度算法要求系统中所有任务的周期相同且等于其时限,而实际中任务的周期常常是互不相同的.根据控制系统中任务的特点,结合任务分配算法与处理器的调度算法,提出了基于基版本/副版本技术和EDF算法的容错调度算法.该算法不要求任务的周期都相同,并通过设置基版本/副版本任务时限控制它们的执行时间不重叠,给出了基版本/副版本任务时限的设置方法,并对任务集的可调度性进行了分析.当任务集可调度时,给出其最大利用率和最小处理器个数的约束条件.最后给出一个仿真实例,结果表明了算法的有效性.     

Comparative study of task duplication static scheduling versus clustering and non-clustering techniques

One of the major issues that needs to be addressed in distributed memory multiprocessor (DMM) systems is the program task partitioning and scheduling problems, i.e. mapping of an application program's precedence related task threads among the processing elements of a DMM system. The optimal task partitioning and scheduling problem, with the goal of minimizing the program execution time and interprocessor communication overhead, is known to be an NP-complete problem. The paper addresses the design, development and performance evaluation of a novel static task partitioning and scheduling method called linear clustering with task duplication (LCTD). LCTD employs the linear (sequential) execution of tasks and task duplication heuristics in achieving minimized computation and interprocessor communication delays in DMMs. The superiority of the proposed LCTD algorithm is demonstrated through simulation studies and comparison against several of the existing static scheduling schemes, such as heavy node first (HNF) and linear clustering. We show that the proposed method can obtain an average of 33% improvement in program execution time and 21% improvement in processor utilization compared to linear clustering and HNF methods.     

基于多目标全局约束的任务分配和调度算法

针对嵌入式系统中大多数任务执行算法不考虑目标成本问题,提出了一种基于多目标全局约束的任务分配和调度算法。算法使用约束逻辑编程来对任务执行资源如处理单元、通信设备以及代码和数据存储量的使用进行多目标全局约束。算法假设ROM和RAM分别用于代码存储和数据存储,算法还考虑数据在数据存储器中的位置。实验结果表明,尽管在多个约束条件下,提出的任务分配和调度算法无论在代码存储和数据存储量使用方面,还是在对任务有效求解方面都能取得比普遍采用的贪婪调度算法更好的结果。     

Fault-Tolerant Dynamic Rescheduling for Heterogeneous Computing Systems

As the scale and complexity of heterogeneous computing systems grow, failures occur frequently and have an adverse effect on solving large-scale applications. Hence, fault-tolerant scheduling is an imperative step for large-scale computing systems. The existing fault-tolerant scheduling algorithms belong to static scheduling, and they allocate multiple copies of each task to several processors no matter whether processor failures affect the execution of tasks. Such active replication strategies not only waste resource but also sacrifice the makespan. What is more, they cannot guarantee the successful execution of applications. In this paper, we propose a fault-tolerant dynamic rescheduling algorithm named FTDR, which can overcome above drawbacks. FTDR keeps listening to the processor failure, and reschedules the suspended tasks once failures occur. Because FTDR reschedules the tasks that are suspended because of failures, it can tolerate an arbitrary number of failures. Randomly generated DAGs are tested in our experiments. Experimental results show that the proposed algorithm achieves good performance in terms of makespan and resource consumption compared with its direct competitors.     

软件容错模型中反向与正向调度算法研究

为了保证实时系统在发生任务失效时仍旧能够正常地工作,通常采用软件容错模型来提高实时系统的容错能力。本文分析了软件容错模型中的BCE容错调度算法,针对该算法中的反向调度和正向调度两个过程,给出了RMB、DMB、FDMB、EDFB四种反向调度算法和RMF、EDFF两种正向调度算法,并指出了反向调度和正向调度相互协调的特性。将各种算法在BCE算法中进行模拟,结果表明,EDFF正向调度算法能够与四种反向调度算法更好地协调,从而获得比RMF正向调度算法更高的调度性能;模拟结果还表明,四种反向调 度算法在BCE算法中的性能相近。最后,本文得出了RMB（或DMB）反向调度算法与EDFF正向调度算法的组合较适用于软件容错模型的结论。     

基于非精确计算的多错误模式下的容错优化调度算法

实时系统中每个任务必须在其截止时间内产生逻辑正确结果。但是,由于过载并不保证 每个实时任务都能满足此要求。因此,适当降低实时任务精确度以及在错误发生时提供最大利用率 的容错优化方法以保证系统的实时性与可靠性变得非常重要。利用非精确调度中任务的可选部分为 强制部分的错误恢复提供潜在的时间容余,提出了在多个错误发生时既能保证报酬最大化又能提供 强制部分恢复处理的容错优化调度形式算法,并结合实例给出分析过程。     

Exploiting Redundancies to Enhance Schedulability in Fault-Tolerant and Real-Time Distributed Systems

In the past decades, distributed systems have been widely applied to real-time applications, most of which have fault-tolerance requirements to assure high reliability. Due to the stringent space constraints of real-time systems, the issue of schedulability becomes a major concern in the design of fault-tolerant and real-time distributed systems. Most existing real-time and fault-tolerant scheduling algorithms, which are based on the primary-backup scheme for periodic real-time tasks, introduce unnecessary redundancies by aggressively using active-backup copies. To solve this problem, we propose two novel fault-tolerant techniques, which are seamlessly integrated with fixed-priority-based scheduling algorithms. These techniques leverage redundancies to enhance schedulability in fault-tolerant and real-time distributed systems. Our fault-tolerant techniques make use of the primary-backup scheme to tolerate permanent hardware failures. The first technique (referred to as Tercos) terminates the execution of active-backup copies, when corresponding primary copies are successfully completed. Tercos is designed to reduce scheduling lengths in fault-free scenarios to enhance schedulability by virtue of executing portions of active-backup copies in passive forms. The second technique (referred to as Debus) uses a deferred-active-backup scheme to further minimize schedule lengths to improve the schedulability performance. Debus schedules active-backup copies as late as possible, while terminating active-backup copies when their primary copies are completed. Experimental results show that, compared with existing algorithms in literature, Tercos can significantly improve schedulability by up to 17.0% (with an average of 9.7%). Furthermore, empirical results reveal that Debus can enhance schedulability over Tercos by up to 12% (with an average of 7.8%).