基于局部关键路径与截止期限分配的云工作流调度算法

为了解决云计算中截止期限约束下的工作流调度代价优化问题,提出一种基于局部关键路径和截止期限分配的工作流任务调度算法。为了满足期限约束,并最小化执行代价,算法将工作流任务的调度过程划分为两个阶段:期限分配阶段和调度资源选择阶段。期限分配阶段定义工作流的局部关键路径,并以递归的方式在局部关键路径上的任务间进行子期限分配;调度资源选择阶段在满足任务子期限的同时,为每个任务选择执行代价最低的资源进行任务调度,以实现调度代价优化。分析算法的时间复杂度,并通过一个算例对算法的实现思路进行了详细阐述。通过科学工作流结构的仿真实验,证明了算法不仅可以满足截止期限约束,而且可以降低工作流任务的执行代价。     

基于放置代价的可重构系统任务统一调度算法

高效的任务调度算法对可重构系统的性能有极大的影响。针对目前可重构系统任务在线调度算法的不足,提出了一种基于放置代价的调度算法。该算法考虑了3种代价,分别为:硬件任务在FPGA上的执行时间、占用的FPGA面积以及FPGA的碎片情况,并且也考虑了软硬件任务的统一调度。在调度过程中,当代价超过设定的阈值时,就拒绝其在FPGA上运行,并由CPU执行其软实现。通过合理地拒绝一些代价较大的任务,能够从整体上提高任务调度成功率。实验表明,同已有算法相比,该算法能够获得更高的任务截止保证率。     

一种基于代价抢占的混合可重构任务调度算法*

针对同时存在独立任务和相依性任务的混合可重构任务调度,提出了基于代价抢占的混合可重构任务实时调度算法。提出了相依性任务等价运行截止时刻的计算方法,使混合可重构任务按照配置截止时刻排队配置。针对相依性任务调度特点,分析得到了相依性任务集合调度失败的充分条件,提前判定和丢弃无法调度成功的相依性任务集合;通过有限预配置防止相依性任务无效占用可重构资源;通过基于代价抢占减少调度失败任务个数。仿真结果表明,该调度算法提高了任务调度成功率。     

一种基于能耗优化的云计算系统任务调度方法

服务器执行任务产生的能耗是云计算系统动态能耗的重要组成部分。为降低云计算系统任务执行的总能耗,提出了一种基于能耗优化的最早完成时间任务调度方法,建立了服务器动态功率计算模型,基于动态功率的服务器执行能耗模型,以及云计算系统的能耗优化模型。调度策略根据任务的截止时间要求和在不同服务器上的执行能耗,选择不同的调度算法,以获得最小任务执行总能耗。实验结果证明,提出的任务调度方法,能够较好地满足任务截止时间的要求,降低云计算系统任务执行的总能耗。     

多处理器系统的在线节能调度算法

随着多处理器系统计算性能的提高,能耗管理已变得越来越重要,如何满足实时约束并有效降低能耗成为实时调度中的一个重要问题。基于多处理器计算系统,针对随机到达的任务,提出一种在线节能调度算法(OLEAS)。该算法在满足任务截止期限的前提下,尽量将任务调度到产生能耗最少的处理器,当某个任务在所有处理器上都不能满足截止期限要求时,则调整处理器之间的部分任务,使之尽量满足截止期限要求。同时,OLEAS尽量使单个处理器上的任务按平均电压/频率执行,以降低能耗,只有当新到任务不满足截止期限要求时,才逐个调高前面任务的电压/频率。模拟实验比较了OLEAS、最早完成时间优先(EFF)、最高电压节能(HVEA)、最低电压节能(LVEA)、贪心最小能耗(MEG)和最小能耗最小完成时间(ME-MC)的性能,结果表明OLEAS在满足任务截止期限和节省能耗方面具有明显的综合优势     

一种在线节能实时调度算法

