控制系统中实时任务的动态优化调度算法

提出一种新的调度算法——带有非周期服务器的EDF调度算法.分析了所有任务的可调度性,给出了可调度条件,并给出一种新的周期性任务模型以及主优先级和辅助优先级的概念.它们在保证任务可调度的前提下,对周期性任务的采样频率和控制延时进行优化.仿真结果表明,该算法可以提高周期性任务的采样频率,并降低控制延时,即能优化系统的性能.     

Energy-efficient scheduling of real-time tasks with shared resources

This paper explores the energy-efficient scheduling of real-time tasks on a non-ideal DVS processor in the presence of resource sharing. We assume that tasks are periodic, preemptive and may access to shared resources. When dynamic-priority and fixed-priority scheduling are considered, we use the earliest deadline first (EDF) algorithm and the rate monotonic (RM) algorithm to schedule the given set of tasks. Based on the stack resource policy (SRP), we propose an approach, called blocking-aware two-speed (BATS) algorithm, to synchronize the tasks with shared resources and to calculate appropriate execution speeds so that the shared resources can be accessed in a mutual exclusive manner and the energy consumption can be reduced. Particularly, BATS uses a static low speed to execute tasks initially, and then it switches to a high speed dynamically whenever a task blocks a higher priority task. More specifically, the processor runs at the high speed from the beginning of the blocking until the deadline of the blocked task or the processor becomes idle. In order to guarantee that the deadlines of tasks are met, the static low speed and the dynamic high speeds are derived based on the theoretical analysis of the schedulability of tasks. Compared with existing work, BATS achieves more energy saving because its dynamic high speeds are lower than that of existing work and the processor has less chance to execute tasks at the high speeds. The schedulability analysis and the properties of our proposed BATS are provided in this paper. We also evaluated the capabilities of BATS by a series of experiments, for which we have some encouraging results.     

EDF统一调度硬实时周期任务和偶发任务的可调度性判定算法

现有的硬实时周期任务和非周期任务的混合调度方法都没有保证非周期任务的实时性,所以不适合调度具有强实时要求的偶发任务.通过分析和计算EDF算法调度偶发任务所占用的空闲时间和挪用时间,以及调度后对空闲时间和最大可挪用时间的影响,提出一种采用EDF算法统一调度硬实时周期任务和偶发任务时的可调度性充分判定算法.最后用仿真实验得出了该算法在不同系统负载下的判定准确率和偶发任务的平均响应时间.     

Implementation and evaluation of global and partitioned scheduling in a real-time OS

In this work, we provide an experimental comparison between Global-EDF and Partitioned-EDF, considering the run-time overhead of a real-time operating system (RTOS). Recent works have confirmed that OS implementation aspects, such as the choice of scheduling data structures and interrupt handling mechanisms, impact real-time schedulability as much as scheduling theoretic aspects. However, these studies used real-time patches applied into a general-purpose OS. By measuring the run-time overhead of an RTOS designed from scratch, we show how close the schedulability ratio of task sets is to the theoretical hard real-time schedulability tests. Moreover, we show how a well-designed object-oriented RTOS allows code reuse of scheduling components (e.g., thread, scheduling criteria, and schedulers) and easy real-time scheduling extensions. We compare our RTOS to a real-time patch for Linux in terms of the task set schedulability ratio of several generated task sets. In some cases, Global-EDF considering the overhead of the RTOS is superior to Partitioned-EDF considering the overhead of the patched Linux, which clearly shows how different OSs impact hard real-time schedulers.     

Scheduling aperiodic tasks in dynamic priority systems

In this paper we present five new on-line algorithms for servicing soft aperiodic requests in realtime systems, where a set of hard periodic tasks is scheduled using the Earliest Deadline First (EDF) algorithm. All the proposed solutions can achieve full processor utilization and enhance aperiodic responsiveness, still guaranteeing the execution of the periodic tasks. Operation of the algorithms, performance, schedulability analysis, and implementation complexity are discussed and compared with classical alternative solutions, such as background and polling service. Extensive simulations show that algorithms with contained run-time overhead present nearly optimal responsiveness.A valuable contribution of this work is to provide the real-time system designer with a wide range of practical solutions which allow to balance efficiency against implementation complexity.     

Parameter adaptation for generalized multiframe tasks: schedulability analysis,case study,and applications to self-suspending tasks

