Linux进程优先级与调度解析

前言

之前我们简单介绍了Linux中系统的几种状态，这篇文章我们来对进程的优先级、进程调度做简要的介绍。

优先级

概念

之前我们了解的权限解决的是"能不能"的问题，而优先级解决的的是"在能的基础上先后的问题"。
优先级是进程在已经能得到某种资源的前提下，决定进程获得某种资源的先后顺序。
为什么要有优先级呢？这是因为操作系统的资源是有限的，当资源不足时，需要合理分配资源，此时，就需要设置优先级。

PRI与NI

查看进程优先级可使用指令**“ps -l”**，如下所示：

其中有几个重要信息，如下：

UID：代表执行者的身份
PRI：代表这个进场可被执行的优先级，即父进程的代号
NI：代表这个进程的nice值

其中PRI与NI为进程优先级的相关信息，其实它们就是task_struct两个整型变量。
PRI是进程的优先级，也就是进程被CPU执行的先后顺序，PRI越小的进程优先级越高。
NI是nice值，其表示进程可被执行的优先级的修正数值，PRI越小越快被执行，当加入nice
值后，将会使得PRI变为：PRI(new) = PRI(old) + nice，其中PRI(old)默认为80。
修改进程优先级，可以先输入top指令，然后输入r，输入要改变优先级的进程pid，再根据提示输入对应数据，这里输入的为10，如下所示：

所以，更改优先级，其实改的是进程的NI值。nice的取值范围为[-20 , 19]，那么优先级的取值范围为[60 , 99]，当nice值为负值的时候，该程序会将优先级值变小，即优先级会变高，则其越快被执行，设置的nice值必须在规定范围内，若超过规定范围，会取区间端点的值。但是，不能频率过高地更改优先级，否则会被操作系统阻拦。
从上可以看出，进程的优先级是有限的，这是由于Linux系统为分时操作系统，系统会为每个进程分配时间片，同时会以相对公平公正的调度策略，较为均衡地让不同的进程都能在一段时间内，都能得到CPU资源，所以不能过度改变优先级，否则会长时间使某一进程长时间占用CPU，因此要将进程的优先级控制在一定范围内。

相关概念

竞争性

系统进程数目众多，而CPU资源只有少量，甚至1个，所以进程之间是具有竞争属性的。为
了高效完成任务，更合理竞争相关资源，便具有了优先级。

独立性

多进程运行，需要独享各种资源，多进程运行期间互不干扰。这是因为每一个进程都有独立的内核数据结构和进程自己的代码和数据，这是进程具有独立性的原因。

并行

多个进程在多个CPU下分别，同进进行运行，这称之为并行。

并发

多个进程在⼀个CPU下采用进程切换的方式，在⼀段时间之内，让多个进程都得以推进，称之为并发。

进程切换

进程切换其实际含义是任务切换,或者CPU寄存器切换。当多任务内核决定运行另外的任务时,它保存正在运行的进程的临时数据，也就是上下文数据，并开始下一个任务的运行。如下所示：

寄存器是共享的，但是寄存器里面的数据，本质是进程私有的。

调度算法

Linux内核里面的链表结构

在结构体内部，知道对象某一成员的地址后，就可以算出该成员地址相对于起始地址的偏移量，计算方式如下：

offsetof(结构体类型, 成员名) = (结构体类型)&(((结构体类型 *)0)->成员名)

知道偏移量后，进一步可以算出结构体对象的地址：

结构体地址 = (结构体类型*)((char*)成员地址 - offsetof(结构体类型, 成员名))

在Linux系统中，链表结构如下：

进程是通过链表组织起来的，只不过与之前链表不同的是，这里的链表中的下一个指针不指向下一个结构体的首地址，而是指向下一个结构体中的Node成员的首地址，得到结构体内其中一个变量的起始地址，就可以获得结构体的地址以及其它变量的地址。
Linux系统这样设计链表结构，是为了增加对链式管理的扩展性。当要对新的设备进行管理时，可以在结构体内相关设备的属性，使得代码只需要维护一份。
在task_struct中，会维护一个成员，使得该进程可以放在全局的双链表中，也会维护另外一个成员，可以使得该进程在运行队列中。因此，一个进程，既可以属于全局的，也可以属于某一队列的。

调度策略

Linux系统中，每一个CPU都有一个对应的运行队列，如下所示：

其中，该队列有一个成员变量queue[140]，其中0-99对应的位置为实时优先级，这里不做讨论，100-139对应的位置为普通优先级，而优先级的范围为[60, 99]，系统会将进程优先级映射到[100, 139]区间，因此，优先级数字，本质是数组下标，数组中的每一个都会存储一个先进先出的队列，队列中存储着对应优先级的进程task_struct，选择进程时，先根据优先级选择对应的队列，然后再根据先进先出的规则对优先级进行调度。
因此，根据优先级选择进程的时候，本质是一个hash计算的过程，一旦确定队列，剩下的就是根据FIFO规则进行调度。先选择一个不为空的队列，再选择一个最先到达的进程。
bitmap[5]存储的时对应的位图，该成员用来表示某一个队列是否为空。
nr_active用来表示当前队列中进程的个数，若大于0，再查bitmap找到不为空的队列。

active指针和expired指针

若持续有优先级较高的进程到达，低优先级的进程就会得不到调度，这种现象称为饥饿现象。在Linux系统中，为了解决该问题，系统内定义了一个数组 struct prio_array_t array[2];其中，struct prio_array_t结构如下：

structprio_array_t{nr_active,bitmap[5],queue[140]};

数组中两个元素对应不同的哈希表，同时有两个指针active指针和expired指针，分别指向活跃哈希表(也称活跃140队列)和过期哈希表(也称过期140队列)，CPU选择进程时，只会查看活跃队列里的进程，当进程的时间片内后，将进程放入过期队列中，因此，活跃队列中的进程会越来越少，当活跃队列中的进程数量为0时，只需要swap(&active, &expired)，即交换两个指针，按照上面的过程继续调度即可。当新进程来临时，将对应进程放入过期队列。当正在调度进程优先级发生变化时，先按照原来的优先级进行调度，进程时间片结束后，再通过nice值修改优先级，再放入过期队列中即可。通过以上措施，即可解决操作系统中的饥饿问题。