在linux *** 作系统内核实现里经常使用的红黑树

在linux *** 作系统内核实现里经常使用的红黑树如下：

二叉树，按中序遍历后为一递增数组，自平衡意味着树的高度有一个上限，对于红黑树，其为2log(n+1)，所以时间复杂度为最差为Olog(n)。

赋予二叉搜索树自平衡特性的方法有多种，红黑树通过一下4条约束实现自平衡:

Every node is either red or black.

All NIL nodes (figure 1) are considered black.

A red node does not have a red child.

Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.

其中根节点为黑色。

红黑树的搜索与二叉搜索树无异，但是插入和删除可能会违背上述四条原则。需要用到左旋右旋 *** 作。左旋右旋上图，可以看到左旋右旋本身不改变二叉搜索树的特性，旋转后必要时改变节点的颜色可消除插入或者删除带来的红冲突和黑冲突，有时红黑树的重新平衡需要迭代进行。

红黑树比较适合的应用场景:

需要动态插入、删除、查找的场景，包括但不限于：

某些数据库的增删改查，比如select * from xxx where 这类条件检索。

linux内核中进程通过红黑树组织管理，便于快速插入、删除、查找进程的task_struct。

linux内存中内存的管理：分配和回收。用红黑树组织已经分配的内存块，当应用程序调用free释放内存的时候，可以根据内存地址在红黑树中快速找到目标内存块。

hashmap中(key,value)增、删、改查的实现；java 8就采用了RBTree替代链表。

Ext3文件系统，通过红黑树组织目录项。

上回书说到 Linux进程的由来 和 Linux进程的创建 ，其实在同一时刻只能支持有限个进程或线程同时运行(这取决于CPU核数量，基本上一个进程对应一个CPU)，在一个运行的 *** 作系统上可能运行着很多进程，如果运行的进程占据CPU的时间很长，就有可能导致其他进程饿死。为了解决这种问题， *** 作系统引入了 进程调度器 来进行进程的切换，轮流让各个进程使用CPU资源。

1）rq： 进程的运行队列( runqueue)， 每个CPU对应一个 ，包含自旋锁(spinlock)、进程数量、用于公平调度的CFS信息结构、当前运行的进程描述符等。实际的进程队列用红黑树来维护(通过CFS信息结构来访问)。

2）cfs_rq： cfs调度的进程运行队列信息 ，包含红黑树的根结点、正在运行的进程指针、用于负载均衡的叶子队列等。

3）sched_entity： 把需要调度的东西抽象成调度实体 ，调度实体可以是进程、进程组、用户等。这里包含负载权重值、对应红黑树结点、 虚拟运行时vruntime 等。

4）sched_class：把 调度策略(算法)抽象成调度类 ，包含一组通用的调度 *** 作接口。接口和实现是分离，可以根据调度接口去实现不同的调度算法，使一个Linux调度程序可以有多个不同的调度策略。

1） 关闭内核抢占 ，初始化部分变量。获取当前CPU的ID号，并赋值给局部变量CPU， 使rq指向CPU对应的运行队列 。 标识当前CPU发生任务切换 ，通知RCU更新状态，如果当前CPU处于rcu_read_lock状态，当前进程将会放入rnp->blkd_tasks阻塞队列，并呈现在rnp->gp_tasks链表中。 关闭本地中断 ，获取所要保护的运行队列的自旋锁， 为查找可运行进程做准备 。

2） 检查prev的状态，更新运行队列 。如果不是可运行状态，而且在内核态没被抢占，应该从运行队列中 删除prev进程 。如果是非阻塞挂起信号，而且状态为TASK_INTER-RUPTIBLE，就把该进程的状态设置为TASK_RUNNING，并将它 插入到运行队列 。

3）task_on_rq_queued(prev) 将pre进程插入到运行队列的队尾。

4）pick_next_task 选取将要执行的next进程。

5）context_switch(rq, prev, next)进行 进程上下文切换 。

1) 该进程分配的CPU时间片用完。

