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

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

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

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

网络化运动控制系统的经典调度算法应用研究

网络化运动控制系统作为一类特殊的实时系统,其系统的性能与资源（处理器、网络）的调度密切相关,将实时调度理论应用于网络化运动控制系统非常必要。在对用于单处理器的经典实时调度算法（RM和EDF）以及网络调度的研究现状进行综述的基础上,对网络调度和任务调度的异同点及网络调度的实现方法和应用技术进行了研究。最后,对RM和EDF两类调度算法在网络化运动控制系统中的应用及调度优化问题进行了仿真研究。     

两种经典实时调度算法的研究与实现

速率单调（RM）调度和最早截止期限优先（EDF）调度在实时调度领域占有重要低位。基于一个x86体系结构的小系统上设计实现RM和EDF调度算法，并在不同的工作负载下，以任务截止期错失率作为衡量不同任务调度算法性能优劣的指标，对两种算法进行了性能分析和比较。在通常情况下，RM和EDF都可以保证任务成功调度，EDF算法可承受较多的工作负载。但是随着负载的增加，EDF算法性能急剧下降，到一定过载程度，EDF算法性能低于RM算法。     

单调比率(RM)调度算法及应用

介绍了任务死线不大于其周期的任务集调度条件分析及算法实现。这种约束条件放松, 有利于周期与非周期任务混合模型调度。同时,分析了以往调度算法中单调比率调度算法约束条件, 并指明了计算时间复杂度的缺点。因而,在RM算法基础之上提出一种实时系统调度算法及实现流 程图,并对提出的现场级实时调度算法进行了对比测试。     

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

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

一种改进的容错RM算法

嵌入式实时系统应用越来越广泛,而作为系统核心的调度算法的稳定,健壮和容错也成为日益增长的需求。Liu和Layland提出的经典单调速率算法(RM)并不带有容错功能。利用时域错误掩蔽法(TEM)对经典RM算法进行改进,提出RMF算法,该算法能在一个计划周期中对多个临时错误进行修正。在考虑最坏的两种错误分布情况下,分析RMF可调度性的充要条件并给出算法SCHEDULABLE-RMF检查RMF的可调度性。实验结果表明该算法在系统低负载的情况下能有效降低任务运行结果中的错误比例。     

多处理器单调速率任务分配算法性能评价

多处理器任务分配调度算法是一类经典实时调度算法，然而目前研究在如何根据任务集特征选择任务分配算法方面少见指导性原则，不利于提高多处理器任务分配算法的可调度率及使用尽可能少的处理器达到最优调度结果。基于两种多处理器任务调度策略的比较，本文给出划分策略下的多处理器RM调度的可调度条件和任务分配算法夏分析。仿真结果表明，各任务分配算法所需处理器数与任务集总利用率成正比。同时，分析总结出各算法适用范围及如何根据任务集利用率选择合适算法的指导原则。最后结果还表明，实际算法性能与理论性能界存在差异。     

基于多处理机的混合实时任务容错调度

提出了一种混合实时任务容错调度算法．该算法采用Rate Monotonic(RM)算法完成周期任务的静态调度；采用预订处理机时间方法和Earlier Deadline First(EDF)算法动态调度非周期任务；采用主／副版本备份技术确保系统的容错能力．通过充分利用周期任务的剩余处理机时间调度非周期任务和主动备份与被动备份相结合的方法有效地减少了处理机数．仿真结果证明了算法的有效性．     

一种分布式实时系统任务调度算法的设计

结合分布式系统和实时系统的特点,分析了分布式系统任务调度算法和实时系统任务调度算法,为了能够较好地实现系统的并行性能、实时任务的调度性能以及网络的负载平衡,提出一种将分布式系统任务调度算法和实时系统任务调度算法想结合的算法,采用层次式调度算法以及动态权值的轮转调度算法和速率单调调度算法相结合,在队列权值固定的实验基础上,采用随机改变队列权值的算法,实验证明该随机改变队列权值的算法能够更好地调度任务.     

A Feasibility Decision Algorithm for Rate Monotonic and Deadline Monotonic Scheduling

Rate monotonic and deadline monotonic scheduling are commonly used for periodic real-time task systems. This paper discusses a feasibility decision for a given real-time task system when the system is scheduled by rate monotonic and deadline monotonic scheduling. The time complexity of existing feasibility decision algorithms depends on both the number of tasks and maximum periods or deadlines when the periods and deadlines are integers. This paper presents a new necessary and sufficient condition for a given task system to be feasible and proposes a new feasibility decision algorithm based on that condition. The time complexity of this algorithm depends solely on the number of tasks. This condition can also be applied as a sufficient condition for a task system using priority inheritance protocols to be feasible with rate monotonic and deadline monotonic scheduling.     

提高软非周期任务响应性能的调度算法

