Linux·进程概念(下)

1. 进程优先级

优先级就是获得某种资源的先后顺序，因为CPU资源是有限的，因此各个进程之间要去争取CPU的资源。

那么针对Linux操作系统下的PCB中，也就是task_struct结构体中，使用了int类型的变量记录了每个进程的优先级属性，其中优先级数字越小，代表该进程优先级越高。

我先随便启动一个进程，来看看优先级

我们打开一个进程，然后用另一个终端输入指令 ps -al 就可以。

我们只关注PRI和NI的数值。其中 PRI(priority) 代表Linux进程的最终优先级，NI(nice) 是优先级的nice数据，或者说优先级的修正数据。

nice在这里可以翻译成 "细微的"。把优先级设计成两个参数一起操控的原因是为了防止因为一些优先级的问题导致进程运行问题，比如如果一个程序的进程正在运行但是我们一下子把PRI调低了，那这个进程还要不要执行下去。因此在修改进程优先级的时候，可以现在nice值上修改，等到操作系统更新优先级的时候就统一把优先级从新设置了。

ps：这里我们可以看到一个UID的值，这是user id的意思，表示目前是哪个用户在进行这个进程，就像一个学生的学号一样。进程也是通过这个值来判断一个用户对某文件是否有读写权限的。

1.1 修改优先级

修改优先级在Linux中并不多用，而且不建议修改进程优先级。

nice值的取值是 [-20, 19] 一共40个值，每次调整都是在PRI为80的基础上进行加减，而不是以原优先级为基础进行调整。也就是说调整优先级的操作更类似于是在重置并修改。

我们下面用 top(Linux下的任务管理器) 来调整一下优先级

首先随便启动一个进程，然后在另一台终端上输入top命令，再在top中敲 r ，此时可以看到pid to renie的提示，然后我们就可以输入进程id，再修改nice值了。

修改的时候直接输入新nice值

】

然后我们退出top查看一下进程优先级，果然是被改变了。如果在改优先级的时候发现修改请求被拒绝了，那就是权限不够，直接 sudo top 提权打开任务管理器就能改优先级了。

之所以这个nice值只能在一个可控范围内调整就是为了所有进程尽量均衡的调用，这也是分时操作系统的原则。

2. 进程切换

每一个进程都有对应的时间片，时间片跑完了就要切换进程，这个就是进程的调度轮转。那时间片到了有可能这个进程还没有跑完，那如何让一个进程可以在任何地方重新调度切换就是关键。

简单来讲，就是在一个进程将要结束自己的这一时间片时，会将自己的运行数据暂时存储起来带走，等重新轮转到自己的时候，再将运行数据给CPU，继续之前的结果计算。

在CPU中有很多寄存器，例如ebp、esp、eax、ebx等等。本次我们只关注 eip(pc指针) 和 ir

ir 寄存器，也叫指令寄存器，其中保存的是正在执行的指令

eip 也叫pc指针，其中存放的是当前正在执行的指令的下一条指令，若有call这种函数调用，其中也会对应记录。

CPU内部的寄存器记录的是进程正在执行时的瞬时状态信息数据，我们将这个数据称为上下文数据。

那么进程切换的核心就是进程上下文数据的保存和恢复。

当一个进程要开始进入CPU计算了，首先把main函数入口处的地址放到pc指针处，然后在ir寄存器加载第一条命令，CPU控制器将这条命令拿去分析，有需要时交给运算器去计算。当这段进程的时间片跑完后，会将此时该进程在CPU中运算所留下来的所有痕迹拿出去存起来，痕迹比如ebp、esp中存的数据，ir、eip中运行到哪里的记录。这个存储的地方就是PCB中，以 tss_struct(任务状态段) 一种结构体存在，等重新轮转到这段进程的时候就把任务状态段中的数据重新加载到CPU的对应寄存器中就可以接着上次运行继续了。

3. Linux中的调度算法

我们之前轮调进程的时候都是在一个运行队列中，按顺序从头到尾轮一个遍，这种调度算法虽然简单，但是完全表现不出进程优先级的效果，因此我们下面浅谈一下Linux内核中写的调度算法时什么样的。

Linux中的调度算法是基于一种类似哈希表结构实现的。

首先，Lunix的哈希表或者说运行队列中只有140个元素，其中 0到99 前100个元素位置是留给实时进程的，100到139 后40个元素是给分时进程的，也就是说我们只能通过优先级控制后40个元素的位置。

其对应方案，也就是哈希函数为 i = pri - 60 + 100 真实进程优先级减60加100，真实进程优先级因为有nice值的限制，只能以80为基础在nice值 [-20, 19] 的范围限制下修改，也就是说真实进程优先级的范围是 [60, 99] ，这个范围经过哈希函数的映射后正好就是 [100, 139]

