调度：比例份额

票券对应期望份额

比例共享调度不再把最短完成时间或最快响应当作首要目标，而是让每个作业获得与其票数成正比的处理器时间。系统记录全部票券的总和，每次时间片开始时从该范围内均匀抽出一个号码，拥有该号码的作业立即投入运行。票数越多，被抽中的机会越大，长期来看实际占用比例就会贴近票数比例。

随机抽奖的实现步骤

实现时只需维护作业链表及其票数。抽出获胜号码后，从链表头开始累加各作业票数，一旦累加值超过获胜号码就停止，当前作业即为胜者。把票数多的作业放在链表前面可以缩短平均查找长度，但顺序并不影响正确性。因为每次抽奖相互独立，短时间内实际比例会出现明显起伏。

票券的三种实用操作

用户可以先在自己的局部货币里给下属作业分票，系统再按比例换算成全局票券。客户作业可以把票临时转给正在为自己服务的服务器，让服务器在处理请求期间获得更高优先级，完成后再把票收回。在彼此信任的作业集合里，某个作业还可以自行增减票数来表达瞬时需求，无需再与其他作业协商。

公平性随运行长度改善

因为每次决策都是独立随机事件，作业运行时间越短，实际获得的时间片数就越可能偏离票数比例。随着竞争持续进行，大数定律逐渐发挥作用，观察到的份额会越来越接近票券所代表的目标比例。因此该方法特别适合运行时间较长、对精确瞬时公平要求不高的场景。

常见误区

• 把随机抽奖误当成确定性配额，以为短作业也能精确拿到票数对应的时间。
• 在互不信任的环境里允许作业自行膨胀票数，结果某个作业轻易独占全部处理器。
• 使用质量很差的伪随机数，导致即使运行很久份额仍无法收敛到期望值。

最低标准 C11 · 完整程序 · 下载 .c

#include <stdio.h>

int main(void) {
    int tickets[2] = {75, 25};
    char names[2] = {'A', 'B'};
    int winners[20] = {42, 81, 15, 67, 92, 3, 55, 78, 29, 88, 11, 60, 73, 95, 8, 34, 49, 71, 19, 84};
    printf("Winning tickets: ");
    for (int i = 0; i < 20; i++) {
        printf("%d ", winners[i]);
    }
    printf("\nSchedule: ");
    for (int i = 0; i < 20; i++) {
        int winner = winners[i];
        int counter = 0;
        int j;
        for (j = 0; j < 2; j++) {
            counter += tickets[j];
            if (counter > winner) {
                break;
            }
        }
        printf("%c ", names[j]);
    }
    printf("\n");
    return 0;
}

在本地编译

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-09-lottery.c -o example && ./example

预期结果

Winning tickets: 42 81 15 67 92 3 55 78 29 88 11 60 73 95 8 34 49 71 19 84 
Schedule: A B A A B A A B A B A A A B A A A A A B 

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

作业P持有65张票，作业Q持有35张票。请任意给出5个介于0到99的获胜号码，并写出对应的运行序列。为什么这5次抽奖几乎不可能正好出现3.25:1.75的比例？

继续查证

• OSTEP chapter PDF

标准草案与官方章节会更新；版本标记只说明示例最低要求。