linux内核进程调度

本节主要介绍进程的调度器，设计的目标：吞吐和响应，轮流让其他进程获取CPU资源。

进程调度机制的架构

操作系统通过中断机制，来周期性地触发调度算法进行进程的切换。

• rq: 可运行队列，每个CPU对应一个，包含自旋锁，进程数量，用于公平调度的CFS结构体，当前正在运行的进程描述符。
• cfs_rq: cfs调度的运行队列信息，包含红黑色的根节点，正在运行的进程指针，用于负载均衡的叶子队列等。
• sched_entity: 调度实体，包含负载权重值，对应红黑树节点，虚拟运行时vruntime等。
• sched_class: 调度算法抽象成的调度类，包含一组通用的调度操作接口，将接口和实现分离。

schedule函数的流程包括：

1. 关闭内核抢占，标识cpu状态。通知RCU更新状态，关闭本地终端，获取所要保护的运行队列的自旋锁，为查找可运行进程做准备。
2. 检查prev状态，决定是否将进程插入到运行队列，或者从运行队列中删除。
3. task_on_rq_queued(prev) : 将pre进程插入到运行队列的队尾。
4. pick_next_task : 选取下一个将要执行的进程。
5. context_switch(rq, prev, next) 进行进程上下文切换。

CPU/IO消耗型进程

吞吐 vs. 响应

• 响应：最小化某个任务的响应时间，哪怕牺牲其他的任务为代价。
• 吞吐：全局视野，整个系统的workload被最大化处理。

任何操作系统的调度器设计只追求2个目标：吞吐率大和延迟低。这2个目标有点类似零和游戏，因为吞吐率要大，势必要把更多的时间放在做真实的有用功，而不是把时间浪费在频繁的进程上下文切换；而延迟要低，势必要求优先级高的进程可以随时抢占进来，打断别人，强行插队。但是，抢占会引起上下文切换，上下文切换的时间本身对吞吐率来讲，是一个消耗，这个消耗可以低到2us或者更低（这看起来没什么？），但是上下文切换更大的消耗不是切换本身，而是切换会引起大量的cache miss。你明明weibo跑的很爽，现在切过去微信，那么CPU的cache是不太容易命中微信的。

操作系统中估算”上下文切换”对吞吐能力影响时，不是计算上下文切换本身，而是在CPU 高速cache中的miss。一旦从一个进程切到另一个进程，会造成比较多的cache miss，从而影响吞吐能力。

在内核编译的时候，Kernel Features —> Preemption Model选项实际上可以让我们编译内核的时候，是倾向于支持吞吐，还是支持响应

preemption model：选择内核的抢占模型，影响调度算法

1. No Forced Preemption （Server）： 不强制抢占，更在意吞吐，支撑比较大的连接等。
2. Voluntary kernel preemption (Desktop)： 内核不能抢占。
3. Preemtible Kernel（low-latency desktop）： 内核都可以抢占，更在意响应，滑动触摸屏等操作需要立刻响应。

I/O消耗型 vs. CPU消耗型

• IO bound： CPU利用率低，进程的运行效率主要受限于I/O速度；
• tips: IO 消耗型对拿到CPU(延迟)比较敏感，应该被优先调度。一般需要CPU的响应速度快，即优先级要求比较高。
• CPU bound： 多数时间花在CPU上面（做运算）；

调度算法： 策略 + 优先级

早期2.6调度器：优先级数组 和 Bitmaps

• 0～ 139： 在内核空间， 把整个Linux优先级划分为0～139，数字越小，优先级越高。用户空间设置时，是反过来的。
• 某个优先级有TASK_RUNNING进程，响应bit设置1。
• 调度第一个bitmap设置为1的进程

SCHED_FIFO、SCHED_RR

实时（RT）进程调度策略： 0～99采用的RT，100～139是非RT的。

• SCHED_FIFO： 不同优先级按照优先级高的先跑到睡眠，优先级低的再跑；同等优先级先进先出。
• SCHED_RR：不同优先级按照优先级高的先跑到睡眠，优先级低的再跑；同等优先级轮转。

当所有的SCHED_FIFO和SCHED_RR都运行至睡眠态，就开始运行 100～139之间的 普通task_struct。这些进程讲究 nice，

SCHED_NORMAL

非实时进程的调度和动态优先级：

早期内核2.6的调度器，100对应nice值为 -20，139对应nice值为19。对于普通进程，优先级高不会形成对优先级低的绝对优势，并不会阻塞优先级低的进程拿到时间片。
普通进程在不同优先级之间进行轮转，nice值越高，优先级越低。此时优先级的具体作用是：

1. 时间片。优先级高的进程可以得到更多时间片。
2. 抢占。从睡眠状态到醒来，可以优先去抢占优先级低的进程。

Linux根据睡眠情况，动态奖励和惩罚。 越睡，优先级越高。想让CPU消耗型进程和IO消耗型进程竞争时，IO消耗型的进程可以竞争过CPU消耗型。

rt的门限

Linux内核在period的时间里RT最多只能跑runtime的时间。
在参数 /proc/sys/kernel/sched_rt_period_us 和 /proc/sys/kernel/sched_rt_runtime_us 中设置。单位：微秒。

CFS 完全公平调度

后期，Linux对普通进程调度，提供了 完全公平调度算法，每次都会调vruntime最小的进程调度。

红黑树，左边节点小于右边节点的值，运行到目前为止 （vruntime最小）的进程，同时考虑了CPU/IO和nice。

vruntime: virtual runtime，＝ pruntime/weight 权重* 系数。

随着时间运行，分子pruntime变大，vruntime也就变大，优先级变低。喜欢睡眠、IO消耗型的进程，分子小。nice值低的，分母大。但是RT的进程，优先级高于所有普通的进程。

红黑树实现的CFS，用分子pruntime来照顾 睡眠情况，用分母来照顾nice值。

当进程里fork了多个线程，每个线程的 调度策略都可以不同，优先级可以不同。原因显然。

酷客网相关文章：

• linux内核fork vfork
• linux内核进程管理
• Linux内核IO与网络模型
• Linux内核锁