带权轮询调度”(Weighted Round-Robin Scheduling,WRR)
http://blog.163.com/s_u/blog/static/1330836720105233102894/
Round-Robin Scheduling,RR
https://svn.apache.org/repos/asf/cassandra/trunk/src/java/org/apache/cassandra/scheduler/RoundRobinScheduler.java
随机性考虑
WRR的运行结果是固定的,如果需要考虑随机性的话,需要再做一些额外工作。简单的话可以先对队列的顺序做随机,但这样实际的顺序还是固定的。可以按实际需要频繁暂存一定(随机)数量的结果,再随机处理后依次输出。
http://blog.163.com/s_u/blog/static/1330836720105233102894/
由于每台服务器的配置、安装的业务应用等不同,其处理能力会不一样。所以,我们根据服务器的不同处理能力,给每个服务器分配不同的权值,使其能够接受相应权值数的服务请求。
假设有一组服务器S = {S0, S1, …, Sn-1},W(Si)表示服务器Si的权值,一个指示变量i表示上一次选择的服务器,指示变量cw表示当前调度的权值,max(S)表示集合S中所有服务器的最大权值,gcd(S)表示集合S中所有服务器权值的最大公约数。变量i初始化为-1,cw初始化为零。
带权值的轮询算法是常用的选择算法,常在对选择集合中各被选元素优先级不等的集合进行选择时使用。虽然被选集合元素的优先级(以后用权值表示)不等,但在选择时需要一个当前权值来决定应该选择哪一个元素。在选择时需要从上次选择元素之后开始进行,如果循环到集合开始开始处(也即开始新一轮的选择),需要降低当前权值,然后从集合中找到首先大于权值的元素。这样随着当前权值不断降低,能够被选中的元素的范围也就由权值从大到小的顺序不断扩张。从而实现了选择的顺序从权值由高到低的顺序进行。在当前权值变化到0时,需要再次将权值置为最高,从而进行下一轮循环。
while (true) {
i = (i + 1) mod n;
if (i == 0) {
cw = cw - gcd(S);
if (cw <= 0) {
cw = max(S);
if (cw == 0)
return NULL;
}
}
if (W(Si) >= cw)
return Si;
}
http://techcodecorner.blogspot.com/2014/03/the-weighted-round-robin-schedulingis.html
class WeightedRounRobin {
Scanner sc = new Scanner(System.in);
int[] S, W;
int size, i = -1, cw = 0, max, gcd;
WeightedRounRobin(int size) {
this.size = size;
W = new int[size];
S = new int[size];
}
public void execute() {
for (int j = 0; j < size; j++) {
System.out.print("Enter weight of P" + (j + 1) + ":");
W[j] = sc.nextInt();
}
max = getMaxValue(W);
gcd = new GCD().getGcdOfArray(W);
// algorithm
System.out.println("Scheduling sequence will be as follow");
while (true) {
i = (i + 1) % size;
if (i == 0) {
cw = cw - gcd;
if (cw <= 0) {
cw = max;
if (cw == 0) {
return;
}
}
}
if (W[i] >= cw) {
System.out.print("P" + i + "\t");
}
}
}
private int gcd(int number1, int number2) //Finds GCD of 2 numbers.
{
if (number2 == 0) {
return number1;
}
return gcd(number2, number1 % number2);
}
public int getGcdOfArray(int[] arr) {
int result = arr[0];
for (int i = 1; i < arr.length; i++) {
result = gcd(result, arr[i]);
}
return result;
}
}
# 最大公约数
def gcd(nums):
m = nums[0]
for n in nums[1:]:
while n != 0:
m, n = n, m % n
return m
# Weighted Round-Robin Scheduling
def wrr_select():
current = N - 1
current_weight = 0
while True:
current = (current + 1) % N
if current == 0:
current_weight -= gcd(weight)
if current_weight <= 0:
current_weight = max(weight)
if weight[current] >= current_weight:
yield current
wrr_test = wrr_select()
for i in range(1000):
print(wrr_test.__next__())
http://www.jianshu.com/p/a6a56f107327Round-Robin Scheduling,RR
N = 3
# Round-Robin Scheduling
def rr_select():
last = N - 1
while True:
current = (last + 1) % N
last = current
yield current
rr_test = rr_select()
for i in range(1000):
print(rr_test.__next__())
http://kb.linuxvirtualserver.org/wiki/Weighted_Round-Robin_Schedulinghttps://svn.apache.org/repos/asf/cassandra/trunk/src/java/org/apache/cassandra/scheduler/RoundRobinScheduler.java
随机性考虑
WRR的运行结果是固定的,如果需要考虑随机性的话,需要再做一些额外工作。简单的话可以先对队列的顺序做随机,但这样实际的顺序还是固定的。可以按实际需要频繁暂存一定(随机)数量的结果,再随机处理后依次输出。