【Linux 内核】CFS 调度器 ⑥ ( CFS 调度器就绪队列 cfs_rq | Linux 内核调度实体 sched_entity | “ 红黑树 “ 数据结构 rb_root_cached )

韩曙亮

发布于 2023-03-30 13:59:41

8280

发布于 2023-03-30 13:59:41

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、CFS 调度器就绪队列 cfs_rq

调度器的主要职责就是对 " 进程 " 进行 " 调度管理 " , 调度时进程是放在 " 调度队列 " 中的 ,

CFS 调度器的调度队列是 struct cfs_rq ;

通过该 " CFS 调度器就绪队列 " cfs_rq , 可以跟踪 " 就绪队列 " 信息 , 管理 " 就绪状态 " 调度实体 , 维护着一个按照虚拟时钟排序的 " 红黑树 " 数据结构 ;

该 struct cfs_rq 结构体在 Linux 内核源码的 linux-5.6.18\kernel\sched\sched.h 头文件中定义 ;

/* CFS-related fields in a runqueue */
struct cfs_rq {
	struct load_weight	load;
	unsigned long		runnable_weight;
	unsigned int		nr_running;
	unsigned int		h_nr_running;      /* SCHED_{NORMAL,BATCH,IDLE} */
	unsigned int		idle_h_nr_running; /* SCHED_IDLE */

	u64			exec_clock;
	u64			min_vruntime;

	struct rb_root_cached	tasks_timeline;

	/*
	 * 'curr' points to currently running entity on this cfs_rq.
	 * It is set to NULL otherwise (i.e when none are currently running).
	 */
	struct sched_entity	*curr;
	struct sched_entity	*next;
	struct sched_entity	*last;
	struct sched_entity	*skip;
}

二、Linux 内核调度实体 sched_entity

sched_entity 结构体就是可以被 Linux 内核调度的实体 ;

可以将该 " 调度实体 " 插入到红黑树 ( 执行队列 ) 节点中 ;

	struct sched_entity	*curr;
	struct sched_entity	*next;
	struct sched_entity	*last;
	struct sched_entity	*skip;

三、" 红黑树 " 数据结构 rb_root_cached

在 " CFS 调度器就绪队列 " cfs_rq中定义的

struct rb_root_cached	tasks_timeline;

字段 , 就是按照 " 虚拟时钟 " 排序的 " 红黑树 " 数据结构 ,

tasks_timeline 指针指向 rb_root_cached 类型的结构体 ,

rb_root 成员是这个 " 红黑树 " 数据结构的根节点 ;

rb_leftmost 成员指向这个 " 红黑树 " 数据结构的最左侧的 " 调度实体 " , 就是 " 虚拟时间 " 最小的调度实体 ;

该 " 红黑树 " 数据结构如下 : 在 Linux 内核源码 linux-5.6.18\include\linux\rbtree.h 路径对应的源码中定义 ;

/*
 * Leftmost-cached rbtrees.
 *
 * We do not cache the rightmost node based on footprint
 * size vs number of potential users that could benefit
 * from O(1) rb_last(). Just not worth it, users that want
 * this feature can always implement the logic explicitly.
 * Furthermore, users that want to cache both pointers may
 * find it a bit asymmetric, but that's ok.
 */
struct rb_root_cached {
	struct rb_root rb_root;
	struct rb_node *rb_leftmost;
};