项目经验分享：在Linux内核中添加一个任务调度器

发表于 3年以前 | 总阅读数：490 次

各位参与开源之夏的同学们，大家好，下面的文字我将带大家一起看看这个暑假我在openEuler参与的开源项目。

近几天的西安接连下了数场雨，一夜之间从短袖换起了长衣，丝丝寒意也在告诉我大二的暑假就这样结束了。

还好，这个假期有幸参与到Linux内核的学习的过程中来，虽然一路以来遇到重重困难，但好在有导师和前人的博客书籍的帮助，收获也算颇丰。

写下这段话时我刚刚起床，窗外的秋雨还在淅淅沥沥地下，没睡醒的我打开电脑，今日的必应壁纸也呼应着没睡醒的我，为什么是不太清醒呢，因为清醒哪会有这种颜色。清醒的时候都是横平竖直的，花是红的，天是蓝的，花的颜色跑进天上，天的颜色又钻进人心里的时刻，怎么能是清醒呢。*

洗把脸，收拾起心情，清醒起来，让我们开始吧！

进程的生存法则

我们先清楚一个概念：为什么会存在任务调度的行为？

计算机上进行的任务有成百上千，但负责处理运行任务的硬件资源却是屈指可数，那同一时刻，也只能有相对较少的任务得到并行计算处理，大部分任务是等待执行的。为了权衡好硬件成本与任务计算效率，达到全局最优的目的，调度任务在有限硬件资源上运行的组件就诞生了 -- 任务调度器(Scheduler)。

计算机上的任务各有各的特点，部分任务对时间比较敏感，这类任务如果不能及时分得CPU资源处理，则会产生卡顿不连贯。例如与用户交互类型的应用，想象当你在计算机上打字时屏幕上缺迟迟不显示没有反应。有些任务则是计算密集型对时间不敏感，只需要更多的时间来计算，及时响应与什么时候完成没有非常重要，这类任务例如MATLAB、编译器这类需要大量使用CPU计算时间然而不需要及时响应。

Linux内核作为一个通用的操作系统，需要兼顾完成各种各样行为特征的任务，有批处理任务、实时任务和交互式任务等。为了对CPU资源的利用率达到尽可能的高同时还兼容各种任务需求，我们的系统需要任务调度器通过一定的算法来分配CPU资源给不同任务，在任务相应迅速和最大系统利用率中寻找平衡。

为了进一步了解任务调度，我们从进程状态引入，循序渐进地了解现代Linux中调度器的实现。

进程的状态

三态模型

简便期间，先从传统的操作系统教材给出进程的三态模型入手：

由于计算机资源有限，不可能同一时刻所有任务都可以得到计算运行，因此操作系统大致上将任务在某一时刻划分为三种状态，分别是：

得到计算资源的 运行态 Running
无需计算资源的 阻塞/睡眠态 Block
需要计算资源但无法立即得到只能等待被分配的 就绪 Ready

当一个进程被调度器选中得到CPU计算资源正在运行时，其状态为运行；一旦进程产生请求IO、系统调用等主动放弃CPU的行为，进程状态转换为阻塞；一旦任务结束IO或使用完单次最大CPU时间后进程进入等待运行的队列，处于就绪态。

Linux进程状态实现

对于活跃的进程，Linux将其进程区分为两大类：运行与睡眠

Linux中没有严格区分进程的就绪和运行态，认为两种状态的任务其实都是需要CPU计算资源只不过是一种任务正在被CPU计算处理，另一种任务等待CPU资源。在对进程状态标识上，传统意义的就绪和运行均被表示为宏TASK_RUNNING状态

传统概念的睡眠进程被细分成了三种状态：

轻度睡眠 TASK_INTERRUPTIBLE可被信号打断的睡眠
中度睡眠 TASK_KILLABLE: 只能被致命信号打断的睡眠
重度睡眠 TASK_UNINTERRUPTIBLE:不能被任何信号打断的睡眠

我们可以看到，其实处于Ready的进程也是只要给CPU资源，就能马上能被投入运行的，奈何CPU资源有限，现在被其他任务所占，只能在就绪队列中等待运行。等待需要时间成本，那么为了更好地将就绪任务及时放到CPU上运行，有没有一种抽象专门负责系统中任务高效合理地调度迁移呢？有，这就是我们要引入的进程调度器。

纵览Linux下的五种任务调度器

对于不同类型有不同特点的任务，Linux内核提供了五种调度器管理这些任务

