【Linux】进程调度 | 进程切换上下文数据

🪐🪐🪐欢迎来到程序员餐厅💫💫💫

      **主厨：邪王真眼**

主厨的主页：Chef‘s blog

所属专栏：青果大战linux

总有光环在陨落，总有新星在闪烁

小感慨：

ddl是这样的，老师只要布置作业就好了，我们学生要考虑的就多了

进程优先级

基本概念

• cpu资源分配的先后顺序就是进程的优先级
• 优先级高的进程优先被CPU执行。优先级低的进程会较后地被执行，合理的配置不同进程的优先级可以更好的满足用户的需求

查看进程优先级

在linux或者unix系统中，用ps –l命令则会输出进程的相关信息，如下

• UID : 代表执行者的身份
• PID : 代表这个进程的代号
• PPID ：代表这个进程是由哪个进程发展衍生而来的，亦即父进程的代号
• PRI ：代表这个进程可被执行的优先级，其值越小越早被执行
• NI ：代表这个进程的nice值

在未修改状态下，PRI是一个进程的默认优先级大小，不同的进程初始PRI可能一样可能不一样，nice是对该默认值进行的修改大小，nice的范围是[-20,19]，相当于优先级的大小范围是[60,99]共计40个种类。

为什么Linux会对nice的大小进行限制呢？这其实是怕用户乱设置优先级，比如直接来个10000或者-10000，这样就会难以管理，这点在后面的运行队列结构分析会讨论。

修改优先级

我们现在启动了一个进程（死循环），他的PID是8947

输入top指令进入该界面

输入r表示开始修改nice，接着他会弹出一条命令行，我们接着输入我们要修改的进程的PID

输入我们想要把nice修改成多少即可

最后输入q退出该界面，再输入ps -al查看进程，就会发现我们NI值变成了15，PRI值变成了95

但是请注意，我们的PRI结果=PRI的初始值+NI，而不是上一次的PRI+NI

我们现在试试把NI改为-15，就会发现他的值是65（初始值80-15），而不是80（上一次的值95-15）

进程调度

进程调度是指OS在管理进程的执行时所采取的策略 

优先级管理

我们之前提到过，OS对进程的管理就是”先描述，再组织“，先把进程描述为task_struct,接着再维护称链表等数据结构。

接着我们思考两点

• CPU是极其注重效率的，即时间复杂度要尽可能的去压缩，
• CPU运行进程依靠的不是他的先来后到，而是优先级（其实也不止，但先考虑这么多）。

根据第一点，我们就想到要队列这种数据结构维护运行队列，可以达到O（1）的时间复杂度

根据第二点，我们想到堆的数据结构，达到考虑优先级的目的。

合二为一，怎么办？

于是伟大的哈希出现了，我们采用开散列（哈希桶）的方法，我们可以开一个40个元素的vector，里面放PCB指针。

假如有个这样在有新的进程要加入运行队列，他的优先级是60，我们就可以把它放到第一个元素所维护的链表中。

当CPU也只需要从头到尾遍历哈希表，即可实现按照优先级运行进程。

但是，假如只有一张哈希表，当优先级高的进程被弹出后（时间片限制），他还要重新接入哈希表（因为还没跑完），还会原来的那个位置，这就会导致后面的进程一直等待。所以我们发现一张哈希不够，要两张，一张放置运行队列，另一张放置从运行队列弹出但是还没运行完需要接着跑的进程。当运行队列跑完了，就直接交换两个队列的指针（O（1）），于是CPU就可以继续运行进程了。

代码演示

我们先写了一个结构体Queue，他的成员对象有三个

当num为0说明该队列的进程全被运行了一遍，可以更换哈希表了

数组开了140个是因为OS会把前100个用于实时进程，关于实时进程我们目前不用考虑当不存在就ok。

接着我们写了一个结构体，它就是我们一直说的运行队列

active指向当前CPU要去运行的进程所组成的Queue对象

