操作系统当中各类调度算法
一、处理器调度算法
处理器调度的核心目标是提高 CPU 利用率、吞吐量，并减少等待时间和响应时间。调度算法决定了就绪队列中哪个进程获得 CPU 的使用权。
算法对比总览
| 算法 | 名称 | 抢占性 | 特点 | 优缺点 |
|---|---|---|---|---|
| FCFS | 先来先服务 | 非抢占 | 按请求顺序排队 | 实现简单；对短进程不利 |
| RR | 时间片轮转 | 抢占 | 公平分配时间片 | 响应快；时间片大小难抉择 |
| SPN | 短进程优先 | 非抢占 | 优先处理耗时短的 | 平均等待时间最短；会导致长进程“饥饿” |
| SRT | 最短剩余时间优先 | 抢占 | SPN 的抢占式版本 | 响应极快；需要预知运行时间 |
| HRRF | 最高响应比优先 | 非抢占 | 优先级 = (等待+服务)/服务 | 兼顾长短进程；计算开销较大 |
| Feedback | 多级反馈队列 | 抢占 | 多级队列 + 优先级递减 | 动态自适应；实现最复杂 |
各算法核心概念详解
1. FCFS（先来先服务）
- 解释：按照进程到达就绪队列的先后顺序分配 CPU，一旦获得 CPU 便一直运行直到完成或阻塞。这是最基础的非抢占式调度算法，实现简单，但短进程若排在长进程之后，等待时间会大大增加，不利于交互性。
2. RR（时间片轮转）
- 解释：将 CPU 时间划分为固定大小的时间片，就绪队列中的进程轮流执行一个时间片。若进程在时间片内未完成，则回到队列尾部。该算法兼顾了公平性和响应速度，是分时系统的基础。时间片过小会导致频繁上下文切换，过大则退化为 FCFS。
3. SPN（短进程优先）
- 解释：选择服务时间最短的进程优先执行，非抢占式。该算法能有效降低平均等待时间，在所有非抢占式算法中平均周转时间最优。但长进程可能长期得不到执行（饥饿现象），且需要预先知道每个进程的服务时间。
4. SRT（最短剩余时间优先）
- 解释：SPN 的抢占式版本。当有新进程到达，且其剩余服务时间小于当前进程的剩余时间时，立即抢占 CPU。该算法响应极快，对短进程尤为有利，但同样需要预知运行时间，且抢占带来的上下文切换开销较大。
5. HRRF（最高响应比优先）
- 解释：动态计算每个进程的优先级，公式为 $ \text{优先级} = \frac{\text{等待时间} + \text{服务时间}}{\text{服务时间}} $，选择优先级最高的进程执行。该算法兼顾了长短进程：短进程因分母小容易优先，而长进程随等待时间增加优先级会逐渐提升，避免了饥饿。缺点是需要每次调度时重新计算，开销较大。
6. Feedback（多级反馈队列）
- 解释：设置多个优先级递减的就绪队列，新进程进入最高优先级队列，时间片逐渐增大。同一队列内按 RR 调度，若时间片用完则降入下一队列。系统优先调度高优先级队列。该算法动态自适应，既能快速响应短进程，又能保证长进程不会饿死，是现代通用操作系统（如 Linux、Windows）的调度基础，但实现最为复杂。
二、页面替换算法
当内存不足时，需要将某些页面置换出内存，这些算法决定了“置换谁”。页面替换算法的目标是减少缺页率，提高内存访问效率。
常见页面置换算法概念说明
1. OPT（最佳置换算法）
- 解释：置换未来最长时间内不再访问的页面。这是理论上的最优解，缺页率最低，但无法实现（因为无法预知未来的访问序列），仅作为衡量其他算法性能的上限标尺。
2. FIFO（先进先出）
- 解释：最早进入内存的页面先被置换。实现最为简单，只需维护一个队列即可。但性能较差，且存在 Belady 异常——即内存块增多时缺页率反而上升的反常现象，因此在实际系统中较少单独使用。
3. LRU（最近最久未使用）
- 解释：置换最久未被访问的页面。基于程序局部性原理，认为近期访问过的页面在未来更有可能被再次访问。这是工业界最常用的高性能算法，但需要硬件支持（如访问位或栈记录）才能高效实现，否则查找开销较大。
4. CLOCK（时钟置换算法）
- 解释：给每个页面设置一个访问位（Reference Bit），使用指针绕环扫描。若访问位为 1 则置 0 并跳过；若为 0 则置换该页面。它是 LRU 的一种高效近似实现，开销小、兼容性好，在实际操作系统（如 Linux）中广泛使用，也称为“第二次机会算法”。
三、磁盘寻道算法
磁盘调度旨在最小化磁头移动的平均寻道时间，从而提升磁盘 I/O 的整体性能。磁盘存取总时间由三部分构成：
$$
T_a = T_s + \frac{1}{2r} + \frac{b}{rN}
$$
- (T_s) (Seek Time)：寻道时间，磁头臂移动到指定磁道的时间。这是磁盘存取中耗时占比最大的一部分，因此寻道算法主要针对它进行优化。
- (1/2r)：旋转延迟，平均需要等待半圈扇区旋转到磁头下方。
- (b/rN)：传送时间，实际读写数据的时间。
寻道算法概念对比
| 算法 | 逻辑说明 | 特点 |
|---|---|---|
| FCFS | 按请求到达顺序移动 | 公平，但性能很差 |
| SSTF | 优先处理离当前磁头最近的请求 | 吞吐量高，但会导致远端请求饥饿 |
| SCAN | 磁头在磁盘一端向另一端移动，途中处理请求 | 避免饥饿，即“电梯调度算法” |
| LOOK | SCAN 的优化版，磁头只移动到最远的请求点即折返 | 减少了无用的磁头空转 |
| C-SCAN | 磁头单向移动，到达末端后直接跳回起点 | 提供更均匀的响应时间 |
| C-LOOK | C-SCAN 的优化版，仅在最远请求处折返 | 进一步优化了 C-SCAN 的效率 |
各算法核心概念详解
1. FCFS（先来先服务）
- 解释：按请求到达的先后顺序依次服务磁头臂移动。逻辑最简单、实现最公平，但磁头移动距离往往很长，整体效率低下，不适合高负载场景。
2. SSTF（最短寻道时间优先）
- 解释：选择离当前磁头位置最近的请求优先服务。能有效降低平均寻道时间，吞吐量较高，但会导致远离当前磁头位置的请求长期得不到服务（饥饿现象），且对磁头运动轨迹没有全局规划。
3. SCAN（电梯调度算法）
- 解释：磁头沿一个方向（例如从内圈到外圈）移动，途中处理所有经过的请求，到达磁盘另一端后再反向。该算法避免了饥饿，响应时间较为均衡，但会存在磁头在两端之间来回移动的“无效空转”。
4. LOOK（优化 SCAN）
- 解释：SCAN 的优化版，磁头不需要移动到磁盘的物理边界，而是只移动到当前方向最远的请求点即可折返。减少了无用的磁头空转距离，进一步提升了效率。
5. C-SCAN（循环扫描）
- 解释：磁头单向移动，从一端到另一端处理请求，到达末端后直接跳回起点，再重新开始。该算法提供了更均匀的响应时间，避免了 SCAN 中两端请求响应时间差异大的问题，但跳回起点的操作会带来额外的开销。
6. C-LOOK（优化 C-SCAN）
- 解释：C-SCAN 的优化版，磁头只移动到当前方向最远的请求点即折返回到起点，不移动到磁盘物理末端。在 C-SCAN 均匀响应的基础上，进一步减少了空转距离，是磁盘调度中兼顾效率与公平性的常见选择。