最早截止期优先算法在CAN FD网络中的改进

针对应用于CAN FD网络中的调度算法,平均分区编码方式的最早截止期算法对报文进行非抢占调度时,其对大范围的截止期编码能力有限,报文易出现较大概率优先级反转以及总线负载较高等问题。通过分析造成报文传递延迟的各种原因并结合之前相关分区调度算法的不足,文中提出了基于指数–幂函数分区的最早截止期优先算法对报文进行调度的改进方式,即在对报文的截止期进行指数分区的基础上,进一步采用幂函数分区细分。文中对该算法的可调度性进行了分析,并使用CANoe进行了仿真验证。实验表明,与现有的平均分区调度算法相比,改进后的算法扩大了截止期的表示范围,降低了总线负载,优化了优先级反转问题,达到了更好的调度效果。

最早截止期优先调度算法的改进

在基于IEEE802.16d协议的服务流调度过程中,为了保证优先级较高的任务优先得到服务,并尽量将调度过程对系统资源的消耗控制在可承受的范围内,在分析已有的非抢占式及抢占式两种方案的最早截止期优先(EDF)算法优缺点的基础上,重点考虑时间特性、重要性特性、顺序参考三方面作为调节参数,同时兼顾传输距离,对已有的EDF算法进行改进。提出了基于重要性因素抢占的半抢占式EDF算法。通过仿真实验,把改进后的EDF算法应用到IEEE802.16d协议的实时轮询业务(RTPS)服务流调度中。结果表明,改进后的EDF算法较好地平衡了抢占及非抢占式EDF算法的优缺点,具备较前两者更小且更稳定的延时。

基于最早截止期优先算法的过渡过程研究

在以最早截止期优先算法调度的实时系统中,如果出现新任务插入和/或现行任务加速要求,而系统所剩带宽又不足时,必须进行带宽转让,系统运行模式将被迫发生改变。针对该问题,研究新任务插入和/或现行任务加速的动态过程,分析带宽转让对系统可调度性的影响。应用处理器需求准则,证明截止期丢失只可能出现在某一时间点之前。通过该结论可以合理定义过渡过程的长度,从而展示一个清晰的三阶段模型。最后给出相关仿真实例。

用于多媒体的最早截止时间优先算法改进

对经典实时调度算法之一的最早截止时间优先算法进行研究,提出一种基于动态死线时间的改进方法,避免了瞬时过载导致的系统不可预测的行为.实验表明,本方法保证了连续多媒体应用的服务质量,达到较高的资源利用率,使该算法更加适合多媒体应用环境.

容错最早时限优先调度

最早时限优先调度 ( EDF)是最优的动态可抢占优先级实时调度算法 ,具有灵活、简单和高效的特点 ,但并没有考虑实时系统的容错要求。本文提出一种容错 EDF算法 ,实现在规定时间段内的单个错误容错。本文详细分析了该算法的容错机制 ,证明了该算法的正确性 。

云环境下基于EDF和LWF的回填算法

由于云资源有限,如何保证时限和提高资源利用率一直是提高成本效益的关键问题.提出一种基于最早截止时限优先算法(EDF)和最大权重优先算法(LWF)的回填算法.该算法通过使用LWF算法支持等待队列中所有的任务按照时限评分排序,在回填任务时,考虑任务的权重,以提高资源利用率;当检测到回填的任务错过了截止时限,则采用EDF算法,以满足时限保证.仿真结果表明,相比平衡螺旋法回填算法和EASS回填算法,提出的算法具有更短的服务延迟时限和更高的资源利用率.

混合动力汽车CAN网络优先级动态分配方法

在混合动力汽车网络结构和消息实时性分析的基础上,将最早截止期优先算法(EDF)引入到网络集成协议设计中,提出基于EDF调度的优先级分配策略,给出了实现该策略的非均匀分区编码方法及可调度判定条件,指出了该判定条件下的分区因子无关性。仿真结果表明该方法能够满足截止期变化范围较大的CAN消息集传输要求,使网络具有较高的利用率。

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

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

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

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

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

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

软件容错模型中的部分抢占实时调度算法

为了减少软件容错模型中实时调度算法的抢占次数,提出了一种部分抢占调度算法(PPA),该算法不仅考虑了如何尽可能多地执行主部分,还考虑了如何减少抢占次数,采用了类似非抢占最早时限优先算法(EDFA)来调度主部分.对不同CPU利用率和软件错误概率的任务集合进行模拟实验,结果表明,PPA算法在可以获得与目前所知的同类算法近似调度性能的同时,还可以在一定情况下极大地减少任务调度间的抢占次数,从而减少了系统中因抢占次数过多带来的额外运行时调度开销等负面因素.

