周期多帧任务的固定优先级调度算法的调度分析

实时操作系统的核心问题－－实时任务的调度是实时系统研究的重点之一。主要讨论了周期多帧任务的固定优先级调度算法的调度情况,证明了对于周期多帧任务DM算法不是最优的,同时也证明了对于累积单调周期多帧任务的DM算法是最优的。     

常带宽服务器混合任务低功耗调度算法

针对包含有截止期限限制的周期任务和有响应时间要求的非周期任务的实时系统混合任务集,提出常带宽服务器混合任务低功耗调度算法(constant bandwidth server mix task low power scheduling algorithm, CBSMTLPSA).该算法是2阶段调度算法,并且结合了动态电压调节(dynamic voltage scaling, DVS)技术和动态功耗管理(dynamic power management, DPM)技术.离线阶段确定任务的离线速度,充分利用处理器的资源;在线阶段通过回收周期任务提早完成的空闲时间以及服务器产生的空闲时间,利用DVS技术调节处理器的运行速度,并且当处理器处于空闲状态时,判断是否使用DPM技术以达到进一步降低能耗的目的.仿真实验表明所提出的CBSMTLPSA算法比CBS/DRA-W(constant bandwidth server for dynamic reclaim algorithm base workload)算法节约6.02%～34.14%的能耗;CBSMTLPSA算法的能耗与非周期任务的响应时间的乘积比CBS/DRA-W算法低5.86%～34.06%.     

可靠性感知周期任务能耗管理调度算法

针对EDF/DDM(earliest deadline first/dynamic deadline modify)算法不能利用空闲时间降低能耗的不足,提出了能够回收空闲时间的静态节能(static saving energy,SSE)算法。针对SSE算法没有考虑系统可靠性问题,在证明可靠性感知资源受限周期任务调度问题是NP难之后,提出两种启发式算法:最长执行时间优先算法(longest execution time first,LETF)算法和最短执行时间优先算法(shortest execution time first,SETF)算法。仿真实验表明所提出的LETF算法和SETF算法的能耗均低于EDF/DDM算法的能耗。此外,SETF算法和LETF算法的出错率比EDF/DDM算法低,是EDF/DDM算法的97%和76%,系统可靠性得到提高。     

多处理器固定优先级算法的可调度性分析

针对多处理器实时调度中的固定优先级(FP)调度算法,提出了一种改进的可调度性判定方法。引入Baruah的最早截止期优先(EDF)窗口分析框架,将高优先级任务带入作业的最大数量限定为m-1(m为处理器个数),进而对任务的干涉上界进行重新界定,并由此得到一个更加紧密的可调度性判定充分条件。仿真实验结果表明,该方法增加了通过判定任务集的数量,体现出更优的可调度判定性能。     

CAN总线固定优先级调度算法的应用

分析了CAN总线的最差消息传输模型，提出了一种固定优先级调度算法；针对系统控制实时性的要求及特点，对6自由度平台系统的消息进行调度。实际使用证明，该方法改善了6自由度平台的整体控制性能，提高了网络利用率，消息的截止期得到满足。     

实时多处理器系统的双优先级调度算法

针对同构多处理器系统提出一种基于双优先级的实时任务调度算法.对偶发任务进行接受测试,进一步提高了系统对偶发任务调度的成功率.模拟结果表明,当多核处理器系统利用率达到极限时,该算法依然能够在完成强实时周期任务的成功调度前提下,保证软实时周期任务和偶发任务具有较高的调度成功率.     

EDF统一调度硬实时周期任务和偶发任务的可调度性判定算法

现有的硬实时周期任务和非周期任务的混合调度方法都没有保证非周期任务的实时性,所以不适合调度具有强实时要求的偶发任务.通过分析和计算EDF算法调度偶发任务所占用的空闲时间和挪用时间,以及调度后对空闲时间和最大可挪用时间的影响,提出一种采用EDF算法统一调度硬实时周期任务和偶发任务时的可调度性充分判定算法.最后用仿真实验得出了该算法在不同系统负载下的判定准确率和偶发任务的平均响应时间.     

固定优先级抢占调度算法下非周期任务实时性能研究

嵌入式实时系统不仅要在功能上满足需求,而且要在性能上满足实时性需求.给定调度算法,实时性取决于各个任务的到达特征和执行时间.任务的到达特征由应用环境决定.为此,本文研究任务执行时间对实时性能的影响,为嵌入式系统设计提供参考.针对固定优先级抢占调度算法,应用排队论,提出一种非周期实时任务的理论模型.该理论模型包含两个优先级不同的非周期实时任务,给出了任务的执行时间长短对时限错过率、任务响应时间、任务队列长度等实时性能的影响.给出一个应用实例,仿真结果验证了理论模型的正确性.     

多特征参数的任务模糊调度算法

针对任务具有特征参数多和特征参数不确定性的特点,提出了一种基于模糊理论的任务调度算法。利用模糊集合来描述任务的不确定性特征;使用多层模糊综合评判和最大隶属度原理来综合考虑任务的多个特征参数并确定任务的优先级;采用动态构建多层评判模型的调度策略来减小任务优先级评判的失效率。仿真表明,该算法提高了任务调度的成功率,降低了任务截止期的错失率和任务优先级评判的失效率。该方法可应用于优先等级有限的实时系统任务动态调度中。     