The generalized multiframe task model (GMF) extends the sporadic task model and multiframe task model. Each frame in the GMF model contains an execution time, a relative deadline, and a minimum inter-arrival time. These parameters are fixed after task specification time in the GMF model. However, multimedia and adaptive control systems may be overloaded and no longer stabilized when the task parameters in such systems are not flexible. In order to address this problem, deadlines and periods of frames may change to alleviate temporal overload, e.g., in the parameter adaptation and elastic scheduling model. In this paper, we propose a new model GMF-PA (the GMF model with parameter adaptation). This model allows task parameters to be flexible in arbitrary-deadline systems. A necessary schedulability test based on mixed-integer linear programming is given to check the schedulability under EDF scheduling and optimally assign frame deadlines and periods at the same time. We also prove that the test is a sufficient and necessary schedulability test when frame deadlines and periods must be integers. An approximation algorithm is also deployed to reduce computational running time and indicates a sufficient schedulability test in general. The speed-up factor of our approximation algorithm is \(1+\epsilon \) where \(\epsilon \) can be arbitrarily small, with respect to the exact schedulability test of GMF-PA tasks under EDF. We also apply the GMF model to self-suspending tasks. By extending recent work on scheduling self-suspending tasks, we remove the assumption that frame deadlines are equally assigned in self-suspending tasks, and the system is extended from constrained-deadline systems to arbitrary-deadline systems. We have done extensive experiments to show that the schedulability ratio is improved using our techniques in our GMF-PA model.     

基于RM与EDF的实时混合调度算法研究

通过对实时系统中静态调度算法RM和动态调度算法EDF的研究与分析,针对两种调度算法在实际应用中的问题,提出了一种基于阈值δ的混合调度算法,将RM与EDF调度算法相结合,并从数学角度描述了混合调度算法的可调度性与实时任务的周期、执行时间等属性之间的关系,给出了混合调度算法可调度性的充分必要条件。最后用实验验证了混合调度算法的有效性。     

An efficient dynamic scheduling algorithm for multiprocessorreal-time systems

Many time-critical applications require predictable performance and tasks in these applications have deadlines to be met. In this paper, we propose an efficient algorithm for nonpreemptive scheduling of dynamically arriving real-time tasks (aperiodic tasks) in multiprocessor systems. A real-time task is characterized by its deadline, resource requirements, and worst case computation time on p processors, where p is the degree of parallelization of the task. We use this parallelism in tasks to meet their deadlines and, thus, obtain better schedulability compared to nonparallelizable task scheduling algorithms. To study the effectiveness of the proposed scheduling algorithm, we have conducted extensive simulation studies and compared its performance with the myopic scheduling algorithm. The simulation studies show that the schedulability of the proposed algorithm is always higher than that of the myopic algorithm for a wide variety of task parameters     

An Upper Bound of Task Loads in a Deadline-D All Busy Period for Multiprocessor Global EDF Real-Time Systems

This paper addresses a number of mathematical issues related to multiprocessor global EDF platforms. We present a deadline-d all busy period and backward interference which are important concepts for multiprocessor EDF systems, and some general schedulability conditions for any studied job are proposed. We formally prove that at most m-1 different tasks’ jobs could contribute their execution time to an interval starting with a P_busy−d, and we propose an approach for computing an exact upper bound of the total deadline-d task load in a given interval. Therefore, the proposed results are important foundations for constructing exact schedulability analyses of global EDF scheduling systems.     

分时EDF算法及其在多媒体操作系统中的应用

提出了一种新的CPU调度算法－－分时EDF（Earliest Deadine First)算法,该算法能保证硬实时任务不丢失死线,并易于在分时系统中实现。以分时EDF算法为基础,提出一种新的CPU层次调度算法－－HRFSFQ,该算法用于多媒体操作系统时能保证各类任务的QoS。最后通过大量实验证明了上述算法的有效性和正确性。     

Rate Monotonic vs. EDF: Judgment Day

Since the first results published in 1973 by Liu and Layland on the Rate Monotonic (RM) and Earliest Deadline First (EDF) algorithms, a lot of progress has been made in the schedulability analysis of periodic task sets. Unfortunately, many misconceptions still exist about the properties of these two scheduling methods, which usually tend to favor RM more than EDF. Typical wrong statements often heard in technical conferences and even in research papers claim that RM is easier to analyze than EDF, it introduces less runtime overhead, it is more predictable in overload conditions, and causes less jitter in task execution.Since the above statements are either wrong, or not precise, it is time to clarify these issues in a systematic fashion, because the use of EDF allows a better exploitation of the available resources and significantly improves system's performance.This paper compares RM against EDF under several aspects, using existing theoretical results, specific simulation experiments, or simple counterexamples to show that many common beliefs are either false or only restricted to specific situations.     

Hybrid Scheduling of Dynamic Task Graphs with Selective Duplication for Multiprocessors under Memory and Time Constraints

This paper presents a hybrid scheduling methodology for task graphs to multiprocessor embedded systems. The proposed methodology is designed for task graphs which are dynamic in nature due to the presence of conditional tasks as well as tasks whose execution times are unpredictable but bounded. We have presented the methodology as a three phase strategy in which task nodes are mapped to the processors in the first (static mapping) phase. In the second (selective duplication) phase some critical nodes are identified and duplicated for possible rescheduling at run-time depending on the code memory constraints of the processors. The third (online) phase is a run-time scheduling algorithm that performs list scheduling based on actual dynamics of the schedule up to the current time. We show that this technique provides better schedule length (up to 20%) compared to previous techniques which are predominantly static in nature with low overhead and comparable in complexity with existing online techniques. The effects of model parameters like number of processors, memory and various task graph parameters on performance are investigated in this paper.     

