Linux的调度策略区分实时进程和普通进程，实时进程的优先级要高于普通进程。
当系统中有实时进程运行时，普通进程几乎是无法分到时间片的（只能分到5%的CPU时间）。 linux服务器上很少有实时进程，除非手动设定。大部分都是普通进程。
实时调度策略被实时调度器管理，普通调度策略被完全公平调度器来管理。
Linux提供了两种实时调度策略：SCHED_FIFO 和 SCHED_RR
SCHED_FIFO是一个简单的先进先出的调度算法，没有时间片的概念。一个实时进程只有在阻塞、主动放弃处理器或者被更高优先级的实时进程抢占时才会暂停或者停止运行。同等优先级的进程使用循环（round-robin）的方式运行，但是也只有在实时进程阻塞或者主动放弃处理器时，才会执行循环队列中的下一个进程。低优先级的实时进程无法抢占高优先级的实时进程，高优先级的实时进程进入runnable状态时，总是会立刻抢占低优先级的实时进程。
SCHED_RR是SCHED_FIFO加上时间片的版本，每个实时进程用完时间片后，其他和该实时进程优先级相同的实时进程可以被调度。但是低优先级的仍然不会被调度，直到没有比它优先级更高的实时进程时才会被调度。和SCHED_FIFO一样，高优先级的实时进程总是可以立刻抢占低优先级的实时进程。
通过这两个调度策略，Linux提供了一个软实时调度，和硬实时调度的区别在于，软实时调度会尽力使进程能在deadline之前运行，但是不保证一定能做到。而硬实时调度就是保证可以满足任何调度要求。虽然不能做到硬实时调度，但是Linux的实时调度算法性能还是不错的。
参看：linux 进程优先级之设置实时进程
思考：实时进程会抢占普通进程，但是普通进程仍有5%的时间来运行任务而不至于饿死。Linux中的调度程序是在不断发展完善的，2.6.23内核开始采用CFS调度程序。
SCHED_NORMAL使用完全公平调度算法（CFS），之前的算法直接将nice值对应时间片的长度，而在CFS中，nice值只作为进程获取处理器运行比的权重，每个进程都有一个权重，nice优先级越高，权重越大，表示应该运行更长的时间。Linux的实现中，每个进程都有一个vruntime字段，vruntime是经过量化的进程运行时间，也就是实际运行时间除以权重，所以每个量化后的vruntime应该相等，这就体现了公平性。
CFS当然也支持抢占，但与实时调度算法不同，实时调度算法是根据优先级进行抢占，CFS是根据vruntime进行抢占，vruntime小就拥有优先被运行的权利。
CFS是基于下面的理念的：假设一个有着n个进程的系统中有一个理想的、完美的多任务处理器，每个进程都将获得1/n的处理器时间。即确保任何可测量周期内，每个进程都运行相同多的时间，假设有两个进程，在10毫秒周期内，每个总的运行时间都是5ms，那么理想情况下，我们可以视作每个进程都运行了10ms，每个使用了50%的CPU性能，这种模型被称为完美的多任务处理系统。但是实际上这种模型是不实际的，因为没有考虑到进程切换的代价：一方面是切换操作的成本，另一方面是会对cache命中率造成影响。CFS会让每个进程运行一段时间，调度时选择当前执行时间（使用的是virtual runtime）最少的进程作为下一个运行的进程。CPU使用nice值来计算每个进程获得的处理器比例（processor proportion），nice值越大（优先级越低）获得的处理器比例越低。同时系统中的进程越多，每个进程获得的处理器比例也越低。
CFS会设定一个目标周期（target latency），根据每个进程的处理器比例分配一个目标周期总的“时间片”。目标周期设定得越小，每个进程获得的时间片就越小，系统的交互响应速度就越快，但同时进程切换的开销也越大。假设目标周期设定为20ms，每个进程的优先级相同，即处理器比例相同，那么如果有2个进程，每个进程的时间片为10ms，如果有4个进程，每个进程的时间片为5ms，如果有20个进程，时间片将为1ms。如果进程数无限增加，那么每个进程的时间片将趋近于0。很明显，这将导致不可接受的进程切换开销。所以CFS为时间片设定了一个最小粒度（minimum granularity），默认为1ms。这是为了保证系统性能做的trade-off，这种情况下并不是完全公平（completely fair）。但是时间片没有超过最小粒度之前，CFS仍然是完全公平的。
CFS中vruntime计算方法可参看 CFS（Completely Fair Scheduling）中vruntime计算方法。
CFS由四个组件组成：
运行时间记录（Time Counting）进程选择（Process Selection）调度程序入口（The Scheduler Entry Point）睡眠和唤醒（Sleeping and Waking Up）调度程序需要记录进程运行的时间，CFS使用调度程序实体结构（scheduler entity structure）来记录进程运行时间，该结构使用struct sched_entity来存储，进程描述符task_struct结构中的se保存每个进程的sched_entity。 sched_entity中的vruntime保存进程的虚拟运行时间（即实际运行时间经过加权计算后的时间），vruntime的单位是纳秒，所以不受系统的timer tick的粒度限制。在一个理想的完美多任务操作系统中，每个进程的vruntime应该都是相同的（实际环境中做不到）。内核使用update_curr()函数来更新运行进程的vruntime，系统时钟（system timer）会定期调用update_curr()，此外每当有进程进入runnable状态或者blocked状态时，也会调用update_curr()来更新vruntime。
虽然无法做到让每个进程的vruntime相同，但是我们可以使vruntime尽可能的接近，所以CFS每次会选择vruntime最小的进程来运行。CFS使用红黑树来管理所有处于runnable状态的进程，使用进程的vruntime作为红黑树的key。红黑树是一种平衡二叉查找树，树最左边的节点是树的最小值，所以CFS每次都会选择最左边的节点的进程来运行，实际上，CFS并不会每次对红黑树进程查找，它使用rb_leftmost来存储最左边的节点，这样将查找最小节点的时间复杂度从O(lgN)降到了O(1)。如果红黑树为空，意味着没有runnnable的进程，此时CFS会选择idel task（PID为0的进程）来执行。
每当有进程进入runnable状态或者通过fork()创建了一个新的进程时，CFS就会将该进程加入红黑树。每当有进程进入blocked状态或者停止执行（terminate）时，CFS会将该进程从红黑树中移除。
最主要的调度程序入口是schedule()函数。schedule()函数会找到优先级最高的调度类（scheduler class），并从该调度类获得下一个要运行的进程，如果该调度类没有runnable进程，就会检查优先级次高的调度类，以此类推。例如，CFS是用来调度普通进程（normal process）的，调度实时进程（real-time process）的调度类优先级比CFS更高，所以会先检查实时进程的调度类，然后才到CFS。
睡眠状态（sleeping），即阻塞状态（blocked）是一种特殊的不可运行（nonrunnable）状态。进程进入睡眠状态的原因多种多样，比如等待I/O完成或者是请求的资源暂时无法获得等。不管是什么情况，在内核中的表现是一样的：进程将自己标识为sleeping，将自己加入等待队列（wait queue），并将自己从runnable进程的红黑树中移除，然后调用schedule()，让调度器选择一个新的进程去执行。唤醒（waking up）是相反的：进程被标识为runnable，被从wait queue中移除，并插入runnable进程红黑树中（不一定马上运行，需要调度器选中它才可以运行）。
等待队列(wait queue)有很多个，每个等待队列存储等待某个特定事件的所有进程。当某个事件发生时，内核会唤醒该事件对应的等待队列上的所有进程。通常是导致该事件发生的代码调用wake_up()来唤醒该数据的等待队列上的所有进程。比如当磁盘中的数据读取完成时，VFS会调用wake_up（）。
CPU从一个进程切换到另一个进程需要进行上下文切换，schedule()会调用context_switch()函数来完成上下文切换。该函数首先会调用switch_mm()将虚拟内存映射从上一个进程的切换到下一个进程的（这意味着TLB的内容全部失效了，需要从0开始缓冲。对TLB切换的一个优化是保留上一个进程除高端内存的内核空间地址映射，因为这部分对所有进程来说是一样的，都是直接线性映射），然后调用switch_to()来保存上一个进程的处理器状态并恢复下一个进程的处理器状态，包括栈信息、处理器寄存器和其他架构相关的每个进程自有（per-process）的处理器状态。
内核必须要知道什么时候该调用scheduler()，如果只让进程自己主动调用scheduler()的话，用户程序可以无限期地运行下去，这显然是不行的。内核使用need_resched flag来表明是否应该调用scheduler()。scheduler_tick()和try_to_wake_up()（当优先级比正在执行的进程高的进程被唤醒时try_to_wake_up()会被调用）都可能会设置need_resched。need_resched用来告诉内核有一个进程“更值得”运行，应该尽快调用scheduler()。
对于用户空间进程，调度可能会发生在（need_resched被设置时才会调用调度器）：
进程从系统调用中返回用户空间之前进程从中断处理程序中返回用户空间之前内核进程也是可以被抢占的，但是和用户进程有些不一样，当正在运行的进程是内核进程时，还要判断内核进程是否持有锁(lock），内核进程每获得一个锁，preempt_count就会加1，只有preempt_count为0且need_resched被设置时才会调用调度器。
对于内核空间进程，调度可能会发生在：
中断处理程序退出，在返回内核空间之前内核进程可以被抢占时（即preempt_count变为0时）内核进程自己主动调用scheduler()内核进程阻塞（阻塞的结果是scheduler()会被调用）有五种调度类：
fair_sched_class，现在较高版本的Linux上也就是CFS(Completely Fair Scheduler)，Linux上面主要的调度方式，由CONFIG_FAIR_GROUP_SCHED宏控制 rt_sched_class，由CONFIG_RT_GROUP_SCHED宏控制，实时调度类型。 dl_sched_class，deadline调度类，实时调度中较高级别的调度类型，一般之后在系统紧急情况下会调用； stop_sched_class，最高优先级的调度类型，属于实时调度类型的一种，在系统终止时会在其上创建进程进入调度。 idle_sched_class，优先级最低，在系统空闲时才会进入该调度类型调度，一般系统中只有一个idle，那就是初始化进程init_task，在初始化完成后它将自己设置为idle进程，并不做更多工作。首先需要关闭抢占，防止调度重入，然后调用__schedule，进行current相关的处理，比如有待决信号，则继续标记状态为TASK_RUNNING，或者如果需要睡眠则调用deactivate_task将从运行队列移除后加入对应的等待队列，通过pick_next_task选择下一个需要执行的进程，进行context_switch进入新进程运行。
首先判断当前进程调度类sched_class是否为fair_sched_calss，也就是CFS，如果是且当前cpu的调度队列下所有调度实体数目与其下面所有CFS调度类的下属群组内的调度实体数目总数相同，即无RT等其他调度类中有调度实体存在（rq->nr_running == rq->cfs.h_nr_running），则直接返回当前调度类fair_sched_class的pick_next_task选择结果，否则需要遍历所有调度类for_each_class(class)，返回class->pick_next_task的非空结果。
这里需要关注的是for_each_class的遍历过程，从sched_class_highest开始，也就是stop_sched_class。
#define sched_class_highest (&stop_sched_class) #define for_each_class(class) \ for (class = sched_class_highest; class; class = class->next) extern const struct sched_class stop_sched_class; extern const struct sched_class dl_sched_class; extern const struct sched_class rt_sched_class; extern const struct sched_class fair_sched_class; extern const struct sched_class idle_sched_class;按照优先级依次罗列组成单链表：
stop_sched_class->next->dl_sched_class->next->rt_sched_class->next->fair_sched_class->next->idle_sched_class->next=MULL在编译过程中通过early_initcall(cpu_stop_init)进行stop相关的注册，cpu_stop_init对cpu_stop_threads进行了注册，其create方法被调用时实际执行了cpu_stop_create->sched_set_stop_task，对stop的sched_class进行注册，create的执行路径如下：
cpu_stop_init-> smpboot_register_percpu_thread-> smpboot_register_percpu_thread_cpumask-> __smpboot_create_thread-> cpu_stop_threads.create(即cpu_stop_create)现在回到pick_next_task，由于stop_sched_class作为最高级别调度类将所有系统中的调度类链接起来，遍历过程查看所有sched_class，从最高优先级开始，直到找到一个可以调度的进程返回，如果整个系统空闲，则之中会调度到系统初始化进程init_task，其最后被设置为idle进程在系统空闲时的调度执行，上面对sched_init的解释里面有详细说明。
参考： https://blog.csdn.net/damontive/article/details/80494997 https://blog.csdn.net/Vince_/article/details/89054330
