K

KyrieGuo

V1

2022/05/31阅读:24主题:橙心

调度器源码分析

1、调度器及其功能

  • 内核中用来安排进程执行的模块称为调度器(scheduler),它可以切换进程状态(process state)。例如执行、可中断睡眠、不可中断睡眠、退出、暂停等。

  • 调度器是cpu中央处理器的管理员,主要负责完成两件事:一、选择某些就绪进程来执行,二是打断某些执行的进程让它们变为就绪态。调度器分配cpu时间的基本依据就是进程的优先级。上下文切换(contex switch):将进程在cpu中切换执行的过程,内核承担此任务,负责重建和存储被切换掉之前的cpu状态。

2、调度类sched_class结构体与调度类

sched_class结构体表示调度类,定义在kernel/sched/sched.h
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
};

成员

  • enqueue_task:向就绪队列添加一个进程,某个任务进入可运行状态时,该函数将会调用。

  • dequeue_task:将一个进程从就绪队列中进行删除,当某个任务退出可运行状态时调用该函数,它将从红黑树中去掉对应调度实体。

  • yield_task:在进程想要资源放弃对处理器的控制权时,可使用在sched_yield系统调用,会调用内核API去处理操作。

  • check_preempt_curr:检查当前运行的任务是否被抢占。

  • pick_next_task:选择下来要运行的最合适的实体。

  • put_prev_task:用于另一个进程代替当前运行的进程。

  • set_curr_task:当任务修改它的调用类或修改它的任务组时,将调用这个函数

  • task_tick:在每次激活周期调度器时,由周期性调度器调用

Linux调度类

调度类:dl_sched_class、rt_sched_class、fair_sched_classidle_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调度策略的普通进程优先运行。代码可以到有一个函数pick_next_task函数即可。

  • 调度类的优先级顺序:stop_sched_class > dl_sched_class > rt_sched_class > fair_sched_class > idle_sched_class
//优先级最高的线程,会中断所有其他线程,并且不会被其他任务打断
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,
};
const struct sched_class dl_sched_class = {
 .next   = &rt_sched_class,
 .enqueue_task  = enqueue_task_dl,
 .dequeue_task  = dequeue_task_dl,
 .yield_task  = yield_task_dl,

 .check_preempt_curr = check_preempt_curr_dl,

 .pick_next_task  = pick_next_task_dl,
 .put_prev_task  = put_prev_task_dl,

#ifdef CONFIG_SMP
 .select_task_rq  = select_task_rq_dl,
 .set_cpus_allowed       = set_cpus_allowed_dl,
 .rq_online              = rq_online_dl,
 .rq_offline             = rq_offline_dl,
 .task_woken  = task_woken_dl,
#endif

 .set_curr_task  = set_curr_task_dl,
 .task_tick  = task_tick_dl,
 .task_fork              = task_fork_dl,
 .task_dead  = task_dead_dl,

 .prio_changed           = prio_changed_dl,
 .switched_from  = switched_from_dl,
 .switched_to  = switched_to_dl,

 .update_curr  = update_curr_dl,
};
//作用于实时线程
const struct sched_class rt_sched_class = {
 .next   = &fair_sched_class,
 .enqueue_task  = enqueue_task_rt,
 .dequeue_task  = dequeue_task_rt,
 .yield_task  = yield_task_rt,

 .check_preempt_curr = check_preempt_curr_rt,

 .pick_next_task  = pick_next_task_rt,
 .put_prev_task  = put_prev_task_rt,

#ifdef CONFIG_SMP
 .select_task_rq  = select_task_rq_rt,

 .set_cpus_allowed       = set_cpus_allowed_common,
 .rq_online              = rq_online_rt,
 .rq_offline             = rq_offline_rt,
 .task_woken  = task_woken_rt,
 .switched_from  = switched_from_rt,
#endif

 .set_curr_task          = set_curr_task_rt,
 .task_tick  = task_tick_rt,

 .get_rr_interval = get_rr_interval_rt,

 .prio_changed  = prio_changed_rt,
 .switched_to  = switched_to_rt,

 .update_curr  = update_curr_rt,
};
//每个cpu的第一个PID=0的线程,swapper,是一个静态线程。调度类属于idle_sched_class。一般运行在开机过程和cpu异常的时候会做dump
const struct sched_class idle_sched_class = {
 /* .next is NULL */
 /* no enqueue/yield_task for idle tasks */

 /* dequeue is not valid, we print a debug message there: */
 .dequeue_task  = dequeue_task_idle,

 .check_preempt_curr = check_preempt_curr_idle,

 .pick_next_task  = pick_next_task_idle,
 .put_prev_task  = put_prev_task_idle,

#ifdef CONFIG_SMP
 .select_task_rq  = select_task_rq_idle,
 .set_cpus_allowed = set_cpus_allowed_common,
#endif

 .set_curr_task          = set_curr_task_idle,
 .task_tick  = task_tick_idle,

 .get_rr_interval = get_rr_interval_idle,

 .prio_changed  = prio_changed_idle,
 .switched_to  = switched_to_idle,
 .update_curr  = update_curr_idle,
};
//公平调度器CFS,一般常用线程
const struct sched_class fair_sched_class = {
 .next   = &idle_sched_class,
 .enqueue_task  = enqueue_task_fair,
 .dequeue_task  = dequeue_task_fair,
 .yield_task  = yield_task_fair,
 .yield_to_task  = yield_to_task_fair,

 .check_preempt_curr = check_preempt_wakeup,

 .pick_next_task  = pick_next_task_fair,
 .put_prev_task  = put_prev_task_fair,

#ifdef CONFIG_SMP
 .select_task_rq  = select_task_rq_fair,
 .migrate_task_rq = migrate_task_rq_fair,

 .rq_online  = rq_online_fair,
 .rq_offline  = rq_offline_fair,

 .task_waking  = task_waking_fair,
 .task_dead  = task_dead_fair,
 .set_cpus_allowed = set_cpus_allowed_common,
#endif

 .set_curr_task          = set_curr_task_fair,
 .task_tick  = task_tick_fair,
 .task_fork  = task_fork_fair,

 .prio_changed  = prio_changed_fair,
 .switched_from  = switched_from_fair,
 .switched_to  = switched_to_fair,

 .get_rr_interval = get_rr_interval_fair,

 .update_curr  = update_curr_fair,

#ifdef CONFIG_FAIR_GROUP_SCHED
 .task_move_group = task_move_group_fair,
#endif
};
  • SCHED_NORMAL,SCHED_BATCH,SCHED_IDLE直接被映射到fair_sched_class;
  • SCHED_RR,SCHED_FIFO与rt_schedule_class进行相关联;

Linux调度的核心选择下一个合适的task运行时,会按照优先级顺序调度类的pick_next_task函数

3、优先级

  • task_struct结构体中采用三个成员表示进程的优先级:prio和normal_prio表示动态优先级,static_prio表示进程的静态优先级
  • 内核将任务优先级划分,实时优先级范围是0到MAX_RT_PRIO-1(即99),而普通进程的静态优先级范围是从MAX_RT_PRIO到MAX_PRIO-1(即100-139)
#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):优先级低,更长执行时间的进程

进程的优先级是一个0-139的整数来表示的。数字越小,优先级越高。其中优先级0-99给实时进程,100-139留给普通进程。

分类:

后端

标签:

操作系统

作者介绍

K
KyrieGuo
V1