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

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

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

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

最早截止期优先的网络控制系统动态调度研究

网络控制是涉及计算机技术、自动控制技术、通信技术和最优化理论等的综合学科,网络调度对网络控制系统性能的影响是近年来国际学术界研究的热点。介绍了网络控制系统的基本组成和可调度性分析方法,提出一种由实时任务调度理论改进的网络动态调度理论——最早截止期优先(EDF)动态调度算法,并在控制器局域网络下采用Truetime与Simulink仿真工具共同构建了多回路的网络控制系统。仿真实验结果表明:最早截止期优先动态调度算法可以在不确定的网络环境下使各回路控制器性能达到最优。

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

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

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

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

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

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

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

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

基于EDF的汽车CAN网络动态调度机制设计

CAN网络消息调度的方法直接关系到整车通信的实时性。在CAN网络特点基础上,提出一种基于EDF的分布式CAN网络动态调度方法。将CAN帧标识符分成静态段和动态段两部分,给出静态段ID设计原则和内容;针对动态段,提出分布式环境下节点内部消息的EDF调度机制,并通过建立消息阻塞模型,分析其可调度性;在此基础上,提出基于"幂函数"的动态段编码方法,并证明了其误差。仿真实验结果表明,该机制实现了基于EDF的CAN网络消息动态调度,有效降低了消息传输的最坏响应时间,提高了网络带宽利用率。

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

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

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

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

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

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

一种改进的最大紧急度优先调度算法及其实现

任务调度策略是实时系统内核的关键组成部分,也是保证系统实时性的一个重要研究领域。最大紧急度优先(Maxi-mum Urgency First)调度综合了静态和动态优先级调度的优点,但是采用这种调度机制不能保证关键任务满足时限。本文结合最早截止期优先(Earliest Deadline First)调度算法,提出一种改进的最大紧急度优先调度算法,并在μC_OS-II下实现了这种调度策略。实验结果表明,采用改进的最大紧急度优先调度算法可正确调度,同时保证了关键任务满足截止期,有效的完善了μC_OS-II实时调度性能。

不确定环境下的嵌入式实时系统EDF调度算法研究与分析

大部分嵌入式系统的实时调度算法,都是按任务的最坏执行时间进行调度,会浪费各种资源.针对网络多媒体系统的实时应用需求和当前调度算法的实时性能的不足,本文分析了嵌入式实时系统中有代表性的动态EDF调度算法,建立了一个周期性的任务集模型,依据该模型,提出来了一个改进的EDF调度算法,最后用实验验证了改进的EDF调度算法的有效性.

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

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

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

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

多核处理器限制性可抢占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(Earliest Deadline First)算法来实现系统的自适应调度。最后对比常规多功能雷达的自适应调度进行了仿真比较,且对仿真结果进行了定量分析,结果表明采用多任务并行EDF(MTPEDF)算法的基于孔径分割的一体化雷达系统具有一定的优越性。

无线传感器网络的信息处理研究

无线传感器网络是以数据为中心的信息处理系统。本文根据目标跟踪对信息处理的需求,提出了协同信号与信息处理CSIP的概念,设计了基于MICA2节点和PDA的CSIP策略的实验,并采用基于(m,k)-firm的丢包策略。实验显示基于(m,k)-firm的策略比EDF更能减少信息的丢失率,并能够降低信号的失真。

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

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