讀博那些事兒 | CCF優博、南大蔣炎岩：我的博士五年
- 2019 年 10 月 4 日
- 筆記
來源：知乎專欄：軟體工程技術研究漫談
作者：蔣炎岩
本文正式版《讀博士的難與易》發表在《中國電腦學會通訊》(CCCF) 2019 年第 8 期 (CCF 優博專題)。在這裡可以無拘無束，放飛自我了。這篇文章的結構和嚴肅版不太一樣，技術的內容放到了最後，大家最關心的 「怎麼守住髮際線」 放在了前面。
背景
在圡博里我算是比較成功的了 (CCF 優博和 ACM China 優博提名，兩項都是 Top 5)，寫這篇文章一方面防止我忘記讀博時期很多有趣的經歷，另一方面也許能給還在泥潭中掙扎的同道中人一些啟發。
先交待一下為什麼要讀博。其實就是覺得想再浪幾年做點什麼有意義的事情 (真實原因是自己很懶沒有考 G/T)，而且 Top 2 也不在南京，沒辦法就在南大讀吧。做這個決定的時候完全不知道在中國讀博意味著什麼，就隨便找了個據說很牛逼的組把自己給賣了。
那個時候人工智慧已經很熱了，為什麼沒選呢？是因為從小被數學好的人嚇怕了…… 這裡要提一下我小時候一起長大的兩位好友，一個是 Richard Peng，另一個是 Zeyuan Allen-Zhu。尤其是 rpeng 那種過目不忘的神人，從幼兒園開始就相愛相殺 (哈哈哈)，後來就搞不過他了。再後來人家去了加拿大，眼看著他各種 STOC/FOCS/SODA，又後來當了美國隊長，不跟咱玩了。
開玩笑。我覺得他給我樹立了一個很好的榜樣，大概是 「知道厲害的人有多厲害」。既然玩不來這個遊戲，就一定要找一個要積累足夠的經驗才能玩起來的領域：
永遠不要跟一個傻 X 爭論。他會把你拉到他的水平上，然後用他豐富的經驗打敗你。
對任何領域來說，經驗都非常重要。不過數學的 training 有點從小就落下了；加上當時對系統軟體還挺感興趣，讀博的時候南大基本沒有人做 System 和 PL，所以選了一個最接近的軟體方向，雖然我也不知道軟體方向是做什麼的，就這麼上車了 (為此還讓出了一個保送碩士的名額，嘿！) 這個路線和廣大保研群眾簡直相似得不能再相似了。
1. 守住髮際線
讀博士嘛，大家肯定最關心的是畢業問題，要是畢業的時候能守住日漸退行的髮際線就更好了。鑒於我讀博士基本是 「自學青年的勝利」，而且還有濃密的頭髮，自己的經驗應該能幫到大家。總結起來就是：臉皮要厚、葯不能停、刻意練習，然後在發表論文的邊緣瘋狂試探就好了。
臉皮要厚
我入坑的第一個研究問題簡直就是四九年入國軍，到今天這個方向的好論文已經非常…… 稀疏了。概括地說就是在基礎的機制已經很難改進的前提下，設計策略去 「overfit」 應用場景，刷出更好的實驗效果來。那段時間幾乎每天要都拷問自己：做這東西有個卵用？試一試吧，實驗設備又相當落後，只要方位角度差一點點，測出來的數據就飛到十萬八千里之外了。但畢竟老闆是 「軟體方法學」 出身的 (雖然我也是做 「軟體方法學」 的，但我大約的確不知道我到底是做什麼的)，他們自帶能說會道的光環，每次都能在方法學的制高點忽悠得你啞口無言，新手學生真是百口莫辯，項目也就一直這樣莫名其妙地進行下去了。
後來我學會了一個經驗，現在和老闆們交流時，頭腦里先預備好一個 SMT Solver。老闆每說一句話，我就先把這句話在邏輯上取反，然後扔到 SMT Solver 里求解一下，看看他到底是怎麼把這件事忽悠過去的。我驚訝地發現，求解的一般結果，要麼是公理體系有些不同，要麼是在一些非常基本的問題上沒能達成一致。一個典型的例子是，老闆們有時候會覺得 「再小的 contribution 也是 contribution」，但如果你有一個預設的 significance 的 lower bound，這句話就不成立了。這一招屢試不爽，每次都說不過老闆的同學們可以多多嘗試 (許暢 ：有的時候說的話還看環境，對有不同抗打擊能力的人要斟酌說不同的話，可以細細體會老闆是鼓勵你還是安慰你 —— 不要把老闆安慰你的好心硬戳破了)。
我覺得知乎上遇到自己不喜歡研究問題的博士生肯定相當多。這時候，臉皮厚的作用就發揮出來了：我有腿，不喜歡這個問題可以跑路啊！
我先後鴿了兩個研究方向，科研進展為零 (但本人心態比較好，沒有掉頭髮)。然後在選第三個研究方向的時候 (研一結束時，進組兩年後)，非常非常非常感謝許暢：他非常謹慎地在 ICSE』12 的時候戳了 HKUST 的張成志教授，說我們這有個學生，給他點難整的問題整整。張老師就說，嘿嘿嘿不好做的問題那是大大的有，可以試試並發，給了兩篇相關的 paper。於是我就這樣上車了 —— 我們組沒有人是這個領域的專家，甚至做程式 (靜態或動態) 分析的人都沒有。
在最後一次厚臉皮以後，就是知乎上的常見套路了，讀論文寫程式碼發 paper…… 雖然沒人手把手帶我飛，但這個領域研究的人多，好論文也多，非常適合新人學習。給我啟發最多的論文都來自 PL、系統和硬體，可想而知在此過程中補充了多少基礎知識。因此，我現在儘可能給新人推薦這種已經很多人研究過的領域，雖說在這種領域發論文可能相對更難一些，但能學到非常多的東西。相反 (也是另一種很常見的情況)，你如果進入一個特別小眾的領域，只有幾個人在玩，入門視野就窄了、格局就小了，就算能灌很多論文，我個人覺得不是很利於今後的職業生涯。
師傅領進門，修行看個人。這次終於算是入了豪門，老闆們的支援功不可沒。
葯不能停
鴿人可以，學習姿勢不能停 (廢話)。
我覺得自己還算是個熱愛學習的人，在那個時候讀了很多與研究方向無關的教科書、論文和公開課，也聽了很多學術報告。我記得 李沐 在 PhD 回憶錄里提到了 「Parallel and Distributed Computer: Numerical Algorithms」 這本書給他很大啟發，我也讀過，寫得非常好，那些經典的視角在今天都不過時。以及時候開始讀雜誌 Communications of the ACM (CACM)，到今天應該看完 10 年份了 (入坑之後往前補了不少，但後來也堅持不下去了)。雖然很多文章並不能完全讀懂，但大部分時候都是在 「開眼界」，看看其他領域的人在用什麼方法解決什麼問題，算是構建電腦科學的世界觀。
另一個成功的例子是 Tim Roughgarden 在演算法課上一句話提到了一份 USENIX Security』03 的工作，然後就這一句話啟發我們做了正則表達式複雜性攻擊的工作 (當然做研究沒有那麼順利，中間的波折就忽略了)，並且很意外地獲得了 ACM SIGSOFT Distinguished Paper (真是意外，其實是 Conditional Accept，差點掛了)。這個論文的點睛之筆是非常規地使用了 Pumping Lemma，已經不記得是什麼時候在什麼地方學過這個定理，但的確那一瞬間就想到了。
學習經歷培養一個人的研究品味 (taste)，所以不必想著眼前立即得到的好處。具體來說，「學習」 就是幫助博士生訓練一個分類器，能判定 「什麼東西是好東西」，有真正的 contributions。好東西看多了，你看到那些爛的東西就很自然的排斥了 (如果導師是這方面專家，可以事半功倍，但無論如何靠自己都是第一位的)。最近幾年過了我心中 bar 的論文投稿，被拒的情況相當少 (所以我的總體錄用率遠大於會議的錄用率，雖然好些感覺沒過 bar 的也中了)。總結來說，自學青年想要勝利，我覺得讀得多是非常重要的。
刻意練習
另一個經常遇到的問題是怎麼閱讀論文。網上也有很多建議、方法，我自己的理解是看論文有些類似神經網路的訓練 (許暢：一定要明白人的學習能力遠超過機器，其通過極少例子領悟到真相的泛化能力是極強的 —— 想想悟道)：在看到研究問題以後，先試圖給出自己的分析和方案，然後再看作者的做法，如果有自己沒能想到的奇思妙想，再通過 「反向傳播」 糾正自己思路的盲區，重點是把作者的方法用自己容易解釋的邏輯解釋出來 (這一步非常非常重要！)。老闆有一句話說得非常在理：必須閱讀 100 篇甚至更多的論文，才能對一個研究領域有一些基礎的感覺。
其他方面也是可以練習的，比如寫作和寫程式碼 (因為我比較喜歡寫程式碼，所以後者沒有花去太多的時間也不痛苦，覺得 hacking 很好玩)。第一篇論文的寫作被搞慘了 (有圖為證，此處 @許暢 )。即便改到這個程度，因為底子太差還是被審稿人罵了，說這論文做的不錯，寫的也勉強能看懂，但行文真的是一坨屎，連標題都有語病。
收到審稿意見以後嚇壞了，趕緊去學習了一些公開課、教程 (有些老闆給研究生的建議寫得真的很棒，比如 Manuel Blum 給研究生的建議)，還有萬能的 stackexchange。等到 camera ready 的時候已經有了非常顯著的提高了；再後來自己也能在非常短的時間裡寫出讀得過去的論文了。
在發表論文的邊緣瘋狂試探
在對相關工作有已經有一定了解的基礎上，我有了 (若干) 個想法。其中一個我覺得 「很有前途」 的想法，經過跟老闆討論被否定了，覺得這東西不就是個 XXXXXX 嘛，沒啥卵用。另一個我覺得 「沒前途」 的想法，老闆們一直在慫恿繼續搞 (很可能是出於鼓勵的心態，但我至今都不覺得這個 paper 能發得出來)。再後來一個我覺得 「挺一般」 的想法成了我的第一篇論文。
再之後我發現 Mike Bond 在 OOPSLA』13 上發表了一篇和 「有前途想法」 幾乎一模一樣的論文，但實現得非常好，可以說遠超過了我當時的眼界。事後總結，我覺得是老闆們的口味可能已經被大項目或者整個領域帶歪了，覺得技術已經是無關緊要的東西了，反正總有人能做出來的，做出來也就幾句話就講清楚了，不帶勁。「突破天際」 的東西才是他們真正想要的。在這件事上我感受到了 「方法學」 的危險，有時候甚至覺得方法學就是逃避的借口 —— 別人發了個什麼論文，也就是把這麼幾個想法拼起來，提升了這麼一點，不過如此嘛。但如果讓大談方法的人去實際做一個，很可能會因為缺少對其中各種坑的認識做不出來。
但突破天際的東西哪那麼容易能做出來呢？不過也沒事，這件事一方面讓人有些不爽，另一方面還是讓人挺爽的：畢竟自己的腦袋還是好使的，這次在 state-of-the-art 的邊緣，也許下次就超過了呢。反正 99% 的 idea 都是別人已經想到或者沒有用的，但小概率事件大量重複必然發生，只要每天堅持拍腦袋，腦袋一定會禿的，哦不，是一定會有靠譜的 idea 的。只要因為拍腦袋損失頭髮的速度不及頭髮生長的速度，髮際線就能保住了。我曾經聽說過 Yuanyuan Zhou 組裡的軼事，每周組會的時候強行要求每個人出一個新的 idea，還會給好的 idea 頒獎。這個機制壓力超大，但的確成效很好。
我寫第一篇論文的時候，就只是想做點什麼好玩的東西，但之後就不滿足於此了，總是想做更好的、有真正研究貢獻的東西。從發第一篇高峰會開始，保持自己研究工作的品質上升就已經是相當困難的了。所以就算從灌水開始，也不要有太大的負擔，來日方長嘛。
讀博大概就是這麼簡單，功夫到了該有的就有了，覺得痛苦的可能需要回去補基本功，或者是看看自己在大方向上有沒有犯錯誤。
其實關於守住髮際線，上面說的都是騙人的。真正的原因是我遺傳了我爸優秀的基因。但關於做研究的故事，都是真的，有堅持就會有回報。
2. 奇聞趣事
拖延症
誰沒有拖延症呢？我拖了兩把超大的。第一次是因為論文得以發表，可以找機會出國轉轉，留學基金委掏錢，有個申請的流程。結果我把聯繫導師的事情拖延到了截止日期的前一天。對，你沒看錯，我們花一天時間聯繫了一位老闆僅有一面之緣之人，在 24 小時內搞定了推薦信和材料。在材料交出去的那一瞬間，我只知道這個人做的東西好像和我有那麼一丟丟關係。
有時候覺得運氣來了擋也擋不住：
1. 我很驚訝地發現我讀過那位神秘導師 (秦鋒) 的研究組在 OSDI』14 上發表的一篇有關崩潰一致性的論文，非常喜歡，這就是緣分 (其實是論文讀得夠多)。
2. 我選擇了潛伏在留學生群里 (而不是拖家帶口的訪問學者)，於是找到了兩位超棒的室友。一位是挖石油的，一位是搞錢的，讓美帝的生活十分愉快。
3. 實驗室的大哥們 (按輩分算其實是師弟) 對我十分照顧，其樂融融大家庭，讓美帝的科研工作也十分愉快。
我拖的第二把超大的是花兩周時間寫完了畢業論文。記得 2017 年 9 月初，我問老闆是不是可以畢業了，老闆說好啊，一般是 11 月交論文，嗯我們來看看…… 一看不得了，距離論文初稿提交還有兩周多一丟丟，而那個時候我寫完的部分大概只有 5 頁。
這時候，是個懶人的好處就體現出來了：我會用工具啊！之前寫論文的時候總覺得 LaTeX 無論用什麼工具編輯，多多少少都會干擾寫作的順暢。我總結很大的原因是文字和程式碼混排在一起，比如用等寬字體吧，文字讀起來怪；用 Serif 吧，程式碼沒法看。所以之前的幾篇論文，我就開發了自己的 LyX 模板。期間我修正了很多不滿意已有學位畢業論文模板的地方，全文 2632 個公式、40 個插圖、12 個附表、144 篇參考文獻，兩周就搞定了，雖然提交以後到答辯前花了近一個月的時間玩命 polish……
這種極限操作的能力，可能來自於以前參加 ACM-ICPC，三人一台機不太夠用，所以練習在紙上寫完整的程式碼。到後來可以做到幾頁紙的程式碼，proof read 一遍，敲進去編譯過就能交，過了就是過了，不過稍微測點數據再讀一遍程式碼也能搞定。總體來說，我在讀博期間甚至到今天依然經常極限操作，但幾乎沒有錯過任何自己預設好的 deadline，所以好像給老闆 (以及其他共事者 / 合作者) 一個我很靠譜的假象 (實際上是因為總還有更不靠譜的人)。
神奇的美帝
在美國短短半年的訪問讓我感到非常舒適：所有的瑣事都甩鍋了，可以非常靜心地體驗一下不一樣的生活。經常順著 Olentangy River 步行到學校，從盛夏到秋冬，一路上的風景變化都還歷歷在目。
在研究方面，我們做了一個很有趣的小工具：用 ptrace 攔截系統調用，用虛擬設備收集塊設備的日誌，然後用一些演算法上的小技巧來自動檢測應用程式中的崩潰一致性缺陷。因為之前玩過很多東西，所以做起來可以說是相當順手，半年的訪問期間就完成了選題、程式碼、實驗，找到了包括 Coreutils、Gzip 等軟體里的缺陷，論文也順利發表。最近我收到了 Perl 社區的感謝，在最新的穩定版里修復了我們報告的 bug。回顧自己求學的經歷，技術方面的積累都是互聯網和開源軟體培養的，自己一直在索取，如今能做一些微小的回報，欣喜甚至勝過博士畢業。
老秦 (forgive me! 實驗室里的兄弟們都是這麼稱呼的哈哈！) 給了我很多指導，還教導我們兩件事：「Get out of your comfort zone」，和 「Don』t give up easy」。第二條我要特別提一下，我自己的很多想法在做的過程中很多次都覺得可能做不下去了，但之後總是找到辦法又撈回來了。我記得很清楚，在美帝時論文已經基本成型，但缺一個 NP-Completeness 的證明 (課後習題難度)，不過那時候可能腦子有點短路，很久都卡著。有時候想著不證明就不證明吧，反正不影響論文的結果，但忽然某一天我坐 Shuttle 回公寓的時候就想到了關鍵步驟，那時候正值俄亥俄州的冬天，但忽然就覺得一點也不寒冷了。
這一小段訪問經歷還很大程度地影響了我的價值觀，我之後就愛上了 「把軟體放在地上摩擦」。我現在的風格是 「For fun and profits」，首先為了程式設計師的那種自我滿足，其次是創造一些對社會有用的實際價值。我想出了一個評價自己研究工作的 metric：我如果做了個東西，我要想一下那些在 Google/FB 工作的碼農同學們覺得怎麼樣，如果他們覺得無趣，那還是趁早放棄來得比較好。我覺得在美國的半年對我生涯產生了很大改變：從一開始只是為了 「做點什麼不一樣的東西」，到現在想真正做點 「有用的東西」。
最後，在美帝也沒少出去玩，美國的歷史不長，但每一個城市卻都保留了很多舊時光的印記。
3. 勸退
所以你還想讀博士嗎？好像也沒什麼難的 —— 找一個 (足夠) 困難的方向，把相關的論文都讀了，然後死命想還能做什麼就完事了。當然要事情真那麼好，讀博士也就不至於知乎上說得那麼慘了 —— 沒遇到對的人、如果臉皮不夠厚…… 一步走錯就可能半途夭折。現在中國的學術界在一個驚人的轉折點上，隨著下一代人從小受到的訓練越來越好，我那點三腳貓的基本功遲早是保不住的。做研究可能並不是靠被動地 「學習」 就能搞定的，長江後浪推前浪，前浪立馬就死在沙灘上。現在我覺得自己大概在活下去的 「及格線」 上 —— 從小我自己就不是個 hardworking 的人，但 fully focused 的時候還是可以做出一些差強人意的東西。如果我讀博士時候再努力一些，雜七雜八的事情別管那麼多：
- 該死的系統實驗課，哦沒什麼，也就是讓本科生自己寫個 CPU，上面跑個自己的作業系統以及應用程式。這也沒啥技術含量 (沒少人做過)，就是花時間；
- 帶江蘇省隊的訓練和省級競賽的組織等，維護評測機、競賽現場的各種腳本和臨時背鍋，當了好多年的救火隊長；
- 帶著 ACM-ICPC 集訓隊訓練，再早些時候還打打 TC，在紅名的邊緣瘋狂試探……
然後遊戲再少打一點，不要談戀愛結婚 (已屏蔽老婆)，publication list 也不會就這麼孤零零的幾篇了。我經常和學生們說，如果你們連導師都不能正面剛，還是謹慎考慮一下讀博這件事吧。
因此在這裡必須勸退一波想要 「通過讀個博士過上安逸日子」 的人，這條路越來越行不通了。如果你還沒有被勸退，恭喜你！讀博的經歷是獨一無二的，如果當了一個社畜 (我曾經有過無數當社畜的機會)，就不會有那麼多精彩的發現了。
簡短的致謝
走上電腦科學的道路多多少少算是件 「命中注定」 的事，大概要從幼兒園起相愛相殺的基友彭泱 (Richard Peng) 開始吧。他是個非常神奇的人物：記憶力超強、解題速度超快、受到的訓練超好。這個基本上是我能見到的 「天花板」，雖然如他所說，做數學的人更可怕，不過好像那些人並不在我生活的世界裡。然後一路都遇到很多有趣的人 (無法一一致謝)，包括大學時代一起參加 ACM-ICPC 的隊友李昂和李珅，度過了非常愉快美好的本科時光，在美國重逢的時候還一起旅遊了一場 Regional (說好的 AK 變成了各種 WA 到死)。到讀博期間，我的導師們 (呂校長、馬所長、許暢和秦鋒老師) 都非常支援我，給了我超棒的研究環境，甚至有時候都不好意思差遣我當馬仔，我自己是覺得不太好意思的 (我有一個做馬仔的覺悟，但好像也許因為自己有同學多做了一些馬仔活)。
一段精彩的生活告一段落，謹此紀念。
p.s. 感謝老闆許暢在文中標註的 「老闆內心獨白」。
高能預警：以下是技術內容可以忽略
4. 附錄：我到底做了個啥玩意？
從 「哲♂學家吃飯」 問題說起
從某種意義上來說，博士期間我是研究哲 ♂ 學的。「哲學家吃飯問題」 是大學時代學習並發編程時的經典難題。現在哲學家們受到盛情的邀請來到舌尖上的中國，面對一桌豐盛的菜肴，他們不再受限於必須同時拿起手邊的兩根筷子才能用餐，因此可以更盡興地享用美食。另一方面，吃中餐的哲學家們也帶來了一個新的問題 —— 聚餐是一個很複雜的過程，我們能否把吃飯時發生的事情像講故事一樣，完整地複述出來？
如果把哲學家看作是執行緒，每道菜看作是變數，那麼每個哲學家在吃飯的過程中都可以多次執行以下兩個操作：(1) 觀察某一道菜，在瞬間記下這道菜的模樣 (相當於讀出變數的值)；(2) 吃某一道菜，在瞬間改變它的模樣 (相當於為某個變數寫入一個值)。哲學家們都是了不起的天才，在吃飯的過程中都已默默地記下自己所知的一切，即每個執行緒記錄下自身發生的讀 / 寫操作的變數和它們的數值。
之後的一天，哲學家們重新聚在一起，試圖解決 「哲學家吃中餐問題」：他們各自整理了對那一天吃飯過程的記憶，並試圖一起還原出吃飯的完整過程。更確切地說，我們希望在程式執行結束後，把執行緒本地的讀 / 寫操作日誌合併成全局的變數讀 / 寫序列，相當於給所有讀 / 寫事件分配發生的先後次序，使得每個讀事件讀出的數值都等於最近一次對該變數寫入事件寫入的數值（即根據執行緒本地日誌得到全局滿足順序一致性的事件排序），如圖 1 所示。Gibbons 和 Korach 在 1997 年對於 「哲學家吃中餐問題」 給出了一個頗為悲觀的答案 [1]：如果 P ≠ NP，再聰明的哲學家也無法在多項式時間裡恢復出滿足順序一致性的事件排序。甚至，即便哲學家吃的是火鍋 (只有一道菜，即一個變數的情形)，NP – 完全性也是成立的。
圖 1：「哲學家吃中餐問題」 示意圖。R/W 分別代表讀 / 寫事件，紅色表示滿足順序一致性的執行緒調度
哲學家和攝像機
「哲學家吃中餐問題」 為什麼重要？想想我們身邊的並發程式 —— 作業系統內核、雲計算 / 分散式系統、伺服器應用，大家都有的體驗是它們很難寫、更難寫對。因為不確定性的存在，即使我們已經知道程式里有缺陷 (bug)，要想復現缺陷觸發的過程都很困難，更不用說測試了。哲學家吃中餐問題恰恰就是要解決從日誌中恢復出程式執行過程的難題，這對並發程式調試技術的重要性是不言而喻的。不僅是調試，我們還可以針對觀測到的一次執行預測程式中的缺陷，例如數據競爭或 use-after-free；甚至在運行時就對程式的行為進行干預，避免並發缺陷被觸發。這一大類基於程式執行軌跡實現的技術統一稱為並發程式的動態分析技術。
「哲學家吃中餐問題」 的 NP – 完全性 (固有的困難) 並不意味著我們無法在實際中解決它。為了實現並發程式的動態分析，必須在運行時觀測並發程式的執行，而觀測卻並不局限於 「執行緒本地的記錄」。我們希望有一台 「攝像機」 拍攝下哲 ♂ 學 (家吃飯) 的全過程，而修改程式的程式碼或運行時環境，恰好能實現這樣的攝像機：為所有共享記憶體的讀 / 寫操作上鎖，並在鎖的保護下記錄它們發生的順序，就得到了共享記憶體訪問的日誌，如圖 2 所示。從此意義上，觀測並發程式執行又是容易的。
圖 2：修改程式程式碼對共享記憶體讀操作進行觀測 (標記 「►」 的為插入的程式碼)
難與易之間的矛盾是觀測並發程式執行的開銷。雖然鎖可以實現有效的觀測，但卻降低了系統的並行度、拖慢了程式的執行。並發性存在於電腦系統棧的各個層次上，因此來自體系結構、電腦系統、程式設計語言和軟體工程領域的研究者，全都對實現高效的並發程式動態分析有興趣。在三十多年的研究歷程中，我們看到了很多非常精彩的鎖機制的實現：藉助硬體的快取一致性協議 [2]，使用虛擬機、分支計數和用分頁機制實現的 CREW 協議 [3, 4]，以及在執行緒局部訪問下 「樂觀」 的鎖機制 [5]。另一方面，我們可以通過記錄間接資訊 (如每個執行緒執行的路徑)，使用約束求解的方式去恢復共享記憶體訪問的日誌 [6]。我的博士論文在運行時獲取共享記憶體訪問數據依賴這一問題上做了一些微小的貢獻，主要集中在利用局部性減少鎖的開銷。例如，我們發現在空間 (地址) 上連續的多個變數，例如數組的一部分，在共享記憶體訪問的意義上通常可以看成是一個大的 「虛擬變數」。如果以虛擬變數為單位進行記錄，則可以有效減少鎖的數量，並大幅減少日誌的數量 [7]。
在觀測並發程式執行的基礎上就可以實現各式各樣的動態分析技術了。這裡舉一個我們測試並發程式的例子 [8] (參見知乎專欄中的科普文)：
midwinter1993：擰龍頭法測試並發程式
https://zhuanlan.zhihu.com/p/51341151
試想我們把執行緒中的讀 / 寫事件按順序串在一根繩子上 (圖 3)，處理器按照固定的速度按順序執行繩子上的事件。改變繩子的長度 (例如拉繩子相當於把執行緒執行的速度變慢) 就得到了不同的執行緒調度 —— 那些觸發並發缺陷的調度，很可能隱藏在某些繩子長度的配置中。我們設計了聰明的策略生成具有多樣性的執行緒調度，在先前研究者已經反覆測試過的並發程式上找到了前所未知的並發缺陷。對於複雜性日漸增長的並發程式來說，動態分析是一項非常有前景的技術，對具體內容感興趣的讀者可以參考我們的中文綜述 [9]。
圖 3：基於執行緒調速的並發程式測試技術示意
有沒有免費的午餐？
觀測並發程式執行是非常基礎且重要的問題，來自各個領域的研究者都取得了豐碩的成果，但唯獨 「完美」 現在還做不到。現有觀測並發程式執行的工作可分為兩類：要麼存在一個 NP – 難的最壞情況，要麼不可避免會在某些情況下用鎖 (類似圖 2 的方式) 保證一次觀測不被其他執行緒打斷。
「哲學家吃中餐問題」 的 NP – 完全性一定程度上反映了現有研究工作面臨的困境 —— 如果只允許程式進行少量的執行緒本地記錄，則恢復滿足順序一致性的全局調度是困難的。另一方面，我們也已經知道共享記憶體上的互斥和可序列化並發對象必須藉助讀 – 寫原子操作才能實現 [10]。這啟發我們提出了一個猜想：觀測並發程式的執行沒有免費的午餐 (no-free-lunch)。具體的陳述是，在一個限定的計算模型下，即便允許對並發程式進行一定程度的修改 (在共享記憶體訪問前後插入一定數量的共享記憶體讀 / 寫操作，其中寫操作只限於為觀測並發程式執行而額外分配的記憶體)，只要這些插入的讀 / 寫序列是等待無關 (wait-free) 的，就存在某種執行緒調度，根據執行緒本地的觀測結果恢復滿足順序一致性的程式執行是 NP – 完全的。
如果這個猜想成立，就對這 30 年的研究成果給了一個 「二分性」 的總結 —— 想要觀測並發程式的執行，要麼添加處理器之間的同步，要麼付出 NP – 完全的代價。這意味著觀測並發程式執行是既困難又容易的。目前我們相信這個猜想是成立的。在試圖證明它的過程中，我們對 「哲學家吃中餐問題」 給出了的一個新的（簡化的）證明，並據此得出了一些有用的結論，例如在對程式的修改能寫成只讀前綴 + 只寫後綴的情形下的 NP – 完全性。受限於掌握的數學工具，我們還沒能完全證明或否定這個猜想。如果猜想被推翻，我們就更驚奇了 —— 說明 30 年來大家的努力都有本質上的不足，抑或 P = NP，也許我們就需要重新理解整個電腦科學了。
上面都是假話。這個猜想很早就想到了，但一直找不到合適的數學工具證明，加上研究方向的轉變，猜想就只證明到這個程度 (也是個課後習題難度)，其實是博士論文爛尾了……
在試圖解決這個猜想的過程中，其實給了我們很多啟發 —— 猜想必須在很多限定條件下才能成立。因此只要假設的條件被推翻，觀測並發程式執行就變得不困難了。例如，我們的複雜性結論是在 「最壞情況」 下得出的，即存在一個 NP – 完全的 「極端」 執行緒調度。但最壞情況也許像平滑分析 [11] 中指出的那樣，在實際中很難存在。現實中的並發程式執行有它的特徵 (例如各種局部性)，也被我們用來降低觀測並發程式執行的開銷。就在難與易之間，理論和實踐得到相互的印證。然而在理論與實踐中，我們都仍有很多未解決的難題，博士讀了很多年，反而覺得研究才剛剛開始，而不像是告一段落了。
參考文獻
[1] PB Gibbons, E Korach. Testing shared memory. SIAM Journal on Computing, 26(4), 1997: 1208-1244.
[2] M Xu, R Bodik, MD Hill. A 「Flight data recorder」 for enabling full-system multiprocessor deterministic replay. In Proceedings of the International Symposium on Computer Architecture (ISCA), 2003.
[3] GW Dunlap, ST King, S Cinar, et al. ReVirt: Enabling intrusion analysis through virtual-machine logging and replay. In Proceedings of the Symposium on Operating Systems Design and Implementation (OSDI), 2002.
[4] GW Dunlap, DG Lucchetti, P Chen, et al. Execution replay for multiprocessor virtual machines. In Proceedings of the ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (VEE), 2008.
[5] MD Bond, M Kulkarni, M Cao, et al. Octet: Capturing and controlling cross-thread dependences efficiently. In Proceedings of the ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA), 2013.
[6] J Huang, C Zhang, J Dolby. CLAP: Recording local executions to reproduce concurrency failures. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2013.
[7] Y Jiang, C Xu, D Li, et al. Online shared memory dependence reduction via bisectional coordination. In Proceedings of the International Symposium on the Foundations of Software Engineering (FSE), 2016.
[8] D Chen, Y Jiang, C Xu, et al. Testing multithreaded programs via thread speed control. In Proceedings of the Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE), 2018.
[9] 蔣炎岩，許暢，馬曉星，呂建。獲取訪存依賴：並發程式動態分析基礎技術綜述 [J]. 軟體學報，28 (4):747-763, 2017.
[10] H Attiya, R Guerraoui, D Hendler, et al. Laws of Order: Expensive synchronization in concurrent algorithms cannot be eliminated. In Proceedings of the ACM SIGPLAN/SIGACT Symposium on Principles of Programming Languages (POPL), 2011.
[11] DA Spielman, SH Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3), 2004: 385-463.
（經授權轉載自知乎專欄：軟體工程技術研究漫談，作者：蔣炎岩，點擊閱讀原文查看原文。）
