说实话我在很长一段时间里一直把操作系统里的前驱图和数据结构里的AOE网当成两门课里各自为政的概念一个用来讲进程并发一个用来算关键路径考试各考各的过了就散。直到有次复习操作系统我在“前驱图”那一页停住笔脑子突然蹦出数据结构课的AOE网才发现这俩东西的底层逻辑惊人地相似——甚至可以说它们都在做同一件事把看不见的时间画成看得见的形状。前驱图画的是“谁必须在谁之前”AOE网画的是“每件事要花多久整条链路哪里最卡”。一个是骨架一个是带秒表的骨架合在一起恰恰就是我对“时间的形状”最直观的一次理解。这篇随笔就是想把这条线彻底捋清楚适合正在学操作系统、数据结构或者正在准备考研408的朋友。如果你也经常把这两个概念搅在一起看完这篇文章你应该能像我一样把它们稳稳拆开又稳稳装回去。1. 为什么我会把这两个名词放在一起1.1 一次复习笔记的意外发现事情发生得很平常。我在回顾操作系统里进程并发那一章书上讲多个进程之间如果有先后约束就需要用前驱图来表示。我照着图画了一个小例子画完盯着图发呆忽然觉得不对——这张图长得怎么那么像数据结构里讲AOE网时画的工程图接着我往前翻发现AOE网那一章的标题附近总是跟着“拓扑排序”“关键路径”“最早发生时间”这些词。而操作系统的前驱图也一样要谈“前驱后继”“并行度”“程序顺序执行还是并发执行”。我开始把它们并排放在笔记本上越看越觉得这两幅图不是巧合撞脸而是同一个抽象思想在不同学科里的两次具象化。它们的共同本质都是有向无环图DAG。所谓无环就是不能出现A等B、B又等A的循环死锁所谓有向就是从“前”指向“后”用来表达一种不可逆的顺序关系。前驱图里是“前驱进程完成后后继进程才能开始”AOE网里是“这个活动做完那个事件才能发生”。顺序是一切时间感的基础。所以就有了这篇随笔的标题我看见了时间的形状。前驱图给时间搭了骨架AOE网给骨架标上了刻度。两者叠在一起就是一张可以计算的、有形状的时间地图。1.2 这篇笔记想帮你解决什么问题如果你现在脑子里是乱的我想帮你理清三件事。第一前驱图和AOE网各自的定义、画法、用途这是基础中的基础必须像背自己名字一样熟。第二它们之间的对应关系。前驱图里的顶点是进程或语句边是约束AOE网里的顶点是事件边是活动。这四个词如果搞混后面做题肯定翻车。很多人考试失分不是不会算而是把“顶点是什么、边是什么”搞反了一错全错。第三怎样从“会画”升级到“会算”。AOE网里的最早发生时间、最迟发生时间、关键路径本质上是一套动态规划算法在前驱图上的应用。你一旦意识到这一点再回头看操作系统里的进程调度、并行分析会通畅非常多。这篇随笔不是教科书式的系统讲解而是我站在学生的角度把我踩过的坑、想明白的道理、以及做题时真正管用的思路原原本本分享出来。你不需要有多深的基础只要知道图的基本概念跟上我的思路就行。2. 前驱图操作系统里最早画出的“先后关系”2.1 前驱图到底画的是什么前驱图也常被写作“前趋图”英文叫Precedence Graph。操作系统教材里它通常用来描述一个程序内部各条语句之间的执行约束或者一组并发进程之间的同步关系。我更喜欢把它理解成一张“入场券清单”每个节点进场之前必须确认哪些节点已经离场。具体定义是这样的每个结点代表一个进程、程序段或者一条语句通常画成圆圈。每条有向边代表两个结点之间的前驱关系。如果有一条从结点Pi指向结点Pj的边就说Pi是Pj的前驱Pj是Pi的后继记作Pi → Pj。执行规则是只有当Pi完成后Pj才能开始。如果Pj有多个前驱那么所有前驱都必须完成Pj才能启动。注意这里有个容易误解的点前驱图的边不是“数据流”也不是“消息传递”它只是一个纯粹的时序约束。即使两个进程之间没有任何数据交换只要你希望它们按某个顺序执行就可以用前驱图来表达。我一开始总是把前驱图理解成“程序的执行流向图”其实它不是。它是约束图不是流程动画。举个例子下面这几条语句S1a x 1S2b a 1依赖S1必须先算aS3c y 1独立不依赖任何人如果用一个单核CPU老实巴交地按顺序执行那就是S1→S2→S3一条线走到底效率不高。但如果告诉你S1和S3互不相干S2必须等S1那么S3完全可以和S1并行执行。于是前驱图可以画成S1和S3是并列的两个起点S2挂在S1后面。这种画法直接暴露了整个程序里哪些部分可以并行、哪些部分必须等待。2.2 一个能跑通思路的小例子我复习时常用一个更贴近生活的类比早高峰出门。P1起床必须先做P2洗漱必须等起床完成P3烧水起床之后就可以做不需要等洗漱P4吃早餐必须等洗漱和烧水都完成否则没法吃那么前驱图就是P1分叉出P2和P3P2和P3再汇合到P4。这个结构很有意思一方面它抓住了操作系统的核心追求——尽可能并行。P2和P3可以同时进行只要资源够。另一方面它也抓住了并发的底线——汇合处必须等齐。你不能P2没完成就坐到餐桌前也不能P3水没烧开就泡茶。这种“分叉-汇合”结构在操作系统里对应的就是进程派生和汇合。这就是为什么前驱图在操作系统里那么重要它能把“能不能并发”“最多能并发到什么程度”一眼看出来。我在做课后题的时候最常用的一个技巧是先看整个图里有多少条从起点到终点的路径然后数每条路径覆盖了哪些节点。两条平行路径意味着理论上可以并行但一旦某条路径里的节点是另一个节点的前驱那这条路径内部必须串行。前驱图给出的不是绝对时间而是相对时间的骨架。顺便提一个容易错的点如果前驱图里有环比如P1→P2→P3→P1那么这个程序永远无法启动因为每个进程都在等它前面的进程完成而前面的进程也在等它。操作系统里这叫循环等待严重时就是死锁的前奏。所以合法的前驱图必须是无环的。3. 从“先后”到“工期”AOE网把时间摆上了桌面3.1 AOE网的定义活动在边上事件在顶点前驱图解决的是“谁先谁后”但它有个天生的短板它不关心每件事要花多久。起床和烧水到底是1分钟还是10分钟前驱图一概不管。可在现实工程里时间就是钱时间就是命。于是数据结构的AOE网来了。AOE全称Activity On Edge直译就是“活动在边上”。它的定义刚好把前驱图的语义做了一次对称翻转顶点表示事件event它是一个时间点代表某些活动已经完成、后续活动可以开始的瞬间。边表示活动activity也就是需要花时间去做的事情。边上的权值表示这个活动需要持续的时间。注意这里又一个容易混的点前驱图里顶点是活动边是约束AOE网里边是活动顶点是约束。前者顶点有事做后者边有事做。如果把两者搞混后面算最早时间时你就不知道到底该把时长加在哪个头上。AOE网通常只有一个入度为0的顶点叫源点代表整个工程开始也只有一个出度为0的顶点叫汇点代表整个工程结束。这样设计是为了让我们能清晰地从起点一路算到终点。3.2 关键路径到底在找什么AOE网最著名的应用就是关键路径。很多人第一次听到“关键路径”都以为是最短路径我当时也一样心想既然是关键是不是要找一条最快的捷径完全不是。关键路径找的是最长路径。为什么是找最长因为一个工程的完工时间不取决于最快的部分而取决于最慢的部分。就像几个人一起搬货进仓库所有货都搬完才能收工那完工时间由最后搬完的那个人决定。AOE网里从源点到汇点有多条路径每条路径上的活动时间是累加的。整条路径的总时长就是这条路径的工期。工程整体要等所有路径都完成所以总工期等于这些路径时长的最大值。我举个例子你立刻就能懂。假设你早上要出门上班事件1开始活动A穿衣服耗时3分钟事件1→事件2活动B拿钥匙和手机耗时2分钟事件1→事件3活动C下楼耗时2分钟事件2→事件4活动D启动车耗时2分钟事件3→事件4活动E开到公司耗时10分钟事件4→事件5这样的事件图里从源点1到汇点5有两条路径1→2→4→53 2 10 15分钟1→3→4→52 2 10 14分钟总工期是15分钟而不是14分钟。关键路径就是第一条路径“穿衣服→下楼→开车”。这条路径上的任何一道活动只要慢1分钟整个上班时间就慢1分钟。而“拿钥匙和手机”那条分支上有1分钟的机动时间你可以多磨蹭1分钟而不影响总时间。这就是关键路径的直觉它是一串决定整体节奏的连续动作一旦卡住满盘皆输。4. 一个工程实例午休做饭也能讲清楚AOE网4.1 完整例子煮饭这件事里的关键链理论课看多了容易犯困我自己复习的时候喜欢把抽象概念套到每天都会做的事上。这里就用“做一顿午饭并上桌”来当一个完整的AOE网案例把计算过程完整过一遍包你能学会。假设你的午餐包含这么几件事活动A淘米耗时3分钟。事件1开工→事件2米已淘好活动B洗菜切菜耗时4分钟。事件1开工→事件3菜料已备好活动C煮饭耗时10分钟。事件2米已淘好→事件4饭已煮熟活动D炒菜耗时7分钟。事件3菜料已备好→事件4菜已炒好和饭同步完成活动E装盘上桌耗时2分钟。事件4饭和菜都好了→事件5开饭注意活动之间有个依赖关系炒菜不要求饭煮熟煮饭也不要求菜切好但最终要开饭必须等这两条分支都汇合到事件4。于是这个AOE网里有两条路径路径一事件1→事件2→事件4→事件5耗时3 10 2 15分钟路径二事件1→事件3→事件4→事件5耗时4 7 2 13分钟总工期15分钟。路径一就是关键路径活动A、C、E是关键活动。4.2 手把手计算最早、最迟和关键路径光知道哪条路径长还不够考试和实际项目里我们还需要知道每个事件最早什么时候能发生、每个事件最晚什么时候必须发生以及每个活动有多少机动时间。我下面完整算一遍你照着这个步骤走AOE网的计算题基本就不会再慌。第一步正向求每个事件的最早发生时间Ve。规则很简单从源点开始源点的最早发生时间定义为0。如果一个事件只有一个前驱那它的最早发生时间等于前驱事件的最早时间加上活动耗时如果有多个前驱就取最大值。为什么取最大因为这个事件必须等所有前置活动都完成才能发生所以要以最慢的那个为准。好我按图推一遍事件1Ve(1) 0事件2只有前驱事件1活动A耗时3Ve(2) 0 3 3事件3只有前驱事件1活动B耗时4Ve(3) 0 4 4事件4有两个前驱。从事件2来Ve(2) C耗时10 3 10 13从事件3来Ve(3) D耗时7 4 7 11。取最大值13所以Ve(4) 13。事件5只有前驱事件4Ve(5) 13 2 15。所以整个工程最早15分钟完工这验证了我们前面对两条路径时长的判断。第二步反向求每个事件的最迟发生时间Vl。从汇点倒着往前推。汇点的最迟发生时间就等于它的最早发生时间因为整个工程不能往后拖。然后一个事件如果有多条后继它的最迟时间等于后继事件的最迟时间减去活动耗时再取最小值。为什么取最小因为要保证所有后续活动都能按时开始这个事件必须赶在最早的截止时间前发生。事件5Vl(5) Ve(5) 15事件4只有后继事件5活动E耗时2Vl(4) 15 - 2 13事件2只有后继事件4活动C耗时10Vl(2) 13 - 10 3事件3只有后继事件4活动D耗时7Vl(3) 13 - 7 6事件1有两个后继。一个到事件2Vl(2) - A耗时3 3 - 3 0另一个到事件3Vl(3) - B耗时4 6 - 4 2。取最小值0所以Vl(1) 0。源点最迟发生时间算出来还是0这很合理因为源点不能拖延拖延了整个工程就晚了。第三步求每个活动的机动时间松弛时间找出关键活动。活动的机动时间公式是后继事件的最迟发生时间 - 前驱事件的最早发生时间 - 活动本身耗时。如果一个活动的机动时间是0那它就是关键活动一天都不能歇。活动AVl(2) - Ve(1) - 3 3 - 0 - 3 0机动时间0关键活动。活动BVl(3) - Ve(1) - 4 6 - 0 - 4 2可以晚开工2分钟不影响全局。活动CVl(4) - Ve(2) - 10 13 - 3 - 10 0关键活动。活动DVl(4) - Ve(3) - 7 13 - 4 - 7 2有2分钟机动。活动EVl(5) - Ve(4) - 2 15 - 13 - 2 0关键活动。于是关键路径就是由活动A、C、E组成的也就是15分钟的那条线路。这条路径上的每个活动都不能出岔子。所谓“看见时间的形状”在这一刻变得具象了时间不是均匀流动的河而是一张网上的一串最紧绷的链子只有关键路径真正的绷着。我把上面这些计算整理成一张速查表用的时候直接照抄。事件最早发生时间Ve最迟发生时间Vl说明事件100源点不能拖延事件233淘米完成无机动事件346备菜完成有2分钟机动事件41313饭和菜都好了无机动事件51515汇点决定总工期5. 两幅图的灵魂是同一个偏序与无环5.1 偏序关系的形状前面我们分别看完了前驱图和AOE网现在把它们拉到一起对比一下你会发现一个更本质的东西它们表达的都是偏序关系。什么叫偏序关系就是一组元素之间部分两两可比但未必全部可比。用大白话说有一些东西之间有先后顺序但有一些东西没有先后顺序它们可以并行。前驱图里S1在S2之前这是确定的但S1和S3谁先谁后无所谓它们只是没有关系。AOE网里淘米必须在煮饭之前这是确定的但煮饭和洗菜之间没有强制顺序。这种“一部分有序一部分无序”的状态就是偏序。我们日常感受到的时间好像是一条笔直的线早晨接着中午接着晚上但在计算机的世界里在工程的调度中很多事件之间的关系不是一条线而是一张网。这张网里的某些点之间根本没有先后可言。偏序关系画出来就是“有形状的时间”它不是直线而是分叉、汇合、交错的一张复杂网络。5.2 拓扑排序把“时间的形状”拉成一条直线偏序虽然看起来乱但我们可以用一种算法把它拉直这个算法就叫拓扑排序。拓扑排序做的事情就是给一个有向无环图的所有顶点排出一个线性序列使得对于每条边Pi→PjPi都排在Pj前面。这就像你把一张交错的关系网拽成一条可供流水线执行的清单。这一步是连接前驱图和AOE网的关键桥梁。操作系统要把并发程序真正跑起来不可能真的让所有进程同时出生、同时调度它得按照前驱图的约束给进程分配CPU而分配顺序的确定本质上就是一个拓扑排序问题。数据结构里在做AOE网的关键路径计算之前也通常要先做拓扑排序以保证所有前驱事件的最早发生时间都已经算完后续事件才能开始计算。我自己的体会是拓扑排序就是时间从“网状”到“线状”的一次投影。它把藏在图里的先后关系暴露成一张顺序表让机器能执行让人能检查。这就像你把一屋子人的复杂站队关系拍成一张合影排得整整齐齐谁高谁低一目了然但实际上每个人之间的关系网络比照片复杂得多。这里也顺便回答一个常见疑惑为什么前驱图和AOE网都要求“无环”因为环一出现偏序就变成了循环依赖拓扑排序根本排不出来。这有点像生活中你让别人给你提意见别人说要先问A你去找AA说要先问BB说你先问A——永远没有头。无环是“时间的形状”能够成立的最基本条件。6. 从图结构到算法它们如何串起两门课6.1 操作系统进程并发中的前驱约束操作系统里的前驱图最典型的使用场景是表现一个程序内部语句级别的并发可能。课程里常提到的Bernstein条件用来判断两条语句到底能不能交换执行顺序、能不能并发其实也可以用前驱图辅助理解。如果你有一组语句它们之间没有任何数据依赖比如一个算axby一个算cxdy这两个计算完全独立那么在前驱图里它们就是两个没有边连接的节点天然可以并行。反之如果第二条语句的输入依赖第一条语句的输出前驱图里就必须有一条边硬要并行就会得到错误结果。学操作系统时我会刻意训练自己拿到一段包含多条语句的代码先画它的前驱图然后问自己三个问题图里有多少条从入口到出口的路径这决定了理论上的最大并行度。哪些节点是汇合点汇合点意味着同步等待是并发的瓶颈。如果把某些节点挪到不同CPU上执行前驱图的边会不会导致某个CPU空等这套训练做完之后再看进程调度、PV操作、信号量这些章节会有一种打通的感觉。因为所谓的同步互斥本质就是为了保证前驱图里的“前驱-后继”关系在实际执行时不被打乱。6.2 数据结构算法中的图遍历与动态规划AOE网的计算放在数据结构的视角下看其实涉及两类核心算法思想一类是图论基础的拓扑排序另一类是动态规划。你注意看我们在第4节计算最早发生时间的过程它从源点出发逐个事件往后推进后一个事件的最早时间依赖于前一个事件的最早时间。这个“子问题的最优解 - 更大问题的最优解”过程就是动态规划的标准套路。它和求有向无环图的最长路径几乎是一模一样的。再仔细体会一下就会明白关键路径问题的本质是DAG上的最长路径问题。我还记得当时突然明白这一点时的心情数据结构课上讲的关键路径原来不是孤立的一个考点它就是动态规划的一个典型应用。只是很多教材把它放在图这一章没明确提动态规划这个词。后来我做考研真题时遇到“给出AOE网求关键路径”的题心里就有底了这不就是一个正向动态规划加一个反向动态规划再加一次扫描吗为了让你快速核对自己有没有掌握整套流程我列一个标准答题步骤检查图中是否有唯一的源点和汇点没有的话先补全。对图做一次拓扑排序如果排不出来说明图有环题目条件不成立。从源点开始正向计算每个事件的最早发生时间Ve多个前驱取最大值。从汇点开始反向计算每个事件的最迟发生时间Vl多个后继取最小值。对每条边和每个活动计算机动时间机动时间为0的活动构成关键路径。这个流程我建议你自己动笔走一遍不要盯着看看十遍也不如手写一遍。当初我就是靠着反复手算上面这套午饭例子才彻底把AOE网的细节吃透。7. 我踩过的坑和给初学者的建议7.1 最容易混淆的三种错误第一类错误也是最经典的把前驱图和AOE网的语义记反。前驱图是“顶点任务边约束”AOE网是“边活动顶点事件”。有同学做题时看到AOE网里有顶点就默认顶点是任务结果把活动时间全部算到顶点上整个关键路径错得离谱。我的办法是死记一句话AOEActivity On Edge活动是在边上的记住Edge就够了。第二类错误多个前驱取max还是取min搞反。正向求最早发生时间多个前驱取最大值因为都要完成反向求最迟发生时间多个后继取最小值因为每个后继都不能耽误。我建议不要死记结论而是回到物理意义去感受。一个事件“最早”能发生必须等最慢的前驱走完所以取大一个事件“最迟”能发生必须赶最快的后续截止时间所以取小。想通这个物理含义就不会再混淆。第三类错误总把关键路径理解成最短路。如果抱着“找捷径”的心态去做这道题会有一种强烈的不安感。要记住工程总工期 最长路径不是最短路径。最短路径在AOE网里只是一个美好的愿望但现实工程必须等最慢的人。你可以想象一群人去赶火车集合时间不由跑得最快的人决定而由收拾行李最慢的那个人决定。关键路径就是那个“收拾行李最慢的人”组成的连续链路。7.2 复习时的高效思路如果你和我一样平时边学操作系统边学数据结构我强烈建议你做一件事把这两个知识点放在同一张复习纸上对比着背。左边画前驱图右边画AOE网中间写它们的公因子“有向无环图、拓扑排序、偏序关系”。这样做的好处是你对这两个概念的印象会从“两个考点”升级为“一个模型的两种应用”记忆负担反而更小。还有一个心得别满足于看懂例题要能自己造题。我复习到后半段经常自己编一个小工程画出一个AOE网然后不看答案算出所有事件的最早、最迟时间和关键路径。自己出题比做题更能暴露理解漏洞。比如我会故意设计两条汇合路径让其中一条正好比另一条多1分钟看看关键路径会不会变。这种微调式的出题法能让你把计算方法掌握得极其扎实。最后提醒一下如果考场上你花了很多时间都没能找出关键路径可以先看看有没有哪个事件的最早发生时间和最迟发生时间不同。不是0机动时间的活动就可以排除掉剩下的不多了。这是我实战中觉得最省时的小技巧。8. 最后你说“看见时间的形状”那到底看见了什么写到这里我想把自己最真实的感受放在最后。以前我总觉得“时间”是一个哲学词看不见摸不着。但学了前驱图和AOE网之后我发现计算机学科给时间提供了一个非常硬核的模型时间不是一个均匀流动的东西而是由事件之间的偏序关系、活动之间的依赖链路共同刻出来的结构。前驱图把“谁在谁后面”画出来AOE网给每段关系标上代价关键路径再把那个真正卡住全部节奏的链条找出来。时间在这套模型里有结点、有边、有权值有最长路径和机动时间——它真的可以被画出来被算出来被优化出来。我个人在复习过程中最大的收获不是会做几道考研题而是学会了用一种“图”的眼光看待任务安排。不管是写代码、做项目、还是安排日常琐事我都习惯了先问一句哪些事是强依赖哪些事可以并行哪条链路最不能拖延这慢慢变成了一种思维方式。AOE网的关键路径让我意识到忙碌不等于高效真正重要的是识别出那几件决定整体节奏的事然后盯紧它们。最后再分享一个小技巧如果你也想体验一次“看见时间的形状”可以拿自己周末的一天画一张AOE网。起床、洗漱、早饭、出门、见朋友、买菜、做饭每件事标上预估时间画好依赖关系然后找出你的关键路径。你会发现那些让你周末匆匆忙忙的往往不是全部事情而是某一条被卡住的链路。看懂了这张网你就能在现实中主动留下了那条链路而给其他事情留出机动时间。