加权Round Robin 调度算法。
在查找的时候看到了这样一段代码,
1. j = i;
2. do{
3. j = (j+1) mod n;
4. if( ... ){
5. j = i;
6. return j;
7. }
8. } while( j != i );
....
这里的while循环颇耐人寻味,因为任何时候一进入这个循环,语句1就会执行,从而j被重新赋值,而如果if条件满足,显然while循环也是没有用的,现在我就想判断一下什么时候会执行while循环。
while循环的条件是j!=i, 首先看看如果j==i会怎么样。
进入do的时候j刚被i赋值,可以认为j = (i+1) mod n,所以如果j==i,则意味着,
(i+1) mod n == i (EQ1)
=> i + 1 == k * n + i;
=> 1 == k * n
=> k = 1 && n == 1 ( both are natural number )
也就是说,只要k=1和n=1那么上面的等式EQ1总是成立的,事实显然不是如此,比如(8+1) mod 1 == 8 是错误的,可是上面的推理中哪里产生的错误呢?
如果从另一个角度来看,则不会得出矛盾,即任何数x mod n 的结果一定是{0,n-1},由此分三种情况:
1) i >= n:肯定不相等,因为(i+1) mod n 与i不在一个数值域
2) i == n -1: (i+1) mod n == 0 , 如果i==0,则成立,这时候n-1==1,则n=1,所以,当i==0 && n==1 的时候成立
3) i < n - 1:(i+1) mod n == (i+1),i+1 != i ,所以这时候不会成立
结论,i == 0 && n == 1 的时候 (i + 1 ) mod n = i成立。
上面第二中方法并没有什么矛盾,但是第一种方法推导的过程错在哪里呢?
这样的话,也就是说任何时候
阅读(1183) | 评论(0) | 转发(0) |