Linux理论与编程：红黑树

Linux理论与编程：红黑树

使用案例：

如 linux内核中，完全公平调度策略CFS的运行队列 使用"红黑树"方法管理属于其的进程。

红黑树是“半平衡二叉树”！效率好！！！

使用rb_entry、rb_insert_color、rb_erase等。

Linux代码关键结构体如下：

struct rq { ------------ 每个CPU都有一个。
    struct cfs_rq cfs;
    struct rt_rq rt;

    ...

}

/* CFS-related fields in a runqueue */
struct cfs_rq {
    struct rb_root tasks_timeline;    ------  红黑树的根，完全公平调度策略使用红黑树存储所有相关进程。
    struct rb_node *rb_leftmost;      ------- 查找下一个待执行进程的快捷方式。

struct rt_rq {
    struct rt_prio_array active;   ---- 双向指针的数组，用来分别链接不同优先级的进程链表。

    ...

}

每个进程都对应为一个红黑树节点。

struct sched_entity {
    struct rb_node        run_node;

    ...
}

struct sched_rt_entity {
    struct list_head run_list;

    ...
}

struct task_struct {;
    struct sched_entity se;
    struct sched_rt_entity rt;

    ...

}