执行调度的任务调度节点主要由5大组件构成，如图7所示：任务等待队列、负载均衡器、任务选择器、权重调整器、节点状态更新线程。其中，任务等待队列采用半队列的特殊设计，即任务队列的一半是在调度中心节点侧的待调度队列(vTaskQue)，而另一半是在服务节点端的待处理队列(rTaskQue)。这样的设计是因为每一个等待队列中每次被调度选中的任务数量受限，且定向分配唯一的节点，所以每一个任务逻辑上对应唯一的vTaskQue。该队列在调度中心侧，是一个虚拟的队列，而物理上可以存在于一个共享的任务存储缓冲池中，当出现不均衡情况时，从逻辑上讲，调度就是将过载节点i的vTaskQue(i)中未执行的任务迁移至轻载节点j的vTaskQue(j)中；服务节点端的rTaskQue则是独立的物理结构；负载均衡器(LoadManager)会根据当前本区域的负载以及当前服务节点的负载情况来计算判断是否应该给该服务节点分配原子态任务；任务选择器(TaskSelector)负责从一个vTaskQue中选取一个任务给服务节点；任务调度更新线程(UpdateThread)会每隔特定时间间隔(如10s)更新一次可调度的等待队列，在更新的过程中，它会启动调度节点Agent与各服务加工节点Agent的交互程序，获取服务节点的能力模型，并计算综合能力指数F*，排序器(CapacityAdjuster)则采用能力排序来更新节点状态表中各节点的能力状况(Agent状态表)及其权重(按升序排序)。
width=342，height=282，dpi=110
Figure7Frameworkofaschedulingnode
图7调度节点的框架
公平调度的实质就是维持不同能力贡献的节点有相应吞吐量的状态。分配任务前，需要对所有服务节点按照F*的大小进行升序排列，并以此序列为横坐标计算累计百分比，如表1所示。
Table1Statisticsofthenumberamp;loadofservicenodes
表1服务节点数量及负载统计数据
width=331，height=105，dpi=110
width=624，height=334，dpi=110
Figure8AfairschedulingalgorithmbasedonloadGinicoefficient
图8基于基尼系数的网络公平负载调度算法
实际运作中如遇到能力相同的节点，可将它们视为一个对等体群，比如，表1中4号点位置，不一定只对应一个单点，也可以是代表一个有近20个节点的对等体群，这些点的能力指标均为F*，合在一起具有较大的服务能力，故承担了近40%的服务任务，群内的工作量就完全等分，并按照序号先后进行分配。各点确定位置后，再采用二次曲线y拟合，作Lorenz曲线，最终计算网络服务负载基尼系数Gn，实际计算时还可采用实用公式(6)：
width=199，height=41，dpi=110
(6)
其中，u代表区域内所有n个服务节点的负载均值，y坐标是任务负载累计比例，yi和yj分别是服务节点i和j所对应的负载分配量累计百分比。公式(6)易于直接在编程中实现，其时间复杂度也较低，为O(n2)。
基尼系数用来判别服务网络负载是否均衡(公平)分布，所以公平分配的标准也借鉴了经济学领域的基尼系数合理分布的范围[15]：按照国际惯例设定基尼系数在0.2以下表示高度平均，0.2～0.3表示相对平均，0.3～0.4表示较为合理，0.4～0.5表示差距偏大，0.6以上表示差距悬殊，就是通常所指的危险值。本文将较为理想的服务网络基尼系数尝试定位在0.3～0.45；为了同时体现差异性和均衡性，将0.45作为触发公平调度的阈值δ，从而控制曲线所围面积的比值在[0.3，0.5)，在这个范围之内的任务负载分配不会造成严重的不均衡现象，从而保障资源利用率和服务运作的性能。
本文调度算法的另一个关键环节就是按照服务节点能力对服务节点进行升序排序，升序的意义在于体现“能者多劳”的原则，既让能力较强的节点承担较多的任务，又保持了全局的资源充分利用，达到一个任务公平分配和吞吐量最大的帕累托解。整个调度算法流程形成一个自反馈的闭环结构，详细步骤如下(如图8所示)：
步骤1分配任务前，输入各服务节点Agent上报的节点能力模型数据以及各节点已分配负载。
本小章还未完，请点击下一页继续阅读后面精彩内容！
喜欢即将消逝的乡村请大家收藏：(m.x33yq.org)即将消逝的乡村33言情更新速度全网最快。