2.2.5 核心概念 - 优先级

简要介绍任务的优先级,即Priority

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

优先级并不是隐藏在内核中的概念,对于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

    因此所有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_nicesys_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 对优先级的使用最为复杂,也最为精巧,后续我们将详细讨论。

Last updated