江苏龙网

  1. 首页 > 资讯 > 科技 > >

「」Linux 是如何调度进程的？

通过上文《Linux进程在内核眼中是什么样子的？》 ， 可以理解内核关于进程线程的所有管理都是通过一个结构体 —— task_struct 。《Linux 进程线程是如何创建的？》也让我们知道了用户态下进程线程是如何创建的 ， 不同的创建方式又有哪些优劣 。本文就看下内核态是如何对 task 进行调度的 。
调度的发展历史
「」Linux 是如何调度进程的？
文章图片

文章图片

O(n)算法虽然历史有点悠久 ， 但很有必要研究 ， 是后续O(1)等算法理解的基础 。由于O(n)不是本文重点 ， 建议先去网上了解相关知识点 。
O(1) 调度器:
O(1) 调度器中引入了per-CPU runqueue的概念 。系统中所有的可运行状态的进程首先经过负载均衡模块挂入各个CPU的runqueue ， 每隔 200ms ， 处理器都会检查 CPU 的负载是否不均衡 ， 如果不均衡 ， 处理器就会在 CPU 之间进行一次任务均衡操作 。然后由主调度器和tick调度器驱动该CPU上的调度行为 。每一个优先级的进程被挂入不同链表中 。
「」Linux 是如何调度进程的？
文章图片

文章图片

上图说明了 task 与负载均衡和 runqueue 以及对应调度器之间的关系 。每个 runqueue 里又会分为active和expired队列 ， 每个队列中挂载着140个优先级不同的 task。关于调度器在 runqueue 里的算法实现我们看下面一张图：
「」Linux 是如何调度进程的？
文章图片

文章图片

来自网络
可以看出2.6 kernel 里有 140 种优先级 ， 所以我们就用长度为 140 的 array 去记录优先级 。每个优先级下面用一个 FIFO queue 管理这个优先级下的 process 。
那么 ， 我们怎么找到当前最高优先级下面的可执行的 process 呢？如果从 0 开始一直遍历下去 ， 算法虽然不是 O(N) ， 但是是跟优先级多少相关的 O(M) ， 也不能算作 O(1) 。在 2.6 scheduler 里 ， 采用 bitarray 。它为每种优先级分配一个 bit ， 如果这个优先级队列下面有 process ， 那么就对相应的 bit 染色 ， 置为 1 ， 否则置为 0 。问题就简化成寻找一个 bitarray 里面最高位是 1 的 bit（left-most bit） ， 这基本上是一条 CPU 指令的事（fls）
大致的思路齐备 ， 我们来整理下步骤：
在 active bitarray 里 ， 寻找 left-most bit 的位置 x 。
在 active priority array（APA）中 ， 找到对应队列 APA[x] 。
从 APA[x] 中 dequeue 一个 process ， dequeue 后 ， 如果 APA[x] 的 queue 为空 ， 那么将 active bitarray 里第 x bit置为 0 。
【「」Linux 是如何调度进程的？】对于当前执行完的 process ， 重新计算其 priority ， 然后 enqueue 到 expired priority array（EPA）相应的队里 EPA[priority] 。
如果 priority 在 expired bitarray 里对应的 bit 为 0 ， 将其置 1 。
如果 active bitarray 全为零 ， 将 active bitarray 和 expired bitarray 交换一下 。
CFS 调度器:
虚拟时间：
比如 ， 调度周期是12ms ， 2个相同优先级的进程A和B ， 那么每个进程的运行时间各为6ms 。倘若进程A,B的优先级nice分别为0和1 ， 那么权重分别是1024和820 。它们的关系如下：
权重 = 1024 / 1.25nice(次方)
那么进程A获取的运行时间是12x1024/(1024+820)=6.66ms ， 进程B获取的运行时间是12x820/(1024+820)=5.34ms 。进程A的cpu使用比例是6.66/10=66.6% ， 进程B的cpu使用比例是5.34/10=53.4% 。这里我们看到2个进程的执行时间分别是6.66ms和5.34ms ， 是不一样的 。但是CFS是想让每个进程完全公平调度 ， 这里就引入一个概念——虚拟时间 ， CFS也是通过虚拟时间相等来保证调度公平的 。虚拟时间vriture_runtime和实际时间wall time转换公式如下：


推荐阅读


上一篇：『5G』一款主攻游戏的手机，这样的配置，简直不要太香！

下一篇：[]荣耀30提前确定，轻薄机身＋双开孔＋麒麟985，性价比胜过华为P40