C算法
Linux 进程优先级与调度机制详解
Linux 进程优先级由 PRI 和 NI 值决定，范围分别为 [60, 99] 和 [-20, 19]。通过 ps、top、nice 等命令可查看或调整优先级。内核采用 O(1) 调度算法，利用运行队列（runqueue）、活动队列（active）和过期队列（expired）实现高效进程调度。进程切换涉及保存和恢复硬件上下文数据。
Linux 进程优先级由 PRI 和 NI 值决定，范围分别为 [60, 99] 和 [-20, 19]。通过 ps、top、nice 等命令可查看或调整优先级。内核采用 O(1) 调度算法，利用运行队列（runqueue）、活动队列（active）和过期队列（expired）实现高效进程调度。进程切换涉及保存和恢复硬件上下文数据。
在了解完不同进程的状态后，我们知道了进程在做什么事情时应该处于什么状态，但进程的运行有没有先后顺序呢？如果有，系统如何决定谁先谁后？而且进程在切换时是如何进行的？
CPU 资源分配的先后顺序，即进程的优先级（priority）。
优先级产生的本质是目标资源的稀缺，导致需要用优先级确认先后顺序。电脑的 CPU 只有一两块，但进程有成百上千，因此必然存在优先级。
在操作系统内，优先级是 PCB 中的一种整型数字。值越低，优先级越高；反之优先级越低。大多数操作系统基于时间片的分时操作系统，每个进程分有自己的时间片。进程运行时并不一直占有 CPU，而是有一定的运行时间，时间到了需等待下一轮。这类系统通常考虑各进程之间的公平性，虽然有优先级差别，但不能过大。
优先级 VS 权限
优先级本质上是指得到资源的先后问题。权限本质是指是否能得到某种资源。
查看优先级常用 ps -la 指令。
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
int main() {
pid_t id = fork();
if (id == 0) {
// child
while (1) {
printf("我是一个子进程，pid: %d, ppid: %d\n", getpid(), getppid());
sleep(1);
}
} else {
// parent
int cnt = 5;
while (1) {
printf("我是一个父进程，pid: %d, ppid: %d\n", getpid(), getppid());
sleep(1);
}
}
return 0;
}
使用 ps -al | head -1 && ps -al | grep myprocess 打印头信息并筛选内容。
在 head 输出中有很多英文缩写，解释如下：
ls -ln（n 表示 num，显示数字）。我的用户 ID 为 1000。
在 Linux 系统中，访问任何资源都是进程访问，进程代表用户。
查看 head 时看到的 PRI 和 NI 说明如下：
修改优先级并非直接修改 PRI，而是通过修改 NI 间接修改 PRI。
进程真实的优先级 = PRI（默认） + NI
注： 不建议随意修改优先级，会影响 OS 调度平衡，一般也不改。
尝试修改进程优先级。
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
int main() {
while (1) {
printf("我是一个进程，pid: %d, ppid: %d\n", getpid(), getppid());
sleep(1);
}
return 0;
}
可以使用 top 命令进入后直接输入 r。
再输入进程 PID。
修改优先级，这里改为 10。
此时可以看到优先级 PRI 从 80 变到了 90，NI 就是 10。相当于把优先级调低了。
再来尝试把优先级更改为 -10。
可以看到，它的 PRI 并不是变成了 80，而是 70。这说明进程优先级永远是 PRI 的默认值（80）+ NI 的值，每次调整都是从 80 进行更改的。
试试优先级能不能变成负数，将 NI 值调为 -100。
可以看到不能变成负数，最小就是 60。
再看看 NI 值最大是多少，将 NI 值调为 100。
可以看到，NI 最大值就是 19。
所以 NI 值处在 [-20, 19]；Linux 的优先级范围 [60, 99]。
优先级范围如此狭小的原因主要是考虑到公平性。如果优先级设立不合理，会导致优先级低的进程长时间得不到 CPU 资源，进而导致进程饥饿。
调整优先级的方法还可以是 nice 命令或者 renice 命令。
一个进程占有 CPU，并不是把代码全部跑完后才停下来（除非代码十分短），每个进程 OS 都会给它分配一个叫做时间片的东西。进程只能在这个时间片区间内运行，如果时间到了，OS 就会把这个进程从 CPU 上拿下来，放回调度队列中，等到下一次轮到它后又重新分配一个时间片。这样就不会出现一个进程一直占有 CPU 的情况。
所以死循环进程不会打死 OS，不会一直占有 CPU。
CPU 在执行进程时就和 PCB 没什么关系了，它主要是访问 PCB 对应的代码和数据。CPU 不是把代码和数据一股脑全部塞入其中，而是一条一条地来调。同时为了让 CPU 能够运行代码和数据，CPU 中存在很多寄存器，例如 pc/EIP、ebp/esp、eax/ebx/ecx/edx、cs/ds/es/fs/gs 等。这些寄存器的功能各不相同，OS 在进程运行时，寄存器上会填入各种临时值。CPU 中存在一个 pc 指针，它里面会保存正在执行的指令的下一条指令的地址。
结论：
当进程 A 正在运行时，CPU 的寄存器里就会保存进程在运行期间所有的临时数据。当前进程在 CPU 内的所有进程内容被称为当前进程的硬件上下文数据。当进程运行期间时间片到了，进程就得剥离下来，但不能让进程 A 直接切走，而是要把在各种寄存器中的各种值也一块带走，也就是把数据拷贝出来。这时就能把进程剥离下来，放入 runqueue 结尾或者其他地方。再把进程 B 放到 CPU 中，进程 B 就将寄存器中的数据全部覆盖掉了，进程 B 就开始运行。进程 B 运行完了后剥离下来，假如又排到了进程 A，此时不是进程 A 直接开始运行，而是将曾经保存的历史上下文数据重新恢复到寄存器上，此时进程 A 就可以在历史的位置继续运行了。
所以进程切换本质就是保存和恢复当前数据的硬件上下文数据，即 CPU 内寄存器的内容。
既然进程剥离时要保存硬件上下文，那上下文保存到哪里了呢？
可以理解为保存到进程的 task_struct 中，但其实当代计算机要保存的数据已经非常大，它已经被单独独立出来了。每个 PCB 中都有一个 TSS（任务状态段），本质就是一个结构体，在这个结构体中放入我们的上下文，它能通过 PCB 找到。
全新的进程和已经调度过的进程该怎么区分呢？
其实就是在 PCB 中加一个标记位来区分的。
调度和切换共同构成了一个调度器，调度器的功能有两个：其一就是切换，其二就是选择进程（把当前进程保存起来后，再从系统中选择一个进程，最后把进程放上来）。
计算机中，一个 CPU 就有一个运行队列（两个 CPU 就两个运行队列），这个运行队列就叫 runqueue，不同的操作系统运行队列名可能不同。
在运行队列中有许多不同的变量，这里来解释部分。
queue[140]：
它的类型是 struct task_struct* queue[140]，它是一个结构体指针数组，它有 140 个的原因是因为 Linux 的优先级是 140 个。但是之前不是说 Linux 的优先级是 [60, 99] 40 个嘛？这里怎么就是 140 个了呢？
其实 Linux 的优先级就是 140 个，其中的 [0, 99] 100 个优先级我们称之为实时优先级，这个优先级我们不考虑。我们的操作系统分为两大类别：一个是分时操作系统（按照时间片进行公平调度），还有一种是实时操作系统。实时操作系统与分时不同的地方在于它如果来了一个优先级高的进程必须立即响应，不能等上一个进程时间到了才响应（和优先级相关），如果这个进程要处理就必须处理完才能处理下一个。实时操作系统一般在工业领域的使用会比较多，比如汽车等，如果出现要紧急刹车的情况，如果是分时操作系统就要等上一个进程时间到了才会刹车，那样就来不及了。我们不考虑实时操作系统，所以就只有 40 个优先级。如果进程优先级在 61，OS 就会把这个进程链接到 queue[101] 上，同理，OS 将进程都链接好后，之后的调度就是在 queue 上有数字低到数字高调度。所以 CPU 从宏观上由前往后的不同优先级遍历调度，由局部上是 FIFO 调度。所以说 queue 本质就是一个哈希表。
但是难道每一次都得去遍历一遍数组吗？有没有可以让调度器快速挑选一个进程的方法呢？
答案当然是有的，那就是 bitmap[5]：位图。它是 unsigned int 类型，有 32 个 bit 位，总共有 5 个，也就是 160 位，拿出其中的 140 位去标记 queue 的各个位置。如果对应 queue 上链有进程就标记为 1，如果没有就标记为 0。这样就实现了快速挑选进程。我们称为 Linux 真实调度算法：O(1) 调度算法。
但是如果只是这样，那当 OS 在 queue 队列中找到一个死循环进程后运行完了，那进程继续链入对应优先级后面，那不是得把优先级高的执行完毕才执行优先级低的吗？这样不就是进程饥饿吗？所以进程不单单只是如此。
为了防止上面的情况发生，我们在 runqueue 队列中又插入了一个和 queue 一模一样的队列。本质是在 runqueue 队列中塞入了一个数组（struct rqueue_elem prio_array[2]），记录了两个 rqueue_elem 的结构体，在这个结构体中塞入我们的 queue[140]、bitmap[5]、nr_active。其中一个是记录活跃进程的，还有一个是记录过期进程的。同时我们再定义两个指针，它们的类型 struct rqueue_elem*，一个叫做 active (struct rqueue_elem* active = &prio_array[0])，还有一个叫做 expired (struct rqueue_elem* expired = &prio_array[1])。
当进程准备运行时，OS 通过 active 找到对应的 queue 进行运行，等时间片到了以后，从 CPU 上剥离出来，进程不能再链入 active 对应的 queue 队列中，而是放到 expired 所指向的 queue 队列中。此时 active 指向的 queue 队列的进程越来越少，expired 队列指向的进程越来越多。当 active 队列的进程全部调完后，swap(&active, &expired)。如果在运行时来了新进程时，理论上我们会把进程放入 expired 指向的队列当中，也就是所谓的就绪队列。但是 Linux 系统是基于时间片轮转的，它支持进程抢占，所以说进程可以插队，就是将进程直接链入 active 指向的 queue 队列中。这也说明了为什么 PRI 要专门有个 NI，如果我们只有是更改 PRI，那该如何修改我们的进程，无论是把进程重新放到 active 或者 expired 中都不好，但是如果只是更改 PRI 的值却不换地方，那就会很奇怪，所以我们加了一个 NI 值，这样就可以在我们的进程运行时链入 expired 队列中时更改。
与活跃队列相对的，保存活跃进程上运行完的进程。
分别指向活跃队列和过期队列的指针。
以上就是我们进程的优先级和如何调度。此时大脑中应该有进程运行切换时的动态图了，如果没有，大家可以看看卡在那个环节，然后再去复习，之后就是不断完善这个图的各个部分的细节。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online