彩票调度与随机服务份额

十二次实际抽签并不必然恰好按比例 ​

给定下面一条用于复算的票序列。它是明确输入，不把它称为来自某个未记录的随机种子：

依区间映射，胜者为

A取得7片，B取得3片，C取得2片，累计服务就是7、3、2毫秒。目标比例对应12片中的6、4、2，因此这次偏差为 $(+1,-1,0)$。偏离均值不表示抽签算法错误，也不能只因C恰好取得2就说该轨迹“完全公平”。

要复现实验，应保存抽签输出或精确的伪随机算法、种子和调用次序。只保存“使用随机调度”不足以重现某一张时间表。

期望份额与有限窗口误差 ​

保持资格集合和票数固定，每片等长且抽签独立。令 $X_i$ 为 $m$ 次抽签中任务 $i$ 的胜出次数，那么每次“是否胜出”是成功概率 $p_i$ 的二值试验，故

二项分布理路二项分布Binomial distribution固定次数独立同概率 Bernoulli 试验中成功总数的离散分布。是这里分析重复抽签的工具。它不参与调度器选人的代码；即使不计算方差，也可以执行上述票区间算法。

在12片实验中，A的期望为6，方差为3；B的期望为4，方差为 $8/3$；C的期望为2，方差为 $5/3$。不同任务的次数不是相互独立，因为它们相加恒为12，一项多拿必有其他项少拿。

份额 $X_i/m$ 的方差为 $p_i(1-p_i)/m$，因此增加窗口能降低份额波动的尺度。不过“长期接近”没有给出每个短窗口恰好按比例的承诺，任意一个固定有限窗口里都可能出现明显偏差。

正概率不等于有确定等待上界 ​

C一次不中签的概率为 $5/6$，连续12次不中签的概率为

所以“平均每6次中1次”绝不等于“最多等6次”。若希望在当前固定模型下，至少一次选到C的概率不低于95%，需要

$m=16$时尚不够，$m=17$时才达到要求；它仍是概率保证，不是第17次一定会中的硬截止期。

对固定 $p_i>0$，$\underset{m\to \mathrm{\infty }}{lim}(1-p_i{)}^m=0$，因此无限重复独立抽签时，某个持续可运行任务永远不中签的概率为0。有限多个任务都无限次取得机会也可由同样的后缀论证得到。这种“几乎必然”结论没有给所有可能样本路径统一的有限等待界，与确定有界等待理路饥饿与公平性Starvation and fairness · 调度公平性 · 无饥饿用调度与服务选择的公平假设刻画持续请求者是否可能永久得不到完成机会。不同。

若票比例随着到达不断下降，则固定 $p_i$ 的计算不再适用；若伪随机序列有偏或相关，也不能直接套独立二项分布。必须先检查随机性与资格集合的假设，再报告概率。

分配次数与实际服务要分开 ​

前面的份额推导依赖每片长度相同。若A、B各有一张票，而A每次运行1毫秒、B每次只运行0.25毫秒就让出，即使两者长期胜出次数接近，A取得的CPU服务也会约为B的四倍。按“中了几次”记账会高估B的服务。

原始彩票调度提出补偿票等机制处理短片：按消耗比例临时调整后续竞争权重。本页不把补偿规则混入固定独立抽签实验；一旦权重随上次运行改变，前面简单的二项分布就不是整段运行的直接模型。步幅调度理路步幅调度与虚拟服务账本Stride scheduling · Proportional-share stride scheduler · Virtual pass按票数倒数设置步幅，每次运行最小pass者并按实际服务推进，复算十二片序列，证明固定成员下的有界虚拟差并说明加入和短片边界。可以直接把实际片长计入虚拟服务增量，提供另一个对照。

休眠任务也不积累一张“以后补回所有错失CPU”的欠条。本页的份额只在共同参与竞争的时间里定义；若要支持额度积累或预约，需要另行规定配额周期与上限。

谁能分票，也是政策的一部分 ​

假如系统只约定“每个进程给100票”，一个用户创建十个进程就能获得1000票。若想保护用户之间的份额，应先给用户固定总预算，再由其内部拆分，或采用原论文的票券货币/层次结构。

一个简单例子是用户U、V各有6张全局票。U把其中4给U1、2给U2，V全部给V1。三任务概率为 $1/3,1/6,1/2$，U两个任务合计仍为 $1/2$。若U可以无条件额外铸票，这个用户级保证就消失。

线性扫描 $n$ 个任务选择区间，最坏为 $O(n)$；维护累计权重树可把抽样查找与单项权重更新做到 $O(\log n)$。还要计随机数生成、票数溢出和无偏区间采样的成本，不能用带模偏差的随机整数取余悄悄改变票概率。