一、引言
1.1 编写目的
该软件需求说明书的编制是为了使用户和软件开发者双方对该软件的初始规定有一个共同的理解， 使之成为整个开发工作的基础。
1.2 定义
服务器
服务器类型：具有多种类型的服务器，每种服务器具有多个参数，分别为：服务器类型、规格（cpu核数、内存大小）、购买时的硬件成本、运行时每天能耗成本。如下图:
MUMA架构：可以理解为每台服务器都具有两个规格（cpu核数、内存大小）可以不同的节点A和B，当虚拟机双节点部署时，两个节点同时为虚拟机提供相同规格的资源
服务器成本：每台服务器的使用成本由两部分构成：1.一次性支出的硬件成本，在购买时支出；2.能耗成本，服务器运行一天的能耗，不开机不需要支出
虚拟机：
虚拟机类型：向用户提供可以购买的多种类型的虚拟机，每种虚拟机具有多个参数，分别为：虚拟机型号、规格（cpu核数、内存大小）、部署方式（单\双节点部署），如下图:
单\双节点部署方式：单节点部署是将虚拟机的全部资源都由服务器中的一个节点提供，其虚拟机规格可能为奇数；双节点部署是虚拟机的全部资源由一台服务器的两个节点各占一半同时提供，其虚拟机规格一定位偶数。
请求类型：用户有两种请求类型。创建请求为用户请求创建虚拟机，数据格式为：（add、虚拟机型号、虚拟机ID）；删除请求为删除之前创建好的虚拟机，数据格式为：（del、虚拟机ID）
部分如下图：
二、任务概述
2.1 目标
该程序开发主要的意图是：目前云资源的使用、规划分配和资源调度的调度有着非常大的优化空间，通过对着三个方面具体的优化使运营成本有着大幅度的降低。
2.2 假定和约束
- 可采购的服务器种类数量N（第一行）：1~100的正整数
- 服务器核数内存：大小不超过10
- 硬件购买成本：不超过500000
- 每日能耗成本：不超过5000
- 服务器型号：长度不超过20，由大小写字母及数字组成
- 可购买的虚拟机种类数量M：1~1000的正整数
- 虚拟机双节点部署时，服务器两个节点必须个提供一半的资源
- 虚拟机型号：长度不超过20，由大小写字母、数字和’.’组成
- 请求数列总天数T：1~1000的正整数
- 创建请求总数：不超过500000
- 虚拟机ID：范围不超过带符号的32位整数表示的范围且唯一的正整数
三、需求规定
3.1 时间特性要求
对于每组测试数据，程序必须在90秒内输出合法的解，若超时则无成绩，多组数据有一组无成绩则整体无成绩 3.2 输入输出要求
合法性判定时，严格按照输入和输出的请求序列顺序进行模拟！！
对于每一天的操作，会先按顺序执行选手输出的购买操作，然后按顺序执行选手输出的迁移操作，最后按顺序执行当天的创造和删除操作!!
输入中若有当天创建当天删除的虚拟机，对于这类请求依然按顺序正常处理
输入及输入标准
输出及输出标准
日志信息必须输出到标准错误？？
四、难点及可优化点分析
4.1 难点分析
- 难点一： 减少购买服务器数量、提高总体服务器资源利用率
- 难点二： 如何高效的找到规格最匹配的服务器或服务器节点，怎么才算最匹配，标准是什么
- 难点三：
4.2 可优化点及可能优化方案
- 不同设备总核心数量与内存数量比例不同。如何挑选
可能优化思路：因为内存及核数与购买成本与每日能耗成本接近正相关，当遇到请求创建一个虚拟机时，可以进行预迁移操作，即尝试选取与虚拟机所需要的规格相近的服务器或服务器节点，就能尽可能的减少总成本，当没有与其匹配的服务器时在购买
- 不同的虚拟机类型的安置方式不同，单例或双例。如何计算分配
可能的优化思路：单节点虚拟机尽可能的部署在已经购买的服务器上，则在没有成本变化的基础上完成了一次需求；双节点则有两种思路，一种是在已经购买的虚拟机中寻找空闲的且资源规格更相近的，一种思路是直接购买与该虚拟机资源规格最相近且购买成本最低的
- 不同硬件设备的价格不一样。需要根据性能和维护费来对比选择，用什么方法选
想法:因为规格与硬件成本与能耗约成正相关，且每个服务器的硬件成本大多数在1×10^5 量级，而每日的能耗成本在150左右，且最大运行天数为1000，即每个服务器最大能耗成本约为1.5×10^5，则可以主要考虑服务器购买的数量的减少上
每天需要创建的虚拟机种类可能是非常多的。会涉及到如何分配和购买设备的问题
思路：
进行虚拟机迁移时，由于数量有限，如何选取最佳的虚拟机进行迁移
思路：利用虚拟机在服务器上的资源利用率来顺序从低到高进行迁移，所以可能进行多次迁移
- 补充添加。。。
4.3 相关算法
- 装箱问题( NP-hard 问题)
- 首次适应算法（First Fit,FF）
- 最佳适应算法（Best Fit,BF）
- 降序首次、最佳适应算法（FFD，BFD）
- 轮询算法（Round-Robin,RR）
即所有的虚拟机到达时会从上一个虚拟机被放置的物理机的下一台机器开始检测，判断这台机器能否满足他的资源要求，如果可以就放置在该机器，不可以就继续检测下一台，知道放置成功为止。
- 蚁群算法
具体最优解构建是这样完成的，在蚁群算法的每次循环中，每只蚂蚁根据概率转移函数在所有等待被放置的虚拟机进行搜索，每只蚂蚁完成一次循环时会的到一个局部最优解，对于第一只完成循环的蚂蚁，它将这局部最优解保存为全局最优解，而后面的每只蚂蚁都将自己得到的局部最优解与全局最优解进行比较如果她的解更好，最会用他的解来替代全局最优解，如此循环下去，最终得到最好的全局最优解
- 遗传算法
五、设计流程图
蚁群算法下最优解构建流程图：
六、参考资料
- 云平台下虚拟机调度研究与实现_郑艳琪
- 云数据中心中虚拟机初始化放置策略的优化算法及其应用研究_任田田
- 云计算资源调度研究综述_林伟伟
- 一种基于动态重配置虚拟资源的云计算资源调度方法_林伟伟
- 云计算环境下虚拟资源调度策略的研究_黄青