第 9 章 调度：比例份额

第 9 章 调度：比例份额

核心理念：比例份额

比例份额（proportional-share）调度，也称公平份额（fair-share）调度，其核心目标是确保每个工作获得特定比例的 CPU 时间，而非优化周转时间或响应时间。

彩票调度是比例份额调度的典型实现，基本思想如下：

• 彩票抽奖：系统定期举行彩票抽奖。
• 中奖运行：中奖的进程获得下一个时间片的运行权。
• 份额控制：进程拥有的彩票越多，赢得抽奖（即获得 CPU 时间）的机会就越大。

关键问题

如何设计调度程序来按比例分配 CPU？其关键机制是什么？效率如何？

彩票调度 (Lottery Scheduling)

基本概念：彩票与份额

彩票（ticket）代表了进程占有资源的份额。

• 份额计算：进程拥有的彩票数占总票数的百分比，即为其应占有的资源比例。
• 概率实现：调度程序通过定期抽奖（如每个时间片）决定运行对象。虽然单次结果是随机的，但长期运行下，进程获得的 CPU 时间会趋于其份额比例。

随机性的优势

彩票调度利用随机性来实现决策，具有以下优势：

1. 规避边角情况：避免了传统算法（如 LRU）在特定负载下的最差表现。
2. 轻量化：几乎不需要记录历史状态（如已运行时间），只需维护拥有的彩票数。
3. 高效快捷：只要随机数生成够快，决策过程就极快。

调度示例

假设进程 A 有 75 张彩票，B 有 25 张：

• 期望：A 占 75% CPU，B 占 25%。
• 过程：从 0-99 中抽取随机数，落在 0-74 运行 A，落在 75-99 运行 B。
• 结果：短期内可能有偏差（如运行 20 次，B 仅中 4 次占 20%），但运行时间越长，实际比例越接近期望值。

彩票作为通用抽象

彩票不仅能表示 CPU 份额，还可用于内存管理等任何需要表示“所有权比例”的场景。

彩票操作机制

彩票调度提供了一些灵活的机制来管理份额：

• 彩票货币 (Ticket Currency)：允许用户在内部按需分配彩票（自定义货币），系统自动将其兑换为全局彩票。
  • 示例：用户 A 拥有 100 张全局彩票，可分给 A1、A2 各 500 张内部彩票，系统自动兑换为各 50 张全局彩票。
• 彩票转让 (Ticket Transfer)：进程可临时将彩票交给另一进程。
  • 场景：客户端/服务端交互。客户端转让彩票给服务端以加速请求处理，完成后收回。
• 彩票通胀 (Ticket Inflation)：进程在相互信任的环境下，可以临时提升或降低自己的彩票数量，以调节获取 CPU 时间的优先级。

机制总结

这些机制增强了调度的灵活性，使得资源分配能够适应复杂的应用场景（如多用户管理、同步协作等）。

实现与算法

彩票调度的实现非常简单，核心只需：一个随机数生成器、一个进程列表以及彩票总数。

调度逻辑

1. 抽取中奖号码：从 0 到彩票总数之间随机选取一个值 winner。
2. 遍历查找：遍历进程列表，累加各进程的彩票数，直到累加值超过 winner。

// counter: 累加器，用于寻找中奖者
int counter = 0; 
 
// winner: 随机生成 0 到 totaltickets 之间的中奖号码
int winner = getrandom(0, totaltickets); 
 
// current: 遍历进程链表
node_t *current = head; 
 
while (current) { 
    counter = counter + current->tickets; 
    if (counter > winner) 
        break; // 找到中奖者
    current = current->next; 
} 
// 'current' 即为中奖进程，加载并运行它

性能优化

为了提高查找效率，可以将进程列表按彩票数递减排序。这样可以确保彩票数最多的进程排在前面，从而在大多数情况下以最少的迭代次数找到中奖者。

公平性评估

为了衡量彩票调度的效果，我们引入不公平指标 $U$ (Unfairness metric)：

• 定义：$U=\frac{\text{第一个工作完成时间}}{\text{第二个工作完成时间}}$。
• 目标：完美的公平调度程序 $U=1$。

实验表明（如图 9.2）：

• 短作业：平均不公平度较差，随机性波动明显。
• 长作业：随着运行时间增加，实际分配比例趋于期望值，$U$ 指标逐渐接近 1。

结论：彩票调度在作业运行时间较长时，才能更有效地实现公平份额。

步长调度 (Stride Scheduling)

虽然彩票调度实现简单，但在短时间内无法保证精确的比例。步长调度是一种确定性的公平分配算法。

核心概念

• 步长 (Stride)：与票数成反比。计算方式：$Stride=\frac{\text{大常数}}{\text{票数}}$。
• 行程值 (Pass)：记录进程的总体进展。每次运行后，行程值增加其步长：$Pass=Pass+Stride$。
• 调度策略：每次选择当前行程值最小的进程运行。

current = remove_min(queue);       // 选择行程值最小的进程
schedule(current);                 // 运行一个时间片
current->pass += current->stride;  // 更新行程值
insert(queue, current);            // 放回队列

调度示例

假设 A、B、C 步长分别为 100、200、40，初始行程值均为 0：

行程值 (A) (步长=100)	行程值 (B) (步长=200)	行程值 (C) (步长=40)	谁运行
0	0	0	A
100	0	0	B
100	200	0	C
100	200	40	C
100	200	80	C
100	200	120	A
200	200	120	C
200	200	160	C
200	200	200	……

结论：步长调度在每个周期内都能精确维持份额比例。

方案对比：彩票 vs 步长

算法	优势	劣势
彩票调度	无全局状态：新进程加入只需更新总票数，处理新进程更合理。	概率公平，短时间内可能不准确。
步长调度	精确公平：每个调度周期都能达到预期的比例。	需要全局状态：新进程加入时行程值难以初始化（若设为 0 会独占 CPU）。

总结

彩票分配（如何确定每个工作的票数）目前仍是一个开放性问题，没有最佳答案。