虚拟化集群系统资源非合作博弈分配策略的研究

刘轶彤

天津职业大学，中国·天津 300410

虚拟化；非合作博弈；效用最优；资源分配策略

1 概述

动漫三维作品的后期渲染、视频作品的合成加工、交互作品中虚拟现实效果的实时呈现，都需要具有大规模运算能力的设备对项目文件提供输出保障。随着学院对设备投入力度的增加，已建立具有高处理性能的集群系统。集群系统由多台相同配置的计算机工作站组成，相互之间利用光纤交换机进行数据传递。为用户项目文件的处理，提供高效、统一的处理器、内存和存储资源。在集群系统中通过资源管理软件对项目文件进行资源分配。

随着虚拟化技术的发展，将虚拟化软件安装在集群系统中，建立同时对多个用户提供处理服务的虚拟化集群系统。对资源进行虚拟化，按照相应的类别形成统一的处理器资源集合、内存集合及存储集合，各类资源被划分成相应资源池。在实际任务处理中，一般将系统资源等价于集群系统中处理项目文件所需的处理器资源，将内存和存储资源视为足够充足。虚拟化集群系统主要解决如何充分、合理利用处理器资源的问题，需要对原来集群系统中任务分配策略进行调整，使任务分发软件有效地分配和管理处理器资源，实现系统最大限度的资源利用。

论文考虑到实际的系统资源分配中存在的经济因素，引入博弈理论中非合作模型，结合任务文件对处理器资源使用的费用预算和完成任务最迟截止时间的条件约束，对虚拟化集群系统中资源分配策略进行分析，构建出单位时间内使用相应处理器资源产生费用的函数关系，证明在分配策略下存在纳什均衡解的条件。利用非合作博弈策略求得纳什平衡，从而使资源分配得到最优解。

2 虚拟化集群系统中资源分配经济模型的构建

在虚拟化集群系统中可以通过资源管理软件实时地将集群处理器资源进行整合，按照实际的需要和支付，分配相应的资源，使集群系统的任务管理具有灵活、公平、高效的特点。在合理分配处理资源的同时，需要考虑经济上的因素，按照用户的支付费用，在当前系统处理器资源池中得到相应比例的资源量。根据虚拟化集群系统的工作原理，资源池中资源不是指定一台或几台上的物理资源，而是虚拟化集群系统的处理器资源可应用量，进行实时地分配给不同需求的项目文件[1]。设定提交项目文件的用户数为N={1，2...i...n}，集群系统中物理工作站数M={1，2...j...m}，用户提交的项目任务数为T={1，2...k...t}。Pkj是任务K 在机器J 上所占用的资源比例，按照单位时间处理器资源的使用价格Mk，乘以所需的处理器资源数量Ck和执行时间Tkj，得到项目文件使用资源产生的费用，确保实际支付价格不能大于整个文件的初始预算。如资源单位时间使用价格、项目文件的处理预算，以及项目文件的最迟截止时间作为参数和约束条件，构成的模型如下：

3 虚拟化集群系统资源分配的非合作博弈

3.1 博弈理论的定义及模型

处理器资源作为虚拟化集群系统中最核心的部分，在处理多个用户提交执行任务文件的问题时，如何对资源池中资源的分配采用合理的策略，保证整个系统能够实时有序地进行，提高系统的性能。虚拟化集群系统在设备的购买、软件使用以及人员维护，都会产生经济上的费用，因此对于提交任务的用户在使用系统资源时需要缴纳一定的费用。系统中资源分配问题与社会经济活动有一定的相似性，可以引用经济学中博弈理论，解决对多个用户申请虚拟化集群系统处理资源的分配策略，从而使整个资源池中的分配对每个用户达到最优[2]。

