主桙副版本模型中预分配容错实时调度算法

实时系统中任务的超时完成可能导致灾难性后果,因此要求系统具备容错处理能力,以保证系统出错后的实时性及可靠性。主/副版本模型是提高实时系统容错能力的有效技术。传统的容错实时调度算法通过为副版本预留处理器时间来实现软件容错,为副版本预留的处理器时间在系统运行过程中需动态调整,增加了系统的容错调度开销。提出一种基于res‐backw ards‐RM 预分配子算法的容错实时调度算法BCE*,通过限制预分配过程中高优先级任务的抢占条件,在不影响系统可调度性的同时可以有效避免副版本预留时间的动态调整,降低系统的容错调度开销。仿真实验验证了BC E*算法的可行性及有效性,且在系统出错概率及主版本负载较低的环境下,BC E*算法对系统容错调度开销的优化效果更显著。     

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

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

异构分布式系统中基于负载均衡的容错调度算法

提出了基于主/从版本的具有容错功能的进程调度算法HDALF和HDLDF,且分别给出两种算法的时间复杂度并对算法的负载均衡性和节点资源利用率作了讨论.与以往容错调度算法不同的是,此算法是在被动进程复制模式下、适合于异构分布式系统的容错调度算法.而以往的研究都是建立在主从版本进程有相等的负载或执行时间相同的模型基础上,或者仅适合于同构分布式系统.实验结果表明,HDALF算法和HDLDF算法的性能比基于同构分布式模型下的两阶段算法更加优越.并且得出了这样的结果：当系统发生故障前后的负载均衡性权值相等时,在负载均衡和处理机资源利用率方面,HDLDF算法都要优于HDALF算法.     

一种基于多处理机的容错实时任务调度算法

容错是实时系统的重要要求,在实时系统中,若一个实时任务没在规定的时间期限内完成,则认为系统出现错误,针对多处理机实时系统提出了一种容错调度算法．算法采用了任务的主从备份技术和Ｆｉｒｓｔ－ｆｉｔ启发式方法,通过为可能因处理机故障而执行失败的实时任务预留重新运行的时间来实现容错功能;并通过对预留时间段的重叠利用和无错时预留时间的回收分配,来提高处理机的利用率和系统对任务的接收率．模拟结果表明算法是有效     

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

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

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

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

异构集群中基于优先级的任务容错调度算法

提出一种基于任务优先级的容错调度算法,任务的优先级并不是由用户指定,而是由任务的开始时间、执行时间和截止期限决定的。该算法能够容忍异构集群系统中一个节点故障,采用主动/被动副版本相结合的执行方式和重叠技术的备份方式,提高系统资源利用率。通过实验证明了该算法在容错调度中的可靠性和高效性。     

基于异构分布式系统的实时容错调度算法

目前文献中研究的实时容错调度算法都是基于同构分布式系统，系统中的所有处理机完全相同。该文首先建立了一个基于异构分布式系统实时容错调度模型，异构分布式系统中的各个处理机均不相同。基于该异构分布式系统模型，该文引入了可靠性代价（reliability cost）概念，并提出两种静态实时容错调度算法（RTFTNO和RTFTRC）用于调度周期性实时容错任务。算法RTFTRC在调度任务时，尽量使系统的可靠性代价最小；而算法RTFTNO在调度实时任务时，没有考虑系统的可靠性代价。该文详细讨论了两种调度算法的性能。性能模拟实验分别比较了两个算法的可靠性代价，超时比率和可调度性；并研究了任务的计算时间与可靠性代价的关系以及调度长度阈值与最小处理机个数的关系。实验结果表明，算法RTFTRC的性能优于算法RTFTNO。     

一种基于负载均衡异构分布式系统的改进容错调度算法*

基于基/副版本技术提出了一种具有容错功能的静态进程调度算法。给出了一个新的设计模型,并在该模型上提出HDAL算法。此前类似负载均衡容错调度算法都是通过排序来解决故障发生前后的负载均衡调度问题。该算法与以往算法不同之处就是在不依赖排序情况下,通过引进控制进程来解决负载均衡调度问题,并且该算法的负载均衡性在一定程度上具有了可控性。最后通过模拟实验得到以下有意义的结论：在业务繁忙的异构系统中,HDAL算法比以往算法资源利用率高,负载均衡性更好,并且在调度速度上优势明显。     

面向运行时间预测和容错感知的网格资源分配

提出与描述了一种面向任务运行时间预测和容错感知（Fault-Aware）的网格资源分配策略,采用主动容错的方式,在资源出错之前尽量提前避免它出错或异常的情况发生。该策略把网格中任务的运行时间（runtime）预测和资源的在线时间（uptime）预测结合起来,相对于普通的调度策略具有比较高的资源利用率。在具体的CoBRA网格中间件中实现了该容错感知调度,描述了实现该容错感知调度策略模块的功能。测试过程中选择了睡眠任务技术,划分四种不同的场景进行实验,把该容错感知资源分配与普通的FCFS调度策略进行比较,结果证明在可变化的资源可用性的情况下系统可以加快应用的整体执行时间,具有很小的偏差。     

Feasible processor allocation in a Hard-Real-Time environment

Consider the problem of scheduling a set of preemptible tasks in one or more processor systems. The task system consists of a set of independent tasks or a task set with precedence relations. Each task is characterized by execution time and deadline. This article presents scheduling algorithms that guarantee all time constraints. These algorithms are so easy to implement that they can be used in real-time operating systems. An overview is given for the different feasible scheduling algorithms of some task and processor systems.     

一种改进的基于任务复制的多核调度算法