<center>这五种调度中stop调度器和idle-task调度器，仅由内核使用，用户无法进行选择。</center>

每一个进程会隶属于某一种调度策略，某一个调度器可能有多种调度策略，管理这些策略的任务。

我们来思考一下，作为一类任务的调度管家，这个管家需要做哪些事呢？

当CPU有空闲时，为了达到高效利用CPU的目的，如何选择下一个即将运行的任务。
对与多处理器系统，调度器涉及到选核与任务在核心上迁移功能。
为了掌握CPU负载情况，我们需要统计负载，可以进行负载控制和负载均衡。

对于所有调度器，Linux内核采用面向对象的程序设计思想中的多态机制，使用struct sched_class来作为基类表示调度类的抽象，其结构体将作为某一任务task_struct的成员表示负责管理该任务的调度器，使用的调度策略将在__sched_setscheduler()中对task_struct中policy字段进行设置。

我们可以清晰地看到，sched_class中充满了大量的函数指针，这些函数指针也就是上述提到某一调度器要实现的调度功能，这些功能可能会因不同调度器的不同而不同。

对于调度器内部任务的管理，enqueue_task dequeue_task 负责将新任务添加到等待被调度的等待队列及将任务从等待队列中移除，yield_task yield_to_task pick_next_task put_prev_task set_next_task check_preempt_curr涉及到选任务，对于多核SMP架构的系统有相关的负载控制功能，同样对于时钟调度、子进程生成、子进程结束等调度处理也有相关实现。

我们再移步到task_struct中调度相关的部分，我们可以看到，const struct sched_class *sched_class;成员，该成员将在任务初始化时被分配具体调度器，这将会在sched\_fork()函数中进行，不同的调度类将会被赋予不同的派生类值，例如某一任务由CFS调度器管理，那么这个任务的task_struct中的sched_class指针将指向派生类fair_sched_class。

CFS调度器的调度结构体实现中，我们可以看到这里的成员对应着task_struct中的sched_class指针成员的基类型结构体成员，函数指针在这里被指定了对应的实现，例如该调度器将某个任务添加到调度器的等待队列中的enqueue_task方法被指定成为enqueue_task_fair

等待队列

由于系统中总有任务需要等待分配CPU资源而处于就绪态，因此在Linux内核中，内核会给每个CPU分配一个全局的就绪队列/等待队列(struct rq)，每一个就绪队列中会有在该CPU上等待运行的所有任务，不过这个所有任务会进一步细分，每一个任务都属于某个调度器管理，调度器中也有属于自己管理任务的就绪队列，所有调度器管理的任务的就绪队列最终会汇集到每个CPU的全局就绪队列上，最终操作就绪队列一定也就是指定到某个调度器的就绪队列上。

简便期间，这里将简化全局队列struct rq和CFS调度器的就绪队列struct cfs_rq成员，看看其实现：

我们可以看到，每一个CPU上的struct rq内部并内有直接的任务数据结构，而是将其细分成三种调度器队列，这些队列中才有真正管理任务的数据结构。CFS调度器管理的任务队列中有记录队列权重、队列上任务数量、任务最小虚拟时间、任务红黑树等成员。

调度程序 -- 调度时

`schedule()`之主动调度

一个进程可能由于需要IO或定时器到时等其他情况从而主动释放 CPU 的控制权，这时他会主动调用 schedule() 调度函数，从而调度程序将调度其它进程占用 CPU。

schedule() 函数从事了大量的工作，包括保存程序状态，选任务，调度运行。

当这个主动放弃 CPU 的进程被重新调度占用 CPU，由于那么它将从上次停止执行的位置开始执行，也就是说它将从调用 schedule() 的下一行代码处开始执行。进程一般都是用调用schedule() 进入睡眠状态的，如下的伪码大致展示如何被调度且进入睡眠状态。

sleeping_task = current;

set_current_state(TASK_INTERRUPTIBLE);

schedule();      --      wake_up_process(sleeping_task); // 将进程重新标记为TASK_RUNNING放入调度器的就绪队列中

// Continue
func();

下图展示了schedule() 函数的大致逻辑：

`schudule_tick()`之时钟周期调度

`wake_up_process()`之进程唤醒调度

进程切换 -- 调度本质

调度触发点 -- 调度标志

Linux内核在每个进程中的strcuct thread_info中的flag的某几位上标识TIF_NEED_RESCHED目前该任务是否需要被抢占重新调度，内核在即将返回用户空间时会检查标识TIF_NEED_RESCHED标志进程是否需要重新调度，若被标识则会调用schedule()函数进行调度。

