EDF调度算法可调度性分析方法的改进研究

任务集的可调度性分析是实时系统研究和应用的关键问题。针对抢占式与不可抢占式EDF(earliest deadline first)调度算法, 分别给出了实时任务集新的可调度性测试条件, 针对任务集为可调度时可以实现快速判定。通过与已有的EDF算法的可调度性判定充要条件相结合, 提出了改进的抢占式与不可抢占式EDF算法的可调度性分析方法。仿真实验表明, 相对现有EDF算法的可调度性分析方法, 所提出的方法能有效提高算法性能。     

一种不影响任务集合可调度性的优先级映射算法

采用静态优先级调度的实时系统中,当任务个数多于优先级个数时,只能给多个任务分配相同的优先级.现有分配算法增大了高优先级任务的最坏情况响应时间,可能造成任务集合不可调度.利用抢占阈值的调度算法,能在提高任务集合可调度性的同时,使用较少的线程.但所用优先级个数没有减少.提出了一种优先级映射算法——阈值段间映射法(threshold segment mapping, TSM),以及与之配合的事件驱动线程框架.证明了TSM是严格排序的.仿真结果表明,在保证任务集合可调度的前提下,TSM使用了比现有映射算法更少的优先级.     

强实时系统静态优先级调度的可调度性分析

文章在系统阐述和借鉴经典的强实时系统静态优先级调度理论的基础上,通过引入忙周期的概念,分析了任务时限超过任务周期的实时系统任务集的可调度特性,拓宽了该理论的应用范围,更有利于实时系统的设计者对任务的运行时间行为进行事前分析与预测。     

抢占阈值调度算法的分析与研究

本文详细论述了应用于静态优先级实时系统的抢占阈值调度算法。描述了算法实现和任务集合可调度性判定公式的推导,分析了算法的性能特点,阐述了抢占阈值调度是静态优先级嵌入式实时系统开发中调度算法的合适选择。     

不可抢占式EDF调度算法的可调度性分析

现有的不可抢占式EDF调度算法的可调度性分析判定条件限定实时任务的截止期必须等于其周期,限制了它的使用范围。论文突破这一限制,提出了更具一般性的可调度性分析判定充要条件。通过对可调度性判定充要条件的分析,提出了基于不可抢占式EDF调度算法的周期性实时系统可调度性分析算法。     

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

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

容错优先级可提升的抢占阈值容错调度算法

基于软件容错模型,提出了允许容错优先级提升的抢占阈值容错调度算法(extended fault-tolerantfixed-priority with preemption threshold,简称FT-FPPT*).该算法能够在抢占式容错调度算法(fault-tolerantfixed-priority preemptive,简称FT-FPP)和抢占阈值容错调度算法(fault-tolerant fixed-priority with preemptionthreshold,简称FT-FPPT)无法提高系统容错能力的情况下,进一步提高系统的容错能力.为了获得系统中任务优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的优先级配置搜索算法(priorityassignment search algorithm,简称PASA).经过深入分析和实验证明,与FT-FPPT算法相比,FT-FPPT*算法能够有效地提高硬实时系统的容错能力.     

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

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

低复杂度的阈值优化实时调度算法

嵌入式实时系统在其CPU及内存资源相对稀缺时,必须采用复杂度低,系统开销小的调度算法.基于阈值的调度算法可以提高任务的调度性,减少任务间的切换,以此减少内存需求和系统开销.提出了基于抢占差值的阈值分配优化算法.算法在最小阈值分配法基础上,从高优先级向低优先级方向设置任务的阈值,为任务集找出一组满足最大抢占差值的阈值分配方案.经过理论分析及实例验证,算法可以显著降低任务的切换次数,并且算法的复杂度优于传统的优化算法.     

实时事务调度及静态可调度性分析

在类似闭环控制的硬实时数据库应用环境,实时事务具有一定的静态可预报性,其中实时事务的可调度性分析是维护实时数据库时间正确性的基础.通过利用抢占阈值,提出了一种新的实时事务处理模型,它集成了CPU调度和数据调度,实现离线并发控制,具有单阻塞的特征与好的静态可预测性,并有利于降低事务系统的负载和改善可调度性.进一步由此建立了实时事务的静态可调度性分析模型以及求最优可行调度的整数规划模型,该模型有利于达到实时事务调度的整体优化.     

基于Hadoop的三队列作业调度算法

Hadoop集群单队列作业调度会产生短作业等待、资源利用率低的问题;采用多队列调度可兼顾公平、提高执行效率,但会带来手工配置参数、资源互占、算法复杂等问题。针对上述问题,提出三队列作业调度算法,利用区分作业类型、动态调整作业优先级、配置共享资源池、作业抢占等设计,达到平衡作业需求、简化一般作业调度流程、提升并行执行能力的目的。对短作业占比高,各作业占比均衡以及一般作业为主,偶尔出现长、短作业三种情况与先进先出(FIFO)算法进行了对比实验,结果三队列算法的运行时间均比FIFO算法要少。实验结果表明,在短作业聚集时,三队列算法的执行效率提升并不显著;但当各种作业并存且分布均衡时,效果很明显,这符合了算法设计时短作业优先、一般作业简化流程、兼顾长作业的初衷,提高了作业整体执行效率。     

基于广义罚函数可行性准则的DE算法对不确定数据的处理

针对不确定数据集成效率低的问题,构造基于区域分割的广义罚函数可行性准则,分析了分割搜索区域的迭代点特征和可行性准则的性质与优势,据此提出一种基于广义罚函数可行性准则改进的DE算法(DE-GPFFC算法).机器学习数据集UCI中不确定数据集的数值结果显示:不确定数据集中最优可行点趋向概率0.5分布,其他数据点趋向概率0,1分布,其中趋向于概率0.5分布的数据点位于可行域int(D),其他数据点位于非可行域out(D).DE-GPFFC算法使得不确定数据集在可行域边界Round(D)进行跨区域搜索,有效提高了不确定数据分类集成效率.     

多资源约束的车辆调度问题的改进遗传算法

随着世界经济的发展,物流产业中需要满足的需求越来越多,车辆管理调度是物流系统中一个重要环节。如何在多资源约束的情况下实现车辆的合理的调度是促进现代物流业繁荣和发展的关键问题,因此,通过研究物流配送中的车辆调度需求,针对传统的遗传算法阻碍了车辆调度的发展和改进,减缓物流业快速发展的缺点,提出一种改进的、有效的,对一般车辆调度问题具有一定适用性的遗传算法。通过实例论证表明该算法具有可行性和高效性。     

非集中调度模型下的网格资源调度研究*

针对当前网格资源调度系统扩展性差的问题,提出了基于非集中调度模型的以保守Backfilling算法为核心的网格资源调度算法.探讨了网格任务在站点处理器数目异构情况下,网格作业多站点协同调度问题.实验仿真证明,在跨网格站的资源调度中,运用资源预留策略和多站点作业分块可以改善作业的平均响应时间,并起到负载平衡的效果.     

基于改进时间指针的相控阵雷达任务调度方法

针对相控阵雷达实时任务调度中时间资源利用不充分的问题,提出了一种基于改进时间指针的任务自适应调度方法.以时间指针为对象,从整个调度时间轴上所有满足时间指针处执行条件的任务请求中,选择一个优先级最高的任务作为当前时刻的执行任务,有效减少了空闲时间的浪费,使得相控阵雷达能够在有限时间资源内调度执行更多的任务.与基于传统时间指针的调度方法仿真对比,结果表明:方法提高了任务调度成功率和时间利用率,有效提升1了相控阵雷达的整体调度性能,具有一定的优越性.     

改进区块遗传算法解决分布式车间调度问题

针对分布式车间调度问题,提出了改进区块遗传算法(modified block-genetic algorithm,MBGA).用NEH和随机性两种方式得到高质量的初始解,然后进行统计分析,选出精英染色体,建立工件-车间分配矩阵和工件-机器排序矩阵,挖掘联系紧密的基因链组成区块.构建基于区块的人工染色体,并进行基因重组,...     

基于改进遗传退火算法的生产智能调度系统

为了满足多品种小批量生产模式的需求,设计了一套基于智能调度算法的生产调度系统。根据数据的特点和系统的需求,设计了合理的数据结构和不同的调度规则;根据实际应用的要求,改进了遗传退火算法,使算法可以进行柔性调度和优先级调度,并且算法可以满足零件装配关系约束。在.NET3.5框架下,开发了生产智能调度系统,实现了对生产任务的智能调度。     

基于GridSim的网格算法测试软件开发*

针对目前绝大部分的网格任务调度实验均建立在仿真实验的基础之上,而GridSim网格模拟器在支持多任务、多资源环境下的网格算法测试方面表现得越来越力不从心,开发一个便于网格研究者使用的网格算法测试软件迫在眉睫。设计并实现了基于GridSim的网格算法测试程序,该程序包括了构建环境模块、任务调度模块和结果输出模块三个子模块。通过实验验证,该程序能够达到在多任务、多资源环境中分析、对比和验证网格调度算法性能的目的。     

物流云服务下基于改进蝙蝠算法的任务调度

针对物流云服务模式中调度任务多、信息量大、需求广的特点,提出了一种改进蝙蝠算法求解物流云服务调度问题的方案,其优化目标为最小化调度时间和最大化资源利用率.根据设计的算法流程,首先基于工件升序排列(ranked order value,ROV)规则对蝙蝠个体进行重新编码;然后调整初始化数据范围来减少分配任务超载和资源闲置现象,并在迭代过程中增加约束条件来均衡任务量,最终实现了资源与任务的智能调度.通过和遗传、粒子群以及基本蝙蝠算法的对比分析,体现了改进算法的优越性.最后利用Witness对方案进行仿真,证明了改进蝙蝠算法在解决物流云服务任务调度中的有效性,同时扩展了蝙蝠算法的应用领域.