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

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

具有依赖关系的周期任务实时调度方法

随着多核技术在嵌入式领域的快速发展,越来越多的功能被集成在同一个平台上,任务之间的关系越来越复杂.而当前大多数的实时周期任务的调度模型都是不考虑任务之间关系的相互独立的任务模型.文中则针对具有依赖关系的周期任务,提出了一种基于ST(Simple-Tree)的实时周期任务调度模型,通过该模型来维护任务之间的依赖关系.此外,为了有效地提高系统利用率以及降低死限丢失率,文中还提出了可延迟时间越短越优先的调度方法并和RM算法、EDF算法进行仿真实验比较,结果表明该方法具有较高的核利用率和较低的死限丢失率.     

强实时系统的调度

实时系统的一个重要研究领域是调度 ,实时任务能否在规定的时限内完成依赖于调度算法的好坏。本文给出了当前强实时系统的主要调度思想和模型 ,并对各算法的特点进行了评述 ,对强实时系统的设计和论证具有重要意义。     

截止时限为关键参数的混合关键级实时任务调度研究

混合关键级系统 (mixed criticality system)的研究源于在单一平台上执行多个重要级不同的功能,当前混合关键级调度研究,一般考虑高关键级任务在不同关键级运行模式表现为或周期或计算时间不同,即以任务释放时间间隔和最差情况执行时间为关键参数.但截至时限(dendline)也是实时任务的重要时间参数,尤其是对硬实时任务,以截止时限作为关键参数进行相应混合关键级调度的研究尚是空白.针对此问题,以截止时限作为关键参数,以响应时间分析为基础,对单处理器平台中的混和关键级任务的可调度性进行分析,并提出了一种预提升关键级的调度算法RCLA(raising critical-level in advance),在低关键级运行模式下,高关键级低优先级任务有限度地提前抢占低关键级高优先级任务的执行,既确保了满足高关键级任务在不同关键级运行模式下的截止时限,也让尽可能多的任务可以被调度执行,使得计算资源得以充分利用.仿真结果验证了RCLA算法的有效性.     

异构分布式控制系统中实时任务的调度算法

分布式控制系统是一种应用极为广泛的异构分布式实时系统，系统中同时存在有多种实时任务，如何将这些任务分配到各个处理器上并保证它们的时限是系统关键技术之一．在结合启发式任务分配算法和单处理器任务调度算法的基础上，提出了一种分布式控制系统的调度算法．该算法考虑了各个处理器的负载均衡，同时又能满足所有任务的时限．仿真结果表明了算法的有效性．     

开放式实时环境中的集成调度框架

开放式实时环境中的多类型实时任务并存的情况给实时调度机制带来了新的需求和挑战．提出了一种适用于开放式实时环境的3层集成调度框架，它基于服务器方式的实时调度理论，把5种既有相关性又有功能互补特征的服务器有机的集成到统一的调度机制中．可支持多种类型的实时任务及非实时任务共存于同一系统的混合调度，并且根据它们的属性自动选择最合适的服务器与之搭配．相对于现有方法，该调度框架可支持的调度对象类型更广泛，易于进行服务质量控制，并且有良好的可扩展性．因此，更适合于开放式实时环境．     

基于多处理机的混合实时任务容错调度

提出了一种混合实时任务容错调度算法．该算法采用Rate Monotonic(RM)算法完成周期任务的静态调度；采用预订处理机时间方法和Earlier Deadline First(EDF)算法动态调度非周期任务；采用主／副版本备份技术确保系统的容错能力．通过充分利用周期任务的剩余处理机时间调度非周期任务和主动备份与被动备份相结合的方法有效地减少了处理机数．仿真结果证明了算法的有效性．     

单调时限调度算法的可调度分析

单调时限调度通过定义Di≤Ti放宽了单调比率调度对被调度任务集的限制,使之更加近似于工程实际,但现有的单调时限调度的可调度分析的充分条件十分复杂。文章提出并证明了基于最小处理器利用率上限的单调时限调度的充分可调度条件,大大简化了单调时限调度的调度分析。     

光纤通道交换机在强实时约束下的分组调度

以光纤通道交换网络强实时约束下的性能研究为背景,采用实时通信中的周期性任务模型,提出了负载匹配的加权轮循分组调度,导出了在该方法下网络消息集严格实时的充要条件,以最差情形下强实时的网络可达负载率为性能衡量指标推证了采用该算法的优越性并通过仿真进行了验证.     