随着多处理器系统规模的不断扩大,如何节能成为一个亟待解决的重要问题。为此,基于多处理器系统提出一种针对随机任务的在线节能实时调度算法。使用统计方法,根据已有任务的到达时间和计算量估计新任务在空闲处理器上执行的电压/频率,使还未到达的任务能够满足截止期限并有效节能。在考虑单个处理器上执行的任务时,计算执行这些任务所需的平均电压/频率,使所有任务的执行速度尽量均衡,当某些任务不能满足截止期限要求时,则调高未执行任务的电压/频率。实验结果表明,与EDF,HVEA,MEG和ME-MC算法相比,该算法在满足截止期限和节能方面具有明显的优势。     

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

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

一种可行的分布式硬实时容错调度算法

针对分布式硬实时系统发生处理机故障后,当前周期内的任务实例和后续实例相对截止期限的不同紧迫程度,提出非紧迫周期内延迟策略——DNUP(delay in non-urgent period).该策略能够尽可能地推迟非紧迫实例的执行,使得低优先级实例有更多的机会完成其紧迫周期内的执行,从而实现处理器空闲(slack)资源的合理挪动.仿真实验结果表明,与其他几个著名的分布式容错调度算法相比,DNUP策略能够提高任务的可调度性,从而有效减少了所需处理机的数目.     

云科学工作流截止期限约束代价优化调度算法*

针对异构云环境下科学工作流调度的代价优化问题,提出一种基于约束关键路径的代价优化调度算法(CSACCP)。算法以满足截止期限约束同时最小化执行代价为目标,充分考虑云环境和科学工作流的独有特性,设定任务的向上权值,将工作流分解成约束关键路径(CCP)集合。结合首次适应插入算法以减少空闲时隙,改善费用优化效果,采用及时完成和最小费用增长代价的虚拟机选择策略形成备选资源集合。整体分配CCP到最便宜的虚拟机实例,压缩数据通信开销减少工作流的执行代价。通过四种著名的科学工作流仿真测试,结果表明与现有启发式算法相比,CSACCP不仅可以在满足截止期限的约束下得到更小的执行代价,还拥有更高的任务调度成功率。     

QoS约束云环境下的工作流能效调度算法

云环境可以为大规模工作流的执行提供高效、可靠的运行环境,但工作流执行时带来的高能耗不仅会增加云资源提供方的经济成本,还会影响云系统的可靠性,并对环境产生不利影响。为了在满足用户截止时间QoS需求的同时降低云环境中工作流调度的执行能耗,提出一种工作流能效调度算法QCWES。该算法将工作流的能效调度方案求解划分为3个阶段:截止时间重分配、任务调度选择排序以及基于DVFS的最佳资源选择。截止时间重分配阶段旨在将用户定义的全局工作流截止时间在各个任务间进行重分配,任务调度选择排序阶段旨在通过自顶向下的任务分级方式得到任务调度序列;基于DVFS的最佳资源选择阶段旨在为每个任务选择带有合适电压/频率等级的最优目标资源,在满足任务的子截止时间的前提下使总体能耗达到最小。通过随机工作流和基于高斯消元法的现实工作流结构,对算法的性能进行仿真实验分析。结果表明,所提算法可以在满足截止时间约束下降低工作流的执行能耗,实现用户方的QoS需求与资源方的能耗间的均衡。     

基于(m,k)-firm约束规范的混合任务调度算法研究

讨论了在准实时环境下,包括准实时周期任务和准实时非周期任务在内的混合任务调度算法HTSF.HTSF算法是在满足周期任务(m,k)-firm 约束规范的前提下提高非周期任务可调度性,同时合理利用可用空闲时间,提高整个系统的服务质量.HTSF算法给出了非周期任务的可调度性分析方法,同时采用静态调度与动态调度相结合的方法调度周期任务和非周期任务.模拟测试结果显示,系统对非周期任务的接收率比同类相关算法的接收率高.     

提高软非周期任务响应性能的调度算法

