高佳曼 徐欢乐

(1. 东莞理工学院 计算机科学与技术学院， 广东东莞 523808；2. 香港中文大学 计算机学院， 香港 999077)

虚拟化是构建云计算基础架构的重要技术之一[1]，虚拟化技术支持一台物理机上绑定多台虚拟机，每台虚拟机上应用程序的资源请求和负载更改类型均不相同，虚拟机之间独立运行且互不影响。多处理器系统在性能提高和节能计算领域的优异表现，成为云计算虚拟化领域最受关注的话题。早期多处理器系统多数是UMA架构的，但随着系统规模的不断增大，前端总线和内存控制器容易产生系统的性能瓶颈。在此背景下，NUMA架构应运而生且逐步被各大服务商采用。NUMA架构[2]中每个节点都由一个物理CPU和它所有的本地内存、I/O资源组成，具有远端内存访问特性，即每个节点不仅可以访问本地内存，还可以访问整个系统的所有其他内存，如图1所示。

针对计算密集型任务时，虚拟机需要占用较多的CPU和内存资源，但对网络带宽和IO的需求较少；针对IO密集型任务时，虚拟机主要的需求在于快速的IO响应，CPU常处于低载状态[3]。若NUMA架构上的虚拟机系统在运行过程中遇到“短时间内大量的读写/计算操作请求时”就会产生高并发现象，导致虚拟机之间对共享资源的竞争，从而造成系统性能的下降。

图1 NUMA架构

在多核虚拟化平台中，都是将片上的所有可共享资源作为一个整体，调度器对虚拟机进行公平的共享资源分配，虚拟机之间可以独立地运行自己的应用程序。实际系统运行过程中，服务器可能存在大量的最终用户，而应用程序具有不同的资源需求。由于NUMA体系结构具有可扩展的带宽性能特性，一直是主要的多处理器体系结构[4]。然而，NUMA体系结构却引入了额外的开销，如远程访问延迟和内存流量拥塞，严重影响应用程序的性能。当前VMM(Virtual Machine Monitor)虚拟机监控器的vCPU调度器通常采用负载均衡机制进行调度，但负载均衡机制不考虑应用程序的访存特征，只提高多核服务器下CPU资源的利用率，而造成其他资源的竞争与浪费[5]。因此，如何让虚拟机监控器根据虚拟机之间的资源占用情况和系统的负载特点合理的为虚拟机进行适当的调度，以减少共享资源竞争，从而提高系统的性能已经成为了在实现调度程序时所考虑的重要因素。

1 相关工作

随着云计算业务的不断扩大，用户需求日益增多，资源调度面临着更大的挑战。在多核CPU结构中，每个核心有其独立的L1、L2缓存和共用的L3缓存[6]。如果一个进程在核心间来回切换，各个核心的缓存命中率就会受到影响。相反如果不管如何调度，进程都始终可以在一个核心上执行，那么其数据的L1、L2 缓存的命中率可以显著提高。为了让一些进程始终在一个核心上执行，就需要进行一定的绑核操作。绑定以后，调度器就会让这个进程/线程只在所绑定的核上运行。

线程绑定的并行优化程度和服务器架构有密切关系，线程绑定的主要目的是提高线程访问cpu的cache(缓存)命中率，从而提高程序的并行性能。NUMA模式是一种并行分布式存储器访问方式，处理器可以同时访问多个不同的存储器地址，因此NUMA架构相比SMP架构上使用线程绑定的方式更能提高并行效率。在NUMA系统架构中，可以理解为虚拟机是某核心的一个进程，而虚拟机的vCPU是核心进程中的一种特殊的线程[7]。不同的vCPU是不同的线程，不同的线程是运行在不同的CPU上的。通过处理器的关联可以让虚拟机的vCPU/内存绑定到固定主机的物理核心上，也可以进行动态分配，绑核的vCPU/内存只在所绑定的核上运行，但并不代表该vCPU/内存独占这个核，其他vCPU/内存也可以在这个核上工作。而虚拟机的初始化放置就是虚拟CPU/内存与物理机核心的一种绑定关系，且虚拟机的初始化放置具有长期效应。通过设置合理的初始化虚拟机放置，可以有效地减少NUMA系统中的远端内存访问和资源竞争。

