单调速率及其扩展算法的可调度性判定

任务可调度性判定是实时系统调度理论研究的核心问题.单调速率(RM)算法是实时调度的重要算法,自其提出以来已被广泛研究.然而到目前为止,尚缺乏专题性的文章来系统而深入地探讨RM及其扩展算法的可调度性判定,以及各种现实条件和实现方式(包括任务调度的时间开销和任务同步问题等)对可调度性的影响.围绕RM算法下的可调度性判定问题,由浅入深,系统性地讨论各种不同假设和实现方式对可调度性的影响,具体为下述3大类问题：（1）理想的RM算法下的可调度性判定的CPU利用率最小上界最小及可调度的充分必要条件;（2）考虑调度时间开销情况下的可调度性判定条件;（3）优先级反转协议及其对可调度性的影响.给除了具体实例来叙述上述问题,并从算法复杂度和可检测率两方面比较各种算法的优劣。     

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

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

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

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

经典RM调度算法在无人机发动机试车台软件开发中的应用

现代无人机发动机测试项目多、实时性要求高,早期的基于非实时的片上系统不能很好地满足测试要求。本文以某型无人机发动机试车台软件系统实际开发为例,在软件开发中引入了经典RM调度算法,分析了经典RM算法的可调度性判定法则,描述了片上系统任务集设计过程,进行了RM可调度性理论判定。通过对任务集的实际可调度性测试表明：硬件利用率最大可达到93．8％,达到设计指标要求;系统运行稳定可靠,并取得预期效果。     

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

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

定时器驱动的RM调度机制建模及其性能优化

在Katcher等人对定时器驱动的RM(Rate Monotonic)调度机制研究的基础上，通过对该机制下实时任务抢占行为的分析，建立了周期性任务的抢占模型，给出了直接抢占发生的充分必要条件，据此确定了任务间的抢占关系，进而精确了可调性的判定条件，然后讨论了系统的平均响应时间．依据此抢占模型，受生物界寄生现象的启发，提出了一个改善嵌入式系统实时性能的方法，将获取机制和利用机制分离，屏蔽了复杂优化计算对目标嵌入式系统性能的负面影响．最后，通过实验验证了该方法在改善抢占关系、减少抢占开销和增强系统可调度性方面的有效性，结果表明可调度利用率可以提高0．25％～6．64％。     

基于EDF调度策略的端到端实时系统可调度性分析算法

端到端实时任务调度模型可用于描述许多分布式实时系统.提出一种基于EDF调度策略的端到端实时任务调度模型,给出了端到端实时系统的可调度性判定条件,并提出其可调度性分析算法,该可调度性判定条件及可调度性分析算法适用于采用非连续工作型同步协议和连续工作型同步协议控制下的端到端实时系统.与固定优先级的端到端实时任务调度模型及其算法相比,基于EDF调度策略的端到端实时任务调度模型和算法更加简单和易于实现,仿真结果也表明具有较高的性能.     

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

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

混合实时事务的延期单调速率调度算法及其可调度性分析

对于含有实时和非实时两部分的混合实时应用，传统的单调速率调度算法(RM)已不再适用.为此，该文引入“混合实时事务”的概念，并针对这类事务提出一种延期单调速率调度算法(DRM)；着重分析了DRM算法对混合实时事务的可调度性；进行了实验测试与性能分析比较．结果表明，事务集中混合实时事务占的比例越高，混合事务中非实时子事务占的比例越大，该算法的CPU使用率阈值就越高，且在各种情况下，DRM算法与RM算法相比性能都更优，最低情况也与之一样．     

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

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

现场级硬实时网络在线调度

通过对主要周期和非周期硬实时调度算法的深入研究，提出了一种可用于调度链路数据包的在线硬实时调度系统(ARTCS)。该调度器基于单调比率调度算法：RM、风车调度算法Sr和轮询服务器调度算法，能快速判定可调度性，进而自动生成总线表，使调度算法将数据包作为周期数据包进行调度。ARTCS简单、易用，有效地利用了总线带宽。顺序执行总线表，不仅能保证硬实时的性能，而且避免了消息传输中的中断和阻塞，因而较好地满足了现场总线领域中硬实时通信系统的要求。     

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.     

SET-MRTS：一种多处理器实时系统可调度性实验平台

