一种基于时分复用的云资源管理方法

第４２卷第５期２０１４年５月

ＪＯＩ琅ＮＡＩ，ｏＦ删Ｉ

同济大学学报（自然科学版）

Ｖ０１．４２Ｎｏ．５

ＵＮＩⅦＲｓＩＴＹ（ＮＡｎ瓜ＡＩ，ＳＣＩＥＮＣＥ）

Ｍａｙ２０１４

文章编号：０２５３—３７４Ｘ（２０１４）０５—０７８２—０８ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．０２５３—３７４ｘ．２０１４．０５．０２０

一种基于时分复用的云资源管理方法

匡桂娟１’２…，曾国荪１’３

（１．同济大学电子与信息工程学院，上海２０１８０４；２．青岛农业大学理学与信息学院，山东青岛２６６１０９；

３．国家高性能计算机工程技术中心同济分中心，上海２０１８０４）

摘要：为了实现多租户的云计算环境下用户对计算资源的公平使用，用有限资源应对最大量的用户需求，针对云计算中

ｔ０ｂｅｖａｌｉｄ．

ｗｏｒｄｓ：ｃｌｏｕｄ

ｔａｓｋｓ

Ｋｅｙｃｏｍｐｕｔｉｎｇ；ｂａｔｃｈｓｃｈｅｄｕｌｉｎｇ；

成批到达的可划分独立任务，研究了一种基于时分复用的虚

ｒｅｓｏｕｒｃｅ

ｖｉｒｔｕａｌｉｚａｔｉｏｎ；ｔｉｍｅ—ｄｉｖｉｓｉｏｎｍｕｌｔｉｐｌｅｘｉｎｇ

拟化资源管理方法．将整个云中计算资源作为复用对象，根据用户任务需求确定资源的复用周期和时间片，给出了资源时分复用的多种策略，并且对不同策略进行了深入的性能指标分析，形成了相应结论，以应对和指导不同应用场景．最后验证了资源管理方法的有效性．

关键词：云计算；批任务调度；资源虚拟化；时分复用中图分类号：ＴＰ３３８

文献标志码：Ａ

云计算是在并行计算、分布式计算、集群计算、网格计算等基础上发展起来的一种基于网络的计算

模式，以服务的形式对外提供ＩＴ资源，包括基础设施服务ＩａａＳ（ｉｎｆｒａｓｔｒｕｃｔｕｒｅ

ＰａａＳ（ｐｌａｔｆｏｒｍ

（ｓｏｆｔｗａｒｅ

ａｓ

ａ

ａｓ

ａｓ

ａ

ｓｅｒｖｉｃｅ）、平台服务

ａ

ｓｅｒｖｉｃｅ）、软件服务ＳａａＳ

ｓｅｒｖｉｃｅ）等，并且具有ＳＬＡ（ｓｅｒｖｉｃｅ

Ｔｉｍｅ－ｄｉｖｉｓｉｏｎ

Ｍｕｌｔｉｐｌｅｘｉｎｇ－ｂａｓｅｄ

Ｃｌｏｕｄ

ｌｅｖｅｌ

ａｇｒｅｅｍｅｎｔ）保障［１。２］．对数据中心而言，有效整

ＲｅｓｏｍＭａｎａｇｅｍｅｎｔＭｅｔｈｏｄｓ

合云数据中心的资源，提高资源利用率，节约能源，降低运行成本是云数据中心关注的热点［３］．对于用

Ｅｎｇｉｎｅｅｒｉｎｇ，Ｔｏｎｇｊｉ

ｏｆ

ＫＵＡＮＧＧ饥ｉｊ凇＂１ ２～，２固、７ＧＧｕｏｓｕｎｌ ３

（１．Ｃｏｌｌｅｇｅ

ｏｆ

Ｅｌｅｃｔｒｏｎｉｃｓ

ａｎｄ

Ｉｎｆｏｒｍａｔｉｏｎ

户而言，可以通过Ｉｎｔｅｒｎｅｔ随时随地享有公平获取服务的机会．实现云计算资源管理自动部署，动态扩展，按需分配，方便用户按需获取资源是云计算研究的热点和难点．２０１０年Ｚｅｎｏｓｓ的调查报告指出云资源管理是仅次于云安全问题的一大挑战［４］．

