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;

...

}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/65ad8804c2523e6c26f4376cbb078907.html