1.1 共享资源竞争

在多核NUMA架构服务器系统中，内存访问密集型线程对共享资源的竞争已经严重影响了系统的性能。Blagodurov等人[8]进行的相关研究指出，当时最先进的竞争管理算法(Compare And Swap，CAS)在NUMA系统架构中并不能有效地发挥作用，甚至与默认的操作系统调度程序相比，可能会降低性能。先前的研究也提出了一些方法来解决虚拟化系统中的NUMA开销，但仍然存在一些限制。例如，文献[9]通过采用vCPU的性能监控数据(PMU)信息进行采样，分析归纳vCPU特征并采取针对性调度的策略，可以减少系统中vCPU的远端内存访问和缓解共享资源竞争，提升访存密集型应用程序的性能。但是这种方法存在一定的误差，影响最终的调度决策效率。Blagodurov等人[10]提出了一种线程调度机制DINO，该机制可以根据当前内存亲和度和存在的竞争资源来调度线程或者迁移内存，使线程CPU和内存尽可能处在同一个节点上。通过对比不同绑定策略性能的差异，来分析不同因素造成的资源开销；但是这样的量化方式忽略了各因素之间的相互影响。文献[11]认为执行时间最小化并不能代表最大化数据局部性。他们认为将数据分配给远端的内存可能更有利于避免内存冲突，达到性能提升。因此，设计了一种新线程调度机制N-MASS，该机制充分地利用数据局部性特点，通过均衡LLC竞争，达到提高系统的整体性能目的。

Christina等人[12]提出了一个在线可扩展的调度器Paragon。它利用系统先前的关于应用程序的信息，使用协同过滤技术，通过识别与之前设计的应用程序的相似性，快速准确地对不同资源需求的工作进行分类。Paragon能够以最小化干扰和最大化服务器利用率的方式调度应用程序， 但比较依赖于先前的应用程序信息。此后，Shuang Chen等人[13]提出一个不需要应用的先验知识，能够利用细粒度的检测与资源划分动态地调整系统应用间的共享资源分配的控制器Parties。它由一个检测组件和一个资源分配组件组成，前者检测每个应用的尾延迟、内存容量、网络带宽使用量，后者使用检测结果来决定恰当的资源分配，并强制对他们隔离。它能够让多个延迟敏感的应用在不违反QoS前提下共享一个物理主机的资源管理器，大幅提升吞吐率。此外，Parties适用于动态变化的负载，并可利用资源替换性来快速实现收敛。

文献[14]针对最新的NUMA系统，通过实验说明影响系统性能的最主要因素是内存访问控制器和互连总线竞争，提出了一种解决算法，将多线程程序对内存的访问均匀地分配在所有的 NUMA 节点上，避免多个内存访问请求集中在单个NUMA节点上，能够减少系统竞争。文献[15]提出了一种在非一致性内存访问(NUMA)多socket多核平台上共定位并行应用的协同调度技术。该技术为并行应用程序分配核心资源，使内存控制器和CPU核心的利用率最大化。文献[16]提出了虚拟化环境下多核片上共享资源管理技术，主要包括LLC的划分控制和访存带宽控制，并在此基础上提出了二者的动态调节优化技术和虚拟机分组优化技术，在系统整体负载较大的情况下能够保证其响应时间，提高系统的实时性。文献[17-18]研究了资源竞争引起的NUMA架构性能下降问题，文献[18]虽然缓解了内存访问控制器的竞争，但是效果有限。

1.2 虚拟机的放置

虚拟机的放置[19]是指在如何根据虚拟机对各类资源的请求如CPU、内存、带宽等，将若干虚拟机合理放置到合适的物理机上，同时满足物理机的资源约束条件以及平台要求的高资源利用率和低能源消耗等目标。虚拟机放置问题近年来已逐渐成为研究的重点，现有的研究通常会考虑以下两种类型的约束类型[20]。一是虚拟机与物理机的映射关系，每个虚拟机只能放置到一台物理主机上，但每台物理机上可以有多个虚拟机；二是一台物理机上的所有虚拟机的资源需求量之和不能超过物理机的资源容量。