云资源管理的困难不仅在于云中心要管理的资源规模庞大，还来自于它要同时为多租户提供服务这一云的本质特征［５］．师雪霖等［６］指出，目前云计算中许多资源管理方法仍沿用传统的网格资源的管理方法，例如采用线性规划的数学模型，运用启发式算法对问题求解等［７］．这些算法没有很好地考虑到云

Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２０１８０４，Ｃｈｉｎａ；２．Ｓｃｈｏｏｌ

Ａｇｒｉｃｕｌｔｕｒａｌ

Ｓｃｉｅｎｃｅ

ａｎｄ

Ｉｎｆｏｒｍａｔｉｏｎ

Ｓｃｉｅｎｃｅ，ＱｉｎｇｄａｏＵｎｉｖｅｒｓｉｔｙ，Ｑｉｎｇｄａｏ

２６６１０９．Ｃｈｉｎａ；３．ＴｏｎｇｊｉＢｒａｎｃｈ．ＮａｔｉｏｎａｌＥｎｇｉｎｅｅｒｉｎｇ＆Ｔｅｃｈｎｏｌｏｇｙ

ＣｅｎｔｅｒｏｆＨｉｇｈＰｅｒｆｏｒｍａｎｃｅＣｏｍｐｕｔｅｒ，Ｓｈａｎｇｈａｉ２０１８０４，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｆｏｃｕｓｉｎｇｔｈｅｃｌｏｕｄ

ｒｅｓｏｕｒｃｅ

ｏｎ

ｔｈｅｄｉｖｉｄａｂｌｅｂａｔｃｈｔａｓｋｓｒｕｎｎｉｎｇｉｎ

ｓｔｕｄｙｉｓｍａｄｅ

ｏｆｔｈｅ

ｃｏｍｐｕｔｉｎｇｅｎｖｉｒｏｎｍｅｎｔ，ａｖｉｒｔｕａｌｉｚａｔｉｏｎｂａｓｅｄ

ｏｎ

ｔｉｍｅ ｄｉｖｉｓｉｏｎｍｕｌｔｉｐｌｅｘｉｎｇｉｎ

ｏｒｄｅｒｔｏ

ｅｎｓｕｒｅａ

ｆａｉｒｏｐｐｏｒｔｕｎｉｔｙｆｏｒｕｓｅｒｓｉｎｃｌｏｕｄｃｏｍｐｕｔｉｎｇａｎｄｓａｔｉｓｆｙ

ｔｈｅｒｅｑｕｉｒｅｍｅｎｔｓ

ａｓ

ｗｉｔｈｍｕｌｔｉ—ｔｅｎａｎｔｓｍｕｃｈ

ａｓａｓ

ｐｏｓｓｉｂｌｅ．Ｃｏｍｐｕｔａｔｉｏｎａｌｒｅｓｏｕｒｃｅ

ｔｈｅ

ｔｉｍｅ—ｍｕｌｔｉｐｌｅｘｉｎｇ

ｉｎｃｌｏｕｄｓｙｓｔｅｍｉｓｖｉｅｗｅｄ

Ａｃｃｏｒｄｉｎｇ

ｔｏ

ｏｂｊｅｃｔ．

ｗｉｔｈ

ｕｓｅｒｓ’

计算的应用特点，大多数仍然只关注任务的最短完

成时间．已有的较好的云资源管理系统多从云运营

ｒｅｑｕｉｒｅｍｅｎｔｓ，ｔｈｅｓｌｉｃｅｓ

ａｒｅ

ａｐｐｒｏｐｒｉａｔｅｍｕｌｔｉｐｌｅｘｉｎｇｃｙｃｌｅｔｈｅ

ａｎｄｔｉｍｅ

ｄｅｔｅｒｍｉｎｅｄ

ｐｒｏｐｏｓｅｄ

ｓｔｒａｔｅｇｉｅｓ．