博弈论可以对多个相互独立可自主选择策略的用户，在策略空间的选择问题上，用户相互牵连和制约，提供一个合适的分析框架。博弈的主体至少有3 个要素：参与者，策略空间、效用函数。博弈论的形式表达为：G={N,Si(N),Ui(⋅)}。以用户对资源的出价集合表示为策略空间，Si为用户i 的策略集合，每个用户的效用以效用函数集合表示{Ui(.)}，Ui表示用户i 的效用函数。博弈中参与者i 的效用表示为Ui(s)，对于Si最优策略称为Si*为用户i 达到纳什均衡的出价策略。以s 表示博弈中所有用户的策略选择，si是用户i 的策略表示，s-i是除用户i 以外用户的策略选择。博弈分为合作博弈和非合作博弈。虚拟化集群系统中每个用户体较大项目任务文件具有并行处理的特性，在资源的利用和分配过程中，每个用户没有形成一种合作的模式，只是根据相互的出价的抉择，在可支付的费用条件下，处理时间最小值作为资源分配结果的原则下，进行策略选择问题，得到效用的最优策略，即为建立一种非合作博弈模型。每个用户进行策略的不断优化进行调整，以到达自身的最优策略选择，在这种策略下是每个用户都达到一种最优的状态的均衡模型，形成非合作博弈模型中的最优策略组合，任何其他的策略选择都会小于均衡下的效用最大值，即为在资源分配中形成一种纳什均衡，即为每个用户最优值的策略组合[3]。

3.2 非合作博弈模型中纳什均衡的存在条件

论文引入博弈理论，首先要根据虚拟化集群系统的资源分配原则，对任务处理中使用的参数进行表示。用户i 完成任务t 所获得系统的CPU 的资源处理量、执行任务的时间及用户i 的使用系统实际支付费用：

在非合作博弈模型中纳什均衡的存在条件为：（1）策略空间Si=(i=1，2，...，N)是欧式空间中一个非空的、紧的凸集。（2）效用函数Ui(s)是连续的且对Si是拟凹的。

用户的出价策略空间Si为单个点集，显然是欧氏空间上一个非空的紧致凸集，满足条件（1）。效用模型形式化为费用约束下，解决任务处理的时间尽量最小化的优化问题，对于在最优化的问题应该转化为。已知效用函数Ui(s) 在Si上满足连续性。关于凹性，

在得到的二阶导数结果公式中，任务大小qit，以及博弈用户的出价sit和，以及占用系统资源的数量，三个参数均为正数，因此二阶导数，已知效用函数Ui(s) 在策略Si上是凹函数。满足效用最优化模型存在非合作博弈纳什均衡解的条件[4]。

3.3 效用策略选择的最优解

再利用系统资源总体预算的约束条件下利用拉格朗日方法去求解最值问题

通过对L(sit)关于λ进行一阶导数运算，比将其值为0

可得：

si1为用户i 对第一个任务使用集群资源的最优出价，其他用户同时也遵循这个出价的策略函数，用户i 通过最优出价策略达到效用最优[5]。

4 实验及结果分析

对虚拟化集群系统的任务管理软件进行测试，通过软件分析在应用非合作博弈理论的分配策略后，统计用户的项目预算和任务文件的使用的资源价格以及执行时间的相互关系。上述推导出理论应用在拥有48 台服务器，每台内置8 核处理器组成的虚拟化集群系统。参数a表示系统处理器的处理能力，变化范围为[96MIPS，384MIPS]，用户的预算为b，变化范围为[50，150]，设定同时参与提交任务数为n，变化范围为[2，6]。

表1根据使用系统处理器的处理能力a 及提交任务数n，产生任务对资源出价的变化情况。随着用户数量的增加，通过对出价策略的考虑，影响任务执行时间的变化情况。

表1 系统处理器分配能力和出价的变化情况

在表2中用户的预算b 和提交任务数a 的变化时，任务文件的执行时间受到影响。预算的增加会加快任务的执行时间，随着提交任务的增加，获得的相对资源会减少，增加任务的执行时间。

表2 在用户的预算和执行时间的变化情况

5 结语

论文通过对虚拟化集群系统结合非合作博弈理论，从而寻求效用最大化的处理资源的分配策略，该策略可以将用户的预算和在博弈中用户间的出价策略建立相互联系。根据用户自身的预算，进行对系统资源的合理分配需求。通过用户项目文件的“预算-出价-时间”关系达到纳什均衡，是分配策略达到效用最大化，证明了虚拟化集群系统中应用非合作博弈资源分配策略的可行性，具有一定的推广和应用价值。