专栏首页认证协议的形式化分析虚拟化资源管理阅读笔记(一)
原创

虚拟化资源管理阅读笔记(一)

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选择问题。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基础知识补充1:密钥交换/协商机制

    密钥协商这一概念也得以提出。一方面它能为参与者提供身份认证,另一方面,也能与参与者协商并共享会话密钥。

    春风大魔王
  • 形式化分析工具(六):HLPSL Tutorial(Example3)

    示例协议来源为安德鲁安全RPC协议的改编版:该协议用于相互认证双方,然后建立可以用于进一步通信的新共享密钥K1ab(可以作为其它协议的一部分)。此协议的A-B表...

    春风大魔王
  • (补充)SPAN+AVISPA for Verifying Cryptographic Protocols

    消息认证:如果A知道是谁创建的消息m,则称A能认证m。电子签名:私钥加密、公钥解密。(ID,{ID}K-1) 比较ID是否一样。

    春风大魔王
  • 新基建!腾讯宣布投入5000亿

    ? 腾讯将在新基建上投入5000亿。 今年的政府工作报告指出,重点支持既促消费惠民生又调结构增后劲的“两新一重”建设,其中“两新一重”中的第一个“新”,就是新...

    腾讯文旅
  • Linux下不同文件编码的转换

    字符编码(Character Encoding)可以说就是让某一字符序列匹配一个指定集合中的某一东西,常见的例子包括长短电键组合起来表示的摩斯电码(Morse ...

    大江小浪
  • 泛微ecology OA系统配置文件泄露

    协作系统泛微e-cology OA被曝存在数据库配置信息泄露漏洞,如攻击者可直接访问数据库,则可直接获取用户数据,甚至可以直接控制数据库服务器。

    Aran
  • 技术沙龙 | 音视频及融合通信产品技术沙龙邀你参加

    ? ? ? 长按识别二维码,关注腾讯云视频 ? 点击“阅读原文”报名参加

    腾讯云视频
  • Scala-1.字符串

    和Java不同。Scala直接用==就行了,也不怕null,但是不能在null上调用方法:

    悠扬前奏
  • React使用代理解决跨域问题

    这次又遇到跨域问题,大佬推荐我用跨域代理来解决 本文仅限使用creat-react-app来创建的项目 参考文档:https://facebook.gith...

    治电小白菜
  • 二维码会被人类扫完吗?

    支付码、名片码、健康码、校园码、复学码、乘车码、挪车码码码码码码码码码码码码码码码码码码码码码码码码码码,这么多码?光疫情期间,微信“码上经济”就用掉了 14...

    腾讯大讲堂

扫码关注云+社区

领取腾讯云代金券