The Non-preemptive Scheduling of Periodic Tasks upon Multiprocessors

The non-preemptive scheduling of periodic task systems upon processing platforms comprised of several identical processors is considered. The exact problem has previously been proven intractable even upon single processors; sufficient conditions are presented here for determining whether a given periodic task system will meet all deadlines if scheduled non-preemptively upon a multiprocessor platform using the earliest-deadline first scheduling algorithm. Supported in part by the National Science Foundation (Grant Nos. CCR-9988327 and ITR-0082866). Sanjoy Baruah is a professor of Computer Science at the University of North Carolina at Chapel Hill. He received his Ph.D. from the University of Texas at Austin in 1993. His research and teaching interests are in scheduling theory, real-time and safety-critical system design, and resource-allocation and sharing in distributed computing environments.     

Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems

The utilization bound for earliest deadline first (EDF) scheduling is extended from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. Since the multiprocessor utilization bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms. As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account. Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing, release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches, and mode changes.     

面向多处理器的实时周期任务容错调度算法研究

主副版本策略是多处理器系统实时任务调度中处理容错问题的一种重要方式.根据分布式控制系统的特点,本文提出一种改进的FTRMBF算法-PR-FTRMBF,以提高系统周期任务的可调度性.在FTRMBF等已有的调度算法中,当没有处理器分配给当前副版本时,将为副版本分配新的处理器;本文提出的改进算法则以回溯的方式重新分配主版本.在保证系统实时性能和容错能力的前提下,节省了处理器数目.仿真实验表明,与FTRMBF算法相比,改进算法显著提高了系统任务的可调度性.     

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.     

多处理器混合关键性系统中的划分调度策略

多核处理器正越发广泛地应用到现代嵌入式系统的设计与实现当中,其强大的计算能力为将多个不同关键性级别的功能子系统集成到统一的共享资源平台提供了支持.混合关键性系统的调度问题即便在单处理器平台中都极具挑战性,在多处理器平台则更为困难.将目前资源利用率最高的单处理器混合关键性调度算法EY-VD扩展到多处理器平台中.首先,结合传统的划分调度策略提出了适用于多处理器混合关键性系统的MC-PEDF(mixedcriticality partitioned earliest deadline first)划分调度算法.尽管比之前的算法有更好的可调度性能,但传统的划分策略不能有效地平衡不同关键性级别下的负载,故其不完全适用于混合关键性系统.为了克服传统策略的不足,提出了划分调度策略OCOP(one criticality one partition).OCOP允许系统在关键性模式切换时对实时任务集进行重新划分,进而更好地平衡各个处理器在不同关键性模式中的资源利用率.基于OCOP,提出了第2种划分调度算法MC-MP-EDF(mixed-criticality multi-partitioned EDF).基于随机生成任务集的仿真实验结果表明,与MC-PEDF和已有的算法相比,MC-MP-EDF能够显著地提高系统的可调度性,尤其是在处理器数量较多的系统中.     

队头阻塞优化的EDF可重构任务调度算法

针对最早截止时刻优先(earliest deadline first,EDF)调度算法队头阻塞任务导致资源利用率和配置端口复用率低下的问题,提出一种队头阻塞优化的EDF实时调度算法.通过定义无效阻塞任务并引入无效阻塞任务丢弃策略,提前判定和丢弃无法调度成功的任务,以利于后续任务调度;通过定义队头阻塞任务最早布局成功时刻...     

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

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

容错最早时限优先调度

最早时限优先调度（EDF）是最优的动态可抢占先级实时调度算法,具有灵活、简单和高效的特点,但并没有考虑实时系统的容错要求。本文提出一种容错EDF算法,实现在规定时间段内的单个错误容错。本文详细分析了该算法的容错机制,证明了该算法的正确性,并给出了算法的可调度条件。     

多特征协调的实时调度算法

目前大多数实时调度算法都依据单一的特征参数确定任务优先级,本文提出一种基于多特征协调的实时调度算法,对特定高优先级任务优先处理,并且对其他任务的调度不产生任何影响。同时,在系统超载的时候,有效避免了EDF算法性能的急剧下降。实验结果表明,该算法有效地保证了特定任务的调度优先级,相对于EDF算法性能有明显改进。     

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.     

一种有约束关系的实时周期任务调度算法研究

在多核嵌入式平台下,针对具有约束关系的实时周期任务,提出一种基于任务关键因子和截止时间的调度算法BVDS(Based on Value and Deadline Scheduling).该算法以有效利用处理器为原则,根据每个处理器的实际运行情况,为有可能在截止时间前完成的任务分配处理器资源.算法实现分为两个阶段:第一阶段根据任务的到达时间、关键因子以及执行时间构建等待任务链表;第二阶段,在执行过程中,充分考虑不同任务的执行时间以及任务之间的约束关系进行优先级分配.实验结果表明,该算法在牺牲少量处理器利用率的前提下,有效地降低了任务的死限丢失率.     

减链约束多处理器任务在三处理器中的调度

研究三个并行处理器环境中,具有递减链约束的多处理器任务的调度问题,调度目标 是最小化总处理时间,假设单项任务需单位处理时间.首先给出了减链调度问题的最优化性质 与条件,并说明了减链调度问题仍然是NP难的.随后基于两段flow-shop问题的Johnson's算 法的修正和减链调度问题最优化性质,提出了一个启发式算法,并从分析和仿真计算两方面说 明该算法是有效的和高效的.     

TinyOS中DSA调度策略的研究

