https://z.itpub.net/article/detail/4D5A28D92B6F801DF6E4C7F793969996

进程优先级：

普通任务优先级：

所有的类 Unix 操作系统都实现了优先级调度机制。它的核心思想就是给任务设定一个值，然后通过该值决定任务的重要程度。如果任务的优先级一致，则一次重复运行它们。在 Linux 中，每一个普通任务都被赋予了一个 nice 值，它的范围是 -20 到 +19，任务默认 nice 值是 0。

nice 值越高，任务优先级越低（it's nice to others）。Linux 中可以使用 nice(int increment) 系统调用来修改当前进程的优先级。该系统调用的实现位于 <kernel/shced/core.c> 中。默认情况下，用户只能为该用户启动的进程增加 nice 值（即降低优先级）。如果需要增加优先级（减少 nice 值），或者修改其它用户进程优先级，则必须以 root 身份操作。

实时任务优先级：

在 Linux 中，除了普通任务外，还有一类任务属于实时任务。实时任务是确保它们能够在一定时间范围内执行的任务，有两类实时任务，列举如下：

硬实时任务：会有严格的时间限制，任务必须在时限内完成。比如直升机的飞控系统，就需要及时响应驾驶员的操控，并做出预期的动作。然而，Linux 本身并不支持硬实时任务，但是有一些基于它修改的版本，如 RTLinux（它们通常被称为 RTOS）则是支持硬实时调度的。

软实时任务：软实时任务其实也会有时间限制，但不是那么严格。也就是说，任务晚一点运行任务，并不会造成不可挽回的灾难性事故。实践中，软实时任务会提供一定的时间限制保障，但是不要过度依赖这种特性。例如，VOIP 软件会使用软实时保障的协议传来送音视频信号，但是即便因为操作系统负载过高，而产生一点延迟，也不会造成很大影响。无论如何，软实时任务总会比普通任务的优先级更高。

Linux 中实时任务的优先级范围是 0~99，但是有趣的是，它和 nice 值的作用刚好相反，这里的优先级值越大，就意味着优先级越高。

内核视角下的进程优先级：

实时上，内核看到的任务优先级和用户看到的并不相同，在计算和管理优先级时也需要考虑很多方面。Linux 内核中使用 0~139 表示任务的优先级，并且，值越小，优先级越高（注意和用户空间的区别）。其中 0~99 保留给实时进程，100~139（映射成 nice 值就是 -20~19）保留给普通进程。

CFS：

单核调度:

CFS 的全称是 Complete Fair Scheduler，也就是完全公平调度器。它实现了一个基于权重的公平队列算法，从而将 CPU 时间分配给多个任务（每个任务的权重和它的 nice 值有关，nice 值越低，权重值越高）。每个任务都有一个关联的虚拟运行时间 vruntime，它表示一个任务所使用的 CPU 时间除以其优先级得到的值。相同优先级和相同 vruntime 的两个任务实际运行的时间也是相同的，这就意味着 CPU 资源是由它们均分了。为了保证所有任务能够公平推进，每当需要抢占当前任务时，CFS 总会挑选出 vruntime 小的那个任务运行。

内核版本在 2.6.38 之前，每个线程（任务）会被当成独立的调度单元，并且和系统中其它线程共享资源，这就意味着一个多线程的应用会比单线程的应用获得更多的资源。之后，CFS 不断改进，目前已经支持将一个应用中的线程打包到 cgroup 结构中，cgroup 的 vruntime 是其中所有线程的 vuntime 之和。然后 CFS 就可以将它的算法应用于cgroup 之间，从而保证公平性。当某个 cgroup 被选中后，其中拥有小 vruntime 的线程会被执行，从而保证 cgroup 中的线程之间的公平性。cgroup 还可以嵌套，例如 systemd 会自动配置 cgroup 来保证不同用户之间的公平性，然后在用户运行的多个应用之间维持公平性。 

CFS 通过在一定时间内运行调度所有的线程来避免饥饿问题。当运行的 线程数在 8 个及以下时，默认的时间周期是 48ms；而当多于 8 个线程时，时间周期就会随着线程数量而增加（6ms * 线程数，之所以选择 6ms，是为了避免频繁抢占，导致上下文切换频繁切换的开销）。由于 CFS 总是会挑选 vruntime 小的线程执行，它就需要避免某个线程的 vruntime 太小，以至于其它线程需要等待很久才能得到调度（会有饥饿问题）。所以在实践中，CFS 会保证所有线程之间的 vruntime 之差低于抢占时间（6ms），它是通过如下两点来保证的：

当线程创建时，它的 vruntime 值等于运行队列中等待执行线程的大 vruntime；

当线程从睡眠中唤醒时，它的 vruntime 值会被更新为大于或等于所有待调度线程中小的 vruntime。使用小 vruntime 还可以保证频繁睡眠的线程优先被调度，这对于桌面系统非常适合，它会减少交互应用的响应延迟。

CFS 还引入了启发式调度思想来改善高速缓存利用率。例如，当线程被唤醒时，它会检查该线程的 vruntime 和正在运行的线程 vruntime 之差是否非常显著（临界值是 1ms），如果不是的话，则不会抢占当前正在运行的任务。但是这种做法还是以牺牲调度延迟为代价的，算是一种权衡吧。 

