共享资源约束下多核实时任务分配算法

为了提高多核实时系统任务分配效率,研究分组固定优先级调度策略下的任务分配算法.通过分析核间任务阻塞对任务最坏情况响应时间产生的影响,提出由于任务间共享资源冲突而引发了任务分配故障问题;指出负载非均衡算法,如First-fit算法、Best-fit算法容易引发任务分配故障.为了避免该问题,提出基于分组与负载均衡的任务分配算法.该算法将存在访问共享资源冲突的任务分配到同一核上,以避免核间任务阻塞;当这些任务无法分配到同一核上时,将这些任务依次分配到当前负载最轻的核上以避免任务分配故障.可调度性分析实验表明,采用该算法可以避免任务分配故障,减少分配任务所需的处理器核数(比Worst-fit算法少10%～40%).     

一种负载感知的异构MPSoC任务调度算法

处理器核的异构性、运行时负载和任务间依赖关系,是影响异构MPSoC任务调度算法性能的关键因素。该文提出了一种负载感知的异构MPSoC任务调度算法,在满足任务间依赖关系的前提下,根据计算开销和通信负载将待调度任务集划分为任务子集。在考虑处理器核负载状态的基础上,通过赋权二部图最大权匹配,将任务子集调度到适载的处理器核上运行,提高了待调度任务集总执行效率。仿真实验结果表明,该算法有效降低了任务集的调度长度,提高了处理器核的利用率。     

负载自适应的异构MPSoC任务调度算法研究

在异构MPSoC中,并行任务通过调度算法被分配到各个处理器核上运行,因而任务调度算法的优劣将直接影响异构MPSoC的应用性能。根据处理器核类型和任务间依赖关系,以减小任务间通信开销为目标,提出一种具备负载自适应能力的异构MPSoC任务调度算法。首先,将待调度任务集划分为多个并行任务子集;其次,在考虑处理器核负载的基础上,根据并行任务子集集合、处理器核集合及任务子集在各个核上的执行效率生成赋权二部图;最后,利用赋权二部图最大权匹配方法,将并行任务子集合理地调度到负载适应的处理器核上运行,以降低任务集的平均调度长度,并提高处理器核利用率,从而实现异构MPSoC应用性能的提升。仿真实验在不同的任务总数、任务最大前驱数、核类型、核数量的应用场景下,通过任务集平均调度长度、处理器核利用率两项指标对提出算法进行了定量分析。结果表明,提出算法能有效降低任务集平均调度长度,在实现负载自适应的同时提高异构MPSoC处理器核的利用率。     

基于利用率和负载均衡的多核实时调度算法研究

针对分区调度算法在实时多处理器系统中处理器利用率不高的现象,提出一种基于利用率和负载均衡的分区调度算法BUWBPA(Based on Utilization and Workload Balance Partition Algorithm)。该算法在满足任务实时性要求的基础上,以寻求高利用率和负载均衡为目标进行任务分配,将任务分配分成两个阶段:第一个阶段以高利用率为原则,选择任务集内利用率最高的任务先分配;第二个阶段以负载均衡为原则,根据处理器数选择利用率总和等于1或接近于1的任务进行分配,并且在此阶段对于未达到充分利用的处理器,选取可能调度的零星任务,对任务进行再次重新分配,以达到负载均衡和系统最大利用率。实验证明,该算法在实现最大利用率的前提下能很好地达到负载均衡。     

面向多核的时间帧加权公平调度算法

多核系统在移动终端、多媒体设备上的广泛应用对于多核系统的调度提出了新的要求,由于这些多核设备中大量的周期性与实时动态任务的执行,使得传统的Pfair和ERfair等经典算法产生了大量的任务迁移,同时对于动态任务调度并不能提供良好的支持。因此,在Pfair经典调度算法的基础上,结合EDF等局部调度算法,以时间帧的模式轮转多任务的周期执行,并采用处理器时间帧间的任务固定来降低任务的迁移率。仿真实验表明,在对任务调度公平性影响很小的情况下,大大降低了任务的迁移率并能更好的处理动态任务,具有更高的效率和更为广泛的使用范围。     

含启动开销总线网络实时可分性负载调度算法

针对异构总线网络,提出了一种含启动开销的实时可分性负载调度方法。建立了实时可分性负载调度的最优化模型,即在满足实时任务截止期限的约束条件下,使系统计算资源消耗最小化;根据可分性负载调度的最优性原理,分析了网络中处理器负载分配的最优次序以及参与计算的处理器数目;在此基础上提出一种实时可分性负载调度算法并给出了算法的实现流程,该算法能够利用网络中最少的处理器数目,保证实时任务在其截止期限之前计算完成。理论分析和仿真测试都验证了所提出算法的有效性。     

高可信赖实时操作系统的防危调度机制

为增强实时操作系统的防危性,在分析现有调度机制的基础上,探讨了最大关键度优先的调度算法,该算法是一种混合型的优先级实时调度算法,由静态优先级、动态子优先级和静态子优先级3部分组成,综合了固定优先级调度算法和动态优先级调度算法的优点,既可充分利用处理器资源,又能在发生瞬时过载时保证关键任务不受非关键任务的影响,从而增强了实时操作系统的防危性。     

新的混合关键任务调度算法的研究

分析了混合关键系统中当前任务调度方法存在的问题, 提出一种正反向时间分割和关键因子优先的调度算法, 该方法将所有混合关键任务按照不同级别进行时间正反向分割得出空闲时间窗口, 并根据关键因子的大小决定优先级别. 为了减少在关键级别转化过程中优先级低的任务丢失死限的工作数量, 将空闲窗口分配给由于关键级别转化而使得优先级落后的任务. 仿真实验表明, 该方法在降低任务丢失死限率和完成任务的数量方面比按照关键级别进行优先级指派算法(CAPA)和OCBP方法较优.     

