1.调度器

内核中用来安排进程执行的模块称为调度器（scheduler），它可以切换进程状态.

调度器是CPU中央处理器的管理员，主要负责完成做两件事情：

• 选择某些就绪进 程来执行
• 打断某些执行的进程让它们变为就绪状态

调度器分配CPU时间的基本依据就是进程的优先级。上下文 切换（context switch）：将进程在CPU中切换执行的过程，内核承担此任务，负责重建和存储被切换掉之前的CPU状态

2.调度类分析

sched_class结构体表示调度类，定义在kernel/sched/sched.h

成员分析

enqueue_task:向就绪队列添加一个进程,当某个任务进入运行状态,该函数将会被调用,将调度的实体放入到红黑树中

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

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

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

pick_next_task:选择要运行的最合适的进程

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

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

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

struct sched_class {//系统中有多个调度类,按照调度的优先级存放在链表中const struct sched_class *next;//将进程加入到执行队列当中,即将调度实体(进程)存放到红黑树中,并对nr_running变量自增1void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);//从执行的队列当中删除进程,并对nr_running变量自减1void (*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//为进程选择一个合适的CPUint  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);//迁移任务到另一个CPUvoid (*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函数,可能引起进程切换,驱动运行时(running)被抢占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_SCHEDvoid (*task_move_group) (struct task_struct *p);
#endif
};

3.调度类

Linux调度类：dl_sched_class、rt_sched_class、fair_sched_class及idle_sched_class等。每一个进程都对应一种调度策略,每一种调度策略又对应一种调度类,每一个调度类可以对应多种调度策略.

SCHED_FIFO调度策略的实时进程永远比SCHED_NORMAL调度策略的普通进程优先级高

调度类的优先级顺序:

stop_sched_class > dl_sched_class > rt_sched_class > fair_sched_class > idle_sched_class

//linux内核调度策略源码：/include/uapi/linux/sched.h
extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;//实时调度器,调度策略:SCHED_FIFO,SCHED_RR
extern const struct sched_class rt_sched_class; 
//完全公平调度器,调度策略:SCHED_NORMAL,SCHED_BATCH等
extern const struct sched_class fair_sched_class;extern const struct 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,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,//作用于实时进程
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,//每个CPU的第一个PID=0线程,swapper是一个静态线程,调度类属于idel_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,// 源码目录：kernel/sched/fair.c
//公平调度器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,

SCHED_NORMAL,SCHED_BATCH,SCHED_IDLE直接映射到fair_sched_class

SCHED_RR,SCHED_FIFO与rt_schedule_class进行关联

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

4.优先级与调度策略

//源码：/include/linux/sched/prio.h
#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为普通进程

调度策略

unsigned int policy:保存进程的调度策略

SHCED_NORMAL:用于普通进程,通过CFS调度器来实现

SHCED_BATCH:相当于SCHED_NORMAL分化的版本,采用分时策略,根据动态优先级,分配CPU运行所需要资源

SHCED_IDLE:优先级最低,在系统空空闲时才执行这类进程

SHCED_RR:轮流调度算法(实时调度策略)

SHCED_DEADLINE:新支持的实时进程调度策略,针对突发性的计算

SCHED_BATCH用于非交互处理器消耗性进程,SHCED_IDLE是在系统负载很低时使用CFS

/** Scheduling policies*/
#define SCHED_NORMAL		0
#define SCHED_FIFO		1
#define SCHED_RR		2
#define SCHED_BATCH		3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE		5
#define SCHED_DEADLINE		6

5.调度器结构分析

进程调度任务:合理分配CPU时间给运行的进程

调度器目标:有效的分配CPU时间片

主调度器:通过schedule()函数来完成进程的选择和切换

周期调度器:根据频率自动调用

scheduler_tick函数:根据进程运行时间触发调度

上下文切换:用于切换地址空间,切换寄存器,栈空间

源码目录：kernel/sched/sched.h

/* 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_64BITu64 min_vruntime_copy;
#endif//红黑树的rootstruct 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;