实时环境中常常既包含硬周期任务,又包含软非周期任务,引入一种改进软非周期实时任务响应时间的算法.已有的解决混合任务调度问题的方法都是基于速率单调（Rate Monotonic）策略的,其中从周期任务“挪用时间”的算法被证明优于其他所有算法.但是,速率单调算法限制了处理器的使用率,从而使周期任务的可“挪用”时间受到限制.最后期限驱动（Deadline Driven）策略DD可使潜在的处理器利用率达到100%.新算法正是在周期任务的调度中适当加入了DD策略,从而使非周期任务的响应时间得以缩短.仿真实验的结果表明,这种算法的性能优于已有的所有算法,而由它所带来的额外开销却不算很高.     

应用于实时系统的RMS算法的改进

本文阐述了以PLC为核心的HGJD001实验台电气控制系统，并采用上位计算机实现对实验台运行状态的通讯监测。     

单机实时系统中的一种混合型实时容错调度算法

目前研究单机实时系统的调度算法文章大多只能调度单一类型的任务。本文在PKSA算法的基础上，建立了一种混合型实时容错模型，提出一种调度算法不仅可以调度有容错需求的周期任务，同时也能够调度无容错需求的周期任务和非周期非实时任务，实现了调度混合型任务的目的。     

单机实时系统中的一种混合型实时容错调度算法

目前研究单机实时系统的调度算法文章大多只能调度单一类型的任务。本文在PKSA算法的基础上,建立了一种混合型实时容错模型,提出一种调度算法不仅可以调度有容错需求的周期任务,同时也能够调度无容错需求的周期任务和非周期非实时任务,实现了调度混合型任务的目的。     

一种实时系统中的多任务可预测调度算法

通过研究实时系统中可能出现的任务类型，提出了一种实时系统任务模型和基于这个模型的多任务调度算法，分析了该算法下所有周期任务和非周期任务可调度的条件。该算法结合了DMS(Dcadlinc Monotonic Scheduling)和DD(Deadline Driven)算法，在保证系统中周期任务执行的前提下,也使非周期任务获得了，较好的响应时间。     

基于多处理机的混合实时任务容错调度

提出了一种混合实时任务容错调度算法．该算法采用Rate Monotonic(RM)算法完成周期任务的静态调度；采用预订处理机时间方法和Earlier Deadline First(EDF)算法动态调度非周期任务；采用主／副版本备份技术确保系统的容错能力．通过充分利用周期任务的剩余处理机时间调度非周期任务和主动备份与被动备份相结合的方法有效地减少了处理机数．仿真结果证明了算法的有效性．     

一类特殊的非抢占式周期任务的调度方法

现实世界中针对许多任务的资源调度分配和使用具有时效性,对该类任务的调度问题目前的研究还较少。针对此类调度问题,分析其特点,明确其与已有调度模型研究问题的区别,提出新的非抢占式周期任务调度模型,并证明了该类问题为NP完全问题。在此基础上,给出了一种求解最优解的模式剪枝算法,以及一种求解近似解的快速求解算法。相关实验表明,提出的两种算法能够针对不同的需求场景分别对调度问题进行高效求解。     

Dynamic priority scheduling of periodic and aperiodic tasks in hard real-time systems

This paper addresses the problem of scheduling aperiodic tasks in real-time systems. The proposed scheme combines the Earliest-Deadline-First algorithm for scheduling periodic tasks with the Deferrable Server approach for servicing aperiodic tasks. Necessary and sufficient conditions are derived for guaranteeing feasibility of a given periodic task set when a deferrable server is present. An analytic model is proposed for selecting the best feasible period and computation time of the server to minimize the mean response time of aperiodic tasks. An evaluation of the proposed model using a simulator indicates that the server parameters selected by the model result in mean response times that are close to the best mean response time determined by the simulator.     

EDF统一调度硬实时周期任务和偶发任务的可调度性判定算法

现有的硬实时周期任务和非周期任务的混合调度方法都没有保证非周期任务的实时性,所以不适合调度具有强实时要求的偶发任务.通过分析和计算EDF算法调度偶发任务所占用的空闲时间和挪用时间,以及调度后对空闲时间和最大可挪用时间的影响,提出一种采用EDF算法统一调度硬实时周期任务和偶发任务时的可调度性充分判定算法.最后用仿真实验得出了该算法在不同系统负载下的判定准确率和偶发任务的平均响应时间.