实时调度算法分类研究

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

基于改进EDF的多核处理器混合任务调度算法

为解决多核处理器系统中的实时任务调度问题，尤其是实时任务和非实时任务的混合调度问题，在对最早截止时间优先（EDF）算法进行改进的基础上，提出多核处理器混合任务调度算法——EDF．segment算法。EDF—segment算法可以整理调度混合任务时出现的碎片，并通过对碎片的迁移、合并提高处理器的利用率，从而提高系统处理混合任务的性能。通过EDF．segment算法不但可以解决混合任务的调度问题，还可以避免使用EDF算法时造成的多核处理器利用率下降，在保证实时任务处理延迟的前提下提升多核处理器的利用率。经过理论推导和实验分析证明，EDF—segment算法可以有效地应用于多核处理器系统中。

一种考虑截止期的METCD业务组合调度方法

海洋设备检定、校准和检测(marine equipment testing,calibrate&detection,METCD)业务规模大、紧急情况多,如何对业务进行合理的调配是海洋计量检定行业亟待解决的问题。提出了一种考虑截止期的任务组合METCD业务调度方法。在建立业务调度问题数学模型的基础上,采用最早截止时间优先—蚁群算法(EDFPACO)对模型求解,在最早截止日期的约束条件下对任务组合处理的最优调度方案,达到降低任务总完成时间和减少执行空间浪费双重优化目标。为了验证方法的可行性,以国家海洋局东海标准技术中心的业务为实例,将EDF-PACO算法与传统的最早截止时间优先算法和蚁群算法进行比较,结果表明所提出的调度方法在满足截止期的约束条件下,能高效地对海洋设备的计量检定业务进行组合调度。

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

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

带宽约束下舰艇编队网络的跨平台任务调度算法

[目的]舰艇编队无线IP网络的带宽有限且具有时变性,故为满足编队作战应用对跨平台任务运行的时限要求,需研究网络带宽约束下的跨平台任务调度算法。[方法]提出舰艇编队无线IP网络任务调度模型,运用"任务发起方"和"任务响应方"的通信模式,实现"最早时限优先+先来先服务"两级任务调度。采用所提的最早时限优先(EDF)扩展算法,在传统的单平台单处理机实时调度算法基础上,将任务执行时间的计算由处理机占用时间转换为网络占用时间,以适用于舰艇编队需要,进而推导出任务可调度性的判定条件,并对此进行试验验证。[结果]试验结果表明,在所构建的测试网络环境下,可计算得到舰艇编队跨平台任务集合的可调度性。[结论]所提理论模型及算法具有较强的可实施性,对于指导舰艇编队无线IP网络的任务规划和任务调度具有重要价值。

OPC实时任务系统动态调度算法的研究与设计

本文基于已有的OPCServer实时任务模型,设计了处理混合任务集的动态调度算法(基于截止期优先)和实现方式。该算法实现了对混合任集可调度性的判断,可以完成有硬实时性要求的非周期性任务和周期性任务的调度,并给出了相应的调度结果。

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

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

嵌入式实时操作系统的容错调度算法研究

基于时间冗余的实时系统调度算法,要求一定的时间冗余。采用非精确计算技术,将实时任务分为强制执行部分和可选执行部分,将可选执行部分的处理部分作为强制执行部分的容错操作预留处理时间。非精确容错最早时限优先调度算法,通过降低为容错操作专门预留的空闲处理器时间,增加了可用于实时任务正常运行的处理器时间,提高系统的任务吞吐量和资源利用率。

基于CAN FD总线的动静态调度算法研究

受调度算法的影响,CAN FD报文在总线传输过程中会出现时延、阻塞等障碍,从而导致报文优先级分配不均,无法正常占用总线进行传输。为解决该问题,分析造成报文时延的原因,总结出CAN FD报文的最坏响应时间量化公式。建立调度模型,分别基于固定优先级算法和最早截止期优先算法对CAN FD报文进行调度分析,并采用CANoe进行仿真实验验证。实验结果表明,CAN FD报文在波特率为250kBaud和500kBaud的情况下进行调度时,最早截止期优先算法最优可100%实时传输报文,相较于固定优先级调度具有优先级分配更加灵活、报文实时性更强的优势。