3、任务调度算法(上)：先来先服务(FCFS)、短任务优先(SJF)、时间片轮转(RR)
各位同学，咱们今天聊聊机顶盒里的「交通警察」——任务调度算法。说白了，就是CPU该先处理谁的问题。
我刚开始做机顶盒那会儿，总觉得调度嘛，谁先来谁先上，简单得很。结果有一次直播源切换时，画面卡了整整两秒，用户投诉电话都打爆了。后来一查，原来是后台一个下载任务把CPU占死了。嗯，从那以后我才真正重视起调度算法来。
3.1 先来先服务（FCFS）
这是最朴素的算法。就像排队买奶茶，谁先到谁先买。在机顶盒里，谁先发起系统调用，谁就先获得CPU。
核心思想：非抢占式，按到达顺序执行，直到任务主动释放CPU。
我举个例子。假设有三个任务：
| 任务 | 到达时间 | 执行时间（ms） |
|---|---|---|
| T1（红外遥控响应） | 0 | 10 |
| T2（视频解码帧） | 2 | 30 |
| T3（网络状态轮询） | 4 | 5 |
按FCFS，执行顺序就是T1→T2→T3。T1在0时刻开始，10ms结束。T2等到10ms才开始，到40ms结束。T3等到40ms才开始，45ms结束。
你算算平均等待时间：(0 + (10-2) + (40-4)) / 3 = 14.67ms。看起来还行？
我曾经踩过的坑：有一次机顶盒开机后，一个后台OTA升级任务先到了，它要下载200MB的固件包。结果用户按遥控器换台，等了整整8秒才有反应。这就是FCFS的「护航效应」——一个长任务堵在后面，所有短任务都得排队等死。
FCFS的优点是实现简单，不需要复杂的数据结构。但缺点也很明显：对短任务不友好，交互体验差。在机顶盒这种对实时性有要求的场景，我一般只在系统初始化阶段用FCFS。
3.2 短任务优先（SJF）
这个算法就聪明多了。它让执行时间最短的任务先跑。你想想看，机顶盒里大部分操作都是短任务——按个键、切个台、调个音量。把这些短任务优先处理，用户体验会好很多。
核心思想：非抢占式（或抢占式），选择剩余执行时间最短的任务执行。
还是刚才那三个任务，用SJF怎么调度？
T1在0时刻到达，直接执行。10ms后T1结束。此时T2（30ms）和T3（5ms）都在等待。SJF会选择T3，因为它更短。T3从10ms执行到15ms。最后T2从15ms执行到45ms。
平均等待时间：(0 + (15-2) + (10-4)) / 3 = 6.33ms。比FCFS的14.67ms好了一倍多！
我个人习惯：在机顶盒的UI响应线程里，我会用SJF的变种。因为用户按键的响应时间通常只有几毫秒，而视频解码一帧可能需要16ms（60fps）。让按键响应优先，用户会觉得「这盒子真跟手」。
但SJF有个致命问题——你怎么知道任务要执行多久？
在实际系统中，我们通常用历史执行时间来估算。比如上次按键处理用了3ms，这次也按3ms算。但估算总有误差。我曾经遇到过一个解码任务，平时都是16ms一帧，突然有一次码率飙升，一帧处理了80ms。SJF按老数据把它当成短任务优先执行，结果把其他任务都堵死了。
注意：SJF在理论上是最优的（平均等待时间最小），但在实践中很难完美实现。因为任务执行时间不可预测，而且短任务可能被源源不断地新任务「插队」，导致长任务永远得不到执行——这就是「饥饿」问题。
3.3 时间片轮转（RR）
好了，前两种算法都有各自的毛病。FCFS对短任务不友好，SJF可能导致长任务饿死。那有没有一种算法，既公平又能保证响应？
有，就是时间片轮转。每个任务轮流执行一小段时间，时间到了就换下一个。就像打牌时轮流摸牌，每人摸一张，公平得很。
核心思想：抢占式，每个任务分配一个固定时间片（time slice），时间片耗尽则强制切换。
假设时间片设为10ms，还是那三个任务：
| 时间（ms） | 执行任务 | 说明 |
|---|---|---|
| 0-10 | T1 | T1执行10ms后结束 |
| 10-20 | T2 | T2执行10ms，还剩20ms |
| 20-25 | T3 | T3执行5ms后结束 |
| 25-35 | T2 | T2再执行10ms，还剩10ms |
| 35-45 | T2 | T2执行最后10ms，结束 |
平均等待时间：(0 + (10-2) + (20-4)) / 3 = 8ms。介于FCFS和SJF之间。
时间片的大小很关键。设大了，RR就退化成FCFS；设小了，上下文切换的开销会吃掉CPU性能。
我建议：在机顶盒里，时间片通常设为10-20ms。为什么？因为人眼对画面变化的感知阈值大约是50ms。10ms的切换粒度，能保证每个任务在50ms内至少轮到2-3次，用户基本感觉不到卡顿。
RR的优点是公平性好，没有饥饿问题。每个任务都能得到CPU时间。缺点是上下文切换开销大，而且对实时性要求高的任务（比如音频解码）可能因为时间片用完而被中断。
我记得有一次调试一个机顶盒的音频卡顿问题。音频解码任务每10ms需要处理一次数据，但时间片轮转把它切走了，导致音频缓冲区溢出。后来我把音频任务的优先级提高，并给它分配了更大的时间片，问题才解决。
3.4 三种算法的对比
| 算法 | 抢占式？ | 平均等待时间 | 饥饿问题 | 适用场景 |
|---|---|---|---|---|
| FCFS | 否 | 高 | 无 | 批处理、系统初始化 |
| SJF | 通常非抢占 | 低（理论最优） | 有（长任务饿死） | 短任务为主的交互系统 |
| RR | 是 | 中等 | 无 | 分时系统、通用场景 |
在实际的机顶盒系统中，我们很少只用一种算法。通常的做法是：
- 高优先级任务（如中断处理、音频解码）用FCFS，因为它们必须立即执行
- 中等优先级任务（如UI响应、网络轮询）用RR，保证公平
- 低优先级任务（如日志写入、OTA下载）用SJF的思想，尽量不阻塞其他任务
说白了，调度算法没有银弹。你得根据具体的硬件平台、业务场景、用户体验要求来组合使用。我做了十年机顶盒，每次换芯片平台，调度参数都得重新调一遍。
下一节课，咱们接着讲优先级调度和多级队列调度。那些才是机顶盒里真正常用的东西。今天先消化这三个基础算法，有什么问题咱们课后聊。