expired指向从运行队列弹出，要接着排队的进程所组成的Queue对象

现在我们假设CPU把它上面的一个进程A跑完了，于是他要去找下一个进程B，有个很简单的方法，他直接对这个140的数组遍历，遇到的第一个task_struct就是所存放的进程中优先级最高的进程。

于是直接把A和B交换，然后把A存放到expired里即可，这样的时间复杂度是O（1），但他最坏要循环140次，

Linux社区里的大佬并不满意这种效率，于是位图闪亮登场，一共是140个元素，我们可以用5个int的比特位，来存储各个优先级对应位置的状态，如果第三个位置有进程插入，那第三个比特位就是1，否则是0，以此类推。于是我们可以这么写

加入从0开始的32个比特位都为0，则bitmap[0]=0,于是我们可以直接排查掉32个比特位，假如发现bitmap[i] 不为0，接着就通过lowbite的方法直接找到是最早哪个bite为不为0（自低位向高位查找）

于是时间复杂度直接提高到遍历个位数次即可。这就是linuxO（1）调度算法

当然，具体要更加复杂，因为我们的CPU是分时CPU，所以对于那些明明在运行队列呆了很久运行时间却很短的进程，OS会提高他的优先级，反之亦然，诸如此类的操作还有别的，但笔者能力有限还不了解。

当OS发现该num==0，即active所维护的哈希表空了，就让swap一下active指向arr[1],让expired指向arr[0],如此反复交换，就实现了OS的优先级管理

swap（active，expired）；

PCB的双链表结构

从最开始接触进程开始我们就说了，OS会通过指针把PCB链接起来进行管理，但是它并不像我们学的简单的双链表结构如下

我们并没有把连接字段直接写进去，而是这样的：

因为我们一个PCB可能既在一个键盘的等待队列，也在一个鼠标的等待队列，或是别的队列，如果是在建立一个PCB显然是有新的内存开销的，于是当一个进程需要带着多个队列中时，只需要向他的PCB中写入新的节点字段即可

但随之而来一个问题，我们得到这个节点字段的指针后如何访问她所在结构体PCB的其他成员呢？

如果得到的是这个进程PCB的指针那可以直接用”->“进行访问，但我们得到的不是该PCB的地址，而是他内部的某个成员的地址。这里就要用c语言中offset宏了。他的原理很简单。

结合这个代码演示大家就知道成员变量的地址和该结构体的地址是有关系的，我们只要求出他们之间的偏移量即可。这并不困难，使用下面的代码即可。

于是我们就可以通过结构体的某个成员找到该结构体的地址了。

进程切换

我们知道了进程是如何进行优先级管理的了，但是现在我们去把目光放到单独的一次进程切换中。

1. 进程A时间片到了，被移除，换进程B上来
2. A等待一段时间后再次被调度

此时A进程当让应该接着被移除前的进度继续运行，可是，它怎么直到上次跑到哪了？

显然，这里出现了数据的读取和存储。

进程在进行切换时会出现大量的临时数据需要保存，我们讲这些数据称之为进程的上下文数据。

首先，这些数据不可能存在CPU，因为CPU太小了（几十KB），也不会存在磁盘，因为进程本身就是掉电就丢失，那在掉电后你在磁盘保存下来他的上下文数据也没有意义了，于是他的数据只会呆在内存，而且应该是和该进程紧密相关的一片空间，没错，就是task_struct!

我们可以抽出两个寄存器细说一下

程序一开始，PC寄存器会把程序的第一条指令（main函数）地址读进去，接着ir会根据该地址找到指令内容，并将其读进去，然后交给处理器处理指令，与此同时PC寄存器会更新地址，具体为新地址=原地址+该地址对应指令长度，于是ir再次获取新指令，循环往复。

当进程第二次被加载进CPU时，ir就会读取task_struct中存储的上一次运行的最后一条指令的地址，而不是该程序的第一条指令地址，于是程序就可以继续跑了。

思维导图