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调度算法的核心原理 |
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 };
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); }
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进行调度文章来源:https://www.toymoban.com/news/detail-413453.html
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); }
文章来源地址https://www.toymoban.com/news/detail-413453.html
到了这里,关于极简cfs公平调度算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!