2
极简cfs公平调度算法 - organic
source link: https://www.cnblogs.com/organic/p/17320040.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
1. 说明
1> linux内核关于task调度这块是比较复杂的，流程也比较长，要从源码一一讲清楚很容易看晕
2> 本篇文章主要是讲清楚cfs公平调度算法如何将task在时钟中断驱动下切换调度，所以与此无关的代码一律略过
3> 本篇只讲最简单的task调度，略过组调度，组调度在下一篇《极简组调度-CGroup如何限制cpu》中讲解
4> 本篇源码来自CentOS7.6的3.10.0-957.el7内核
2. 极简task调度核心思想
1> linux采用cfs公平调度算法，其用vruntime记录task运行的cpu时长，每次用重新调度时，总是选择vruntime最小的task进行调度
2> 所有Ready状态的task会分配到不同cpu的rq队列上，等待调度运行
3> 时钟中断中，++当前task运行时间vruntime，并检测当前task运行时间是否超过一个时间片，或者其vruntime比当前cpu rq队列中最小的vruntime task大一个时间片，则设置resched标记(但并不立马进行task切换，因为此时仍在中断上下文中)
4> 所有中断返回后（当然也包括时钟中断），都会jump到ret_from_intr，这里会检查resched标记，如果置位，则调用schedule()选择vruntime最小的task进行调度
3. 极简task调度相关数据结构
3.1 名词解释
|
全称
|
说明
|
|
| se | schedule entity | 调度实例，可以是一个task，也可以是一个group（当使用组调度时），linux支持组调度后，将调度实例从原来的task，抽象为se |
| rq | run queue | cpu的运行队列，每个cpu一个，处于Ready状态的se挂在对应的cpu运行队列上后，才会被选择投入运行 |
| cfs_rq | cfs rq | 公平调度运行队列，因为一般进程都是用cfs调度算法，一般进程的se都是挂在rq.cfs_rq上的 |
| vruntime | virtual runtime | se的一个重要成员，记录调度实例的cpu运行时长，schedule时，cfs调度每次都选取vruntime最小的se投入运行，这就是cfs调度算法的核心原理 |
3.2 数据结构
struct sched_entity
{
unsigned int on_rq; // se是否在rq上，不在的话即使task是Ready状态也不会投入运行的
u64 vruntime; // cpu运行时长，cfs调度算法总是选择该值最小的se投入运行
};
struct task
{
struct sched_entity se; // 调度实例
};
struct rq
{
struct cfs_rq cfs; // 所有要调度的se都挂在cfs rq中
struct task_struct* curr; // 当前cpu上运行的task
};
struct cfs_rq
{
struct rb_root tasks_timeline; // 以vruntime为key，se为value的红黑树根节点，schedule时，cfs调度算法每次从这里挑选vruntime最小的se投入运行
struct rb_node* rb_leftmost; // tasks_timeline红黑树最左的叶子节点，即vruntime最小的se，直接取这个节点以加快速度
sched_entity* curr; // cfs_rq中当前正在运行的se
struct rq* rq; /* cpu runqueue to which this cfs_rq is attached */
unsigned int nr_running; // cfs_rq队列上有多少个se
};
3.3 数据结构关系
2.3 极简task调度code
2.3.1 时钟中断
1> task调度的发动机时钟中断触发后，会在smp_apic_timer_interrupt()中处理，经过层层调用，最终会到entity_tick()
entity_tick()
{
update_curr();
// 如果当前cfs_rq上的se大于1，则检查是否要重新调度
if (cfs_rq->nr_running > 1)
check_preempt_tick(cfs_rq, curr);
}
2> update_curr()主要是++当前task se的vruntime（当然这里还对组调度进行了处理，这里不讲组调度，先略过）
void update_curr(struct cfs_rq* cfs_rq)
{
struct sched_entity* curr = cfs_rq->curr;
curr->vruntime += delta_exec; // 增加se的运行时间
}
3> check_preempt_tick()判定当前运行的时间大于sched_slice时，即超过了时间片，或者其vruntime比当前cpu rq队列中最小的vruntime task大一个时间片，就会标记resched，然后等中断返回后会调用schedule()进行task切换
void check_preempt_tick()
{
// 如果运行时间大于sched_slice，则resched
if (delta_exec > ideal_runtime)
resched_task(rq_of(cfs_rq)->curr);
// 如果比最小vruntime大一个sched_slice，则resched
se = __pick_first_entity(cfs_rq); // 选择cfs.rb_leftmost的se，即vruntime最小的se
delta = curr->vruntime - se->vruntime;
if (delta > ideal_runtime)
resched_task(rq_of(cfs_rq)->curr);
}
4> resched_curr()非常简单，就是设置一个resched标记位TIF_NEED_RESCHED
void resched_curr(struct rq* rq)
{
struct task_struct* curr = rq->curr;
set_tsk_thread_flag(curr, TIF_NEED_RESCHED);
}
2.3.2 schedule
1> 时钟中断返回后，会jump到ret_from_intr(有兴趣可以去分析这段汇编)，如果resched标记被置位，就会调用schedule()进行调度
void schedule()
{
prev = rq->curr;
put_prev_task_fair(rq, prev); // 对当前task进行处理，如果该task属于一个group，还要对组调度进行处理，这里不展开
// 选择下一个task并切换运行
next = pick_next_task(rq); // 选择一个vruntime最小的task进行调度
context_switch(rq, prev, next);
}
2> pick_next_task() → pick_next_task_fair() → pick_next_entity() → __pick_first_entity()，__pick_first_entity()选择vruntime最小的cfs_rq->rb_leftmost节点se进行调度
struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
struct rb_node *left = cfs_rq->rb_leftmost;
return rb_entry(left, struct sched_entity, run_node);
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK