使用案例:
如 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;
...
}