2) 该进程主动放弃CPU(例如IO *** 作)。

3) 某一进程抢占CPU获得执行机会。

Linux并没有使用x86 CPU自带的任务切换机制，需要通过手工的方式实现了切换。

进程创建后在内核的数据结构为task_struct ， 该结构中有掩码属性cpus_allowed，4个核的CPU可以有4位掩码，如果CPU开启超线程，有一个8位掩码，进程可以运行在掩码位设置为1的CPU上。

Linux内核API提供了两个系统调用 ，让用户可以修改和查看当前的掩码：

1) sched_setaffinity()：用来修改位掩码。

2) sched_getaffinity()：用来查看当前的位掩码。

在下次task被唤醒时，select_task_rq_fair根据cpu_allowed里的掩码来确定将其置于哪个CPU的运行队列，一个进程在某一时刻只能存在于一个CPU的运行队列里。

在Nginx中，使用了CPU亲和度来完成某些场景的工作：

worker_processes      4

worker_cpu_affinity 0001001001001000

上面这个配置说明了4个工作进程中的每一个和一个CPU核挂钩。如果这个内容写入Nginx的配置文件中，然后Nginx启动或者重新加载配置的时候，若worker_process是4，就会启用4个worker，然后把worker_cpu_affinity后面的4个值当作4个cpu affinity mask，分别调用ngx_setaffinity，然后就把4个worker进程分别绑定到CPU0～3上。

worker_processes      2

worker_cpu_affinity 01011010

上面这个配置则说明了两个工作进程中的每一个和2个核挂钩。

在前文中，我们分析了内核中进程和线程的统一结构体task_struct，并分析进程、线程的创建和派生的过程。在本文中，我们会对任务间调度进行详细剖析，了解其原理和整个执行过程。由此，进程、线程部分的大体框架就算是介绍完了。本节主要分为三个部分：Linux内核中常见的调度策略，调度的基本结构体以及调度发生的整个流程。下面将详细展开说明。

Linux 作为一个多任务 *** 作系统，将每个 CPU 的时间划分为很短的时间片，再通过调度器轮流分配给各个任务使用，因此造成多任务同时运行的错觉。为了维护 CPU 时间，Linux 通过事先定义的节拍率（内核中表示为 HZ），触发时间中断，并使用全局变量 Jiffies 记录了开机以来的节拍数。每发生一次时间中断，Jiffies 的值就加 1。节拍率 HZ 是内核的可配选项，可以设置为 100、250、1000 等。不同的系统可能设置不同的数值，可以通过查询 /boot/config 内核选项来查看它的配置值。

Linux的调度策略主要分为实时任务和普通任务。实时任务需求尽快返回结果，而普通任务则没有较高的要求。在前文中我们提到了task_struct中调度策略相应的变量为policy，调度优先级有prio, static_prio, normal_prio, rt_priority几个。优先级其实就是一个数值，对于实时进程来说，优先级的范围是 0 99；对于普通进程，优先级的范围是 100 139。数值越小，优先级越高。

实时调度策略主要包括以下几种

普通调度策略主要包括以下几种：

首先，我们需要一个结构体去执行调度策略，即sched_class。该类有几种实现方式

普通任务调度实体源码如下，这里面包含了 vruntime 和权重 load_weight，以及对于运行时间的统计。

在调度时，多个任务调度实体会首先区分是实时任务还是普通任务，然后通过以时间为顺序的红黑树结构组合起来，vruntime 最小的在树的左侧，vruntime最多的在树的右侧。以CFS策略为例，则会选择红黑树最左边的叶子节点作为下一个将获得 CPU 的任务。而这颗红黑树，我们称之为运行时队列（run queue），即struct rq。

其中包含结构体cfs_rq，其定义如下，主要是CFS调度相关的结构体，主要有权值相关变量、vruntime相关变量以及红黑树指针，其中结构体rb_root_cached即为红黑树的节点

