公平任务队列基于HFSC的层次调度实现
为 SaaS 服务平台提供服务的过程中，如何公平地为客户分配资源是一个关键问题。特别是在服务吞吐量存在性能瓶颈、单位时间内只能处理有限任务的情况下，如何在不同付费单位及其子用户之间实现公平的任务调度，确保一定比例的任务能够被及时处理以提升用户体验，成为一个常见的挑战。本文将探讨一种基于层次公平服务曲线（HFSC）的公平任务队列实现，分析其具体业务需求，并提出相应的解决方案。
需求说明
我们提供的 SaaS 服务为每个付费单位分配一个“域”（CustomGroup），即一个用户组集合。域管理员可以在其中构建一个树状的用户组结构，每个用户组内可定义多个角色（Role），角色与具体用户绑定。每个用户在一个域中仅能拥有一个角色。用户可通过购买的算力创建不同优先级（低、中、高、最高）的任务，优先级越高，所需算力越多，且高优先级任务优先被处理。我们希望设计一种调度算法，确保在单位时间内为不同用户提供公平的服务，避免某些任务长时间未被处理。
域-用户组-角色-用户的结构图：
算法参考
WeightedFairQueueing(WFQ)
WFQ 是一种调度算法，主要用于管理多个数据流（比如网络数据包、任务队列等），确保它们能按照一定的“公平性”和“权重”分配资源。它是 Fair Queueing（公平队列）的升级版，增加了“权重”这个概念。想象一下，你在管理一个自助餐厅的队伍。有的人拿了小份食物（数据量小），有的人拿了大份（数据量大），还有人愿意多付钱要求优先服务（权重高）。WFQ 的目标是让每个人都能按顺序拿到食物，但那些付钱多的人（高权重）会稍微优先一点，同时保证没人被完全饿着。
WFQ 的核心是通过模拟一个“理想的公平系统”来决定谁先被服务。它的基本步骤是：
- 给每个数据流分配权重:每个数据流（比如网络连接、任务）都有一个权重值，比如 1、2、3，代表它们的重要程度或优先级。权重越高，分配到的资源（比如带宽、处理时间）越多。
- 计算虚拟完成时间
- 假设有个“虚拟时钟”，它记录每个数据包（或任务）在理想情况下应该被处理完的时间。
- 这个时间不是真实时间，而是根据数据包的大小和权重算出来的。公式很简单：
虚拟完成时间 = 上一个数据包的虚拟完成时间 + (数据包大小 / 权重)
VFT = max(arrive_time, VFT_prev) + len / weight - 数据量小的包，完成时间早；权重高的流，完成时间也更早。
- 按虚拟完成时间排序:把所有数据包按它们的虚拟完成时间从小到大排好序，然后依次处理。谁的虚拟完成时间最早，谁就先被服务。
- 循环执行:每处理完一个数据包，就更新虚拟时钟，重新计算新来的数据包的虚拟完成时间，继续排序和处理。
WFQ 在网络编程和任务调度中特别常见。以下是几个典型场景：
- 网络路由器
- 应用：管理不同用户的网络流量。
- 比如，一个路由器同时处理视频流（高权重）和邮件下载（低权重）。WFQ 保证视频流更顺畅，同时邮件下载不会完全卡住。
- 任务调度器
- 应用：在服务器上分配 CPU 时间给不同任务。
- 比如，一个高优先级的任务（权重高）会更快完成，低优先级的任务也能分到一点资源。
- 消息队列
- 应用：在消息系统中处理不同来源的消息。
- 比如，一个聊天应用的“VIP 用户消息”可以优先发送。
WeightedFairQueueing优缺点分析
- 优点：
- 公平性强：通过权重比例分配资源，高权重任务更快完成。
- 实现简单：仅需维护队列和虚拟时间。
- 缺点：单层次：无法支持优先级、客户、用户等多级调度。
- 启发：WFQ 的虚拟时间计算适合底层任务队列，但需扩展到分层场景。
HierarchicalFairServiceCurve(H-FSC)
HFSC 是一种更高级的调度算法，通常用于网络带宽分配或任务调度。它在 Weighted Fair Queueing (WFQ) 的基础上增加了“层次结构”和“服务曲线”的概念。简单来说，它不仅能公平分配资源，还能按照一个“树状结构”管理多个数据流，并保证每个数据流的服务质量（QoS，比如延迟、带宽）。想象一下，你在组织一场宴会：
- 有不同的桌子（层次），每桌有不同的人（数据流）。
- 每桌有总的食物量（带宽），桌子之间按权重分配。
- 每桌内部的人也要按规则分食物，而且得保证没人饿着，还得满足某些人的特殊需求（比如“VIP 必须在 5 分钟内吃到”）。
HFSC 就像一个超级聪明的服务员，能同时管好桌子之间和桌子内部的分配。
HFSC的核心逻辑
HFSC 的核心是通过“层次结构”和“服务曲线”来调度资源。分解一下：
层次结构（Hierarchy）
- 数据流被组织成一个树状结构。
- 树的根节点代表总资源（比如总带宽），子节点是不同的类别（比如视频、语音、普通数据），每个类别下又有更细的子节点（比如具体用户）。
- 资源先按权重从根节点分配到子节点，再在子节点内部分配。
服务曲线（Service Curve）
- 每个数据流或节点都有一个“服务曲线”，简单理解就是“资源分配的时间表”。
- 服务曲线通常分两部分：
- 实时性曲线：短期内保证一定资源（比如前 1 秒给 50Mbps）。
- 长期公平性曲线：长期按权重分配（比如平均 30Mbps）。
e/d/v参数
HFSC 用三个关键参数来决定调度顺序：
- Eligible Time (e)：数据包“有资格”被调度的最早时间。
- Deadline Time (d)：数据包“必须”完成的最晚时间。
- Virtual Time (v)：系统级别的“虚拟时钟”，保证长期公平性。
调度逻辑：
- 找出所有 e ≤ 当前时间 的数据包（有资格的）。
- 在这些包中，优先处理 d 最小的（最紧急的）。
- 用 v 更新全局时钟，确保公平性。
这三个参数是 HFSC 的灵魂，我们用一个例子来说明。假设：
-
总带宽 100Mbps。
-
数据流 A：实时速率 r1 = 80Mbps（前 1 秒），长期速率 r2 = 50Mbps。
-
数据包大小 = 80Mb（位），到达时间 = 0 秒。
-
Eligible Time (e)
- 表示“包什么时候可以开始竞争”。
- 计算：e = 到达时间 + (数据包大小 / r1) = 0 + (80Mb / 80Mbps) = 1.0 秒。
- 意思是，这个包在 1 秒时才能被调度。
-
Deadline Time (d)
- 表示“包必须在什么时候完成”。
- 计算：d = e + (数据包大小 / r1) = 1.0 + (80Mb / 80Mbps) = 2.0 秒。
- 意思是，这个包最晚得在 2 秒内处理完。
-
Virtual Time (v)
- 表示“公平性的时钟”。
- 计算：v = max(当前 v_system, 当前时间) + (数据包大小 / r2) = max(0, 0) + (80Mb / 50Mbps) = 1.6 秒。
- 意思是，处理完后，系统虚拟时间跳到 1.6 秒。
-
调度过程：
- 时间 0 秒：e = 1.0 > 0，包没资格，等待。
- 时间 1 秒：e = 1.0 ≤ 1，包有资格，d = 2.0，处理它。
- 更新 v_system = 1.6。
HFSC的应用场景
HFSC 特别适合需要复杂资源管理的场景：
- 网络 QoS：在路由器中管理带宽，保证视频会议低延迟，文件下载有平均带宽。
- 虚拟化：在云计算中分配 CPU 或网络资源给虚拟机。
- 任务调度：在服务器上按层级管理任务，比如部门 → 项目组 → 具体任务。
HFSC简单实现
-
实现思路
- 数据结构：
- 用树表示层次，每个节点有权重和服务曲线。
- 数据包记录大小、到达时间、e/d/v。
- 用优先级队列按 d 排序。
- 数据结构：
-
调度步骤：
- 检查所有包，找出 e ≤ 当前时间的。
- 按 d 排序，处理 d 最小的。
- 更新 v_system。
-
层次管理：
- 从叶子节点计算 e/d/v，向上汇总资源需求。
-
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57import heapq
class Packet:
def __init__(self, size, arrival_time):
self.size = size
self.arrival_time = arrival_time
self.e = 0
self.d = 0
self.v = 0
class Node:
def __init__(self, weight, r1=None, r2=None):
self.weight = weight
self.r1 = r1 # 实时速率
self.r2 = r2 # 长期速率
self.packets = []
def add_packet(self, size, arrival_time):
pkt = Packet(size, arrival_time)
if self.r1:
pkt.e = arrival_time + (size / self.r1)
pkt.d = pkt.e + (size / self.r1)
else:
pkt.e = arrival_time
pkt.d = float('inf')
pkt.v = max(v_system, arrival_time) + (size / self.r2)
self.packets.append(pkt)
v_system = 0.0 # 全局虚拟时间
# 构建树
video = Node(weight=70, r1=80, r2=70)
data = Node(weight=30, r2=30)
video.add_packet(80, 0)
data.add_packet(30, 0)
# 调度
def schedule(nodes, time):
global v_system
eligible = []
for node in nodes:
for pkt in node.packets:
if pkt.e <= time:
eligible.append((pkt.d, pkt))
if eligible:
heapq.heapify(eligible)
d, pkt = heapq.heappop(eligible)
print(f"时间 {time}: 处理大小={pkt.size}, e={pkt.e:.2f}, d={pkt.d:.2f}, v={pkt.v:.2f}")
v_system = max(v_system, pkt.v)
for node in nodes:
if pkt in node.packets:
node.packets.remove(pkt)
break
# 测试
for t in [0.0, 1.0]:
schedule([video, data], t) -
输出：
- 时间 0：处理数据包（大小=30）。
- 时间 1：处理视频包（大小=80）。
EarliestDeadlineFirst(EDF)最先结束最先调度
EDF 是一种实时调度算法，专门用于处理有“截止时间”（deadline）要求任务的系统。它的核心思想很简单：哪个任务的截止时间最早，就先处理哪个任务。想象你在一家快递公司工作，手头有几件包裹，每件都有一个“最晚送达时间”。EDF 就像一个聪明的调度员，总是优先处理最快要过期的包裹，确保尽量不超时。
- 实时系统：EDF 特别适合需要严格时间保证的场景，比如嵌入式设备、实时操作系统。
- 动态优先级：不像固定优先级调度，EDF 的优先级是动态的，根据任务的截止时间实时调整。
EDF的核心逻辑
EDF 的调度规则可以用一句话概括：在任意时刻，选择截止时间（deadline）最早的任务执行。具体步骤如下：
- 任务定义：
- 每个任务有三个关键属性：
- 到达时间（arrival time）：任务什么时候进入系统。
- 执行时间（execution time）：任务需要多少时间完成。
- 截止时间（deadline）：任务必须在什么时候完成。
- 有时还会有周期性（periodic tasks），但我们先从简单情况开始。
- 每个任务有三个关键属性：
- 调度过程：
- 检查所有已经到达的任务（到达时间 ≤ 当前时间）。
- 在这些任务中，找出截止时间最早的那个。
- 执行这个任务，直到完成或被更高优先级（截止时间更早）的任务抢占。
- 抢占式调度：
- EDF 通常是抢占式的（preemptive）：如果一个新任务到达，且它的截止时间比当前任务更早，当前任务会被暂停，新任务优先执行。
一个简单的例子：
- 假设有 3 个任务：
- 任务 A：到达时间 = 0，执行时间 = 2，截止时间 = 4。
- 任务 B：到达时间 = 1，执行时间 = 1，截止时间 = 3。
- 任务 C：到达时间 = 2，执行时间 = 1，截止时间 = 5。
- 调度过程：
- 时间 0：只有 A 到达，截止时间 = 4，开始执行 A。
- 时间 1：A 还剩 1 单位时间，B 到达，截止时间 = 3 < A 的 4，暂停 A，执行 B。
- 时间 2：B 完成（用了 1 单位时间），恢复 A，C 到达，但 A 的截止时间 4 < C 的 5，继续执行 A。
- 时间 3：A 完成（总共用了 2 单位时间），执行 C。
- 时间 4：C 完成（用了 1 单位时间）。
- 结果：
- 执行顺序：A（0-1）→ B（1-2）→ A（2-3）→ C（3-4）。
- 所有任务都在截止时间前完成：A 在 3 < 4，B 在 2 < 3，C 在 4 < 5。
EDF的特点
- 优点：
- 如果任务集是“可调度的”（总负载不超过系统容量），EDF 能保证所有任务按时完成。
- 简单直观，适合实时性要求高的场景。
- 缺点：
- 如果任务超载（执行时间总和超过可用时间），EDF 可能导致多个任务失败。
- 需要实时跟踪截止时间，计算开销稍高。
EDF 在实时系统中非常常见，以下是几个典型场景：
- 嵌入式系统
- 应用：汽车电子中控制刹车、引擎的任务调度。
- 比如，刹车信号（截止时间短）优先于空调调整。
- 实时操作系统 (RTOS)
- 应用：在 RTOS 中调度周期性任务。
- 比如，一个传感器每秒采样一次，必须在下次采样前处理完数据。
- 多媒体处理
- 应用：视频解码中保证帧按时渲染。
- 比如，每帧必须在 33ms（30fps）内完成。
实现EDF的简单思路
要实现 EDF，你需要：
- 用一个数据结构存储任务，记录到达时间、执行时间和截止时间。
- 用优先级队列（按截止时间排序）管理可执行任务。
- 每次调度时，检查新到达的任务，更新优先级。
1 | import heapq |
输出结果：
1 | 时间 0: 执行 A |
CompleteFairScheduler(CFS)
CFS 是一种任务调度算法，最早由 Ingo Molnár 设计并引入 Linux 内核（从 2.6.23 版本开始），用来替代之前的 O(1) 调度器。它的目标是让所有任务尽可能公平地分享 CPU 时间，同时保持调度的高效性和低复杂性。想象你在组织一个派对，桌上有一块大蛋糕（CPU 时间），有几个人（任务）等着分蛋糕。CFS 的原则是：每个人都能分到蛋糕，而且分得尽量平均。如果有人更“重要”（权重高），他们会多拿一点，但不会完全抢走别人的份。
- 公平性：CFS 的核心是“时间公平”，而不是简单地轮流执行。
- 适用性：广泛用于现代操作系统的进程调度。
CFS的核心逻辑
CFS 的核心思想是基于“虚拟运行时间”（vruntime），通过它来衡量和分配 CPU 时间。以下是它的基本逻辑：
- 虚拟运行时间 (vruntime)：
- 每个任务都有一个 vruntime，表示它“应该”获得的 CPU 时间。
- vruntime 的增长速度与任务的权重（优先级）成反比：
- 权重越高，vruntime 增长越慢，任务获得更多 CPU 时间。
- 权重越低，vruntime 增长越快，任务获得较少 CPU 时间。
- 调度原则：
- CFS 总是选择 vruntime 最小的任务执行。
- 为什么？因为 vruntime 小意味着这个任务“欠”了 CPU 时间，应该优先补偿。
- 红黑树管理：
- CFS 用红黑树（一种高效的平衡二叉搜索树）存储所有任务，按 vruntime 排序。
- 每次调度时，从树的最左端（vruntime 最小）取出任务。
- 时间片：
- 任务不会一次性用完分配的时间，而是分成小块（时间片）执行。
- 时间片长度动态调整，确保公平性和响应性。
- 抢占式调度：
- 如果一个新任务的 vruntime 比当前任务小，当前任务会被抢占。
一个简单的例子：
- 假设有 3 个任务：
- 任务 A：权重 = 1。
- 任务 B：权重 = 2。
- 任务 C：权重 = 3。
- 总权重 = 1 + 2 + 3 = 6。
- 假设 CPU 每秒分配 1 个单位时间：
- A 应得 1/6 秒，vruntime 增长速度 = 1 / 1 = 1。
- B 应得 2/6 秒，vruntime 增长速度 = 1 / 2 = 0.5。
- C 应得 3/6 秒，vruntime 增长速度 = 1 / 3 ≈ 0.33。
- 调度过程：
- 初始：A、B、C 的 vruntime 都是 0。
- 时间 0：选 vruntime 最小的 A（0），运行 1 单位时间，vruntime += 1 → 1。
- 时间 1：A=1, B=0, C=0，选 B（0），运行 1 单位时间，vruntime += 0.5 → 0.5。
- 时间 2：A=1, B=0.5, C=0，选 C（0），运行 1 单位时间，vruntime += 0.33 → 0.33。
- 时间 3：A=1, B=0.5, C=0.33，选 C（0.33），vruntime += 0.33 → 0.66。
- 结果：
- 高权重任务（C）运行更多时间，低权重任务（A）运行较少，比例接近 1:2:3。
CFS的特点
- 优点：
- 公平性：长期看，所有任务按权重比例获得 CPU 时间。
- 高效性：红黑树操作的时间复杂度是 O(log n)。
- 灵活性：支持动态调整权重，适应不同任务需求。
- 缺点：
- 不适合硬实时系统（没有严格的截止时间保证）。
- 对高负载下响应性要求高的场景可能不够理想。
CFS 主要用于操作系统内核，但它的思想也可以应用到其他场景：
- 操作系统进程调度
- 应用：Linux 系统中管理用户进程。
- 比如，一个后台任务（低权重）和一个游戏（高权重）并行运行，CFS 保证游戏更流畅。
- 虚拟机调度
- 应用：在虚拟化环境中分配 CPU 给虚拟机。
- 比如，一个虚拟机跑关键服务，分配更高权重。
- 自定义任务调度
- 应用：在服务器程序中管理线程。
- 比如，一个 Web 服务器优先处理 VIP 用户请求。
实现CFS的简单思路
要实现 CFS，你需要：
- 用一个红黑树（或优先级队列）存储任务，按 vruntime 排序。
- 每次调度时，取 vruntime 最小的任务。
- 更新 vruntime，根据权重调整增长速度。
伪代码示例（Python，用堆模拟）
1 | import heapq |
输出：
1 | #C（高权重）执行 2 次，B 执行 2 次，A 执行 1 次，符合权重比例。 |
HierarchicalWeightedFairQueueing(HWFQ)
HWFQ 是一种高级调度算法，它结合了 Weighted Fair Queueing (WFQ) 的加权公平性和“层次结构”的思想。它的目标是在多个层次上公平分配资源，比如网络带宽或 CPU 时间，同时允许不同类别的数据流或任务根据权重获得不同的服务质量。
想象你在管理一个学校的食堂：
- 有不同的年级（层次），比如高年级和低年级。
- 每个年级有几个班（子层次），每个班的学生（数据流）需要分饭。
- 高年级可能更重要（权重高），分到的饭多一些，但每个年级内部也要公平。
- HWFQ 就像一个食堂管理员，先按年级分配饭量，再在每个年级内部按班公平分。
- 层次性：资源分配像树一样，从根节点（总资源）分到子节点（类别），再到叶子节点（具体任务）。
- 加权公平：每个节点有权重，决定它能分到多少资源。
HWFQ 的核心逻辑
HWFQ 的核心是通过“层次结构”和“虚拟完成时间”来调度资源。以下是它的基本步骤：
- 树形层次结构：
- 数据流或任务被组织成一棵树。
- 根节点代表总资源（比如 100Mbps 带宽）。
- 中间节点是类别（比如视频、语音），有自己的权重。
- 叶子节点是具体的数据流或任务，也有权重。
- 资源先按权重从根分配到中间节点，再到叶子节点。
- 虚拟完成时间 (Virtual Finish Time)：
- 每个数据包或任务计算一个“虚拟完成时间”，表示它在理想情况下应该完成的时间。
- 计算公式（简化版）：
虚拟完成时间 = 上一个包的完成时间 + (数据包大小 / 权重对应的速率)。
- 权重越高，速率越大，虚拟完成时间越早。
- 调度过程：
- 从树的叶子节点开始，计算每个数据包的虚拟完成时间。
- 每个中间节点从它的子节点中选择虚拟完成时间最早的包，向上汇总。
- 根节点最终选择全局虚拟完成时间最早的包执行。
- 公平性保证：
- 每个层次的节点按权重分配资源。
- 叶子节点内的数据流也按权重公平分享父节点的资源。
一个简单的例子
- 假设总带宽是 100Mbps，树结构如下：
- 根节点：100Mbps。
- 视频类（权重 70%，70Mbps）：
- V1（权重 1），V2（权重 2）。
- 数据类（权重 30%，30Mbps）：
- D1（权重 1）。
- 数据包：
- V1：100Mb，V2：100Mb，D1：100Mb。
- 计算虚拟完成时间：假设起始时间为 0：
- V1：带宽 = 70 * (1 / (1+2)) ≈ 23.33Mbps，虚拟完成时间 = 100 / 23.33 ≈ 4.29 秒。
- V2：带宽 = 70 * (2 / (1+2)) ≈ 46.67Mbps，虚拟完成时间 = 100 / 46.67 ≈ 2.14 秒。
- D1：带宽 = 30 * (1 / 1) = 30Mbps，虚拟完成时间 = 100 / 30 ≈ 3.33 秒。
- 调度顺序：
- V2（2.14） → D1（3.33） → V1（4.29）。
- V2（高权重）最先完成，D1 次之，V1 最后。
HWFQ的特点
- 优点：
- 层次公平：既保证大类别间的公平，又保证类别内部的公平。
- 灵活性：支持复杂的资源分配需求。
- 可预测性：通过虚拟完成时间提供延迟保证。
- 缺点：
- 复杂性：需要维护树结构和计算虚拟时间，复杂度高于简单 WFQ。
- 实时性有限：不像 EDF 那样严格按截止时间调度。
HWFQ 适用于需要层次化资源管理的场景：
- 网络带宽管理
- 应用：在路由器中分配带宽给不同部门或用户组。
- 比如，公司网络中研发部门（高权重）优先，行政部门次之。
- 云计算资源分配
- 应用：在虚拟化环境中分配 CPU 或网络资源。
- 比如，一个租户有多个虚拟机，按权重分配资源。
- 任务调度
- 应用：在服务器上管理多级任务。
- 比如，一个项目组有多个子任务，按重要性分配处理时间。
实现HWFQ的简单思路
要实现 HWFQ，你需要：
- 用树结构表示层次，每个节点有权重和子节点。
- 为每个数据包计算虚拟完成时间。
- 用优先级队列在每个节点选择最早完成的包。
伪代码示例（Python）
1 | import heapq |
输出：
1 | 调度 V2, 虚拟完成时间=2.14 |
WFQ 与 H-FSC 结合的动机
- 需求分析：
- 层次性：业务需要按优先级、客户和用户分级调度。
- 公平性：资源分配需根据权重比例，避免饿死。
- 简洁性：实现不能过于复杂，便于维护。
- WFQ 的局限：
- 单层次设计无法直接满足需求，但其虚拟时间计算（VFT）简单高效，是公平调度的核心。
- H-FSC 的优势：
- 分层结构天然支持多级调度，虚拟时间管理与 WFQ 兼容。
- 服务曲线虽强大，但对非实时任务（如批量处理）并非必需。
- 结合动机：
- 用 H-FSC 的树形结构解决层次问题。
- 用 WFQ 的虚拟时间计算作为叶子节点的调度基础，简化 H-FSC 的复杂状态。
结合点
- 层次结构（H-FSC）：
- 采用 H-FSC 的树形设计：Root -> Priority -> Customer -> User。
- 每个节点维护 vt，用于调度选择。
- 底层队列（WFQ）：
- 叶子节点使用 WeightedFairQueue，直接应用 WFQ 的 VFT 计算。
- 任务的 vft 驱动队列的 curr_vt，进而影响节点的 vt。
- 调度逻辑：
- 从根节点递归选择 vt 最小的叶子节点（H-FSC 风格）。
- 叶子节点按 FIFO 弹出任务，更新 vt（WFQ 风格）。
取舍与优化
- 保留：
- WFQ 的 VFT 计算：简单高效，核心公平性保证。
- H-FSC 的层次选择：支持多级权重。
- 简化：
- 移除 H-FSC 的 e 和 d：减少计算开销，适用于非实时场景。
- 不采用红黑树：线性遍历子节点，牺牲部分性能换取简洁性。
- 权衡：
- 性能：O(n) 遍历适合中小规模，放弃 O(log n) 的复杂数据结构。
- 实时性：无服务曲线支持，专注公平性而非硬时限。
实现步骤
- 任务添加：
- 从 HfscScheduler 递归找到叶子节点（H-FSC）。
- 在 WeightedFairQueue 中计算 vft 并入队（WFQ）。
- 任务移除：
- 遍历树选择 vt 最小的叶子节点（H-FSC）。
- 从队列弹出任务并更新 vt（WFQ）。
- 虚拟时间同步：
- 叶子节点的 vt 与 WeightedFairQueue 的 curr_vt 同步。
- 中间节点的 vt 根据子节点更新，保留 H-FSC 的层次协调。
方案考虑点与优缺点
考虑点:
- 分层需求：树形结构支持多级权重。
- 公平性：虚拟时间避免饿死。
- 性能：O(n) 遍历，适合中小规模。
- 扩展性：动态添加节点。
优点:
- 层次公平：多级权重分配。
- 实现简单：结合 WFQ 简洁性，简化 H-FSC。
- 灵活性：权重可调。
缺点:
- 性能瓶颈：大规模节点效率低。
- 简化局限：无实时性支持。
- 单线程假设：需额外并发控制。
算法的python实现
类图
- HfscScheduler 包含一个 root（HfscNode）。
- HfscNode 可以有多个子节点（children），叶子节点拥有一个 WeightedFairQueue。
- WeightedFairQueue 包含多个 ScheduledTask。
代码实现
scheduled_task.py
1 | class ScheduledTask: |
weighted_fair_queue.py
1 | from collections import deque |
hfsc_node.py
1 | class HfscNode: |
hfsc_scheduler.py
1 | class HfscScheduler: |