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

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

一种新的异构实时分布式系统的容错调度算法

一般来说,异构分布式实时系统中任务的周期并不完全相同且任务的时限不等于它们的周期,同时系统中还有一些无容错需求的任务.因此现有的任务调度算法一般不能满足这些要求.针对这类系统,在结合基版本/副版本技术和EDF算法的基础上,给出了一种新的容错调度算法.该算法由两部分组成：任务分配调度算法和单处理器调度算法.对于单处理器调度算法,本文采用了EDF算法;在此基础上,给出一种启发式静态任务分配算法.分析了系统的可调度性,给出了任务可调度条件和基版本/副版本时限的设置方法.仿真结果表明,这种算法是有效的.     

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

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

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

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

分布式控制系统中多种混合任务的容错调度

分布式控制系统中存在有强实时、软实时和非实时等多种实时性的任务,其中强实时任务必须在其时限前完成,否则会出现灾难性后果,因此必须为分布式控制系统提供一定的容错能力。首先给出了用于调度多种实时性任务的单处理器调度算法——双优先级队列调度算法,并分析算法的可调度性条件。针对分布式控制系统,考虑基版本与副版本的执行时间不同时,结合版本复制技术和单处理器调度算法提出了一种新的容错调度算法。分析了算法的可调度行,给出了可任务集的可调度条件判断方法和基版本任务时限的设置方法。在此基础上,采用启发式静态任务分配算法,保证各处理器的负载均衡。本算法在保证任务容错可调度的条件下,可提高系统中各处理器的利用率,仿真结果表明该算法是有效的。     

分布式实时系统双工容错技术研究

本文介绍一个高可用性的分布式实时双工系统。文中首先建立了系统模型,通过模型给出了系统高可用性的定量公式,最后着重介绍了实现双工的几种主要技术,包括机组切换、数据恢复和双工结果处理等。     

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

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

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

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

单机实时系统中的一种混合型实时容错调度算法

目前研究单机实时系统的调度算法文章大多只能调度单一类型的任务。本文在PKSA算法的基础上，建立了一种混合型实时容错模型，提出一种调度算法不仅可以调度有容错需求的周期任务，同时也能够调度无容错需求的周期任务和非周期非实时任务，实现了调度混合型任务的目的。     

面向硬实时系统的容错调度算法研究

目前基于软件容错模型的调度算法大部分都是针对如何提高主版本可执行性的预测精度,很少考虑如何提高主版本的完成率.基于这一问题,本文提出一种基于软件容错模型的实时调度算法(kernel),该算法有选择地重新执行某些失败的主版本并允许其运行在更高的优先级别上,尽最大努力地提高了主版本的完成率,改善了输出结果的计算精度.仿真实验表明,与同类算法相比,kernel算法在提高系统容错能力方面更为有效.     

A dominant predecessor duplication scheduling algorithm for heterogeneous systems

This paper proposes a new duplication-based task scheduling algorithm for distributed heterogeneous computing (DHC) systems. For such systems, many researchers have focused on solving the NP-complete problem of scheduling directed acyclic task graphs to minimize the makespan. However, the heterogeneity of computational resources and communication mechanisms poses some major obstacles to achieving high parallel efficiency. This paper proposes a heuristic strategy called the Dominant Predecessor Duplication (DPD) scheduling algorithm, which allows for system heterogeneities and communication bandwidth to exploit the potential of parallel processing. This algorithm can improve system utilization and avoid redundant resource consumption, resulting in better schedules. Experimental results show that the system heterogeneities and program structures of applications affect scheduling performance, and that our presented algorithm is better able to avoid these problems than those presented in previous literature. Here, we show that our algorithm can be applied to design efficient distributed systems to overcome performance bottlenecks caused by system heterogeneities.

分布式调度算法在VOQ交换机中的应用

为提高高速通信网络的通信效率,针对VOQ交换机,提出在交换机的各个输出端口中进行分布式通信调度(DSA)的策略。DSA算法可直接支持变长数据包通信调度,克服了传统信元交换只能调度定长数据包的缺点,降低了交换机的实现复杂度。仿真结果表明：在各种流量下,DSA算法都比信元调度算法具有更好的调度性能。     

A non-preemptive scheduling algorithm for soft real-time systems

Real-time systems are often designed using preemptive scheduling and worst-case execution time estimates to guarantee the execution of high priority tasks. There is, however, an interest in exploring non-preemptive scheduling models for real-time systems, particularly for soft real-time multimedia applications. In this paper, we propose a new algorithm that uses multiple scheduling strategies for efficient non-preemptive scheduling of tasks. Our goal is to improve the success ratio of the well-known Earliest Deadline First (EDF) approach when the load on the system is very high and to improve the overall performance in both underloaded and overloaded conditions. Our approach, known as group-EDF (gEDF) is based on dynamic grouping of tasks with deadlines that are very close to each other, and using Shortest Job First (SJF) technique to schedule tasks within the group. We will present results comparing gEDF with other real-time algorithms including, EDF, Best-effort, and Guarantee, by using randomly generated tasks with varying execution times, release times, deadlines and tolerance to missing deadlines, under varying workloads. We believe that grouping tasks dynamically with similar deadlines and utilizing a secondary criteria, such as minimizing the total execution time (or other metrics such as power or resource availability) for scheduling tasks within a group, can lead to new and more efficient real-time scheduling algorithms.     

Adaptive pre-task assignment scheduling strategy for heterogeneous distributed raytracing system

One of the main obstacles in obtaining high performance from heterogeneous distributed computing (HDC) system is the inevitable communication overhead. This occurs when tasks executing on different computing nodes exchange data or the assigned sub-task size is very small. In this paper, we present adaptive pre-task assignment (APA) strategy for heterogeneous distributed raytracing system. In this strategy, the master assigns pre-task to the each node. The size of sub-task for each node is proportional to the node’s performance. One of the main features of this strategy is that it reduces the inter-processes communication, the cost overhead of the node’s idle time and load imbalance, which normally occurs in traditional runtime task scheduling (RTS) strategies. Performances of the RTS and APA strategies are evaluated on manager/master and workers model of HDC system. The experimental results of our proposed (APA) strategy have shown a significant improvement in the performance over RTS strategy.     

An efficient list-based task scheduling algorithm for heterogeneous distributed computing environment

The task scheduling in heterogeneous distributed computing systems plays a crucial role in reducing the makespan and maximizing resource utilization. The diverse nature of the devices in heterogeneous distributed computing systems intensifies the complexity of scheduling the tasks. To overcome this problem, a new list-based static task scheduling algorithm namely Deadline-Aware-Longest-Path-of-all-Predecessors (DA-LPP) is being proposed in this article. In the prioritization phase of the DA-LPP algorithm, the path length of the current task from all its predecessors at each level is computed and among them, the longest path length value is assigned as the rank of the task. This strategy emphasizes the tasks in the critical path. This well-optimized prioritization phase leads to an observable minimization in the makespan of the applications. In the processor selection phase, the DA-LPP algorithm implements the improved insertion-based policy which effectively utilizes the unoccupied leftover free time slots of the processors which improve resource utilization, further least computation cost allocation approach is followed to minimize the overall computation cost of the processors and parental prioritization policy is incorporated to further reduce the scheduling length. To demonstrate the robustness of the proposed algorithm, a synthetic graph generator is used in this experiment to generate a huge variety of graphs. Apart from the synthetic graphs, real-world application graphs like Montage, LIGO, Cybershake, and Epigenomic are also considered to grade the performance of the DA-LPP algorithm. Experimental results of the DA-LPP algorithm show improvement in performance in terms of scheduling length ratio, makespan reduction rate , and resource reduction rate when compared with other algorithms like DQWS, DUCO, DCO and EPRD. The results reveal that for 1000 task set with deadline equals to two times of the critical path, the scheduling length ratio of the DA-LPP algorithm is better than DQWS by 35%, DUCO by 23%, DCO by 26 %, and EPRD by 17%.     

Effective real-time scheduling algorithm for cyber physical systems society

CPS (Cyber Physical Systems) tightly couple their cyber factor and physical factor in distributed computing or Grids environments to provide real-time services such as avionics, transportation, manufacturing processes, energy, healthcare, etc. We need to consider not only the cyber space (CPU, network, storage systems, etc.) and the physical space (location, migration, etc.) but also the socio space and mental space for the precise analysis and useful services. In this paper, real-time scheduling algorithms, namely ELST (Effective Least Slack Time First) and H-ELST (Heuristic-Effective Least Slack Time First), are presented for CPS, where servicing node needs to move to serviced node for real-time services. We measure the real-time performance in terms of deadline meet ratio by mathematical analysis and simulations. The results show that our algorithms reduce a deadline miss ratio approximately up to 50% and 20% compared to the conventional real-time scheduling algorithm, FIFO (First In First Out) and LST (Least Slack Time First), respectively.     

Parallelizing with BDSC,a resource-constrained scheduling algorithm for shared and distributed memory systems

We introduce a new parallelization framework for scientific computing based on BDSC, an efficient automatic scheduling algorithm for parallel programs in the presence of resource constraints on the number of processors and their local memory size. BDSC extends Yang and Gerasoulis’s Dominant Sequence Clustering (DSC) algorithm; it uses sophisticated cost models and addresses both shared and distributed parallel memory architectures. We describe BDSC, its integration within the PIPS compiler infrastructure and its application to the parallelization of four well-known scientific applications: Harris, ABF, equake and IS. Our experiments suggest that BDSC’s focus on efficient resource management leads to significant parallelization speedups on both shared and distributed memory systems, improving upon DSC results, as shown by the comparison of the sequential and parallelized versions of these four applications running on both OpenMP and MPI frameworks.     

A design of RFTOG model for distributed real-time applications

In this paper, we design the Real-Time Fault-Tolerant Object Group (RFTOG) model that supports the grouping of distributed objects that are required for distributed application. The proposed model basically provides two services. One is the group management service, which supports both consistency maintenance and transparency of the replicated objects with a variety of replication mechanisms. It also provides the load balancing of distributed applications. The other is real-time service in an object group. When the clients request the service to the service object selected through the load balance, this service guarantees the service execution within deadline for the clients’ requests. We develop the Naval Air Defense System (NADS) simulator for verifying the effectiveness of the services proposed by the RFTOG model.     

异构传感网中基于组合指派编码模型的节点调度算法

针对感知半径异构无线传感器网络(WSN)中的节点调度问题,提出了一种基于组合指派编码模型的分布式节点调度算法。首先确定最大可能的组个数;然后基于两跳簇概念进行分布式分簇;最后对每个簇中的节点采用组合指派编码模型分布式调度到不同的组中。理论分析与仿真实验表明,与已有基于随机方式与两跳簇方式的调度算法相比,所提算法能更有效地延长网络的生命周期,因此更加适合感知半径异构无线传感器网络环境。