之后不同优先级的进程就可以开散列式的打散到各个队列当中，相同优先级的进程就可以如哈希桶一样挂到一起。如此利用哈希表结构完成进程在O(1)时间复杂度内的入运行队列。

然而在实际的进程控制操作中可能会遇到3种情况：1. 进程正常退出 2. 进程跑完时间片 3. 新插入进程。

进程正常退出就是走Z状态再走X状态，父进程释放其资源完成退出。但是到插入进程的话会有一点问题，如果有人一直恶意、频繁的插入优先级非常高的新进程，就会导致操作系统一直在执行新进程，而永远没有机会执行其他优先级较低的进程，这种情况下那些一直执行不到的进程就被称为饥饿进程。

那么为了避免饥饿进程的发生，Linux调度算法种引入了一个活跃进程和过期进程的处理方案，正在进行的进程哈希表被称为活跃进程的哈希表，新插入的进程和跑完时间片的进程都会被放入过期进程的哈希表中，最后活跃进程的哈希表完全都跑完了，也就是说活跃进程的哈希表为空后，交换活跃进程与过期进程的哈希表，如此循环。也就是说Linux调度算法中用两个哈希表作为基础，解决了饥饿进程的问题。

但是两个哈希表仅仅是基础，它们分别又被外面包了一层结构体，两个结构体组成了一个2元素的数组用来集中控制，最后数组外面又包了一层结构体，最后这一层结构体才被叫做运行队列runqueue

刚才说的包来包去的很复杂，我们照着上图捋一遍。

首先存放着进程PCB的哈希表被包在结构体queue中，同时在这个结构体中有表示哈希表一共存放多少进程的个数的nr_active变量，位图bitmap[5]，这是一个有5个int元素的数组，作用是帮助在O(1)时间复杂度之内找到一个有效的哈希桶，具体怎么操作的我们后面详谈。

之后这个两个queue结构体被封装进一个两元素的数组，便于统一管理。

最后数组、活跃进程指针、过期进程指针，被封装到运行队列结构体中。两个指针分别指向数组的两个元素，这两个元素中就是活跃进程的哈希表和过期进程的哈希表，此时完成逻辑闭环。

位图bitmap[5]是利用比特位标识哈希表中某个位置有没有哈希桶，5个int一共40个字节，160个bit位，后20个比特位没有意义，不看，只看前140个bit位。第几号比特位为1，表示哈希表中第几位有哈希桶，这个哈希桶不一定只有一共，可能这个位置坠了一串哈希桶，就说明这个位置有一串优先级一样的进程。

在寻找有效哈希桶的时候可以先看bitmap5个数组元素的值，如果5个元素都为0，说明现在没有进程在运行状态。如果不为0，就接用 n&(n-1) 的思路快速找到第一个为1的比特位，大概操作就是用 n&(n-1)的值按位异或^n，就可以直接暴露出第一个为1的比特位，分析这个值，可以得到第几号比特位为1。

n&(n-1)的思路在下面这个连接中

C语言·操作符详解-CSDN博客

最终找到有效哈希桶，如果是一串哈希桶，就从第一个开始运算并头删，直到这组哈系统全部调度完毕。如此可以在O(1)时间复杂度内利用位图完成有效哈希桶搜索。

如此O(1)级别的进程哈希桶插入，O(1)级别的哈希桶搜索，最成就为Linux的O(1)级别进程调度算法。

4. Linux中的数据结构

我们之前在学习数据结构的时候，比如链表，一共节点中既要存贮数据(属性字段)，又要有next、prev指针(连接字段)，但是在Linux源代码中对于数据结构的处理是只有连接字段，没有属性字段的。

就是说只提供链条，而我们要把链条手动绑在各个结构体节点上，我们以双向链表举例子。

在需要由数据结构链接起来的结构体节点之间用数据结构的链条绑定起来，而不是直接把节点绑定起来。

这么做的意义是可以把同一种结构体节点同时用不同的数据结构方案绑定起来，而不用写多份节点形式来适应不同的绑定方案。

因为绑定的是结构体的成员变量，因此如何通过成员变量找到改成员所属的结构体就十分重要。解决方案就是计算该成员的偏移量，通过 所属结构体地址 = 该成员地址 - 偏移量 的公式可以计算出。C语言库中提供了一个宏来帮助计算偏移量 offsetof (type,member); <stddef.h>

至于偏移量和结构体内存分配方案是什么可以转到：C语言·自定义类型：结构体-CSDN博客

如果想要自己计算偏移量，可以参考这个思路