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

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

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

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

模糊数据流实时任务调度算法

针对数据流系统中实时查询任务的特点,提出了基于模糊综合评判的动态优先级调度算法。用语言模糊集描述任务的不确定性因素和不同的优先等级,利用最大隶属度原理确定任务的优先等级。算法充分考虑了任务的持续周期性、任务之间存在依赖关系与共享滑动窗口的特点对任务优先级的影响。从累积实现价值率、差分截止期保证率和CPU切换频率3个方面测试了算法的性能,实验表明所提出算法相对于HVF算法、LSF算法、模糊动态抢占调度算法都有很大的改进。     

基于D-S理论的区间值模糊多QoS测量与网格任务调度算法

非凡的服务质量是网格的基本特征,基于QoS的网格任务调度问题已成为国内外研究的热点.由于网格环境的复杂性和用户主观判断的模糊性,传统基于QoS的网格调度算法不能处理具有多个模糊QoS需求的调度问题.用区间值模糊来描述用户的主观QoS需求信息,提出基于D-S理论的区间值模糊多QoS测量方法,对区间值模糊数表达的用户多QoS需求进行融合与处理,再将这些区间值模糊数QoS融合值作为任务的优先级加入到任务调度算法中,提出一种基于D-S理论的网格任务多匹配调度算法.研究结果和仿真实验表明,该算法不仅可以处理区间值模糊不确定性信息,在满足用户多QoS需求的情况下还可大大减小任务调度的时间跨度.     

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

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

基于RTOS中多特征参数的动态调度算法

分析了常见的任务调度方法的特点,提出了一种基于多特征参数的动态调度策略VDDSA。综合考虑任务的价值和截止期,建立了该算法的模型,并给出了优先级的设计方法。通过任务的弹性系数和系统的权重因子的实时调整,使该算法具有一定的自适应功能。在μC/OS-Ⅱ上实现和测试了该算法,实验结果表明在所有负载条件下,VDDSA都具有较好的调度性能。     

模糊动态抢占调度算法

针对不确定任务特征，提出应用模糊理论进行动态抢占调度，用语言模糊集来描述任务的不确定特征和不同的优先级等级，利用最大隶属度原理确定任务的优先级等级，采用优先调度高优先级等级任务的调度策略提高重要任务的调度成功率，实现具有不确定任务特征的抢占调度，与传统的EDF和LSF算法相比较，仿真表明，所提算法能够提高重要任务的调度成功率，并降低重要任务的截止期错失率；同时，任务间的平均切换次数大大小于LSF的平均切换次数，而与EDF保持相当，该方法可应用于计算机控制系统的控制任务调度，并借鉴于其它具有不确定任务特征或具有有限优先级等级的实时调度问题研究中。     

基于模糊理论的任务分配与调度算法

基于模糊可靠性分配中的综合评判方法,提出一种用于数据并行交换的任务分配与调度算法。综合考虑影响任务优先级的各个因素及各影响因素自身的模糊特性,从而确定任务优先级,并解决任务分配过程中优先级的模糊决策问题。实验结果表明,该算法能提高任务的执行成功率,缩短任务的平均等待时间。     

物联网环境下具有顺序约束关系的静态任务表调度算法

针对物联网异构调度环境下并行计算的静态任务调度问题,提出了一种基于最早完成时间策略改变调度顺序的表调度算法HDPTS。该算法针对现有表调度算法在调度前不能准确地确定调度顺序的问题,在IHEFT算法的基础上添加了一个动态优先级调度策略,当节点的前驱任务都已经完成调度任务时,就改变该节点的调度优先级。任务优先级的计算在所有前驱任务到达这个任务的最晚完成时间与所有资源上最大可以使用时间之间取最大值的基础上,同时考虑到分配到各个资源上的任务对后继任务的影响和资源上的负载情况,以及上行权重的计算值和对出口任务的影响,使得优先级计算更加合理,能够根据任务分配动态合理改变任务调度顺序。通过随机生成一个算例进行测试,结果表明HDPTS比IHEFT、HEFT在调度长度方面减少14.29%;对大量随机产生的特定结构的有向无环图(DAG)进行测试,测试结果显示HDPTS算法比IHEFT、HEFT和LDCP算法更有效。     

一种全局较优的静态任务调度算法

针对现有任务调度算法优先级选取过于单一所产生局部较优调度结果的问题,从全局较优出发,提出一种先分层后分支决定优先级的静态任务调度算法—HGCOTS算法。该算法考虑了任务间较大的通信开销和冗余任务对异构CMP任务调度效率的影响,通过综合区间插入和任务复制技术最大限度地降低了任务间的通信开销,对冗余任务进行删除,明显提高了任务调度效率。使用随机生成图进行模拟实验,与其他算法相比,新算法具有更小的调度长度。     

模糊反馈控制实时调度算法

为了解决模糊不确定任务集在不可预测环境下的动态抢占调度问题,应用模糊规则和模糊调度理论,提出一个基于模糊反馈控制的调度算法,并建立相应的调度架构.该架构由基本调度器和模糊反馈控制两部分组成.用模糊调度算法作为基本调度器的调度算法,将任务集按不同优先级等级进行划分,优先级等级高的任务优先调度,从而使得更多的重要任务得到调度;模糊控制器与任务流调节策略一起构成模糊反馈控制部分.仿真结果表明,模糊反     

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

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

一种实时异构系统的集成动态调度算法

提出了一种实时异构系统的集成动态调度算法.该算法通过一个新的任务分配策略以及软实时任务的服务质量QoS(quality of service)降级策略,不仅以统一方式完成了对实时异构系统中硬、软实时任务的集成动态调度,而且提高了算法的调度成功率.同时,还进行了大量的模拟研究.这些模拟以传统的近视算法为基准,将其应用在实时异构系统集成动态调度时的调度成功率与新算法进行比较,模拟结果表明,在多种任务参数取值下,新算法的调度成功率均高于传统的近视算法.     

实时控制任务的模糊反馈调度系统研究

分析了实时控制任务的控制性能在不同控制阶段与处理器利用率需求间的关系,提出一种实时控制任务的模糊反馈调度系统.模糊控制器通过监测实时控制任务的误差及其变化率,查询模糊决策表,动态决定任务的优先级,反馈调度器根据优先级分配任务的利用率.仿真结果表明，在计算资源有限时，该方法能有效改善实时控制任务的控制性能.     

A Feasibility Decision Algorithm for Rate Monotonic and Deadline Monotonic Scheduling

Rate monotonic and deadline monotonic scheduling are commonly used for periodic real-time task systems. This paper discusses a feasibility decision for a given real-time task system when the system is scheduled by rate monotonic and deadline monotonic scheduling. The time complexity of existing feasibility decision algorithms depends on both the number of tasks and maximum periods or deadlines when the periods and deadlines are integers. This paper presents a new necessary and sufficient condition for a given task system to be feasible and proposes a new feasibility decision algorithm based on that condition. The time complexity of this algorithm depends solely on the number of tasks. This condition can also be applied as a sufficient condition for a task system using priority inheritance protocols to be feasible with rate monotonic and deadline monotonic scheduling.