进程优先级和切换
第一部分：进程优先级 (Process Priority）
系统中的进程成百上千，但 CPU（核）可能只有几个。谁先用 CPU？这就涉及到竞争性。为了合理分配资源，必须要有优先级 。
1. PRI 与 NI：一对“相爱相杀”的数值
在 Linux 中，衡量进程优先级的指标主要有两个：PRI(Priority) 和NI(Nice)。
- PRI (Priority)：
- 含义：这是进程真正的优先级。值越小，优先级越高（越早被执行）。
- 现状：用户通常无法直接硬性修改这个值，它由内核动态调整。
- NI (Nice)：
- 含义：这个名字很有趣，意为“这个进程有多‘友善’”。
- 作用：它是优先级的修正数据。
- 取值范围：
-20到19，共 40 个级别 。
- 负值（如 -20）：表示“我不友善”，我要抢 CPU ->优先级变高。
- 正值（如 19）：表示“我很谦让”，CPU 给别人先用 ->优先级变低。
2. 计算公式
内核计算最终优先级的公式非常简单：
- 结论：调整进程优先级，在 Linux 下，本质上就是调整nice 值。
nice为负值，PRI变小，优先级变高。nice为正值，PRI变大，优先级变低。
查看命令：
输入 ps -l 可以看到：
UID：谁启动的。PRI：最终优先级。- NI：nice 值。
第二部分：进程切换 (Context Switch)
既然进程有优先级，高优先级的来了，正在跑的低优先级进程就得让路。或者时间片到了，大家轮流坐庄。
问题是：进程 A 被切下去时，它跑到哪一行代码、寄存器里存的临时结果怎么办？
这就涉及到了上下文 (Context)。
1. 什么是“上下文”？
CPU 内有一堆寄存器（eax,ebx,eip程序计数器,esp栈指针等）。
- 硬件层面：CPU 里的寄存器只有一套（物理硬件）。
- 软件层面：每个进程都认为自己独占这些寄存器。
进程的上下文：就是进程执行时，CPU 寄存器中所有的临时数据8。
2. 切换过程
当 OS 决定把进程 A 换下，把进程 B 换上时，会发生以下动作：
- 保存 (Save)：把 CPU 寄存器里属于进程 A 的数据，统统打包保存到进程 A 的PCB (
task_struct)中（具体是保存在内核栈或 TSS 结构里）。 - 恢复 (Restore)：从进程 B 的 PCB 中，把它上次没跑完的寄存器数据读出来，填回 CPU 的寄存器里 。
- 执行：CPU 指针 (
eip) 指向了进程 B 上次停下的地方，继续运行。
课件中的比喻：
就像你读书记笔记。你要去吃饭（被切走），必须把书签夹好（保存上下文）。等你回来（被调度回来），翻到书签页（恢复上下文），继续往下读，而不是从头读 11。
第三部分：Linux 内核的 O(1) 调度算法
问题：如果有 1000 个进程，OS 怎么快速找到优先级最高的那个去运行？如果遍历链表，时间复杂度是 O(N)，进程越多越慢。
Linux 2.6 引入了 O(1) 调度算法，不管有多少进程，查找时间都是固定的常数！
1. 核心数据结构：runqueue(运行队列)
每个 CPU 都有一个运行队列。在这个队列里，有两个关键的指针数组结构：活动队列 (Active)和过期队列 (Expired)。
结构如下（prio_array）：
queue[140]：这是一个数组，包含了 140 个链表。
- 优先级映射：第 0-99 号下标对应实时进程（我们暂不关心），100-139 号下标对应普通进程的优先级。
- 哈希桶原理：优先级为 100 的进程全挂在
queue[100]的链表上，优先级 101 的挂在queue[101]上。
bitmap[5]：位图。用来标记哪个优先级的链表不为空。查找非空队列时，不需要遍历数组，直接查位图，效率极高 。
2. 运作机制
- 调度谁？
调度器直接去 活动队列 (Active) 里找优先级最高的（下标最小的）非空链表，拿出第一个进程去跑。因为有位图，这个过程是 O(1) 的 。
- 时间片用完了怎么办？
当一个进程时间片耗尽，它会被从 Active 队列 拿下来，重新计算优先级，然后扔到 Expired 队列 里去 。
- 乾坤大挪移 (关键!)
随着时间推移，Active 队列里的进程越来越少（都跑完去 Expired 了），Expired 队列里的进程越来越多。
当 Active 队列空了怎么办？
OS 只需要交换两个指针：active和expired指针互换！
- 原来的 Expired 瞬间变成了 Active，里面装满了分配好新时间片的进程。
- 原来的 Active 变成了空荡荡的 Expired，准备接收下一波跑累的进程。
总结
- 优先级 (PRI/NI)决定了进程在
queue[140]数组中的位置。 - 上下文切换保证了进程可以暂停和恢复。
- O(1) 调度器利用双队列 (Active/Expired)和指针交换，保证了在海量进程下系统依然极其流畅。