实时环境中常常既包含硬周期任务,又包含软非周期任务,引入一种改进软非周期实时任务响应时间的算法.已有的解决混合任务调度问题的方法都是基于速率单调（Rate Monotonic）策略的,其中从周期任务“挪用时间”的算法被证明优于其他所有算法.但是,速率单调算法限制了处理器的使用率,从而使周期任务的可“挪用”时间受到限制.最后期限驱动（Deadline Driven）策略DD可使潜在的处理器利用率达到100%.新算法正是在周期任务的调度中适当加入了DD策略,从而使非周期任务的响应时间得以缩短.仿真实验的结果表明,这种算法的性能优于已有的所有算法,而由它所带来的额外开销却不算很高.     

The Non-Optimality of the Monotonic Priority Assignments for Hard Real-Time Offset Free Systems

In this paper, we study the problem of scheduling hard real-time periodic tasks with static priority pre-emptive algorithms. We consider tasks which are characterized by a period, a hard deadline, a computation time and an offset (the time of the first request), where the offsets may be chosen by the scheduling algorithm, hence the denomination offset free systems.We study the rate monotonic and the deadline monotonic priority assignments for this kind of system and we compare the offset free systems and the asynchronous systems in terms of priority assignment. Hence, we show that the rate and the deadline monotonic priority assignments are not optimal for offset free systems.     

Probabilistic optimisation of checkpoint intervals for real-time multi-tasks

This article considers the checkpoint placement problem for real-time systems. In our environment, multiple real-time tasks with arbitrary periods are scheduled in the system by the rate monotonic algorithm, and checkpoints are inserted at a constant interval in each task while the width of the interval is different with respect to the task. We derive an explicit formula of the probability that all the tasks are successfully completed with a given set of checkpoint intervals. Then we determine the optimal checkpoint intervals that maximise the probability of task completion. The probability computation includes the schedulability analysis with respect to the numbers of re-executed checkpoint intervals. Our method does not necessitate any algebraic condition on the periods of the scheduled tasks.     

一种静态优先级保序饱和分配算法

在通信、雷达、导航以及各种消费类电子产品等领域,嵌入式实时调度已逐渐成为电子电气系统的控制核心,成本与性价比都是设计者需要考虑的重要内容.实际应用中,系统能够支持的优先级教目是有限的,当任务数目多于系统优先级数目时,RM,DM等优先级非受限最优算法尽管已经不再适用,但是仍然可以作为任务的自然优先级来辅助系统设计.利用自然优先级先验知识,提出一种保序饱和分配算法,用于任意截止期模型的最优保序分配.进一步的研究表明,当所有任务周期不小于其相对截止时间时,DM保序饱和分配是最少优先级分配.本算法复杂度低,可调度的判定总次数等于任务总数,远低于AGP和LNPA.     

单调速率调度算法的可调度性分析与仿真

单调速率调度算法是一种经典的周期任务调度算法，在采用单调速率调度算法调度周期任务前对算法的可调度性进行分析和仿真是十分必要的。该文介绍了单调速率调度算法的基本调度规则和可调度的充分必要条件，分别基于Windows平台的多线程机制和实时操作系统SACOS的RMS管理器对单调速率调度算法的可调度性进行仿真，并对仿真结：果进行了评价与分析。仿真结果表明，这两种方法可为单调速率调度算法的可调度性分析提供有益的指导。     

扩展单调速率算法及在FF调度时间表构建中的应用

FF现场总线采用集中令牌式通信介质访问控制方式.首先,本文针对单调速率算法没有考虑周期相同时任务的调度,提出了扩展单调速率算法,以便对周期信息进行优先级分配;其次,应用此算法,给出构建调度时间表的方法,并给出了简易的调度时间表有效性判据,以保证周期信息的实时性通信;最后,通过一个应用实例来描述扩展单调速率算法及在FF调度时间表构建中的应用.     

一种基于非抢占RM算法的可行性判决算法及应用

为中断服务例程建立了任务模型，在该模型的基础上给出了中断服务例程集使用非抢占RM调度的可行性的充分必要条件，并且基于该条件提出了一种新的非抢占RM算法的可行性判决算法。进一步地，给出了如何改进不可调度例程集的方法，并且将该方法应用到一个具体工程项目中，取得较好的效果。     

基于RM调度算法的μC/OS-II多任务周期的设计

嵌入式实时操作系统μC/OS II对于多任务调度采用让就绪表中优先级最高的任务总是处于运行状态，这种策略在周期性多任务的调度中存在着缺陷，可能使得任务的周期设计不当导致任务不能被调度。通过引入单调速率调度算法，在对多个任务设计任务周期时予以分析，确定每个任务都能被调度。     

基于命题投影时序逻辑的单调速率调度算法模型检测

提出了基于命题投影时序逻辑(propositional projection temporal logic,简称PPTL)的单调速率调度(rate monotonic scheduling,简称RMS)模型检测方法.该方法使用SPIN模型检测器的系统建模语言PROMELA为任务调度系统建模,使用PPTL描述系统期望的性质,通过SPIN验证系统模型是否满足性质,从而得知一个任务组在RMS下是否可调度.同时,RMS算法控制下的任务调度系统的其他性质也可以得到验证.