Linux内核必懂知识—调度器和完全公平调度器CFS
调度器分析
调度器
-
内核中安排进程执行的模块,用以切换进程状态。
-
做两件事:选择某些就绪进程来执行;打断某些执行的进程让其变为就绪状态。
-
分配CPU时间的基本依据:进程优先级。 上下文切换(context switch):将进程在CPU中切换执行的过程,内核承担 此任务,负责重建和存储被切换掉之前的CPU状态。
调度类sched_class结构体与调度类
sched_class结构体表示调度类,定义在kernel/sched/sched.h。
-
成员解析 ecqueue_task:向就绪队列添加一个进程,某个任务进入可运行状态时,该函数将会被调用,它将调度实体放入到红黑树中。 dequeue_task:将一个进程从就绪队列中进行删除,当某个任务退出可运行状态时调用该函数,它将从红黑树中去掉对应调度实体。 yield_task:在进程想要资源放弃对处理器的控制权时,可食用在sched_yield系统调用,会调用内核API去处理操作。 check_preempt_curr:检查当前运行任务是否被抢占。 pick_next_task:选在接下来要运行的最合适的实体(进程)。 put_prev_task:用于另一个进程代替当前运行的进程。 set_curr_task:当任务修改它的调用类或修改它的任务组时,将调用这个函数。 task_tick:在每次激活周期调度器时,由周期性调度器调用。
-
源码注释
-
// 系统当中有多个调度类,按照调度优先级排成一个链表,下一个优先级调度类
-
const struct sched_class *next;
-
// 将进程加入到执行队列当中,即将调度实体(进程)存放到红黑树中,并对nr_running变量自动加1
-
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
-
// 从执行队列当中删除进程,并对nr_running变量自动减1
-
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
-
// 放弃CPU执行权,实际上该函数执行先出队后入队,在这种情况下,它直接将调度实体放在红黑树的最右端
-
void (*yield_task) (struct rq *rq);
-
bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
-
// 用于检查当前进程是否可以被新的进程抢占
-
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
-
-
/*
-
* It is the responsibility of the pick_next_task() method that will
-
* return the next task to call put_prev_task() on the @prev task or
-
* something equivalent.
-
*
-
* May return RETRY_TASK when it finds a higher prio class has runnable
-
* tasks.
-
*/
-
// 选择下一个应该要运行的进程
-
struct task_struct * (*pick_next_task) (struct rq *rq,
-
struct task_struct *prev);
-
// 将进程放回到运行队列当中
-
void (*put_prev_task) (struct rq *rq, struct task_struct *p);
-
-
#ifdef CONFIG_SMP
-
// 为进程选择一个合适的CPU
-
int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
-
// 迁移任务到另一个CPU
-
void (*migrate_task_rq)(struct task_struct *p);
-
// 专门用户唤醒进程
-
void (*task_waking) (struct task_struct *task);
-
void (*task_woken) (struct rq *this_rq, struct task_struct *task);
-
// 修改进程在CPU的亲和力
-
void (*set_cpus_allowed)(struct task_struct *p,
-
const struct cpumask *newmask);
-
// 启动运行队列
-
void (*rq_online)(struct rq *rq);
-
// 禁止运行队列
-
void (*rq_offline)(struct rq *rq);
-
#endif
-
// 当进程改变它的调度类或进程组时被调用
-
void (*set_curr_task) (struct rq *rq);
-
// 调用自己time_tick函数,可能引起进程切换,将驱动运行时抢占
-
void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
-
// 当进程创建时候调用,不同调度策略的进程初始化不一样
-
void (*task_fork) (struct task_struct *p);
-
// 进程退出时会使用
-
void (*task_dead) (struct task_struct *p);
-
-
/*
-
* The switched_from() call is allowed to drop rq->lock, therefore we
-
* cannot assume the switched_from/switched_to pair is serliazed by
-
* rq->lock. They are however serialized by p->pi_lock.
-
*/
-
// 专门用于进程切换操作
-
void (*switched_from) (struct rq *this_rq, struct task_struct *task);
-
void (*switched_to) (struct rq *this_rq, struct task_struct *task);
-
// 更改进程优先级
-
void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
-
int oldprio);
-
-
unsigned int (*get_rr_interval) (struct rq *rq,
-
struct task_struct *task);
-
-
void (*update_curr) (struct rq *rq);
-
-
#ifdef CONFIG_FAIR_GROUP_SCHED
-
void (*task_move_group) (struct task_struct *p);
-
#endif
-
};
-
```struct sched_class {
-
// 系统当中有多个调度类,按照调度优先级排成一个链表,下一个优先级调度类
-
const struct sched_class *next;
-
// 江金城加入到执行队列当中,即将调度实体(进程)存放到红黑树中,并对nr_running变量自动加1
-
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
-
// 从执行队列当中删除进程,并对nr_running变量自动减1
-
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
-
// 放弃CPU执行权,实际上该函数执行先出队后入队,在这种情况下,它直接将调度实体放在红黑树的最右端
-
void (*yield_task) (struct rq *rq);
-
bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
-
// 用于检查当前进程是否可以被新的进程抢占
-
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
-
-
/*
-
* It is the responsibility of the pick_next_task() method that will
-
* return the next task to call put_prev_task() on the @prev task or
-
* something equivalent.
-
*
-
* May return RETRY_TASK when it finds a higher prio class has runnable
-
* tasks.
-
*/
-
// 选择下一个应该要运行的进程
-
struct task_struct * (*pick_next_task) (struct rq *rq,
-
struct task_struct *prev);
-
// 将进程放回到运行队列当中
-
void (*put_prev_task) (struct rq *rq, struct task_struct *p);
-
-
#ifdef CONFIG_SMP
-
// 为进程选择一个合适的CPU
-
int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
-
// 迁移任务到另一个CPU
-
void (*migrate_task_rq)(struct task_struct *p);
-
// 专门用户唤醒进程
-
void (*task_waking) (struct task_struct *task);
-
void (*task_woken) (struct rq *this_rq, struct task_struct *task);
-
// 修改进程在CPU的亲和力
-
void (*set_cpus_allowed)(struct task_struct *p,
-
const struct cpumask *newmask);
-
// 启动运行队列
-
void (*rq_online)(struct rq *rq);
-
// 禁止运行队列
-
void (*rq_offline)(struct rq *rq);
-
#endif
-
// 当进程改变它的调度类或进程组时被调用
-
void (*set_curr_task) (struct rq *rq);
-
// 调用自己time_tick函数,可能引起进程切换,将驱动运行时抢占
-
void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
-
// 当进程创建时候调用,不同调度策略的进程初始化不一样
-
void (*task_fork) (struct task_struct *p);
-
// 进程退出时会使用
-
void (*task_dead) (struct task_struct *p);
-
-
/*
-
* The switched_from() call is allowed to drop rq->lock, therefore we
-
* cannot assume the switched_from/switched_to pair is serliazed by
-
* rq->lock. They are however serialized by p->pi_lock.
-
*/
-
// 专门用于进程切换操作
-
void (*switched_from) (struct rq *this_rq, struct task_struct *task);
-
void (*switched_to) (struct rq *this_rq, struct task_struct *task);
-
// 更改进程优先级
-
void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
-
int oldprio);
-
-
unsigned int (*get_rr_interval) (struct rq *rq,
-
struct task_struct *task);
-
-
void (*update_curr) (struct rq *rq);
-
-
#ifdef CONFIG_FAIR_GROUP_SCHED
-
void (*task_move_group) (struct task_struct *p);
-
#endif
-
};
Linux调度类
dl_sched_class、rt_sched_class、fair_sched_class及idle_sched_class等。每个进程都有对应一种调度策略,每一种调度策略又对应一种调度类(每一个调度类可以对应多种调度策略)。
-
extern const struct sched_class stop_sched_class;
-
extern const struct sched_class dl_sched_class;
-
extern const struct sched_class rt_sched_class;
-
extern const struct sched_class fair_sched_class;
-
extern const struct sched_class idle_sched_class;
rt_sched_class类 实时调度器(调度策略:SCHED_FIFO SCHED_RR)
fair_sched_class类 完全公平调度器(调度策略:SCHED_NORMAL、SCHED_BATCH)
SCHED_FIFO调度策略的实时进程永远比SCHED_NORMAL调度策略的普通进程优先运行。eg:pick_next_task函数。
调度类优先级顺序:stop_sched_class > dl_sched_class > rt_sched_class > fair_sched_class > idle_sched_class.
stop_sched_class:优先级最高的线程,会中断所有其他线程,并且不会被其他任务打断。
dl_sched_class
rt_sched_class:作用于实时线程。
fair_sched_class: 公平调度器CFS,作用: 一般常用线程。
idle_sched_class: 每个CPU的第一个PID=0线程,swapper,是一个静态线程。每个调度类属于
idle_sched_class。一般运行在开机过程和CPU异常时会做dump。 SCHED_NORMAL,SCHED_BATCH,SCHED_IDLE直接被映射到fair_sched_class;
SCHED_RR,SCHED_FIFO与rt_sched_class相关联。
-
* Simple, special scheduling class for the per-CPU stop tasks:
-
*/
-
const struct sched_class stop_sched_class = {
-
.next = &dl_sched_class,
-
-
.enqueue_task = enqueue_task_stop,
-
.dequeue_task = dequeue_task_stop,
-
.yield_task = yield_task_stop,
-
-
.check_preempt_curr = check_preempt_curr_stop,
-
-
.pick_next_task = pick_next_task_stop,
-
.put_prev_task = put_prev_task_stop,
-
-
#ifdef CONFIG_SMP
-
.select_task_rq = select_task_rq_stop,
-
.set_cpus_allowed = set_cpus_allowed_common,
-
#endif
-
-
.set_curr_task = set_curr_task_stop,
-
.task_tick = task_tick_stop,
-
-
.get_rr_interval = get_rr_interval_stop,
-
-
.prio_changed = prio_changed_stop,
-
.switched_to = switched_to_stop,
-
.update_curr = update_curr_stop,
-
};
Linux调度核心选择下一个合适的task运行时,会按照优先级顺序遍历调度类的pick_next_task函数。
学习思维导图以及Linux内核相关学习视频,清晰版导图可以点击:linux内核学习资料 获取
Linux内核开发系统学习视频链接:Linux内核源码/内存调优/文件系统/进程管理/设备驱动/网络协议栈学习视频
优先级
-
task_struct结构体中采用三个成员表示进程的优先级:prio和normal_prio表示动态优先级, static_prio表示进程的静态优先级。
-
内核将任务优先级划分,实时优先级范围是0到MAX_RT_PRIO-1(即99),而普通进 程的静态优先级范围是从MAX_RT_PRIO到MAX_PRIO-1(即100到139)。数字越小优先级越高。
-
/*
-
* Priority of a process goes from 0..MAX_PRIO-1, valid RT
-
* priority is 0..MAX_RT_PRIO-1, and SCHED_NORMAL/SCHED_BATCH
-
* tasks are in the range MAX_RT_PRIO..MAX_PRIO-1. Priority
-
* values are inverted: lower p->prio value means higher priority.
-
*
-
* The MAX_USER_RT_PRIO value allows the actual maximum
-
* RT priority to be separate from the value exported to
-
* user-space. This allows kernel threads to set their
-
* priority to a value higher than any user task. Note:
-
* MAX_RT_PRIO must not be smaller than MAX_USER_RT_PRIO.
-
*/
-
-
#define MAX_USER_RT_PRIO 100
-
#define MAX_RT_PRIO MAX_USER_RT_PRIO
-
-
#define MAX_PRIO (MAX_RT_PRIO NICE_WIDTH)
-
#define DEFAULT_PRIO (MAX_RT_PRIO NICE_WIDTH / 2)
-
进程分类
-
实时进程(Real-Time Process):优先级高、需要立即被执行的进程。
-
普通进程(Normal Process):优先级低、更长执行时间的进程。
调度策略
unsigned int policy:保存进程的调度策略(5种)
-
SCHED_NORMAL:用于普通进程,通过CFS调度器实现。
-
SCHED_BATCH: 相当于SCHED_NORMAL分化版本,采用分时策略,根据动态优先级,分配CPU运行需要资源。用于非交互处理器消耗型进程。
-
SCHED_IDLE:优先级最低,在系统空闲时才执行这类进程。系统负载很低时使用CFS。
-
SCHED_FIFO:先进先出调度算法(实时调度策略),相同优先级任务先到先服务,高优先级任务可以抢占低优先级任务。
-
SCHED_RR:轮流调度算法(实时调度策略)。
-
SCHED_DEADLINE:新支持实时进程调度策略,针对突发性计算。
-
/*
-
* Scheduling policies
-
*/
-
-
-
-
-
/* SCHED_ISO: reserved but not implemented yet */
-
-
完全公平调度算法(时间片轮询调度算法)
实现完全公平调度算法,要为进程定义两个时间:
-
实际运行时间 实际运行时间=调度周期进程权重/所有进程权重之和。 调度周期:指所有进程运行一遍所需要的时间。 进程权重:根据进程的重要性,分配给每个进程不同的权重。
-
2.虚拟运行时间 虚拟运行时间=实际运行时间1024/进程权重=(调度周期进程权重/所有进程权重之和) 1024/进程权重=调度周期*1024/所有进程总权重。 一个调度周期里,所有进程的虚拟运行时间相同。
-
基本原理 CFS定义一种新调度模型,它给cfs_rq(cfs的run queue)中的每一个进程都设置一个虚 拟时钟-virtual runtime(vruntime)。如果一个进程得以执行,随着执行时间的不断增长,其 vruntime也将不断增大,没有得到执行的进程vruntime将保持不变。
调度器结构分析
任务:合理分配CPU时间给运行进程。
目标:有效分配CPU是时间片。
主调度器:通过schedule()函数来完成进程的选择和切换。 周期调度器:根据频率自动调用scheduler_tick函数,作用:根据进程运行时间触发调度。 上下文切换:主要做两件事:切换地址空间;切换寄存器和栈空间。
CFS就绪队列
调度管理是各个调度器的职责。CFS的顶级调度就队列struct cfs_rq。
-
/* CFS-related fields in a runqueue */
-
// CFS调度运行队列,每个CPU的rq都会包含一个cfs_rq,每个组调度的sched_entity也会有一个cfs_rq队列
-
struct cfs_rq {
-
// CFS运行队列中所有进程总负载
-
struct load_weight load;
-
// nr_running::cfs_rq中调度实体数量
-
// h_nr_running 只对进程有效
-
unsigned int nr_running, h_nr_running;
-
-
u64 exec_clock;
-
//跟踪记录队列所有进程最小虚拟运行时间
-
u64 min_vruntime;
-
#ifndef CONFIG_64BIT
-
u64 min_vruntime_copy;
-
#endif
-
// 红黑树的root 用于在按时间排序的红黑树中管理所有进程
-
struct rb_root tasks_timeline;
-
// 下一个调度结点(红黑树最左边结点就是下个调度实体)
-
struct rb_node *rb_leftmost;
-
-
/*
-
* '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, *next, *last, *skip;
-
-
#ifdef CONFIG_SCHED_DEBUG
-
unsigned int nr_spread_over;
-
#endif
-
-
#ifdef CONFIG_SMP
-
/*
-
* CFS load tracking
-
*/
-
struct sched_avg avg;
-
u64 runnable_load_sum;
-
unsigned long runnable_load_avg;
-
#ifdef CONFIG_FAIR_GROUP_SCHED
-
unsigned long tg_load_avg_contrib;
-
#endif
-
atomic_long_t removed_load_avg, removed_util_avg;
-
#ifndef CONFIG_64BIT
-
u64 load_last_update_time_copy;
-
#endif
-
-
#ifdef CONFIG_FAIR_GROUP_SCHED
-
/*
-
* h_load = weight * f(tg)
-
*
-
* Where f(tg) is the recursive weight fraction assigned to
-
* this group.
-
*/
-
unsigned long h_load;
-
u64 last_h_load_update;
-
struct sched_entity *h_load_next;
-
#endif /* CONFIG_FAIR_GROUP_SCHED */
-
#endif /* CONFIG_SMP */
-
-
#ifdef CONFIG_FAIR_GROUP_SCHED
-
struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */
-
-
/*
-
* leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
-
* a hierarchy). Non-leaf lrqs hold other higher schedulable entities
-
* (like users, containers etc.)
-
*
-
* leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
-
* list is used during load balance.
-
*/
-
int on_list;
-
struct list_head leaf_cfs_rq_list;
-
struct task_group *tg; /* group that "owns" this runqueue */
-
-
#ifdef CONFIG_CFS_BANDWIDTH
-
int runtime_enabled;
-
u64 runtime_expires;
-
s64 runtime_remaining;
-
-
u64 throttled_clock, throttled_clock_task;
-
u64 throttled_clock_task_time;
-
int throttled, throttle_count;
-
struct list_head throttled_list;
-
#endif /* CONFIG_CFS_BANDWIDTH */
-
#endif /* CONFIG_FAIR_GROUP_SCHED */
-
};
总结
本文主要介绍了调度器分析:功能,调度类sched_class结构体与调度类;Linux调度类(5种)及其优先级,调度策略(5种);完全公平调度算法,包括实际运行时间、虚拟运行时间,调度器结构分析,CFS就绪队列等内容。
Linux内核学习大纲:Linux内核学习思维导图
视频学习链接:Linux内核源码/内存调优/文件系统/进程管理/设备驱动/网络协议栈
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfhbjgi
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24