在本章中，我们将研究一种不同类型的调度器，称为比例份额（proportional-share）调度器，有时也称为公平共享（fair-share）调度器。比例共享基于一个简单的概念:调度程序不优化周转或响应时间，而是尝试确保每个作业获得一定百分比的CPU时间。
沃尔德斯伯格(Waldspurger)和威尔(wehl) [WW94]在研究中发现了一个比例份额调度的优秀早期例子，被称为彩票调度（lottery scheduling）;然而，这个想法肯定是比较古老的[KL88]。其基本思想非常简单:经常举行抽奖，以确定下一步应该运行哪个进程;应该更频繁运行的进程应该获得更多的中奖机会。很容易,不是吗?现在，来看看细节!但不是在我们的关键之前：

关键的问题：如何按比例份额CPU 我们如何设计一个调度程序以比例方式共享CPU ?这样做的关键机制是什么?效果如何?

9.1 基本概念：票数代表你的份额 Basic Concept: Tickets Represent Your Share

底层的彩票调度是一个非常基本的概念:票数（tickets），它用于表示进程(或用户或其他)应该接收的资源份额。进程拥有的票据百分比表示它在相关系统资源中的份额。
让我们来看一个例子。想象两个进程A和B，并且A有75张票，而B只有25张票。因此，我们希望A接收CPU的75%，B接收剩下的25%。
彩票调度（Lottery scheduling）通过每隔一段时间(例如，每个时间片)持有彩票来实现概率性(但不是确定性)。持有彩票很简单:调度程序必须知道总共有多少张彩票(在我们的示例中，有100张)。调度程序然后选择一个中奖的彩票，它是一个从0到99的数字。假设A持有0到74的彩票，B持有75到99的彩票，中奖的彩票只决定A还是B运行。然后调度程序加载获胜进程的状态并运行它。

计算机科学家总是从0开始计数。这对非计算机类型的人来说是如此奇怪，以至于名人觉得有必要写一下我们为什么这样做[D82]。

下面是一个彩票调度程序中奖彩票的输出示例:

以下是最终的时间表:

从这个例子中可以看出，在彩票调度中使用随机性会导致满足期望比例的概率正确性，但不能保证。在上面的示例中，B只运行了20个时间段中的4个(20%)，而不是期望的25%的分配。然而，这两种工作竞争的时间越长，它们就越有可能达到预期的百分比。

Tip：用票数来代表份额 彩票(和步幅)调度设计中最强大(也是最基本)的机制之一就是票（ticket）。在这些示例中，票证用于表示进程在CPU中的份额，但可以应用得更广泛。例如，在最近关于虚拟内存管理系统的工作中，Waldspurger展示了如何使用票据来表示来宾操作系统的内存共享[W02]。因此，如果您需要一种机制来表示所有权的比例，那么这个概念可能就是……(等待它)……这张票。

9.2 票据机制 Ticket Mechanisms

彩票调度还提供了许多机制，以不同的、有时是有用的方式操纵彩票。一种方式是使用票券（ticket currency）的概念。货币允许拥有一组票据的用户在他们自己的作业中以任何他们想要的货币分配票据;然后系统自动将上述货币转换为正确的全局值。
例如，假设用户A和用户B每人得到了100张票。用户A运行两个作业，A1和A2，并以A货币给他们每人500张票(总共1000张票)。用户B只运行一个作业，并给它10张票(总共10张)。系统将 A1 和 A2 的分配从 A 的货币各 500 转换为全球货币各 50；同理，B1的10张票换算成100张票。然后以全球票币（总共 200 个）进行抽奖以确定运行哪个作业。

另一个有用的机制是票据转移（ticket transfer）。通过转移，一个进程可以暂时将它的票交给另一个进程。这种能力在客户端/服务器设置中特别有用，客户端进程向服务器发送消息，要求它代表客户端做一些工作。为了加快工作速度，客户端可以将票传递给服务器，从而在服务器处理客户端请求的同时尝试最大化服务器的性能。完成后，服务器然后将票证传输回客户端，一切都和以前一样。
最后，票证通胀（ticket inflation）有时是一种有用的技术。随着通货膨胀（inflation），一个进程可以暂时增加或减少它拥有的票数。当然，在进程相互不信任的竞争场景中，这毫无意义；一个贪婪的进程可以给自己大量的票并接管机器。相反，可以在一组进程相互信任的环境中应用通货膨胀；在这种情况下，如果任何一个进程知道它需要更多的 CPU 时间，它可以提高它的票证价值，作为一种向系统反映这种需求的方式，所有这些都不需要与任何其他进程通信。