内核中多处涉及到了设置TIF_NEED_RESCHED标志，统一调用resched_curr --> set_tsk_need_resched来设置

check_preempt_tick 时钟中断
check_preempt_wakeup 进程被唤醒时，被唤醒的进程可能抢占当前进程，此时会标记
fork --> _do_fork创建新进程时，新进程可能抢占当前进程，此时会标记
set_user_nice 修改进程nice值的时候，此时会标记新建子进程
__migrate_swap_task 任务在CPU间迁移时
smp_send_reschedule 负载均衡时

给某个进程设置完待调度标志后，在特殊的 调度时机 调用need_resched()检查是否有调度标志，再进行schedule()调度

调度时机 -- 执行 __schedule()

用户抢占

1. 进程主动放弃CPU，调用schedule()函数

2. 从内核态的 系统调用/中断/异常处理程序返回到 用户态空间 时，可以进行schedule()调度 (像时钟中断、fork新建进程等行为后会判断是否调度)

内核抢占

内核抢占是指当进程运行在内核模式放入时候可以被其他进程抢占，支持内核抢占可以防止运行在内核模式下的进程过长占用CPU时间导致交互类应用无法及时响应，尤其在桌面系统这种要求更快响应速度场景下可能会产生卡顿。开启对内核抢占的支持后，会多出现几个调度时机

0 . 主动调用/进程受阻塞调用schedule()

i.e. a . 调用local_bh_enable()开启软中断时 b . 调用spin_unlock()释放自旋锁时

1 . 在系统调用或者异常中断上下文中调用preempt_enable() 2 . 从中断处理程序返回到内核空间前preempt_schedule_irq()

`preempt_count` -- 抢占计数器

每个进程task_struct中的thread_info都有一个int类型preempt_count成员，这个成员作为抢占计数器，抢占、中断处理函数可能会将不同部分的计数加或减数。

preempt count低8位用于控制抢占，当大于0时表示不可被抢占，等于0表示可以被抢占

VIP任务调度器

本次题目要求我们实现一个这样的任务调度器

1、具有较CFS任务更高一级，但是较RT任务低的抢占优先性，VIP调度类内部任务之间抢占优先性按照CFS 的抢占优先性规则来实现。

>> 抢占是内核抢占&用户抢占导致触发__schedule()函数进行选任务和切换上下文的。这批任务和普通CFS任务没有优先性，抢占上属于同一优先级是不行的，为了让这批任务VIP调度策略任务具有抢占优先性，就建立一个VIP调度类，在RT和CFS中间，以实现抢占时较CFS具有更高抢占优先性。

VIP任务内部按照CFS处理策略，这是实现任务内部的抢占优先性

2、具有 TOP-N 的选核策略，选择每个核上VIP负载最低最空闲的核运行，同时保证CPU的capacity > 任务的util;

3、按照任务的权重进行划分优先级，与CFS一致；

4、按照CFS的选任务机制，根据vruntime的大小选择最小的vruntime任务；

5、具有CPU bandwidth和load-balance功能；

最高理想

一台理想的计算机上，可以并行(同时运行)任意多数量的任务。

VIP调度器选任务的策略与CFS调度器类似，我们要试图达到一种“理想化的多核CPU”系统，CPU全部的计算能力将会被所有的任务以等大的速率并行运行瓜分，每个任务将会分得CPU_speed * 1/number_of_running_tasks 大小的速度。

例如：一台计算机上有同等优先级的N个进程，每个进程应得到机器算力的1/N，一个进程运行需要10分钟，如果5个进程在此理想计算机上运行，每个进程将会得到CPU算力的20%，每个进程并行执行，那么每个进程将需要50min时间运行

因此该调度器的设计基本可以用一句话概括：在真实硬件上模拟“理想的、精确的多任务 CPU”。

接入

添加内核开关，可选开关该调度器

我们新设置一种调度策略SCHED_VIP，采用这种策略管理的任务由VIP调度器调度

我们通过sched_setscheduler(pid_t, SCHED_POLICY, struct sched_param*)函数设置某一任务使用SCHED_VIP调度策略被VIP调度器调度。

由于采用SCHED_VIP调度策略的任务优先级应高于CFS调度器管理任务，低于RT调度器管理任务，因此在对任务优先级设置时，将原有的priority:``0-99 RT | 100-139 CFS 拓展成为 0-99 RT | 100-139 VIP | 140-179 CFS，对应的优先级计算如下：

