全局EDZL实时调度算法的可调度性判定

可调度性判定就是离线验证实时系统中所有任务是否可调度。通过可调度性判定,能够更好地保证实时系统的可靠性。有多种分析方法可用于可调度性判定,得到的结果有所不同。通过分析在多处理器实时系统中全局EDZL算法的任务需求,考虑带入作业和带出作业对处理器资源的需求。引入最大连续忙区间的概念,以确定带入作业的最大个数,得到了多处理器实时系统中全局EDZL算法的可调度性判定算法。实验结果说明了这种方法提高了通过可调度性判定的任务数量,是一种更紧密的可调度性判断方法。     

多处理器EPDFPfair算法的可调度性判定

针对多处理器实时调度中的最早伪时限优先(EPDF)Pfair算法,分析了EPDF算法在M个处理器平台上的可调度利用率约束,根据基于利用率的充分可调度性判定,提出了一种改进的可调度性判定方法。这种方法可以得到更多的可调度任务集,从而使得满足判定的强实时系统和使用tie-breaking规则困难的动态任务系统的调度有较小的开销。实验结果表明,改进的可调度性判定方法增加了判为可调度的任务集数量,具有较好的性能。     

实时调度EDZL算法的可调度性判定

针对多处理器实时调度中的EDZL调度算法,利用多任务之间的相互干涉关系,找出与多处理器之间的时间约束条件,提出了一种可调度性判定的方法,并对给出的判定方法进行了证明。给出了一种判定多处理器实时EDZL可调度性的算法,这种方法可在设计多处理器实时系统时使用。     

基于负载计算的多处理器全局EDF判定方法

在多处理器实时调度过程中,干涉上界的取值对于可调度性判定的性能具有较大影响。为此,针对实时系统的最早截止期优先调度算法,引入任务松弛的有关概念,提出一种基于负载计算的可调度性判定方法。通过减小问题区间内带入作业的工作负载取值,增加任务集通过可调度性判定的可能。实验结果表明,随着处理器数量的增加,该判定方法较传统方法有5%~10%的性能提升。     

多处理器系统实时调度的可预测性

在多处理器实时系统中,由于调度的不规则性,系统的可预测性判定问题尤为重要。针对多处理器系统中实时任务调度的可预测性问题,给出了不可预测的实时任务集反例,证明了一种可预测的实时任务集合。对于多处理器实时系统中常用的最早截止期零松弛调度算法(earliest deadline zero laxity,EDZL)的可预测性,利用EDZL算法的基本性质,用一种简捷的方法证明了EDZL算法是可预测的。通过仿真系统验证了证明的正确性,该方法可用于多处理器及分布式实时系统的设计和验证。     

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

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

基于周期虚拟缩减的实时任务调度和分析方法

针对航天器等安全关键系统中实时任务调度和可调度性分析的实际问题, 提出基于任务周期虚拟缩减的可调度性判定方法, 构建SHT (strong-hard task)任务模型对强硬实时任务进行精确描述, 并根据任务时间特性分配优先级. 虚拟化所有强实时任务为一个硬实时任务, 对此硬实时任务周期虚拟缩减并计算出其最差虚拟执行时间, 然后按RMS可调度性判定公式判定. 给出了判定方法的严格证明, 可对包含n个SHT任务的任务集进行快速可调度性判定, 此算法时间复杂度仅为O(n²). 在我国空间站计算机进行了对比验证, 实验表明判定效率优于现有可调度性判定方法, 平均运行时间开销降低了41.8%, 可调度率提高了5.7%.     

一种改进的RM可调度性判定算法

固定优先级任务可调度性判定是实时系统调度理论研究的核心问题之一.目前已有的各种判定方法可归结为两大类:多项式时间调度判定和确切性判定.多项式时间调度判定通常采用调度充分条件来进行,为此,许多理想条件下基于RM(rate monotonic)调度算法的CPU利用率最小上界被提了出来.确切性判定利用RM调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的.但是由于时间复杂度较差,确切性判定方法难以实现在线分析.提出了一种改进的RM可调度性判定方法(improved schedulability test algorithm,简称ISTA).首先介绍了任务调度空间这一概念,并提出了二叉树表示,然后进一步提出了相关的剪枝理论.在此基础上,研究了任务之间可调度性的相关性及其对判定任务集可调度性的影响,提出并证明了相关的定理.最后基于提出的定理,给出了一种改进的伪多项式时间可调度性判定算法,并与已有的判定方法进行了比较.仿真结果表明,该算法平均性能作为任务集内任务个数的函数具有显著提高.     

基于最优虚拟截止日期多处理器混合时序调度

为提高混合临界系统实时调度有效性,提出基于最优虚拟截止日期的多处理器混合时序调度算法.将现有非抢占最早截止时间可调度性测试算法推广到混合临界多处理器系统,引入时序保证技术,确保系统在两个不同临界值间过渡;将所提可调度性测试扩展到混合临界系统,利用系统级截止期缩减参数控制,设计最优虚拟截止日期分配策略.仿真结果表明,采用最优虚拟截止时间分配策略可调度性测试可发现大量额外可调度任务集,实现混合临界多处理器非抢占调度性能提升.     