9.3 实现 Implementation

关于彩票调度最令人惊讶的事情可能是它的实现的简单性。您所需要的是一个良好的随机数生成器来挑选中奖的彩票，一个跟踪系统进程的数据结构(例如，链表)，以及彩票总数。
让我们假设我们将进程保存在一个链表中。下面是一个由三个进程A、B和C组成的示例，每个进程都有一些票据。

为了做出调度决定，我们首先必须从总票数 (400) 中选择一个随机数（获胜者），假设我们选择了数字 300。然后，我们简单地遍历链表，使用一个简单的计数器来帮助我们找到获胜者（图 9.1）。

令人惊讶的是，正如 Bjorn Lindberg 所指出的那样，正确地做到这一点可能具有挑战性。有关更多详细信息，请参阅http://stackoverflow.com/questions/2509679/how-to-generate-a-random-number-from-within-a-range。

该代码遍历进程列表，将每个票据值添加到计数器，直到值超过winner。一旦出现这种情况，当前列表元素将胜出。在我们的中奖彩票示例为 300 的情况下，发生以下情况。首先， counter 增加到 100 来计算 A 的票；因为 100 小于 300，所以循环继续。然后柜台将更新为 150（B 的票），仍然少于 300，因此我们再次继续。最后，计数器更新为 400（明显大于 300），因此我们跳出循环，current 指向 C（赢家）。
为了使这个过程最高效，通常最好按照从最高到最低的顺序来组织列表。排序不影响算法的正确性;但是，它通常可以确保使用最少的列表迭代次数，特别是在有几个流程拥有大多数票据的情况下。

9.4

一个例子 An Example 为了使彩票调度的动态更容易理解，我们现在对两个相互竞争的工作的完成时间进行了简短的研究，每个工作都有相同数量的彩票(100)和相同的运行时间(R，我们将改变它)。
在这个场景中，我们希望每个任务大致在同一时间完成，但由于抽签调度的随机性，有时一个任务会在另一个任务之前完成。为了量化这种差异，我们定义了一个简单的公平指标（fairness metric），F，它就是第一个任务完成的时间除以第二个任务完成的时间。例如，如果R = 10，第一个作业在时间10结束(第二个作业在时间20结束)，则F = 10/20 = 0.5。当两个作业几乎同时完成时，F将非常接近1。在这个场景中，这就是我们的目标:一个完全公平的调度程序将实现F = 1。
图9.2描绘了在30次试验中，当两个工作的长度(R)从1到1000不等时的平均公平性(结果是通过本章末尾提供的模拟器生成的)。从图中可以看出，当工作时间不是很长时，平均公平度可能会很低。只有当作业运行大量的时间片时，抽签调度器才会接近期望的公平结果。

9.5 如何分配票数 How To Assign Tickets?

关于彩票调度，我们还没有解决的一个问题是:如何将票数分配给工作?这个问题很棘手，因为系统的行为很大程度上取决于票的分配方式。一种方法是假设用户最了解情况;在这种情况下，每个用户都获得了一定数量的票据，用户可以按照自己的需要将票据分配给任何作业。然而，这个解决方案不是解决方案:它实际上并没有告诉您该做什么。因此，给定一组作业，票分配问题仍然是开放的。

9.6

步幅调度 Stride Scheduling 你可能还想知道:为什么要使用随机性?正如我们在上面所看到的，虽然随机性为我们提供了一个简单的(并且大致正确的)调度程序，但它偶尔不会提供准确的比例，特别是在短时间范围内。因此，Waldspurger发明了stride scheduling(确定性公平共享调度程序)[W95]。
步幅调度也很简单。系统中的每个作业都有一个步幅，它与它拥有的票数成反比。在上面的示例中，对于作业 A、B 和 C，分别有 100、50 和 250 张票，我们可以通过将某个大数字除以每个进程已分配的票数来计算每个工单的步幅。例如，如果我们将 10,000 除以这些票证值中的每一个，我们将获得以下 A、B 和 C 的步幅值：100、200 和 40。我们称该值为每个进程的步幅（stride）；每次进程运行时，我们都会为其步幅增加一个计数器（称为传递（pass）值）以跟踪其全局进度。
调度程序然后使用stride和pass来确定下一步应该运行哪个进程。其基本思想很简单:在任何给定时间，选择迄今为止pass值最低的进程运行;当你运行一个进程时，按它的步数增加它的pass计数器。Waldspurger [W95]提供了一个伪代码实现:

