Lottery Scheduling 基本机制

Resource Rights (资源权利)

  • 彩票 (ticket) 表示资源权利, 具有 三个性质:
    • 抽象 (abstract): 与具体机器细节无关;
    • 相对 (relative): 票所代表的份额随竞争情况 (总彩票数量) 动态变化;
    • 统一 (uniform): 异构资源都能抽象为 tickets; 比如各种 CPU, I/O 设备;

Lotteries (抽签调度)

  • 每次调度就是一次抽签, 任务的获胜概率: p=tTp = \frac{t}{T}, 其中 t = 本任务票数, T = 总票数;

  • 获胜次数服从 binomial distribution; 等待第一次获胜的时间服从 geometric distribution;

  • 长期看, 任务的资源份额 ≈\approx 票份额; 因此保证概率公平 (probabilistic fairness);

  • 任何持有 非零 票数的任务都会在有限时间内赢得抽签, 因此不会出现饿死 (starvation);

  • 问题: 如果一个任务的彩票数量很少, 为什么不会 starvation? 它被运行的概率不是应该很低吗?

  • 回答: 只要任务持有的票数大于零, 它在每次抽签中都有非零的获胜概率;虽然概率可能很小, 但等待时间服从几何分布, 期望为 1/p, 是有限的;因此平均响应时间有限, 任务最终一定会运行, 不会像传统优先级调度中那样被永久饿死;

Modular Resource Management (模块化资源管理)

论文引入 tickets 作为一等公民对象 (first-class objects), 可 传递, 转移, 膨胀, 货币化, 用于模块化的资源管理;

  • 模块化 (modular) 在这里指: 不同的子系统, 用户, 应用, 甚至线程, 可以独立地(independently)管理自己的资源分配策略, 而不需要与其他部分紧密耦合; -> Currency 内部的管理是其自己管理的
  • 换句话说, 调度策略不再是单一的, 全局固定的(像传统的优先级调度), 而是允许 并行存在多个"局部调度策略", 它们通过彩票(tickets)来在系统级别汇总;

Ticket Transfers(票据转移)

  • 当任务因依赖阻塞时, 可以把票转让给等待的对象(如 RPC client →\rightarrow server);
    • 线程 A 正在等待线程 B 的结果, A 可以把自己的票转给 B;
  • 解决优先级反转 (priority inversion) 问题;

Ticket Inflation(票据膨胀)

  • 任务可以通过"造票"提升调度权;
  • 一般禁止, 因为会破坏模块化与隔离性 (insulation);
  • 在互相信任的环境下, 可以用于方便地调整份额;

Ticket Currencies(票据货币)

  • 每个 group 或用户可以定义自己的 currency;
  • 一个 currency 由更基础的 backing tickets 支撑;
  • Currency 可以组成层级(acyclic graph), 支持汇率换算;
  • 作用: 隔离膨胀效应, 跨信任边界保护, 灵活共享;

问题: 这里的 insulation 具体指什么?
回答: insulation 表示 隔离保护, 保证一个模块的资源管理策略不会影响其他模块; 通过 currency 抽象, 每个模块可以在自己内部自由调整, 而不会稀释其他模块的权利;

问题: 一个 ticket 可以在多个 currency 体系中吗?
回答: 不可以; 一张 ticket 总是以某个 currency 计价; 跨 currency 的比较依赖于将票值换算成基准货币 (base currency);

问题: 不同 currency 之间的 ticket 汇率是统一的吗? 比如 Alice 1000 票和 Bob 2000 票二者的权重就是 1:2?
回答: 所有票最终都会转换为 base 货币单位下的值, 因此跨 currency 比较是统一的; 但具体汇率是动态的, 取决于 currency 的 active amount sum 和 backing value (base ticket 总量);例如 Alice currency backed by 1000 base, 但只有 500 active tickets, 那么每张 Alice 票的价值就提升一倍;

问题: fund/unfund 的含义是什么?
回答: fund 表示给某个 currency 添加 backing tickets, 相当于注资, 增加该 currency 的全局权重; unfund 表示撤资, 移除 backing tickets, 减少其份额;这是操作系统管理员或上层模块动态调整资源分配的手段; 也就是说, currency 之间的调度公平是基于 base ticket 总量来公平分配的

