具有纠错能力的截止期优先调度

基于实时任务错误分析,提出一种具有纠错能力的最早截止期调度算法FR EDF,并给出该算法的充要条件,证明了已有相关结果是该充要条件的自然推论.所提出的算法适合处理周期性实时任务,又能兼顾处理非周期性实时任务,同时还可以纠正两个错误发生的时间间隔大于某一常数的单个错误.

分布式实时事务一阶段实时提交

给出了分布式实时事务一致性实时提交协议的形式化定义和一致性实时提交协议的正确性准则;在此基础上,提出了适合于分布式实时事务的一致性实时提交协议———一阶段实时提交协议(1PRCP),1PRCP通过参与者与协调者的一次消息交换,在一个阶段完成分布式实时事务的提交活动.结合超时恢复协议,1PRCP能避免由于站点故障或网络通信链路故障而导致的阻塞.研究结果证明了1PRCP的正确性和优越性.

混合事务的ERtTDF调度算法及可调度性分析

在实时数据库及数据处理系统中,针对周期性实时事务,应用经典的EDF等调度算法对其可以得到可行的调度;而对于混合实时事务-事务的时间性质是混合的,经典EDF不太适用。文中扩展EDF为最早实时事务截止期优先-ERtTDF(EarliestReal-timeTransactionDeadlineFirst),它可以有效地调度混合事务。文中给出了其可调度条件和时间需求条件,并把时间需求条件扩展到时限小于周期以及引入资源共享控制等方面,最后给出了集成调度实时、非实时以及混合事务的系统框架。通过性能比较,可以得到ERtTDF算法处理上面事务模型时性能较经典EDF更优。

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

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

实时调度算法分类研究

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

基于RTLinux的实时调度算法改进及实现

RTLinux是一个具有实时内核的Linux操作系统.很适合在其上实现各种实时调度算法,文章分析了RTLinux的工作原理和已实现的调度算法,分析了其不足,提出了用EFDF对其进行改进.并介绍了在RTLiux上如何实现可达截止期最早的调度算法.通过在RTLinux系统中的实现,证实了该算法的有效性.

实时系统中传统调度方式的一种改进方法

介绍了在实时操作系统(RTOS)中两种典型的调度算法,速率单调调度(RMS)算法和最早死线优先(EDF)调度算法。指出了传统实时系统中调度机制的不足之处,给出一个通用调度框架模型(GSF)。该模型将调度器分成事务分派器和事务调度器两个部分,事务分派器根据任务的需求设置相应的属性,而事务调度器则根据任务的属性决定采用哪种调度算法。该模型使得调度更加灵活、有效。

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

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

多特征协调的实时调度算法

目前大多数实时调度算法都依据单一的特征参数确定任务优先级,本文提出一种基于多特征协调的实时调度算法,对特定高优先级任务优先处理,并且对其他任务的调度不产生任何影响。同时,在系统超载的时候,有效避免了EDF算法性能的急剧下降。实验结果表明,该算法有效地保证了特定任务的调度优先级,相对于EDF算法性能有明显改进。

基于希尔排序的动态优先级调度算法

实时调度策略中,EDF算法应用最为广泛,但其在系统过载的情况下,仅由任务截止期决定任务执行顺序,使得截止期错失率非常高,且系统收益小。近年来,出现了一些改进的EDF算法,综合考虑了时间和执行价值,但未加入能量因素,对于能量有限的系统,充分利用能量是极其重要的。针对这一问题,提出一种基于希尔排序的动态优先级调度算法,在系统过载时,综合考虑任务截止时间、执行价值、消耗能量三种因素确定任务优先级,通过希尔排序算法选出优先级高的任务加入优先调度子集,进行率先调度。实验结果表明,该算法不仅能降低任务截止期错失率,还能提高系统执行收益。

支持缓存划分的全局EDF实时系统调度策略

