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

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

EDF调度算法可调度性分析方法的改进研究

任务集的可调度性分析是实时系统研究和应用的关键问题。针对抢占式与不可抢占式EDF(earliest deadline first)调度算法, 分别给出了实时任务集新的可调度性测试条件, 针对任务集为可调度时可以实现快速判定。通过与已有的EDF算法的可调度性判定充要条件相结合, 提出了改进的抢占式与不可抢占式EDF算法的可调度性分析方法。仿真实验表明, 相对现有EDF算法的可调度性分析方法, 所提出的方法能有效提高算法性能。     

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

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

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

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

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

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

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

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

基于单调速率的可调度性判定改进算法

在单调速率调度策略的基础上,提出一种改进的任务集可调度性判定算法。该算法通过设定时钟变量模拟调度过程中的系统时钟,在时钟变量值增长过程中,根据任务优先级从高到低的顺序,分析各个任务的截止时间限的满足情况,判定任务的可调度性,从而确定任务集的可调度性。通过实例分析及与现有判定方法的比较,验证了该算法的正确性和高效性。     

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

针对航天器等安全关键系统中实时任务调度和可调度性分析的实际问题, 提出基于任务周期虚拟缩减的可调度性判定方法, 构建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).首先介绍了任务调度空间这一概念,并提出了二叉树表示,然后进一步提出了相关的剪枝理论.在此基础上,研究了任务之间可调度性的相关性及其对判定任务集可调度性的影响,提出并证明了相关的定理.最后基于提出的定理,给出了一种改进的伪多项式时间可调度性判定算法,并与已有的判定方法进行了比较.仿真结果表明,该算法平均性能作为任务集内任务个数的函数具有显著提高.     

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

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

Generalized rate monotonic schedulability bounds using relative period ratios

One of the most well-studied scheduling algorithms for real-time systems is the Rate Monotonic (RM) scheduling for periodic tasks. In this paper we derive a generalized RM schedulability bound by considering relative period ratios among tasks in a system. We show that schedulability bounds published earlier are special cases of our generalized bound. Our new bound may provide a higher value than earlier results.     

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.     

Cache-Conscious Limited Preemptive Scheduling

In multi-tasking real-time systems, inter-task cache interference due to preemptions degrades schedulability as well as performance. To address this problem, we propose a novel scheduling scheme, called limited preemptive scheduling (LPS), that limits preemptions to execution points with small cache-related preemption costs. Limiting preemptions decreases the cache-related preemption costs of tasks but increases blocking delay of higher priority tasks. The proposed scheme makes an optimal trade-off between these two factors to maximize the schedulability of a given task set while minimizing cache-related preemption delay of tasks. Experimental results show that the LPS scheme improves the maximum schedulable utilization by up to 40\% compared with the traditional fully preemptive scheduling (FPS) scheme. The results also show that up to 20\% of processor time is saved by the LPS scheme due to reduction in the cache-related preemption costs. Finally, the results show that both the improvement of schedulability and the saving of processor time by the LPS scheme increase as the speed gap between the processor and main memory widens.     

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

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

实时中间件动态调度算法的研究及应用

文章建立了实时中间件OPC服务器的实时调度模型,设计了处理混合任务的动态调度算法(基于EDF)和实现方式,分析了算法的可调度性和非周期任务的响应性能及参数设计,并给出了相应的调度结果。     

Static priority scheduling of event-triggered real-time embedded systems

Real-time embedded systems are often specified as a collection of independent tasks, each generating a sequence of event-triggered code blocks. The goal of scheduling tasks in this domain is to find an execution order which satisfies all real-time constraints. Within the context of recurring real-time tasks, all previous work either allowed preemptions, or only considered dynamic scheduling, and generally had exponential complexity. However, for many embedded systems running on limited resources, preemptive scheduling may be very costly due to high context switching and memory overheads, and dynamic scheduling can be less desirable due to high CPU overhead. In this paper, we study static priority scheduling of recurring real-time tasks. We focus on and obtain schedule-theoretic results for the non-preemptive uniprocessor case. To achieve this, we derive a sufficient (albeit not necessary) condition for schedulability under static priority scheduling and show that this condition can be efficiently tested in practice. The latter technique is demonstrated with examples, where in each case, an optimal solution for a given problem specification is obtained within reasonable time, by first detecting good candidates using meta-heuristics, and then by testing them for schedulability.

实时事务调度及静态可调度性分析

在类似闭环控制的硬实时数据库应用环境,实时事务具有一定的静态可预报性,其中实时事务的可调度性分析是维护实时数据库时间正确性的基础.通过利用抢占阈值,提出了一种新的实时事务处理模型,它集成了CPU调度和数据调度,实现离线并发控制,具有单阻塞的特征与好的静态可预测性,并有利于降低事务系统的负载和改善可调度性.进一步由此建立了实时事务的静态可调度性分析模型以及求最优可行调度的整数规划模型,该模型有利于达到实时事务调度的整体优化.     

长释放时间间隔优先的混合任务调度算法

针对混合任务实时调度的需求和MUF算法的局限性,提出了一种长释放时间间隔优先的混合任务实时调度算法LRIF,该算法除了可对周期性硬实时任务提供调度保证外,同时还可确保非周期性软实时任务的可调度率。论文还提出了LRIF调度算法的可调度性分析方法,并讨论了LRIF调度算法的实现方法。     

Interference-aware fixed-priority schedulability analysis on multiprocessors

This paper presents new schedulability tests for preemptive global fixed-priority (FP) scheduling of sporadic tasks on identical multiprocessor platform. One of the main challenges in deriving a schedulability test for global FP scheduling is identifying the worst-case runtime behavior, i.e., the critical instant, at which the release of a job suffers the maximum interference from the jobs of its higher priority tasks. Unfortunately, the critical instant is not yet known for sporadic tasks under global FP scheduling. To overcome this limitation, pessimism is introduced during the schedulability analysis to safely approximate the worst-case. The endeavor in this paper is to reduce such pessimism by proposing three new schedulability tests for global FP scheduling. Another challenge for global FP scheduling is the problem of assigning the fixed priorities to the tasks because no efficient method to find the optimal priority ordering in such case is currently known. Each of the schedulability tests proposed in this paper can be used to determine the priority of each task based on Audsley’s approach. It is shown that the proposed tests not only theoretically dominate but also empirically perform better than the state-of-the-art schedulability test for global FP scheduling of sporadic tasks.