【 *** 作系统笔记】第九章—彩票调度

【 *** 作系统笔记】第九章—彩票调度 知识点 彩票调度

彩票数（ticket）代表了进程（或用户或其他）占有某个资源的份额。一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。

一个简单的例子

优势

彩票调度最精彩的地方在于利用了随机性
随机方法相对于传统的决策方式，至少有 3 点优势。

第一，随机方法常常可以避免奇怪的边角情况
第二，随机方法很轻量，几乎不需要记录任何状态。
第三，随机方法很快。只要能很快地产生随机数，做出决策就很快

彩票调度机制

1、一种方式是利用彩票货币（ticket currency）的概念。这种方式允许拥有一组彩票的用户以他们喜欢的某种货币，将彩票分给自己的不同工作。之后 *** 作系统再自动将这种货币兑换为正确的全局彩票。

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

2、彩票转让，一个进程可以临时将自己的彩票交给另一个进程。

3、彩票通胀（ticket inflation）有时也很有用。利用通胀，一个进程可以临时提升或降低自己拥有的彩票数量。

代码实现

要让这个过程更有效率，建议将列表项按照彩票数递减排序

1 // counter: used to track if we've found the winner yet
2 int counter = 0;
3
4 // winner: use some call to a random number generator to
5 // get a value, between 0 and the total # of tickets
6 int winner = getrandom(0, totaltickets);
7
8 // current: use this to walk through the list of jobs
9 node_t *current = head;
10
11 // loop until the sum of ticket values is > the winner
12 while (current) {
13 counter = counter + current->tickets;
14 if (counter > winner)
15 break; // found the winner
16 current = current->next;
17 }
18 // 'current' is the winner: schedule it...

步长调度

确定性的公平分配算法

步长调度也很简单。系统中的每个工作都有自己的步长，这个值与票数值成反比。当需要进行调度时，选择目前拥有最小行程值的进程，并且在运行之后将该进程的行程值增加一个步长。

一个例子

A、B、C 这3 个工作的票数分别是100、50 和250，我们通过用一个大数分别除以他们的票数来获得每个进程的步长。比如用10000 除以这些票数值，得到了3 个进程的步长分别为100、200 和40。我们称这个值为每个进程的步长（stride）。每次进程运
行后，我们会让它的计数器 [称为行程（pass）值] 增加它的步长，记录它的总体进展。

可以看出，C 运行了 5 次、A 运行了 2 次，B 一次，正好是票数的比例——200、100 和 50。彩票调度算法只能一段时间后，在概率上实现比例，而步长调度算法可以在每个调度周期后做到完全正确。

优势

步长调度能实现一个确定性的公平分配算法。

随机方式可以使得调度程序的实现简单（且大致正确），但偶尔并不能产生正确的比例，尤其在工作运行时间很短的情况下。

劣势

彩票调度有一个步长调度没有的优势——不需要全局状态。因此彩票调度算法能够更合理地处理新加入的进程。

总结

比例份额调度的两种实现：彩票调度和步长调度。但这两种方法没有作为 CPU 调度程序被广泛使用

原因一：这两种方式都不能很好地适合 I/O[AC97]

原因二：没有解决如何分配彩票的问题

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

原因四：步长调度需要全局状态，不能很好的解决新加入的进程

比例份额调度程序只有在这些问题可以相对容易解决的领域更有用（例如容易确定份额比例）。例如在虚拟（virtualized）数据中心中，你可能会希望分配1/4 的CPU 周期给Windows 虚拟机，剩余的给Linux 系统，比例分配的方式可以更简单高效。