基于分批优化的实时多处理器系统的集成动态调度算法

提出了一种基于分批优化的实时多处理器系统的集成动态调度算法，该算法采用在每次扩充当前局部调度时，通过对所选取的一批任务进行优化分配的策略以及软实时任务的服务质量QoS（quality of service）降级策略，以统一方式实现了对实时多处理器糸统中硬、软实时任务的集成动态调度．进行了大量的模拟研究，结果表明．在多种任务参数取值下，新算法的调度成功率均高于近视算法（Myopic Algorithm）．     

Comments on “Generalized rate monotonic schedulability bounds using relative period ratios”

In this Letter, it is shown that the schedulability test method for task sets with the maximum period ratio larger than or equal to 2 presented in the paper [Wei et al., Generalized rate monotonic schedulability bounds using relative period ratios, Information Processing Letters 107 (5) (2008) 142-148] is not exactly correct by presenting a counter-example. Correct sufficient conditions for using period ratios in RM schedulability test when the maximum period ratio is not less than 2 are also presented.     

Efficient online schedulability tests for real-time systems

Many computer systems, such as those for open system environments or multimedia services, need an efficient schedulability test for online admission control of new jobs. Although various polynomial time schedulability tests have been proposed, they often fail to decide the schedulability of the system precisely when the system is heavily loaded. On the other hand, most precise schedulability tests proposed to date have a high complexity and may not be suitable for online tests. We present new efficient online schedulability tests for both the periodic process model [C. L. Liu et al., (1973)] and the multiframe process model [A. K. Mok et al., (1997)] in uniprocessor environments. The schedulability tests are shown to be more precise and efficient than any existing polynomial-time schedulability tests. Moreover, the tests can be done incrementally as each new task arrives at the system. Our proposed tests can also be used for the multiframe model where a task may have different computation times in different periods. We show the performance of the proposed schedulability tests in several simulation experiments.     

An analysis of EDF schedulability on a multiprocessor

A new schedulability test is derived for preemptive deadline scheduling of periodic or sporadic real-time tasks on a single-queue m-server system. The new test allows the task deadline to be more or less than the task period, and is based on a new analysis concept, called a /spl mu/-busy interval. This generalizes a result of Goossens et al. [2003] that a system of periodic tasks with maximum individual task utilization u/sub max/ is EDF-schedulable on m processors if the total utilization does not exceed m(1 /sup max/)+u/sub max/. The new test allows the analysis of hybrid EDF-US [x] scheduling, and the conclusion that EDF-US[1/2] is optimal, with a guaranteed worst-case schedulable utilization of (m +1)/2.     

应用于实时系统的DMS算法可调度性分析

固定优先级任务的可调度性判定是实时系统调度理论研究的核心问题之一。本文提出了一种可行的DMS可调度性判定方法——确切性判定方法（precised schedulability test algorithln,简称PSTA）,利用DMS调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的。首先给出了DMS调度模型,介绍了可调度性判定的基本思想,然后进一步通过实验提出并证明了PSTA相关的定理。     

Schedulability Analysis of Global Scheduling Algorithms on Multiprocessor Platforms

This paper addresses the schedulability problem of periodic and sporadic real-time task sets with constrained deadlines preemptively scheduled on a multiprocessor platform composed by identical processors. We assume that a global work-conserving scheduler is used and migration from one processor to another is allowed during a task lifetime. First, a general method to derive schedulability conditions for multiprocessor real-time systems will be presented. The analysis will be applied to two typical scheduling algorithms: earliest deadline first (EDF) and fixed priority (FP). Then, the derived schedulability conditions will be tightened, refining the analysis with a simple and effective technique that significantly improves the percentage of accepted task sets. The effectiveness of the proposed test is shown through an extensive set of synthetic experiments.     

Using an adversary simulator to evaluate global EDF scheduling of sporadic task sets on multiprocessors

Schedulability analysis of real-time multiprocessor systems is usually based on sufficient but not necessary tests that produce pessimistic results. One difficulty in evaluating the effectiveness of sufficient schedulability tests has been distinguishing the cause of a task set failing the test, i.e., finding out whether the task set is in fact not schedulable or it is actually schedulable but the test itself is too pessimistic. Necessary schedulability tests help to distinguish between these two situations, since if a task set fails in the test then it is guaranteed to be unschedulable. An adversary simulator is a scheduling simulator that uses the non-determinism of the task model to generate scenarios that will stress a specific scheduling algorithm, improving the odds of a deadline miss. In this paper we describe a new adversary simulator algorithm for sporadic task sets executed on multiprocessors scheduled by Global Earliest Deadline First (G-EDF). It is shown that this new adversary simulator is more effective as a necessary test than existing approaches. We also estimate the uncertainty regarding G-EDF by applying to the same task sets a well-known sufficient schedulability test from the literature and the necessary schedulability test based on the adversary simulator.