基于多核处理器的低能耗任务调度优化算法

针对多核处理器的高性能所带来的高能耗问题,对TL-DVFS算法中任务迁移开销问题进行了分析,提出了一种基于TL面的节能调度算法ITL-DVFS.该算法在不增加算法时间复杂度的前提下,通过对堆进行操作,有效地减少每个TL面初始时刻任务的迁移开销.结合全局动态电压频率调节技术,在TL面的初始时刻和偶发任务释放时刻动态调节多核处理器的电压频率.结果表明,ITL-DVFS可以有效地减少任务的迁移开销,在负载达到某一值后,可有效降低处理器功耗.     

基于负载均衡度的云计算任务调度算法

针对当前云计算环境中用户群与数据量庞大的特点,如何设计高效的负载均衡调度算法是云计算领域一直探索的重要课题.提出一种基于负载均衡度的云计算任务调度算法(TS-CCLB),该算法首先依据空间案投影分析计算了集群的负载均衡度,以此给出调度决策变量,并依据任务的执行代价完成时限赋予任务不同的优先级别.任务调度时将任务按优先级调度到最大决策变量值所对应的虚拟机上.实验结果表明,该算法可有效提高云计算集群的负载均衡性,缩短总任务的完成时间,尤其当任务数与节点规模较大时,优势更为明显.     

基于粒子群优化的多核处理器系统节能调度算法

针对嵌入式多核系统中的实时性和能耗问题,提出了基于粒子群优化的多核处理器系统节能调度算法.通过对多核处理器系统任务调度和能量消耗的分析,建立了新的编码策略和相应的目标函数,将任务划分、任务调度及电压选择3个过程整合到粒子群算法的一个单迭代寻优循环中,并兼顾系统的实时性,将问题转化为有约束的粒子群优化问题,利用可行性规则的约束处理技术,形成基于约束粒子群优化的整体节能调度算法.实验结果表明:本文算法能以较快的速度收敛于使系统能耗更少的调度解.     

改进CS算法结合决策树的云工作流调度

对云计算环境下工作流任务调度的现有方案进行分析,针对存在运行时间长、资源利用率低等不足,提出一种结合改进型布谷鸟搜索算法和决策树的工作流任务调度方案。首先,根据工作流任务属性分配截止期限;其次,利用改进型布谷鸟搜索算法将工作流分割成多个子工作流,最小化数据依赖性,再利用决策树选择出满足任务QoS约束的资源;最后,根据任务的计算时间、排队时间和通信延迟的总和来判断是否满足截止期限约束,以此配置相应的资源。实验结果表明,该方案具有较短的总运行时间和较高的任务完成率。     

基于非精确计算模型的OSL算法

目的研究多处理机系统任务分配的启发式策略和容错调度算法,设计一种高效实时调度算法．方法只对任务强制部分进行复制,将任务分为强制执行部分主版本PTMi、强制执行部分副版本BkMi．和选择执行部分Oi,采用可选择部分后调度．结果提出了可选择部分后调度（Optional Scheduling Later,OSL）算法,通过实例与ICDM算法进行了仿真比较,说明了该算法的有效性．结论该算法使任务的完成时间提前,提高了处理机的利用率,便于广泛应用．     

混合关键任务可靠调度方法与调度性分析

为了解决云计算环境下混合关键性任务的可靠调度问题,提出了一种基于主副版本两阶段的混合关键任务可靠调度方法．算法首先对需要调度的混合关键性任务进行优先级划分,按照调度截止期最短的原则将主版本任务调度到目标虚拟机上,对副版本任务按照复制成本最低的原则使用重叠方法进行调度;再对调度到不同虚拟机上的主副版本任务进行可调度分析,对于不能满足分析的任务启动更高关键性等级进行处理．实验结果表明了混合关键任务可靠调度方法具有较高的可靠性和负载平衡能力．     

DAG任务模型的粒子群优化调度算法

在并行多处理器系统中,通常用有向无环图(DAG)表示任务之间的依赖关系.为了提高该任务模型调度算法的性能,基于粒子群优化算法,提出一种新的调度算法.算法将任务高度和粒子位置作为任务优先级,使用表调度策略生成有效的调度方案,在满足任务间依赖关系的条件下,使所有任务的完成时间最小.仿真实验结果表明,与遗传算法相比,所提出的算法提高了解的质量和收敛速度,特别适合于规模较大的多处理器任务调度.     

多处理器实时系统容错ICDM调度算法

目的提出一种针对多处理器实时系统中具有时间、资源和容错需求任务的调度算法来满足硬实时系统实时性及可靠性要求．使硬实时系统在发生故障的情况下，任务也能在其截止期内完成，不致产生灾难性后果．方法将非精确计算模型引入到Distance Myopic算法中，通过非精确计算模型与Distance Myopic算法的有效结合，提出ICDM算法．结果任务分为主副两个版本，每个任务都由两部分组成：强制执行部分和选择执行部分；当任务强制执行部分不能达到截止期时．通过调用MOPT算法减小前序任务选择部分的执行时间，使其满足截止期要求．ICDM算法使任务在保证结果可接受的情况下，在其截止期内完成，提高了任务的可调度性．结论通过引入非精确计算模型，使算法的可调度性增强了，也提高了硬实时系统的实时性及可靠性．     

多核处理机环境下的定积分的并行计算

利用Java语言,研究了多核处理机环境下的定积分的并行计算,数值试验结果表明：在多核处理机环境下的计算效率明显高于单核处理机环境。