对结构体dl_rq有类似的定义，运行队列由红黑树结构体构成，并按照deadline策略进行管理

对于实施队列相应的rt_rq则有所不同，并没有用红黑树实现。

下面再看看调度类sched_class，该类以函数指针的形式定义了诸多队列 *** 作，如

调度类分为下面几种：

队列 *** 作中函数指针指向不同策略队列的实际执行函数函数，在linux/kernel/sched/目录下，fair.c、idle.c、rt.c等文件对不同类型的策略实现了不同的函数，如fair.c中定义了

以选择下一个任务为例，CFS对应的是pick_next_task_fair，而rt_rq对应的则是pick_next_task_rt，等等。

由此，我们来总结一下：

有了上述的基本策略和基本调度结构体，我们可以形成大致的骨架，下面就是需要核心的调度流程将其拼凑成一个整体，实现调度系统。调度分为两种，主动调度和抢占式调度。

说到调用，逃不过核心函数schedule()。其中sched_submit_work()函数完成当前任务的收尾工作，以避免出现如死锁或者IO中断等情况。之后首先禁止抢占式调度的发生，然后调用__schedule()函数完成调度，之后重新打开抢占式调度，如果需要重新调度则会一直重复该过程，否则结束函数。

而__schedule()函数则是实际的核心调度函数，该函数主要 *** 作包括选取下一进程和进行上下文切换，而上下文切换又包括用户态空间切换和内核态的切换。具体的解释可以参照英文源码注释以及中文对各个步骤的注释。

其中核心函数是获取下一个任务的pick_next_task()以及上下文切换的context_switch()，下面详细展开剖析。首先看看pick_next_task()，该函数会根据调度策略分类，调用该类对应的调度函数选择下一个任务实体。根据前文分析我们知道，最终是在不同的红黑树上选择最左节点作为下一个任务实体并返回。

下面来看看上下文切换。上下文切换主要干两件事情，一是切换任务空间，也即虚拟内存；二是切换寄存器和 CPU 上下文。关于任务空间的切换放在内存部分的文章中详细介绍，这里先按下不表，通过任务空间切换实际完成了用户态的上下文切换工作。下面我们重点看一下内核态切换，即寄存器和CPU上下文的切换。

switch_to()就是寄存器和栈的切换，它调用到了 __switch_to_asm。这是一段汇编代码，主要用于栈的切换， 其中32位使用esp作为栈顶指针，64位使用rsp，其他部分代码一致。通过该段汇编代码我们完成了栈顶指针的切换，并调用__switch_to完成最终TSS的切换。注意switch_to中其实是有三个变量，分别是prev, next, last，而实际在使用时，我们会对last也赋值为prev。这里的设计意图需要结合一个例子来说明。假设有ABC三个任务，从A调度到B，B到C，最后C回到A，我们假设仅保存prev和next，则流程如下

最终调用__switch_to()函数。该函数中涉及到一个结构体TSS(Task State Segment)，该结构体存放了所有的寄存器。另外还有一个特殊的寄存器TR（Task Register）会指向TSS，我们通过更改TR的值，会触发硬件保存CPU所有寄存器在当前TSS，并从新的TSS读取寄存器的值加载入CPU，从而完成一次硬中断带来的上下文切换工作。系统初始化的时候，会调用 cpu_init()给每一个 CPU 关联一个 TSS，然后将 TR 指向这个 TSS，然后在 *** 作系统的运行过程中，TR 就不切换了，永远指向这个 TSS。当修改TR的值得时候，则为任务调度。

更多Linux内核视频教程文本资料免费领取后台私信【 内核大礼包 】自行获取。

在完成了switch_to()的内核态切换后，还有一个重要的函数finish_task_switch()负责善后清理工作。在前面介绍switch_to三个参数的时候我们已经说明了使用last的重要性。而这里为何让prev和last均赋值为prev，是因为prev在后面没有需要用到，所以节省了一个指针空间来存储last。

至此，我们完成了内核态的切换工作，也完成了整个主动调度的过程。