近年来,随着实时调度研究的快速发展,可调度性实验的复杂性随之增加,然而,由于缺乏标准化、模块化的可调度性实验工具,研究者往往需要耗费大量时间进行实验;此外,由于实验源码不能公开获得,使得实验结果难以验证,实验代码难以重用与扩展。针对可调度性实验重复工作量大、难以验证的问题,提出一种可调度性实验基础框架。该框架通过随机分布产生任务系统集合,并测试其可调度性,基于该框架设计并实现了一个新的可调度性实验开源平台——SET-MRTS。该平台采用模块化架构设计了任务模块、处理器模块、共享资源模块、算法库、配置解析模块以及输出模块。实验结果表明,SET-MRTS支持单/多处理器实时调度算法和实时同步协议分析,能够正确地进行可调度性对比实验,输出直观的实验结果,并且支持算法库的扩充,与算法库中已实现的算法进行对比实验,具有良好的兼容性与可扩展性。SET-MRTS是第一个支持完整实验流程,包括算法实现、参数配置、结果统计、图表绘制等的可调度性实验开源平台。     

一种新的组优先级动态实时调度算法

传统动态调度算法由于对优先级个数没有限制,在实际应用中往往受制约,达不到很好的调度性能.针对此问题,考虑硬实时抢占任务调度需要,提出一种新的组优先级动态实时调度算法.研究作业执行顺序改变对系统可调度性能的影响,给出作业分组可调度性能测试.新算法将满足分组可调度测试公式的作业作为一个任务组,各任务组之间按照最小截止期优先调度,任务组内按照最短作业优先的原则执行作业.仿真结果表明,与最小截止期优先等传统调度算法相比,新算法不仅能有效降低算法所需优先级个数,还能提高任务调度的成功率,缩短平均响应时间,减少任务切换次数.     

An efficient approach for the multiprocessor non-preemptive strictly periodic task scheduling problem

Strict periodicity constraint is of great importance since it concerns some hard real-time systems where missing deadlines leads to catastrophic situations. However, the problem of schedulability analysis for non-preemptive strictly periodic tasks on a multiprocessor platform is even more intractable than the one with the common periodicity. In order to implement such systems, designers need effective tools based on fast and near-optimal solutions.This paper presents a schedulability analysis which results mainly in a, two versions, task assignment and start-time calculation algorithm. The first one targets the harmonic task periods case while the second one targets the non-harmonic task periods case. Each version is based on a sufficient uniprocessor schedulability test. In addition, for the non-harmonic case which is the most intractable, the uniprocessor sufficient schedulability test uses the strictly periodic task utilization factor. This factor stands for the fraction of time spent to execute a task while its strict periodicity and the ones of the already scheduled tasks are met. As a result, an efficient and easily implementable scheduling algorithm is proposed which begins by assigning tasks to processors then attributes a start-time to every task in such a way that strict periodicity and deadline constraints are met. The effectiveness of the proposed scheduling algorithm, in both versions, has been shown by a performance evaluation and comparisons with an optimal and a similar suboptimal solution.     

Minimum and maximum utilization bounds for multiprocessor rate monotonic scheduling

The utilization bound for real-time rate monotonic (RM) scheduling on uniprocessors is extended to multiprocessors with partitioning-based scheduling. This allows fast schedulability tests to be performed on multiprocessors and quantifies the influence of key parameters, such as the number of processors and task sizes on the schedulability of the system. The multiprocessor utilization bound is a function of the allocation algorithm, so among all the allocation algorithms there exists at least one allocation algorithm providing the minimum multiprocessor utilization bound, and one allocation algorithm providing the maximum multiprocessor utilization bound. We prove that the multiprocessor utilization bound associated with the allocation heuristic worst fit (WF) coincides with that minimum if we use Liu and Layland's bound (LLB) as the uniprocessor schedulability condition. In addition, we present a class of allocation algorithms sharing the same multiprocessor utilization bound which coincides with the aforementioned maximum using LLB. The heuristics first fit decreasing (FFD) and best fit decreasing (BFD) belong to this class. Thus, not even an optimal allocation algorithm can guarantee a higher multiprocessor utilization bound than that of FFD and BFD using LLB. Finally, the pessimism of the multiprocessor utilization bounds is estimated through extensive simulations.     

基于RTLinux的实时测控系统

为了提高和解决工业实时测控系统中的实时性与多任务调度问题，提出了将RTLinux引入了工业测控领域的实现方法；从分析研究RTLinux的实现原理和特征出发，详细介绍了一套工业控制计‘算机测控系统的硬件结构，着重论述了RTLinux应用于工业实时测控系统领域的软件开发过程，成功地实现了一个基于RTLinux的多任务实时测控系统，最后应用速率单调调度算法及其可调度性判定定理，对测控系统实时性和可调度性进行丁分析与测试，测试结果满足测控系统的实时性要求。