【敬业奉献】何伟群：80后“法官姐姐”倾心少年审判

?? 各位看官好，我是！ ?? Linux == Linux is not Unix ！ ?? 今天来学习Linux的进程优先级及进程调度，从底层剖析OS是如何进行进程调度的。

进程优先级

什么是优先级？

• 指定一个进程获取某种资源的先后顺序
• 本质是进程获取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指针的内容，就相当于有具有了?批新的活动进程！（因为执行过的进程都在过期队列里啊）

源码设计