期中周的那個深夜我左手壓著操作系統(tǒng)的教材右手攤開數(shù)據(jù)結構的復習講義。一邊是前驅圖的判斷題一邊是AOE網(wǎng)的關鍵路徑大題我本來只想把這兩頁一起看掉省得來回翻書結果越看越不對勁——怎么它們畫出來的東西長得那么像那是我這個學期第一次強烈地感覺到操作系統(tǒng)和數(shù)據(jù)結構并不是兩門割裂的課它們只是在用不同的尺子量同一張圖。而那張圖畫的正是時間的形狀。如果你也正在學這兩門課或者已經(jīng)學過但當時沒想通我建議你耐著性子看完這篇隨筆。我不打算搞成標準講義只想順著那次復習的頓悟把前驅圖和AOE網(wǎng)放在一張桌子上講清楚它們各自是什么、為什么能被我硬看成同一個東西以及這個看穿的視角對后續(xù)學操作系統(tǒng)、做系統(tǒng)設計到底有什么用。1. 那個晚上兩本教材的同一張圖很多教材在講進程同步之前都會先花小半頁提一下前驅圖。它看起來特別像一個用于描述程序段之間先后關系的箭頭圖幾個圓圈幾個箭頭然后告訴你P1必須在P2之前執(zhí)行P2必須在P3之前執(zhí)行。當時我并沒有太當回事覺得這不就是把流程圖畫出來了嘛有什么可講的結果真到了做操作系統(tǒng)作業(yè)的時候才發(fā)現(xiàn)越簡單的工具越容易被低估。另一邊數(shù)據(jù)結構里的AOE網(wǎng)就慘多了。它屬于圖論那一章的最后一塊內容前面你已經(jīng)熬過了鄰接矩陣、鄰接表、最小生成樹、最短路徑到AOE網(wǎng)的時候整個人基本是麻的。教材上又是一堆像蜘蛛網(wǎng)一樣的圖邊上寫著一堆數(shù)字緊接著就是關鍵路徑ve、vl、e、l四個數(shù)組的定義和公式。我當時只求套公式能算對壓根沒想過它還有什么更深的含義。1.1 前驅圖教材里被匆匆?guī)н^的一張圖前驅圖Precedence Graph的定義其實很樸素用一個有向無環(huán)圖DAG來表示多個程序段或進程之間的前驅關系。圖中的每個頂點可以是一個語句、一個程序段或者一個進程每條有向邊表示前驅與后繼的約束比如從頂點Pi畫一條邊指向Pj就意味著Pj只有在Pi完成之后才能開始。我最初對這個定義有點輕蔑因為它實在太像流程圖或拓撲排序題了。但真正讓我改觀的是它的使用場景操作系統(tǒng)里想表達一組進程能不能并發(fā)執(zhí)行時前驅圖幾乎是唯一能把約束關系畫清楚的工具。你光用文字描述進程B要等進程A進程C又不等進程B一句話就繞暈了但畫成圖一眼就能看出誰跟誰沒有邊相連沒有邊相連就意味著它們在邏輯上沒有前后依賴可以被調度器放到不同CPU核上同時跑。這個沒有邊就能并發(fā)的特點是我后來理解整個操作系統(tǒng)的并發(fā)模型的第一塊基石。沒有它信號量、互斥鎖、條件變量全都是零散的API有了它這些同步機制就全部變成了如何把前驅約束轉化成阻塞和喚醒的工程問題。1.2 AOE網(wǎng)期末復習時繞不開的關鍵路徑AOE網(wǎng)的全稱是Activity On Edge network也就是邊表示活動的網(wǎng)。它的頂點表示事件有向邊表示一個活動邊上的權值表示該活動的持續(xù)時間。因為活動都被放到了邊上所以AOE網(wǎng)常用于估算一個工程的最短完成時間并找出哪些活動拖不得拖一天就拖垮整個工期這些活動連成的路徑就叫關鍵路徑。我當時復習到這一節(jié)時已經(jīng)是一臉疲憊。AOE的計算套路不難難的是容易忘先拓撲排序再正向算ve反向算vl然后算每個活動的e和l最后找l減e等于0的活動連起來就是關鍵路徑。步驟本身非常機械但恰恰因為機械很多同學包括我會不自覺地放棄思考只把它當成一道套公式的題。但那個晚上當我看著AOE網(wǎng)里的那些箭頭時腦子里突然閃過一個念頭這不就是前驅圖嗎AOE網(wǎng)也有頂點也有有向邊也是無環(huán)的邊也代表兩個頂點之間的先后關系。唯一比較大的區(qū)別是AOE的邊上多了一個數(shù)字——時間。這個多了一個數(shù)字的地方恰恰就是我那天晚上最大的頓悟來源。1.3 啪的一下它們在我腦子里疊在了一起我先在草稿紙上畫了一個最普通的前驅圖P1發(fā)出箭頭指向P2和P3P2和P3又分別指向P4。然后我在旁邊畫了一個同樣結構的AOE網(wǎng)頂點一、頂點二之間連了一條帶權值的邊繼續(xù)往下到匯點。去掉邊上數(shù)字之后兩張圖幾乎完全重合。我愣了好幾秒因為在我當時的認知里操作系統(tǒng)是操作系統(tǒng)數(shù)據(jù)結構是數(shù)據(jù)結構它們像兩個大抽屜里面分別裝著進程調度和圖算法兩堆零件。但那一個瞬間抽屜的隔板消失了原來操作系統(tǒng)里描述進程間先后的前驅圖本質上就是數(shù)據(jù)結構里AOV網(wǎng)的一種實例而AOE網(wǎng)則是在這個骨架之上給每條依賴關系加上了時間成本——這哪里是什么兩門課這就是同一張時間地圖的兩種畫法。從那以后我再看任何帶依賴關系的系統(tǒng)第一反應都是先畫一張DAG。這個習慣幫我省了無數(shù)腦子。2. 前驅圖到底想表達什么一組進程的出場順序要真正把前驅圖和AOE網(wǎng)放在一起我們得先把前驅圖這層窗戶紙捅破看清楚它到底在描述什么。很多操作系統(tǒng)教材把前驅圖放在進程的描述與控制那一章位置靠前篇幅不大但它的作用很像樂高積木的基座后面所有的并發(fā)問題都是從誰先誰后這個基座上長出來的。2.1 頂點是程序段箭頭是必須等前驅圖里最基本的語義就是必須等。畫一條從A到B的有向邊代表如果事件A沒有完成事件B就不能開始。這里的A和B不一定非得是進程也可以是幾條語句、幾個子程序甚至一次磁盤I/O和一次CPU計算。也就是說只要你愿意完全可以把一個人寫代碼時的提交流程畫成一張前驅圖。正因為這個語義足夠輕所以前驅圖能描述的范圍特別廣。比如你在一個程序里有五個程序段段之間有各種數(shù)據(jù)依賴你可以把依賴關系全部畫進圖里調度器和編譯器看到這同一張圖能做的事情完全不一樣——理解這一點是讀懂前驅圖的關鍵。2.2 用手畫一遍這五條語句的前驅關系我們不用教材里那些抽象的P1、P2換一個更生活化的例子。假設有這五條賦值語句S1: a x 1S2: b a 2S3: c y 1S4: d b cS5: e a * b表面上看它們只是五句話但仔細分析數(shù)據(jù)依賴就能發(fā)現(xiàn)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是相互獨立的程序段理論上可以同時執(zhí)行分給兩個CPU核去跑完全沒問題。讀到這里你可能發(fā)現(xiàn)了前驅圖并不僅僅是排隊圖它同時還是并發(fā)機會的探測器兩條邊沒有交集的地方就是可以被并行化的地方。2.3 前驅圖最終回答的是能不能并發(fā)嗎更準確一點說前驅圖回答的是在邏輯上能不能并發(fā)執(zhí)行。注意邏輯上三個字這是我和很多同學踩過的一個坑。前驅圖里沒有時間軸它不關心S1執(zhí)行要3毫秒還是30毫秒不關心CPU有幾個核也不關心內存帶寬夠不夠。它只告訴調度器從依賴關系來看S1和S3之間不互相欠賬你有權把它們放到同一時刻的兩個核上至于實際跑起來哪個先完成、能不能真的提速那是調度策略和硬件資源的問題。這個區(qū)別非常重要因為它是前驅圖與AOE網(wǎng)之間最本質的那道分界線。前驅圖說可以或者必須先AOE網(wǎng)卻在每條依賴邊上補上了要花多久。你想想如果一個人只知道哪些事能做卻不知道每件事要多久那他就永遠算不出整個工程什么時候能完成。從能不能到多久思維層面是一個大臺階而邁上這個臺階的橋梁就是AOE網(wǎng)。3. AOE網(wǎng)把工程的耗時一條一條算到邊上如果說前驅圖是一張純結構的依賴圖那么AOE網(wǎng)就是給它注入了時間。數(shù)據(jù)結構里講AOE網(wǎng)時通常會從AOV網(wǎng)引出AOV網(wǎng)的頂點表示活動邊只表示活動之間的偏序關系AOE網(wǎng)則反過來邊表示活動邊上的權值表示活動耗時。這個反一下曾經(jīng)讓我很別扭但后來我發(fā)現(xiàn)正是因為活動被放到了邊上AOE網(wǎng)才能把一個工程的總工期直觀地攤在圖中讓人一眼看出時間都花在了哪里。3.1 AOV是排隊AOE是計時AOV網(wǎng)Activity On Vertex你可能更熟悉它是拓撲排序那節(jié)的主角。AOV網(wǎng)里頂點代表各種活動比如課程表里學完高等數(shù)學才能學線性代數(shù)邊只是一條先后約束沒有數(shù)字。前驅圖從數(shù)據(jù)結構的角度看完全可以視作AOV網(wǎng)的一個具體實例進程也就是活動箭頭就是必須先修。AOE網(wǎng)則完全是另一種氣質。它把活動當成邊把頂點當成事件。什么叫事件就是一條或幾條活動完成的瞬間。比如說一個工程的基礎施工完成就是一個事件它發(fā)生在地基開挖和材料進場這兩項活動都結束的那一剎那。事件本身不耗時耗時的是活動。理解這個轉變后AOE網(wǎng)的核心問題就變得很自然既然整個工程是由一條條有依賴關系、有耗時的活動組成的那整個工程最早什么時候能全部完工要壓縮工期應該優(yōu)先壓縮哪些活動答案就是找到關鍵路徑也就是從源點到匯點之間權值之和最大的那條路徑因為整條鏈上任何一個活動拖延都會直接導致總工期拖延。3.2 ve、vl、e、l四個數(shù)組的完整推演很多教材給AOE網(wǎng)的計算步驟寫得非常干癟新手看過去全是字母。我這里借著復習時的筆記把這個過程按我自己的理解重講一遍盡量講成人話。第一步給圖中每個頂點算兩個時間ve[i]表示事件i的最早發(fā)生時間vl[i]表示事件i的最遲發(fā)生時間。ve從源點開始沿著拓撲序向后推源點的ve是0每個頂點的ve等于它所有前驅頂點的ve加上對應活動耗時然后取最大值。為什么取最大因為一個事件往往要等好幾條活動線都完成才發(fā)生必須等最慢的那條所以取眾前綴路徑里最長的耗時這就是最早的真實含義。vl則是從匯點倒著推匯點的vl等于它的ve然后用后繼頂點的vl減去活動耗時來更新當前頂點的vl取最小值。為什么取最小因為你雖然不能晚于某個時間點但這個時間是受后面一系列活動倒逼出來的后路越緊張當前事件能容忍的余地就越小一旦某個后繼活動很關鍵當前事件就必須留出足夠提前量。有了ve和vl再算每個活動a的e和l?；顒觓是頂點i到頂點j的一條邊權重為w那么活動a的最早開始時間e就是ve[i]最晚開始時間l就是vl[j] - w。最后看l - e等于0的活動就是關鍵活動一點緩沖都沒有一拖就拖垮總工期大于0的活動說明有富余時間晚一點開始也不影響整體。把這些關鍵活動串起來就是關鍵路徑。3.3 手工計算一份完整的AOE網(wǎng)光講定義不夠我把自己考試前手算過的一個例子貼出來。假設有一個AOE網(wǎng)共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。最后把活動參數(shù)列一張表活動邊耗時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. 同一個有向無環(huán)的骨架問的是兩個世界的事到這里前驅圖和AOE網(wǎng)在結構上的高度重合已經(jīng)沒什么可避諱的了它們都是DAG都有頂點都有有向邊拓撲排序都對它們有效。區(qū)別在于前驅圖的邊是純約束AOE網(wǎng)的邊是約束加成本。這個差別看起來只是多寫一個權重但就是因為這個權重兩個圖開始回答完全不同的問題。4.1 相同的DAG骨架先列一個能幫你看得很清楚的對比表。這張表是我復習到后來自己總結的比對著兩本教材抄定義有用得多維度操作系統(tǒng)前驅圖數(shù)據(jù)結構AOE網(wǎng)頂點含義程序段、進程、語句事件活動完成的瞬間邊含義前驅/后繼約束一個活動且?guī)Ш臅r邊權無活動的持續(xù)時間核心問題哪些程序段可以并發(fā)必須遵守什么順序整個工程最短耗時哪些活動拖不得最怕什么有環(huán)導致死鎖或無法調度關鍵路徑上的活動延誤常用算法拓撲排序、偏序分析拓撲排序、ve/vl遞推、關鍵路徑查找看見沒有骨架是完全一樣的。即使是在具體場景里前驅圖也可以畫成AOE網(wǎng)的樣子——只要你在每條依賴邊上標上耗時一個進程結構瞬間就變成了一個可以做工期估算的工程網(wǎng)絡。我后來甚至覺得操作系統(tǒng)的教材里之所以不講AOE只是因為它和數(shù)據(jù)結構各司其職不想重復害得我們要靠自己去把兩塊知識拼起來。4.2 前驅圖回答能不能AOE網(wǎng)回答多久前驅圖的典型用途是把進程之間的先后關系理清楚好讓調度器決定誰和誰可以并行。它回答的是能不能帶點邏輯的意味。你見過的最典型例子就是生產(chǎn)者-消費者模型生產(chǎn)者在前消費者在后中間用一個緩沖區(qū)隔開前驅關系明明白白至于生產(chǎn)一個數(shù)據(jù)要花多久、消費一個要花多久前驅圖不關心。AOE網(wǎng)則自帶成本視角它回答的是多久。同樣一張依賴圖一旦把每項活動的時間標上去問題就從誰先誰后進化成了整個流程最多需要多少時間和哪些環(huán)節(jié)是瓶頸。為什么要重視瓶頸因為非瓶頸環(huán)節(jié)你優(yōu)化到飛起總工期可能紋絲不動瓶頸環(huán)節(jié)哪怕只優(yōu)化一天整個項目就能提前一天交付。這就是關鍵路徑的意義也是所以工程管理者都需要它的原因。4.3 拓撲排序兩門課共享的解題起手式不管前驅圖還是AOE網(wǎng)你拿到的第一反應都應該是同一個動作先做拓撲排序檢查有沒有環(huán)。檢查有環(huán)這個動作在前驅圖里尤其重要因為如果進程之間存在循環(huán)等待關系那意味著誰都在等別人先完成這在操作系統(tǒng)里就是死鎖的前兆在AOE網(wǎng)里有環(huán)則意味著工程描述自相矛盾根本無法計算合理的工期。我之所以強調這個共享起手式是因為它直接暴露了知識體系的統(tǒng)一性。你在數(shù)據(jù)結構課上辛辛苦苦學的拓撲排序到了操作系統(tǒng)里依然是核心工具你在操作系統(tǒng)里見到的進程依賴圖到了數(shù)據(jù)結構里依然是圖算法處理的經(jīng)典對象。很多同學覺得課程之間沒關聯(lián)其實只是因為缺少一個把知識點交叉引用的動作。如果你正在學這兩門課我強烈建議你學完數(shù)據(jù)結構圖的章節(jié)之后回到操作系統(tǒng)重新看一遍前驅圖和信號量你會發(fā)現(xiàn)整個知識脈絡突然就通了。5. 時間的形狀從串行到并發(fā)一條時間線怎么長成了一張網(wǎng)標題里那句我看見了時間的形狀并不是修辭夸張。如果你只接觸單核時代的程序時間確實是直線指令一條一條執(zhí)行總耗時等于所有指令耗時相加沒有分叉沒有并行時間像一根面再怎么拉也只有長度。但一旦進入并發(fā)和分布式系統(tǒng)時間就不再只是一根面了它會分叉、會匯合、會互相等待最終變成一張網(wǎng)。5.1 串行時代的時間是一條線單核單進程的時代程序執(zhí)行路徑非常單純CPU按指令順序走完一條線這條路的總耗時就是把所有步驟的耗時加起來。你不需要畫圖因為根本不存在分叉。這也是我們最早建立的時間直覺——總時間等于每項時間之和。但這條直覺在面對現(xiàn)代計算機時會崩。現(xiàn)在的機器有多個CPU核心一個程序可能開好幾個線程幾個線程之間還有依賴關系。這時候你如果還把所有耗時全部線性相加算出來的時間不僅偏大而且完全看不出哪里有可能并行、哪里有瓶頸。換句話說線性時間的直覺在并發(fā)世界里已經(jīng)失效了。5.2 并發(fā)系統(tǒng)的時間是織物一旦允許并行時間就變成了織物它在某些點分叉在另一些點匯合。前驅圖就是這塊織物的緯線畫出哪些線能并排走哪些線必須交錯等待AOE網(wǎng)則是給緯線標上了長度。你盯著這張網(wǎng)看會看到時間的流動方式有的支路快早早匯入主線有的支路慢壓著整段工程的完成點而那些怎么拖都直接導致總工期延后的活動就是織物的主骨架。我特別喜歡時間的形狀這個說法是因為它把工程和算法從抽象符號變成了空間里的實體。你看一張AOE網(wǎng)時可以把自己想象成站在源點沿著每一條邊向前走。最輕松的路不一定讓你第一個到終點最長的路才決定了整個井口什么時候冒出光。時間在這個圖里不是流動的液體而是被約束出的形狀——受制于依賴、受制于瓶頸、受制于每一條邊上的代價。5.3 木桶最慢的那塊板決定整個工程的進度用木桶效應來解釋關鍵路徑是最容易懂的版本一個木桶能裝多少水取決于最短那塊木板一個AOE網(wǎng)里的工程要多久完工取決于最長那條路徑。你可以把其他所有路徑優(yōu)化到飛起但只要關鍵路徑不動總工期一寸都不會縮短。這種思維放到生活里也很有意思。比如做飯招待朋友洗菜10分鐘、切菜8分鐘、煮飯20分鐘、炒菜12分鐘。如果洗切炒是完全串行那就是50分鐘但如果煮飯的20分鐘可以和其他準備并行整個流程的關鍵路徑就會大幅縮短。你再仔細排一排發(fā)現(xiàn)關鍵是煮飯那條支路和炒菜那條支路誰更長于是你會主動調整動作的先后順序讓耗時長的支路盡早開始。這不就是AOE網(wǎng)的現(xiàn)實投影嗎我從那以后每次看到時間管理教程里畫任務依賴圖都會忍不住用ve/vl算一遍看看到底哪些事是真正的關鍵活動。6. 把這兩張圖落進真實的項目與復習建議說到底前驅圖和AOE網(wǎng)不是只存在于教科書里的名詞。操作系統(tǒng)里的同步原語項目管理里的關鍵路徑法甚至你平時排自己的日程都可以用它們作為思考工具。最后這部分我把自己的實踐和踩過的坑一起寫出來希望對正在學習的你有點用。6.1 前驅圖怎么變成真實的同步代碼在操作系統(tǒng)里前驅圖中誰必須等誰最終要落實成代碼常用的手段就是信號量。比如圖里有一條邊從P1指向P2那你就在這條邊上放一個初值為0的信號量P1結束時執(zhí)行V操作讓信號量加一P2開始前執(zhí)行P操作阻塞等待。多個前驅時需要在每個前驅完成后都V一次后繼方能通過。這個套路看似極簡但幾乎所有經(jīng)典同步問題都可以用它推演出來生產(chǎn)者-消費者、讀者-寫者、哲學家就餐本質上都是在處理一張前驅圖的邊。我自己曾犯過的一個錯誤是只考慮了圖的一部分邊漏掉了某條隱式的依賴結果程序在真實環(huán)境下偶發(fā)崩潰。后來我養(yǎng)成了一個習慣寫多線程代碼之前先在草稿紙上畫出線程間所有必須等和可以并行的關系確認沒有環(huán)、沒有漏邊再動手寫同步代碼。這個習慣幫我省下的調試點時間比我數(shù)據(jù)結構作業(yè)里畫的所有圖都要多。6.2 AOE網(wǎng)在項目管理里的位置AOE網(wǎng)的思想在真實世界里并不叫AOE而叫關鍵路徑法CPM。工程項目管理中人們會把任務拆成一個個帶工期、帶依賴的活動畫出網(wǎng)絡圖找出關鍵路徑然后集中資源去優(yōu)化那些關鍵活動。這正是AOE網(wǎng)在數(shù)據(jù)結構之外的另一重身份。很多時候算法書上那些算完就完事的代碼落地到現(xiàn)實中就是另一種語言的名字這也是我為什么堅持說通一門課要往別的課里看一眼。如果你以后要在團隊里排開發(fā)計劃可以試著把任務拆成DAG給每條依賴標上預估耗時然后用ve/vl手工排一遍找出真正決定里程碑的關鍵路徑。你會發(fā)現(xiàn)很多看似緊急的雜活根本不在關鍵路徑上真正需要盯的永遠是那條最長鏈條上的人和事。6.3 一些能讓你少走彎路的復習建議第一畫圖永遠比背公式重要。前驅圖你要能自己畫出五條語句誰依賴誰的實際例子AOE網(wǎng)你要能獨立算出一個題目的ve、vl、e、l表格而不是只看著教材的例題點頭。第二計算時務必先拓撲排序。我吃過虧在沒檢查環(huán)的情況下直接算ve結果得到錯誤結果。拓撲排序不只是為了排序它是保證遞推順序合理的前提只有前驅都處理完后繼才能用上正確的前驅最大值。第三分清事件最早發(fā)生時間和活動最早開始時間。事件ve是所有前驅活動全部完成的那個時刻活動e則是它的起點事件已發(fā)生就能立刻開工的時刻。很多人c在算e時直接套用vl端點導致前后矛盾其實e永遠等于起點事件的vel永遠等于終點事件的vl減去邊權。第四動手寫一遍關鍵路徑的代碼。不用寫得很復雜用鄰接表存儲圖拓撲排序的同時更新ve再逆拓撲序更新vl最后遍歷每條邊求l-e。寫過一遍之后你對AOE網(wǎng)的理解會比看十遍教材都牢。那晚之后我再也不覺得操作系統(tǒng)和數(shù)據(jù)結構是兩本不相干的書了。前驅圖給我看的是進程之間時空的骨架AOE網(wǎng)給這個骨架注入了度量兩者合在一起就是一張能用箭頭和數(shù)字畫出時間形狀的地圖。如果你正卡在某個概念里繞不出來不妨試著把另一門課里的同類概念拉過來對照著看很多死結往往就這么松開了。