cpu调度-完全公平的调度模式

在本文中，我们将讨论另一种调度方法-公平调度。公平调度模式基于一个基本概念：与MLFQ相比，它可以优化周转时间和相应时间，公平调度模式是确保每个任务获得一定百分比的cpu时间。

基本概念：票据数量代表应分配的数量

应该分配资源的比例与任务拥有的票证的比例一样多。如果有两个任务A和B，A有75张票，B有25张票，那么A应该有75％的CPU时间，B应该有25％的CPU时间。

奖池调度方法是通过定期抽奖（时间间隔）来确定谁中奖。系统中有任务A和任务B，共计100张。其中，A有75张，从0到74。B有25张照片，从75到99。然后开始抽奖，如果开奖是0到74，则选择A，否则选择B。调度程序将加载选定的流程陈述并运行它。

我们可以观察到正确性的可能性由随机性保证，但不能保证正确性。这很容易理解。如果随机次数相对较少，则机会较大。如果有很多随机时间，则非常接近我们想要的比率。

在这里，我在谈论随机性的好处。随机性的好处之一是不会有特定的输出会导致性能下降。例如，算法中的随机快速排序是为了避免在特定情况下的不良性能。 。第二个是随机且非常轻量级的，只需要跟踪很小的状态即可。例如，如果要计算每个进程使用的cpu时间，则需要运行每个进程然后进行计数。随机化只需要知道每个进程拥有的票证数量即可。第三随机速度非常快。线性同余方法是最简单的伪随机算法之一，它仅具有加法和乘法运算。

收据机制

乐透排程方法提供了多种不同的方式来操纵彩票。

用于乐透调度的伪代码如下：

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 while (current) {
11 counter = counter + current->tickets;
12 if (counter > winner)
13 break; // found the winner
14 current = current->next;
15 }
16 // ’current’ is the winner: schedule it...

实现乐透调度最令人惊奇的事情是实现它的简单性。只要有一个不错的随机数来选择门票。让我们假设使用链表来组织过程。下面是链表组织过程的。

首先，我们需要在400内随机生成一个随机数，然后遍历链表以选择要运行的适当任务。为了使链接列表更有效地运行，最好将链接列表从最大到最小排序。排序不会影响算法的正确性，但可以减少遍历的次数，尤其是当流程中有大量票证时。

如何分配票证以及为什么不能使用确定性

使用随机策略的计划程序只能提供近似的准确性，尤其是对于短任务，这种计划方法无法提供准确性。因此，Waldspurger发明了明确的公平调度程序逐步调度。

步骤调度也非常简单。每个任务的步长与票证数量成反比。使用上面的示例，A，B和C分别具有音符100、50和250。然后步长的计算就更大了，这里我们将音符数除以10000。然后步长分别是100、200、40。每次流程运行时，我们都以步长递增计数器，并以此方式跟踪其全局进度。

调度程序确定下一个正在运行的进程的通过步骤，并选择当前运行路径最短的进程。

伪代码如下：

curr = remove_min(queue); // pick client with min pass
schedule(curr); // run for quantum
curr->pass += curr->stride; // update pass using stride
insert(queue, curr); // return curr to queue

Linux的完全公平的调度模式

基于上述对公平调度模式的准备，当前的linux调度模式使用轮询来实现类似的目标。这种调度模式称为完全公平调度程序（CFS），其实现方式高效且可扩展。

为了实现非常高效的实施，在CFS的整个设计中，仅准备了很少的时间来制定调度决策。它使用非常聪明的数据结构来组织任务。最近的研究表明，调度程序的效率非常重要。对Google数据中心的研究表明，即使通过主动优化，调度本身仍占据整个数据中心cpu时间的5％。减轻调度负荷是现代调度程序的主要目标。

基本操作

基于此概念的大多数调度程序都使用固定长度的时间片，但是CFS有所不同。其目标是通过对虚拟运行时（vruntime）的简单统计，即一定比例的物理时间，在多个竞争进程之间平均分配cpu时间。

每个进程运行时，调度程序将计算虚拟运行时。在大多数情况下，每个过程都以相同的速率增长。当发生调度决定时，调度程序将选择运行时间最小的进程。