由于多核处理器争用共享缓存导致的不确定性为实时系统带来极大的挑战.为解决这个问题,现代处理器引入了缓存划分技术,通过隔离处理器核对缓存的访问从而提高了时间可预测性.但是,这种隔离技术可能导致实时任务因缓存分区的数量不足而被阻塞,而传统的实时调度算法与分析方法无法有效应对这种情况.因此,提出了支持缓存划分的可抢占全局最早截止期优先(EDF)实时调度算法gEDFca,并结合最新的缓存敏感调度理论针对这种调度算法进行了可调度性分析,提出了一种基于线性规划的可调度性判定条件.还提出了一种具有线性时间复杂度的优化算法,进一步提高了分析方法的性能.随机生成任务的仿真实验表明,提出的可调度性判定方法具有较高的效率.同时,优化算法提高了算法可调度性.

基于EDF的实时任务带宽转让研究综述

实时任务带宽转让问题在网络通信和机器人目标逼近等许多场合具有应用背景。当新任务插入或老任务加速时,可能需要某些现行任务转让带宽。该文从三个方面对这个问题进行综述。一是如何进行压缩任务的选择,以便尽快而安全地实现这种转让;二是如何求出最早的安全转让时刻;三是有关算法的收敛问题。这三个方面都是基于最早截止期优先算法来展开研究的。

基于贪心策略的EDF调度算法优化

最早截止期优先(EDF)调度算法在系统过载的情况下会产生"多米诺效应",导致无法满足多数任务的实时性要求。针对该问题,提出一种基于贪心策略的最优调度集选择方法。通过引入一个表示任务价值的因子与任务的截止时间共同决定任务的优先级,当系统过载时,在EDF算法的可调度范围内选取重要任务作为优先调度对象。理论性能分析和实验结果表明,该算法不仅能在过载时降低实时系统的任务截止期错失率,而且能保证关键任务的优先调度。

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

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

基于CANopen协议的电动执行机构CAN总线通信设计

针对电动执行机构的现场通信需求,设计了基于CANopen协议的电动执行机构CAN总线通信的应用层协议;分析了基于CANopen的电动执行机构的主要CAN通信对象,给出了CAN应用层的总体设计以及CANopen协议对象字典设计的方法;分析了电动执行机构组成的分布式CAN网络中低优先级消息可能存在的通信实时性问题,并采用最早截止期优先算法改善CAN总线通信的实时性,实验表明,该算法可以很好地解决低优先级消息的通信实时性问题。

多核处理器限制性可抢占G-EDF调度策略研究

多核处理器全局最早截止期优先(Global Earliest Deadline First,G-EDF)调度策略允许任务的抢占和任务在处理器之间迁移,频繁的抢占和核间迁移会导致较高的处理器开销,造成系统资源的浪费.然而目前针对多核处理器的可调度性分析方法都基于这样的假设:任务抢占和系统间迁移的开销计入最差响应时间或者忽略不计.但是实际研究表明该部分的开销在系统资源总开销中占重要部分,因此不可简单的忽略不计.而不可抢占调度,会给高优先级任务代入太多的阻塞从而导致其不可被调度.针对这类问题,实时领域的研究者们提出了限制性可抢占调度策略,且在全局固定优先级方面取得了很多的研究成果,然而在G-EDF方面的研究工作相对较少.该文研究了限制性可抢占全局最早截止期优先(Limited Preemption Global EDF,G-LP-EDF)调度策略,该策略结合了完全可抢占和完全不可抢占的优点.G-LP-EDF调度策略把目前G-EDF最佳的分析方法和限制性可抢占调度策略相结合,目的是减少G-EDF的额外系统开销,避免系统资源的浪费,而不降低G-EDF的调度性.最后通过仿真实验,G-LP-EDF分析方法在平均抢占次数上比G-EDF至少可减少40%,而两个分析方法之间的可调性没有明显差距,大约为1%.效率上两个方法随着最差执行时间的取值增大而增多,这是两个方法的本质造成的.然而G-LP-EDF整体比G-EDF的平均处理时间要慢,但差距都不足1s.

EDF实时调度算法中的关键问题求解

针对截止期最早优先(EDF)调度算法存在的问题,通过分析和证明EDF调度算法中最大可挪用时间的性质,结合EDF的最优调度过程,提出一种可延迟时间逼近(DTA)算法,以快速准确地计算EDF算法调度周期任务的最大可挪用时间,并且证明了该算法的时间复杂度只和周期任务数、处理器的占用率之和有关.仿真实验验证了DTA算法的时间性能.