Linux内核的进程调度算法分析
概述
进程是操作系统的核心概念之一，也是自多任务（分时）处理系统出现以来最成功的抽象概念之一。在多任务并发系统中，对计算、存储、IO等资源的合理、高效分配是决定系统性能和稳定性的关键因素。在复杂的系统中，各种任务对资源的占用种类、时间、实时要求等有着很大的差异，对于执行任务的进程而言，这个问题就等价于如何高效、合理地对进程进行调度。
历史
Linux 2.6 以后的内核仍然存在中断、软中断、自旋锁等原子上下文进程无法抢占执行的情况，这是 Linux 内核本身只提供软实时能力的原因。
如果给 Linux 内核打上 RT-Preempt 补丁，则中断和软中断都被线程化了，自旋锁也被互斥体替换，Linux 内核变得能支持硬实时。
调度算法的常用策略
FIFO
基于优先级
轮询
时间片
O(N) 调度算法
O(1) 调度算法
CFS 调度算法
任何进程所获得的处理器时间是由它自己和其他所有可运行进程 nice 值的相对差值决定的。nice 值对时间片的作用不再是算术加权，而是几何加权。任何 nice 值对应的绝对时间不再是一个绝对值，而是处理器的使用比。
—— LKD
CFS 调度算法的核心：选择具有最小 vruntime 的任务。任务被组织成红黑树（rbtree）的结构，树上节点的键值就是可运行进程的 vruntime。
CFS 的进程选择算法可简单总结为： “运行 rbtree 树中最左边叶子节点所代表的那个进程。”