《Operating Systems: Three Easy Pieces》学习笔记(七) 调度：比例份额

本章将介绍一种不同的调度方法–比例份额（proportional-share）调度，有时也称为公平份额（fair-share）调度程序。比例份额算法基于一个简单的想法：调 度程序的最终目标，是确保每个工作获得一定比例的 CPU 时间，而不是优化周转时间和响 应时间。

比例份额调度程序有一个非常优秀的现代例子，由 Waldspurger 和 Weihl 发现，名为彩票调度（lottery scheduling）。基本思想很简 单：每隔一段时间，都会举行一次彩票抽奖，以确定接下来应该运行哪个进程。越是应该频繁运行的进程，越是应该拥有更多地赢得彩票的机会。

基本概念：彩票数表示份额

彩票调度背后是一个非常基本的概念：彩票数（ticket）代表了进程（或用户或其他）占有某个资源的份额。一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。

下面来看一个例子。假设有两个进程 A 和 B，A 拥有 75 张彩票，B 拥有 25 张。因此我们希望 A 占用 75%的 CPU 时间，而 B 占用 25%。

通过不断定时地（比如，每个时间片）抽取彩票，彩票调度从概率上（但不是确定的） 获得这种份额比例。抽取彩票的过程很简单：调度程序知道总共的彩票数（在我们的例子中，有 100 张）。调度程序随机抽取中奖彩票，这是从 0 和 99 之间的一个数，拥有这个数对应 的彩票的进程中奖。假设进程 A 拥有 0 到 74 共 75 张彩票，进程 B 拥有 75 到 99 的 25 张，中奖的彩票就决定了运行 A 或 B。调度程序然后加载中奖进程的状态，并运行它。

随机性决策优势：

• 避免最差情况
• 轻量，不需要记录过多状态，传统公平调度需要记录进程的大量状态
• 随机方法很快，决策也快

下面是彩票调度程序输出的中奖彩票和对应的调度结果:

63	85	70	39	76	17	29	41	36	39	10	99	68	83	63	62	43	0	49	49
A		A	A		A	A	A	A	A	A		A		A	A	A	A	A	A
	B			B							B		B

从这个例子中可以看出，彩票调度中利用了随机性，这导致了从概率上满足期望的比例，但并不能确保。在上面的例子中，工作 B 运行了 20 个时间片中的 4 个，只是占了20%，而不是期望的25%。但是，这两个工作运行得时间越长，它们得到的 CPU 时间比例就会越接近期望。

彩票机制

彩票调度还提供了一些机制，以不同且有效的方式来调度彩票。一种方式是利用彩票货币（ticket currency）的概念。这种方式允许拥有一组彩票的用户以他们喜欢的某种货币， 将彩票分给自己的不同工作。之后操作系统再自动将这种货币兑换为正确的全局彩票。

比如，假设用户 A 和用户 B 每人拥有 100 张彩票。用户 A 有两个工作 A1 和 A2，他以自己的货币，给每个工作 500 张彩票货币（共 1000 张）。用户 B 只运行一个工作，给它 10 张彩票货币（总共 10 张）。操作系统将进行兑换，将 A1 和 A2 拥有的 A 的彩票货币 500 张，兑换成彩票 50 张。类似地，兑换给 B1 的 10 张彩票货币兑换成彩票 100 张。然后会对全局彩票货币（共 200 张）举行抽奖，决定哪个工作运行。

User A

-> 500 (A's ticket currency) to A1 -> 50 (global currency)

-> 500 (A's ticket currency) to A2 -> 50 (global currency)

User B

-> 10 (B's ticket currency) to B1 -> 100 (global currency)

另一个有用的机制是彩票转让（ticket transfer）。通过转让，一个进程可以临时将自己的彩票交给另一个进程。这种机制在客户端/服务端交互的场景中尤其有用，在这种场景中，客户端进程向服务端发送消息，请求其按自己的需求执行工作，为了加速服务端的执行，客户端可以将自己的彩票转让给服务端，从而尽可能加速服务端执行自己请求的速度。服务端执行结束后会将这部分彩票归还给客户端。这在客户端和服务端在同一台机器上运行时有用。

最后，彩票通胀（ticket inflation）有时也很有用。利用通胀，一个进程可以临时提升降低自己拥有的彩票数量。当然在竞争环境中，进程之间互相不信任，这种机制就没什么意义。一个贪婪的进程可能给自己非常多的彩票，从而接管机器。但是，通胀可以用于进程之间相互信任的环境。在这种情况下，如果一个进程知道它需要更多 CPU 时间，就可以增加自己的彩票，从而将自己的需求告知操作系统，这一切不需要与任何其他进程通信。

实现

假定我们用列表记录进程。下面的例子中有 A、B、C 这 3 个进程，每个进程有一定数 量的彩票。

在做出调度决策之前，首先要从彩票总数 400 中选择一个随机数（中奖号码）。假设 选择了 300。然后，遍历链表，用一个简单的计数器帮助我们找到中奖者

// counter: used to track if we've found the winner yet
int counter = 0;
// winner: use some call to a random number generator to get a value, between 0 and the total # of tickets
int winner = getrandom(0, totaltickets);
// current: use this to walk through the list of jobs
node_t *current = head;
// loop until the sum of ticket values is > the winner
while (current) {
    counter = counter + current->tickets;
    if (counter > winner)
        break; // found the winner
    current = current->next;
}
// 'current' is the winner: schedule it...

这段代码从前向后遍历进程列表，将每张票的值加到 counter 上，直到值超过 winner。

A:100,B:50,C:250，总计 400 票，按照 A、B、C 的方式排序，如果摇到 1-100，则 A 中奖，101-150 则 B 中奖，151-400 则 C 中奖，符合概率分布。也就是 counter 递增的原理

要让这个过程更有效率，建议将列表项按照彩票数递减排序。这个顺序并不会影响算法的正确性，但能保证用最小的迭代次数找到需要的结点，尤其当大多数彩票被少数进程掌握时。

评估方法

公平性

我们定义了一个简单的不公平指标U（unfairness metric），将两个工作完成时刻相除得到 U 的值。比如，运行时间 R 为 10，第一个工作在时刻 10 完成，另一个在 20，U=10/20=0.5。如果两个工作几乎同时完成，U 的值将很接近于 1。在这种情况下，我们的目标是：完美的公平调度程序可以做到U=1。

当工作执行时间很短时，平均不公平度非常糟糕。只有当工作执行非常多的时间片时，彩票调度算法才能得到期望的结果。

步长调度

假设，A:100,B:50,C:250，总计 400 票，使用 10000 除以票数，得到步长A:100,B:200,C:40。每次程序被调度，每个工作对应的计数器累加得到行程值。

规则是总是调度行程值最低的工作，初始都是 0，则按顺序 A 执行，A 的行程值变为 100，BC 还为 0，则 B 运行，然后 C 运行，此时行程是 A:100,B:200,C:40，C 最小，则 C 再运行，直到 120，此时 A 为 100 最小，调度 A。

这种调度可以保证每个周期内绝对公平，但无法处理新进程插入后的情况

小结

不能很好适应 I/O，票数分配规则没有好的方案

作业

参考

• Operating Systems: Three Easy Pieces 中文版