研究者一般根据目标的数量，使用不同的算法来解决虚拟机的放置问题。由于虚拟机放置问题也可以看作是一种特殊的装箱问题，启发式算法如首次适应下降算法(First Fit Decreasing，FFD)或最佳适应下降算法(Best Fit Decreasing，BFD)是求解装箱问题的常用算法[21]，但当主机数量极其庞大时，启发式算法不能在有效的时间内得到较好的放置方案。此外，元启发式算法和混合启发式算法通常用于解决虚拟机放置的多目标问题。例如，文献[22]针对最小化能源消耗和最大化资利用率两个目标，应用多目标蚁群算法来解决虚拟机放置问题。文献[23]用局部优化程序扩展了遗传算法，提高了原遗传算法的收敛性。LR(Logistic Regression，逻辑回归)算法[24]通过建立拟合模型预测曲线趋势，能够大幅度减少系统功耗。但以上两种算法在计算密集型任务虚拟化环境中，完成时间不可估量。虽然MGA(Micro-Genetic Algorithm，微遗传)算法[25]能够在增加服务商利润的同时降低系统能耗，但当该算法陷入局部最优时不能建立有效反馈。

在NUMA架构中，由于虚拟机的初始放置位置产生的资源竞争不可忽视。如果虚拟机初始位置放置不当，就会造成大量的远端内存访问，使得带宽性能会至少下降57%，而内存流量拥塞可能会将内存访问延迟增加到5倍。此外，由于虚拟化层引入的语义差距，运行在虚拟机内的应用程序对底层的NUMA特性并不了解。如果没有NUMA感知的虚拟机放置资源管理，就无法保证应用程序的性能。因此，在NUMA架构下如何获得更健壮的虚拟机放置方案也受到了云提供商越来越多的关注。

现代多核系统具有复杂的共享资源层次结构，不同的虚拟cpu与硬件的映射关系对系统性能影响有很大的差异。文献[26]对NUMA架构下虚拟机位置放置问题进行了充分的讨论：需要分配给容器的硬件资源决定了容器的性能以及消耗的能量。一般来说，资源如何分配受到两方面决策影响。其一，用户决定容器需要多少内核、内存和其他资源；其二，系统软件在启动容器时，决定如何将容器的虚拟核心映射到物理核心上。当所有虚拟核心集中到单个NUMA节点中时，它们会有更多的资源共享，一个容器的最佳性能位置很难预测。如果目标不仅是选择性能最好的位置，而且是在使用节点的数量和性能之间实现平衡，那么问题就会变得更加复杂。作者将虚拟机放置问题转化为调度问题，单调度问题即调度只有一种硬件资源，或一组绑定的会影响vCPU放置性能的硬件资源。多调度问题即多种资源，转化为调度问题的主要目的是在给定vCPU放置时提供一个数值分数，该分数表示特定资源的静态利用率，这意味着它只依赖于vCPU的位置，而不是动态的工作负载。分数越高，则表示给定的虚拟机放置效果越好。

基于上述分析，将虚拟机放置问题转化为调度问题，提出了一个虚拟机放置的模型，并设计了一种基于强化学习的调度算法。该方法根据虚拟机的任务类型进行资源调度，将虚拟机的放置过程描述为随机采样的过程，并根据系统的运行状态引入近端策略优化[27](Proximal Policy Optimization，PPO)和交叉熵[28](Cross Entropy，CE)强化学习机制。智能体通过与虚拟机资源环境的不断交互来分析出虚拟机与物理机之间的绑定关系对系统性能的影响，进而选择出对系统性能影响最小的解决方案，达到优化目的。

2 问题描述

