轮询调度算法

1、轮询调度算法(Round-Robin Scheduling)2010-06-23 15:10:28|分类：默认分类|举报|字号订阅毫无疑问，随着互联网、移动网络接入成本的降低，互联网正在日益深入地走入 我们的生活，越来越成为人们获取信息的高效平台，ICP行业也顺势呈现出强劲 的成长趋势，成为互联网迅猛发展形势下最大的受益者，也直接促成了从web1.0 到web2.0以及社区、博客、视频等一系列互联网时代的更迭和运营模式的变动。但是随着各站点访问量和信息交流量的迅猛增长，如何使用最小的资源成本， 提高网络的效率，最优化用户体验，已经成为网络管理人员不得不面对的挑战。从技术上讲，就是ICP行业面临

2、的网络资源有效利用问题，也就是如何进行 对网络的访问分流，以便能够快速响应用户反应，即：负载均衡。从这篇文章起，我们将讲述在负载均衡技术实现中的核心技术：负载均衡算 法(算法)的原理及其实现，使大家对负载均衡底层技术有一个深刻的了解。这些 算法是负载均衡设备中的核心实现基础。本篇文章先讲述轮询调度算法(Round-Robin)及其在此基础上改进型的权 重轮询算法(Weighted Round-Robin)。轮询调度算法(Round-Robin Scheduling)轮询调度算法的原理是每一次把来自用户的请求轮流分配给内部中的服务器，从1开始，直到N(内部服务器个数)，然后重新开始循环。算法的优

3、点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无 状态调度。轮询调度算法流程假设有一组服务器N台，S = S1, S2,，Sn一个指示变量i表示上一次 选择的服务器ID。变量i被初始化为N-1。其算法如下：j = i；do(j = (j + 1) mod n;i = j；return Si; while (j != i);return NULL;1OCaG.CQfin.Gn这种算法的逻辑实现如图1所示:鱼裁均衡算法一轮询客户讪靖一求被严格分发客户端1OCaG.CQfin.Gn这种算法的逻辑实现如图1所示:鱼裁均衡算法一轮询客户讪靖一求被严格分发客户端感由器负投埼循器图1轮询调度实现逻

4、辑图示轮询调度算法假设所有服务器的处理性能都相同，不关心每台服务器的当前 连接数和响应速度。当请求服务间隔时间变化比较大时，轮询调度算法容易导致 服务器间的负载不平衡。所以此种均衡算法适合于服务器组中的所有服务器都有相同的软硬件配置 并且平均服务请求相对均衡的情况。权重轮询调度算法(Weighted Round-Robin Scheduling)上面所讲的轮询调度算法并没有考虑每台服务器的处理能力，在实际情况中， 可能并不是这种情况。由于每台服务器的配置、安装的业务应用等不同，其处理 能力会不一样。所以，我们根据服务器的不同处理能力，给每个服务器分配不同 的权值，使其能够接受相应权值数的服务请

5、求。权重轮询调度算法流程假设有一组服务器S = S0, S1,，sn，W(Si)表示服务器Si的权值，一 个指示变量i表示上一次选择的服务器，指示变量cw表示当前调度的权值， max(S)表示集合S中所有服务器的最大权值，gcd(S)表示集合S中所有服务器 权值的最大公约数。变量i初始化为-1, cw初始化为零。其算法如下：while (true) (i = (i + 1) mod n;if (i = 0) (cw = cw - gcd(S);if (cw = cw)return Si;这种算法的逻辑实现如图2所示，图中我们假定四台服务器的处理能力为 3:1:1:1。员载均衡算法一权重轮询调度图2权重轮询调度实现逻辑图示Internet客户端路由器员载均衡算法一权重轮询调度图2权重轮询调度实现逻辑图示Internet客户端路由器员载均衡器管理员设置把客户的靖 求3:1:1:1比例分配由于权重轮询调度算法考虑到了不同服务器的处理能力，所以这种均衡算法 能确保高性能的服务器得到更多的使用率，避