歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> 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;

    ...

}

Copyright © Linux教程網 All Rights Reserved