虚拟化资源管理阅读笔记（一）

Efficient Resource Management for Virtual Machine Allocation in Cloud Data Centers 笔记

一种新的资源管理系统模型，并提出一种在云数据中心中进行有效的虚拟机分配的方法。从技术上讲，虚拟机分配问题正式化为装箱问题，而Best Fit算法（BF）被部署为云数据中心中的一种有效资源管理。系统模型将有助于节省未充分利用的物理服务器，并在将虚拟机映射到数据中心中的服务器时有效地做出响应。

二进制搜索方法

二分查找算法基本思想 二分查找算法的前置条件是,一个已经排序好的序列(在本篇文章中为了说明问题的方便,假设这个序列是升序排列的),这样在查找所要查找的元素时,首先与序列中间的元素进行比较,如果大于这个元素,就在当前序列的后半部分继续查找,如果小于这个元素,就在当前序列的前半部分继续查找,直到找到相同的元素,或者所查找的序列范围为空为止.

Bin packing（装箱问题）

Problem：给定n件物品和k个箱子，每一个箱子的容量为1，每一件物品的大小w为(0,1)，要求使用最少数目的箱子来装上全部的物品。

这个问题是NPC问题，只有approximation（近似）算法。

一个2-approximation的多项式算法。

算法：

先打开一个箱子，然后逐一放入物品，如果当前的物品没有一个已打开的箱子可以放入，那么就新打开一个箱子来装它。

算法是2-approximation的，证明：

假设最优解需要B*个箱子，上述算法需要B个。那么，考虑使用上述算法的完成情况，至少会有B-1个箱子是半满的（箱子使用了多余一半的容量），这是因为，如果有两个箱子使用量不足一半，那么根据算法，后一个箱子的物品要被放入第一个箱子，因此上述结论正确。那么全部物品的总量S>(B-1)*0.5，即，B-1<2*S，又考虑到B是整数，则B-1<=B，因此有B<=2*S，而S<=B*，所以B<=2*B，因此是2-approximation算法。

原文链接：https://blog.csdn.net/u010900754/java/article/details/53894023

P问题、NP问题、NPC问题、NP-hard问题详解

VM放置与VM选择问题。