3.7.4.1. linux进程调度器概述
内存中保存了对每个进程的唯一描述，并通过若干结构和其他进程连接起来
调度器面对的情形就是这样，其任务是在程序之间共享CPU时间,创造并行执行的错觉,该任务分为两个不同的部分,其中一个涉及 调度策略 另一个涉及 上下文切换
3.7.4.1.1. 背景知识
3.7.4.1.1.1. 什么是调度器
通常来说,操作系统是应用程序和可用资源之间的媒介
典型的资源有内存和物理设备，其实CPU也可以认为是一种资源,调度器可以临时分配一个任务在上面执行,调度器使我们同时执行多个程序成为可能，因此可以与具有 各种需求的用户共享CPU
内核必须提供一种方法，在各个进程之间尽可能的公平的共享CPU时间,而又要考虑不同人物的任务优先级
调度器的一个重要目标是有效的分配CPU时间片，同时提供很好的用户体验，调度器还需要面对一些互相冲突的目标，例如既要为关键实时任务最小化响应时间，又要最大限度 的提高CPU的总体利用率
3.7.4.1.1.2. 调度策略
linux操作系统算法需要解决几个互相冲突的目标
进程响应时间尽可能快
后台作业的吞吐量即可能高
尽可能避免进程的饥饿现象
低优先级和高优先级进程的需要尽可能调和
调度策略的任务就是决定什么时候以一种怎么样的方式选择一个新进程占用CPU运行
3.7.4.1.1.3. 进程饥饿
进程饥饿，指当等待时间给进程推进和响应带来明显影响成为进程饥饿。当饥饿到一定程度进程即使完成也无实际意义的时候成为饥饿死亡
产生饥饿的原因主要是，在一个动态系统中对于每种资源系统需要确定一个分配策略，当多个进程同时访问某种资源时，由分配策略确定资源分配给进程的次序，如果策略 不当或者产生死锁则会发生饥饿
3.7.4.1.2. linux进程分类
传统上分为 I/O受限(I/O-dound) 和 CPU受限(CPU-bound)
I/O受限型：别称I/O密集型，频繁使用I/O设备，并花费很多时间在等待I/O操作的完成，例如数据库服务器或者文本编辑器
CPU受限型：别称计算密集型，花费大量CPU时间进程数值计算
另外一种分类方法把进程分为三类：
交互式进程：此类进程经常与用户进程交互，因此需要花费很多时间在等待键盘和鼠标操作，当接受了用户的输入后进程必须很快被唤醒，否则会感觉系统反映迟钝
批处理进程：此类进程不与用户进行交互，经常处于后台运行，此类进程不需要快速响应，比如程序语言的编译程序、数据库搜索引擎
实时进程：这类进程有很强的调度需要，这样的进程绝不会被低优先级的进程阻塞，并且他们的响应时间要尽可能的短
对于实时进程，采用FIFO或者Round Robin的调度策略
对于普通进程，则需要区分交互式和批处理式的不同，传统linux调度器提高交互式应用的优先级，使得它们能更快的调度。而CFS和RSDL等新的调度器的核心思想是完全公平。 这个设计理念不仅大大的简化了调度器代码复杂度，还对各种调度需求提供了更完美的支持
3.7.4.1.3. linux调度器设计
3.7.4.1.3.1. linux进程调度器的框架
两个调度器
可以用两种方法来激活调度
一种是比较直接的，比如进程打算睡眠或者处于其他原因放弃CPU
另一种是通过周期性的机制，以固定的频率运行不时的检测是否有必要
因此当前linux的调度程序由两个调度器组成：主调度器，周期性调度器(通用调度器或者核心调度器)。并且每个调度器包括两个内容：调度框架 及 调度器类
6种调度策略
字段 |
描述 |
调度器 |
|---|---|---|
SCHED_NORMAL |
用于普通进程,通过CFS调度器实现 |
cfs |
SCHED_BATCH |
SCHED_NORMAL普通进程的分化版本,采用分时策略,根据动态优先级,分配CPU运算资源. |
cfs |
SCHED_IDLE |
优先级最低，只有在系统空闲时才跑这类进程 |
cfs |
SCHED_FIFO |
先入先出(实时调度策略),相同优先级的先到先服务，高优先级的可以抢占低优先级的任务 |
rt |
SCHED_RR |
轮流调度算法(实时调度策略),采用时间片，相同优先级的当用完时间片以后会被放到队列尾部,以保证 公平性,高优先级的可以抢占低优先级的 |
rt |
SCHED_DEADLINE |
新支持的实时进程调度策略,针对突发型计算,且对延迟和完成时间高度敏感的任务适用. |
而依据其调度策略的不同实现了5个调度器类，一个调度器类可以用一种或者多种调度策略某一类进程，也可以用于特殊情况或者调度特殊功能的进程
调度器类 |
描述 |
对应的调度策略 |
|---|---|---|
stop_sched_class |
优先级最高的线程，会中断所有其他线程，且不会被其他任务打断 1.发生在cpu_stop_cpu_callback进行cpu之间任务migration 2.HOTPLUG_CPU的情况下关闭任务 |
不需要调度普通进程 |
dl_sched_class |
采用EDF最早截至时间优先算法调度实时进程 |
SCHED_DEADLINE |
rt_sched_class |
采用RR算法或者FIFO算法调度实时进程，具体调度策略由进程的task_struct->policy指定 |
SCHED_FIFO/RR |
fair_sched_class |
采用CFS算法调度普通的非实时进程 |
SCHED_NORMAL/BATCH |
idle_sched_class |
采用CFS算法调度idle进程，每个cpu的第一个pid=0线程：swapper，是一个静态线程 在ps中看不到的，一般运行在开机过程或者cpu异常的时候做dump |
SCHED_IDLE |
所属进程的优先级顺序为
stop_sched_calss > dl_sched_class > rt_sched_class > fair_sched_class > idle_sched_class
3个调度实体
调度器不限于调度进程，还可以调度更大的实体，比如实现组调度：可用的cpu时间首先在一半的进程组之间分配，接下来分配的时间在组内进行二次分配
因此需要一个通用的数据结构描述这个调度实体，即sched_entity结构，其实际上就代表了一个调度对象，可以为一个进程，也可以为一个进程组
调度实体 |
名称 |
描述 |
调度器类 |
|---|---|---|---|
sched_dl_entity |
DEADLINE调度实体 |
采用EDF算法调度的实体调度实体 |
dl_class_class |
sched_dt_entity |
RT调度实体 |
采用RR或者FIFO算法调度的实时调度实体 |
rt_sched_class |
sched_entity |
CFS调度实体 |
采用CFS算法调度的普通非实时进程调度实体 |
fair_sched_class |
调度器类的就绪队列
对于调度框架和调度器类，他们都有自己管理的运行队列，调度框架只时别rq，而对于cfs调度器类他的运行队列则是cfs_rq(内部使用红黑树组织调度实体)，实时 rt的运行队列rt_rq(内部使用优先级bitmap+双向链表组织调度实体)，此外内核对新增的dl实时策略也提供了运行队列dl_rq
调度器整体框架
本质上通用调度器(核心调度器)是一个分配器,与其他两个组件交互
调度器用来判断接下来运行哪个进程
内核支持不通的调度策略(完全公平调度,实时调度,在无事可做的时候调度空闲进程,即0号进程也叫swapper进程,idle进程),调度类使得能够以模块化的方法 实现这些策略，即一个类的代码不需要与其他类的代码交互，当调度器被调用时,它会查询调度器类，得知接下来运行哪个进程
在选中将要运行的进程之后，必须执行底层的任务切换
这需要与CPU的紧密交互,每个进程刚好属于某一调度类,各个调度类负责管理所属的进程,通用调度器本身不涉及进程管理,其工作都委托给调度器类
每个进程都属于某个调度器类(由字段task_struct->sched_class),由调度器类采用进程对应的调度策略调度(由task_struct->policy)进行调度,task_struct也存储了其对应 的调度实体标识。
linux实现了6种调度策略，而依据其调度策略的不同实现了5个调度器类,一个调度器类可以用一种或者多种调度策略某一类进程,也可以用于特殊情况或者调度特殊功能的进程、
调度器类 |
调度策略 |
调度算法 |
调度实体 |
调度对象 |
|---|---|---|---|---|
stop_sched_cla |
无 |
无 |
无 |
|
dl_sched_class |
SCHED_DEADLINE |
sched_dl_entity |
采用DEF最早截至时间有限算法调度实时进程 |
|
rt_sched_class |
SCHED_FIFO/RR |
RR时间片轮转/FIFO |
sched_rt_entity |
实时进程 |
fair_sched_cla |
SCHED_NORMAL |
CFS完全公平调度算法 |
sched_entity |
采用CFS算法普通非实时进程 |
idle_sched_cla |
SCHED_IDLE |
无 |
无 |
idle进程 |
3.7.4.1.4. 进程的调度
什么样的进程会进入调度器进行选择,就是处于TASK_RUNNING状态的进程，而其他状态的进程都不会进入进入调度器进行调度
发生调度的时机如下
调用cond_resched()时
显示调用schedule()时
从系统调用或者异常中断返回用户空间时
从中断上下文返回用户空间时
当开启内核抢占(默认开启)时，会多出几个调度时机,如下
在系统调用或者异常中断上下文种调用preempt_enable()时(多次调用,系统只在最后一次调用时会调度)
在中断上下文种从中断处理函数返回到可抢占的上下文时(这里是中断下半部,中断上半部实际上会关中断,而新的中断只会被登记,由于上半部处理很快,上半部处理完成后才会执行新的的中断信号,这样就形成了可重入)
在系统启动调度器初始化时会初始化一个调度定时器,调度定时器每隔一定时间执行一个中断,在中断会对当前运行进程时间进行更新,如果进程需要被调度,在调度定时器中断中会设置一个调度标志位,之后从定时器中断返回 因为上面已经提到从中断上下文返回时是有调度时机的,在内核源码的汇编代码中所有中断返回处理都必需去判断调度标志位是否设置,如设置则执行schedule()进行调度
我们知道实时进程和普通进程是共存的,调度器是怎么协调他们之间的调度的呢，其实很简单,每次调度时会现在实时进程运行队列中查看是否有可运行的实时进程，如果没有再去普通进程的运行队列找下一个可运行的普通进程 ,如果也没有则取运行idle进程