A Constant-Approximate Feasibility Test for?Multiprocessor Real-Time Scheduling

We devise an approximate feasibility test for multiprocessor real-time scheduling in the sporadic task model. We give an algorithm that, given a task system and ε>0, correctly decides either that the task system can be scheduled using the Earliest Deadline First algorithm on m speed-(2?1/m+ε) machines, or that the system is not schedulable by any algorithm on m unit speed machines. This speedup bound is known to be the best possible for EDF. The running time of the algorithm is polynomial in the size of the task system and 1/ε. We also provide a generalized tight bound that trades off speed with additional machines.     

EDZL scheduling analysis

A schedulability test is derived for the global Earliest Deadline Zero Laxity (EDZL) scheduling algorithm on a platform with multiple identical processors. The test is sufficient, but not necessary, to guarantee that a system of independent sporadic tasks with arbitrary deadlines will be successfully scheduled, with no missed deadlines, by the multiprocessor EDZL algorithm. Global EDZL is known to be at least as effective as global Earliest-Deadline-First (EDF) in scheduling task sets to meet deadlines. It is shown, by testing on large numbers of pseudo-randomly generated task sets, that the combination of EDZL and the new schedulability test is able to guarantee that far more task sets meet deadlines than the combination of EDF and known EDF schedulability tests. In the second part of the paper, an improved version of the EDZL-schedulability test is presented. This new algorithm is able to efficiently exploit information on the slack values of interfering tasks, to iteratively refine the estimation of the interference a task can be subjected to. This iterative algorithm is shown to have better performance than the initial test, in terms of schedulable task sets detected.

Preference-oriented real-time scheduling and its application in fault-tolerant systems

In this paper, we consider a set of real-time periodic tasks where some tasks are preferably executed as soon as possible (ASAP) and others as late as possible (ALAP) while still meeting their deadlines. After introducing the idea of preference-oriented (PO) execution, we formally define the concept of PO-optimality. For fully-loaded systems (with 100% utilization), we first propose a PO-optimal scheduler, namely ASAP-Ensured Earliest Deadline (SEED), by focusing on ASAP tasks where the optimality of ALAP tasks’ preference is achieved implicitly due to the harmonicity of the PO-optimal schedules for such systems. Then, for under-utilized systems (with less than 100% utilization), we show the discrepancies between different PO-optimal schedules. By extending SEED, we propose a generalized Preference-Oriented Earliest Deadline (POED) scheduler that can obtain a PO-optimal schedule for any schedulable task set. The application of the POED scheduler in a dual-processor fault-tolerant system is further illustrated. We evaluate the proposed PO-optimal schedulers through extensive simulations. The results show that, comparing to that of the well-known EDF scheduler, the scheduling overheads of SEED and POED are higher (but still manageable) due to the additional consideration of tasks’ preferences. However, SEED and POED can achieve the preference-oriented execution objectives in a more successful way than EDF.     

基于EDF调度算法的端到端延迟保证方法

EDF(EarliestDeadlineFirst)是一种高效的调度算法。为了将其应用于提供端到端延迟保证,提出了一种新的算法JT-EDF(JitterTunableEDF),并证明了所有的端到端EDF调度算法都可以在相同的条件下保证相同的端到端延迟界。     

基于流量隔离的公平聚集器

为实现对微流的最差延迟最早聚集,并对聚集完成的宏流进行过滤与排序,实现宏流公平调度,提出基于流量隔离的公平聚集器(FAFI)。FAFI解决了在基于流量聚集调度模式中,同一宏流内部各竞争微流之间的突发流量对数据包传输延迟产生影响的问题。通过严格的数学推理与演算,证明FAFI的有效性。仿真实验验证了对FAFI模型的定量分析结果和FAFI模型的性能。     

Limited carry-in technique for real-time multi-core scheduling

