进程包括两类: 实时进程(优先级高); 普通进程 - 两种进程调度策略不同: task_struct->policy 指明采用哪种调度策略(有6种策略) - 优先级配合调度策略, 实时进程(0-99); 普通进程(100-139) - 实时调度策略, 高优先级可抢占低优先级进程 - FIFO: 相同优先级进程先来先得 - RR: 轮流调度策略, 采用时间片轮流调度相同优先级进程 - Deadline: 在调度时, 选择 deadline 最近的进程 - 普通调度策略 - normal: 普通进程 - batch: 后台进程, 可以降低优先级 - idle: 空闲时才运行 - 调度类: task_struct 中 * sched_class 指向封装了调度策略执行逻辑的类(有5种) - stop: 优先级最高. 将中断其他所有进程, 且不能被打断 - dl: 实现 deadline 调度策略 - rt: RR 或 FIFO, 具体策略由 task_struct->policy 指定 - fair: 普通进程调度 - idle: 空闲进程调度 - 普通进程的 fair 完全公平调度算法 CFS(Linux 实现) - 记录进程运行时间( vruntime 虚拟运行时间) - 优先调度 vruntime 小的进程 - 按照比例累计 vruntime, 使之考虑进优先级关系 - 调度队列和调度实体 - CFS 中需要对 vruntime 排序找最小, 不断查询更新, 因此利用红黑树实现调度队列 - task_struct 中有 实时, deadline 和 cfs 三个调度实体, cfs 调度实体即红黑树节点 - 每个 CPU 都有 rq 结构体, 里面有 dl_rq, rt_rq 和 cfs_rq 三个调度队列以及其他信息; 队列描述该 CPU 所运行的所有进程 - 先在 rt_rq 中找进程运行, 若没有再到 cfs_rq 中找; cfs_rq 中 rb_root 指向红黑树根节点, rb_leftmost指向最左节点 - 调度类如何工作 - 调度类中有一个成员指向下一个调度类(按优先级顺序串起来) - 找下一个运行任务时, 按 stop-dl-rt-fair-idle 依次调用调度类, 不同调度类操作不同调度队列
#define SCHED_NORMAL 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_BATCH 3
#define SCHED_IDLE 5
#define SCHED_DEADLINE 6
完全公平调度算法
首先，你需要记录下进程的运行时间。CPU 会提供一个时钟，过一段时间就触发一个时钟中断。就像咱们的表滴答一下，这个我们叫 Tick。CFS 会为每一个进程安排一个虚拟运行时间 vruntime。如果一个进程在运行，随着时间的增长，也就是一个个 tick 的到来，进程的 vruntime 将不断增大。没有得到执行的进程 vruntime 不变。显然，那些 vruntime 少的，原来受到了不公平的对待，需要给它补上，所以会优先运行这样的进程。
如何给优先级高的进程多分时间呢？这个简单，就相当于 N 个口袋，优先级高的袋子大，优先级低的袋子小。这样球就不能按照个数分配了，要按照比例来，大口袋的放了一半和小口袋放了一半，里面的球数目虽然差很多，也认为是公平的。
CPU 也是这样的，每个 CPU 都有自己的 struct rq 结构，其用于描述在此 CPU 上所运行的所有进程，其包括一个实时进程队列 rt_rq 和一个 CFS 运行队列 cfs_rq，在调度时，调度器首先会先去实时进程队列找是否有实时进程需要运行，如果没有才会去 CFS 运行队列找是否有进程需要运行。
那么上下文切换的时候，CPU的开销都具体有哪些呢？开销分成两种，一种是直接开销、一种是间接开销。
直接开销就是在切换时，cpu必须做的事情，包括：
1、切换页表全局目录
2、切换内核态堆栈
3、切换硬件上下文（进程恢复前，必须装入寄存器的数据统称为硬件上下文）
间接开销主要指的是虽然切换到一个新进程后，由于各种缓存并不热，速度运行会慢一些。如果进程始终都在一个CPU上调度还好一些，如果跨CPU的话，之前热起来的TLB、L1、L2、L3因为运行的进程已经变了，所以以局部性原理cache起来的代码、数据也都没有用了，导致新进程穿透到内存的IO会变多。 其实我们上面的实验并没有很好地测量到这种情况，所以实际的上下文切换开销可能比3.5us要大。