这提出了一个问题，何时以及何时应该执行调度决策？如果CFS决策过于频繁，则可以保证公平，但是会带来性能消耗（上下文切换过多）。如果粮安委的决策时间过长，则很难保证公平。

CFS使用参数来控制调度时间。首先是预定的延迟。 CFS使用此值来确定制定决策的频率。典型值为48ms。当系统中有n个进程在运行时，调度延迟/ n是调度周期。

例如，假设系统中有4个进程在运行。将调度的等待时间除以4，因此到达每个进程的时间片为12ms。调度程序首先选择要运行的进程，直到时间片用完为止，然后在最小的要运行的vruntime进程中，周期是这样的。应该注意的是，当任务数量改变时，时间片长度也会动态改变。

如果系统中正在运行许多进程，是否可能导致时间片太短？为了解决这个问题，CFS引入了第二个参数min_granularity，通常将此值设置为6ms，当划分的时间片长度小于min_granularity时，必须设置min_granularity的值，目的是避免过多安排消费。

例如，系统中有10个进程在运行。时间片长度应为4.8ms。使用min_granularity，时间片长度设置为6ms。

CFS使用定期时钟中断。发生中断时，CFS有机会制定计划决策。即使任务的时间片不是调度周期的整数倍，也没关系，因为可以准确记录vruntime，并且随着时间的增加，您将慢慢获得适当的cpu时间。

重量

CFS还可以控制进程的权重，从而使系统管理员可以给某些进程更多的CPU时间。这不是问题，而是过程的良好水平。 nice值的范围是-20到19，默认值为0。正数表示低优先级，负数表示高优先级。具体优先级对应的权重如下：

static const int prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};

根据权重值，可以计算每个过程的时间片长度。计算公式如下：

此外，vruntime的计算方法也已更改。

这里要注意两个概念，即调度程序的调度周期和时间片除以每个进程。添加不同的权重后，调度程序的调度周期会改变吗？调度决策周期与时钟周期相关，并且时钟周期以固定周期发生，因此可能会发生时间片不同但决策周期相同的情况。时钟中断大约每2ms至3ms发生一次。这是在内核编译期间确定的，可能会失去一些准确性。

使用红黑树

计划程序必须高效。现在我们讨论一个问题，调度程序如何找到需要调度的下一个任务。现代操作系统可能会运行1000个任务，因此无法使用链表进行遍历。

CFS通过红黑树，通过vruntime的大小来解决流程的组织任务，红黑树是二进制平衡树。与简单树相比，在最坏的情况下，简单树可能会退化为链接列表。红黑树只需要执行一些简单的维护工作即可确保树的高度为logN。 CFS不会维护此数据结构上的所有进程，而只会维护包含运行和可运行状态的进程。如果该进程被阻止，则将其从此处删除。红黑树的插入，搜索和删除都是logN的复杂性，并且具有良好的性能。

I / O和睡眠中的处理过程

想象一个场景，其中有两个正在运行的进程A和B，而A继续运行。此时，B睡眠10秒钟。如果根据以前的调度策略使vruntime保持不变，则A唤醒后，它将独占cpu 10秒钟，以弥补后面的10秒钟，这显然是不可接受的。

在这种情况下，CFS将在唤醒到集合中可以找到的最小vruntime值后立即修改任务的vruntime。这样，就避免了饿死任务的可能性，但是经常睡眠很短时间的任务无法获得本应合理获得的cpu时间。

最终摘要

我们讨论了比例分配调度的方法，并提到了3种方法：彩票方法，分步方法和linux完全公平调度模式。完全公平的调度方法有点像具有权重的RR调度方法。

没有调度程序是完美的，公平调度模型也有问题。例如，它对于频繁进行I / O的程序并不友好。还有如何分配过程权重的问题。此问题仍然存在。其他调度程序（例如MLFQ）将自动进行调整，以简化部署过程。

好消息是，许多方案对这些问题并不敏感，完全公平的调度可以非常有效地运行。例如，在数据中心中，您需要将1/4的CPU分配给Windows VM，其余的分配给Linux安装程序。比例分配将简单有效。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shoujiruanjian/article-323482-1.html