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

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

改进的最小空闲时间优先调度算法

最小空闲时间优先(least slack first,简称LSF)算法结合任务执行的缓急程度来给任务分配优先级.任务所剩的空闲时间越少,就越需要尽快执行.然而,LSF算法造成任务之间的频繁切换或严重的颠簸现象,增大了系统开销,并限制了其应用.在调度策略中设置抢占阈值可以减少任务之间的切换,但现有的抢占阈值设置方法因受到固定优先级的限制而不适用于LSF算法.为了减轻LSF算法的颠簸现象,基于抢占阈值的思想,提出适用于LSF算法的抢占阈值分配方法,动态地给每个任务配置抢占阈值.任务的抢占阈值是随着任务执行的缓急程度不同而动态地变化的,而且不受任务个数的限制.仿真结果表明,通过对LSF算法的改进,任务之间的切换大大减少,同时降低了任务截止期错失率.该改进型算法对设计和实现实时操作系统具有一定的参考价值.     

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

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

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

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

基于动态抢占阈值的LSF调度算法

在最小空闲时间优先(LSF)调度算法中,当任务集中有多个任务的优先级相同或相近时,过多的上下文切换会产生“颠簸”现象,从而大幅增加系统开销。为此,结合LSF算法的特点,通过设计合理的动态抢占阈值,提出一种改进的调度算法DPTLSF。仿真结果表明,改进的算法能够大幅减少“颠簸”现象的发生,降低任务集的截止期错失率。     

实时嵌入式异构环境下多优先级混合任务调度动态策略

针对现有异构环境下的调度策略,引入迫切密度和剩余价值密度,分析迫切密度和剩余价值密度调节任务执行紧急程度的影响、对优先级制定,通过构建单有向无环图（ DAG）系统模型实现了混合任务的动态调度。仿真实验结果表明：该调度策略在系统负载较高的情况下,仍有较优的任务执行效能和避免颠簸现象。     

基于双层优先级的中继卫星系统任务调度算法

中继卫星系统在天基信息网中起着桥梁的作用。为充分利用卫星资源以提供快速可靠的数据中继服务,需要对高价值、高紧迫性的任务开展调度方法研究。首先,在分析中继卫星系统任务与资源的基础上,建立了多任务、多资源的调度模型。而后,提出了任务调度优先级和时间窗口选择优先级模型,并在此基础上提出了一种基于双层优先级的中继卫星系统调度算法。最后,根据算法在仿真算例中的应用可见：相比对照算法,基于双层优先级的调度算法更有利于满足高价值、高紧迫性任务的执行条件,从而提高了任务成功率和调度综合收益。     

一种解决卫星网络通信冲突的调度算法

在卫星网络中多颗卫星同时对一颗卫星进行通信申请会产生任务冲突问题。为此,提出一种基于动态优先级的调度算法。建立卫星通信任务模型,利用任务执行紧迫性表达任务截止期与空余时间这2个时间约束,并根据卫星网络的特点,通过调整参数p控制紧迫性对任务优先级的影响程度。利用STK场景建立冲突模型进行仿真实验,结果证明该算法的任务完成率相比FCFS算法提高了3.9%。     

多处理器硬实时系统的抢占阈值调度研究

在实时系统中,抢占在提高系统灵活性的同时带来额外的系统开销,特别在多处理器平台上抢占导致的作业迁移会造成相当大的性能下降,减少不必要的抢占是硬实时系统研究的重要方向.抢占阈值调度是处于抢占调度和不可抢占调度之间的一种混合调度方法,在保持调度能力的基础上限制抢占.基于截止期分析建立了多处理器硬实时系统抢占阈值调度的可调度性判定条件,针对抢占阈值调度提出一种改进的优先级分配算法OPA-MLL,并建立了抢占阈值分配(preemption threshold assignment,PTA)算法.仿真结果表明,采用OPA-MLL算法和PTA算法分别给任务集分配优先级和抢占阈值时,可调度任务集比率明显提高,同时能最大程度限制抢占次数.     

基于动态抢占阈值的实时调度

具有抢占阈值的调度算法集非抢占调度和纯抢占调度的特点，既减少了由于过多的随意抢占造成的CPU资源浪费，又保证了一定的任务截止期错失率及CPU资源利用率。已有的工作基本集中于讨论任务集完全给定，任务数、任务的优先级及任务的抢占阈值在调度前已完全确定，而且要求不同的任务具有不同的优先级，提出的具有抢占阈值的调度算法，完全放松了对这些条件的限制，即任务的个数不确定，任务的优先级及其抢占阈值在调度过程中可以动态地变化。最后以常用的LSF调度策略为例，结合动态的抢占阈值进行仿真，仿真结果表明，对于不确定的任务集、任务优先级和抢占阈值，利用具有抢占阈值的动态调度算法，降低了任务截止期错失率、提高了CPU的有效使用率。