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