Linux 调度

• 调度策略与调度类
• 进程包括两类: 实时进程(优先级高); 普通进程
• 两种进程调度策略不同: task_struct->policy 指明采用哪种调度策略(有6种策略)
• 优先级配合调度策略, 实时进程(0-99); 普通进程(100-139)

实时调度策略, 高优先级可抢占低优先级进程

• FIFO: 相同优先级进程先来先得
• RR: 轮流调度策略, 采用时间片轮流调度相同优先级进程
• Deadline: 在调度时, 选择 deadline 最近的进程

普通调度策略

• normal: 普通进程
• batch: 后台进程, 可以降低优先级
• idle: 空闲时才运行

调度类: task_struct 中 * sched_class 指向封装了调度策略执行逻辑的类(有5种)

• stop: 优先级最高. 将中断其他所有进程, 且不能被打断
• dl: 实现 deadline 调度策略
• rt: RR 或 FIFO, 具体策略由 task_struct->policy 指定
• fair: 普通进程调度
• idle: 空闲进程调度

• 普通进程的 fair 完全公平调度算法 CFS(Linux 实现)
• 记录进程运行时间( vruntime 虚拟运行时间)
• 优先调度 vruntime 小的进程
• 按照比例累计 vruntime, 使之考虑进优先级关系
• 调度队列和调度实体
• CFS 中需要对 vruntime 排序找最小, 不断查询更新, 因此利用红黑树实现调度队列
• task_struct 中有 实时, deadline 和 cfs 三个调度实体, cfs 调度实体即红黑树节点
• 每个 CPU 都有 rq 结构体, 里面有 dl_rq, rt_rq 和 cfs_rq 三个调度队列以及其他信息; 队列描述该 CPU 所运行的所有进程
• 先在 rt_rq 中找进程运行, 若没有再到 cfs_rq 中找; cfs_rq 中 rb_root 指向红黑树根节点, rb_leftmost指向最左节点

调度类如何工作

• 调度类中有一个成员指向下一个调度类(按优先级顺序串起来)
• 找下一个运行任务时, 按 stop-dl-rt-fair-idle 依次调用调度类, 不同调度类操作不同调度队列

进程上下文切换

上下文切换主要干两件事情，一是切换进程空间，也即虚拟内存；二是切换寄存器和CPU上下文

image.png