一种基于任务竞争力的工作流调度算法

网格计算聚集了大量的异构分布式的计算或存储资源,为科学研究提供了一个高性能环境.然而,网格资源的异构性和自治性特征使得任务调度变得极其复杂.针对DAG表示的科学工作流调度问题,根据任务可用资源率确定任务调度的优先级,以任务竞争力刻画任务对资源的最佳匹配度,基于分层调度策略提出了一种基于任务竞争力的工作流调度算法.采用GridSim模拟实验表明该算法相对于其他两个算法,具有更小的执行时间.     

云计算环境下的大规模图状数据处理任务调度算法

针对云计算环境下调度算法必须考虑资源租赁成本的问题,提出一种新的基于粒子群优化的大规模图状数据处理任务调度算法(LGPPSO).首先,该算法将图状数据处理任务调度方案编码为粒子群中粒子的位置,并利用任务的调度长度和资源租赁成本建立适应度函数来评价当前粒子的优劣程度,然后重新定义粒子群的参数和相关操作,最后在算法的每一次迭代过程中,粒子不断更新自身的速度和位置,以获得任务调度的近似最优解.模拟实验结果表明:在仅以调度长度为目标时,LGPPSO算法的调度长度比异构最早完成时间任务调度算法(HEFT)平均降低约12.3%;在以调度长度和资源租赁成本为目标时,与成本感知任务调度算法(CCSH)相比,在资源租赁成本基本一致的情况下,LGPPSO算法的调度长度平均降低约9.97%.     

支持优先级约束任务的容错调度算法

为了解决异构分布式系统中可靠调度问题,提出一种考虑处理机链路通信竞争的,支持优先级约束任务的容错调度(FSPCT)算法。该算法使用通信竞争模型描述处理机之间通信,在备份成本最小化和备份任务最早完成之间寻求平衡点。对主副版本任务的最早开始时间进行分析,并限定了所执行的处理机,在处理机出现故障后任务可以顺利执行。实验结果表明FSPCT算法的综合性能优于现有一些算法。     

基于动态任务优先级的网格任务调度算法研究

网格环境下的任务调度是一个NP完全问题.为了确保每一步都能优先调度影响调度长度最大的就绪任务,提出一种采用动态任务优先级策略的任务调度算法.在进行任务调度的过程中,通过动态计算任务图DAG的关键路径并有效地利用处理器的空闲时间段来复制任务,使任务节点之间的通信开销尽可能降低,进而缩短整个任务图的完成时间.大量的模拟实验结果表明,所提的算法在任务完成时间上明显优于HEFT算法和DDS算法.     

μC/OS-Ⅱ内核任务调度算法的改进

μC/OS-Ⅱ是一个基于任务优先级抢占式的实时内核,但它不具有相同优先级任务的实时调度功能.为了使μC/OS-Ⅱ内核既支持不同优先级的多任务抢占式调度,又支持同一优先级的多任务调度,提出对μC/OS-Ⅱ内核的改造,加入以时间片轮转调度算法进行相同优先级任务的调度.方法是保持原有不同优先级抢占式调度链表,增加相同优先级的时间片轮转调度链表,通过任务控制块指针使任务调度在2个链表之间切换.给出了在μC/OS-Ⅱ任务调度模块中算法改进的实现步骤、实验过程和结果.结果说明了提出的改进调度算法是可行的.     

一种可调节动态任务调度算法

提出了适于异构环境独立任务调度的可调节动态调度算法(AS算法)。该算法以任务与处理机的执行时间和完成时间作为参数共同构造任务调度顺序的衡量值,其中二者所占的比重能进行适当调整。AS算法克服了Min-min算法单纯追求局部最优的局限性,更适合异构环境。实验结果表明AS算法可以有效地降低调度跨度,其性能比Min-min算法有所提高。     

一种基于任务分解的时间均衡调度算法

网格环境下的任务调度是一个NP完全问题,它一直是网格领域研究的核心。针对计算网格中的任务放牧调度这类问题,提出了一种基于任务分解的时间均衡调度算法。该算法在调度过程中充分考虑了网格资源的特点,采用重复调度和任务分解策略,并进行了仿真实验。在任务完成时间和系统吞吐率两方面与Max-min和Max-int算法进行比较,实验结果证明该算法优于Maxmin和Max-int,是一种性能较好的任务调度算法。     

一种面向教育云资源共享的优先级队列任务调度算法