固定优先级抢占调度算法下非周期任务实时性能研究

嵌入式实时系统不仅要在功能上满足需求,而且要在性能上满足实时性需求.给定调度算法,实时性取决于各个任务的到达特征和执行时间.任务的到达特征由应用环境决定.为此,本文研究任务执行时间对实时性能的影响,为嵌入式系统设计提供参考.针对固定优先级抢占调度算法,应用排队论,提出一种非周期实时任务的理论模型.该理论模型包含两个优先级不同的非周期实时任务,给出了任务的执行时间长短对时限错过率、任务响应时间、任务队列长度等实时性能的影响.给出一个应用实例,仿真结果验证了理论模型的正确性.     

基于自平衡的非周期任务动态实时调度算法

为了更有效地进行开放和不可预测系统的载荷管理，提出了一种基于自平衡的动态实时调度模型——DRSSR（Dynamic Real-time Scheduling based on Self-Regulation）.DRSSR把许可控制和QoS降级相结合，采用反馈控制技术来确保系统的性能、消除干扰和提高系统吞吐率.建立了DRSSR的数学模型，并分析了其稳态性能和瞬态性能.最后，一组基于实时操作系统CRTOS-Ⅱ的实验表明，DRSSR在不确定实时环境中具有良好的性能，并且响应快、实现简单.     

可靠性代价驱动的实时任务调度算法

1 概述分布式系统越来越广泛地用于重要的实时系统应用程序中,关键问题在于必须保证每个任务在其截止时间之前完成。在许多实时调度算法中调度性是需要最大化的功能目标之一。为了使实时调度算法更实用,必须考虑任务优先权限制。文[11]中提出将离线分析和在线保证结合使用的方案。文[12]提出了一个分布式实时系统中的最佳任务调度算法。上述算法都是为同构分布式系统设计的,均假定系统中的处理器都是一样的,所以不能直接应用于异构分布式系     

实时系统中的非定期任务调度算法综述

非定期任务调度是实时系统中的一个重要研究内容,综述了实时系统中非定期任务调度算法的研究与进展,按照这些算法的特征分为基于服务器的算法与基于空闲时间的算法两大类别,并着重对每个类别中的不同算法的特征与性能进行了分析,通过对这些算法的比较与分析,希望为实时系统的研究与开发者提供有意义的参考,最后还给出了非定期任务调度进一步研究的思路与建议。     

混合云中基于截止时间和费用约束的调度方法研究*

针对混合云调度中私有云利用率不高和公有云费用偏高的问题,基于性能和费用目标提出了两个调度策略—截止时间优先和费用优先策略,建立了混合云中的任务和资源模型,能够根据用户提交的任务需求自适应选择合适的调度资源,对截止时间要求比较高的任务可以优先调度至公有云,对费用要求高的任务可以优先调度至私有云,而且两种策略均满足截止时间和一定的费用约束,因此相对于其它类似的基准调度方法,本文的两种调度策略在调度完成时间、费用、截止时间超出率和私有云利用率等方面均有很好的表现,尤其是当任务量比较大的时候,两种调度策略表现出更好的自适应性和优势。     

Dynamic Real-time Scheduling of Firm Periodic Tasks with Hard and Soft Aperiodic Tasks

In this paper, we address the problem of the dynamic scheduling of skippable periodic task sets (i.e., period tasks allowing occasional skips of instances), together with aperiodic tasks. Scheduling of tasks is handled thanks to the merging of two existing approaches: the Skip-Over task model and the EDL (Earliest Deadline as Late as possible) aperiodic task server. The objective is to provide two on-line scheduling algorithms, namely EDL-RTO and EDL-BWP, in order to minimize the average response time of soft aperiodic requests, while ensuring that the QoS (Quality of Service) of periodic tasks will never be less than a specified bound. We also extend our results to the acceptance of sporadic tasks (i.e., aperiodic tasks with deadlines). We show that these novel scheduling algorithms have better performance compared to related algorithms regarding aperiodic response time and acceptance ratio. Audrey Marchand guaduated in Computer Engineering at the Ecole polytechnique of the University of Nantes (France), in 2002. She is currently a PhD student at the University of Nantes. Her research interests include real-time scheduling theory, aperiodic service mechanisms, quality of service guarantees in soft real-time systems, and Linux-based real-time operating systems and applications. Maryline Chetto received the degree of Docteur de 3ème cycle in control engineering and the degree of Habilitée à Diriger des Recherches in Computer Science from the University of Nantes, France, in 1984 and 1993, respectively. From 1984 to 1985, she held the position of Assistant professor of Computer Science at the University of Rennes, while her research was with the Institut de Recherche en Informatique et Systèmes Aléatoires, Rennes. In 1986, she returned to Nantes and is currently a professor with the Institute of Technology of the University of Nantes. She is conducting her research at IRCCyN. Her main research interests include scheduling and fault-tolerance technologies for real-time applications. She has published more than 60 journal articles and conference papers in the area of real-time operating systems. She is the leader of a French national R&D project, namely Cleopatre, supported by the French government, which aims to provide free open source real-time solutions.     

