游戏客户端架构 / 系统课时
依赖图怎样表达执行关系
依赖图怎样表达执行关系
当输入、移动和空间查询系统在同一帧内更新实体时,只按注册顺序执行,很难说清哪些顺序必须保留、哪些任务可以重叠。本课把 System 对组件的访问关系转换成有向依赖图,再计算可执行批次,让调度规则能被检查而不是靠约定猜测。
学习目标
- 用读取集合与写入集合识别 System 之间的潜在数据冲突。
- 区分冲突关系和有向先后约束,构建无环依赖图。
- 通过拓扑分层获得执行批次,并定位循环依赖与遗漏资源。
从组件读写集合开始
为每个 System 声明两个集合:R 表示本次执行需要读取的组件类型,W 表示可能写入的组件类型。两个系统只读同一种组件通常可以同时运行;一方写入、另一方读取或写入同一组件时,就存在访问冲突。冲突意味着不能在没有额外保护的情况下重叠执行,但还没有说明先后方向。
例如,Move 读取 MoveIntent、写入 Position;Spatial 读取 Position、写入 SpatialIndex;Render 读取 Position、写入 RenderData。Move 与后两者有冲突,而 Spatial 与 Render 只共享对 Position 的读取,写入目标互不重叠,因此可以成为同一批候选任务。
这里的集合默认按组件类型统计,属于保守判断:即使两个任务操作不同实体的 Position,也可能被判为冲突。需要更精细的并行调度时,可以继续细化到实体范围或 Chunk,但必须能证明访问范围确实不交叉。
给冲突确定方向,才能画出有向图
读写集合只能找出需要约束的系统对,不能自动决定箭头指向。方向来自本帧业务语义:如果空间索引必须反映刚计算出的新位置,就要求 Move → Spatial;如果渲染准备也要读取该位置,则要求 Move → Render。Spatial 和 Render 之间没有必要增加顺序边。
再加入 Input(生成 MoveIntent)与 HitTest(读取 SpatialIndex),就形成两条分支:Input → Move → Spatial → HitTest,以及 Move → Render。箭头表示后者必须等前者完成;没有边不一定代表可并行,还需检查是否有未纳入图的共享资源或显式阶段约束。

从依赖图计算执行批次
下面用 Python 3 标准库演示:先找出冲突对,再根据已确认的阶段优先级给冲突边定向,最后反复取出所有零入度节点。priority 是本示例已核对过语义的排序依据,不表示实际项目能按注册顺序或字母顺序随意决定读写先后。
access = {
"Input": ({"InputDevice"}, {"MoveIntent"}),
"Move": ({"MoveIntent"}, {"Position"}),
"Spatial": ({"Position"}, {"SpatialIndex"}),
"Render": ({"Position"}, {"RenderData"}),
"HitTest": ({"SpatialIndex"}, {"HitPairs"}),
}
priority = ["Input", "Move", "Spatial", "Render", "HitTest"]
def conflicts(a, b):
reads_a, writes_a = access[a]
reads_b, writes_b = access[b]
# 读/写或写/写相交才构成组件访问冲突。
return bool((writes_a & (reads_b | writes_b)) |
(writes_b & reads_a))
edges = {name: set() for name in priority}
for i, a in enumerate(priority):
for b in priority[i + 1:]:
if conflicts(a, b):
edges[a].add(b)
indegree = {name: 0 for name in priority}
for successors in edges.values():
for b in successors:
indegree[b] += 1
batch = 1
while indegree:
ready = sorted(name for name, degree in indegree.items() if degree == 0)
if not ready:
raise ValueError("存在循环依赖")
print(f"批次 {batch}: {','.join(ready)}")
# 整批完成后再解除后继的依赖。
for name in ready:
del indegree[name]
for name in ready:
for next_name in edges[name]:
if next_name in indegree:
indegree[next_name] -= 1
batch += 1预期输出:
批次 1: Input
批次 2: Move
批次 3: Render,Spatial
批次 4: HitTest第三批中的两个 System 可以并行;HitTest 必须等 Spatial 的索引写入结束。这里用整批屏障实现便于理解的拓扑分层。真实任务调度器还可以在某个节点的所有前驱一完成时立即提交它,不必等待同层中无关的慢任务。
发现环时不要强行执行
有向无环图要求每个节点最终都能达到零入度。如果人为添加 Spatial → Render 和 Render → Spatial 两条约束,剩余节点就无法继续出队,代码会抛出循环依赖错误。不能通过随机删除一条边让程序勉强运行;应检查是否把“本帧必须看到新值”和“允许看到上一帧快照”混在了一起。
解决环通常需要拆成前后两个阶段、引入只读快照或双缓冲,或者明确某个反馈要延迟到下一帧。这样调整的是数据语义,而不是仅调整调度列表。对于写入同一个结果的多个系统,还要确定覆盖、累加或归并规则,单纯让它们排队并不能保证业务结果正确。
检查图外的隐藏依赖
组件集合并不是全部资源。全局随机数状态、事件队列、物理世界对象、单例缓存以及实体创建和销毁,都可能让两项看似无冲突的工作互相影响。应把共享资源也纳入读写声明,或者规定清楚的阶段边界;结构变化通常先写入命令缓冲,等迭代结束后统一提交。
验证时,至少检查三个条件:每条先后边对应的前驱确实已完成,同批 System 没有未保护的写入冲突,故意制造的反向依赖能触发环检测。依赖图的价值不是把所有系统串起来,而是只保留正确性真正要求的顺序,把其余执行空间留给调度器。