针对教育云资源共享中任务调度时优先级不同带来的挑战,提出了一种基于任务优先级的最优调度算法优化教育服务质量.文章首先分析了各种任务的服务质量需求,对任务进行优先级分类,设计了一种基于优先级的队列调度核心算法.然后,分析了所设计调度算法的实施过程和具体步骤.仿真结果验证了优先级队列任务调度算法能够降低系统的处理时延,从而...     

一种新型的云任务调度算法研究

云计算具有弹性、保证服务质量和按需的资源配置模型等特征,通常用于处理大批量的计算任务,因此任务调度策略对资源使用效率起着至关重要的作用.考虑到任务的数量和到达服务器的时间不确定性,并且用户对任务的执行往往有一定的期望(如任务优先级、执行时间等),如何合理地分配计算资源,最大程度满足用户的服务质量需求是一个值得研究的问题.为此,提出了一种新型的云环境下QoS-aware服务质量感知的任务调度算法(QTS),该算法结合贪心算法的思想,并加入了任务完成满意度模型作为任务调度的评价依据.通过扩展CloudSim仿真平台进行实验,将QTS与RR调度、Max-Min和Min-Min调度比较,结果表明,QTS是一种有效的任务调度算法.     

经济网格中基于剪枝策略的时间-费用优化任务调度

由于在经济网格环境下,存在着资源异构和分布的特征,网格任务调度变成了一个复杂的问题.为此,针对独立任务,在考虑用户的服务质量经济需求偏好的基础上,提出了一个优化用户时间和费用的任务调度方案选择算法.该算法首先将网格中兼顾时间和费用的任务调度方案形式化为一个n层m叉树,然后将调度方案的选择问题转化为树的遍历问题,最后利用剪枝方法避免无效路径的搜索,降低了时间复杂度,实现了任务的优化调度.结果表明该算法能按照用户的时限和费用需求偏好选择优化的调度方案,且在性能上优于传统的未剪枝算法.所以该算法是一种可行的任务调度算法.     

有通信冲突的异构系统上的任务调度

在新的系统模型上，提出了一个任务调度算法．该系统模型考虑了通信冲突，即在任何时刻，一个处理器只能接收一条消息，发送一条消息．新的算法包括异构系统中任务优先级的高效排序和基于任务复制的处理器分配两部分．随机产生的任务图和一个具体应用的任务图进行调度试验的结果表明，该算法比已有调度算法的性能有了显著的提高．     

考虑释放时间和调度顺序的可分任务调度模型

针对处理机具有任意释放时间的异构并行与分布式系统,通过寻找最优的处理机调度顺序和任务分配方案,使得任务的完成时间达到最短.首先,在给定处理机调度顺序的情况下,分析了处理机释放时间对任务完成时间的影响,得到了任务分配方案关于处理机调度顺序和时序约束条件的解析解;然后,以调度顺序和时序约束条件为变量,以任务的最短完成时间为目标,建立了一种新的可分任务调度模型;最后,设计了高效的全局优化遗传算法求解该模型.仿真结果表明所提算法比已有算法完成任务的时间更短.     

一种基于模糊逻辑优先级的雷达任务自适应调度算法

为适应目标环境变化情况,提出了一种基于模糊逻辑优先级的雷达任务自适应调度算法.该方法基于目标运动状态和属性通过模糊逻辑推理动态确定任务的优先级,并结合时间窗的特点采用一步回溯方法调整发生冲突的任务,保证更多高优先级的任务在其期望的时间内被调度.仿真结果表明,该调度算法在保证调度率的前提下降低了任务的调度代价.     

一种成本驱动的云计算任务调度策略

为了使得云计算不仅满足调度任务的QoS要求,且尽可能地最大化其服务收益,从云服务提供方的角度出发,提出了一种成本驱动的云计算任务调度策略.提出的方法在满足用户任务QoS约束的前提下,以最大化云环境单位计算开销的服务收益作为其调度目标,在此基础上建立相应的任务调度模型,最后通过遗传算法在多项式时间复杂度内对上述调度目标进行优化求解.在Cloudsim模拟器上完成了一系列仿真测试.结果表明:提出的方法在任务完成时间、调度完成时间超过调度截止时间底线的任务比例,以及云环境单位计算开销的服务收益等指标上均优于传统的Min-min算法和改进的QoS约束的Min-min算法.     

基于CSA和PSO的多目标优化任务调度算法

针对现有云计算环境中任务调度算法资源利用率低、完成时间长和调度成本高的问题,提出一种基于布谷鸟搜索算法(Cuckoo Search Algorithm, CSA)和粒子群优化(Particle Swarm Optimization, PSO)混合的多目标优化任务调度策略.该策略以完成时间、成本以及最后期限违反率为目标函数,将布谷鸟搜索算法和粒子群优化有效地组合来执行智能优化任务调度问题,避免调度过程中出现局部最优现象.实验结果表明:相对于其他启发式调度算法,本文提出的方法明显具有优势,可以最大程度地降低完成时间、调度成本和最后期限违反率.     

网格计算中基于任务优先级的负载均衡算法

任务调度是网格计算研究的核心问题之一,任务调度策略的好坏将直接影响网格系统的性能.在对已有启发式任务调度算法进行分析比较基础上,针对于网格计算中的高吞吐率应用的任务调度问题,提出了一种综合考虑资源节点性能度量和任务优先级的负载均衡的启发式任务调度算法.进行了仿真实验,在任务完成时间和系统吞吐率二个方面与传统的Min-min算法、Max-min算法和Sufferage算法进行比较.仿真结果表明该算法不但可以减小任务总的完成时间,而且可以提高系统的吞吐率,更适用于高吞吐率应用任务调度问题的解决.     

双参数模糊调度在实时控制系统中的应用

针对嵌入式多任务实时控制系统,提出模糊调度设计(FSD)算法.该算法基于任务重要性和空闲时间2个特征参数,动态调整任务优先级,使得空闲时间越短且越重要的任务,其优先级越高.FSD算法在资源有限时可以提高关键任务的可调度性和控制性能,在不同系统负载下,通过灵活的模糊调度规则获得满意的系统可调度性能.为评估调度算法,定义性能指标IVR为任务价值总和与任务重要性之和的比值,若IVR越大,则系统可调度性越好.仿真结果表明:在正常负载下,FSD算法在保证关键任务可调度性的同时,对非关键任务的可调度性影响较小,任务调度成功率比MIX(加权组合)算法的高;超载时,FSD算法优先保证关键任务在其截止期内完成,避免EDF(截止期优先)算法中易出现的多米诺现象发生,有效提高系统的整体性能.     

基于不同分配策略的云计算任务调度性能比较与分析

形式化描述了云计算环境下的负载均衡任务调度问题,借助动态规划方法形式化推导了最早完成时间的启发式优先分配策略,给出了基于先易后难优先分配策略、先难后易优先分配策略的启发式云计算任务调度算法。阐述了基于顺序调度策略、先易后难优先分配策略、先难后易优先分配策略等启发式任务调度算法和基于禁忌搜索策略、元胞演化策略等智能任务调度算法。针对不同分配策略的云计算任务调度进行性能比较与分析,提出了完成时间可改进百分比和资源负载平衡因子的调度性能评价指标,实验数据对比充分表明:与启发式调度算法相比,智能调度算法能减少任务执行时间,优化资源负载均衡性能。     

一种基于贪心策略的启发式云计算任务调度算法

提出了一种基于贪心策略的启发式任务调度算法,用于优化云计算环境下任务调度中执行时间。首先,给出了云计算环境下任务调度问题的形式化描述及其最早完成时间的启发式优先分配原则;接着,基于最早完成时间的优先分配原则,采用贪心策略难易交错地分配任务求得任务调度的初始解;进而,引入了任务对交换的收益值概念,采用贪心策略选择收益值大的任务对交换优化任务调度初始解的执行时间;最后,在Cloud Sim云计算仿真实验平台下进行了顺序调度算法、Min-Min算法、Max-Min算法和本文算法的对比实验,实验数据对比充分验证了本文算法既能减少任务执行时间,又能使资源负载相对平衡。     

异构系统中带可用性约束的性能优化调度算法

针对可用性约束以及任务响应时间不同给异构系统中实时任务调度分配带来的处理机节点难选取的问题,提出了一种带可用性约束的性能优化调度算法(PO-SSAC)。该算法将异构系统内处理机节点、实时任务以及带可用性约束的实时任务调度过程进行数学建模,通过考虑可用性成本与任务平均响应时间的折中,引入系统综合开销的概念,根据实时任务的可用性需求为其分配系统综合开销最少的处理机节点调度执行,达到系统调度资源合理利用的目的。实验结果表明,在实时任务调度可用性方面,与SSAC算法相比,PO-SSAC算法提升了3.4%,与MinMin算法相比,提升了76.9%,与Sufferage算法相比,提升了76.5%;与Sufferage算法相比,PO-SSAC算法的系统综合开销减少了约30%,优化了异构系统的实时任务调度性能。