在多核系统中,任务调度是决定系统性能的关键因素之一。为优化任务调度,基于一些典型的任务调度算法（如PPA,徐成提出的算法等）,提出了一种新的任务调度算法。该算法一方面合理确定前驱任务复制的先后顺序,而且进行两个阶段的复制,从而可以复制更多的前驱任务以减少调度长度和处理器上空余时间;另一方面,通过去除不影响任务系统调度长度的冗余簇,然后进行簇之间的合并,以减少处理机的数目和调度长度。实验表明,改进后的算法在任务调度的性能上优于典型算法。     

通用调度框架的改进及其在Linux中的实现

在嵌入式Linux实时系统中,要求内核对不同时问约束的任务采用不同的调度算法.但目前Linux内核采用单一的实时调度模式,不能灵活地执行多种调度算法,也就无法满足实时系统中实时任务的时间约束.引入了一种能够在Linux内核调度中执行多种调度算法的框架,即通用调度框架(GSF),并改进了其中的多算法调用机制,从而更好地在Linux内核中实现GSF.     

一种开放混合实时系统的开放自适应调度算法

开放计算环境下的实时与非实时任务不确定并发,以及多种实时约束混合的复杂约束系统,即开放混合实时系统的需求越来越广泛.通过引入接收控制、调度服务器、自适应调节机制,提出一种开放环境下的自适应实时系统调度架构--OARtS(open adaptive real-time scheduling).它能适应开放计算环境的不确定性,有控制地接受实时任务运行;可根据系统空闲计算带宽变化,自适应地调节任务的实时等级,使得系统运行在最优的实时性能上;对于软实时任务,可根据其计算带宽需求变化,自适应地调节其计算带宽分配,以适应任务执行时间时变引起的实时不确定性.     

基于Milter实现的中文垃圾邮件过滤系统

提出一种基于内容的中文垃圾邮件实时过滤系统的实现方案，该系统建立在Linux的Sendmail邮件服务器上，通过Milter接口实时提取邮件内容，并结合中文分词及文本分类算法对邮件实施分类和过滤。该系统可嵌入多种文本分类算法，具有良好的可扩展性。通过测试对该系统内嵌入的不同分类算法模型进行了分析和比较。     

异构Hadoop环境下的实时作业调度算法

为提升Hadoop集群在异构环境下处理硬实时作业的性能,提出一种基于历史进度自动调整作业优先级的调度算法（HAPS）。该算法实时监控作业进度信息,对作业进度率进行指数平滑预测,计算作业剩余执行时间,动态估算作业空闲时间。并据此实时更新作业队列中作业的优先级顺序,优先调度空闲时间小的作业。实验结果表明,HAPS有效地提高了异构环境下硬实时作业的执行成功率。     

树型网格计算环境下的自适应任务调度算法

提出一种基于树型计算网格的自适应调度算法,实现对小粒度独立任务和用户大作业的自适应最优调度。通过对网格环境的实时检测,给出了基于节点负载状况、节点任务执行时间、任务传输时间和任务特性的自适应调度算法,即基于最优任务分配方案的启发式任务调度算法。通过实验与其他调度算法的比较,证明了所提出的任务调度算法在负载平衡和最优跨度方面具有明显的优越性。     

Scheduling optional computations for adaptive real-time systems

At present, the critical computations of real-time systems are guaranteed before run-time by performing a worst-case analysis of the system's timing and resource requirements. The result is that real-time systems are engineered to have spare capacity, under normal operation. A challenge of current research is to make use of this spare capacity, in order to satisfy requirements for adaptivity in the system. Adaptivity can be implemented by optional computations with firm deadlines, which can be guaranteed at run-time by the use of flexible scheduling. This report assumes that the algorithms which attempt to guarantee optional computations at run-time, actually run on the same processor as the optional and critical computations themselves. The report starts with a brief survey of the complex requirements for adaptivity within real-time systems. Such requirements can include task hierarchies composed of interdependent subtasks each with its own utility. Evidence is cited which indicates that the run-time support for a computational model which supports all such requirements, would incur overheads so large, that little spare capacity would remain for the optional computations themselves. Following this, the report presents a constrained computational model, which, it is claimed, could be cost-effectively supported at run-time. The model is nevertheless general enough to satisfy many of the requirements for adaptivity. The constrained model uses Best Effort Admissions Policy to arbitrate between three categories of optional computation, each with its own utility level. The viability of the constrained model is demonstrated by simulation studies which compare the performance of the model to that of First-Come-First-Served Admissions Policy.     

Resource reclaiming in multiprocessor real-time systems

Most real-time scheduling algorithms schedule tasks with regard to their worst case computation times. Resources reclaiming refers to the problem of utilizing the resources left unused by a task when it executes in less than its worst case computation time, or when a task is deleted from the current schedule. Dynamic resource reclaiming algorithms that are effective, avoid any run time anomalies, and have bounded overhead costs that are independent of the number of tasks in the schedule are presented. Each task is assumed to have a worst case computation time, a deadline, and a set of resource requirements. The algorithms utilize the information given in a multiprocessor task schedule and perform online local optimization. The effectiveness of the algorithms is demonstrated through simulation studies     

异构分布式实时仿真系统的容错调度算法

异构分布式实时仿真系统是一类特殊的实时系统,基于改进的SP(spare processor)容错模型(checkpoint-based spare processor,简称CSP)对其容错问题进行了研究.首先,根据仿真系统的特点提出了两个命题,这是后续工作的基础;而后,基于Markov链对仿真任务的最坏反应时间进行了分析,并提出了仿真任务的可调度性分析规则;最后,基于CSP容错模型和上述可调度分析规则提出了异构分布式实时仿真系统的容错调度算法CSP-RTFT.算法的仿真结果表明:该算法较之基于SP模型的算法SP-RTFT可获得更好的稳定性、更高的任务接收率;缺点是资源利用率比PB模型下的算法要低.