根据文献[29]，面向NUMA架构的虚拟化系统主要包括以下四个方面的资源竞争：一是内存的竞争，如果两个节点同时访问相同的数据存储器，那么一个节点必须等到另一个节点完成访问才能进行访问，这将降低性能；二是当多个vCPU共享一个缓存空间时，由于缓存的大小有限，容易产生一个vCPU缓存的数据被另外一个vCPU的数据替代的情况，称为缓存竞争；三是所有vCPU对LLC的竞争，且LLC竞争是不可避免的；四是对互联总线的竞争，当多个核心需要访问其他节点上的内存时，就会造成多个核心对互联总线的竞争。当竞争已经存在，数据访问时间将会达到正常数据访问的5倍以上[30]。

2.1 数学模型

虚拟机的放置是计算机领域的一个关键课题，目前研究者对负载均衡、资源利用率和能耗等方面的优化算法[31-33]都有所研究。离线放置表示在虚拟机资源请求量及物理服务器资源均确定的情况下，考虑不同优化目标的虚拟机放置。文中主要考虑离线放置，问题可以表示为如图2，用数学语言描述：将m个具有不同资源请求的虚拟机分配到n个物理机中合适的物理节点上[34]，以实现包括最小化能源消耗和最大化资源利用率、负载平衡和鲁棒性的目标。每台物理计算机都提供多种类型的资源，如CPU、内存和网络带宽。物理机、虚拟机及其之间的绑定关系，以及放置方案可以描述如图2。

图2 虚拟机放置问题示意图

a)物理机

在NUMA系统中，物理机可以描述为NUMA系统上的某个节点，每个节点上都有自己的内部CPU、总线、内存和内存控制器等。假设本系统中节点集合表示为，其中N表示可供选择的节点数量。

b)虚拟机

虚拟机表示为集合VM={VM1,VM2,…,VMM}，其中M为需要放置的虚拟机的个数。每个虚拟机的资源需求量不尽相同，根据任务类型，又分为IO密集型、CPU密集型等。

c)虚拟机与物理机的绑定关系

物理机与虚拟机之间的绑定关系表示为一个N×M的矩阵A。

矩阵A为0-1矩阵，对于每一个虚拟机VMj都有∑i=1naij=1，即一台虚拟机只能分配到一个物理节点上。若aij=1 则表示第j台虚拟机要绑定到第i个物理节点上。

d)虚拟机放置方案表示

同样地，其他虚拟机在NUMA服务器上的放置概率由其对应的其他N×M个参数决定。各虚拟机依次选择放置节点位置，当M个虚拟机全部选择放置完后，得到一次放置方案，将其表示为d={Choose1,Choose2,…,Choosem,…,ChooseM}，Choosem值为{0，1，…，N-1}其中一个，它表示当前虚拟机m选择放置NUMA架构的哪个节点操作。举例说明，如d={2,4,…,2}，则表示第一台和最后一台虚拟机选择放置到节点2，第二台虚拟机选择放置到节点4，以此类推。

2.2 问题目标

在面向NUMA架构的虚拟化系统中，若初始的虚拟机放置不当，容易造成各虚拟机之间的资源竞争，而这种资源竞争也将导致虚拟机的不断迁移，最终造成系统的整体性能下降。在本论文中，我们的最终目标是减少虚拟化的NUMA系统的资源竞争，保证系统性能提高。

IPS(Instruction Per Second，处理器每秒平均完成的指令条数)是衡量CPU性能的重要指标之一，IPS越大，则反映出CPU的性能越好[35]。因此我们将测试得到的IPS作为虚拟机放置算法的优化目标，按照给定放置策略方案di训练模型，将系统执行该策略di时对应的IPS用T(d)表示。T(d)越大，则侧面反映当前系统的资源竞争越小，也就表示当前的放置策略越好。此类设备放置问题用数学等式可以表述为：

其中A表示所有可能摆放位置的集合。

3 算法设计