Ｆｕｒｔｈｅｒｍｏｒｅ，ａｄｅｔａｉｌｅｄｐｅｒｆｏｒｍａｎｃｅａｎａｌｙｓｉｓｆｏｒｄｉｆｆｅｒｅｎｔ

ｓｔｒａｔｅｇｉｅｓｉｓｍａｄｅ．Ｔｈｅｏｒｅｔｉｃａｌａｎａｌｙｓｉｓａｎｄｓｉｍｕｌａｔｉｏｎｓｐｒｏｖｅｔｈｅｔｉｍｅ—ｄｉｖｉｓｉｏｎｍｕｌｔｉｐｌｅｘｉｎｇ

ｒｅｓｏｕｒｃｅ

商角度出发进行管理，追求的是资源的整合和负载

的均衡，如基于ＣＰＵ利用率的资源管理［８‘９］，基于能耗的资源管理［１０］等，也没有很好地关注云计算环境

ｍａｎａｇｅｍｅｎｔｍｅｔｈｏｄ

收稿日期：２０１３—０８—２７

基金项目：国家“八六三”高技术研究发展计划（２００９ＡＡ０１２２０１）；国家自然科学基金（６１２７２１０７，６１２０２１７３，６１１０３０６８）；上海市优秀学科带

头人计划（１０ＸＤｌ４０４４００）；教育部高等学校博士学科点专项科研基金（２００９００７２１１００３５）；教育部网络时代的科技论文快速共享专项研究（２０１１０７４０００１）；华为创新计划（ＩＲＰ一２０１３—１２—０３）

第一作者：匡桂娟（１９７２一），女，讲师，博士生，主要研究方向为并行分布处理及云计算．Ｅ－ｍａｉｌ：ｌｇｊｋｕａｎｇ＠ｔｏｎｇｊｉ．ｅｄｕ．ｃｎ通讯作者：曾国荪（１９６４），男．教授，博士生导师，工学博士，主要研究方向为并行计算、可信软件及信息安全．

Ｅ—ｍａｉｌ：ｇｓｚｅｎｇ＠ｔｏｎ卣ｉ．ｅｄｕ．ｃｎ

万方数据

第５期匡桂娟，等：一种基于时分复用的云资源管理方法

下用户要求公平使用资源的愿望．云数据中心资源管理的关键技术是虚拟化技术，目前运用较多的虚拟化技术有ＸｅｎＥｌｌ］，ＫＶＭＥｌ２］以及ＶｍｗａｒｅＬｌ３３等，主要是以虚拟机的形式向不同用户提供资源，例如

Ａｍａｚｏｎ

ＥＣ２Ｅ１４］．以上这些虚拟化技术属于“以大变

小”的应用模式，即将一台功能强大的物理计算资源

虚拟成多个独立的、满足不同要求的小计算资源，服务不同的用户，在一定程度上提高了物理资源的利用率．虚拟化技术另外一种应用模式是“由小组大”，即将多个孤立的、小的物理资源聚合成一个更强大的服务器，完成特定的功能．例如Ｌｉｎｕｘ的开源项目

ＬＶＳ（１ｉｎｕｘｖｉｒｔｕａｌｓｅｒｖｅｒ）Ｅ１５］．目前虚拟化技术虽然

较好地实现了多用户对计算资源的共享和动态分配，一定程度上提高了资源利用率，但仍然存在很多

问题：计算资源浪费现象仍大量存在，因为虚拟机管理机制中按用户峰值要求，即最高需求量分配资源，通常情况下用户未必需要如此多的资源；虚拟机之间资源不能共享，导致虚拟机资源利用不足；另外，云计算中尤为突出的用户公平使用资源的要求难以

有效保证；有限资源如何应对几乎无限的用户请求

问题尚未引起足够重视．因此，现有虚拟化管理技术还远不能满足按需服务的要求，本文针对云计算中

成批到达的可划分的独立任务，探索一种基于时分

复用的虚拟化资源管理方法．

事实上，在网络并行计算系统中，存在着大量独立的可切分应用程序．例如蒙特卡罗（Ｍｏｎｔｅ

Ｃａｒｌｏ）

