Linux OS进程调度机制探讨

　　Linux OS进程调度机制探讨

　　这里将探讨一下Linux OS的进程调度实现的原理，具体代码就不深挖了。

　　先来说说一些基础知识：

　　3.1 进程调度相关基础知识

　 　在一个系统中，经常运行着多个进程，和CPU个数相比，当然是进程数远远大于CPU个数咯，那么就存在为进程分配CPU资源的问题。一般而言，有两种分 配方式，一个是由进程间协调，例如一个比较友好的进程在一定的时刻主动让出CPU，这样其他进程就有机会使用CPU。但是这种类似道德上的约束往往行不 通，因为总会有“恶意“进程存在嘛！另外一个比较难以克服的问题是友好的标准没法统一，例如什么时候该友好一下？除了这种不靠谱的道德约束外，大师们又引 进了抢占式分配，这种分配方式类似法律约束。每个进程会分配一定的CPU资源，OS也会定时（处理时钟中断）+定点（比如系统调用返回到 userspace前，）检查进程的CPU资源使用情况。一旦某个进程CPU资源消耗完毕，则会毫不留情地挑选下一个进程运行。

　　在操作系统理论中，CPU资源一般用时间片（time slice）来表示。直观意义就是分配给一个进程可以运行在CPU上的时间。也就是CPU资源是用时间单位来衡量的。

　　当然，进程调度是一套复杂的算法，图2展示了Linux上进程调度算法的演化历史。

图2 Linux进程调度算法演化史

　 　从使用CPU的方式来看，进程大体可分为I/O-bound和CPU-bound。二者有什么不同呢？I/O-bound类型的进程大部分时间都处于等 待I/O的状态，当然这种I/O是广义的，例如等待用户按键事件，等待磁盘读写完成。而CPU-bound对于那种需要大量计算的进程，例如一个软件编解 码算法，最极端的就是一个while死循环。从用户体验来说，I/O-B这种进程大部分都是需要人机交互的。OS设计进程调度算法时，一般偏向于IO-B 进程，这样至少用户用起来不会感觉不爽。

　　3.2 Linux进程调度研讨

　　1、调度算法

　　我们先介绍下和进程调度息息相关的进程优先级相关的知识。

　　最直观的想法就是给每个进程设置一个调度优先级，然后按照round-robin方式每次挑选一个优先级最高的进程运行。

　　那么，在Linux中，这个调度优先级是通过nice值来反映的，从-20到19。值越大表示该进程越nice，这个nice是对其他进程的nice，所以优先级越低。

　　再解决优先级的概念后，我们再来看第二个基本问题：CPU资源：time-slice是什么？以及它如何与优先级结合起来？

　　最先想到的就是time-slice应该是一个时间单位，例如20ms。然后每种调度优先级的time-slice和该级别有某种计算关系，例如线性。假设0级对应的时间片是20ms，那么1级的就是15ms。

　 　默认时间片（对应0度优先级）该取多大呢？太大的话（例如2秒）则会导致漫长（从CPU速度来看）的用户等待，例如每个进程都需要运行2秒才会让出 CPU，这样的系统运行起来给人一顿一顿的感觉。而太小的话（例如1ms）则会导致CPU把大量时间浪费在进程上下文切换。前辈们经过长期的实际使用，一 般系统设置的默认时间片在20ms或者10ms。

　　这种以时间（一般为ms）作为时间片单位，并且将时间片与优先级直接映射的方式有什么缺点呢？

　　我们考虑二个例子：

　 　假设0级对应100ms的时间片，那么20级对应的时间片为5ms。现在系统上就一个0级进程和一个20级进程在运行。在105ms内，0级进程将运行 100ms（占20/21），而20级进程将运行5ms（占1/21）。好。假设现在仅有2个20级进程，同样在105ms内，却要每5ms切换一下进程 （因为20级进程每次只能运行5ms），那么105ms内切换了52次。从这个例子可以看出，简单的时间片映射对优先级低的进程极其不公平。例如在只有两 个20级进程的105ms内，按道理应该也只需要切换两次进程即可。但是现在却切了52次。

　　假设0级进程时间片为100ms，每个优先级对应步进为5ms，则1级对应时间片为95ms。如此类推，18级优先级为10ms，19级优先级则为5ms。看出问题了吗？18级优先级进程时间片为19级的2倍！

　　第三个问题就直接剑指时间片了，如果简单地以绝对时间作为时间片的单位，那么算法就得考虑不同机器提供的时间精度了，有些高精度的机器能提供精确到1ms的时间，而有些是10ms。

　　那么Linux的CFS（Completely Fair Scheduler）算法是怎么做的呢？

　　CFS基于一种叫perfect multitasking模型来构建调度算法。

　 　在一个能提供完美多任务能力的CPU中，每个进程能使用1/n的CPU时间。n是当前进程个数。不考虑调度时间（理论上的，这个时间被称为 infinitely small schedule duration time），那么在任何相等时间段内，每次都会运行n个进程。

