期中周的那个深夜我左手压着操作系统的教材右手摊开数据结构的复习讲义。一边是前驱图的判断题一边是AOE网的关键路径大题我本来只想把这两页一起看掉省得来回翻书结果越看越不对劲——怎么它们画出来的东西长得那么像那是我这个学期第一次强烈地感觉到操作系统和数据结构并不是两门割裂的课它们只是在用不同的尺子量同一张图。而那张图画的正是时间的形状。如果你也正在学这两门课或者已经学过但当时没想通我建议你耐着性子看完这篇随笔。我不打算搞成标准讲义只想顺着那次复习的顿悟把前驱图和AOE网放在一张桌子上讲清楚它们各自是什么、为什么能被我硬看成同一个东西以及这个看穿的视角对后续学操作系统、做系统设计到底有什么用。1. 那个晚上两本教材的同一张图很多教材在讲进程同步之前都会先花小半页提一下前驱图。它看起来特别像一个用于描述程序段之间先后关系的箭头图几个圆圈几个箭头然后告诉你P1必须在P2之前执行P2必须在P3之前执行。当时我并没有太当回事觉得这不就是把流程图画出来了嘛有什么可讲的结果真到了做操作系统作业的时候才发现越简单的工具越容易被低估。另一边数据结构里的AOE网就惨多了。它属于图论那一章的最后一块内容前面你已经熬过了邻接矩阵、邻接表、最小生成树、最短路径到AOE网的时候整个人基本是麻的。教材上又是一堆像蜘蛛网一样的图边上写着一堆数字紧接着就是关键路径ve、vl、e、l四个数组的定义和公式。我当时只求套公式能算对压根没想过它还有什么更深的含义。1.1 前驱图教材里被匆匆带过的一张图前驱图Precedence Graph的定义其实很朴素用一个有向无环图DAG来表示多个程序段或进程之间的前驱关系。图中的每个顶点可以是一个语句、一个程序段或者一个进程每条有向边表示前驱与后继的约束比如从顶点Pi画一条边指向Pj就意味着Pj只有在Pi完成之后才能开始。我最初对这个定义有点轻蔑因为它实在太像流程图或拓扑排序题了。但真正让我改观的是它的使用场景操作系统里想表达一组进程能不能并发执行时前驱图几乎是唯一能把约束关系画清楚的工具。你光用文字描述进程B要等进程A进程C又不等进程B一句话就绕晕了但画成图一眼就能看出谁跟谁没有边相连没有边相连就意味着它们在逻辑上没有前后依赖可以被调度器放到不同CPU核上同时跑。这个没有边就能并发的特点是我后来理解整个操作系统的并发模型的第一块基石。没有它信号量、互斥锁、条件变量全都是零散的API有了它这些同步机制就全部变成了如何把前驱约束转化成阻塞和唤醒的工程问题。1.2 AOE网期末复习时绕不开的关键路径AOE网的全称是Activity On Edge network也就是边表示活动的网。它的顶点表示事件有向边表示一个活动边上的权值表示该活动的持续时间。因为活动都被放到了边上所以AOE网常用于估算一个工程的最短完成时间并找出哪些活动拖不得拖一天就拖垮整个工期这些活动连成的路径就叫关键路径。我当时复习到这一节时已经是一脸疲惫。AOE的计算套路不难难的是容易忘先拓扑排序再正向算ve反向算vl然后算每个活动的e和l最后找l减e等于0的活动连起来就是关键路径。步骤本身非常机械但恰恰因为机械很多同学包括我会不自觉地放弃思考只把它当成一道套公式的题。但那个晚上当我看着AOE网里的那些箭头时脑子里突然闪过一个念头这不就是前驱图吗AOE网也有顶点也有有向边也是无环的边也代表两个顶点之间的先后关系。唯一比较大的区别是AOE的边上多了一个数字——时间。这个多了一个数字的地方恰恰就是我那天晚上最大的顿悟来源。1.3 啪的一下它们在我脑子里叠在了一起我先在草稿纸上画了一个最普通的前驱图P1发出箭头指向P2和P3P2和P3又分别指向P4。然后我在旁边画了一个同样结构的AOE网顶点一、顶点二之间连了一条带权值的边继续往下到汇点。去掉边上数字之后两张图几乎完全重合。我愣了好几秒因为在我当时的认知里操作系统是操作系统数据结构是数据结构它们像两个大抽屉里面分别装着进程调度和图算法两堆零件。但那一个瞬间抽屉的隔板消失了原来操作系统里描述进程间先后的前驱图本质上就是数据结构里AOV网的一种实例而AOE网则是在这个骨架之上给每条依赖关系加上了时间成本——这哪里是什么两门课这就是同一张时间地图的两种画法。从那以后我再看任何带依赖关系的系统第一反应都是先画一张DAG。这个习惯帮我省了无数脑子。2. 前驱图到底想表达什么一组进程的出场顺序要真正把前驱图和AOE网放在一起我们得先把前驱图这层窗户纸捅破看清楚它到底在描述什么。很多操作系统教材把前驱图放在进程的描述与控制那一章位置靠前篇幅不大但它的作用很像乐高积木的基座后面所有的并发问题都是从谁先谁后这个基座上长出来的。2.1 顶点是程序段箭头是必须等前驱图里最基本的语义就是必须等。画一条从A到B的有向边代表如果事件A没有完成事件B就不能开始。这里的A和B不一定非得是进程也可以是几条语句、几个子程序甚至一次磁盘I/O和一次CPU计算。也就是说只要你愿意完全可以把一个人写代码时的提交流程画成一张前驱图。正因为这个语义足够轻所以前驱图能描述的范围特别广。比如你在一个程序里有五个程序段段之间有各种数据依赖你可以把依赖关系全部画进图里调度器和编译器看到这同一张图能做的事情完全不一样——理解这一点是读懂前驱图的关键。2.2 用手画一遍这五条语句的前驱关系我们不用教材里那些抽象的P1、P2换一个更生活化的例子。假设有这五条赋值语句S1: a x 1S2: b a 2S3: c y 1S4: d b cS5: e a * b表面上看它们只是五句话但仔细分析数据依赖就能发现S2要用到a所以S2必须等S1先算完S3用的是y不依赖前面的任何结果它和S1、S2之间没有约束S4要用b和c必须等S2和S3都完成S5要用a和b必须等S1和S2完成。把这些依赖画成前驱图就是这个样子S1指向S2S2指向S4和S5S3指向S4。图中没有任何一条边连在S1和S3之间这意味着S1和S3是相互独立的程序段理论上可以同时执行分给两个CPU核去跑完全没问题。读到这里你可能发现了前驱图并不仅仅是排队图它同时还是并发机会的探测器两条边没有交集的地方就是可以被并行化的地方。2.3 前驱图最终回答的是能不能并发吗更准确一点说前驱图回答的是在逻辑上能不能并发执行。注意逻辑上三个字这是我和很多同学踩过的一个坑。前驱图里没有时间轴它不关心S1执行要3毫秒还是30毫秒不关心CPU有几个核也不关心内存带宽够不够。它只告诉调度器从依赖关系来看S1和S3之间不互相欠账你有权把它们放到同一时刻的两个核上至于实际跑起来哪个先完成、能不能真的提速那是调度策略和硬件资源的问题。这个区别非常重要因为它是前驱图与AOE网之间最本质的那道分界线。前驱图说可以或者必须先AOE网却在每条依赖边上补上了要花多久。你想想如果一个人只知道哪些事能做却不知道每件事要多久那他就永远算不出整个工程什么时候能完成。从能不能到多久思维层面是一个大台阶而迈上这个台阶的桥梁就是AOE网。3. AOE网把工程的耗时一条一条算到边上如果说前驱图是一张纯结构的依赖图那么AOE网就是给它注入了时间。数据结构里讲AOE网时通常会从AOV网引出AOV网的顶点表示活动边只表示活动之间的偏序关系AOE网则反过来边表示活动边上的权值表示活动耗时。这个反一下曾经让我很别扭但后来我发现正是因为活动被放到了边上AOE网才能把一个工程的总工期直观地摊在图中让人一眼看出时间都花在了哪里。3.1 AOV是排队AOE是计时AOV网Activity On Vertex你可能更熟悉它是拓扑排序那节的主角。AOV网里顶点代表各种活动比如课程表里学完高等数学才能学线性代数边只是一条先后约束没有数字。前驱图从数据结构的角度看完全可以视作AOV网的一个具体实例进程也就是活动箭头就是必须先修。AOE网则完全是另一种气质。它把活动当成边把顶点当成事件。什么叫事件就是一条或几条活动完成的瞬间。比如说一个工程的基础施工完成就是一个事件它发生在地基开挖和材料进场这两项活动都结束的那一刹那。事件本身不耗时耗时的是活动。理解这个转变后AOE网的核心问题就变得很自然既然整个工程是由一条条有依赖关系、有耗时的活动组成的那整个工程最早什么时候能全部完工要压缩工期应该优先压缩哪些活动答案就是找到关键路径也就是从源点到汇点之间权值之和最大的那条路径因为整条链上任何一个活动拖延都会直接导致总工期拖延。3.2 ve、vl、e、l四个数组的完整推演很多教材给AOE网的计算步骤写得非常干瘪新手看过去全是字母。我这里借着复习时的笔记把这个过程按我自己的理解重讲一遍尽量讲成人话。第一步给图中每个顶点算两个时间ve[i]表示事件i的最早发生时间vl[i]表示事件i的最迟发生时间。ve从源点开始沿着拓扑序向后推源点的ve是0每个顶点的ve等于它所有前驱顶点的ve加上对应活动耗时然后取最大值。为什么取最大因为一个事件往往要等好几条活动线都完成才发生必须等最慢的那条所以取众前缀路径里最长的耗时这就是最早的真实含义。vl则是从汇点倒着推汇点的vl等于它的ve然后用后继顶点的vl减去活动耗时来更新当前顶点的vl取最小值。为什么取最小因为你虽然不能晚于某个时间点但这个时间是受后面一系列活动倒逼出来的后路越紧张当前事件能容忍的余地就越小一旦某个后继活动很关键当前事件就必须留出足够提前量。有了ve和vl再算每个活动a的e和l。活动a是顶点i到顶点j的一条边权重为w那么活动a的最早开始时间e就是ve[i]最晚开始时间l就是vl[j] - w。最后看l - e等于0的活动就是关键活动一点缓冲都没有一拖就拖垮总工期大于0的活动说明有富余时间晚一点开始也不影响整体。把这些关键活动串起来就是关键路径。3.3 手工计算一份完整的AOE网光讲定义不够我把自己考试前手算过的一个例子贴出来。假设有一个AOE网共6个顶点、8条活动a1: 1 - 2耗时3a2: 1 - 3耗时2a3: 2 - 4耗时2a4: 3 - 4耗时4a5: 2 - 5耗时3a6: 3 - 5耗时2a7: 4 - 6耗时2a8: 5 - 6耗时1第一步拓扑排序顺序为1、2、3、4、5、6。接着正向算veve[1]0ve[2]033ve[3]022ve[4]max(ve[2]25ve[3]46)6ve[5]max(ve[2]36ve[3]24)6ve[6]max(ve[4]28ve[5]17)8。反向算vl时先把vl[6]设为ve[6]8往前倒推vl[5]8-17vl[4]8-26vl[3]min(vl[4]-42vl[5]-25)2vl[2]min(vl[4]-24vl[5]-34)4vl[1]min(vl[2]-31vl[3]-20)0。最后把活动参数列一张表活动边耗时well-e是否关键a11-23011否a21-32000是a32-42341否a43-44220是a52-53341否a63-52253否a74-62660是a85-61671否关键活动是a2、a4、a7连成路径1 - 3 - 4 - 6总工期8个单位。这条路径上任何一项活动多耗一天整个工程就晚一天而其他活动哪怕稍微拖一点还有缓冲兜底。算完后我对关键路径这四个字服气了它不是一道考试题它就是所有带依赖的工程里命门的别名。4. 同一个有向无环的骨架问的是两个世界的事到这里前驱图和AOE网在结构上的高度重合已经没什么可避讳的了它们都是DAG都有顶点都有有向边拓扑排序都对它们有效。区别在于前驱图的边是纯约束AOE网的边是约束加成本。这个差别看起来只是多写一个权重但就是因为这个权重两个图开始回答完全不同的问题。4.1 相同的DAG骨架先列一个能帮你看得很清楚的对比表。这张表是我复习到后来自己总结的比对着两本教材抄定义有用得多维度操作系统前驱图数据结构AOE网顶点含义程序段、进程、语句事件活动完成的瞬间边含义前驱/后继约束一个活动且带耗时边权无活动的持续时间核心问题哪些程序段可以并发必须遵守什么顺序整个工程最短耗时哪些活动拖不得最怕什么有环导致死锁或无法调度关键路径上的活动延误常用算法拓扑排序、偏序分析拓扑排序、ve/vl递推、关键路径查找看见没有骨架是完全一样的。即使是在具体场景里前驱图也可以画成AOE网的样子——只要你在每条依赖边上标上耗时一个进程结构瞬间就变成了一个可以做工期估算的工程网络。我后来甚至觉得操作系统的教材里之所以不讲AOE只是因为它和数据结构各司其职不想重复害得我们要靠自己去把两块知识拼起来。4.2 前驱图回答能不能AOE网回答多久前驱图的典型用途是把进程之间的先后关系理清楚好让调度器决定谁和谁可以并行。它回答的是能不能带点逻辑的意味。你见过的最典型例子就是生产者-消费者模型生产者在前消费者在后中间用一个缓冲区隔开前驱关系明明白白至于生产一个数据要花多久、消费一个要花多久前驱图不关心。AOE网则自带成本视角它回答的是多久。同样一张依赖图一旦把每项活动的时间标上去问题就从谁先谁后进化成了整个流程最多需要多少时间和哪些环节是瓶颈。为什么要重视瓶颈因为非瓶颈环节你优化到飞起总工期可能纹丝不动瓶颈环节哪怕只优化一天整个项目就能提前一天交付。这就是关键路径的意义也是所以工程管理者都需要它的原因。4.3 拓扑排序两门课共享的解题起手式不管前驱图还是AOE网你拿到的第一反应都应该是同一个动作先做拓扑排序检查有没有环。检查有环这个动作在前驱图里尤其重要因为如果进程之间存在循环等待关系那意味着谁都在等别人先完成这在操作系统里就是死锁的前兆在AOE网里有环则意味着工程描述自相矛盾根本无法计算合理的工期。我之所以强调这个共享起手式是因为它直接暴露了知识体系的统一性。你在数据结构课上辛辛苦苦学的拓扑排序到了操作系统里依然是核心工具你在操作系统里见到的进程依赖图到了数据结构里依然是图算法处理的经典对象。很多同学觉得课程之间没关联其实只是因为缺少一个把知识点交叉引用的动作。如果你正在学这两门课我强烈建议你学完数据结构图的章节之后回到操作系统重新看一遍前驱图和信号量你会发现整个知识脉络突然就通了。5. 时间的形状从串行到并发一条时间线怎么长成了一张网标题里那句我看见了时间的形状并不是修辞夸张。如果你只接触单核时代的程序时间确实是直线指令一条一条执行总耗时等于所有指令耗时相加没有分叉没有并行时间像一根面再怎么拉也只有长度。但一旦进入并发和分布式系统时间就不再只是一根面了它会分叉、会汇合、会互相等待最终变成一张网。5.1 串行时代的时间是一条线单核单进程的时代程序执行路径非常单纯CPU按指令顺序走完一条线这条路的总耗时就是把所有步骤的耗时加起来。你不需要画图因为根本不存在分叉。这也是我们最早建立的时间直觉——总时间等于每项时间之和。但这条直觉在面对现代计算机时会崩。现在的机器有多个CPU核心一个程序可能开好几个线程几个线程之间还有依赖关系。这时候你如果还把所有耗时全部线性相加算出来的时间不仅偏大而且完全看不出哪里有可能并行、哪里有瓶颈。换句话说线性时间的直觉在并发世界里已经失效了。5.2 并发系统的时间是织物一旦允许并行时间就变成了织物它在某些点分叉在另一些点汇合。前驱图就是这块织物的纬线画出哪些线能并排走哪些线必须交错等待AOE网则是给纬线标上了长度。你盯着这张网看会看到时间的流动方式有的支路快早早汇入主线有的支路慢压着整段工程的完成点而那些怎么拖都直接导致总工期延后的活动就是织物的主骨架。我特别喜欢时间的形状这个说法是因为它把工程和算法从抽象符号变成了空间里的实体。你看一张AOE网时可以把自己想象成站在源点沿着每一条边向前走。最轻松的路不一定让你第一个到终点最长的路才决定了整个井口什么时候冒出光。时间在这个图里不是流动的液体而是被约束出的形状——受制于依赖、受制于瓶颈、受制于每一条边上的代价。5.3 木桶最慢的那块板决定整个工程的进度用木桶效应来解释关键路径是最容易懂的版本一个木桶能装多少水取决于最短那块木板一个AOE网里的工程要多久完工取决于最长那条路径。你可以把其他所有路径优化到飞起但只要关键路径不动总工期一寸都不会缩短。这种思维放到生活里也很有意思。比如做饭招待朋友洗菜10分钟、切菜8分钟、煮饭20分钟、炒菜12分钟。如果洗切炒是完全串行那就是50分钟但如果煮饭的20分钟可以和其他准备并行整个流程的关键路径就会大幅缩短。你再仔细排一排发现关键是煮饭那条支路和炒菜那条支路谁更长于是你会主动调整动作的先后顺序让耗时长的支路尽早开始。这不就是AOE网的现实投影吗我从那以后每次看到时间管理教程里画任务依赖图都会忍不住用ve/vl算一遍看看到底哪些事是真正的关键活动。6. 把这两张图落进真实的项目与复习建议说到底前驱图和AOE网不是只存在于教科书里的名词。操作系统里的同步原语项目管理里的关键路径法甚至你平时排自己的日程都可以用它们作为思考工具。最后这部分我把自己的实践和踩过的坑一起写出来希望对正在学习的你有点用。6.1 前驱图怎么变成真实的同步代码在操作系统里前驱图中谁必须等谁最终要落实成代码常用的手段就是信号量。比如图里有一条边从P1指向P2那你就在这条边上放一个初值为0的信号量P1结束时执行V操作让信号量加一P2开始前执行P操作阻塞等待。多个前驱时需要在每个前驱完成后都V一次后继方能通过。这个套路看似极简但几乎所有经典同步问题都可以用它推演出来生产者-消费者、读者-写者、哲学家就餐本质上都是在处理一张前驱图的边。我自己曾犯过的一个错误是只考虑了图的一部分边漏掉了某条隐式的依赖结果程序在真实环境下偶发崩溃。后来我养成了一个习惯写多线程代码之前先在草稿纸上画出线程间所有必须等和可以并行的关系确认没有环、没有漏边再动手写同步代码。这个习惯帮我省下的调试点时间比我数据结构作业里画的所有图都要多。6.2 AOE网在项目管理里的位置AOE网的思想在真实世界里并不叫AOE而叫关键路径法CPM。工程项目管理中人们会把任务拆成一个个带工期、带依赖的活动画出网络图找出关键路径然后集中资源去优化那些关键活动。这正是AOE网在数据结构之外的另一重身份。很多时候算法书上那些算完就完事的代码落地到现实中就是另一种语言的名字这也是我为什么坚持说通一门课要往别的课里看一眼。如果你以后要在团队里排开发计划可以试着把任务拆成DAG给每条依赖标上预估耗时然后用ve/vl手工排一遍找出真正决定里程碑的关键路径。你会发现很多看似紧急的杂活根本不在关键路径上真正需要盯的永远是那条最长链条上的人和事。6.3 一些能让你少走弯路的复习建议第一画图永远比背公式重要。前驱图你要能自己画出五条语句谁依赖谁的实际例子AOE网你要能独立算出一个题目的ve、vl、e、l表格而不是只看着教材的例题点头。第二计算时务必先拓扑排序。我吃过亏在没检查环的情况下直接算ve结果得到错误结果。拓扑排序不只是为了排序它是保证递推顺序合理的前提只有前驱都处理完后继才能用上正确的前驱最大值。第三分清事件最早发生时间和活动最早开始时间。事件ve是所有前驱活动全部完成的那个时刻活动e则是它的起点事件已发生就能立刻开工的时刻。很多人c在算e时直接套用vl端点导致前后矛盾其实e永远等于起点事件的vel永远等于终点事件的vl减去边权。第四动手写一遍关键路径的代码。不用写得很复杂用邻接表存储图拓扑排序的同时更新ve再逆拓扑序更新vl最后遍历每条边求l-e。写过一遍之后你对AOE网的理解会比看十遍教材都牢。那晚之后我再也不觉得操作系统和数据结构是两本不相干的书了。前驱图给我看的是进程之间时空的骨架AOE网给这个骨架注入了度量两者合在一起就是一张能用箭头和数字画出时间形状的地图。如果你正卡在某个概念里绕不出来不妨试着把另一门课里的同类概念拉过来对照着看很多死结往往就这么松开了。