模拟、分形计算（如Ｍａｎｄｅｌｂｒｏｔ）、海量信息检索（如

ｋｅｙ

ｂｒｅａｋｉｎｇ）、参数扫描、图像处理（如层析成像重

建）、数据挖掘等都可看成是独立可切分计算任务．最近流行的ＭａｐＲｅｄｕｃｅ并行编程模型，特别适合独立的可切分任务的编程求解．本文正是针对批到达的独立可划分任务运行在云计算环境中，给出一种

基于时分复用的资源管理方法，旨在公平有效地使用云资源，并有效地提高系统资源的利用率．１

云资源虚拟化的一般过程

１．１

云资源按需分配的要求

云资源分配的过程就是安排计算资源来应对用

户提出的各种需求，达到期待的目标．该目标对于用户来讲首先是计算时间少，任务的等待时间小，分配

到的计算资源利用率高，可靠性高等方面；对于资源

提供方来讲，因为云计算是规模经济效益驱动下的计算模式，因此云平台一方面要尽量提高资源利用

万方数据

率，另外一方面更希望同时将资源提供给更多的用

户，并且给用户公平的资源使用体验．由于云资源多

样性，以及用户需求的多样性，满足该目标并不是一

件容易的事．图１给出了云计算资源按需分配的示

意图．

在图１中，最上层，用户向云系统提交应用任务，并提出资源请求．用户提交给云系统的应用任务多种多样，可能任务类型不同，例如科学计算、事务处理、实时控制等；可能是通用计算，也可能是专用计算；可能任务可以划分实现并行执行，也可能任务不可划分只能串行执行；可能用户的ＱｏＳ（Ｑｕａｌｉｔｙ

ｏｆ

Ｓｅｒｖｉｃｅ）不尽相同，等等．最底层，资源提供商向云

系统提供物理计算资源．物理资源可能是异构的、分布的、动态的、自治的．例如计算节点可能是ＰＣ机、工作站、小型机、超级计算机，也可能是ＳＩＭＤ

（Ｓｉｎｇｌｅ

Ｉｎｓｔｒｕｃｔｉｏｎ

Ｍｕｌｔｉｐｌｅ

Ｄａｔａ）、ＭＩＭＤ

（ＭｕｌｔｉｐｌｅＩｎｓｔｒｕｃｔｉｏｎＭｕｌｔｉｐｌｅＤａｔａ）、向量机、专用

机等．中间层，管理模块根据用户的ＱｏＳ需求提供与之匹配的物理资源，即将物理资源映射为满足用户需求的逻辑资源．

图１云计算按需分配资源示意图

Ｆｉｇ．１

Ｏｖｅｒｖｉｅｗｏｆｏｎ．ｄｅｍａｎｄ

ｒｅｓｏｕｒｃｅ

ｍａｎａｇｅｍｅｎｔ

ｉｎｃｌｏｕｄｃｏｍｐｕｔｉｎｇｓｙｓｔｅｍ

正如上面所述，在图１中，物理计算资源ｐｒ。，ｐｒ。，…，ｐｂ很可能无法应对大量和多样的用户请求ｕｒ。，ｕｒ：，…，ｕｒ。需要有效的虚拟技术对物理资源进行组织管理，形成逻辑资源ｌｒ。，ｌｒ。，…，ｌｒ。，以

便满足用户需求．这种把有限固定物理资源按需重

新规划构成逻辑资源，以便提高系统利用率的管理

技术就是虚拟化技术．本文研究的时分复用技术属于虚拟化技术的一种．１．２资源分配的基本概念

定义１物理资源（ｐｈｙｓｉｃａｌｒｅｓｏｕｒｃｅ）：是指在

云计算环境中，直接参与计算处理的物理器件，又称

计算节点，可用一个五元组表示ｐｒ一（Ａ，ｒ，ｕ，ｆ，

厂），整个云系统的物理资源记为ＰＲＳ一｛ｐｒ。，ｐｒ：，

同济大学学报（自然科学版）第４２卷

…，ｐｒ。｝．

在上面定义中：Ａ是指物理资源的计算机类型，例如串行计算机、并行计算机、向量计算机、信号处