ORB中实时任务调度的实现

首先讨论了现行的CORBA中实时性应用的缺陷。为了解决这些缺陷,必须对CORBA进行改进,主要讨论对ORB中的任务调度进行改进。在比较了几种静态调度策略（基于速率的策略RMT）和动态调度策略（最早期限策略EDF,最少松弛度策略MLF）的优缺点的基础上,提出了一种动、静态相结合的策略;最重要的优先策略（MIF）。最后用IDL语言定义了ORB中任务调度服务对象与应用的接口,并给出了执行过程。     

一种新型实时调度算法研究

在许多片上特定应用系统中，任务多且切换频繁，任务切换开销大，有时甚至严重影响系统的可调度性．研究了动态可抢占门限调度算法，它通过初始门限值、动态门限值的计算和优化线程分配，实现了在处理器高利用率下，有效降低任务切换开销的目的，并相应地减少了对内存的需求．动态可抢占门限调度算法是将静态抢占门限算法与动态调度算法有机地结合在一起。完成了由静态到动态无缝转换．     

不可抢占式EDF调度算法的可调度性分析

现有的不可抢占式EDF调度算法的可调度性分析判定条件限定实时任务的截止期必须等于其周期,限制了它的使用范围。论文突破这一限制,提出了更具一般性的可调度性分析判定充要条件。通过对可调度性判定充要条件的分析,提出了基于不可抢占式EDF调度算法的周期性实时系统可调度性分析算法。     

OPC实时任务系统动态调度算法的研究与设计

本文基于已有的OPCServer实时任务模型,设计了处理混合任务集的动态调度算法(基于截止期优先)和实现方式。该算法实现了对混合任集可调度性的判断,可以完成有硬实时性要求的非周期性任务和周期性任务的调度,并给出了相应的调度结果。     

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

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

复杂实时系统可调度性判定工具的研究与实现

针对包含多处理器、多分区结构的复杂实时系统存在的可调度性判定问题,提出一种基于仿真方法的任务集可调度性判定工具。通过设定时钟变量模拟任务调度过程,依据纯周期任务集的特性确定仿真区间,调用优化的判定算法,判定任务集的可调度性。测试结果及实例分析表明,该工具能自动、准确、快速地判定任务集的可调度性,并以甘特图的方式绘制任务调度过程,较现有工具更为高效、直观。     

An optimal boundary fair scheduling algorithm for multiprocessor real-time systems

With the emergence of multicore processors, the research on multiprocessor real-time scheduling has caught more researchers’ attention recently. Although the topic has been studied for decades, it is still an evolving research field with many open problems. In this work, focusing on periodic real-time tasks with quantum-based computation requirements and implicit deadlines, we propose a novel optimal scheduling algorithm, namely boundary fair (Bfair), which can achieve full system utilization as the well-known Pfair scheduling algorithms. However, different from Pfair algorithms that make scheduling decisions and enforce proportional progress (i.e., fairness) for all tasks at each and every time unit, Bfair makes scheduling decisions and enforces fairness to tasks only at tasks’ period boundaries (i.e., deadlines of periodic tasks). The correctness of the Bfair algorithm to meet the deadlines of all tasks’ instances is formally proved and its performance is evaluated through extensive simulations. The results show that, compared to that of Pfair algorithms, Bfair can significantly reduce the number of scheduling points (by up to 94%) and the overhead of Bfair at each scheduling point is comparable to that of the most efficient Pfair algorithm (i.e., PD²). Moreover, by aggregating the time allocation of tasks for the time interval between consecutive period boundaries, the resulting Bfair schedule can dramatically reduce the number of required context switches and task migrations (as much as 82% and 85%, respectively) when compared to those of Pfair schedules, which in turn reduces the run-time overhead of the system.     

Load adaptive dynamic scheduling of tasks with hard deadlines useful for industrial applications

All intrinsic properties of the earliest deadline taks scheduling discipline are compiled and discussed in order to show that this is the most advantageous scheme at hand, characterised by efficiency and allowing predictable system behaviour. It is then pointed out how the method naturally extends to the scheduling of tasks having non-pre-emptable regions due to resource access constraints. A sufficient condition is derived, which allows, at any arbitrary point in time and under observation of resource constraints, to check the feasible schedulability of the tasks competing for processor allocation. This condition applies to entirely non-pre-emptable tasks as well. Taking the corresponding overhead into consideration, the circumstances are characterised under which the task context-switches imposed by the scheduling algorithm can be avoided. Favourable consequences of deadline scheduling for virtual storage management are mentioned. Finally, application oriented schemes for coping with transient overloads and thus allowing load adaptive dynamic scheduling are introduced. Such overloads can be easily detected at an early stage utilising the here established schedulability criterion.