type
status
date
slug
summary
tags
category
icon
password
Property
Apr 15, 2023 03:23 PM
比例份额（proportional-share）调度程序，有时也称为
公平份额（fair-share）调度程序，它基于一个简单的想法：调度程序的最终目标，是确保每一个工作获得一定比例的cpu时间，而不是优化周转时间和响应时间。比例份额调度程序有一个非常优秀的现代例子，由 Waldspurger 和 Weihl 发现，名为彩票调度（lottery scheduling）。基本思想很简单：每隔一段时间，都会举行一次彩票抽奖，以确定接下来应该运行哪个进程。越是应该频繁运行的进程，越是应该拥有更多地赢得彩票的机会。关键问题：如何设计调度程序来按比例分配cpu？其关键机制是什么？效率如何？
基本概念：彩票数表示份额
彩票调度背后是一个非常基本的概念：
彩票数（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这三个进程，每个进程有一定数量的彩票。
在做出调度决策之前，首先要从彩票总数
400 中选择一个随机数（中奖号码）。假设 选择了 300。然后，遍历链表，用一个简单的计数器帮助我们找到中奖者这段代码从前向后
遍历进程列表，将每张票的值加到 counter 上，直到值超过 winner。A:100,B:50,C:250，总计 400 票，按照 A、B、C 的方式排序，如果摇到 1-100，则 A 中奖，101-150 则 B 中奖，151-400 则 C 中奖，符合概率分布。也就是 counter 递增的原理
要让这个过程更有效率，建议将列表项按照彩票数
递减排序。这个顺序并不会影响算法的正确性，但能保证用最小的迭代次数找到需要的结点，尤其当大多数彩票被少数进程掌握时。一个例子
为了更好的理解彩票调度的完成过程，我们现在简单研究一下两个互相竞争工作的完成时间，每个工作都有相同的100张彩票，以及相同的运行时间R（稍后会改变）。
这种情况下，我们希望两个工作大约同时完成，但是由于算法的随机性，有时一个工作会先于另一个工作完成。
为了量化这种区别，我们定义了一个简单的
不公平指标U（unfairness metric），将两个工作完成时刻相除得到 U 的值。比如，运行时间 R 为 10，第一个工作在时刻 10 完成，另一个在 20，U=10/20=0.5。如果两个工作几乎同时完成，U 的值将很接近于 1。在这种情况下，我们的目标是：完美的公平调度程序可以做到U=1。当工作执行时间很短时，平均不公平度非常糟糕。只有当工作执行非常多的时间片时，彩票调度算法才能得到期望的结果。
如何分配彩票
系统的运行严重依赖于彩票的分配，但是目前来说还是没有最佳答案。
步长调度算法
虽然随机性使得调度程序的实现简单（且大致正确），但偶尔不能产生正确的比例，尤其在工作时间很短的情况下。由于这个原因，Waldspurger提出了步长调度（stride scheduling）—— 一个确定时间公平性的算法。
系统中每个工作都有自己的
步长， 这个值与票数成反比。我们用一个大数分别处以他们的票数来获得每个进程的步长（stride）。每次进程运行后，我们会让它的计数器（称为行程（pass）值）增加他的步长，记录他的总体进展。之后，调度程序使用进程的步长及行程值来确定调度哪个进程。基本思路很简单：当需要调度时，选择目前拥有
最小进程的进程，并且在运行之后将该进程的行程值增加一个步长。假设，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
- 票数分配规则没有好的方案
参考
- 作者:GJJ
- 链接:https://blog.gaojj.cn/article/blog-08
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。