进程调度简介

laumy
进程调度
2023-03-25
131热度
0评论

调度类别

进程调度依赖于调度策略（schedule policy），linux内核把相同的调度策略抽象成调度类（schedule class）。不同类型的进程采用不同的调度策略，目前Linux内核中默认采用5种调度类，分别是stop、deadline、realtime、CFS和idle。

Stop：最高优先级的进程，只在多核场景下启用，用于热插拔等场景下停止CPU。
Dealine：用于有严格时间要求的实时进程，优先级为-1。
Realtime：用于普通的实时进程，优先级为0~99。
CFS：完全公平调度，非实时类进程，优先级100~139。
Idle：最低优先级进程，当所有进程都没运行之后运行idle，仅供内核使用。

实际上STOP、IDLE不算是真正意义上的调度类，因为其需要在比较特殊的场景下由内核去执行，因此重点的调度主要分为三个DL,RT,CFS。
Linux用户空间程序可以使用如sched_setscheduler来设定用进程的调度策略，SCHED_NORMAL、SCHED_BATCH、SCHED_IDLE使用CFS。SCHED_FIFO和SCHED_RR用于Realtime。SCHED_DEADLINE用于DL调度。
SCHED_FIFO和SCHED_RR使用Realtime。SCHED_FIFO和SCHED_RR的区别是，SCHED_RR按时间片循环运行，如优先级相同的进程，轮流运行固定长度时间片，而SCHED_FIFO先到先得，会一直运行直到自愿放弃或被更高优先级抢占为止。
Linux系统中，按照优先级顺序从高到低顺序遍历各个调度器，如果某个调度器成功取出了任务，则选择任务进行调度。

kernel/sched/core.c

for_each_class(class) {
p = class->pick_next_task(rq);
if (p)
return p;
}

chrt -p 1234  # 可以查看 pid=1234 的进程的 调度策略
chrt -p -f 10 1234  # 修改调度策略为 SCHED_FIFO, 并且优先级为10

调度时机

调度队列

在linux系统中，定义了一个全局的struct rq类型的数组runqueues，每个CPU对应一个数组成员，定义如下：

kernel/sched/core.c
static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

kernel/sched/sched.h
#define cpu_rq(cpu)     (&per_cpu(runqueues, (cpu)))  根据CPU编号获取rq
#define this_rq()       this_cpu_ptr(&runqueues)      获取当前进程的rq
#define task_rq(p)      cpu_rq(task_cpu(p))           获取进程p所在的rq
#define cpu_curr(cpu)       (cpu_rq(cpu)->curr)       根据CPU编号获取正在运行的进程

上图列出了struct rq与struct task_struct之间的关系。每个CPU都对应一个struct rq实体。rq中分别对应3个调度队列（暂不考虑stop、idle类，从数据结构也可以看出stop、idle属于特殊调度类）。
cfs_rq对应的是CFS调度，CFS就绪进程通过红黑树来组织，调度优先选择vruntime最小的进行。
rt_rq对应的是RT调度，RT就绪进程通过链表来组织，每个优先级对应一条链表，相同优先级的进程挂载到同一条链表上；每个链表对应一个bitmap，系统通过查询bitmap的位0或1来判断当前链表中是否有进程就绪。系统调度是一次从高优先级开始遍历查询对应的bitmap，进而选择对应进程运行。
dl_rq对应的是DL调度，后续再阐述。

触发调度

调度顾名思义就是选择一个进程运行，包括系统启动运行的第一个进程，以及运行过程中从当前运行进行切换到另外一个进程。在Linux系统中触发调度的可以分为两类：主动让出调度与抢占式调度（与FreeRTOS的区别，就是抢占式调度这里，FreeRTOS是systick来进行调度，有时间片的概念，而Linux不在有时间片的概念）。
主动调度是CPU主动放弃CPU，包括主动Sleep，读写IO，Mutex等。
抢占调度在Linux系统中并不是立即得到调度权，而是在需要抢占调度时设置一个标志（TIF_NEED_RESCHED），Linux系统在合适时机检测到这个标志会进行调度，因此抢占调度可以分为三个阶段设置抢占调度标志、检测抢占调度标志、选择任务调度。
无论是主动调度还是抢占调度，最终调用的都是函数schedule。

设置抢占调度标志

设置抢占调度的标志一般有以下场景：
- Tick调度：Linux系统中有周期性的时钟，会周期性的检测当前的进程是否运行idle_runtime超期。
- 任务创建：新创建任务的时候，会将任务加入到就绪队列中，会根据优先级判定是否需要抢占。
- 任务唤醒：任务在获取到等待的资源从睡眠中唤醒，判定是否需要抢占。
- 任务切换：调整调度类、优先级等。
- 带宽控制：分配给当前运行的任务带宽用尽。

以上只是列出了部分设置抢占调度标志的代码流程，并未全部列出，并且代码流程做了简化。

Laumy的技术栈