调度队列)
一、进程优先级：谁先拿到 CPU
CPU 分配资源的先后顺序是进程优先权，在ps -l中可以看到描述优先级的两个值：
PRI：进程优先级，值越小越早被执行NI：nice 值，优先级的修正数值，范围-20 ~ 19，共 40 个级别
nice值输入100，最高只能到19：
1.1 PRI 与 NI 的换算关系
优先级公式：
PRI(new)=PRI(old)+NI(nice)nice 为负，新的 PRI 变小，优先级变高，进程更快被执行
结论：Linux 下调优先级就是调 nice。但 nice 不是优先级本身，只是修正数据。
补充：top和ps的显示刻度不同
top的PRI：20 + niceps的PRI：80 + nice
内核O(1)队列下标：100+nice
1.2 查看 / 修改
- 查看：
ps -l关注UID、PID、PPID、PRI、NI - 修改：
top后按r→ 输入 PID → 输入 nice 值 - 命令：
nice、renice；函数：getpriority()、setpriority()
1.3 优先级为什么存在
- 竞争性：进程多，CPU资源少，为了合理竞争才有了优先级
- 独立性：多进程各享资源，互不干扰
- 并行：多 CPU 上同时跑
- 并发：单 CPU 上靠切换，一段时间内都推进
二、进程切换：先存档，再切换
2.1 切换做了什么
进程切换又叫CPU 上下文切换，本质是 CPU 寄存器切换。
内核换任务只做三件事：
- 把当前任务 CPU 寄存器里的全部内容压入该任务自己的堆栈；
- 从下一个任务的栈中把它的状况重新装入 CPU 寄存器；
- 开始运行新任务。
类比两人共用一个工位：A 到点让位，把桌面（寄存器）收进自己抽屉（堆栈）；B 再把抽屉里的东西摆出来接着干。工位不变，人换了。
切换图示：
2.2 什么时候触发切换
触发时机是时间片结束。分时系统里每个进程都有合适的时间片（本质是个计数器），时间片一到，进程就被从 CPU 上剥离下来。
三、O(1) 调度队列：内核怎么挑下一个进程
一个 CPU 拥有一个runqueue，多 CPU 才要考虑负载均衡。优先级分两档：实时0 ~ 99（先不关心），普通100 ~ 139，正好和 nice-20 ~ 19一一对应。
调度图示：
调度过程：
3.1 活动队列 active
nr_active：运行态进程总数；queue[140]：下标即优先级，同优先级按FIFO排队。
挑选三步：从下标 0 遍历queue[140]→ 第一个非空队列就是最高优先级 → 取走队首进程。遍历 140 个队列虽是常数，但常数也能是 140 次比较，仍然低效。
3.2 bitmap[5] 提速
140个优先级用 5×32＝160 个比特位标记队列是否为空，位图一扫就能定位非空队列，查找效率大幅提升。
3.3 过期队列 expired
结构与活动队列一样，装的是时间片耗尽的进程；等活动队列处理完，再给过期队列的进程重新计算时间片。
3.4 交换指针
active永远指向活动队列，expired永远指向过期队列- 活动队列越来越少、过期队列越来越多
- 活动队列清空后，
交换active和expired指针指向的对象，开始第二轮处理
内核struct rq中是这样定义的：
structprio_array{unsignedintnr_active;DECLARE_BITMAP(bitmap,MAX_PRIO+1);structlist_headqueue[MAX_PRIO];};查找最合适调度进程的耗时是常数，不随进程数增长，这就是O(1) 调度算法
该结构出自 Linux 2.6 内核源码（struct rq/struct prio_array）
四、总结
- 优先级：
PRI越小越先跑，PRI(new)=PRI(old)+nice，nice 范围-20 ~ 19，调优先级即调 nice - 切换：寄存器存进本任务堆栈，再装入下一任务的寄存器，由时间片耗尽触发
- O(1)：
queue[140]按优先级排队、bitmap[5]快速定位非空队列、active/expired 双队列交换指针完成批量续期，耗时与进程数无关
感谢阅读，我们下篇见。
