DOC《     》

(2) 收到协商邀请的节点收集本地资源信息,进行本地资源评价,以判定是否参与任务调度;

(3) 责任节点收集各参与协商节点的资源信息及其评价信息,并根据任务信息,对各节点资源进行综合评价,找到最适宜调度节点. 资源及任务信息描述 资源信息描述 云计算结合了成熟的虚拟化技术,各计算结点节点的物理资源被虚拟化为影响任务调度的各类资源,如计算能力、计算成本、负载等.调度问题即为任务与资源的优化匹配.定义RS为节点资源集合,包括CPU、内存、数据存储、带宽4类资源,即(1.1) 各节点需收集的资源信息集合定义为RIS: (1.2) 其中,为处理器计算能力,评价标准为指令执行速度,即单位时间内处理的指令条数(MIPS);

为内存大小;

为数据存储空间;

为通信能力,即节点间网络带宽;

为节点负载,包括CPU、内存和带宽使用率;

为节点故障率,即单位时间内失效的次数,包括网络故障率和服务故障率;

为使用各类资源所需成本,包括处理器单位价格(每百万指令MI),内存单位价格(每1MB),数据存储单位价格(每1G),通信单位价格(每1Mbps). 任务信息描述 对于任务的描述可分为主观信息和客观信息.任务的主观描述,即用户的Qos需求,包括用户期待完成时间、期待费用,和时间限制、费用限制,以及可靠性需求等. 任务客观信息包括任务对资源的硬性限制条件,如操作系统、内存、带宽限制等,以及任务对各类资源的需求量.其中为任务对处理器的需求量,表示为任务长度,即指令数(MI),它影响任务执行时间;

为任务所需内存大小(MB);

为任务所需数据存储空间,即数据文件大小(MB);

此外,任务对网络传输的需求由需传输的数据文件大小表示,它影响了传输时间. 多指标综合评价 本地资源评价 各节点接收到责任节点发布的任务信息,进行本地资源评价,算法具体描述如下: (1)根据任务的硬性限制条件判断,若不能满足该条件,则不参与协商;

否则,进行以下步骤. (2)收集本节点各项负载值,并计算综合负载值.本文采用惩罚型代换合成法[7],该方法加大了对落后指标的惩罚力度,即某个指标不合格将导致整个综合值不合格. (2.1) 其中负载值分别为CPU利用率,内存使用率和带宽负载;

为各项负载值相应的权重,,

.由公式2.1可以看出,综合负载值在[0,1]区间内,若某单项负载为1,则导致综合负载为1. 为确定负载权重,本文对,和对系统性能的影响进行了测试.测试环境为AMD Athlon 64处理器,Linux操作系统.测试算法为快速排序算法和计算值算法.测试结果如图2.1-2.3所示. 图2.1 CPU利用率 图2.2 内存利用率 Fig.2.1 CPU Usage Fig.2.2 Memory Usage 图2.3 网络带宽 Fig.2.3 Network Usage 由上图可知,3种负载对任务完成时间的影响比重大略为4:3:15.因此,可以得到计算系统综合负载的方式: (2.2) 计算任务的估计完成时间.任务i在节点j完成时间记为,需考虑到任务队列等待时间,计算时间,以及通信时间,即(2.3) 其中,为节点的就绪队列执行时间,即(2.4) 这里,为就绪队列长度,其中,由任务i的长度(MI)和CPU处理能力(MIPS)决定,即(2.5) 根据任务数据文件大小和节点i和节点j之间的通信能力得到,如下: (2.6) (3)计算任务执行的费用.任务i在节点j上的代价为 (2.7) 其中为节点j上第k类资源的单位代价,为任务i对第k类资源的需求量. (4)计算节点可靠性.可靠性,即节点在一定时间内正常工作的概率,它服从泊松分布[8],即若节点j故障率为,则节点j在时间t内正常工作的概率为.设网络故障率为,服务故障率为,则有节点j可以正常完成任务的概率为 (2.8) 多指标综合资源评价 责任节点收到参与协商的各节点的本地资源评价信息,采用层次分析方法[9]进行多指标综合评价.如图2.4所示. 定义 任务适宜分配度:计算节点的动态属性,表示该节点对完成任务的适宜度,是本模型资源评价的最终目标.任务将被调度到任务适宜分配度最高的节点. 图2.4 层次分析模型 Fig.2.4 Analytical Hierarchy Model 本模型评价目标为任务适宜分配度,将该目标分为4个子目标,包括完成时间,费用,负载及可靠性.各子目标评估值由相应指标综合评价得出.本模型采用的合成方法为TOPSIS逼近理想解[10]的方法,该方法是多目标决策领域的著名方法,被很多文献应用在多指标综合评价中.该方法的思想为求与理想点的贴近程度,详细思路如下: (1)对各指标进行无量纲化处理.评估指标依性质和作用分为正指标和逆指标,指标数值大小与最终目标一致的,是正指标,即收益型指标;