多核负载均衡:

在多核环境中，Linux CFS 会将工作（work）分摊到多个处理器核心中执行。但是这不等同于将线程均分到多个处理器。比如，一个 CPU 密集型的线程和 10 个频繁睡眠的线程可能分别在两个核上执行，其中一个专门执行 CPU 密集型线程；而另一个则处理那 10 个频繁睡眠的线程。 

为了多个处理器上的工作量均衡，CFS 使用了 load 指标来衡量线程和处理器的负载情况。线程的负载和线程的 CPU 平均使用率相关：经常睡眠的线程负载要低于不睡眠的线程负载。类似 vruntime，线程的负载也是线程的优先级加权得到的。而处理器的负载是在该处理器上可运行线程的负载之和。CFS 会尝试均衡处理器的负载。 

CFS 会在线程创建和唤醒时关注处理器的负载情况，调度器首先要决定将任务放在哪个处理器的运行队列中。这里也会涉及到启发式思想，比如，如果 CFS 检查到生产者-消费者模型，那么它会将消费者线程尽可能地分散到机器的多个处理器上，因为多数核心都适合处理唤醒的线程。

负载均衡还会周期性发生，每隔 4ms，每个处理器都会尝试从其它处理器偷取一些工作。当然，这种 work-stealing 均衡方法还会考虑机器的拓扑结构：处理器会尝试从距离它们「更近」的其它处理器上尝试窃取工作，而非距离「更远」的处理器（如远程 NUMA 节点）。当处理器决定要从其它处理器窃取任务时，它会尝试在二者之间均衡负载，并且会窃取多达 32 个线程。此外，当处理器进入空闲状态时，它也会立刻调用负载均衡器。

在大型的 NUMA 机器上，CFS 并不会粗暴地比较所有 CPU 的负载，而是以分层的方式进行负载均衡。以一台有两个 NUMA 节点的机器为例，CFS 会先在 NUMA 节点内部的处理器之间进行负载均衡，然后比较 NUMA 节点之间的负载（通过节点内部处理器负载计算得到），再决定要不要在两个节点之间进行负载均衡。如果 NUMA 节点之间的负载差距在 25% 以内，则不会进行负载均衡。总结来说，如果两个处理器（或处理器组）之间的距离越远，那么只有在不平衡性差距越大的情况下才会考虑负载均衡。

运行队列:

CFS 引入了红黑树（本质上是一棵半平衡二叉树，对于插入和查找都有 O(log(N)) 的时间复杂度）来维护运行队列，树的节点值是调度单元的 vruntime，拥有小 vruntime 的节点位于树的左下边。

虚拟时钟:

前面提到的 vruntime 究竟是什么呢？为什么叫作虚拟运行时间呢？接下来就要揭开它的神秘面纱。为了更好地实现公平性，CFS 使用了虚拟时钟来测量一个等待的调度单元在一个完全公平的处理器上允许执行的时间。然而，虚拟时钟并没有真实的实现，它只是一个抽象概念。

我们可以基于真实时间和任务的负载权重来计算出虚拟运行时间，该算法是在 update_cur() 函数中实现的，它会更新调度单元的时间记账信息，以及 CFS 运行队列的 min_vruntime（完整定义位于 <kernel/sched/fair.c>）：

来总结下使用虚拟时钟的意义：

当任务运行时，它的虚拟时间总是会增加，从而保证它会被移动到红黑树的右侧；

对于高优先级的任务，虚拟时钟的节拍更慢，从而让它移动到红黑树右侧的速度就越慢，因此它们被再次调度的机会就更大些。

选择下一个任务:

CFS 可以在红黑树中一直找到左（leftmost）边的节点作为下一个运行的任务。但是真正实现 __pick_first_entity() 的函数其实并没有真正地执行查找（虽然可以在 O(log(N)) 时间内找到），我们可以看下它的定义（完整定义位于 <kernel/sched/fair.c>）： 

实时调度器:

Linux 实时任务调度器实现位于 <kernel/sched/rt.c，对于系统而言，实时任务属于贵客，一旦存在实时任务需要调度，那就应当尽可能及时地为它们服务。对于实时任务而言，有两种调度策略存在：

SCHED_FIFO: 这个其实就是一个先到先服务的调度算法。这类任务没有时间片限制，它们会一直运行直到阻塞或者主动放弃 CPU，亦或者被更高优先级的实时任务抢占。该类任务总会抢占 SCHED_NORMAL 任务。如果多个任务具有相同的优先级，那它们会以轮询的方式调度（也就是当一个任务完成后，会被放到队列尾部等待下次执行）；

SCHED_RR: 这种策略类似于 SCHED_FIFO，只是多了时间片限制。相同优先级的任务会以轮询的方式被调度，每个运行的任务都会一直运行，直到其用光自己的时间片，或者被更高优先级的任务抢占。当任务的时间片用光后，它会重新补充能量，并被加入到队列尾部。默认的时间片是 100ms，可以在 <include/linux/sched/rt.h> 找到其定义。

实时任务的优先级是静态的，不会像之前提到的算法，会重新计算任务优先级。用户可以通过 chrt 命令更改任务优先级。