在我们的示例中，我们从三个进程（A、B 和 C）开始，步幅值为 100、200 和 40，并且所有进程的初始值都为 0。因此，首先，任何进程都可能运行，因为他们的pass值同样低。假设我们选择 A（任意；可以选择具有相同低pass值的任何进程）。 A 运行；完成时间片后，我们将其传递值更新为 100。然后我们运行 B，其pass值然后设置为 200。最后，我们运行 C，其pass值增加到 40。此时，算法将选择最低的 pass 值的进程，即 C，然后运行它，将它的 pass 更新为 80（C 的步幅是 40，你还记得）。然后 C 将再次运行（仍然是最低的传递值），将其传递提高到 120。A 现在将运行，将其传递更新为 200（现在等于 B）。然后 C 将再运行两次，将其传递更新为 160 然后是 200。此时，所有传递值再次相等，并且该过程将无限重复。图 9.3 跟踪调度程序随时间的行为。

从图中我们可以看到，C运行了5次，A运行了2次，B只运行了1次，与他们的票值分别为250、100和50成正比。彩票调度随着时间的推移实现概率比例;Stride调度使它们在每个调度周期的末尾完全正确。
因此，您可能会想:既然步幅调度是精确的，为什么还要使用彩票调度呢?彩票调度有一个很好的属性，而步幅调度没有:没有全局状态。想象一个新的任务进入我们上面的步幅调度示例的中间;它的传递值应该是什么?它应该设置为0吗?如果是这样，它将独占CPU。使用彩票调度，每个进程没有全局状态;我们只需添加一个新进程，其中包含所有的票据，更新单个全局变量以跟踪总共有多少票据，然后从那里开始。通过这种方式，彩票使得以合理的方式整合新流程变得容易得多。

9.7

Linux完全公平调度器 The Linux Completely Fair Scheduler (CFS) 尽管早期在公平共享调度方面做了这些工作，但当前的Linux方法以另一种方式实现了类似的目标。调度程序名为完全公平调度程序（Completely Fair Scheduler (or CFS)）[J09]，实现了公平共享调度，但是以一种高效和可伸缩的方式实现的。
为了实现其效率目标，CFS旨在通过其固有的设计和对非常适合任务的数据结构的聪明使用，花费很少的时间来制定调度决策。最近的研究表明调度程序的效率是非常重要的;具体来说，在谷歌数据中心的一项研究中，Kanev等人表明，即使经过积极的优化，调度也会占用数据中心总体CPU时间的5%左右。因此，尽可能地减少开销是现代调度器体系结构的一个关键目标。

基本操作 Basic Operation

尽管大多数调度器都是基于固定时间片的概念，但CFS的操作略有不同。它的目标很简单:在所有竞争的进程中公平地分配一个CPU。它通过称为虚拟运行时（virtual runtime）(vruntime)的简单的基于计数的技术来实现这一点。
当每个进程运行时，它会累积vruntime。在最基本的情况下，每个进程的vruntime以相同的速度增长，与物理(实时)时间成比例。当发生调度决策时，CFS将选择vruntime最低的进程继续运行。
这就提出了一个问题:调度程序如何知道何时停止当前正在运行的进程，并运行下一个进程?这里的紧张关系很明显:如果CFS切换太频繁，公平性就会增加，因为CFS将确保每个进程在很小的时间窗口内都能接收到自己的CPU份额，但这是以性能为代价的(太多的上下文切换);如果CFS切换的频率降低，性能就会提高(减少上下文切换)，但这是以短期的公平性为代价的。
CFS通过各种控制参数来管理这种紧张。第一个是sched_latency。CFS使用这个值来确定一个进程在考虑切换之前应该运行多长时间(实际上是以动态方式确定其时间片)。典型的sched_latency值是48(毫秒);CFS将这个值除以CPU上运行的进程数(n)，以确定进程的时间片，从而确保在这段时间内，CFS是完全公平的。
例如，如果有n = 4个进程在运行，那么CFS将sched_latency的值除以n，以得到每个进程12毫秒的时间片。然后CFS调度第一个作业并运行它，直到它使用了12毫秒的(虚拟)运行时，然后检查是否有使用较低的vruntime来运行的作业。在本例中，有，CFS将切换到其他三个作业中的一个，以此类推。图9.4显示了一个示例，其中四个作业(A、B、C、D)以这种方式运行两个时间片;其中两个(C, D)完成，只剩下两个，然后每个循环运行24毫秒。