接下来我们将VIP调度实体与VIP调度器的就绪队列添加到struct task_struct与struct rq中，完成上层调度器接口的添加。

调度器优先性

还记得上面我们介绍struct sched_class时介绍的第一个成员吗？const struct sched_class *next定义了某个调度器的优先级顺序。

我们看到在RT调度器中，若在VIP调度器开启的状态下，RT调度器对应下一个优先级调度器是VIP调度器，

对于VIP调度器，下一个层级调度器为CFS调度器

我们依靠struct sched_class中的next成员就可以依次遍历从高到低优先级的调度器，这点在内核中for_each_class(class)、for_class_range(class, _from, _to)宏等多处得到了使用

这样就实现了调度器间的优先性，内核中多出也应用了这点，例如

在我们调用pick_next_task()选任务时，会有默认先从CFS中选任务的这一步优化，当选任务失败时就进入到上图所示代码段，对所有优先级调度器按照调度器优先性由高到低遍历选其中需要被调度任务直到选到返回。

选任务

调度实体

调度器调度的抽象实体即为调度实体，调度实体既可以对应单个进程，也可以对应一个进程组，这个进程组可能是下面将谈到的组调度中按照用户来分的进程组，也可能是按照使用Cgroup进行分组的一组进程。

若是对应进程，则在task_struct中有各个调度器sched_entity*指向到对应的调度实体，若是进程组，则有task_group的.se[CPU_id]对应组调度实体(group se)。

内核使用struct sched_entity数据结构来统一抽象要调度的任务：

重点成员摘要：

load: 该调度实体权重，若这个调度实体对应一个task_group，则为整个group中entity的load之和

run_node: 每个CPU上的rq中vip_rq都维护了一棵红黑树管理调度实体的调度，这个成员用来将这个调度实体连接到这个树上的对应位置

on_rq: 调度实体是否在就绪队列上，是1，否0

sum_exec_runtime: 调度实体运行时间总和

vruntime: 调度实体运行虚拟时间总和

vip_rq: 如果这个任务是VIP调度器管理的，那么这是该任务归属的vip队列指针

vip_my_q: 若该任务是VIP调度器管理的，且调度实体对应task\_group，则这个调度实体会有一个就绪队列，管理本组任务的调度

组调度

Linux是一个多用户系统，我们可以想象，假设有两个用户，一个用户运行两个任务，另外一个用户运行八个任务，假设任务间优先级相同，那么用户一将分得全部CPU资源的20%，用户二将分得全部CPU资源的80%，随着第二个用户逐渐增加任务，提高任务优先级，第一个用户会相对而言得到越来越少的CPU资源，这对两个用户各自而言是不公平的。若根据用户组来分得CPU资源，两个用户将会各自分得50%的CPU资源，这也就符合我们的期望，满足公平分得CPU的策略。

这种基于组的调度方式，被称为组调度，Linux内核提供两种进程分组方式，一种是根据不同用户对用户任务间进行分组，另一种是通过配置的Cgroup组来分组设置CPU使用率。

为了管理组调度，内核引入了struct task_group数据结构：

每个进程组task_group中，会对每个CPU上分配一个cfs_rq、vip_rq和rt_rq，表示对应调度器的任务组就绪队列，同样也会对每个CPU上分配一个se、vip和rt_se对应进程组的抽象调度实体(group se)

到现在，我们认识到对于内核的调度器来说，它们调度的对象可以是进程，还可以是一个用户组或cgroup(task_group)对应的调度实体。

就绪队列

调度器调度的单位是进程即task_group，对于VIP调度器调度的任务，我们采用struct vip_rq数据结构内嵌到每个CPU的struct rq内部，vip_rq内部又采用红黑树管理任务

load: 队列上所有调度实体权重之和，其作为队列权重

nr_running: 就绪队列上调度实体的个数

h_nr_running: 仅对进程组有效，所有进程组中nr_running之和

min_vruntime：就绪队列上所有调度实体中最小虚拟时间

tasks_timeline：按虚拟时间大小排序的调度实体红黑树

CPU、全局就绪队列、VIP就绪队列、调度组、调度实体间的关系图