基于动态优先级策略的最优软非周期任务调度算法

周期任务与非周期任务的混合调度是实时调度研究的一个重要方向 通过定义“调度”和“逆调度” ,对实时周期任务集在使用EDF算法调度时的可挪用时间进行分析 ,求出了周期任务集在使用EDF调度时的最大可挪用时间 在此基础上 ,提出用于缩短非周期任务响应时间和周转时间的调度算法———ISA(idlestealingalgorithm) ISA算法充分使用最大可挪用时间 ,在保证周期任务满足最后期限的同时能取得非周期任务的最优响应时间和周转时间 证明了ISA算法的最优性 ,并使用仿真实验进行了性能验证     

一种基于VFD多核系统的硬实时任务节能调度算法

由于芯片功耗不断增加,节能已成为一个亟待解决的重要问题.基于全局异步局域同步(GALS)及电压频率域(VFD)技术的多核处理器计算平台,提出周期性硬实时任务节能调度算法.首先将给定任务集中的实时任务按最差匹配递减(WFD)策略映射到各个计算核上,使各计算核的利用率相对更加均衡,然后利用静态电压/频率调整策略,将每一个VFD内各计算核的共享运行频率降至此VFD中负载最重的计算核的利用率以回收并利用空闲时间节能.在静态策略的基础上提出空闲时间重分配(SR)策略,在保证实时任务可调度的前提下,通过进行任务迁移来平衡VFD内各计算核上的空闲时间分布,以进一步降低VFD的共享运行频率,从而降低能耗.实验表明提出的节能算法可取得较好的节能效果.     

End-to-End Utilization Control for Aperiodic Tasks in Distributed Real-Time Systems

An increasing number of DRTS （Distributed model. The key challenges of such DRTS are guaranteeing Real-Time Systems） are employing an end-to-end aperiodic task utilization on multiple processors to achieve overload protection, and meeting the end-to-end deadlines of aperiodic tasks. This paper proposes an end-to-end utilization control architecture and an IC-EAT （Integration Control for End-to-End Aperiodic Tasks） algorithm, which features a distributed feedback loop that dynamically enforces the desired utilization bound on multiple processors. IC-EAT integrates admission control with feedback control, which is able to dynamically determine the QoS （Quality of Service） of incoming tasks and guarantee the end-to-end deadlines of admitted tasks. Then an LQOCM （Linear Quadratic Optimal Control Model） is presented. Finally, experiments demonstrate that, for the end-to-end DRTS whose control matrix G falls into the stable region, the IC-EAT is convergent and stable. Moreover,it is capable of providing better QoS guarantees for end-to-end aperiodic tasks and improving the system throughput.     

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

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

A Scheduling Extension Scheme of the Earliest Deadline First Policy for Hard Real-Time Uniprocessor Systems Integrated on Posix Threads Based on Linux

The Linux operating system has been employed to execute numerous real-time applications. However, it is limited to support soft real-time systems by two scheduling policies: First-In-First-Out and Round Robin. For real-time systems with critical constraints, the soft real-time support and these scheduling policies are still insufficient. In this work, the Earliest Deadline First scheduling policy, which has been shown in theory to be an optimal one in uniprocessor systems, is introduced as an extension of the Linux kernel. This policy is implemented into the real-time class, without the necessity of defining an additional class. The Linux kernel affords capabilities of a hard real-time operating system by an RT-Preempt patch, enabling the use of Linux to implement hard realtime systems. The integration is compliant with the POSIX real-time and thread standards, ensuring applications portability, employing the GLIBC library. In order to validate the proposed implementation, a set of experiments is conducted, showing that a real-time system that cannot be feasibly scheduled using existing policies, attains feasibility when it is scheduled using the integrated Earliest Deadline First policy.