CPU是一种宝贵的资源，Linux是多任务的OS，这种多任务要求，对于每个任务或者说进程来说，就好像它独占了CPU。想想如果只有一个CPU，但是有80个处于TASK_RUNNING状态的进程，在这八十个进程选择进程，切换进程是多么困难。如果你理解不了这种难度，你可以想想如果你同时有80个女朋友，性格迥异，爱好不同，要做到每个女朋友都认为她自己是你唯一的女友是多么的困难。
刘明在《Linux 调度器BFS简介》中有个很有意思的比喻，linux 内核调度器就像处境尴尬的主妇，满足孩子对晚餐的要求便有可能伤害到老人的食欲，做出一桌让男女老少都满意的饭菜实在是太难了。Linux是一个通用的操作系统，无法预测运行其上的进程有什么样的特点，就像一家人的口味各不相同，孩子喜欢吃甜，爸爸喜欢吃咸，老人喜欢口味清淡，所以调度器也很为难。
一般来说根据进程的特点，可以将进程分成几类
1 交互式进程
这个比较简单了，想想你你使用vi编辑文本，大量的人机交互，进程不断的进入睡眠状态等待你的输入，CPU占用不高但是要求响应迅速，比如你敲了键盘，过了10秒钟才在编辑器上显示出来，这用户体验是多么的糟糕。
2 批处理进程
最典型的就是编译工程这种进程了，如果我们编译一个大型的工程，我们敲了个make，也许1个小时才能编译成功，但是没有人会两个眼睛盯着屏幕看编译的过程，我们更关心的是编译的结果。对于这种进程就是属于姥姥不疼舅舅不爱的进程，这要他在跑就行了，不必给他太多的关注和资源。
3 实时进程
实时进程原本的含义是给定的工作要在指定的时间内完成，不要求你多快，但是一定要在指定的时间前完成指定的任务，多用在火箭 导弹类似的精密系统中。这种实时叫做硬实时，对于Linux 这种通用的OS来讲，完全做到硬实时有点强人所难了，中断，磁盘寻道，总线征用 锁，等很多的机制带来了太多的不确定性，很难做到硬实时。
linux所说的实时进程是软实时，就是尽量的实时，如果做不到，也不会出现毁灭性的后果。比如视频播放器，解码速度有点慢，顶多是视频播放有点卡，用户体验不好，但是不会机毁人亡。
不同的进程，就用不同的调度策略伺候之，对于实时进程，我们就采用实时调度策略：FIFO or Round Robin（时间片轮转）。对于批处理进程和交互进程，我们采用CFS调度器。在之前的版本，Linux采用O(1)调度器的时候，有复杂的方法识别交互性进程，奖励交互性进程，算法比较复杂，现在采用CFS调度器后，核心思想比较简单“完全公平”，降低了代码复杂度，很好地满足了各种需求。
先说说实时调度，实时调度有两个维度1 优先级2 调度策略。linux用户程序可以通过调用sched_setscheduler系统调用来设置进程的优先级和调度策略。
实时进程共有0~99共100种不同的优先级，0优先级最高，99优先级最低，对应100个队列。对于实时进程来说，高优先级实时进程存在，低优先级的实时进程就捞不着CPU资源，普通进程更捞不着CPU资源。
接下来就是调度策略，一种是FIFO，先进先出，如果最高优先级的进程是FIFO类型，那么他就一直执行，一条路跑到黑，直到进程退出，或者它调用sched_yield主动让出资源，或者突然出现更高优先级的进程横空出世，抢占了它的CPU。另外一种是时间片轮转，假如说最高优先级实时进程队列存在多个进程，当前进程耗尽自己时间片后自动排到队尾，选择同一个队列的队列头部的进程去执行。这些事情是在task_tick_rt函数做的。
前面提到实时进程存在，普通进程完全捞不到CPU资源也不完全对，后来LINUX增加组调度策略后，有/proc/sys/kernel/sched_rt_period_us和/proc/sys/kernel/sched_rt_runtime_us两个参数，这两个参数表示的含义是：在sched_rt_peroid_us的周期内，所有的实时进程运行时间之和不得超过sched_rt_runtime_us。 默认值为1秒和0.95秒换句话说，在1秒的周期以内，所有实时进程运行时间之和不得超过0.95秒，剩下的0.5秒钟留给普通进程。
对于普通进程的CFS调度器，内容相对比较独立，如果有时间，后面会有专门的博文总结。
2 SMP时代的进程调度
更要命的是现在进入了多核的时代，纵然不谈服务器的高配置，我的笔记本配置不高，也已经是四核，可见多核计算机已经是满大街了。对于负载的SMP，就引入了新的问题。单核的时候，只有一个CPU，不需要考虑选择几个运行队列，就是一个run queue。但是多核的时候，是建立一个run queue，所有的CPU去run queue上选择摘取可执行的进程，还是每个CPU一个run queue？其实都是可以的。
1 per cpu run queue
目前linux 内核采用的是per cpu run queue，每个CPU去自己的run queue 去选择可执行的进程，这样减少 了竞争。其实除了这个好处，还有另外一个甚至更重要的好处，缓存重利用。进程落在这个CPU的运行队列上，经过多次调度后（暂不考虑多CPU的load balance），仍然是同一颗CPU运行这个进程，也许上次运行时的变量 内存还在cache中，如果只有一个运行队列，多个CPU的话，上次执行所在的CPU和这次执行所在的CPU很可能不是同一颗CPU，那么上次执行调入的缓存就完全用不上了。
2 single run queue
所有的CPU使用同一个队列，这也是可以的，有些人觉着太土，因为如果一个CPU 访问run queue的时候，其他的CPU 就不能访问run queue了，一把大锁降低了性能，尤其是当CPU特别多的时候，想想如果你有1024个CPU，然而只有一个运行队列，run queue这个瓶颈就是显而易见的了。
介绍到这里，很多筒子可能就会说了，那还有啥好纠结的，肯定是per cpu run queue 更优越。但是实际情况要比理论复杂的多。BFS（Brain Fuck Scheduler ，又称脑残调度器）就是一种单一队列的调度器，这种调度器对于桌面应用来说，效果非常的好。感兴趣的筒子可以阅读《Linux调度器BFS简介》和
per cpu run queue也不是完全没有缺点。既然是多个队列，就会有可能不均衡，比如一个CPU忙的要死，另一个CPU无事可做，这种情景本身也是对CPU资源的浪费。内核为了解决这个问题就必须要发起CPU间的负载均衡load balance，两个CPU之间负载均衡，要获取两个run queue的锁，会伤害并发，除此以外，负载均衡本身也消耗CPU资源。
我们按照我们的硬件常识，如果我有两颗物理CPU，每颗物理CPU有两个核，那么我的CPU就是4核的，每个核又可以通过SMT（Simultaneous Multi-Threading）类似的技术实现多个硬件线程或者叫做Virtual CPU，比如Intel的超线程技术，如果每个核可以实现2个Virtual CPU，那么我的硬件就有8个Virtual CPU。这些Virtual CPU 之间的亲缘关系是不同的。
为了应对多核多CPU，Linux引进了调度域的概念，其实就是根据的亲缘关系的远近，划分不同的范围。根据亲缘关系的远近从近到远分成四个层次：
1 超线程
同一个核利用超线程技术演化出来的Virtual CPU。我们知道CPU的速度要比内存访问的速度快，如果cache没有命中，CPU在等待内存的时间里面无事可做，这是一种浪费，就切换到其他线程。这样多个线程分时复用一个核。说实话，这个超线程技术我其实并不是特别理解，改天研究下Intel手册看个究竟。
2 同一个物理CPU的不同Core
3 同一个NUMA结点上的不同物理CPU
4 不同NUMA节点上的物理CPU。
NUMA（非一致性内存系统），CPU和RAM是以结点为单位分组的，同一个CPU访问本结点内的本地RAM代价要比访问其他节点的RAM代价低。CPU亲缘关系越近，他们之间进程迁移的代价越低。比如说，将进程在同一个物理CPU下的两个Core之间迁移，代价要低于不同物理CPU之间的迁移，原因就是一部分cache可以继续使用。
load balance，就是将进程从一个CPU(广义的CPU)迁移到另一个CPU，如果将进程从一个核的一个超线程域搬到另一个超线程域，没啥关系，因为代价不高，就好像让我从办公楼4楼搬到办公楼3楼，代价很低，但是CPU亲缘关系越远，代价越高，就好像上午还在南京上班，下午让我搬到乌鲁木齐上班，所以这种搬家尽量要少。事实上linux 内核也是这么做的。
OK，继续我们的调度域：假如我们有两个物理CPU，每个物理CPU有两个Core，每个Core有通过超线程演化出两个Virtual CPU，那么我们看下下面这个图（这个图是从Linux内核SMP负载均衡浅析中拷贝的）
对于每个virtual CPU，属于一组调度域sched_domain，就像我是位于雨花区的，同时我也是位于南京，我还是江苏的，我还是位于中国的，我隶属的不同区域反应的不过是不同层次看我所处的位置。每个调度域分成多个组，就好像中国分成30多个省级行政单位，每个省级行政单位又分成不同的市，每个市又分成不同的区。
这还只是普通进程的SMP 调度，想想实时进程，我们每个CPU都有队列，也许CPU-a的最高优先级的实时进程尚不如 CPU-b第二高优先级的实时进程，这时候，需要将CPU-b中的实时进程拽到CPU-a上面执行，不然，会出现低优先级的实时进程先执行的异常情况，这个拽的过程是有pull_rt_task 实现的。
参考文献
1 Linux内核SMP负载均衡浅析
2 Linux 进程调度浅析
3 鼠眼看Linux调度器
4 Linux调度器BFS简介
5 BFS，Linux桌面的极速未来