理专用机等；ｒ是指物理资源的时钟中断周期，是物理资源处理动作的基本时间单位；到是计算节点的处理速度，用来表征节点计算能力的大小；Ｃ是指计算

节点进行任务切换的时间开销；ｆ是计算节点特点，ｆＥ｛０，１，２），“ｏ”代表该计算节点不可再划分，即原

子器件，“１”表示计算节点空间上可划分，“２”表示计算节点时间上可划分．

定义２用户需求（ｕｓｅｒｒｅｑｕｉｒｅｍｅｎｔ）：是指请

求云平台提供计算资源、执行任务处理、满足服务质

量的要求，即请求任务，单个用户需求可用一个四元

组表示ｕｒ一（Ａ，训，ｇ，ｒ）．整个云系统的用户需求记为ＵＲＳ＝｛ｕｒｌ，ｕｒ２，…，ｕｋ）．

在上面定义中：Ａ是指用户请求任务的业务类

型，例如科学计算、事务处理、实时控制等；Ｗ是用户

请求任务的计算工作量大小；ｇ是指任务可切分的

粒度，记ｇ一１表示用户任务可以任意切分，显然ｇ一训表示任务不可切分；ｒ是用户任务要求的最晚完成时间，即截止时间（ｄｅａｄｌｉｎｅ）．

定义３逻辑资源（１０９ｉｃａｌｒｅｓｏｕｒｃｅ）：又称虚拟资源，是指利用虚拟化技术对物理资源进行划分、组

合、复用等操作，以便满足用户需求，重新整合的计算资源，是一种用户视角的计算资源．单个逻辑资源

可用一个三元组表示ｌｒ一（Ａ，７．１，ＳＰ），整个云系统的物理资源记为ＬＲＳ一｛ｌｒ，，ｌｒ。，…，ｌｒ。｝．

在上面定义中：Ａ是指逻辑资源虚拟化后的计算类型；ｕ是逻辑资源的综合处理速度，表征逻辑资源的计算能力；ＳＰ＝（ｓｐｌ，ｓｐ２，…，ｓｎ…，ｓｐ＾），志表

示组成逻辑资源ｌｒ用到的物理计算资源种类数，ｓｎ表示组成逻辑资源的第ｉ种物理资源的类型和数量．

２资源时分复用的方法

２．１

计算资源时分复用的基本思想

对于每一个计算资源，将其整个运行时间划分成一个个小的时间片段，让使用该资源的多个用户任务轮流占用这些时间片段．其中一个用户任务一次只占用一个时间片段，当所有用户任务都被运行

一个时间片后，该计算资源的一个运行周期结束，进

入下一个运行周期．如此周而复始，直到所有的用户

请求任务被执行完成．资源时分复用的优点是：①

万方数据

每个用户得到公平使用资源的权利，符合云计算中

多租户的特点；②有限的物理计算资源可以应对尽

可能多的用户需求；③单个任务不独占物理资源，

多个用户通过小的时间片共享一个物理资源，提高

了资源的利用率；④用户只需要在自己分配到的时

间片内执行任务即可，而不需要关心底层如何实现的，提高了资源使用的透明度．时分复用的工作原理如图２所示．

＠之… ＠乏

ａ

ｂ

Ｃ

图２物理资源的时分复用原理

Ｆｉｇ．２

Ｔｉｍｅ－ｄｉｖｉｓｉｏｎｍｕｌｔｉｐｌｅｘｉｎｇｐｒｉｎｃｉｐｌｅ

图２ａ中，资源ｐｒ。的运行周期Ｔ。是一个没有被

切分的周期，表示资源被任务独占的执行模式．图２ｂ中，资源ｐｒｚ的运行周期孔被均等划分，表示资源分配给每个任务相等的时间片的执行模式．图２ｃ中，资源ｐｂ的周期Ｔ。被不均等划分，表示资源分

配给每个任务不等的时间片的执行模式．实施复用

之后的资源称为逻辑资源．

２．２资源时分复用的模型

对于云计算环境中的每个计算节点，实施复用

之后具有运行周期Ｔ、时间片ｓ：，等概念和变量．Ｔ是

