进程调度
首先，我们需要清楚，什么样的进程会进入调度器进行选择，就是处于TASK_RUNNING状态的进程，而其他状态下的进程都不会进入调度器进行调度。
系统发生调度的时机如下:
- 调用
cond_resched()时 - 显式调用
schedule()时 - 从系统调用或者异常中断返回用户空间时
- 从中断上下文返回用户空间时
当开启内核抢占(默认开启)时，会多出几个调度时机，如下
- 在系统调用或者异常中断上下文中调用
preempt_enable()时(多次调用preempt_enable()时，系统只会在最后一次调用时会调度) - 在中断上下文中，从中断处理函数返回到可抢占的上下文时(这里是中断下半部，中断上半部实际上会关中断，而新的中断只会被登记，由于上半部处理很快，上半部处理完成后才会执行新的中断信号，这样就形成了中断可重入)
而在系统启动调度器初始化时会初始化一个调度定时器，调度定时器每隔一定时间执行一个中断，在中断会对当前运行进程运行时间进行更新，如果进程需要被调度，在调度定时器中断中会设置一个调度标志位，之后从定时器中断返回，因为上面已经提到从中断上下文返回时是有调度时机的，在内核源码的汇编代码中所有中断返回处理都必须去判断调度标志位是否设置，如设置则执行schedule()进行调度。
而我们知道实时进程和普通进程是共存的，调度器是怎么协调它们之间的调度的呢，其实很简单，每次调度时，会先在实时进程运行队列中查看是否有可运行的实时进程，如果没有，再去普通进程运行队列找下一个可运行的普通进程，如果也没有，则调度器会使用idle进程进行运行。
系统并不是每时每刻都允许调度的发生，当处于硬中断期间的时候，调度是被系统禁止的，之后硬中断过后才重新允许调度。而对于异常，系统并不会禁止调度，也就是在异常上下文中，系统是有可能发生调度的。
抢占标志
内核在thread_info的flag中设置了一个标识来标志进程是否需要重新调度, 即重新调度TIF_NEED_RESCHED, 内核在即将返回用户空间时会检查标识TIF_NEED_RESCHED标志进程是否需要重新调度。
如果内核检查进程的抢占标识被设置, 则会在一个关键的时刻, 调用调度器来完成调度和抢占的工作。
内核抢占和用户抢占
而根据进程抢占发生的时机, 抢占可以分为内核抢占和用户抢占, 内核抢占就是指一个在内核态运行的进程, 可能在执行内核函数期间被另一个进程取
用户抢占发生几下情况：
- 从系统调用返回用户空间；
- 从中断(异常)处理程序返回用户空间
内核抢占发生的时机，一般发生在：
- 当从中断处理程序正在执行，且返回内核空间之前。当一个中断处理例程退出，在返回到内核态时(kernel-space)。这是隐式的调用schedule()函数，当前任务没有主动放弃CPU使用权，而是被剥夺了CPU使用权。
- 当内核代码再一次具有可抢占性的时候，如解锁（spin_unlock_bh）及使能软中断(local_bh_enable)等, 此时当kernel code从不可抢占状态变为可抢占状态时(preemptible again)。也就是preempt_count从正整数变为0时。这也是隐式的调用schedule()函数
- 如果内核中的任务显式的调用schedule(), 任务主动放弃CPU使用权
- 如果内核中的任务阻塞(这同样也会导致调用schedule()), 导致需要调用schedule()函数。任务主动放弃CPU使用权
内核抢占采用同抢占标识的类似方法被实现, linux内核在thread_info结构中添加了一个自旋锁标识preempt_count, 称为抢占计数器(preemption counter).
进程调度算法
用于实时作业的调度算法FIFO, RR
FIFO:
先进先出的调度策略， 当调度程序把CPU分配给进程的时候， 他把改进城描述符放到运行队列链表的当前位置。 如果没有其他可运行的更高优先级的实时进程，进程就可以一直使用CPU.即使有处于相同优先级的其他进程。
RR
当调度程序把CPU分配给进程的时候， 他把该进程描述符挂到运行队列链表的末尾。 这种策略保证对所有具有相同优先级的实时进程公平的分配CPU时间。
用于普通作业的调度算法CFS
对于普通进程的调度， linux 大致经历了 普通优先级调度算法 ， O(1) ， CFS 调度算法 三个时期。
CFS 最终被设置为linux的默认调度器。它从 RSDL/SD 中吸取了完全公平的思想，不再跟踪进程的睡眠时间，也不再企图区分批处理进城与交互式进程。
算法核心依靠红黑树:
CFS如何实现 pick next
CFS抛弃了 active/expire 数组，而使用红黑树选取下一个被调度进程。
所有状态为RUNABLE的进程都被插入红黑树。在每个调度点，CFS调度器都会选择红黑树的最左边的叶子节点作为下一个将获得cpu的进程。
tick中断
在CFS中，tick中断首先更新调度信息。然后调整当前进程在红黑树中的位置。
调整完成后如果发现当前进程不再是最左边的叶子，就标记need_resched标志，中断返回时就会调用scheduler()完成进程切换。否则当前进程继续占用CPU。
从这里可以看到CFS抛弃了传统的时间片概念。Tick中断只需更新红黑树，以前的所有调度器都在tick中断中递减时间片，当时间片或者配额被用完时才触发优先级调整并重新调度。
scheduler_tick()函数会被时钟中断直接调用。它首先更新runqueue级变量clock；然后调用CFS的tick处理函数task_tick_fair()。
红黑树键值计算
理解CFS的关键就是了解红黑树键值的计算方法。该键值由三个因子计算而得：一是进程已经占用的CPU时间；二是当前进程的nice值；三是当前的cpu负载。
进程插入红黑树的键值即为
键值 = fair_clock - wait_runtime。
fair_clock : 其字面含义上讲就是一个进程应获得的CPU时间，即等于进程已占用的CPU时间除以当前runqueue中的进程总数；
fair_clock = [实际运行时间 * (NICE_0_LOAD/nice)] / 当前runqueue中的进程总数
wait_runtime : 是进程的等待时间。
调度器
周期调度器 scheduler_tick
周期性调度器 scheduler_tick 由内核时钟中断周期性的触发, 周期性调度器以固定的频率激活负责当前进程调度类的周期性调度方法, 以保证系统的并发性, 周期性调度器通过调用进程所属调度器类的task_tick操作完成周期性调度的通知和配置工作, 通过 resched_curr 函数(早期的resched_task函数)设置抢占标识 TIF_NEED_RESCHED 来通知内核在必要的时间由主调度函数完成真正的调度工作, 此种做法称之为延迟调度策略.
主要任务:
- 更新相关统计量 : 管理内核中的与整个系统和各个进程的调度相关的统计量. 其间执行的主要操作是对各种计数器+1
- 激活负责当前进程调度类的周期性调度方法 : 检查进程执行的时间是否超过了它对应的ideal_runtime，如果超过了，则告诉系统，需要启动主调度器(schedule)进行进程切换。
主调度器schedule
schedule 就是主调度器的工作函数, 在内核中的许多地方, 如果要将CPU分配给与当前活动进程不同的另一个进程, 都会直接调用主调度器函数 schedule 或者其子函数 __schedule.
__schedule 完成抢占
- 完成一些必要的检查, 并设置进程状态, 处理进程所在的就绪队列
- 调度全局的pick_next_task选择抢占的进程
- 如果当前cpu上所有的进程都是cfs调度的普通非实时进程, 则直接用cfs调度, 如果无程序可调度则调度idle进程
- 否则从优先级最高的调度器类
sched_class_highest(目前是stop_sched_class)开始依次遍历所有调度器类的pick_next_task函数, 选择最优的那个进程执行 context_switch完成进程上下文切换- 调用
switch_mm(), 把虚拟内存从一个进程映射切换到新进程中 - 调用
switch_to(),从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息
| 调度实体 | 名称 | 描述 |
|---|---|---|
| sched_dl_entity | DEADLINE调度实体 | 采用EDF算法调度的实时调度实体 |
| sched_rt_entity | RT调度实体 | 采用Roound-Robin或者FIFO算法调度的实时调度实体 |
| sched_entity | CFS调度实体 | 采用CFS算法调度的普通非实时进程的调度实体 |
参考内容:
