Linux理论与编程:红黑树

2014-11-24 10:19:18 · 作者: · 浏览: 0

使用案例:


如 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;


...


}