logo资料库

论文研究-基于排队模型和强化学习的动态云任务调度算法 .pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.43M 资料格式：pdf 举报 版权申诉
第1页 / 共15页
第2页 / 共15页
第3页 / 共15页
第4页 / 共15页
第5页 / 共15页
第6页 / 共15页
第7页 / 共15页
第8页 / 共15页
资料共15页，剩余部分请下载后查看
    5 10 15 20 25 30 35 中国科技论文在线 http://www.paper.edu.cn 基于排队模型和强化学习的动态云任务调 度算法# 赵翌欢，丁丁，郭欣欣，康凯旋** （北京交通大学计算机与信息技术学院，北京 100044） 摘要：作为云计算的核心问题之一，如何有效地管理和调度云计算资源是一个极具挑战性的 研究课题。在异构云环境中，为了提高任务调度效率，最小化任务响应时间，降低能耗，本 文提出了一种基于排队模型和强化学习的动态云任务调度算法 QTPRL（Dynamic Cloud Task Scheduling Algorithm Based on Queue Theory and Pre-processed Reinforcement Learning）。该 算法首先基于 M/M/S 排队模型对云任务调度进行建模，采用单队列多资源池的设计思路， 将任务分发到空闲的资源池（物理机）去执行，减少了任务等待队列的长度，从而减少了任 务的等待时间。在此基础上，将任务长度、任务的截止时间和等待时间相结合，构建动态优 先级，对任务进行预处理，并使用强化学习的方法将任务分配到不同物理机空闲的虚拟机上， 完成任务调度。实验结果表明，与传统的云任务调度方法相比，本文提出的算法可以有效减 少任务的响应时间，提高资源利用率，并降低系统能耗。 关键词：云计算；任务调度；排队模型；强化学习；能耗 中图分类号：TP393 A Dynamic Cloud Task Scheduling Based on Queue Queue and Pre-processed Reinforcement Learning zhaoyihuan, dingding, guoxinxin, kangkaixuan (School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044) Abstract: As one of the key issues in cloud computing, it is an extremely challenging research topic to manage and schedule cloud resources. To achieve lower task response time and higher resource utilization in heterogeneous cloud environment, a dynamic cloud task scheduling algorithm based on Queue Theory and Pre-processed Reinforcement Learning(QTPRL) is proposed in this paper to make task scheduling more energy efficient. Firstly, this method builds task scheduling model based on M/M/S queuing model which adopts the design of a single queue and multi-resource pool to submit tasks to the idle resource pool (physical machine) un-uniformly, reducing the length of waiting queue and the waiting time of tasks. On this basis, a dynamic priority is conducted in the related queues by combining the length, deadline and waiting time of tasks to complete pre-processing. Finally, a kind of reinforcement learning method is used to assign tasks to an idle virtual machine on different physical machines. Simulation experiment results show that our scheduling scheme can outperform on the average response time, resource utilization, and the energy consumption compared to most of traditional methods. Keywords: cloud computing; task scheduling; queuing model; reinforcement learning; energy saving 0 引言 近年来，云计算作为传统网络计算的延伸已经被学术界和工业界广泛采用。它是一种通 过网络为用户提供动态服务的模型，因此，提供高效服务是云计算的关键。为了实现这一目 标，云计算系统需要根据任务的不同请求按需分配资源，并能够根据资源池的大小合理调整 基金项目：国家自然科学基金项目（61300176,61473031,61472029,61672086）；中央高等学校基本科研业 务费（2016JBM19） 作者简介：赵翌欢（1993-）,女，硕士研究生，主要研究方向：云计算 通信联系人：丁丁（1980-），女，副教授，博导，主要研究方向：云计算、并行与分布式计算. E-mail: dding@bjtu.edu.cn - 1 -
    40 中国科技论文在线 http://www.paper.edu.cn 来满足任务请求，这就提出了云计算环境中任务调度的问题[1]。然而，由于用户群庞大，任 务数量多，请求类型多样，到达时间的随机性强，加之资源存在异构性和动态性，使得云任 务调度变得十分困难[2-3]。因此，为了给任务分配合适的资源，实现任务响应时间最小化， 资源利用率最大化，从而降低能耗，急需合理的任务调度。 作为云计算的核心问题之一，任务调度的关键包括任务调度模型和任务调度策略两方面。 45 随着计算机技术与 Internet 的普及应用和飞速发展，云计算环境变得越来越复杂，如何把计 50 55 60 65 70 算资源池的资源按照到达时间优化分配给待处理的任务个体，需要考虑到不同集群中虚拟机 的运行状态和资源消耗情况，因此，必须要建立云任务调度模型[4-5]。而云用户数量的急剧 增长对云任务调度策略提出了挑战[6-7]：首先是任务需求、申请时间和任务分布的不平衡， 造成调度十分困难；其次是如果资源配置不是最优的，用户可能会面临高成本、高能耗和性 能下降等问题；最后是云计算环境中节点资源需求的动态变化，容易造成负载的波动，使调 度更加复杂。针对这些问题，需要在云任务调度模型的基础上，提出一种行之有效的任务调 度策略。 1 相关工作 1.1 任务调度模型 目前，云任务调度中已有很多不同的调度模型，其中排队论因其适用于随机服务系统， 且易扩展优化的特点在近年来受到越来越多的重视，在分析系统调度性能，提高系统调度效 率方面发挥着十分重要的作用。文献[8]基于排队论和概率论的理论知识，提出了一种基于 动态负载均衡模型的优化策略。文献[9]建立了云计算的性能管理排队模型，将应用程序当 作队列成员，将虚拟机当作服务机构，根据排队论的知识动态增加或删除虚拟机，以此适应 系统的规模变化。文献[10]基于排队理论中的 M/M/1 模型建立了云计算的性能管理排队模型。 然而，上述基于排队理论的调度模型较为简单，缺乏相应的灵活性，造成调度时间过长，且 大部分适用于同构环境。异构环境下的调度如[11]采用备份任务的方法来实现任务调度，但 是备份过多会造成资源的浪费。因此，现有的方法已经不能满足复杂环境下云任务调度的需 求，建立一种新的调度模型势在必行。 1.2 任务调度策略 任务调度策略对用户应用的服务质量和云计算系统的运行效率等都会产生直接影响。好 的任务调度策略能够有效降低任务完成时间，满足用户对于便捷、安全、人性化的要求，同 时也能提高资源利用率，降低能耗和运营成本，促进云计算系统任务调度的良好发展[12]。 传统的静态调度策略虽然大多数情况下在资源管理中扮演主要角色，但已不能满足大规 模云环境下的调度。自适应动态管理方法有望解决前面提出的挑战[13-14]。早期用于动态调度 的主流技术是启发式技术。该方法的优势在于设计相对简单，文献[15]运用一种启发式shuffle 方法进行任务调度，文献[16]采用改进模拟退火法找到最优分配策略，可以更好的平衡工作 量，最大限度地利用资源，激活较少的主机，并降低云计算的系统功耗。文献[17]提出了多 目标进化算法结合低级回填启发式的方法，来找到工作流到资源的有效映射，最大化几个与 - 2 -
    中国科技论文在线 http://www.paper.edu.cn 服务质量相关的度量，同时减少所需的能量计算。但是这些策略往往只能得到近似次优解， 不太适合异构环境下的动态调度。 目前，机器学习方法被很多研究者用于异构环境下的动态任务调度。如文献[18]提出了一个 云资源管理系统，对时间和能耗进行建模，从以前的资源分配结果中学习。它在运行时使用 这些信息来快速适应工作负载变化,有效地实现了资源与所提供的负载的在线匹配，以追求 成本节省。文献[19]提出了一个能够降低云数据中心能源消耗的资源管理框架。所使用的技 术是用于聚类的k-means，以及用于工作负载预测的随机维纳滤波器，通过实验验证该框架 实现了近乎最佳的能源效率。但是，[18-19]这两种方法受限于设计时预测的可能情形，未纳 入预测的意外情形会导致SLA违规，不适合动态变化较大的环境。文献[20]提出了基于强化 学习和资源控制思想的调度方法，却没有提出整体的设计框架模型，在能耗和性能方面难以 达到理想的平衡。 针对上述研究中存在的任务调度响应时间过长，资源浪费和能耗等问题，本文从任务调 度模型和任务调度策略两个方面研究异构云环境下的任务调度问题，提出了一种基于排队模 型和强化学习的动态云任务调度算法 QTPRL（Dynamic Cloud Task Scheduling Algorithm Based on Queue Theory and Pre-processed Reinforcement Learning）。算法可以具体分为任务 层和调度层两个阶段： 1) 任务层阶段：采用 M/M/S 排队模型对云计算系统进行建模，将随机到达的任务分配 到不同集群的请求队列上，以减少任务的等待时间； 2) 调度层阶段：首先根据任务类型、任务截止时间以及任务等待时间设计动态优先级， 完成预处理，缩短任务调度完成时间；然后根据系统中物理机以及虚拟机当前的执 行状态等信息，对系统的响应时间和资源利用率进行分析，采用强化学习的策略将 任务调度到具体的虚拟机上，使得资源分配更加合理，进一步减少任务的等待时间， 提高资源利用率，降低能耗。 2 基于 M/M/S 排队论的调度模型 排队模型[21]在云计算调度系统中可以表示如下： （a/b/c）:(d/e/f) (1) 其中，a,b,c 分别表示输入、输出（服务时间）的分布及并联的服务站数。d,e,f 分别表示最 多能容纳的负载量，任务总数和排队服务规则，当 d,e,f 三项为∞/∞/FCFS 时可略去。例如， M/M/1 模型表示任务到达时间服从泊松分布、任务服务时间为负指数分布、有 1 个服务器 的排队服务系统。M/M/S 模型则表示任务到达时间服从泊松分布、任务服务时间为负指数 分布、有 S 个服务器的排队服务系统。 2.1 基于 M/M/S 排队论的调度模型 排队模型应用在云任务调度中的主要目标是在最大化资源利用率的同时最小化任务响应时 间。目前国内运营商在处理任务调度问题时，采用了很多基于排队论的方法，但是大部分都 属于 S 个 M/M/1 模型，如图 1 所示。它们大多支持多队列，当任务以一定的平均速率 λ 到 达请求队列时，以 λ/s 的概率分别分配到各个服务器队列。 75 80 85 90 95 100 105 110 - 3 -
    中国科技论文在线 http://www.paper.edu.cn 请求队列 λ …… sλ/ sλ/ sλ/ 1 服务器 μ μ 2 μ s S 个 图 1S 个 M/M/1 模型 Fig.1 S-M/M/1 model 然而，在云计算环境中，由于任务到达时间通常呈现泊松分布，待排队任务随机性强。而每 1 s , 2, ），即每个服务器的平均服务率（单位时间内平均服务完的任务数量）不同， 个集群（即物理机）对不同任务的服务时间也相互独立，且服从不同参数的负指数分布（如 μ μ μ 因此，S 个 M/M/1 模型经常会出现局部队列过长的现象，导致总的任务等待时间较长，调 度效率较差。而 M/M/S 模型具有比 S 个 M/M/1 更快的响应速度，能为各种类型的顾客提 供更高效的服务，更适用于云计算这样复杂的环境。 因此，本文采用 M/M/S 模型构造云任务调度模型，如图 2 所示。在本文提出的基于 M/M/S 排队模型的任务调度中，不同类型的任务按照平均到达率 λ 到达请求队列后，直接以一定的 次序排成一个全局任务队列，并按照如下策略分配到不同的服务器上：当哪个服务器空闲时， 才将任务分配给哪个服务器。这样即使每个服务器的平均服务率不同，也能够避免局部队列 过长的问题。 S 个 1 服务器 μ μ 2 μ s 请求队列 λ …… λ λ λ 图 2M/M/S 模型 Fig.2 M/M/S model 2.2 调度模型的性能分析 本文采用生灭过程的方法对 M/M/S 排队模型进行性能分析。生灭过程可用图 3 所示的发生 率图表示： λ λ λ 1 2 n 2−λ 1n−λ nλ 3 115 120 125 130 135 - 4 -
    中国科技论文在线 http://www.paper.edu.cn 状态 0 1 2 3 ... n-2 n-1 n n+1 ... 2 3 μ μ μ 1 2n−μ nμ 1n−μ 图 3 生灭过程的发生率 Fig3 Transition rates of birth-death process 140 对于每一状态，都可以建立状态平衡方程如表 1 所示。 表 1 生灭过程的状态平衡方程 Tab.1 State equilibrium equation of birth and death process 状态输入率=输出率 0 1 2 … n-1 n 1 μ μ μ 2 3 P 1 P 2 P 3 0 λ P 0 λ P 1 1 + + 0 P + λ μ ） 1 λ μ + 1 2 P 1 P 1 ） 2 0 λ= = （ = （ … = λ n − 2 + 2 P − n λ P 1 n − 1 − n μ P n n + μ n （ λ n + ） 1 λ μ μ − + n 1 n P − P 1 − = + n ） n 1 （ P + 1 n n … ( i i 0,1... ) … n 是状态 i 处于稳定时的概率，λ = n 是服务器 i 的平均服务率。由表 1 可得： 0,1... ) 0,1... ) ( = iP i μ = ( i i n 是任务 i 的平均到达率， 145 150 其中， nC 定义为： = C n = P CP（2） n n 0 − n λ λ λ ... 2 μμ μ ... − n 1 0 − n n 1 1 （3） 在本文基于 M/M/S 排队模型的任务调度中，假设有 S 个并联虚拟机提供服务，每个虚 拟机相互独立且均服从参数为 μ 的负指数分布，任务以一定的平均速率 λ 到达请求队列。 这种情况下，虚拟机的服务率 μ 如公式（4）所示： n μ n =    s = μ ( n = n μ ( n s 1,2,..., ) s + + 1, s 2,...) （4） 则 其中, C n  n （ / ) n = λ μ ρ n ! = n ! λ μ n （ / ) − n s s s ! =    = n ( n ρ s s ! − n s s 1,2,..., ) （5） > n s ( ) λρ μ = ， ρ反映了服务的忙碌和使用的程度，即工作强度。因此，系统的空闲概率 155 0P 如公式（6）所示： - 5 -
    中国科技论文在线 http://www.paper.edu.cn = P 0 − s 1 /[ = n 1 λ μ λ μ s n ( / ) ( / ) ! s ! n + 1 ] λ μ 1 ( / ) − = ! 1 由此得到系统处于工作状态时的任务队长概率分布 nP 如公式（7）所示： s 0 − s 1 /[ s n ρ ρ s 1 ! n n = + 0 1 （6） ] ρ ( / ) s − 任务到达时需要等待的概率 sP 如公式（8）所示： 160 P n  =    = P s n ρ ! n = P n （ 0 0,..., ) s n ρ s s ! − n s > P n s ) ( 0 （7） ∞  = n s = P n ρ S S !( s sP 0 − ρ ) （8） 根据系统在平稳状态下的概率分布，可以计算出平均任务量 sL，即系统中排队等待的任务数 量加上正在执行的任务数量，如公式（9）所示： = L S ∞  = n 0 = nP n ρ s+1 P 0 1)!( s − ρ 2 ) − ( s ρ + （9） 根据平均任务量，可以得到任务从进入系统到服务完毕离去的平均逗留时间 sW 如公式 165 （10）所示： = W s =  L 1  s λ μ   − s ( ρ s P 0 1)!( s − ρ 2 ) + 1     （10） 系统的平均队长为 qL ，即系统中排队等待的任务量如公式（11）所示： ρ 2 ) 根据平均队长，可以得到任务排队等待服务的平均等待时间 qW 如公式（12）所示： ( s n s − − = = L q ∞  − ( n s P n ) = 1 + s ρ P 0 1)!( s （11） 170 = W q − ( s + s P 0 ρ 1)!( s 1 − = L q λ ρ λ 2 ) （12） 通过以上分析可以看出，S 越小，平均队长越长。当 S 为 1 时，此时平均队长的值最大。 随着 S 值越大，平均队长就越小，平均等待时间也越小，资源利用率越高。后面我们将通过 实验进一步证明 M/M/S 模型比 S 个 M/M/1 模型具有更小的平均队长，因此系统的响应时间 更短，调度效率更高。 175 3 基于强化学习的任务调度 高效的任务调度策略不仅可以减少系统的响应时间，而且可以提高系统的资源利用率和系统 吞吐量。然而，复杂的云计算系统往往具有计算节点异构的特点，而且云基础设施上部署的 工作负载又是动态变化的，针对这一问题，本文使用基于强化学习的调度策略来阐述调度层 的过程。 - 6 -
    180 185 中国科技论文在线 http://www.paper.edu.cn 强化学习 Reinforcement Learning（RL）是机器学习领域中的一类算法。由于云计算系统的 所有状态上没有可用的先验信息，而强化学习不受限于预先构建的模型，主要通过训练来维 护系统的稳定：调度程序对复杂运行环境进行自适应学习，通过不断的评估选择使奖惩函数 值最大的动作来得到最终的方案。换言之，调度程序使用基于反馈的调度机制对各个学习阶 段的环境观察并更新，使调度结果越来越接近最优解。因此，强化学习这种动态规划的思想 更适合实现云任务的动态调度。 强化学习算法主要分为三大类:基于策略的算法、基于值函数的算法和 AC（Actor-critic）算 法。但是基于策略的算法不适合反馈较多和变化程度较大的环境；AC 算法参数较多，训练 时间较长，模型较为复杂。在本文中，我们采用基于值函数的算法中一种常用的算法 ——-learning 算法来解决云任务调度问题。 190 3.1 动态优先级设计 在云计算中，不断到达的任务会有不同的长度、不同的截止时间以及不同的等待时间， 为了有效避免强化学习训练过程中初始动作选择的盲目性，提高收敛速度，本文在进行任务 调度之前，首先设计动态优先级对任务进行预处理，从而进一步缩短任务的等待时间，提高 资源利用率，实现高效的任务调度。 195 在本文中，我们主要依据以下三个参数来设计任务的动态优先级： 1) 任务长度：当任务的长度很短时，它可以快速执行，从而尽快为其他任务释放资源。 因此，在本文中任务的长度越短，任务的优先级应该越高； 2) 任务截止时间：任务截止时间是 SLA 中 QoS 的重要参数之一。任务截止时间越近， 任务执行的要求越紧迫，任务的优先级就应该越高； 200 3) 任务年龄：即任务的等待时间，为了避免任务等待时间过长，在本文中任务的等待 时间越长，任务的优先级应该越高。 由此，任务n的优先级 nrank 可由公式（13）计算： rank wl wd wa （13） 2 n 3 n n 1 n = + + 其中， =( iw i 1,2,3) 表示每项参数的权重，每项参数都有两个阈值α β和 (α β< )。根 205 据这两个阈值我们对以上参数的指标值分别进行等级设计，将每个参数分为 3 个等级。 nl表示任务的长度，当任务的长度小于α 时，优先级是 2；当任务的长度大于 β 小于 β l 时，优先级是 1。 l l时，优先级是 3；当任务的长度大于α l并且 nd 表示任务的截止时间，当任务的截止时间小于α d时，优先级是 3；当任务的截止时 间大于α d并且小于 β d 时，优先级是 2；当任务的截止时间大于 β d 时，优先级是 1。 210 na 表示任务的年龄,当任务的等待时间大于 β a 时，优先级是 3；当任务的等待时间大于 a 时，优先级是 2；当任务的等待时间小于α α a并且小于 β 3.2 基于强化学习的任务调度 强化学习以马尔可夫决策过程(Markov decision process, MDP)为基础。因此，采用强化学习 求解任务调度问题的关键就在于如何将调度问题建模为 MDP 模型。通常，一个 MDP 模型 表示如（14）所示： a时，优先级是 1。 215 - 7 -
    t t + 1 ), ), ( , r s a t , , ( , , 中国科技论文在线 http://www.paper.edu.cn { S A P s a s t 其中 S 为状态空间，A 为动作空间， P s a s 为系统处于状态 ts 时，执行决策动作 ta ( , , rs a 为奖惩函数，即在状态 ts 下执行动作 ta获 Q s a 为值函数。基于此，本文给出云任务调度问题中状态空间，动作 +1 后转移到下一状态 +1ts 的状态转移概率， ( , ) 得的立即回报， ( , ) 空间、奖惩函数和 Q 值函数的设计如下： S a A （14） Qs a s s t t ( , ), , + ∈ t t t t ∈ t t } , ) t t 1 t t t 状态空间（S）：一个状态可以定义为每个虚拟机执行任务的情况，可以用一个向量表 ts 表示第一个虚拟机目前被一个任务占用，第二个虚拟机空闲， 示。例如： = (1,0,...,1) 最后一个虚拟机被一个任务占用。 动作空间（A）：对于第 n 个任务请求，我们将其定义为动作空间(0 /1)n 任务请求是否被提供给第 m 个虚拟机执行。 例如， = (0,1,0,...,0) 个任务请求被分配给第 2 个虚拟机。 奖惩函数（r）：被用来反映正确的运行状态和任务的调度效率。目前，能耗是任务调度效 率一个重要的衡量标准。已有的研究表明，能耗与每个计算节点的资源利用率有很大关系[22]。 当计算节点处在空闲状态，或者其资源利用率比较低时，仍然存在 50%的能耗，但是，资 源利用率越高，能耗功率增长越慢。因此，本文从提高资源利用率、降低能耗的角度出发， 在截止时间的约束下，通过减少任务的等待时间来设计奖惩函数，具体由公式（15）表示如 下： m ，这意味着第 n 个 表示 t 时刻第 n tna = r j maximum , _ i j u i local     j =0  i local averw _  j   1 & （15）        subject to w SLA deadline < n 其中，i 为第 i 个物理机，第 i 个物理机的虚拟机数目由 _i local表示，j 为第 i 个物理机 上第 j 个虚拟机， ,iju 是第 i 个物理机上第 j 个虚拟机的利用率，由此可得第 i 个物理机上 所有虚拟机的平均利用率为 _ javerw 表示任务 n 在虚拟机 j 上的平均等待时间， ， i local u i j , j = 0 _ i local nw 是任务 n 的截止时间。对于一个给定的当前任务，如果当前任务被调度给一个虚拟机， 该虚拟机所在的物理机的平均利用率比原来的平均利用率高，该任务所被分配的虚拟机的等 待时间小于原来的等待时间，并且满足 SLA 或 QoS 约束，则调度程序将收到正面奖励，值 为 1；如果没有满足目标函数，且任务的响应时间违反 SLA 或 QoS 约束，将受到惩罚，值 为-1；否则为 0。 状态转换由状态转移概率P 和奖惩函数 r 来决定。在状态之间进行转换时，调度程序 A s 转换 会感知其当前状态 + ∈ 到下一个状态 + 1ts ，并收到来自环境的立即回报 tr。选择的动作不仅影响当前的奖惩值， 而且影响该环境下一时刻的状态及最终的奖惩值。 A来选择可用动作，选择动作 ∈ ( S 和动作 ∈ 1ts a t ta ) t 状态 s 执行动作 a 的 Q 值函数的定义如公式（16）所示： - 8 - 220 225 230 235 240 245
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料