4、并行启动理论基础：有向无环图(DAG)在服务依赖管理中的应用，并行度与资源竞争。

嵌入式Linux启动优化的核心在于将传统的串行启动序列转变为高效的并行执行。然而，服务之间并非独立，它们存在复杂的依赖关系。盲目并行会导致启动失败或系统不稳定。本章将深入探讨并行启动的理论基石——有向无环图（DAG），并分析并行度与资源竞争这两个关键约束。

4.1 服务依赖关系的数学建模：从串行列表到有向图

在传统的SysVinit系统中，启动脚本通过编号（如 S01syslog、S10network）隐式定义了执行顺序。这种线性列表无法表达“A和B可以同时启动，但C必须等A和B都完成”这类复杂关系。

我们将每个服务视为一个节点（Node），服务间的依赖关系视为有向边（Directed Edge）。例如，“服务B必须在服务A之后启动”表示为 A → B。这样，整个系统的启动依赖就构成了一张有向图。

下图展示了一个典型的嵌入式系统服务依赖关系，其中 syslog 和 network 无相互依赖，可以并行启动；httpd 依赖 network；app 依赖 syslog 和 network 两者。

4.2 有向无环图（DAG）与拓扑排序

为了保证并行启动的正确性，依赖图必须是一个有向无环图（DAG）。DAG保证了我们可以找到一个拓扑排序——即所有节点的一个线性序列，使得对于每一条有向边 U → V，在序列中 U 都出现在 V 之前。

拓扑排序是并行调度的基础。算法上，通常使用Kahn算法（基于入度）或DFS深度优先搜索来实现。Kahn算法的核心步骤：

1. 计算所有节点的入度（指向该节点的边数）。
2. 将所有入度为0的节点加入就绪队列（这些节点没有前置依赖，可以立即启动）。
3. 从就绪队列取出一个节点，将其标记为“已调度”，并移除其所有出边；将因此入度变为0的邻居节点加入就绪队列。
4. 重复步骤3，直到所有节点都被调度。如果最终仍有节点未被调度，说明图中存在环。

4.3 并行度：理论上限与实际约束

并行度指在任意时刻可以同时启动的服务数量。理论上，DAG中同一层级的节点（即所有前置依赖都已满足的节点）都可以并行启动。最大并行度受限于DAG的宽度（最宽层级的节点数）。

然而，实际并行度受到以下因素的制约：

下图展示了不同并行度策略对启动时间的影响。理想情况下，并行度越高，启动时间越短，但受限于资源竞争，实际曲线存在一个最优并行度。

4.4 资源竞争：并行启动的“隐形杀手”

资源竞争是并行启动优化中最容易被忽视的问题。即使DAG调度正确，多个服务同时访问同一资源也会导致：

• I/O抖动： 并发读取不同Flash分区时，NAND/ eMMC的随机读取性能远低于顺序读取，导致每个服务的启动时间都显著延长。
• CPU缓存污染： 服务A和服务B频繁切换执行，导致L1/L2缓存命中率下降，CPU执行效率降低。
• 内核锁竞争： 多个服务同时进行 open()、ioctl() 等系统调用，可能在内核层面竞争同一锁（如inode锁、内存管理锁）。

4.5 实践：构建嵌入式系统的DAG调度策略

在实际的嵌入式Linux启动优化中，我们通常采用以下步骤来应用DAG理论：

1. 服务依赖审计： 列出所有启动服务，明确每个服务的 After=、Requires=、Wants= 依赖。
2. DAG构建与环检测： 使用工具（如 systemd-analyze dot）生成依赖图，检查是否存在循环依赖。
3. 层级划分： 根据拓扑排序结果，将服务划分为多个启动阶段（Stage）。同一阶段内的服务无相互依赖，可以并行启动。
4. 资源感知调度： 对访问同一硬件资源（如SD卡、网络接口）的服务，在它们之间插入同步点或使用资源槽（Resource Slot）机制，避免同时访问。
5. 动态并行度调整： 在启动初期（内核刚完成初始化，I/O带宽充裕）使用较高的并行度；在启动后期（内存紧张，服务竞争加剧）适当降低并行度。

下表对比了不同并行调度策略在典型嵌入式场景下的效果：