图中仅仅以双核CPU系统做示例，每个CPU上有一个全局就绪队列struct rq，我们以其中VIP调度器管理任务为例，其内部拥有一棵由调度实体sched_entity组成的任务管理红黑树。红黑树上的结点有两种类型，一种sched_entity对应进程，一种sched_entity对应进程组，这个group entity的vip_my_q成员将不为空，其将指向进程组内部的队列数据结构。图中只演示了一个任务组A，这个任务组在两个CPU上各有一个VIP队列，当然我们可以多分几个组，那么每个CPU就可能会有来自不同任务组的任务组队列。当然，任务组下还可以继续嵌套任务组，这依赖于sched_entity中的vip_my_q指针指向。

调度周期/调度时延

调度周期/调度时延(scheduling period/scheduling latency)是调度器重新进行一次调度(rescheduling)的最小时间间隔，也是调度器管理的所有任务至少都得到一次运行机会所用的真实物理时间。

内核对调度周期默认定义了一个值，我们可以cat /proc/sys/kernel/sched_latency_ns查看，数值单位为纳秒，这个值亦可在内核代码中的 sysctl_sched_latency全局变量设置。

若让一些同等优先级的任务运行，那每个任务将在一次调度周期内得到sysctl_sched_latency / 合理任务数的CPU时间。

但随着任务数量的增加，我们可能会将内核默认调度时延瓜分到很小，导致进程没执行多久就上下文切换到另外一个任务去了，频繁切换上下文的代价大到影响到公平性，显然我们不能任由这种情况发生。因此我们在内核中设置一个全局变量sysctl_sched_min_granularity用来描述每个进程每次执行的最短物理时间，一旦可运行的任务数量大于内核中设定的一个调度周期内最多可运行任务数sched_nr_latency，每个进程执行的时间不再是上述计算，而一个调度周期也不在是内核设定的默认值，而是nr_running * sysctl_sched_min_granularity，调度周期计算在__sched_period给出

其中某些值的修改都是通过访问文件系统的方式进行修改：

sysctl_sched_latency -- /proc/sys/kernel/sched_latency_ns

sysctl_sched_min_granularity -- /proc/sys/kernel/sched_min_granularity_ns

计算任务的虚拟时间

请我们带着这样的问题去思考：调度器对于就绪队列中任务是如何管理的？调度队列任务依据什么顺序排序？在每次选任务出来时又是选择哪一个？

由于现实我们无法达到可以并行任意多数量的任务的最高理想，且现实任务类型多种多样，主要解决既要高响应又要高效公平完成任务的目的，因此我们需要基于一定算法分配不同优先级任务不同的CPU时间，最终无限趋近于并行的“完全公平”。

如果我们基于任务权重分配时间给一个进程：

进程物理时间(real_time) = 调度周期 * 进程的权重/就绪队列所有进程权重之和

这在sched_slice中给出。

上文我们介绍了任务的优先级从0-179，内核提供了相关公式将一定范围的nice值转化为权重便于计算进程时间。

普通进程默认分配到nice值为0，每降低一个优先级，多10%的CPU时间，因此有weight = 1024/1.25nice (nice值越大，分得CPU时间越少)

但基于权重计算的CPU时间(real_time)使得每个进程分配得到时间又不一样了，不符合最初的"理想"。

引入虚拟时间 -- vruntime

为了满足VIP调度算法"理想"：每个任务使用CPU“时间”一样，分得一样的CPU算力，并且需要考虑不同进程的优先级重要性，引入计算虚拟时间片的概念，每个进程的虚拟时间 可以被看做是 在考虑过各种影响因素过加权过后的累计运行时间

现在我们希望不同的进程根据优先级分配的物理时间通过一个公式计算得到一个相同的值，我们称这个值为虚拟时间。我们记录每个进程运行的虚拟时间，当需要选择下一个运行进程的时候，找出虚拟时间最小的进程即可。

我们将计算的虚拟时间存储在 task->vip_se.vruntime 中，VIP调度器总是尝试运行具有最小 p->vip_se.vruntime 值的任务（即到目前为止执行最少的任务）

>> 计算虚拟时间

其中分数部分可能涉及到浮点数运算，为了避免浮点数运算，采用位运算等价计算：

这里的sched_vslice_vip调用calc_delta_vip计算本次调度时延中分给该进程加权后的虚拟"时间片"。(Weighted 1/N slice)

在将新建进程放入到调度队列时(if (initial && sched_feat(START_DEBIT)))，我们会调用一次sched_vslice_vip给出最初的vruntime分配本次调度分给该进程加权后的虚拟"时间片"，也是对新进程vruntime的初始化。

接下来的日子里，进程在得到运行后，一定时机会被调用update_curr_vip更新累加进程的虚拟时间。

