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