虚拟机资源调度是一个复杂的NP难问题，在进行算法设计时如果使用太多参数，则会给系统带来大量的计算开销，尤其是AC(Actor-Critic)算法[36]。AC模型包含两个神经网络，都是在连续状态中更新参数，参数更新前后存在着一定的关联性，致使神经网络不能全局看待问题，甚至学不到好结果。由于云计算环境负载波动性和资源的不确定性，而基于策略的算法需要同种策略进行迭代训练，所以这种方法不适宜云资源调度。因为当步长过大时，学出来的 Policy 震动幅度较大，会导致算法不能收敛；当步长太小时，完成训练的时间又超出了可等待的范围。PPO 根据新旧策略的比值来限制新策略的更新幅度，避免了发生新策略突然严重偏离最优解或者陷入局部最优的问题，能够达到不断更新策略的目的。交叉熵优化算法可以非常快速地得到最优化结果，缩短整体求解时间。因此，采用了PPO和交叉熵优点结合的算法来求解模型。

Post算法的框架如图3所示，包括采集样本算法、强化学习模块等及部分。采集样本算法：根据概率参数矩阵选择放置策略；强化学习模块：利用近端策略优化算法(PPO)和交叉熵最小化算法交替地不断更新采集样本算法的参数矩阵。

3.1 采集样本

假设对于第m台虚拟机的放置，使用参数表示选择第j个设备节点的概率。虚拟机与节点之间的选择映射关系表示为一个D×M的概率矩阵B。

(1)

首先使用softmax函数对所有设备的参数进行规范化，以获得放置的概率分布。为第m台虚拟机选择放置到第j个设备节点的概率由下式给出：

(2)

3.2 强化学习模块

强化学习[37]是机器学习领域的主要算法之一，智能体(Agent)的目的就是争取在与环境的交互中获得尽可能多的累计奖励。虚拟机放置问题是通过使用调度模块不断地调整虚拟机与物理节点的绑定关系，来达到最佳的放置策略。强化学习是求解优化问题的有效工具，近年来强化学习在处理问题的能力和规模上面都得到了显著的提升。对于自适应调度而言，强化学习的随机性质与随机虚拟机绑定的目标是一致的，因此强化学习这种动态规划的思想比较适合应用到虚拟机的放置算法中[38]。

在文中，采用近端策略优化算法和交叉熵优化算法相结合的强化学习优化算法。强化学习过程中，模型概率矩阵采用策略梯度上升法不断更新参数，使得放置策略对应的T(d)不断增加。假设每台虚拟机放置到哪个设备节点是相互独立的，则虚拟机放置位置分布即联合分布f(du)，可以表示为：

(3)

为了获得联合分布概率最接近1的放置分布，从随机生成的参数值开始迭代更新参数，直到最终收敛。最初使用均值参数u(0)，通过不断迭代产生的目标分布(参数为(u(1),u(2),…)逐渐改善联合分布。第t次迭代的目标分布定义为以下条件分布：

f(du(t+1))=f(du(t),T(d)≥γt)，

(4)

其中γt是常数，且γ0≤γ1≤γ2≤…≤γ*。

根据条件概率的定义，等式(4)可以转化为式(5)：

(5)

其中I{·}是指标函数，当条件成立时等于1，否则等于0。等式(5)表示f(du(t))中好位置的概率归一化。通过归一化，将旧分布f(du(t))更新为目标分布f(du(t+1))。随着t在迭代中不断增大，从样本数据集中选择出好放置策略的可能性不断提高。根据这样的直觉，可以通过最小化旧分布和目标分布之间的随机距离(KL-散度)来调整参数u(t)，最小化KL散度表示为等式(6)。

f(du(t))logf(du(t))，

(6)

(7)

(8)

其中，目标分布f(du(t+1))由等式(5)给出。等式(6)的第一项关于u(t)是常数，因此等式(6)可以等效为等式(7)，进一步将其转化为等价的期望形式等式(8)。

1)交叉熵优化算法

交叉熵方法主要是用来衡量两个概率分布之间的差异性信息，用来优化和重要性采样，交叉熵并不对环境进行任何的建模，只需要简单地告诉智能体每步应该采取的策略。一般的损失函数在进行梯度下降计算时可能会由于梯度的弥散出现学习率下降的问题，而交叉熵作为损失函数可以避免这种影响。为了解决上述等式(8)的最小化问题，我们将期望值替换为N个样本的平均值，并将期望值最大化样本平均值表示如式(9)。

(9)

