CPU Virtualization-Scheduling(Proportional Share)

在本章中，我们介绍比例份额（proportional-share）调度，有时也称为公平份额（fair-share）调度。比例份额算法基于一个简单的想法：调度程序的最终目标，是确保每个工作获得一定比例的 CPU 时间，而不是优化周转时间和响应时间。例如彩
票调度（lottery scheduling）。它的基本思想很简单：每隔一段时间，都会举行一次彩票抽奖，以确定接下来应该运行哪个进程。越是频繁运行的进程，拥有更多赢得彩票的机会。

1. Basic Concept: 彩票数表示份额

彩票调度/lottery scheduling背后是一个非常基本的概念：彩票数（tickets）代表了进程（或用户或其他）占有某个资源的份额。一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。假设有两个进程A和B，A拥有75张彩票，B拥有25张。我们希望A占用75%的CPU时间，而B占用25%。通过不断定时地（比如，每个时间片）抽取彩票，彩票调度从概率上（但不是确定的）
获得这种份额比例。抽取彩票的过程很简单：调度程序知道总共的彩票数（在我们的例子中，有100张）。调度程序抽取中奖彩票，这是从0和99之间的一个数，拥有这个数对应的彩票的进程中奖。假设进程A拥有0到74共75张彩票，进程B拥有75到99的25张，中奖的彩票就决定了运行A或B。调度程序然后加载中奖进程的状态，并运行它。下面展示一个彩票调度的例子：



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