Contemporary research on real-time scheduling considered obsolete

The reason for research in scheduling is an economical one, viz., to optimise the utilisation of resources. Up to the present time, almost all interest is directed towards processor scheduling. Departing from the requirements holding for real-time computing, in this paper it is shown that maximum processor utilisation has become obsolete as an optimisation criterion for industrial real-time systems. It is also shown that the earliest-deadline-first discipline and certain modifications thereof provide a satisfactory and final answer to all real-life scheduling needs. To this end, all intrinsic properties of this discipline are compiled and discussed in order to show that it is the most advantageous scheme at hand, characterised by efficiency and allowing for 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 presented, 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. Then, by taking industrial practice and actual cost relations into account, evaluation criteria and design principles for real-time computing systems are developed. The paper closes with pointing to those open optimisation questions, scheduling research ought to address if it wants to deal with practically relevant problems, viz., minimisation of software costs, software complexity, and complexity of schedules, synchronisation sequences, inter-task communication, etc. In other words, simplicity is to be maximised to enhance system dependability and predictability of system behaviour.     

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

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

Towards a stable Earliest Deadline scheduling algorithm

Earliest Deadline algorithm is today the most attractive real-time scheduling theory. However, should the processor experience a transient overload, Earliest Deadline scheduling can not directly ensure that almost the most important tasks of the application are guaranteed. Schedulability condition should be employed to detect transient overloads before they occur, so that these transient overloads can be handle in an appropriate way. We say that Earliest Deadline scheduling is then unstable. The Regisseur is a real-time scheduling controller which provides the stability property to the Earliest Deadline scheduler by the mean of an importance criterion and by the mean of such schedulability condition. In this paper, we first describe the Regisseur principles and the way it works. Then an example is given to point out its performances.     

静态实时中间件的优先级映射问题

使用截止期单调(DM)调度算法和分布式优先级冲顶资源访问控制协议(DPCP)的实时CORBA系统中,当节点的本地优先级个数不足时,必须将多个全局优先级映射成一个本地优先级.这需要:①判定映射后任务可调度性的充分必要条件;②减少时间复杂度的映射算法.为此,推导出判定条件,确定了DGPM映射算法.该算法在保证系统可调度的前提下分配任务,或者证明映射后系统不可调度.证明了DGPM算法能调度其他直序列优先级映射算法可调度的任务和GCS集合.判定条件和算法在实际项目中得到了应用.     

一种无抖动的分布式多媒体任务调度算法

在分布式多媒体系统中,资源的管理和分配算法是保证应用的服务质量（ＱｏＳ）的关键问题,而资源管理中,ＱｏＳ协商和确认都和多媒体任务调芳算法有关,任务调度算法是资源管理的重要内容。现有的调度算法ＥＤＦ,ＲＭ,ＤＳｒ适用在分布式多媒体系统中,有局限性。本文基于风车调度模型,提出了一种无抖动调度的逐步消除候选项的并行算法ＤＭＳｒ,能达到分布系统中多媒体任务周期调度的无抖动特点,并讨论了算法的计算复杂度,证     

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.     

Robust Adaptive Metrics for Deadline Assignment in Distributed Hard Real-Time Systems

Distributed real-time applications usually consist of several component tasks and must be completed by its end-to-end (E-T-E) deadline. As long as the E-T-E deadline of an application is met, the strategy used for dividing it up for component tasks does not affect the application itself. One would therefore like to slice each application E-T-E deadline and assign the slices to component tasks so as to maximize the schedulability of the component tasks, and hence the application. Distribution of the E-T-E deadline over component tasks is a difficult and important problem since there exists a circular dependency between deadline distribution and task assignment. We propose a new deadline-distribution scheme which has two major improvements over the best scheme known to date. It can distribute task deadlines prior to task assignment and relies on new adaptive metrics that yield significantly better performance in the presence of high resource contention. The deadline-distribution problem is formulated for distributed hard real-time systems with relaxed locality constraints, where schedulability analysis must be performed at pre-run-time, and only a subset of the tasks are constrained by pre-assignment to specific processors. Although it is applicable to any scheduling policy, the proposed deadline-distribution scheme is evaluated for a non-preemptive, time-driven scheduling policy. Using extensive simulations, we show that the proposed adaptive metrics deliver much better performance (in terms of success ratio and maximum task lateness) than their non-adaptive counterparts. In particular, the simulation results indicate that, for small systems, the adaptive metrics can improve the success ratio by as much as an order of magnitude. Moreover, the new adaptive metrics are found to exhibit very robust performance over a large variety of application and architecture scenarios.     

硬实时系统在强分区约束下的双层分区调度

文中研究了硬实时系统在强分区约束下的双层分区的调度问题,合理建立了强分区约束下的双层分区调度模型,给出了最坏情况下的分区任务集可调度的判定条件.同时,在此基础上,提出了与分区利用率匹配的分区设计方法,导出了该方法下的系统可调度利用率的最小上限.仿真实验表明,在严格实时的条件下,文中提出的方法相对于现有方法更具优越性,并提高了分区可调度利用率的最小上限.     

基于改进型统一调度算法改善任务集的可调度性

实时系统要求任务在最差情况下能在其截止时间前获得结果,若超过了其截止时间,也会认为是错误的行为,所以改进任务可调度性分析、提高任务集可调度性尤其重要。统一调度能结合固定优先级调度的优点,防止不必要的抢占,降低资源额外销耗,能够提高任务集合的可调度性;但其任务的可调度性分析方法过于粗糙,影响任务最差响应时间分析的结果,降低了任务集的可调度性。针对存在的问题,基于统一调度,增加任务运行阶段数,重新建立任务模型,并提出通过分配任务抢占阈值、调整运行阶段的抢占阈值与长度,优化任务可容忍阻塞,改善任务集可调度性的算法。最后,实验表明,与统一调度算法及其他算法相比,所提出的调度算法能够有效改善任务集的可调度性。     

Integrated dynamic scheduling of hard and QoS degradable real-time tasks in multiprocessor systems

Many time-critical applications require predictable performance and tasks in these applications have deadlines to be met. For tasks with hard deadlines, a deadline miss can be catastrophic while for Quality of Service (QoS) degradable tasks (soft real-time tasks) timely approximate results of poorer quality or occasional deadline misses are acceptable. Imprecise computation and (m,k)-firm guarantee are two workload models that quantify the trade-off between schedulability and result quality. In this paper, we propose dynamic scheduling algorithms for integrated scheduling of real-time tasks, represented by these workload models, in multiprocessor systems. The algorithms aim at improving the schedulability of tasks by exploiting the properties of these models in QoS degradation. We also show how the proposed algorithms can be adapted for integrated scheduling of multimedia streams and hard real-time tasks, and demonstrate their effectiveness in quantifying QoS degradation. Through simulation, we evaluate the performance of these algorithms using the metrics – success ratio (measure of schedulability) and quality. Our simulation results show that one of the proposed algorithms, multilevel degradation algorithm, outperforms the others in terms of both the performance metrics.