一种有限优先级的静态优先级分配算法

静态优先级调度在实时系统中得到了广泛应用.然而,静态优先级调度受到系统支持的优先级个数的限制.当任务的个数大于优先级个数时,需要将多个任务映射到同一个优先级.针对优先级个数有限的情况,给出了在截止期限大于周期时任务可调度的充分必要条件,并提出了基于有限优先级的静态优先级分配算法(AGP).AGP算法对于基本任务集合是最优的静态优先级分配算法.其最优性表现在,所需的优先级个数最小,并且若采用AGP算法不可调度某个任务集,则采用其他静态优先级分配算法也不可调度该任务集.模拟结果表明,AGP算法的可调度性要远远大于常量法.AGP算法对于解决在嵌入式实时系统中任务的优先级分配问题具有重要意义.     

异构集群中基于优先级的任务容错调度算法

提出一种基于任务优先级的容错调度算法,任务的优先级并不是由用户指定,而是由任务的开始时间、执行时间和截止期限决定的。该算法能够容忍异构集群系统中一个节点故障,采用主动/被动副版本相结合的执行方式和重叠技术的备份方式,提高系统资源利用率。通过实验证明了该算法在容错调度中的可靠性和高效性。     

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

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

实时任务优先级动态分配策略

现有大多数方法都是根据任务的截止期、空闲时间或者价值(密度)来确定任务的优先级,很少综合分析以上各个因素对任务优先级的影响.论文研究任务价值密度和紧迫性的变化特征,提出优先级的动态分派策略DPA,该策略可通过参数p与q来调节任务价值密度与紧迫性对任务优先级影响的程度,从而满足不同应用需求.最后,仿真实验结果显示,应用DPA策略的基于优先级的调度可以提高系统累积价值收益,降低任务截止期错失率.     

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

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

一种任务优先级的综合设计方法

提出了一种基于优先级表设计的调度算法.将任务的相对截止期和空闲时间这两个特征参数结合起来,综合设计任务的优先级表,使得截止期越早或空闲时间越短,任务的优先级越高,而且任务的优先级由相对截止期和空闲时间惟一确定.对于任意一个任务,可通过对设计的优先级表进行二元多点插值获得相应任务的惟一优先级.与传统的EDF和LSF算法进行仿真比较,仿真结果表明,通过优先级表设计方法来确定任务的优先级,提高了任务调度的成功率,降低了任务截止期的错失率.该方法可应用于实时系统中实时任务的动态调度中.     

一种固定优先级实时调度算法的可行性测定

实时调度算法是实时系统的关键技术,验证实时调度算法的可行性是保证实时系统性能的必要手段.不同实时调度算法可行性测定方法不同.在简单实时模型上,针对固定优先级实时调度算法给出通过任务最坏响应时间来测定调度算法可行性的方法,分析了影响任务最坏响应时间的各种因素,修正了响应时间方程,将该方法运用在复杂实时模型中.     

一种固定优先级实时调度算法的可行性测定

实时调度算法是实时系统的关键技术,验证实时调度算法的可行性是保证实时系统性能的必要手段。不同实时调度算法可行性测定方法不同。在简单实时模型上,针对固定优先级实时调度算法给出通过任务最坏响应时间来测定调度算法可行性的方法,分析了影响任务最坏响应时间的各种因素,修正了响应时间方程,将该方法运用在复杂实时模型中。     

一种计算混合关键任务响应时间的方法

混合关键系统中不同关键等级的任务在同一个平台运行,任务的可调度性分析更加复杂.基于目前最有效的固定优先级混合关键的调度算法AMC(adaptive mixed criticality),提出了一种任务响应时间分析算法AMC-PM(AMC partition max).该算法将任务最长执行时间(worst case execution time,简称WCET)分成低关键等级态执行时间与高关键等级态执行时间,将这两部分对应的最长响应时间加起来得到总的响应时间上界.通过仿真实验,与已有的AMC响应式分析算法进行比较,结果表明,在任务高关键下最长执行时间较小时,与AMC-rtb相比,AMC-PM能够显著地提高系统的可调度性.同时与AMC-max相比,AMC-PM能够显著降低算法的运行时间.     

实时调度中基于多特征参数的任务优先级设计方法

本文在实时任务调度中基于任务的价值、剩余执行时间、空闲时间以及到达时间等多特征参数设计任务的优先级,并使任务的优先级随着任务紧迫性和完成程度变化而动态调整,并基于新的优先级设计策略提出一种实时动态抢占式调度算法VRSAF算法。仿真实验表明,在负载较轻时,VRSAF算法能获得近似EDF算法的调度性能;在过载情况下,其调度性能优于HVF算法;总体调度性能高,并能在系统过载的情况下实现平缓的降级。     

实时控制系统中固定优先级调度的延迟与抖动控制

在基于固定优先级调度实时控制系统中,任务的延迟与抖动是影响系统稳定性的重要因素,提出一种基于可抢占时间阈值的延迟与抖动控制策略,给出一种保证系统可调度的最优闽值分配算法,并通过对任务延迟和抖动的分析量化出阀值分配后的争最大可能IO延迟及抖动.最后通过仿真实验验证了该策略的有效性.