哈喽，我是子牙老师。今天咱们聊一个有趣的话题：算出Linux内核会调度哪个进程
比如你写了这样的代码
问一下自己这些问题：
这个代码会创建几个进程？
这些进程与调度器是如何关联的？
调度器会按照什么顺序来调度这些进程？
获得调度的进程能获得多少时间片？
公平调度算法CFS不公平体现在哪？
公平调度算法CFS是怎么解决不公平问题的？
好，开整~
Linux内核中有五种调度策略：停机调度、限期调度、实时调度、公平调度、空闲调度。本篇文章只讲与大家息息相关的公平调度，即CFS
其他调度策略，后面有空再分享。关注公众号【硬核子牙】，第一时间获取文章动态
Linux内核会使用多种数据结构将进程结构体task_struct串起来，以应对不同的场景使用需要。数据结构包括：红黑树、双向链表、哈希表。CFS调度算法中，是使用红黑树将task_struct串起来的
上面的代码，会创建8个进程，即Linux内核会创建8个task_struct，挂到CFS调度队列的红黑树上。如果从task_struct的视角来看，长这样
如果把视角往上拉，从CPU的视角来看，长这样
我来解释一下这张图
一、Linux内核为每个CPU核维护一个调度队列struct rq。如果CPU支持超线程技术，每个CPU核支持两个硬件线程，每个硬件线程对应一个struct rq
举例来说，我现在有一个CPU，是4核的，支持超线程技术，那么Linux内核就会创建8个struct rq实例。Linux内核中通过宏cpu_rq(cpu)就可以取到某个CPU对应的调度队列rq，通过传入当前CPU的ID，拿到当前CPU的调度队列rq，进而拿到cfs_rq
二、cfs_rq就是CFS调度器对应的数据结构，里面维护了一个红黑树，进程结构体task_struct就是挂在这颗红黑树上
三、进程与CFS调度器之间不是直接关联的，而是通过一个中间数据结构sched_entity。为什么不能直接关联呢？因为CFS调度器的调度单位不仅仅只是进程，还支持进程组调度，所以需要一个中间层
关于进程组调度，后面再写文章详谈。关注公众号【硬核子牙】，第一时间获取文章动态
四、task_struct中有个属性se，就是sched_entity，sched_entity中的属性run_node，就是挂在红黑树上的节点。cfs_rq中的属性tasks_timeline就是这颗红黑树
上面的图表达的就是CPU、CFS调度器、进程三者之间的关联关系。如果抽象成一个公式就是：
如果你想查看你创建的进程是使用的什么调度策略，可以这样查看
现在你已经知道CPU、CFS调度器、进程三者之间的关联关系了，你有没有想到这几个问题？
一、如果CPU有4个核，那在创建进程的时候，会把进程挂到哪个CPU核对应的运行队列rq中呢？
这个问题牵扯到CPU缓存、CPU亲和、NUMA架构、父进程等影响因素，后面写文章详谈。关注公众号【硬核子牙】，第一时间获取文章动态
二、如果把进程挂到红黑树上，要把这个进程挂在红黑树的哪个位置呢？
接着奏乐，接着舞~
Linux内核根据进程vruntime的大小，将其放在红黑树合适的位置上。CFS调度时，会选择vruntime最小的进程进行调度。所以我们写的代码，我们只要知道它们的vruntime值，就能算出来它们的调度顺序，及能够获得的CPU时间片
那vruntime是怎么算出来的呢？
函数__calc_delta头部的注释列出了具体的公式
这两个公式表达的是同一个意思，因为除法运算效率过低，所以后面都使用优化过后的公式，通过逆元和位移运算得出结果
将公式翻译成人话：vruntime = 进程运行时间 * 进程权重 / 系统默认进程权重。接下来我详细解释公式中的三者
接着舞~
进程运行时间，见名知意，这个进程运行了多长时间。运行时间肯定是结束时间 - 开始时间得出来的。那Linux内核，把哪个时间点作为开始时间呢？进程被选中的时候？还是切入进程开始运行的时候？又把哪个时间点作为结束时间呢？
猜没用，看代码才能找到答案
这个函数就是我们要的答案。Linux内核在这个函数中计算出进程运行了多长时间，代码842行位置。然后将进程的运行时间传入函数calc_delta_fair算出最新的vruntime值，累加到旧的vruntime上
计算进程的运行时间，以调用update_curr作为结束时间点。调用update_curr的地方有10个
计算进程的运行时间，开始的地方在哪呢？其实就是给curr->exec_start的地方在哪？
答案是在进程被选中的时候！你可能想问，那不是有误差吗？大家都有误差，就等于没有误差，懂？
前面看到一个进程的vruntime是累加上去的，那一个进程的初始vruntime是0吗？
如果是0，那就天下大乱了：进程张三说，都快轮到我了，你新创建的进程就能拿到vruntime=0，这对我公平吗？那Linux内核怎么解决的呢：新进程的vruntime = max(父进程的vruntime，当前运行队列中的最小vruntime)，摆证据
至此，关于进程的运行时间的全部，就讲完了
Linux内核中进程优先级与进程权重对应的表如图
这里的进程优先级nice，就是task_struct中的static_prio，取值范围-20 - 19，数值越小，优先级越高，权重越大。切记，真实的static_prio = 120 + task_struct.static_prio
上面数组中nice与weight的对应关系怎么算出来的呢？
举个例子
其实你通过公式去运算得到的结果，与数组sched_prio_to_weight中的值，有些地方会略有差异，是不是公司错了呢？不是，有的地方的值，是人为调整过的。为什么调整？大多数情况按照公式得到的结果比较理想，少数情况不理想，人为调整到理想的数值
为什么选1.25呢？为什么不是2或者3或者其他值呢？
感叹否？我反正把这个研究完，我就感叹：这些人的知识储备也太强大了吧！只有研究Linux内核，你才能意识到顶级码农，是什么样子的
文章大家都是从头看过来的，那有没有猜到系统默认进程权重是多少？猜不到？心太大了
看那个if判断，猜出来没？对！系统默认进程权重就是nice=0，weight=1024！
至此，计算vruntime相关的三个因素都解释完了
前面讲到计算进程的vruntime需要进程的运行时间，那一个进程究竟能拿到多少CPU时间片呢？
进程的时间片 = 调度周期 * 进程权重 / 运行队列中所有进程权重之和
先解释下几个名词
调度周期：在一个时间范围内，运行队列中的每个进程都能运行一次，这个时间范围，就是调度周期。如果运行队列中的进程数小于8，这个调度周期就是6ms。如果超过8，调度周期=任务数*调度最小粒度0.75ms。比如有调度队列中有10个任务，那调度就是就是7.5ms，相关代码如图
什么是最小调度粒度？因为进程来回切换是要做很多很多事情的，如果进程还没跑一会就切，那CPU时间全花在进程切换上了。所有定了一个最小值就是0.75ms。就是说一个进程获得调度，最少都要跑0.75ms才能切走
举个例子帮助大家理解：此时任务队列中有三个进程A、B、C，nice值分别是-10，0，10，那A、B、C分别能获得的时间片是多少呢？
进程A：6ms * 9548 / 9548 + 1024 + 110 = 5.363ms
进程B：6ms * 1024 / 9548 + 1024 + 110 = 0.575ms
进程C：6ms * 110 / 9548 + 1024 + 110 = 0.062ms
至此，关于vruntime的all，你已经完全理解了吧
如果用户张三运行了9个进程，用户李四运行了1个进程，进程的nice值相等，你猜会出现什么样的结果？是不是张三占了大便宜，一个人吃了90%的CPU时间。这就是CFS如果只以进程为调度单位而出现的不公平性
那如何解决呢？引入组调度。组调度有两套机制：一套是自动组调度，autogroup。还有一套是用户可配置组调度，cgroups。下篇文章讲
关注公众号【硬核子牙】，第一时间获取文章动态
本篇文章，我们讲了CPU、CFS调度器、进程三者之间的关系
又讲了vruntime的计算方法，并对其中的三要素进行了详细的讲解
后又延伸讲到某个进程能够得到的CPU时间片的运算方式
这就是CFS调度普通进程的全部。如果CFS只能调度普通进程，则会带来不公平，所以后来引入了CFS组调度，下篇文章分享
我是子牙老师，创业四年，做了多门全网唯一的底层硬核课程
关于Linux内核，已经做到第三期
如果你对Linux内核或其他课程感兴趣，可以咨询班主任，拿试看视频，了解清楚再报名