每个资源为所有用户任务服务一轮花费的时间，又

称资源的复用周期．将Ｔ分成多个小的时间片即乩，表示第ｉ个计算节点为第Ｊ个用户任务分配的时间段．Ｓｉｉ的大小可以相同，也可以不同．每一个物理资源都可以独立地形成相应的逻辑资源，每个时间

片都可以被用来处理任意用户请求任务．要合理有效地划分计算节点的运行时间，必须考虑多方面因素，包括一个计算节点运行周期Ｔ的大小，时间片

Ｓ。的大小，一个运行周期内时间片的数目，以及用户请求任务与时间片的对应关系等．

定义４复用后的物理资源：是一种特殊的虚拟

资源，即采用复用的虚拟化技术，使得物理资源虚拟

化后，逻辑上可以重复多次被多个用户任务同时使用的资源，可用一个四元组表示为ｌｒ７一（Ａ，ｕ，Ｔ，Ｓ）．其中，Ａ是该资源的计算类型，ｕ是该资源的处理速度，丁是该资源复用后的运行周期，Ｓ一｛Ｓ，，Ｓ：，…，Ｓｉ…，Ｓ。）为复用周期中划分的时间片，Ｓ。是第ｉ个时间片，ｍ是时间片的总个数．物理资源复用后的逻辑资源的集合为ＬＲＳ’一｛ｌｒ７。，ｌｒ’２，…，ｌｒ’。）．

将复用后的物理资源集合ＬＲＳ７中不同ｌｒ７的不

第５期匡桂娟，等：一种基于时分复用的云资源管理方法

同时间片ｓｉ进行组合，构成用户可以使用的逻辑资源ＬＲＳ一｛ｌｒｌ，ｌｒ２，…，ｌｋ）．

根据上述分析，沿用上述符号，结合前面定义３

３执行批任务的资源时分复用策略

３．１条件和前提假设

用户视角的虚拟资源定义，云资源复用问题的形式

化描述如下：

不妨假设云计算环境中用户请求任务成批到达，记单批任务到达时刻为０，即每个用户请求到达

都在同一个时刻，但用户任务要求的完成时间可能不同，任务的负载量可能不同，可划分的粒度可能不

］Ｅ，５ｉ：｛ｐｒｌ，ｐｒ２，…，ｐｒ。）一｛ｌｒ’１，ｌｒ７２，…，ｌｒ７。｝

＾｛ｌｒ７ｌ，ｌｒ２，…，ｌｒ７。）一｛ｌｒｌ，ｌｒ２，…，ｌｋ）

７

ｌｒｊ一，Ｕ｛ｌｒ７—４）１一ｌ Ｚ＿… ”

同．这样的假设具有一定的合理性和实效性，虽然用户提交服务请求在时间上可能不是严格同时成批到达的，但是目前云计算应用服务多是大数据事务处

理任务，实时控制服务任务不是太多，因此可以将时间上相近到达的多个任务，看做和处理成时间上同时到达的批任务．用户的要求可以通过任务的截止时间来反映．

假设用户请求任务是独立的可任意切分的．例

ｕｒｊ．ｒ一∑５ｉ

ｉ

Ｔｉ一∑ｓｄ＋研 ｌｒ７“

，一１

ｕｏ．ｒ≤易，易是ｕｏ的截止完成时间

ｌ

１≤ｉ≤订，１≤Ｊ≤ｍ

定义５任务组完成时间（ｍａｋｅｓｐａｎ）：指一组

２．３资源复用评价指标

如图像处理、生物信息学、粒子物理、气象模拟等领

域存在大量可切分的计算任务．对于关联和不可切分计算任务，将在后续工作中进一步研究．

假设成批到达的任务个数为ｍ，云计算环境中

用户请求向系统最早提交任务时刻开始，到所有任

务都执行完成为止，系统运行的一个时间跨度，记为￡。一ｍａｘ￡ｆ，一ｒａｉｎｔ。，其中ｆ“表示用户请求任务ｕｒ。

的完成时刻，￡。表示用户请求任务ｕｒ，到达系统的时刻．

定义６

