|
本文主要介绍一下在Linux系统中进程的调度
调度类和调度策略
进程主要可以分为两种：
- 实时进程：实时进程一般是需要操作系统尽快返回结果，因此优先级比较高
- 普通进程：一般情况下大多数进程都是普通进程，优先级没有实时进程那么高
因此，对于不同的进程就会有不同的调度策略。
在进程数据结构 task_struct 中有一个成员变量为该进程的调度类
unsigned int policy;
配合这个成员变量的还有用于描述优先级的成员变量
int prio, static_prio, normal_prio;
unsigned int rt_priority;
这里的优先级是一个数值，值越小优先级越高，且所有的实时进程优先级都比普通进程的优先级要高
实时进程调度策略
实时进程有三种调度策略：
- SCHED_FIFO ： 先来先服务，但是优先级高的进程可以抢占优先级低的进程。
- SCHED_RR ： 具有相同优先级的进程采用轮流调度的方式，采用时间片，时间片用完的进程会被放到队列的对尾，以此保证公平性，但优先级高的进程同样可以抢占优先级低的进程。
- SCHED_DEADLINE ： 按照deadline的方式进行调度，每次产生调度的时候，DL调度器会优先采用deadline距离当前时间点最近的那个进程。
普通进程调度策略
普通进程的调度策略有：
- SCHED_NORMAL ：普通进程的调度策略
- SCHED_BATCH ： 后台进程的调度策略，由于几乎不需要和前端进行交互，因此可以默默执行且不影响需要交互的进程，可以适当降低其优先级
- SCHED_IDLE ： 特别空闲时才跑的进程，优先级最低
上面的调度策略仅仅只是规定了进程应该这样调度，因此还要有一个调度类来对其进行调度。在task_struct里就有对应的调度类struct sched_class，用于执行调策略。而sched_class的几种实现都分别一一对应上面提到的调度策略。
完全公平调度算法
在Linux里实现了一个基于CFS完全公平调度的算法。
在CFS中，CPU会提供一个时钟，每隔一段时间触发一次时间中断。
CFS为每一个进程都安排了一个虚拟运行时间vruntime，随着时间的增长vruntime会不断增大，而没有运行的进程的vruntime不变。
因此在进行进程调度时优先调度vruntime值低的进程。
配合优先级，优先级高的进程被分配到的vruntime就会大。
CFS有专门的成员变量来对这些时间进行记录，这里不详细展开~
调度队列与调度实体
不难发现，CFS需要一种数据结构来对vruntime进行排序，并且要求查找、插入、修改、以及删除的效率要高，因此使用了红黑树来对其进行存储。
红黑树的节点包括vruntime，成为调度实体
在task_struct中有三个成员变量
struct sched_entity se;
struct sched_rt_entity rt;
struct sched_dl_entity dl;
不光是CFS，其他调度策略也需要一种数据结构来对调度实体进行排序。
进程根据自己是哪种类型的，将自己挂在对应调度策略的数据结构里进行排序，如普通进程会将自己挂在红黑树上。
红黑树以时间为顺序对调度实体进行排序，最小的在左边，最大的在右边。CFS会获取红黑树最左边的节点作为下一个获得cpu的任务。
每个CPU都有自己的struct rq结构，用于描述cpu上所有运行的进程，其中包括rt_rq（实时进程队列）和cfs_rq（CFS运行队列）。在调度时先去实时进程队列看有没有任务需要运行，没有采取cfs队列去看有没有任务需要运行。
cfs_rq有一个成员变量 rb_root，指向红黑树的根节点，在cpu的视角就是一个队列，不断去取最左边的节点进行调度。
在调度类中有一个指针，指向下一个被调度的进程。
不同的调度类有不同的实现方式。
在进行调度时，先会在rt_rq中找下一个任务，只有在rt_rq中找不到任务时，才会在cfs_rq中找下一个任务。
进程的主动调用
当一个进程因为需要等待而主动让出cpu时，会调用 schedule() 进行主动调度
schedule() 的调度过程：
- 对于cfs来说，就是先取出红黑树
- 取出当前正在运行的任务，如果处于就绪状态，则更新vruntime，然后取出红黑树最左边的节点
- 如果最左边节点和当前节点不一样，则说明找到一个更需要运行的进程，将当前任务放回红黑树，将最左边节点的任务设置成当前任务。
- 进行上下文切换
上下文切换
进程上下文切换主要有两件事：
- 切换进程空间 ： 主要涉及到内存相关的知识，这里同样先跳过~
- 切换寄存器和CPU上下文 ：
- 首先是栈的切换：
- 寄存器切换 ：
- 对于每个进程，在内存中维护了一个TSS，这里面有所有的寄存器。
- 还有一个特殊的寄存器TR，指向这某个进程的TSS。更改TR的值，会触发硬件保存CPU所有寄存器的值到当前进程的TSS中，然后从新进程中的TSS读取出所有寄存器的值，加载到CPU对应的寄存器中。
- 但这样又个缺点是，每次进行进程切换的时候，会更改每个寄存器的值，这样每次全量保存、全量切换效率不是很高。
- 因此每个CPU都关联了一个TSS，然后TR永远指向这个TSS。在task_struct中有一个成员变量thread保留了切换进程时需要保存的寄存器，这样每次进程切换时只要将某个进程的thread里面的值写到CPU的TR指向的TSS中就算是完成了切换。
指令指针的保存与回复
当进程进行调度时，一定会调用schedule()
在进程进行切换时，会经过下面三句话
switch_to(prev, next, prev);
barrier();
return finish_task_switch(prev);
当进程执行到switch_to时，内核态的指令指针也是指向这一行，但此时寄存器和栈都已经切换成下一个进程的了，唯一不变的就是这个指令指针，当switch_to返回时指向了下一条指令finish_task_switch，但此时不是当前进程的finish_task_switch，而是下一个进程的finish_task_switch。
由于进程进行调度时一定会调用schedule()，包括此时的新进程也是，因此此时新进程一定是之前在switch_to被切换下去了，而现在只是恢复了而已。（不知道这段表达大家能不能看得懂…我是按照自己的理解来的）
因此当被切换走的进程再次切换回来时就能接着运行啦！
抢占式调度
主动调度时进程调度的第一种方式，第二种方式则是抢占式调度
发生抢占调度的一种情况：一个进程的执行时间太长了，要切换到另一个进程了
在计算机中有一个时钟，每隔一段时间就触发一次时间中断，可以通过这个来查看是否是需要抢占的时间点。
- 先取出当前CPU的运行队列，得到当前正在运行的task_struct，然后调用这个task_struct的调度类的用来处理时钟时间的函数task_tick()
- 如果当前进程是普通进程
- 根据当前进程的task_struct，找到对应的调度实体和cfs队列，调用entity_tick
- 在entity_tick，先更新当前进程的vruntime，然后检查是否是时候被抢占
- 先算出该进程应该运行的实际时间
- 如果该进程的实际运行时间大于计算出来的值，则应该被抢占，除此以外，如果当前进程的vruntime大于红黑树中最小节点的vruntime且差值大于计算出来的值，也应该被抢占。
- 但此时仅仅只是将该进程标记成应被抢占而不是将其直接踢下来，不然该进程无法接着从schedule运行。
另一个应该被抢占的情况是当一个进程被唤醒的时候。
如果被唤醒的进程优先级高于当前正在运行的进程，也会发生抢占
进程抢占的时机
用户态进程抢占时机
对用户态来说，当进程从系统调用返回时就是一个被抢占的时机。
当进程从系统调用返回时，如果该进程被打了标记，则执行schedule系统调用进行进程调度
从中断返回也是进程抢占的时机。
中断返回后，如果是返回到用户态，则和上面的逻辑一样
内核态进程抢占时机
内核态进程被抢占时一般发生在preempt_enable()中
由于内核态的代码在操作时一般是不能中断的，因此在执行这些操作前都会调用preempt_disable()关闭抢占，当再次打开时，也就是调用了preempt_enable()时，就是一个抢占的时机。
然后接下来的操作就和用户态的逻辑差不多了。
总结
本文是自己学习时候的笔记，有不对的地方还请各位指出。
|