调度器
- 调度器：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指向红黑树最左边的调度实体，即虚拟时间最小的调度实体。
