1. 一句话总览
调度算法本质是在回答一个问题：
资源有限时，下一次该服务谁？
不同算法的差异在于：它们用什么标准判断“谁更该被调度”。
2. 调度算法分类
可以分成两大类：
一类：队列调度算法
解决“多个队列/用户/业务，谁先服务”的问题。
一类：流量整形算法
解决“某个用户/业务能不能以这个速率进入网络”的问题。一句话区别：
调度算法：决定资源怎么分。
流量整形：限制流量怎么进。3. 队列优先级算法
3.1 FCFS：先进先出
一句话功能
谁先来，谁先服务。
核心逻辑
按照任务到达顺序排队；
先到的先调度；
当前任务结束后，再调度下一个任务。优点
实现最简单；
调度开销小；
顺序清晰。缺点
不看任务大小；
不看信道好坏；
不看业务优先级；
大任务可能堵住后面的小任务。无线场景理解
适合确定性强、流程简单的场景，例如：
信令调度
重传调度
控制流程排队处理记忆关键词
先来先服务，简单但容易被大任务堵住。3.2 RR：轮询调度
一句话功能
大家轮流来，每个队列都有机会。
核心逻辑
调度器按固定顺序轮询队列；
队列非空就服务一次；
队列为空就跳过。优点
简单；
相对公平；
不会长期饿死某个队列。缺点
不看CQI；
不看信道质量；
不看业务优先级；
系统容量可能较低。无线场景理解
RR 对用户很公平，但对系统吞吐不友好。
例如：
近点用户CQI很好；
远点用户CQI很差；
RR仍然轮流调度。结果是：
公平有了，但吞吐损失大。记忆关键词
人人有份，但不聪明。3.3 WRR：加权轮询
一句话功能
在 RR 基础上加权重，权重大的人多调度几次。
核心逻辑
每个队列配置一个权重；
权重大，调度次数多；
权重小，调度次数少。例如：
队列A权重 = 3
队列B权重 = 1可以理解为：
A被调度3次，B被调度1次。优点
比RR更灵活；
可以体现业务优先级；
实现仍然相对简单。缺点
按报文个数调度；
不考虑报文大小；
大包队列会获得更多实际带宽。关键问题
WRR 看起来公平，但它公平的是：
调度次数不是：
实际带宽如果 A 队列都是大包，B 队列都是小包，A 实际拿到的带宽更大。
记忆关键词
按次数加权，不按字节公平。3.4 DRR：赤字轮询
一句话功能
在 WRR 基础上考虑包长，实现更接近速率公平。
核心逻辑
DRR 引入两个概念：
quantum：每轮给队列增加的调度额度
deficit：队列累计可用额度调度规则：
每轮给队列增加 quantum；
如果 deficit >= 队首包大小，就发送该包；
发送后 deficit -= 包大小；
如果 deficit 不够，就攒到下一轮。举个例子
quantum = 400
包大小 = 900第 1 轮：
deficit = 400，不够发900，不发第 2 轮：
deficit = 800，不够发900，不发第 3 轮：
deficit = 1200，够发900，发送
剩余 deficit = 300优点
考虑包长；
更接近带宽公平；
避免WRR大包占便宜的问题。缺点
需要维护deficit；
要计算包长；
实现复杂度比RR/WRR高。记忆关键词
按字节记账，额度够了再发。3.5 SP：严格优先级
一句话功能
高优先级永远先服务。
核心逻辑
先看最高优先级队列；
只要高优先级队列非空，就一直调度它；
高优先级空了，才调度低优先级。优点
关键业务保障强；
低时延业务可以优先处理；
逻辑清晰。缺点
低优先级可能长期得不到调度；
如果高优先级流量过大，会饿死低优先级。无线场景理解
适合强保障业务，例如：
控制信令
URLLC类低时延业务
高优先级重传
紧急业务但必须配合限速或令牌桶，否则低优先级业务会被压死。
记忆关键词
关键业务绝对优先，但可能饿死低优先级。3.6 SJF：最短任务优先
一句话功能
谁占资源少，谁先服务。
核心逻辑
从待调度任务中选择运行时间最短或资源占用最少的任务；
短任务先完成；
长任务后处理。优点
有利于降低平均等待时间；
有利于提升系统整体吞吐；
小任务响应快。缺点
长任务可能长期等待；
如果短任务持续到来，长任务会被不断推迟。无线场景理解
可以类比：
小包业务
短时延业务
低资源占用业务但如果一直优先小包，大包业务可能被长期压制。
记忆关键词
短任务优先，整体效率高，但长任务容易饥饿。3.7 PF：比例公平
一句话功能
在系统吞吐和用户公平之间折中。
核心公式
PF优先级 = 当前可达速率 / 历史平均速率也可以理解为：
PF = 当前信道好不好 / 过去已经拿了多少资源核心逻辑
当前速率高 → 优先级高；
历史平均速率低 → 优先级高；
长期没被调度的用户会逐渐获得机会。优点
兼顾系统容量和公平性；
比RR更懂信道；
比Max C/I更公平。缺点
原始PF不直接考虑QoS；
不保证时延；
不保证最低速率；
不保证业务体验。和其他算法对比
Max C/I：只看当前信道，吞吐高但不公平。
RR：只看轮流公平，吞吐低。
PF：当前速率 / 历史速率，折中。EPF 是什么
EPF 可以理解为增强版 PF，在 PF 的基础上加入更多权重因子，例如：
业务优先级
QoS需求
时延因子
GBR保障
缓存状态
用户等级简化理解：
PF：主要看速率公平。
EPF：在PF基础上加入业务体验和优先级。记忆关键词
当前好、过去少，就优先调。4. 队列调度算法对比表
| 算法 | 核心标准 | 优点 | 缺点 | 适合场景 |
|---|---|---|---|---|
| FCFS | 到达顺序 | 简单、开销小 | 大任务阻塞小任务 | 信令、重传 |
| RR | 轮流服务 | 公平、简单 | 不看信道，容量低 | 基础公平调度 |
| WRR | 按权重轮询 | 支持优先级 | 不考虑包长 | 多业务队列 |
| DRR | 按字节额度轮询 | 速率公平 | 实现复杂些 | 不同包长队列 |
| SP | 严格优先级 | 关键业务保障强 | 低优先级可能饿死 | 控制面、低时延 |
| SJF | 短任务优先 | 平均等待低 | 长任务可能饥饿 | 小包优先场景 |
| PF | 当前速率/历史速率 | 吞吐与公平折中 | QoS保障不足 | 无线数据调度 |
5. 调度算法之间的主线关系
可以这样理解它们的演进：
FCFS：按到达顺序
RR：按用户公平轮流
WRR：按权重轮流
DRR：按字节公平轮流
SP：按业务优先级
SJF：按任务大小
PF：按信道效率 + 历史公平
EPF：PF + QoS + 业务优先级一句话：
越往后，考虑的因素越多，也越接近真实无线调度。6. 流量整形算法
6.1 流量整形解决什么问题
调度算法解决：
资源给谁？流量整形解决：
流量能不能进？进多少？超速怎么处理？如果没有流量整形，大量突发流量会导致：
缓存拥塞
排队时延增大
丢包增加
网络资源浪费
业务体验恶化所以需要限制流量进入网络的速率。
6.2 令牌桶基本思想
令牌桶可以理解为：
桶里装令牌；
系统按固定速率往桶里放令牌；
报文发送前要拿令牌；
令牌够，报文通过；
令牌不够，报文等待、降级或丢弃。关键参数
令牌生成速率：控制长期平均速率
桶容量：控制允许突发的大小
报文大小：决定需要消耗多少令牌为什么令牌桶能支持突发
因为令牌可以积累。
如果一段时间没有发流量，桶里会攒令牌。 下一波突发到来时，可以用之前攒的令牌快速发送。
6.3 报文染色机制
令牌桶常用颜色标记：
绿色：未超速，正常转发
黄色：轻微超速，降级处理
红色：严重超速，丢弃这不是为了好看，而是为了让系统对不同程度的超速采取不同策略。
7. 单速单桶
一句话功能
只限制平均带宽。
核心逻辑
一个令牌桶；
按固定速率加令牌；
报文来时，如果令牌够就通过；
令牌不够就缓存或丢弃。适用场景
只想限制用户最大带宽；
不需要区分突发程度。优点
简单；
实现成本低；
参数少。缺点
无法区分轻微突发和严重突发；
策略不够精细。记忆关键词
一个桶，控平均速率。8. 单速双桶
一句话功能
在限制平均速率的同时，允许一定突发。
核心逻辑
一个速率；
两个桶；
先填充一个桶；
满了再填另一个桶；
根据两个桶的令牌情况判断绿/黄/红。可以理解为：
C桶：承诺流量
E桶：额外突发流量适用场景
需要限制长期速率；
但允许短时间突发。优点
比单桶更灵活；
能容忍一定突发；
可以做不同颜色标记。缺点
处理流程更复杂；
参数配置更复杂。记忆关键词
一个速率，两个桶，允许突发。9. 双速双桶
一句话功能
同时限制承诺速率和峰值速率。
核心逻辑
两个桶；
两个填充速率；
C桶控制承诺速率；
P桶控制峰值速率；
根据令牌是否足够决定绿/黄/红。常见理解：
CIR：Committed Information Rate，承诺速率
PIR：Peak Information Rate，峰值速率
CBS：承诺突发大小
PBS：峰值突发大小简化判断
C桶和P桶都够：绿色
C桶不够但P桶够：黄色
P桶也不够：红色适用场景
既要限制平均带宽；
又要限制峰值带宽；
还要区分不同程度的突发。优点
最灵活；
可以区分正常、轻微超速、严重超速；
适合精细QoS控制。缺点
实现和配置复杂；
参数理解成本高。记忆关键词
两个速率，两个桶，精细限速。10. 三种令牌桶对比
| 算法 | 桶数量 | 速率数量 | 能否支持突发 | 能否区分颜色 | 复杂度 |
|---|---|---|---|---|---|
| 单速单桶 | 1 | 1 | 弱 | 弱 | 低 |
| 单速双桶 | 2 | 1 | 是 | 是 | 中 |
| 双速双桶 | 2 | 2 | 是 | 是，最精细 | 高 |
11. 调度算法与流量整形的区别
| 对比项 | 调度算法 | 流量整形 |
|---|---|---|
| 解决问题 | 谁先被服务 | 流量能不能进入 |
| 作用位置 | 出队/资源分配 | 入队/入口监管 |
| 典型算法 | RR、WRR、DRR、SP、PF | 令牌桶 |
| 核心目标 | 分配资源 | 控制速率 |
| 关注点 | 公平、优先级、吞吐 | 限速、突发、染色 |
一句话：
调度是“发给谁”；
整形是“让不让进”。12. 学习这批算法的主线
你要按这条线理解：
1. 最简单：FCFS
按到达顺序。
2. 追求公平：RR
每个人轮流来。
3. 加入权重：WRR
重要的人多来几次。
4. 考虑包长：DRR
不按次数公平，而按字节公平。
5. 保障关键业务：SP
高优先级先服务。
6. 提升系统效率：SJF
小任务先完成。
7. 兼顾无线吞吐和公平：PF
信道好且历史少的人优先。
8. 加入业务体验：EPF
PF基础上叠加QoS和业务优先级。
9. 控制入口流量：令牌桶
控制流量速率和突发。13. 你最容易混的点
13.1 WRR 和 DRR 的区别
WRR：按包个数调度。
DRR：按字节额度调度。举例：
队列A：每个包1000字节
队列B：每个包100字节WRR 如果各发 1 个包：
A 实际发了1000字节
B 实际发了100字节这不是真正带宽公平。
DRR 会按字节额度扣账，更公平。
13.2 SP 和 PF 的区别
SP：业务优先级绝对优先。
PF：效率和公平折中。SP 更适合关键业务保障。 PF 更适合无线数据业务调度。
13.3 水桶算法和调度算法不是一类东西
令牌桶不是决定“谁先调度”，而是决定：
这个流量是否超速；
超速后怎么处理。14. 一句话记忆版
FCFS：先来先服务。
RR：大家轮流。
WRR：按权重轮流。
DRR：按字节额度轮流。
SP：高优先级先来。
SJF：短任务先来。
PF：信道好且历史少的先来。
EPF：PF再叠加QoS和业务优先级。
令牌桶：控制流量进入速度。