针对TinyOS任务调度采用非剥夺的先来先服务调度策略,而产生的系统紧急任务不能及时得到响应及节点吞吐量下降情况,该文提出一种新的可抢占时限短作业调度策略——DSA。在绝对时限前执行硬实时任务,满足了系统对实时任务的响应要求,提高处理器的响应速度,对软实时任务实行短作业优先调度策略,提高系统的吞吐量。在TinyOS上测试表明,DSA策略在不影响TinyOS原有性能的情况下,改进了传感器网络承担实时性任务的运行效果。     

PLUFS: 一种开销敏感的周期任务在线多处理器节能实时调度算法

现有周期任务多处理器节能调度算法虽然在考虑处理器实际开销情况下可以实现较好的节能效果,但仍不能保证最优可调度性.针对嵌入式实时系统中不可忽视的状态切换开销,提出一种开销敏感的周期任务在线多处理器节能实时调度算法PLUFS.该算法通过TL面流调度模型与处理器实际切换开销模型相结合,在每个TL面的初始时刻、任务结束执行时刻实现节能调度,在不违反周期任务集最优可调度性的前提下,达到实时约束与能耗节余的合理折中.经过理论证明和模拟实验,结果表明：PLUFS算法不仅保证了周期任务集的最优可调度性,而且节能效果整体优于现有算法,能耗节余比现有算法提高约10%～20%.     

Hybrid Task and Message Scheduling in Hard Real Time Distributed Systems over FlexRay Bus

FlexRay is a vehicular communication protocol designed to meet growing requirements in hard real time automotive systems and to support time triggered as well as event triggered paradigms. Thus, there has been a lot of recent interest in timing analysis techniques in order to provide bounds for the message communication times on FlexRay. In this paper, we present an approach to compute the WCRT （worst case response time） for periodic and sporadic tasks, within a FlexRay node, responsible for sending messages on the FlexRay SS （static segment） and DS （dynamic segment）. On the other hand, we propose a scheduling table for messages transmitted over the FlexRay SS. An interesting innovation would be the use of a scheduling algorithm performed on a FlexRay node to guarantee the arrival of the right data on the right time and to ensure that every task meets its deadline. As application, we will use the extended SAE （society of automotive engineers） benchmark for the FlexRay network to identify the static and dynamic tasks, and calculate the response time, based on a hybrid scheduling model to further prove that the deadline of the SAE benchmark applications is insured.     

Scheduling Messages with Earliest Deadline Techniques

Thispaper discusses the applicability of earliest deadline schedulingtechniques to local area networks. The focus is on controllerarea networks (the only standard that allows direct implementation)although a comparison is tried with other possible implementationson different network topologies (and contention resolution methods).Message scheduling follows the well-known EDF algorithm. Thepaper discusses the limitations and the problems in the implementationof the algorithm on standard controller area network protocols.Then, it presents a short study on the comparative effectivenessof other contention resolution methods modeled on the standardsToken-ring and Carrier Sense Multiple Access-Collision DetectionCSMA-CD (all implementing the earliest deadline scheduling policy.)Finally, the paper shows how to compute an optimal packet sizewith respect to the guaranteeability of the real-time properties,exploiting the trade-off between preemptability and efficiency.     

多目标粒子群算法求解混合多处理机任务作业车间调度问题研究

混合多处理任务作业车间调度(Hybrid Job-shop Scheduling with Multiprocessor Task,HJSMT)是作业车间调度和多处理机任务调度的混合调度问题,即每个工件由多个工序组成且每个工序都需要一组机器同时进行加工.目前对HJSMT研究较少且集中于单目标问题,因此针对多目标HJSM...     

周期性实时任务LLF调度算法改进

为减少松弛度计算和系统调度次数,对周期性实时任务的最低松弛度优先(LLF)调度算法进行了改进。在系统处理过程中引入最低松弛度优先队列,当任务松弛度相同时,开始截止时刻早的任务靠近队首。在任务控制块(TCB)中引入预执行时间,任务被调度以后,如果没有更为紧迫的任务到达,任务执行到预执行时间结束才退出处理器。Matlab仿真试验表明,改进算法有效减少了周期性实时任务的松弛度计算次数和系统调度次数,提高了处理器的利用率。     

一种实时异构嵌入式系统的任务调度算法

异构分布式系统已被广泛应用在实时嵌入式系统中,而调度算法是在进行嵌入式系统综合时,确保系统实现性能目标的一个关键问题,这是一个NP-完全问题.现有的算法主要是启发式算法,性能还有待提高.提出了一个异构分布式系统的动态BLevel优先(dynamic BLevel first,简称DBLF)算法,算法选择就绪任务中动态BLevel值最大的任务进行调度,用插入法为任务分配处理器,遵循以下3个插入原则:满足任务先后顺序关系;任务的最早完成时间(earliest-finish-time,简称EFT)最小;在EFT相等时,优先分配到利用率较低的处理器上.与现有算法比较可以看出,DBLF算法可以有效降低调度长度.     

Scheduling of Offset Free Systems

In this paper, we study the problem of scheduling hard real-time periodic tasks. We consider independent tasks which are characterized by a period, a hard deadline and a computation time, but where the offsets may be chosen by the scheduling algorithm. We first show that we can restrict the problem by considering non-equivalent offset assignments. More precisely, we show that there are finitely many non-equivalent offset assignments and we propose a method to reduce significantly this number and consider only the minimal number of non-equivalent offset assignments. We then propose an optimal offset assignment rule which considers only the non-equivalent offset assignments. However the number of combinations remains exponential; for this reason, we also propose a nearly optimal algorithm with a more reasonable time complexity.