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

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

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

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

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

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

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

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

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

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

一种基于优先级的云工作流动态调度方法

云计算遵循按需资源供应和即用即付定价模式,使得云提供商能够处理大规模的工作流调度.目前已有大量工作对工作流调度问题进行研究,如何以较低的执行成本来满足截止时间约束具有挑战性.本文考虑了云资源的可变性和工作流任务之间的依赖性,提出了一种基于优先级的动态调度算法Pbads,旨在满足时间约束的前提下最小化执行成本.首先,根据任务的依赖关系进行任务合并,并为工作流任务分配子截止期限.其次,基于时间约束和任务依赖性,动态调整任务的优先级和分配策略.此外,针对每个服务动态调整其任务队列的执行顺序,以此降低服务执行成本.最后,将Pbads算法与传统调度算法进行研究对比,实验结果表明Pbads算法在执行成本和满足时间约束方面有更好的表现.

基于优先级表的实时调度算法及其实现

讨论了综合考虑任务的截止期和价值两个特征参数的优先级表设计方法,提出了EDV(earliestdeadlinevalue)与VED(valueearliestdeadline)两种不同的基于优先级表的实时任务调度算法,并且利用多重链表给出了这两种算法的实现,包括任务接收策略与任务完成/夭折策略的算法实现.这种优先级表设计方法及其基于多重链表的实现方法也适用于对任务的其他两种甚至3种不同特征参数之间的综合.基于累积实现价值率、加权截止期保证率与差分截止期保证率3个方面,分析了VED算法与EDV算法的性能,实验结果表明,在所有负载条件下VED算法与EDV算法相对于EDF(earliestdeadlinefirst)算法与HVF(highestvaluefirst)算法都有很大的性能改进.

一种混合优先级的防危调度算法

为增强实时系统任务过载时的防危性,提出一种混合优先级的防危调度算法,其优先级由相对截止期优先级和相对松弛度优先级组成,通过相对松弛度预测任务的可完成性,并采用完全抢占方式防止处理器资源的竞争抖动。仿真结果表明,该算法可充分利用处理器资源,能在发生瞬时过载时有效降低任务的截止期错失率。

价值密度—截止期—回填的网格作业调度算法

在商业网格和云计算环境中,作业有到达时间、计算量、预算、截止期等属性,区分作业的重要性和紧迫性是调度系统的关键问题之一。现有的作业优先级只考虑作业的单个或部分属性。综合考虑以上提及的四个属性,定义了基于价值密度和相对截止期的作业优先级,提出了基于价值密度和相对截止期的网格作业调度算法,并结合回填算法(EASY backfilling)来提高资源的利用率。仿真结果显示,基于价值密度和相对截止期的作业优先级很好地体现了作业的重要性和紧迫性;而回填算法在提高资源利用率上对某些优先级策略效果显著,有些则效果不明显。

容错最早时限优先调度

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

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

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

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

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

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

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

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

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

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

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

基于组合优先级的自适应实时调度算法研究

在嵌入式实时操作系统中,由单个特征参数作为实时任务优先级的调度依据,并不能较好地描述系统中任务的关键性和紧迫性。提出一种基于组合优先级的自适应实时调度算法(SREDF),综合任务的截止期和CPU运行期设计任务的优先级,使截止期越早且CPU运行期越短的任务拥有最高优先级。处理器能有效地调度相同截止期的实时任务,并提前分析和预测任务能否完成。实验表明,该算法降低了任务调度的截止期错失率(MDP),并提高了任务调度的速度和效率。

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

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

Linux下的实时调度算法

Linux实现了实时进程的概念,但并没有提供有效的任务调度支持;另一方面,RM(Rate Monotonic)和EDF(Earliest Deadline First)等传统的优先级调度算法在实时系统中已经得到广泛应用,但它们对于确定优先级所采用的标准比较简单和片面,容易导致紧急型任务的截止期限不能被满足或系统资源不能被充分利用.文中基于RM和EDF提出了一种新的实时调度算法SBRD(Scheduler Based on Rate and Deadline),它的优先级根据重要性和紧急性两个重要因素共同确定.实验表明:与RM和EDF相比,SBRD兼具二者的优点,在保证重要任务顺利执行的前提下,优先执行紧急型任务,以满足更多任务的截止期限,更充分地利用CPU资源;与原Linux的实时调度相比,SBRD能更有效地调度实时任务.

TTCAN调度算法及其在汽车控制系统中的应用

TTCAN协议是一种新的基于时间触发机制的CAN高层协议。针对周期性信号的特点,提出了基于 平均数目分析的静态调度算法;针对非周期信号的随机性,为了避免信号的死锁提出了基于信号截止期的优先级 提升动态调度算法。最后以汽车自动控制系统为背景进行了调度分析,与IEC/ISA相比既满足了信号的实时传 输,又提高了网络资源的利用率。

基于混沌遗传算法的网格工作流调度应用

动态网格环境中,多QoS(服务质量)约束下的工作流调度问题是决定其任务执行成功与否及效率高低的关键。现有的网格工作流调度算法难以满足实际应用中的不同需求,同时算法欠优化,难以提供多种策略,由此提出了一种基于期限与预算两个QoS约束的改进型混沌遗传算法。首先,为避免算法出现收敛停滞将混沌机制引入遗传算法并对变异概率进行自适应处理。其次,提出时间和预算的线性结合概念,将目标函数转换为适应值函数。最终基于工作流调度中的平衡结构和非平衡结构测试了算法的有效性。