文章详情

  • 游戏榜单
  • 软件榜单
关闭导航
热搜榜
热门下载
热门标签
php爱好者> php文档>Weighted Round-Robin Scheduling 和一个奇怪的推导

Weighted Round-Robin Scheduling 和一个奇怪的推导

时间:2009-04-05  来源:raymond1984

http://kb.linuxvirtualserver.org/wiki/Weighted_Round-Robin_Scheduling

加权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成立。

上面第二中方法并没有什么矛盾,但是第一种方法推导的过程错在哪里呢?
这样的话,也就是说任何时候
相关阅读 更多 +
排行榜 更多 +
暗黑封魔录手游

暗黑封魔录手游

角色扮演 下载
战国美人游戏

战国美人游戏

角色扮演 下载
仙境苍穹手游

仙境苍穹手游

角色扮演 下载