Schedulability analysis has been widely studied to provide offline timing guarantees for a set of real-time tasks. The so-called limited carry-in technique, which can be orthogonally incorporated into many different multi-core schedulability analysis methods, was originally introduced for Earliest Deadline First (EDF) scheduling to derive a tighter bound on the amount of interference of carry-in jobs at the expense of investigating a pseudo-polynomial number of intervals. This technique has been later adapted for Fixed-Priority (FP) scheduling to obtain the carry-in bound efficiently by examining only one interval, leading to a significant improvement in multi-core schedulability analysis. However, such a successful result has not yet been transferred to any other non-FP scheduling algorithms. Motivated by this, this paper presents a generic limited carry-in technique that is applicable to any work-conserving algorithms. Specifically, this paper derives a carry-in bound in an algorithm-independent manner and demonstrates how to apply the bound to existing non-FP schedulability analysis methods for better schedulability.     

多处理器固定优先级算法的可调度性分析

针对多处理器实时调度中的固定优先级(FP)调度算法,提出了一种改进的可调度性判定方法。引入Baruah的最早截止期优先(EDF)窗口分析框架,将高优先级任务带入作业的最大数量限定为m-1(m为处理器个数),进而对任务的干涉上界进行重新界定,并由此得到一个更加紧密的可调度性判定充分条件。仿真实验结果表明,该方法增加了通过判定任务集的数量,体现出更优的可调度判定性能。     

Demand-based schedulability analysis for real-time multi-core scheduling

In real-time systems, schedulability analysis has been widely studied to provide offline guarantees on temporal correctness, producing many analysis methods. The demand-based schedulability analysis method has a great potential for high schedulability performance and broad applicability. However, such a potential is not yet fully realized for real-time multi-core scheduling mainly due to (i) the difficulty of calculating the resource demand under dynamic priority scheduling algorithms that are favorable to multi-cores, and (ii) the lack of understanding how to combine the analysis framework with deadline-miss conditions specialized for those scheduling algorithms. Addressing those two issues, to the best of our knowledge, this paper presents the first demand-based schedulability analysis for dynamic job-priority scheduling algorithms: EDZL (Earliest Deadline first until Zero-Laxity) and LLF (Least Laxity First), which are known to be effective for real-time multi-core scheduling. To this end, we first derive demand bound functions that compute the maximum possible amount of resource demand of jobs of each task while the priority of each job can change dynamically under EDZL and LLF. Then, we develop demand-based schedulability analyses for EDZL and LLF, by incorporating those new demand bound functions into the existing demand-based analysis framework. Finally, we combine the framework with additional deadline-miss conditions specialized for those two laxity-based dynamic job-priority scheduling algorithms, yielding tighter schedulability analyses. Via simulations, we demonstrate that the proposed schedulability analyses outperform the existing schedulability analyses for EDZL and LLF.     

New response time analysis for global EDF on a multiprocessor platform

Time-predictability is the most important requirement for a real-time system, and researchers have therefore paid attention to the duration between the arrival and completion of a real-time task, called response time. RTA (Response Time Analysis) studies, however, rely on the same technique, yielding room for further improvement, especially regarding multiprocessor platforms. For this paper, we investigated the properties of an existing utilization-based schedulability analysis for global EDF (Earliest Deadline First) on a multiprocessor platform, and developed a new RTA technique based on the corresponding properties, which calculates the response times of tasks in task sets deemed schedulable by the existing analysis. We demonstrated through simulations that our proposed RTA technique not only calculates response times that are less pessimistic than those of the existing approach, but also successfully derives response times that cannot be obtained by the existing approach.     

A novel view on bounding execution demand under mixed-criticality EDF

Real-Time Systems - In this paper, we are concerned with scheduling a mix of high-criticality (HI) and low-criticality (LO) tasks under Earliest Deadline First (EDF) on one processor. To this end,...     

Improved multiprocessor global schedulability analysis

A new technique was recently introduced by Bonifaci et al. for the analysis of real-time systems scheduled on multiprocessor platforms by the global Earliest Deadline First (EDF) scheduling algorithm. In this paper, this technique is generalized so that it is applicable to the schedulability analysis of real-time systems scheduled on multiprocessor platforms by any work-conserving algorithm. The resulting analysis technique is applied to obtain a new sufficient global Deadline Monotonic (DM) schedulability test. It is shown that this new test is quantitatively superior to pre-existing DM schedulability analysis tests; in addition, the degree of its deviation from any hypothetical optimal scheduler (that may be clairvoyant) is quantitatively bounded. A new global EDF schedulability test is also proposed here that builds on the results of Bonifaci et al. This new test is shown to be less pessimistic and more widely applicable than the earlier result was, while retaining the strong theoretical properties of the earlier result.     