但是，如果运行的进程“太多”怎么办?这难道不会导致时间片太小，从而导致太多的上下文切换吗?好问题!答案是肯定的。
为了解决这个问题，CFS添加了另一个参数min_granularity，这个值通常设置为6毫秒。CFS永远不会将进程的时间片设置为小于此值，以确保不会在调度开销上花费太多时间。
例如，如果有 10 个进程在运行，我们的最初计算会将 sched_latency 除以 10 来确定时间片（结果：4.8 ms）。但是，由于 min_granularity，CFS 会将每个进程的时间片设置为 6 ms。尽管 CFS 不会（相当）在 48 毫秒的目标调度延迟 (sched_latency) 上完全公平，但它会接近，同时仍能实现高 CPU 效率。
请注意，CFS使用了周期性计时器中断，这意味着它只能在固定的时间间隔内做出决定。这个中断会频繁地中断(例如，每1毫秒中断一次)，给CFS一个机会来唤醒并确定当前作业是否已经到达其运行的终点。如果作业的时间片不是计时器中断间隔的完美倍数，那也没关系;CFS精确地跟踪vruntime，这意味着从长期来看，它最终将接近理想的CPU共享。

权重（优先级） Weighting (Niceness)

CFS还支持控制进程优先级，允许用户或管理员为某些进程提供更高的CPU份额。它不是通过票据来实现的，而是通过一种经典的UNIX机制，即进程的nice级别来实现的。对于进程，nice 参数可以设置为 -20 到 +19 之间的任何位置，默认值为 0。nice 值为正值表示优先级较低，负值表示优先级较高；当你太友善（too nice）时，你就不会得到那么多（调度）关注，唉。
CFS将每个进程的nice值映射为权重（weight），如下所示：

这些权重允许我们计算每个进程的有效时间片(就像我们之前做的那样)，但现在考虑它们的优先级差异。假设有n个过程:

让我们做一个例子来看看它是如何工作的。假设有两个任务，A和b, A，因为它是我们最宝贵的任务，它的优先级是-5;B，因为我们讨厌它（B, because we hates it），只有默认的优先级(nice的值等于0)，这意味着(从表)weightA是3121，而weightB是1024。如果然后计算每个作业的时间片，您将发现A的时间片大约是sched_latency的3/4(因此是36毫秒)，B的时间片大约是1/4(因此是12毫秒)。

是的，是的，我们在这里故意使用糟糕的语法，请不要发送错误修复。为什么?嗯，只是稍微提到了《指环王》和我们最喜欢的反英雄咕噜，没什么好激动的。

除了推导时间片计算外，CFS计算vruntime的方式也必须适应。下面是新的公式，它取进程 i 累计的实际运行时间(runtimei)，并将其按进程权重的倒数进行缩放，方法是将默认权重1024 (weight0)除以它的权重weighti。在我们正在运行的例子中，A的vruntime的累积速率是B的三分之一。

上面权重表构造的一个聪明方面是，当nice值的差是常数时，该表保持CPU的比例比率。例如，如果进程A的值是5(而不是-5)，进程B的值是10(而不是0)，那么CFS将以与之前完全相同的方式调度它们。你自己来计算一下原因。

使用红黑树 Using Red-Black Trees

如上所述，CFS的一个主要焦点是效率。对于调度器来说，效率有很多方面，但其中一个方面很简单:当调度器必须找到要运行的下一个作业时，它应该尽可能快地这样做。像链表这样的简单数据结构不能扩展：现代系统有时由 1000 个进程组成，因此每隔这么多毫秒搜索一个长链表是浪费的。
CFS通过将进程保存在红黑树中来解决这个问题[B72]。红黑树是多种平衡树中的一种;与简单的二叉树(在最坏情况的插入模式下，它会退化为类似链表的性能)相比，平衡树需要做一些额外的工作来维持较低的深度，从而确保操作在时间上是对数的(而不是线性的)。
CFS不会将所有进程都保存在这个结构中;相反，只有运行(或可运行)的进程保存在其中。如果进程进入睡眠状态(例如，等待I/O完成，或等待网络数据包到达)，它将从树中删除，并在其他地方保持跟踪。
让我们看一个例子来更清楚地说明这一点。假设有10个作业，它们的vruntime值如下:1、5、9、10、14、18、17、21、22和24。如果我们将这些作业保存在一个有序列表中，那么查找要运行的下一个作业将非常简单:只需删除第一个元素。然而，当将该作业(按顺序)放回列表中时，我们必须扫描列表，寻找插入它的正确位置，这是一个O(n)操作。任何搜索都是非常低效的，平均耗时也是线性的。
在红黑树中保持相同的值可以使大多数操作更高效，如图 9.5 所示。进程在树中按 vruntime 排序，大多数操作（如插入和删除）在时间上是对数的，即 O(log n)。当 n 以千为单位时，对数显然比线性更有效。