抢占式调度通常发生在两种情况下。一种是某任务执行时间过长，另一种是当某任务被唤醒的时候。首先看看任务执行时间过长的情况。

该情况需要衡量一个任务的执行时间长短，执行时间过长则发起抢占。在计算机里面有一个时钟，会过一段时间触发一次时钟中断，通知 *** 作系统时间又过去一个时钟周期，通过这种方式可以查看是否是需要抢占的时间点。

时钟中断处理函数会调用scheduler_tick()。该函数首先取出当前CPU，并由此获取对应的运行队列rq和当前任务curr。接着调用该任务的调度类sched_class对应的task_tick()函数进行时间事件处理。

以普通任务队列为例，对应的调度类为fair_sched_class，对应的时钟处理函数为task_tick_fair()，该函数会获取当前的调度实体和运行队列，并调用entity_tick()函数更新时间。

在entity_tick()中，首先会调用update_curr()更新当前任务的vruntime，然后调用check_preempt_tick()检测现在是否可以发起抢占。

check_preempt_tick() 先是调用 sched_slice() 函数计算出一个调度周期中该任务运行的实际时间 ideal_runtime。sum_exec_runtime 指任务总共执行的实际时间，prev_sum_exec_runtime 指上次该进程被调度时已经占用的实际时间，所以 sum_exec_runtime - prev_sum_exec_runtime 就是这次调度占用实际时间。如果这个时间大于 ideal_runtime，则应该被抢占了。除了这个条件之外，还会通过 __pick_first_entity 取出红黑树中最小的进程。如果当前进程的 vruntime 大于红黑树中最小的进程的 vruntime，且差值大于 ideal_runtime，也应该被抢占了。

如果确认需要被抢占，则会调用resched_curr()函数，该函数会调用set_tsk_need_resched()标记该任务为_TIF_NEED_RESCHED，即该任务应该被抢占。

某些任务会因为中断而唤醒，如当 I/O 到来的时候，I/O进程往往会被唤醒。在这种时候，如果被唤醒的任务优先级高于 CPU 上的当前任务，就会触发抢占。try_to_wake_up() 调用 ttwu_queue() 将这个唤醒的任务添加到队列当中。ttwu_queue() 再调用 ttwu_do_activate() 激活这个任务。ttwu_do_activate() 调用 ttwu_do_wakeup()。这里面调用了 check_preempt_curr() 检查是否应该发生抢占。如果应该发生抢占，也不是直接踢走当前进程，而是将当前进程标记为应该被抢占。

由前面的分析，我们知道了不论是是当前任务执行时间过长还是新任务唤醒，我们均会对现在的任务标记位_TIF_NEED_RESCUED，下面分析实际抢占的发生。真正的抢占还需要一个特定的时机让正在运行中的进程有机会调用一下 __schedule()函数，发起真正的调度。

实际上会调用__schedule()函数共有以下几个时机

从系统调用返回用户态：以64位为例，系统调用的链路为do_syscall_64->syscall_return_slowpath->prepare_exit_to_usermode->exit_to_usermode_loop。在exit_to_usermode_loop中，会检测是否为_TIF_NEED_RESCHED，如果是则调用__schedule()

内核态启动：内核态的执行中，被抢占的时机一般发生在 preempt_enable() 中。在内核态的执行中，有的 *** 作是不能被中断的，所以在进行这些 *** 作之前，总是先调用 preempt_disable() 关闭抢占，当再次打开的时候，就是一次内核态代码被抢占的机会。preempt_enable() 会调用 preempt_count_dec_and_test()，判断 preempt_count 和 TIF_NEED_RESCHED 是否可以被抢占。如果可以，就调用 preempt_schedule->preempt_schedule_common->__schedule 进行调度。

   本文分析了任务调度的策略、结构体以及整个调度流程，其中关于内存上下文切换的部分尚未详细叙述，留待内存部分展开剖析。

1、调度相关结构体及函数实现

2、schedule核心函数

---