ｒｅｓｐｏｎｓｅ

物理资源的个数为卵．假设所有物理资源都是可时分复用的计算资源，所有用户请求任务都可在所有物理资源上运行，所有任务执行完之前所有资源一直

处于运行状态．

任务组平均响应时间（ａｖｅｒａｇｅ

ｔｉｍｅ）：指一组用户请求的第一个任务进入

系统到所有任务都执行为止，每个任务保持在系统

假设物理资源复用切换开销都相等，如此假设目的是为了分析讨论方便，不会影响方法的有效性．

用Ｃ。一ｍａｘＰｒｉ．ｃ，表示所有资源的任务切换开销，

ｌ≤Ｊ≤”

中的平均时间，记为￡。，一』∑（￡“一￡缸）．

｝Ｈ一１

定义７任务组平均延迟率（ａｖｅｒａｇｅ

ｓｌｏｗｄｏｗｎ

那么ｍ次任务切换开销用ｃ表示，ｃ—ｍｆ０．３．２优先和独占策略

ｒａｔｅ）：指用户请求任务的响应时间与系统执行该任

务的运行时间的平均比值，记为ｒａ。一

策略１最小任务优先调度到最快资源上执行：

该策略的思想是每次选择一个任务将其分配到某个

去圣（堕云生），其中如是计算资源运行用户请求

任务ｕｒ，的实际时间．

定义８资源利用率（ｒｅｓｏｕｒｃｅｕｔｉｌｉｚａｔｉｏｎ）：指

资源上，并独占该资源直到任务执行完成，如图２ａ

所示，选择时要满足以下条件：①被选择的任务工作量最小；②被选择的资源执行速度最快；此时任

资源用于用户请求任务的有效工作能力与资源总的

，晶、

【２５ｔｅｚＪ。ｐｒｕｒ．．ｆ

工作能力的比值，记为ｒｕ一

．其中

务在该资源上的预计完成时间是最短的．

策略２最大任务优先调度到最快资源上执行：该策略的思想是每次选择一个任务将其分配到某个资源上，并独占该资源直到任务执行完成，如图２ａ所示，选择时要满足以下条件：①被选择的任务工作量最大；②被选择的资源执行速度最快．该策略有利于系统负载均衡．

（∑ｐｒ“） ｔ。

ｐｒ。。．ｆ代表用户请求ｕｒ被分配到的物理资源ｐｒｕｒ的

切换开销．

定义９

系统任务服务率（ｓｅｒｖｉｃｅｒａｔｅ）：指系

统按照用户要求完成的用户请求任务个数ｚ与提交给系统总的用户请求任务个数Ⅲ的比值，记为＾一

ｌ／ｍ，Ｚ＜ｍ．

假设按照策略１或者策略２，资源ｐｒ，上运行了ｚ，个用户请求任务，分别用ｕｒＪｌ＇ｕｒＪ２’…，ｕｒ。．表示．

同时记￡。ｎ’表示策略１中的ｆ。值，后文中其他策略

万方数据

同济大学学报（自然科学版）第４２卷

的性能评价指标的表示与此类同，则根据２．３节中

评价指标的定义，优先和独占策略具有以下性能指标：

（１）任务组的完成时间

１≤，≤ｎ＼一１

．‘Ｕ，

（２）任务组的平均响应时间

ｔｍｓ（１）刮∥一一ｍａｘ。（２剥带ｏｒｌ）（１）

球）－瑶）＝一１—２一Ｓ（２ｍ

。一１一

１列筹）㈤

，Ｄｒ．．铆，

其中，内层求和表示机器ｐｒ７上第ｙ个任务的响应时

间；次外层求和表示该机器上所有任务响应时间的和；最外层和是所有任务响应时间的和．

（３）任务组平均延迟率

ｋ（１Ｊ—Ｖａｓ（２）一去蚤（警）㈣

（４）资源利用率为

（４）

（∑ｐｏ．ｆ） ｔ。。

ｉ＝１

其中，ｐｒ。ｒ．ｃ代表用户请求被分配到的物理资源．

３．３时分复用策略