实时调度算法分类研究

调度是实时系统的一个研究热点。一个调度算法的好坏决定着实时任务能否在规定的时限内完成。本文对实时调度进行了讨论;研究了经典静态调度算法中的速率单调调度算法,并提出了对该算法的改进;分析了动态调度中的最早截止期最优先算法;最后,对实时调度研究策略方向进行了展望。     

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.     

On the convergence of the holistic analysis for EDF distributed systems

Dynamic scheduling techniques, and EDF (Earliest Deadline First) in particular, have demonstrated their ability to increase the schedulability of real time systems compared to fixed-priority scheduling. In distributed systems, the scheduling policies of the processing nodes tend to be the same as in stand-alone systems and, although few EDF networks exist, it is foreseen that dynamic scheduling will gradually develop into real-time networks. There are some response time analysis techniques for EDF scheduled distributed systems, mostly derived from the holistic analysis developed by Spuri. A major factor influencing the response time is the release jitter of each task, which is the maximum variation suffered by the release time of the task jobs. The convergence of the holistic analysis in the context of EDF distributed systems with shared resources had not been studied until now. There is a circular dependency between the task release jitter values, response times and the preemption level ceilings of shared resources. In this paper we present an extension of Spuri’s algorithm and we demonstrate that its iterative formulas are non-decreasing, even in the presence of shared resources. This result enables us to assert that the new algorithm converges towards a solution for the response times of the tasks and messages in a distributed system.¹     

一种网络延迟精确控制的调度算法

在网络数据传输调度中，基于最早时限优先（EDF）的算法具有单点最优的延迟界限控制能力。现有的各种EDF改进算法，主要着眼于提供延迟上界的保证能力，而当采用机顶盒之类的缓冲能力较弱的设备作为客户终端时，还需要网络提供精确的延迟下界控制能力。在原有EDF改进算法的基础上提出了精确延迟界控制的最早时限优先算法。该算法不但能同时保证延迟上界和下界，还使得节点可以独立地决定为数据流分配的缓冲区大小，并增加了节点允许抖动量的取值范围，从而提高了节点数据的转发效率。     

改进型EDF调度算法的研究与实现

分析实时系统EDF调度算法的优缺点,为优化报文调度,提出基于EDF的相对价值可提升的且相对价值最大的任务最优先调度算法,采用多个参数计算报文的优先级。实验结果表明,与传统EDF调度算法相比,改进型算法能充分利用总线带宽,对总线报文进行最优化调度。     

嵌入式软件实时调度模型设计与仿真

针对应用系统的数据有效期需求,利用基于模型的软件设计方法,提出一种基于生产者-消费者模型的实时调度模型,该模型放宽了最早截止期优先调度算法中周期对截止期的限制,解决了模型中的优先约束问题。设计的实时调度仿真程序可以真实地反映系统对任务的实际调度情况。     

Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling

This paper examines the relative effectiveness of fixed priority pre-emptive scheduling in a uniprocessor system, compared to an optimal algorithm such as Earliest Deadline First (EDF). The quantitative metric used in this comparison is the processor speedup factor, equivalent to the factor by which processor speed needs to increase to ensure that any taskset that is schedulable according to an optimal scheduling algorithm can be scheduled using fixed priority pre-emptive scheduling, assuming an optimal priority assignment policy.     

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.     

面向数据流的嵌入式系统中缓存需求量与反应时间的同步优化

同步数据流图(SynchronousDataflowGraph,SDF)是一个在嵌入式系统设计中应用很广泛的模型。基于该模型人们设计出了多种调度算法,针对信号处理领域中的实际问题作了大量的优化工作,提高了系统的性能。但是原先存在的调度算法是分别以缓存优化,或者反应时间优化为其优化目标,从而导致了一些矛盾结果:比如说减少缓存需求量的同时,增大了反应时间;又或者减少反应时间的时候,增大了缓存的需求量。而该文在EDF(最早最终期限优先算法,一种反应时间优算法)的基础上,不以增大系统优化后的反应时间为代价,进一步对其缓存进行优化。从而达到在减少系统反应时间的同时,也能够减少实际的缓存开销的目的。