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

• UID : 代表执行者的身份

• PID : 代表这个进程的代号

• PPID ：代表这个进程是由哪个进程发展衍生而来的，亦即父进程的代号

• PRI ：代表这个进程可被执行的优先级，其值越小越早被执行

• NI ：代表这个进程的nice值

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

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

修改优先级

输入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，以此类推。于是我们可以这么写