策略３相等时间片相等任务量的时分复用策略：该策略的主要思想是：如图２ｂ所示，云系统中每个复用的物理资源，即逻辑资源，为每一个用户任务分配一个固定和相等的时间片，每一个时间片中不

同计算节点处理的任务量也是相等的，以便云系统

公平地执行每个用户任务．当所有任务都执行了一个时间片以后，就说该计算节点运行了它的一个时分复用周期．如此轮转和周期地执行下去，直到所有的任务都完成．可见，每个用户都能够感觉到均等地享有计算资源的机会．

本策略中固定和相等的时间片用Ｓ。表示，合理设定Ｓ。要求考虑以下几个因素：

（１）计算节点的时钟中断周期，应满足Ｓａ—ｋ ｌｃｍ（｛ｐｒ，．ｒｌＪ一１，２，…，行）），其中ｋ是待定的整数值．因为时钟中断周期是计算节点的最小处理时间单位，为了使每个计算节点都能够在一个时间片内至少执行一个最基本的处理操作，Ｓ。应该大于等于所有时钟中断周期的最小公倍数．但时间片过小会引起任务频繁切换，导致系统开销大．

（２）应满足士≥１０，其中ｃ。一ｍａｘ

ｐｒｊ．ｆ，即将

ｃ

０ｌ＾。

ｌ匐≤”

所有计算节点的任务切换开销看成是相同的，均为Ｃ。．公式中的ｐ是对系统一个时间片中任务运行时间

万方数据

所占比例的一个要求．

（３）考虑任务量与资源处理速度因素，应满足Ｓ。

≤吉。篆蒜，不等式的右边是最小任务在最大

１

ｍｉｎｕｒ，．砌

ｌ≤ｉ≤Ｈ‘。

能力计算资源上的运行时间．

本策略中一个时问片内处理的固定和相等的任

务量用姒表示，７－Ｕａ—ｍｉｎ（ｐｒｊ．ｕ ｓ。），以保证每一

个逻辑资源在一个时间片内，拥有充足的任务工作量，为每个任务都执行相等的工作量．

根据时分复用的原理，如图２ｂ所示，策略３具有以下性能指标：

（１）每个逻辑资源的一个复用周期Ｔ内有ｍ个

时间片，即ｓ｛｛）一ｓ轳’…一ｓ聊一Ｓ。，１≤ｉ≤ｍ，１勺≤恕．

（２）所有逻辑资源的复用周期都是相同的，用固定周期Ｔ∞’表示，满足

Ｔ‘３’一聊 Ｓ。＋ｆ—ｍ Ｓ。＋ｍ Ｃｏ

（５）

（３）任务组的完成时间为

ｔ。门’一（埘 ＆＋ｆ） ｌ』 竖鱼Ｌ—一ｌ（６）

ｒ

１

ｍａｘ（ｕｒ：．硼）］

（４）任务组平均响应时间为

瑶ｋ三（ｍ％㈨ 妻（陪警）（７）ｉ＝１

ｍ一＼ｌ竹

ｄ－－１

１侧。

，

（５）任务组的平均延迟率

ｒ√引一旦业

（８）

Ｓ口

（６）资源利用率为

∥，一蚤荟！盏竖茎乜㈤

～

卵 ｆ裟

…

公式（９）中的分子表示所有任务在所有逻辑资源上实际运行的时间和，即”个资源实际处理任务的总时间．分母表示门个资源在任务组执行期间总的运行时间，即行 ｆ２．

在策略３中，无论用户任务调度到何种逻辑资

源上，在相等的时间片内会执行相等的任务量，这从用户角度看是公平的．但是同时也看到，小任务会很快完成，其分配占用的时间片空闲且得不到利用．另一方面，速度较快的逻辑资源在完成固定任务量后，可能还有余力，没有充分地利用时间片，造成了资源的浪费．为了充分利用资源，因此必须进一步完善时分复用策略．

策略４不等时间片不等任务量的时分复用策

略：该策略的主要思想是：如图２ｃ所示，在每个复用

周期内，云资源为每个任务分配不相等的时间片，使

得每一个任务分配的时间片Ｓ。与该任务的工作量成