我们前面提到linux有两种方法激活调度器：核心调度器和
周期调度器
- 一种是直接的, 比如进程打算睡眠或出于其他原因放弃CPU
- 另一种是通过周期性的机制, 以固定的频率运行, 不时的检测是否有必要
因而内核提供了两个调度器主调度器，周期性调度器，分别实现如上工作, 两者合在一起就组成了核心调度器(core scheduler), 也叫通用调度器(generic scheduler).
他们都根据进程的优先级分配CPU时间, 因此这个过程就叫做优先调度, 我们将在本节主要讲解核心调度器的设计和优先调度的实现方式.
而我们的周期性调度器以固定的频率激活负责当前进程调度类的周期性调度方法, 以保证系统的并发性
1 前景回顾
首先还是让我们简单回顾一下子之前的的内容
1.1 进程调度
内存中保存了对每个进程的唯一描述, 并通过若干结构与其他进程连接起来.
调度器面对的情形就是这样, 其任务是在程序之间共享CPU时间, 创造并行执行的错觉, 该任务分为两个不同的部分, 其中一个涉及调度策略, 另外一个涉及上下文切换.
内核必须提供一种方法, 在各个进程之间尽可能公平地共享CPU时间, 而同时又要考虑不同的任务优先级.
调度器的一般原理是, 按所需分配的计算能力, 向系统中每个进程提供最大的公正性, 或者从另外一个角度上说, 他试图确保没有进程被亏待.
1.2 进程的分类
linux把进程区分为实时进程和非实时进程, 其中非实时进程进一步划分为交互式进程和批处理进程
根据进程的不同分类Linux采用不同的调度策略.
对于实时进程，采用FIFO, Round Robin或者Earliest Deadline First (EDF)最早截止期限优先调度算法|的调度策略.
对于普通进程则采用CFS完全公平调度器进行调度
1.3 linux调度器的演变
| 字段 | 版本 |
|---|---|
| O(n)的始调度算法 | linux-0.11~2.4 |
| O(1)调度器 | linux-2.5 |
| CFS调度器 | linux-2.6~至今 |
1.4 Linux的调度器组成
2个调度器
可以用两种方法来激活调度
- 一种是直接的, 比如进程打算睡眠或出于其他原因放弃CPU
- 另一种是通过周期性的机制, 以固定的频率运行, 不时的检测是否有必要
因此当前linux的调度程序由两个调度器组成：主调度器，周期性调度器(两者又统称为通用调度器(generic scheduler)或核心调度器(core scheduler))
并且每个调度器包括两个内容：调度框架(其实质就是两个函数框架)及调度器类
6种调度策略
linux内核目前实现了6中调度策略(即调度算法), 用于对不同类型的进程进行调度, 或者支持某些特殊的功能
- SCHED_NORMAL和SCHED_BATCH调度普通的非实时进程
- SCHED_FIFO和SCHED_RR和SCHED_DEADLINE则采用不同的调度策略调度实时进程
- SCHED_IDLE则在系统空闲时调用idle进程.
5个调度器类
而依据其调度策略的不同实现了5个调度器类, 一个调度器类可以用一种种或者多种调度策略调度某一类进程, 也可以用于特殊情况或者调度特殊功能的进程.
其所属进程的优先级顺序为
stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class3个调度实体
调度器不限于调度进程, 还可以调度更大的实体, 比如实现组调度.
这种一般性要求调度器不直接操作进程, 而是处理可调度实体, 因此需要一个通用的数据结构描述这个调度实体,即seched_entity结构, 其实际上就代表了一个调度对象，可以为一个进程，也可以为一个进程组.
linux中针对当前可调度的实时和非实时进程, 定义了类型为seched_entity的3个调度实体
- sched_dl_entity 采用EDF算法调度的实时调度实体
sched_rt_entity
- 采用Roound-Robin或者FIFO算法调度的实时调度实体 rt_sched_class
- sched_entity 采用CFS算法调度的普通非实时进程的调度实体
2 周期性调度器
周期性调度器在scheduler_tick中实现. 如果系统正在活动中, 内核会按照频率HZ自动调用该函数. 如果没有近曾在等待调度, 那么在计算机电力供应不足的情况下, 内核将关闭该调度器以减少能耗. 这对于我们的嵌入式设备或者手机终端设备的电源管理是很重要的.
2.1 周期性调度器主流程
scheduler_tick函数定义在kernel/sched/core.c, L2910中, 它有两个主要任务
- 更新相关统计量
管理内核中的与整个系统和各个进程的调度相关的统计量. 其间执行的主要操作是对各种计数器+1
- 激活负责当前进程调度类的周期性调度方法
检查进程执行的时间是否超过了它对应的ideal_runtime，如果超过了，则告诉系统，需要启动主调度器(schedule)进行进程切换。(注意thread_info:preempt_count、thread_info:flags (TIF_NEED_RESCHED))
/*
* This function gets called by the timer code, with HZ frequency.
* We call it with interrupts disabled.
*/
void scheduler_tick(void)
{
/* 1. 获取当前cpu上的全局就绪队列rq和当前运行的进程curr */
/* 1.1 在于SMP的情况下，获得当前CPU的ID。如果不是SMP，那么就返回0 */
int cpu = smp_processor_id();
/* 1.2 获取cpu的全局就绪队列rq, 每个CPU都有一个就绪队列rq */
struct rq *rq = cpu_rq(cpu);
/* 1.3 获取就绪队列上正在运行的进程curr */
struct task_struct *curr = rq->curr;
sched_clock_tick();
/* 2 更新rq上的统计信息, 并执行进程对应调度类的周期性的调度 */
/* 加锁 */
raw_spin_lock(&rq->lock);
/* 2.1 更新rq的当前时间戳.即使rq->clock变为当前时间戳 */
update_rq_clock(rq);
/* 2.2 执行当前运行进程所在调度类的task_tick函数进行周期性调度 */
curr->sched_class->task_tick(rq, curr, 0);
/* 2.3 更新rq的负载信息, 即就绪队列的cpu_load[]数据
* 本质是讲数组中先前存储的负荷值向后移动一个位置，
* 将当前负荷记入数组的第一个位置 */
update_cpu_load_active(rq);
/* 2.4 更新cpu的active count活动计数
* 主要是更新全局cpu就绪队列的calc_load_update*/
calc_global_load_tick(rq);
/* 解锁 *