3. 单机调度算法（上）
各位同学，咱们今天聊聊单机调度。说白了，就是一台机器上，多个任务排队等着被处理，谁先谁后的问题。
我刚开始做系统开发时，觉得调度不就是个队列嘛，先进先出就完事了。后来被现实狠狠教育了一顿——不同的调度策略，性能差距能到几十倍。今天咱们就把三个最经典的算法掰开揉碎讲清楚。
先来先服务（FCFS）
这是最朴素的算法。谁先到，谁先上。就像食堂排队打饭，先来的先吃。
核心逻辑： 按照任务到达时间的先后顺序，依次执行。
优点： 实现简单，公平（至少看起来公平）。
缺点： 平均等待时间可能很长，尤其当短任务排在长任务后面时。
我在项目中遇到过这样一个场景：一个批处理系统里，有个大任务跑了2小时，后面排了十几个小任务，每个只需要几秒钟。结果所有小任务硬生生等了2小时。用户直接炸了。
为什么会这样？因为FCFS不考虑任务长度。你想想看，一个短任务被长任务堵住，体验极差。
适用场景： 对响应时间不敏感、任务长度相近的场景。比如日志批量处理。
短作业优先（SJF）
这个算法就聪明多了。它优先执行预计执行时间最短的任务。
核心逻辑： 每次从就绪队列中，选择预计执行时间最短的任务来执行。
我个人的习惯： 在实现SJF时，我会用一个最小堆来维护任务队列。这样每次取最短任务的时间复杂度是O(1)，插入是O(log n)，效率很高。
优点： 平均等待时间最短，理论上是最优的。
缺点： 需要预知任务执行时间，这在现实中很难。而且长任务可能永远得不到执行（饥饿现象）。
我曾经在一个实时数据处理系统中尝试过SJF。结果发现，短任务源源不断地进来，长任务一直被往后推，最后超时了。嗯，这里要注意——SJF在非抢占式下，长任务可能会被饿死。
变种： 抢占式短作业优先（SRTF）。当一个新任务到达时，如果它的执行时间比当前正在执行的任务剩余时间还短，就抢占CPU。这能进一步降低平均等待时间，但上下文切换开销也上去了。
高响应比优先（HRRN）
这个算法是我个人比较喜欢的。它试图在FCFS和SJF之间找个平衡点。
核心公式：
响应比 = (等待时间 + 预计执行时间) / 预计执行时间说白了，就是等待时间越长，优先级越高；执行时间越短，优先级也越高。两者综合起来算一个比值。
关键点： 每次调度时，计算所有就绪任务的响应比，选最高的那个执行。
优点： 既照顾了短任务（响应比高），又防止了长任务被饿死（等待时间长了，响应比也会升高）。
缺点： 每次调度都要计算所有任务的响应比，时间复杂度O(n)。而且仍然需要预知执行时间。
我记得有一次做数据库连接池的调度优化，就用了HRRN的思路。短查询快速响应，长查询也不会被无限搁置。效果还不错。
三种算法对比
| 算法 | 核心思想 | 平均等待时间 | 饥饿问题 | 实现复杂度 |
|---|---|---|---|---|
| FCFS | 先来先服务 | 可能很长 | 无 | 低 |
| SJF | 最短优先 | 最短（理论最优） | 有（长任务可能饿死） | 中 |
| HRRN | 响应比最高优先 | 较短 | 无（等待时间会提升优先级） | 较高 |
避坑指南： 我曾经在项目中直接用了SJF，结果长任务被饿死，导致系统整体吞吐量下降。后来改用HRRN，虽然每次调度多花了一点计算时间，但整体公平性和吞吐量都好了很多。
所以，选算法不能只看理论最优，还要考虑实际场景。
知识体系图
下面这张图展示了三种算法的核心逻辑和关系：
这张图把三个算法的核心特性和优缺点都列出来了。你可以看到，FCFS最简单但性能差，SJF性能最优但有饥饿风险，HRRN在两者之间做了折中。
实际项目中，我一般会这样选：如果任务长度差异不大，用FCFS就够了；如果短任务居多且能预估时间，用SJF；如果任务长度差异大且不能容忍饥饿，用HRRN。
好了，单机调度的上半部分就到这里。记住一句话：没有银弹，只有最适合场景的算法。