处理I/O和休眠进程 Dealing With I/O And Sleeping Processes

选择最低的vruntime来运行的一个问题是，作业已经休眠了很长一段时间。想象两个进程，A和B，其中一个(A)连续运行，另一个(B)休眠了很长一段时间(比如10秒)。当B醒来时，它的vruntime将比A慢10秒，因此(如果我们不小心的话)，B将在接下来的10秒内独占CPU，而实际上是在饿死（starving）A。
CFS通过在作业醒来时更改作业的vruntime来处理这种情况。具体来说，CFS将该作业的vruntime设置为树中找到的最小值(记住，树只包含正在运行的作业)[B+18]。通过这种方式，CFS避免了饥饿，但并不是没有代价的:短时间睡眠的工作经常不会得到它们公平的CPU份额[AC97]。

其他CFS有趣的地方 Other CFS Fun

CFS还有许多其他特性，太多了，无法在本书的此处讨论。它包括许多提高缓存性能的启发式方法，具有有效处理多个cpu的策略(如本书后面所讨论的)，可以跨大组进程进行调度(而不是将每个进程视为独立的实体)，以及许多其他有趣的特性。阅读最近的研究，从Bouron [B+18]开始，了解更多。

Tip：在适当的时候使用有效的数据结构 在很多情况下，链表就可以了。在许多情况下，它不是。知道何时使用哪个数据结构是优秀工程的标志。在本文讨论的情况下，在早期调度器中找到的简单链表在现代系统上不能很好地工作，特别是在数据中心中负载很大的服务器上。这样的系统包含数千个活动过程;每隔几毫秒搜索一个很长的列表以找到在每个核心上运行的下一个作业将会浪费宝贵的CPU周期。需要更好的结构，CFS通过添加红黑树的出色实现提供了这种结构。更一般地说，在为正在构建的系统选择数据结构时，要仔细考虑它的访问模式和使用频率;通过理解这些，您将能够为手头的任务实现正确的结构。

9.8

总结 Summary 我们介绍了比例份额调度的概念，并简要讨论了三种方法:彩票调度、步幅调度和Linux的完全公平调度程序(CFS)。彩票巧妙地利用随机性来实现一定比例的份额;Stride是确定的。CFS是本章讨论的唯一真正的调度器，它有点像带动态时间片的加权轮询（round-robin），但构建时可扩展，在负载下性能良好;据我们所知，它是目前使用最广泛的公平份额调度程序。
没有调度程序是万灵药，公平分配的调度程序也有其公平分配的问题。一个问题是，这种方法不能与I/O [AC97]很好地结合;正如上面所提到的，偶尔执行I/O的作业可能得不到公平的CPU份额。另一个问题是，他们留下了票或优先级分配的难题，即，你如何知道你的浏览器应该分配多少票，或设置你的文本编辑器的好值?其他通用调度器(如我们前面讨论的MLFQ和其他类似的Linux调度器)会自动处理这些问题，因此可能更容易部署。
好消息是，在许多领域中，这些问题并不是主要关注的问题，使用比例份额调度器效果很好。例如，在虚拟化（virtualized）数据中心(或云（cloud）)中，您可能希望将四分之一的CPU周期分配给Windows VM，其余的分配给基本的Linux安装，比例份额可以简单而有效。这个想法也可以扩展到其他资源;有关如何在VMWare的ESX服务器中按比例共享内存的详细信息，请参阅Waldspurger [W02]。

References

