调度器

• 调度器：Linux内核中用来安排调度进程（一段程序的执行过程）执行的模块成为调度器，他可以切换进程状态。比如：执行、可中断睡眠、不可中断睡眠、退出、暂停等；

• 调度器的主要职责：选择某些就绪的进程来运行、打断某些执行的进程让他们变为就绪态；

• 调度目的：最大效率使用CPU资源

• 主动进入阻塞状态：
• 被动进去阻塞状态：

如果调度器支持就绪状态切换到执行状态，同时支持执行状态切换到就绪状态，则称为抢占式调度器。

调度类sched_class结构体

// 调度类的结构体
struct sched_class {
	const struct sched_class *next; // 系统中有多个调度类，按照优先级按照调度优先级直接排成链表

#ifdef CONFIG_UCLAMP_TASK
	int uclamp_enabled;
#endif

	// 将进程加入到执行队列当中，即将调度实体（进程）存放到红黑树当中，并且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);

	// 选择下一个要运行的进程
	struct task_struct *(*pick_next_task)(struct rq *rq);

	// 将进程加入到运行队列中
	void (*put_prev_task)(struct rq *rq, struct task_struct *p);
	void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);

#ifdef CONFIG_SMP
	int (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);

	// 选择合适的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, int new_cpu);

	// 唤醒进程
	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 (*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);

#define TASK_SET_GROUP		0
#define TASK_MOVE_GROUP		1

#ifdef CONFIG_FAIR_GROUP_SCHED
	void (*task_change_group)(struct task_struct *p, int type);
#endif
};

调度器分类

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; // 空闲调度类

• 优先级（高到低）：停机调度类-限期调度类-实时调度类-公平调度类-空闲调度类；
• 停机调度类：停止进程，优先级最高，可以抢占其他进程；停机进程是优先级最高的进程，可以抢占其他进程；
• 限期调度类： 最早使用的优先算法，使用红黑树把进程按照绝对截止的期限从小到大排序，每次调度会选择截止期限最小的进程；
• 实时调度类：为每一个调度优先级维护一个队列；
• 公平调度类：使用完全公平调度算法。完全公平调度算法引入虚拟运行时间：虚拟运行时间=实际运行实现*nice0对应的权重/进程的权重；
• 空闲调度类：每个CPU上有一个空闲的线程，即0号线程。空闲调度类优先级最低，仅仅当没有其他进程可以调度的时候才会调度空闲线程。

进程优先级

// Linux 内核优先级
#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留给普通进程。

内核调度策略

Linux内核提供一些调度策略让用户应用程序选择调度器。Linux内核调度策略源码如下：

• SCHED_NORMAL：普通进程调度策略，使得ask选择CFS调度器来调度运行；
• SCHED_FIFO：实时进程调度策略，先进先出调度没有时间片，没有更高级优先级的状态下，只有等待主动让出CPU；
• SCHED_RR：实时进程调度策略，时间片轮转，进程使用完时间片之后加入优先级对应运行队列中的尾部，把CPU让给同等优先级的其他进程；
• SCHED_BATCH：普通进程调度策略，批量处理，使task选择CFS调度器来调度运行；
• SCHED_IDLE：普通进程调度策略，使task以最低优先级选择CFS调度器来运行；
• SCHED_DEADLINE：限期进程调度策略，使task选择Deadline调度器来运行。

备注：其中 Stop 调度器和 IDLE-task 调度器，仅使用于内核，用户没有办法进行选择。

CFS调度器

完全公平调度算法体现在对每个进程都是公平的，让每个进程都运行一段相同的的时间片，这就是基于时间片轮询调度算法。CFS定义一种新模型，给cfs_rq（CFS的run queue）中的每个进程都设置一个虚拟时钟virtual runtime。古国一个进程得以执行，随着时间的不断增长，他的vruntime也会不断增大，没有得到执行的进程vruntime保持不变。

进程描述符task_struct结构体中，有几个成员与调度相关，具体成员prio、normal_prio、static_prio、rt_priority等。

实际运行时间

CFS（Completely Fair Scheduler，完全公平调度器）。在实际当中必然会有进程优先级高或者进程优先级低，CFS引入权重代表进程的优先级，各个进程按照权重比例分配CPU时间。

