Stride 调度算法

复制本地路径 | 在线编辑

简单介绍

每个任务都有一个权重，表示它希望占用 CPU 的比例。调度器为每个任务维护一个 stride 值（步长）： stride = 大整数 / 权重。

权重越大，stride 越小 → 任务会更频繁地被调度。每次调度，选择 pass 值最小的任务，执行后，pass 加上 stride。

问题：假设表示 pass 用四位，那么对于 0011，如何判断他是 3，还是已经过了一轮，即已经是 19 了？

解答：

假设大整数叫做 BIG_STRIDE，显然，PASS < BIG_STRIDE。假设把溢出给去掉，即假设计算机可以表示无限大的数，那么对于进程 A 和进程 B 来说，|A_stride - B_stride| < BIG_STRIDE。这个是可以证明的，利用数学归纳法就好咯。很简单~

有了公式 |A_Stride - B_Stride| < BIG_STRIDE，我们可以根据它进行判断。

规定: stride 用无符号存，但是比较是利用有符号。

假设 A 的 stride 为 0011：
- 如果 B 的 stride 为 0110，很显然，此时 B_stride > A_stride.
- 如果 B 的 stride 为 1000，此时 B 如果溢出了，那就是 8

有两种情况: A就没有溢出过，A溢出之后又溢出：
- 第一种: A = 3, |A-B| < 7，通过。
- 第二种: A = 19, |A-B| > 7，失败。

由于第二种违反了 |A_stride - B_stride| < BIG_STRIDE，所以就能判断出是第一种。

当然实际系统中都会用足够大的整数，32 位和 64 位...