[AC97] “Extending Proportional-Share Scheduling to a Network of Workstations” by Andrea
C. Arpaci-Dusseau and David E. Culler. PDPTA’97, June 1997. A paper by one of the authors on
how to extend proportional-share scheduling to work better in a clustered environment.
[B+18] “The Battle of the Schedulers: FreeBSD ULE vs. Linux CFS” by J. Bouron, S. Chevalley,
B. Lepers, W. Zwaenepoel, R. Gouicem, J. Lawall, G. Muller, J. Sopena. USENIX ATC ’18,
July 2018, Boston, Massachusetts. A recent, detailed work comparing Linux CFS and the FreeBSD
schedulers. An excellent overview of each scheduler is also provided. The result of the comparison:
inconclusive (in some cases CFS was better, and in others, ULE (the BSD scheduler), was. Sometimes
in life there are no easy answers.
[B72] “Symmetric binary B-Trees: Data Structure And Maintenance Algorithms” by Rudolf
Bayer. Acta Informatica, Volume 1, Number 4, December 1972. A cool balanced tree introduced
before you were born (most likely). One of many balanced trees out there; study your algorithms book
for more alternatives!
[D82] “Why Numbering Should Start At Zero” by Edsger Dijkstra, August 1982. Available:
http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF. A short note from E.
Dijkstra, one of the pioneers of computer science. We’ll be hearing much more on this guy in the
section on Concurrency. In the meanwhile, enjoy this note, which includes this motivating quote: “One
of my colleagues — not a computing scientist — accused a number of younger computing scientists of
’pedantry’ because they started numbering at zero.” The note explains why doing so is logical.
[K+15] “Profiling A Warehouse-scale Computer” by S. Kanev, P. Ranganathan, J. P. Darago,
K. Hazelwood, T. Moseley, G. Wei, D. Brooks. ISCA ’15, June, 2015, Portland, Oregon. A
fascinating study of where the cycles go in modern data centers, which are increasingly where most of
computing happens. Almost 20% of CPU time is spent in the operating system, 5% in the scheduler
alone!
[J09] “Inside The Linux 2.6 Completely Fair Scheduler” by M. Tim Jones. December 15, 2009.
http://ostep.org/Citations/inside-cfs.pdf. A simple overview of CFS from its ear-
lier days. CFS was created by Ingo Molnar in a short burst of creativity which led to a 100K kernel
patch developed in 62 hours.
[KL88] “A Fair Share Scheduler” by J. Kay and P. Lauder. CACM, Volume 31 Issue 1, January
1988. An early reference to a fair-share scheduler.
[WW94] “Lottery Scheduling: Flexible Proportional-Share Resource Management” by Carl A.
Waldspurger and William E. Weihl. OSDI ’94, November 1994. The landmark paper on lottery
scheduling that got the systems community re-energized about scheduling, fair sharing, and the power
of simple randomized algorithms.
[W95] “Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management” by
Carl A. Waldspurger. Ph.D. Thesis, MIT, 1995. The award-winning thesis of Waldspurger’s that
outlines lottery and stride scheduling. If you’re thinking of writing a Ph.D. dissertation at some point,
you should always have a good example around, to give you something to strive for: this is such a good
one.
[W02] “Memory Resource Management in VMware ESX Server” by Carl A. Waldspurger.
OSDI ’02, Boston, Massachusetts. The paper to read about memory management in VMMs (a.k.a.,
hypervisors). In addition to being relatively easy to read, the paper contains numerous cool ideas about
this new type of VMM-level memory management.

Homework (Simulation)

程序 lottery.py 允许您查看彩票调度程序是如何工作的。有关详细信息，请参阅README文件。

Questions

1. 计算具有3个任务和随机种子1、2和3的模拟的解决方案。
2. 现在运行两个特定的作业:每个作业的长度都是10，但是一个(作业0)只有1张票，另一个(作业1)有100张票(例如，-l 10:1,10:100)。当票的数量如此不平衡时会发生什么?作业0会在作业1完成之前运行吗?多长时间?一般来说，这种彩票的不平衡对彩票调度行为有什么影响?
3. 当运行两个长度为100的作业并且相同的票分配为100 (-l 100:100,100:100)时，调度程序有多不公平?使用一些不同的随机种子运行以确定（概率）答案；让不公平由一项工作比另一项工作提前完成多少来决定。
4. 当量子尺寸（时间片）(-q)变大时，你对上一个问题的答案会如何变化？
5. 你能把这章里的图表做一个版本吗?还有什么值得探索的?如果使用步幅调度程序，图表会是什么样子?