　　上面这段话实在不太好理解。我们举个例子：

　　在普通调度模型中，10ms时间内有两个进程，那么每个都将运行5ms。在单个5ms内，每个进程占据100%CPU

　 　在PM（perfect multitasking）模型中，10ms内每个进程都运行了10ms，但是每个只用50%的CPU。更难理解了？可以想象CPU飞快地进行线程切换， 一下运行进程A，一下运行进程B。在10ms内，似乎每个进程都运行了10ms，但实际上每个进程只占据了50%的CPU。

　　理解这种PM模型的关键在占据50%CPU这句话上，对于那种普通调度模型中，在一定时间内，进程占据了100%CPU。而在PM模型中，进程占据CPU却是1/n。

　　好了,CFS具体是实现这个模型的呢？

　　之前每个进程分配的固定时间的算法现在被替代成每个进程运行的时间将是全体进程个数的函数。这个对应为上面模型描述中的1/n。

　　nice值不再直接对应时间片。在CFS中，nice值对应一个比重。优先级越高的进程，该比重越大。

　　有了这些参数，每个进程运行的“timeslice“将是它的比重和那个n(表示当前系统内所有处于可执行状态的进程/线程)的函数。

　　注意，Linux内核中，进程和线程用同一个结构体表示，所以线程也叫轻量级进程。调度的时候是不区分理论上的进程和线程的。

　 　尽管CFS尽力避开以时间作为调度单位，但是实现中还是需要时间作为资源使用的考量。那么CFS将这个时间称之为target latency。用来对应PM模型中那个infinitly small schedule duration time。假设该值是20ms，那么2个同优先级进程运行时，每个进程使用10ms，4个同优先级进程的时候每个使用5ms。随着进程数增加，每个进程的 时间会趋向于0。那么CFS的实现中，增加了一个minimum granularity，这个时间是最小时间，目前为1ms。

　　上面这些理论还是有点搞不清楚，下面我们看个例子。

　 　一个0级进程和一个5级进程。最后计算出来5级进程的比重将是0级进程的1/3。那么20ms的target latency情况下，0级进程分配15ms，5级进程分配5ms。此时nice值不再直接对应时间值，而仅仅是一个相对CPU时间的比重。所以，假设这 两个进程一个是10级，一个是15级，最后计算出来的时间也是15ms和5ms。

　　PM这个模型还是没说清楚，目前根据《Linux Kernel Development》只能得出上面的结论。

　　2、调度策略和调度class

　　sched_setscheduler函数用来设置进程的调度策略。

　　在实际的内核代码中，我们发现在选择下一个可运行的进程时，存在这一个for循环：

[->kernel/sched.c]
static inline struct task_struct * pick_next_task(struct rq *rq)
{
 const struct sched_class *class;
 struct task_struct *p;
//调度算法是一个集合，每次使用优先级最高的调度算法。这个算法类在代码中用
//sched_class表示
 class = sched_class_highest; 
 for ( ; ; ) {
  p = class->pick_next_task(rq);
  if (p)
   return p;
  class = class->next;
 }
}

　　Linux内核目前使用了两个调度算法类，一个是fair_sched_class，对应于非实时的调度。另外一个是rt_sched_class，对应于实时调度算法。从上面的函数中可知：

　　按照调度算法本身的优先级，获得一个可运行进程。如果该算法没有得到一个进程，则运行下一个调度算法。

　　按照刚才所说，一共只有两个调度算法，那么我们在sched_setscheduler设置的BATCH/IDLE/NORMAL又有什么用呢？

static void
__setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
{
 ……
 if (rt_prio(p->prio))
  p->sched_class = &rt_sched_class;
 else //IDLE/BATCH/NORMAL等设置的都是fair_sched_class
  p->sched_class = &fair_sched_class; 
 set_load_weight(p);
}
//set_load_weight就是根据policy(NORMAL/IDLE/BATCH)，得到一个比重
static void set_load_weight(struct task_struct *p)
{
 if (task_has_rt_policy(p)) {
  p->se.load.weight = prio_to_weight[0] * 2;
  p->se.load.inv_weight = prio_to_wmult[0] >> 1;
  return;
 }
 if (p->policy == SCHED_IDLE) {
  p->se.load.weight = WEIGHT_IDLEPRIO;
  p->se.load.inv_weight = WMULT_IDLEPRIO;
  return;
 }
 p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
 p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
}

　　根据我们前面所说，再结合上面的代码，sched_setscheduler实际上：

　　设置该进程的调度算法类为fair_sched_class

　　根据policy，设置该进程的weight。（这个weight的作用，以后在介绍kernel sched的时候再来讨论）

　　四、总结

　　本随笔从Java层提供的进程调度API开始，介绍了Linux OS上的进程调度相关的知识。对于那些仅需要知道工作原理的人来说，这些知识应该是足够了。