Compensation Tickets(补偿票)

  • 当任务只使用了部分时间片 (f) 时, 系统会给它一个补偿票, 票值放大为 1/f;
  • 确保 I/O-bound 任务不会因提前释放 CPU 而长期吃亏;

Implementation(实现)

随机数

  • 使用 Park-Miller 算法生成均匀分布的随机数, 效率高;

Lotteries 实现方式

  • 最简单: 顺序遍历任务列表, 时间复杂度 O(n);
  • 优化方法:
    • Move-to-front 启发式: 根据拥有票数排序从多到少, 这样热门任务更快找到;
    • 部分和树 (tree of partial sums), 可以在 O(log n) 内找到获胜者;

Mach 内核接口

  • 提供最小接口: 创建/销毁 tickets 和 currencies, fund/unfund, 计算票值;
  • 与标准 timesharing, fixed priority 共存;

Ticket Currencies(票据货币转换)

  • 每个 currency 维护 active amount sum;
  • 当线程阻塞 →\rightarrow 它的票 inactive; 重新 runnable →\rightarrow 票 reactivated;
  • 如果某个 currency active sum = 0 →\rightarrow 递归停用 backing tickets;
  • 票值公式: ticket value=ticket amountcurrency active sum×currency valueticket\ value = \frac{ticket\ amount}{currency\ active\ sum} \times currency\ value
  • 多 currency 调度时: 先在基准单位里生成一个获胜值, 再遍历队列, 累加票值直到超过该值;

问题: 货币和 ticket 究竟是什么关系? 为什么变成 0 之后就要消除所有 ticket?
回答: ticket 是以 currency 计价的调度凭证, currency 则由 backing tickets 提供价值;当某 currency 下没有活跃票时, 意味着没有线程使用这种货币;如果仍让 backing tickets 占用资源, 会虚增全局总票数, 破坏公平性;因此需要递归停用 backing tickets, 避免资源计算失真;

问题: 在调度系统中, 一般 currency 系统是包含了多少粒度的内容?
回答: currency 可以设计在多个粒度层次: 用户级, 组级, 应用级, 线程级; 实际系统中常见的是 用户级或应用级, 因为它们对应操作系统或集群调度器中的资源配额; 更细的线程级虽然可能, 但通常由上层 currency 来统一管理;

Compensation Tickets(补偿票实现)

  • 当任务只用部分时间片 (f), 获得补偿票, 确保长期公平;
    • 但不同任务对 CPU 的使用方式不同:
      • CPU-bound 任务: 通常会用满整个时间片, 比如 100ms;
      • I/O-bound 任务: 可能只用了一部分时间片(例如 20ms)就主动阻塞等待 I/O;
    • 如果不做任何修正, I/O-bound 任务会"吃亏":
      • 它赢得了一个完整的 quantum, 但实际消耗的 CPU 资源远小于应得的份额;
      • 长期看, 它得到的实际资源份额会比它的票数应得的少;
    • 补偿机制 (compensation tickets) 就是为了解决这个问题:
      • 当一个任务只用了量子的一部分 (f), 在它下次参与调度时, 系统给它一个额外的补偿票, 票值放大为 1/f 倍;
      • 这样它下一次赢得调度的概率会变大, 从而弥补上一次没有消耗的份额
  • 例子: 线程 A, B 各持 400 base, A 用满 100ms, B 只用 20ms (f=1/5), 那么 B 下一次会得到一张 1600 base 的补偿票, 总值 2000 base; 这样 B 赢的概率提升, 保证它长期 CPU 有效占用与 A 持平;

Ticket Transfers(Mach 消息系统支持)

  • 在 mach_msg 中实现同步 RPC 时, 自动转移 client 的票给 server;
  • 这样 client 在阻塞时的权利被传递给 server, 用于快速完成请求, 避免优先级反转;

用户接口

  • 提供命令行工具: mktkt, rmtkt, mkcur, rmcur, fund, unfund, lstkt, lscur, fundx;
  • 因为 Mach 内核没有用户概念, 这些命令以 root 权限运行;