其中的d(n)是第n个采样样本。在N个采样样本中，满足条件的子集由常数γt确定。每次选取前ρ*N个优秀的放置位置(ρ∈(0，1))，将γt设置为所有采样样本中第ρ*N个最大的值，使用交叉熵方法求解式(9)，式(9)是一个凸优化问题[39]，可以采用基于梯度的方法求解，以实现全局最优解。此外，对于softmax分布，文献[40]针对问题(9)导出了以下封闭解。

(10)

其中p表示好的位置，P=ρN是好的位置的总数。

在有效的展示位置中，重新计算分配给第m个设备的第j个节点的概率，并将其作为给定新参数的放置概率。在每次交叉熵最小化之后，选择某种放置的概率可能为零，这不利于探索更多潜在的位置。为了更好的探索，将分布与均匀分布混合在一起，以epsilon(e.g. 0.1)的概率从所有可用设备中均匀选择一个设备，而以1-epsilon(e.g. 0.9)的概率根据交叉熵最小化后的概率分布选择设备。即如式(11)。

f(du(t+1))=(1-epsilon)f(du(t+1))+

(11)

其中C为与概率矩阵B同形状的全1矩阵。随着智能体的不断训练，T(d)的值会逐渐上升，最终达到满意为止。

2)近端策略优化算法

在强化学习中，交叉熵最小化是一种批处理学习算法，它在放置了大量(N个，可能是数百个)放置样本后更新参数，这种批处理学习算法缺乏增量参数的改进。PPO算法是一种基于梯度优化的、面向连续或离散动作空间的在线决策深度强化学习算法，在计算梯度时确保与旧策略有相对较小的偏差。因此，整合了交叉熵最小化和近端策略优化算法的优点，每次增加少量K个样本，以实现算法的学习加速。因此，第t次迭代的近端策略优化的目标可表示如式(12)。

(12)

其中b是所有采样样本运行指令数的平均值，而DKL(·) 是新旧分布之间的KL散度。T(d(n)-b)表示奖励信号，如果其训练时间大于平均值，则为正，否则为负。Post算法在算法1中总结。

算法 1：交叉熵和近端策略优化结合算法(Post算法)

输入：样本和概率矩阵。

输出：更新后的概率矩阵。

a) 生成全1的概率矩阵并进行softmax为u(0)；初始化 t=0

b) for n=1,2,…,L do

c) 放置样本d(n)～f(du(t))；

d) 根据样d(n)本搜索对应的IPS值并记录；

e) if n%K == 0 and n%N ≠ 0 then

f) 采用近端策略优化算法(即等式11)更新概率矩阵；

g) 对概率矩阵进行softmax归一化；

h) t=t+1

i) end if

j) if n%N == 0 then

k) 采用交叉熵最小化使用等式(10)实现优化；

l) t=t+1

n) end if

o) end for

每次从样本中连续采样放置策略并评估其对应IPS。对于每K个采样位置，采用近端策略优化执行随机梯度上升步骤，从而逐步改善策略。对于每N个采样位置(N比K大几倍或几十倍)，采用等式(10)更新参数来实现整个正向的策略改进。

4 仿真实验与分析

4.1 实验配置

在本论文中，以6台虚拟机、3个节点的NUMA服务器场景为例。为了验证算法的有效性，在实验之前，采用不同类别虚拟机和物理机配置，对虚拟机放置在NUMA节点上对应的IPS进行测试，并进行记录，制作成虚拟机放置任务的数据集。

在基于强化学习的虚拟机放置算法测试过程中，相关参数设置为：学习率epsilon为0.1，K设置为10，N设置为20，参数更新100次即L=100。实验性能评价指标如下：1)迭代求解的平均值和方差；2)算法的准确率；3)算法迭代时间及CPU与内存利用率等。对于上述平均值和准确率性能指标，实验结果的数值越大，表明基于NUMA架构的数据中心的系统整体性能越好。相反，迭代时间及CPU与内存利用率及方差的数值越小越好。

4.2 实验结果分析

在相同配置下对各算法进行平均采样值分析、采样值方差分析、准确率分析以及CPU和内存利用率以及运行时间进行综合分析，最后得到算法对虚拟机放置样本集的实验结果。首先对Post算法进行算法的迭代求解，测试结果如图4所示。

