【Linux仓库】进程优先级及进程调度【进程·肆】

🌟 各位看官好，我是！

🌍 Linux == Linux is not Unix ！

🚀 今天来学习Linux的进程优先级及进程调度，从底层剖析OS是如何进行进程调度的。

👍 如果觉得这篇文章有帮助，欢迎您一键三连，分享给更多人哦！

目录

进程优先级

查看系统进程

PRI和NI

竞争、独立、并行、并发

进程切换

进程O(1)调度队列

活动队列 

过期队列 

active指针和expired指针

源码设计 

进程优先级

什么是优先级？

• 指定一个进程获取某种资源的先后顺序
• 本质是进程获取cpu资源的优先顺序

为什么要有优先级？

资源少，进程多，才需要竞争。

那Linux是如何保证优先级的呢？请阅下文。

查看系统进程

 PS工具不仅能获得一个进程的PID和PPID，还能获得一个进程的nice值、PRI等，接下来由小拜年带着一一介绍。

• UID : 用户的标示符

• PID : 代表这个进程的代号
• PPID ：代表这个进程是由哪个进程发展衍⽣⽽来的，亦即⽗进程的代号
• PRI ：代表这个进程可被执⾏的优先级，其值越⼩越早被执⾏
• NI ：代表这个进程的nice值

PRI和NI

• PRI也还是⽐较好理解的，即进程的优先级，或者通俗点说就是程序被CPU执⾏的先后顺序，此值越⼩进程的优先级别越⾼。
• 那NI呢?就是我们所要说的nice值了，其表示进程可被执⾏的优先级的修正数值。
• PRI值越⼩越快被执⾏，那么加⼊nice值后，将会使得PRI变为：PRI(new)=PRI(old)+nice
• nice其取值范围是-20⾄19，⼀共40个级别。
• Linux的进程优先级本身范围是【60，99】，一共40个级别。

证明确实是分为40个级别：

⽤top命令更改已存在进程的nice： 进⼊top后按“r”‒>输⼊进程PID‒>输⼊nice值

简单而言，PRI越低代表进程优先级越高，而优先级调整是通过NICE值来调整，那PRI(old)呢？

PRI(old)是固定80，这是一种覆盖式设置，因此只需要调整NI来改变进程优先级。

这里抛出三个问题：

1. nice值为什么要有范围？
2. 为什么nice取值是从-20到19这40个级别呢？
3. 如果一个NICE值足够的大，是否会让该进程得不到调度呢？如果进程因为长时间不被调整，就会造成饥饿问题。（下面讲）

问题1：我们所接触到的操作系统叫做分时操作系统，这种系统的特性是需要尽可能地保证公平公正，即每个进程都要被调度到。那它又是如何做到每个进程都被调度的呢？放在下面讲

问题2：与具体调度算法有关。

竞争、独立、并行、并发

• 竞争性: 系统进程数⽬众多，⽽CPU资源只有少量，甚⾄1个，所以进程之间是具有竞争属性的。为了⾼效完成任务，更合理竞争相关资源，便具有了优先级。
• 独⽴性: 多进程运⾏，需要独享各种资源，多进程运⾏期间互不⼲扰。
• 并行: 多个进程在多个CPU下分别，同时进⾏运⾏，这称之为并⾏。
• 并发: 多个进程在⼀个CPU下采⽤进程切换的⽅式，在⼀段时间之内，让多个进程都得以推进，称之为并发。

进程切换

CPU上下⽂切换：其实际含义是任务切换, 或者CPU寄存器切换。当多任务内核决定运⾏另外的任务时, 它保存正在运⾏任务的当前状态, 也就是CPU寄存器中的全部内容。这些内容被保存在任务⾃⼰的堆栈中, ⼊栈⼯作完成后就把下⼀个将要运⾏的任务的当前状况从该任务的栈中重新装⼊CPU寄存器, 并开始下⼀个任务的运⾏, 这⼀过程就是context switch。 

参考内核0.11代码：

时间片：当代计算机都是分时操作系统，每个进程都有它合适的时间⽚(其实就是⼀个计数 器)。 时间⽚到达，进程就被操作系统从CPU中剥离下来。

进程O(1)调度队列

那么，OS是如何进行进程调度的？

状态+优先级！！！

下图是Linux2.6内核中进程队列的数据结构。  

活动队列 

  一个CPU，有一个运行队列（可能一个电脑不只一个CPU，但我们目前只探讨一个CPU的情况）

• 时间片还没有结束的所有进程都按照优先级放在该队列
• nr_active: 总共有多少个运⾏状态的进程
• queue[140]: ⼀个元素就是⼀个进程队列，相同优先级的进程按照FIFO规则进⾏排队调度,所以，数组下标就是优先级！   （需要注意的是queue数组中的[0,99]不用管，而[100,139]是进程的位置，这不正好也是40个位置吗？？？前面所学的nice值也是40个级别，那么只要将PRI值[60,99]+40不正好能对上进程的位置了。）

那[0,99]用来做什么呢？

Linux 不仅仅在互联网中使用，在工业场景中也会被使用。
如：实时操作系统，Linux操作系统，支持实时操作系统的功能!![0,99]

OS调度进程，是如何选择进程的呢？从该结构中，选择⼀个最合适的进程，过程是怎么的呢？

1. 遍历queue数组时
2. 找到第⼀个⾮空队列，该队列必定为优先级最⾼的队列，因为下标位置靠前，说明PIR低，进程优先级高
3. 拿到选中队列的第⼀个进程，开始运⾏，调度完成！
4. 遍历queue[140]时间复杂度是常数！但还是太低效了！此时Linux开发者又大开脑洞，通过位图的方法来确定下标位置是否含有非空队列。这就是为什么设计出bitmap的原因。

 bitmap[5]:⼀共140个优先级，⼀共140个进程队列。如果bitmap的空间为4，则有4*32=128个下标。为了提⾼查找⾮空队列的效率，就可以⽤5 * 32 = 160个⽐特位表⽰队列是否为空，这样，便可以大大提⾼查找效率！（替换遍历操作，提高了效率，O（1）时间复杂度）

• 比特位位置:表示数组中第几个队列!
• 比特位内容:表明该队列是否为空!

过期队列 

如果调整某进程的nice值过大，此时它的PRI就会变大，导致进程优先级变低，就会插入到活跃队列靠后的位置。如果我再调整其他进程的nice值呢，让它们的优先级比该进程还高，此时操作系统一直都会执行优先级较高的进程，导致位置靠后的进程永远得不到调度。如果进程因为长时间不被调整，就会造成饥饿问题。我们的操作系统是一个分时操作系统，又该如何保证尽量公平公正地调度每一个进程呢？引入了过期队列。（设计者Ingo Molnar 和 Con Kolivas，不得不佩服是一个极为天才的设计）

• 过期队列和活动队列结构⼀模⼀样
• 过期队列上放置的进程，都是时间⽚耗尽的进程
• 当活动队列上的进程都被处理完毕之后，对过期队列的进程进⾏时间⽚重新计算

active指针和expired指针

• active指针永远指向活动队列
• expired指针永远指向过期队列
• 可是活动队列上的进程会越来越少，过期队列上的进程会越来越多，因为进程时间⽚到期时⼀直都存在的。
• 当活跃队列里的进程没了，我又该如何继续调度之前没执行完的进程呢？此时active和expired指针的作用就凸显出来了，我们只需要交换active指针和expired指针的内容，就相当于有具有了⼀批新的活动进程！（因为执行过的进程都在过期队列里啊）

源码设计 

  ​

​