目录
上文聊到了CFS的一个特性，调度周期，本文梳理一下cfs调度器的基本数据结构
task_struct
在linux系统中，所有的任务都是一个task_struct，所以我们从这里作为起点
struct task_struct { volatile long state; # 状态 int on_cpu; # 是否当前CPU unsigned int cpu; # CPU ID int on_rq; # 是否在rq int prio; # 优先级 int static_prio; # nice 优先级 int normal_prio; # 正常优先级 unsigned int rt_priority; # 实时优先级 const struct sched_class *sched_class; # 调度类 struct sched_entity se; # 调度实体 struct sched_rt_entity rt; # rt的调度实体 struct task_group *sched_task_group; # cgroup任务组 struct sched_dl_entity dl; # dl的调度实体 unsigned int policy; # 策略 int nr_cpus_allowed; # 最大cpu值 const cpumask_t *cpus_ptr; # cpu_mask结构体 cpumask_t cpus_mask; # mask掩码 ...... }
任务结构体管理调度实体，所以我们查看调度实体se
sched_entity
struct sched_entity { /* For load-balancing: */ struct load_weight load; # 权重 struct rb_node run_node; # rb-tree struct list_head group_node; # cgroup任务组 unsigned int on_rq; # 是否在rq u64 exec_start; # 执行时间 u64 sum_exec_runtime; # 累计时间 u64 vruntime; # 运行时间 u64 prev_sum_exec_runtime; # 上次累计时间 u64 nr_migrations; # 迁移次数 struct sched_statistics statistics; # 统计信息 int depth; # 深度，cgroup使用 struct sched_entity *parent; # 父节点，cgroup使用 /* rq on which this entity is (to be) queued: */ struct cfs_rq *cfs_rq; # cfs rq /* rq "owned" by this entity/group: */ struct cfs_rq *my_q; # cgroup下的cfs rq /* cached value of my_q->h_nr_running */ unsigned long runnable_weight; # h_nr_running struct sched_avg avg; # 负载均衡 };
调度实体管理运行队列，所以接下来看cfs_rq
cfs rq
struct cfs_rq { struct load_weight load; # 权重 unsigned int nr_running; # 调度实体数量 u64 exec_clock; # 累计时钟 u64 min_vruntime; # 最小运行时间 struct rb_root_cached tasks_timeline; # rb-tree 根 /* * '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; # 当前se指针 struct sched_entity *next; # 下个se指针 struct sched_entity *last; # 上个se指针 struct sched_entity *skip; # 需要跳过的se指针 ...... }
runqueue管理的是rb-tree，所以接下来看rb-tree结构 tasks_timeline
tasks_timeline
struct rb_root_cached { struct rb_root rb_root; # rb-tree 根 struct rb_node *rb_leftmost; # rb-tree 最左节点 };
到这里，cfs的基本结构大致为task_struct->sched_entity->runqueue->rb-tree
但是还有一个不应该忽视的，就是cgroup下的组调度
task_group
struct task_group { struct cgroup_subsys_state css; # cgourp状态 #ifdef CONFIG_FAIR_GROUP_SCHED /* schedulable entities of this group on each CPU */ struct sched_entity **se; # 调度实体 /* runqueue "owned" by this group on each CPU */ struct cfs_rq **cfs_rq; # runqueue unsigned long shares; # cgoup 份额 #ifdef CONFIG_RT_GROUP_SCHED struct sched_rt_entity **rt_se; # rt的调度实体 struct rt_rq **rt_rq; # rt的runqueue struct rt_bandwidth rt_bandwidth; # rt带宽控制 struct cfs_bandwidth cfs_bandwidth; # cfs带宽控制 #endif ...... }
task_group 中有两个重要的成员：其一是sched_entity 指针的数组，将其插入到其父 cfs_rq 的红黑树中，实现组级公平竞争，另一个则是 cfs_rq，用于管理该组内任务的调度队列。我们可以看到重点在task_group的分组行为。
默认情况下，可以按照上面描述的流程管理task_struct->sched_entity->runqueue->rb-tree，但实际上，可以通过cgroup分组，那么其流程管理为task_struct->task_group->sched_entity->runqueue->rb-tree
通过添加这么一个组的概念，借助my_q就可以使得cpu上的任务可以按组来管理了。
总结
本文将调度大的框架上的基本数据结构的交互进行了一个说明，可能很轻松的了解到调度在数据结构上是如何实现or流转的，同样的，我也整理了图示，如下
可以看到，所谓调度，就是从task_struct中，找到group/task内的se，通过se下的runqueue找到rb-tree，然后通过rb-tree进行任务管理，简单明了。
更详细一点的图片如下，摘自网络，意思一致