图4 IPS随迭代变化

从图4可知，更新5次左右的训练迭代后，虚拟机放置对应策略处理指令数的数量明显增加，在10次迭代后已经达到了比较好的效果。随着迭代次数的增加，处理指令数量虽有波动但逐渐收敛，说明提出的模型对一定资源约束条件下的虚拟机放置问题能够有比较好的训练结果。

1)采样值分析。将Post算法与交叉熵算法(CE)、近端策略优化算法(PPO)和策略梯度算法(PG)在采样平均值和采样值方差上进行比较。在模拟实验中，对于每一个放置策略均对应一个性能指标。由于第一步涉及初始放置，因此采用十个样本的平均性能指标来衡量算法对性能的影响。在对样本集进行了十次采样训练之后得到图5和图6所示的对比图。

图5 随迭代变化的平均采样值

图6 十组采样数据方差

基于NUMA系统的数据中心中，根据图5采样平均值的对比结果可以看出Post在每次训练均可比其他三种算法取得较好的成绩。通过图6可以看出，仅使用交叉熵算法或仅使用PPO算法的方差较大，Post和策略梯度算法方差相近且较小。综合图5和图6的结果，Post算法相比其他算法表现出较好的提升系统性能的能力且具有相对稳定性。

2)准确率分析。经过重复多次测试4种算法均可在相对较短的时间内得到最优解。为了验证算法准确率，将算法迭代前5次能求得的最优解进行了统计对比，结果如图7所示。

图7 前五次迭代各算法能求得的最优解

实验结果表明，在实验场景下，其他三种算法虽然能在5次迭代内找到虚拟机放置的最佳位置，但并不是每次都能在5次迭代内找到最优解，而Post算法十次测试均能在5次迭代内找到最优解，本算法准确率较高。为了进一步加强算法测试的准确性，对每个算法都进行了100次测试，实验结果如表1所示。

表1 准确率

其中本文算法Post有91次都能在5次迭代中找到最佳结果，比其他三种算法准确率提升近40%。

3)综合分析。由于算法时间复杂度和空间复杂度的不同，不同的算法迭代时间往往不同，对比了四种算法在同种配置下的迭代运行时间，得到如图8所示结果。

图8 随迭代所需时间变化

根据图8实验结果可知，在仅使用PPO算法求解时，所需的时间开销最大。Post算法时结合了PPO算法和交叉熵算法的优点，在时间开销方面得到了较大的提升。CE算法和PG算法随着迭代次数的增加运行时间呈现线性增长。在本次实验中，只对样本集进行了100次迭代，根据图8所示各算法的运行规律，可以预测当样本量较大时，Post算法所需时间最少。在算法迭代过程中，我们同时获取了各算法每次迭代过程的内存和CPU使用率，结果如表2所示。

表2 算法内存和CPU使用率 %

从表2中可知，在系统配置相同情况下，各算法CPU和内存利用率相差不大，则说明Post算法在保证算法准确率，节约时间的同时能够保证算法不对系统产生其他干扰。

综合以上所有实验结果，认为本文算法能提升现有的NUMA虚拟机系统的性能，可为现有互联网基础服务提供更好的技术支撑。

5 结语

虚拟化技术作为云计算的基础，对云计算的发展有着重要的作用，优化虚拟机的放置策略的性能的研究对现代云计算行业具有重要的意义。文中将设备放置表示为高维的softmax概率分布，将寻找最佳位置的虚拟机放置问题转化为查找最大值的问题。以强化学习为基础，提出了一种算法来解决NUMA架构下虚拟机放置的资源竞争问题，在理论上保证了最佳的效率。主要包括以下两个方面的贡献：一是将NUMA架构下的虚拟机之间的资源竞争问题进行建模；二是将交叉熵和近端策略优化算法强化学习算法融合起来来解决虚拟机放置问题。然而本算法没有对虚拟机的迁移导致的性能下降做出优化，进一步的研究工作是改进初始放置后由于虚拟机迁移而产生的竞争问题。