Chinaunix首页 | 论坛 | 博客
  • 博客访问: 179764
  • 博文数量: 36
  • 博客积分: 2510
  • 博客等级: 少校
  • 技术积分: 410
  • 用 户 组: 普通用户
  • 注册时间: 2009-04-04 12:39
文章分类

全部博文(36)

文章存档

2010年(1)

2009年(35)

我的朋友

分类: LINUX

2009-04-05 18:00:42



加权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) |
给主人留下些什么吧!~~