这里的计算方式很简单，本次计算虚拟时间基于的物理时间不再是进程新建时的做法，而是delta_exec = now - curr->exec_start，delta_exec就是本次累加计算基于的实际物理运行时间。

例如将调度实体放入调度队列时：

初始新建和后续计算虚拟时间到的calc_delta_vip实现如下：

为了便于计算，我们再使用一个数组保存nice值从-20到19的对应inv_weight值

表示一个进程权重采用结构体load_weight表示：

我们对每个进程计算一个虚拟时间，VIP调度器按照虚拟时间(p->vip_se.vruntime**)的大小排序进入红黑树**，处于红黑树最左边的节点就是虚拟时间最小的调度实体，每次选任务pick_next_task都会选择到最左边的调度实体对应的任务。随着时间的推移与红黑树左边任务的运行，其虚拟时间逐渐增加，这些左边的任务渐渐右移至红黑树右侧，红黑树原来右侧的任务被运行的机会少虚拟时间相对较小渐渐左移到红黑树左侧，因此每个调度实体对应的任务都会得到运行的机会。

思考：值得注意的是，我们在task_fork_vip，先对新建任务的vruntime初始化成了父进程的vruntime，在place_vip_entity分配最初时间后，又减去队列的最小vruntime？为什么分配给任务的vruntime不是0呢？如果是0会产生什么样的后果？

VIP任务该如何被管理

到了真正该应用这些数据结构的时候了。

入队

上文我们提到了调度队列是依据调度实体的vruntime成员来排序构建红黑树的，这里的具体实现在enqueue_task_vip及enqueue_vip_entity

enqueue_task_vip中的for_each_sched_vip_entity宏旨在对添加的任务为某group se中的任务时，在group se自己的vip_rq入队后，再重新对该任务所在的group的调度实体se重新入队。倘若vip_se就在最顶层，或未配置组调度，则忽略该循环。

当一个进程入队时，它可能是来自fork、wake up、migrate，对于这些情况在enqueue_vip_entity为了进程间虚拟时间的公平性，我们可能会对他们的虚拟时间进行适当补偿队列记录的最小虚拟时间/虚拟"时间片"(place_vip_entity)，以满足进程间虚拟时间的公平性。这点我们在上文介绍虚拟时间时已给出介绍，下来在enqueue_vip_entity调用__enqueue_vip_entity进入到真正的插入新任务到红黑树调度队列中。在我们分析__enqueue_vip_entity之前，我们先来捋一捋之前引入的数据结构。

我们上述提到的task_struct、sched_entity、struct rb_node、struct rb_root_cached与struct vip_rq是怎么联系到一棵红黑树的呢？我们给出一张关系图：

对于节点在红黑树的insert与remove不熟悉的话，这里推荐阅读内核文档并观看动画演示：

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

https://www.kernel.org/doc/Documentation/rbtree.txt

有两个值得注意的C语言技巧：

我们通过rb_entry宏来访问树结点rb_node对应的整个sched_entity，这里的rb_entry实现为：#define rb_entry(ptr, type, member) container_of(ptr, type, member)，而container_of宏又是内核中很常见的宏，它可以根据传入结构体成员指针，结构体类型，结构体成员利用offset获取到结构体成员所在的结构体的起始地址，进而返回整个结构体实例的指针。
这里我们利用vip_entity_before对左右两个结点比大小，为了防止比较计算vruntime大于64位导致溢出，我们使用(a->vruntime - b->vruntime) < 0判别式来比较。首先我们得知道如何将一个整数取其相反数，即对其进行位运算：取反+1。

假设a->vruntime为2^64+1，b->vruntime位2^64-2，由于a溢出，则其二进制表示为000...001，b二进制表示为11..110，-b表示为00..010(在原有b上取反+1)，此时a->vruntime - b->vruntime = 000...001 + 00..010 = 00..011 > 0即不满足小于0，也就是说a->vruntime > b->vruntime，因此使用这样的计算方法即使有vruntime溢出也能避免计算出错。

出队

dequeue_task_vip``__dequeue_vip_entity实现与入队实现思想基本一致，我们这里不再过多赘述了。

在红黑树上执行入队出队(插入/删除)动作时，其时间复杂度为O(log N)，N是树上的节点数。其层级分明的结构、自平衡的性质、二叉搜索的特点和高效的插入删除动作都成为内核管理事件的不二之选。我们熟知的事件触发机制Epoll内部管理同样也采用的是这种高效的数据结构。