步幅调度与虚拟服务账本

十二次选择，每次只改胜者的pass ​

胜者序列是A、B、A、A、B、C，再重复一次。A取得6片，B取得4片，C取得2片，恰为目标份额。这个“恰好”依赖本组权重和窗口；前5片的计数为3、2、0，C的理想份额是 $5/6$，并未恰好实现。

选择后pass也不必相同。第12片之后C的18大于A的14，表示C下一次应当更晚取得机会，不表示C已经获得比A更多的真实服务。

账本为什么不会无限拉开 ​

令 $D=\underset{i}{max}{d}_i$。在本页固定成员、完整时间片、精确数值的模型里，始终有

初始 $P_i=d_i$，这个界显然成立。假设某次选择前最小pass为 $m$，所有pass都在 $[m,m+D]$ 中。只更新一个最小者，给它加不超过 $D$ 的步幅，更新后的它仍不超过 $m+D$；其余不变，且没有pass下降。因此新的最大最小之差仍不超过 $D$。归纳完成。

设任务 $i$ 已取得 $n_i$ 个完整片，由初始化和每次更新直接得到

上面的界限制的是各任务“下一次虚拟位置”的差。代入后得到

右边是与总运行片数无关的常数，所以运行越来越久时，各任务按票数归一化的累计服务不会越来越偏离。在固定有限成员下，结合 $\sum _i{n}_i=m$，可以推出 $n_i/m\to w_i/\sum _j{w}_j$。

这不是“每项任意时刻都误差小于一片”的证明。原论文另区分两两相对误差与整个集合的绝对误差；对偏斜权重，二者的界不同。本页只使用已经给出归纳推导的虚拟差界。

为什么固定成员不会永远被跳过 ​

假设C的当前pass固定为某值 $H$，此后永远未被选。其他任务只要仍以小于或等于 $H$ 的pass抢在C前面，每次选中就加一个固定正步幅。每个这样的任务能在 $H$ 以下运行的次数有限，任务总数也有限，最后必轮到C，与“永远不选”矛盾。

这解释固定正票数下的无饥饿；它不等于对任意动态到达流、任意暂停和任意整数溢出实现都给出了同一个等待界。特别是如果允许不断加入pass极小的新任务，刚才“其他任务总数有限”的论证就失效。

一小片服务，只应收费一小份 ​

若标准片长为 $q$，任务本次实际只消耗 $u$，则相应扩展把pass增加改为

例如A步幅2、标准片1，本次只运行0.25毫秒，增加应为0.5，而不是2。若原pass为2，更新为2.5，表示这次只取得了四分之一片的服务。按完整片收费，会让频繁短片任务的虚拟账本走得过快，从而拿到过少CPU。

本次让出后若任务阻塞，就先从候选队列移除，不能因为pass小而调度一个尚未就绪的任务。等它重新加入时，还必须明确下面的动态加入规则；不能只改短片公式就声称完成了动态协议。

新加入者不能永远从历史的零点开始 ​

设旧任务pass已经在100附近。若新任务每次创建都设pass为0，它会连续获得许多机会追赶到100；反复创建新身份可以反复领取这份并不属于它的历史补偿。反过来，长期睡眠者保存的旧pass也可能远落后于当前系统进度。

原论文的动态版本维护全局虚拟进度，离开时保存相对于全局进度的剩余距离，回来时重新放置；改变票数还要按新旧步幅比例调整剩余距离。它不是简单地把所有新任务设为0，也不是每次权重变化把所有历史清零。动态版本的完整规则应以原文§2.2–2.4为准，本页十二片证明只覆盖静态版本。

若只是在一个封闭批次开始前把所有pass减去同一个常数，大小次序不变；但运行中对部分任务单独重置会改变次序。防止数值溢出的归一化必须覆盖同一个比较域，不能让一部分睡眠记录仍停在旧坐标系。

实现代价与模型边界 ​

最小优先队列理路优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。可用于按pass取任务、更新后重插，二叉堆每次为 $O(\log n)$，另计实际上下文交接。票数很大、$K$很小时，整数除法可能把步幅截成0，任务再也不向前推进；应选择有足够精度的表示并验证所有有效步幅严格为正。

按CPU时间取得3:2:1不意味着业务吞吐也按3:2:1。缓存状态、锁等待、I/O及不同处理器速度会使同样的服务时间产生不同产出。调度器保证的对象必须与服务账本理路CPU服务、就绪与时间账本CPU service accounting · CPU burst · Ready time · Preemptive scheduling model用实际服务量、剩余量和就绪等待刻画单核调度，固定同刻事件顺序，并把墙钟时间分成运行、阻塞和等待。一致，而不是由“公平”两个字替代。