CFS调度算法简要分析.pdfVIP

CFS 调度算法简要分析    本文可能存在不正确的地方，请读者自行斟酌。  CFS(completely fair schedule)，故名思议完全公平的调度，既然讲公平，那就应该有个评判的标准， 在这之前我们先来讲几个比较重要的概念[1]。  调度实体(sched entiy)：就是调度的对象，可以理解为进程。  虚拟运行时间(vruntime)：即每个调度实体的运行时间。  公平调度队列(cfs_rq):采取公平调度的调度实体的运行队列。  上面谈到公平的依据，CFS 的公平依据就是每个调度实体的权重(weight)，这个权重是有优先级来 决定的，即优先级越高权重越高，linux 内核采用了nice‐prio‐weight 的一个转换关系来实现了每个调度 实体权重的确定。优先级概念主要来自 O(1)调度，CFS 这里是为了兼容 O(1) 。  我们来回顾，进程被创建的时候他的优先级是继承自父进程的，如果想改变原有优先级，linux 内 核提供了几个系统调用来改变进程的 nice 值，从而改变权重，比如 sys_nice()系统调用，下面来看一下 他们之间的转换关系：  /*    * Convert user‐nice values [ ‐20 ... 0 ... 19 ]    * to static priority [ MAX_RT_PRIO..MAX_PRIO‐1 ],    * and back.    */  #define NICE_TO_PRIO(nice)  (MAX_RT_PRIO + (nice) + 20)  #define PRIO_TO_NICE(prio)  ((prio) ‐ MAX_RT_PRIO ‐ 20)    其中，MAX_RT_PRIO=100,nice 的值在‐20 到 19 之前，那么优先级就在 100 ‐ 139 之间。  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, };  再看 prio 和 weight 之间的转换关系，这是个经验公式。通过以上分析我们就可以通过修改 nice 来修改 weight 了，这也就回答了每个调度实体的weight 是怎么确定的这个问题了吧。    为什么要这样设计，因为有个相邻 nice 值之间需要 10%差异的设计要求，看代码就可以知道。    CFS 可实现几种不同的公平策略，这些策略是根据调度的对象的不同来区分的。  默认的是不开组调度的公平策略，即调度的单位是每个调度实体。我们来详细看一下是怎么调度的：  假设现在系统有 A ，B，C 三个进程：  A.weight=1, B.weight=2, C.weight=3.  那么我们可以计算出整个公平调度队列的总权重是  cfs_rq.weight = 6，  很自然的想