# 2.2.5 核心概念 - 优先级

在前面讨论调度类与调度策略时，我们反复地提到优先级，因为不管是调度类还是调度策略，本质上都是在对任务按照优先级排序，这一节中我们将详细探讨一下优先级在内核中的实现。

> 优先级并不是隐藏在内核中的概念，对于Linux用户而言，更加熟悉的是进程的 `nice` 值。 `nice` 值的范围是 \[-20, 19], 数字越低优先级越高。可以理解为一个进程的 nice 数值越大就对其他进程越 nice, 因此越愿意让渡自己的CPU时间，最终自己得到的时间就越少。
>
> 用户可以通过 `top` 命令的 `NI` 这一列查看进程的 nice 值， 用户可以在启动程序时指定 nice 值，也可以对已经运行的程序通过 `renice` 命令进行修改。进程启动进程时，nice 的默认值是0。

优先级是调度器工作的重要基础，优先级如何使用取决于调度类的调度算法，我们先分类来看一下：

* Deadline 进程 DL调度类使用EDF(Earliest Deadline First) 算法来对多个Deadline进程进行调度，即谁的Deadline 在前面，就选择谁来执行，优先级不在调度逻辑的考虑之中。 `struct dl_rq` 队列使用一颗红黑树来组织进程，各个节点根据进程的 deadline 排序：

  ```
  struct dl_rq {
      /* runqueue is an rbtree, ordered by deadline */
      struct rb_root_cached root;

      /* 其他字段此处被删除 */
  }
  ```

  详细的调度算法可以参见：[Deadline Task Scheduling](https://www.kernel.org/doc/html/latest/scheduler/sched-deadline.html)

  因此所有Deadline类型的进程优先级都是 -1, 该值其实相当于只是一个标识符，用来表示当前进程是Deadline类型，在系统中优先级最高，仅此而已。
* 实时进程 RT 调度类的逻辑很简单：永远挑优先级最高的进程执行，如果优先级相同，则根据调度策略进行选择。

  RT 优先级的范围是 \[1, 99], 其中99的优先级最高。
* 普通进程 普通进程被 CFS 调度，该类进程的优先级就是进程的 nice 值。CFS 的调度逻辑会在后文中详细介绍。

可见，只有实时进程与普通进程的优先级会参与调度逻辑，Linux 也提供了系统调用（System Call）来修改这两类进程的优先级，其中 `sys_nice` 用来修改普通进程的 nice 值， `sys_sched_setscheduler` 用来设定与修改调度策略与 RT 优先级。

与优先级相关的字段都在 `task_struct` 中，整理如下：

```
/* file: include/linux/sched.h */
struct task_struct {
    int prio;
    int static_prio;
    int normal_prio;
    unsigned int rt_priority;
```

* rtpriority: 实时优先级 记录上文中的实时优先级，有效范围是 \[1, 99], 数字越大优先级越高，当数值是0时表示该进程是普通进程。
* staticprio: 静态优先级 当用户通过 `sys_nice` 与 `sys_sched_setscheduler` 两个系统调用修改优先级时，改变的就是该字段。

  前文提到 nice 值的范围是\[-20, 19], 而实时优先级的有效范围是\[1, 99], 二者的重叠部分如何处理呢？

  内核在处理 nice 时会加上120, 完成 nice 值与静态优先级之间的转换，内核定义了两个宏来完成二者之间的转换，相关的代码如下：

  ```
  #define MAX_NICE 19
  #define MIN_NICE -20
  #define NICE_WIDTH (MAX_NICE - MIN_NICE + 1)
  #define DEFAULT_PRIO (MAX_RT_PRIO + NICE_WIDTH / 2)

  /* nice 与静态优先级相互转换的宏 */
  #define NICE_TO_PRIO(nice) ((nice) + DEFAULT_PRIO)
  #define PRIO_TO_NICE(prio) ((prio)-DEFAULT_PRIO)
  ```

  新进程创建时该值从父进程继承，静态优先级在进程执行过程中是不会改变的，而当其值发生改变的时候，其他相关优先级也需要重新计算（例如动态优先级）。
* normalprio: 归一化优先级 如果我们使用了不同的方式来刻画同一个概念，那么势必会带来管理上的麻烦，所谓归一化，就是设计一种转换方式，将这些不同的方法统一到同一种方法上去，从而简化问题的模型。

  例如在前文中，我们提到 rtpriority 数字越大，优先级越高；nice 值则相反，而 deadline 进程始终要维持最高优先级。为了便于管理，内核设计了一种归一化算法，将所有的优先级统一到 \[-1, 139] 这个区间上，并且数字越小优先级越大，该优先级就叫着归一化优先级。具体实现如下：

  ```
  static inline int __normal_prio(struct task_struct *p) {
      return p->static_prio;
  }

  static inline int normal_prio(struct task_struct *p) {
      int prio;

      if (task_has_dl_policy(p))
          /* MAX_DL_PRIO为0, 因此Deadline的优先级永远为-1 */
          prio = MAX_DL_PRIO - 1;
      else if (task_has_rt_policy(p))
          /* MAX_RT_PRIO为100, 而rt_priority的范围是[1,99]且数字越大对应的优先级越高，下面的算法实现了优先级反转，高优先级将对应小的数字。
           */
          prio = MAX_RT_PRIO - 1 - p->rt_priority;
      else
          /* 对于普通进程，直接返回静态优先级static_prio */
          prio = __normal_prio(p);
      return prio;
  }
  ```
* prio: 动态优先级 调度器工作时实际使用的优先级，通过函数 `effective_prio()` 计算得到，具体实现如下：

  ```
  static int effective_prio(struct task_struct *p) {
      p->normal_prio = normal_prio(p);
      /* 如果 p.prio 的值小于 100(MAX_RT_PRIO的值), 则返回 1, 否则返回 0 */
      if (!rt_prio(p->prio))
          return p->normal_prio;
      return p->prio;
  }
  ```

在各类进程的调度算法中，CFS 对优先级的使用最为复杂，也最为精巧，后续我们将详细讨论。