假设有两个进程X和Y，X权重为1024，Y权重为2048。

X获得CPU的时间比为：
1024 1024 + 2048 = 33 % \frac{1024}{1024+2048}=33\% 1024+20481024​=33%
Y获得CPU的时间比例为：
2048 1024 + 2048 = 66 % \frac{2048}{1024+2048}=66\% 1024+20482048​=66%
在引入权重之后分配给进程的时间计算公式如下：
实际运行时间 = 调度曲线 ∗ 进程权重 所有进程权重和 实际运行时间=\frac{调度曲线*进程权重}{所有进程权重和} 实际运行时间=所有进程权重和调度曲线∗进程权重​

虚拟运行时间

虚拟运行时间 = 实际运行时间 ∗ N I C E _ 0 _ L O A D 进程权重 = 调度周期 ∗ 进程权重 所有进程权重 ∗ N I C E _ 0 _ L O A D 进程权重 = 调度周期 ∗ 1024 所有进程权重 虚拟运行时间=\frac{实际运行时间*NICE\_0\_LOAD}{进程权重}=\frac{调度周期*进程权重}{所有进程权重}*\frac{NICE\_0\_LOAD}{进程权重}=\frac{调度周期*1024}{所有进程权重} 虚拟运行时间=进程权重实际运行时间∗NICE_0_LOAD​=所有进程权重调度周期∗进程权重​∗进程权重NICE_0_LOAD​=所有进程权重调度周期∗1024​

在一个调度周期里，所有进程的虚拟运行时间是相同的，所以在进程调度时，只要找到虚拟运行时间最小的进程调度即可。

CFS调度器类

• enqueue_task：当任务进入可运行状态时，此函数将调度实体存入红黑树，完成入队操作。
• dequeue_task：当任务退出可运行状态时，此函数将调度实体从红黑树中移除，完成出队操作。

这两个函数接收三个参数运行队列 任务实体 标志，rq是一个抽象出来的运行队列结构体。这个结构体中的包含了完全公平调度器就绪队列 实时调度器就绪队列 限时调度器就绪队列

CFS调度器就绪队列内核源码

/* CFS-related fields in a runqueue */
struct cfs_rq {
	struct load_weight	load;
	unsigned long		runnable_weight;
	unsigned int		nr_running;
	unsigned int		h_nr_running;      /* SCHED_{NORMAL,BATCH,IDLE} */
	unsigned int		idle_h_nr_running; /* SCHED_IDLE */

	u64			exec_clock;
	u64			min_vruntime;
#ifndef CONFIG_64BIT
	u64			min_vruntime_copy;
#endif

	struct rb_root_cached	tasks_timeline;

	/*
	 * '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;
	struct sched_entity	*next;
	struct sched_entity	*last;
	struct sched_entity	*skip;

#ifdef	CONFIG_SCHED_DEBUG
	unsigned int		nr_spread_over;
#endif

#ifdef CONFIG_SMP
	/*
	 * CFS load tracking
	 */
	struct sched_avg	avg;
#ifndef CONFIG_64BIT
	u64			load_last_update_time_copy;
#endif
	struct {
		raw_spinlock_t	lock ____cacheline_aligned;
		int		nr;
		unsigned long	load_avg;
		unsigned long	util_avg;
		unsigned long	runnable_sum;
	} removed;

#ifdef CONFIG_FAIR_GROUP_SCHED
	unsigned long		tg_load_avg_contrib;
	long			propagate;
	long			prop_runnable_sum;

	/*
	 *   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;
	s64			runtime_remaining;

	u64			throttled_clock;
	u64			throttled_clock_task;
	u64			throttled_clock_task_time;
	int			throttled;
	int			throttle_count;
	struct list_head	throttled_list;
#endif /* CONFIG_CFS_BANDWIDTH */
#endif /* CONFIG_FAIR_GROUP_SCHED */
};

cfs_rq：跟踪就绪队列信息，管理就绪态调度实体，维护一棵按照虚拟时间排序的红黑树。tasks_timeline->rb_root指向红黑树的根，tasks_timeline->rb_leftmost指向红黑树最左边的调度实体，即虚拟时间最小的调度实体。