封面是我最近在追的動(dòng)漫《眷思量》，推薦給大家！

本文作者：陳碩

來源：https://www.zhihu.com/question/22608820/answer/21968467

看完后不再迷茫！在校學(xué)生的編程語言和數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)還不錯(cuò)，我認(rèn)為應(yīng)該在《操作系統(tǒng)》和《計(jì)算機(jī)體系結(jié)構(gòu)》這兩門課上下功夫，然后才去讀編程方面的 APUE、UNP 等書。

下面簡(jiǎn)單談?wù)勎覍?duì)學(xué)習(xí)這兩門課的看法和建議，都是站在服務(wù)端程序員的角度，從實(shí)用主義（pragmatic）的立場(chǎng)出發(fā)而言的。

學(xué)習(xí)操作系統(tǒng)的目的，不是讓你去發(fā)明自己操作系統(tǒng)內(nèi)核，打敗 Linux；也不是成為內(nèi)核開發(fā)人員；而是理解操作系統(tǒng)為用戶態(tài)進(jìn)程提供了怎樣的運(yùn)行環(huán)境，作為程序員應(yīng)該如何才能充分利用好這個(gè)環(huán)境，哪些做法是有益的，哪些是做無用功，哪些則是幫倒忙。

學(xué)習(xí)計(jì)算機(jī)體系結(jié)構(gòu)的目的，不是讓你去設(shè)計(jì)自己的 CPU（新的 ISA 或微架構(gòu)），打敗 Intel 和 ARM；也不是參與到 CPU 設(shè)計(jì)團(tuán)隊(duì)，改進(jìn)現(xiàn)有的微架構(gòu)；而是明白現(xiàn)代的處理器的能力與特性（例如流水線、多發(fā)射、分支預(yù)測(cè)、亂序執(zhí)行等等指令級(jí)并行手段，內(nèi)存局部性與 cache，多處理器的內(nèi)存模型、能見度、重排序等等），在編程的時(shí)候通過適當(dāng)組織代碼和數(shù)據(jù)來發(fā)揮 CPU 的效能，避免 pitfalls。Modern Microprocessors

這兩門課程該如何學(xué)？看哪些書？這里我告訴你一個(gè)通用的辦法，去美國(guó)計(jì)算機(jī)系排名靠前的大學(xué)的課程主頁，找到這兩門課最近幾年的課程大綱、講義、參考書目、閱讀材料、隨堂練習(xí)、課后作業(yè)、編程實(shí)驗(yàn)、期末項(xiàng)目等，然后你就心里有數(shù)了。

學(xué)習(xí)任何一門課程都要善于抓住主要矛盾、分清主次、突出重點(diǎn)，關(guān)鍵是掌握知識(shí)框架，學(xué)會(huì)以后真正有用的知識(shí)和技能，而不要把精力平均分配在一些瑣事上。

請(qǐng)?jiān)试S我再次引用孟巖的觀點(diǎn)：http://blog.csdn.net/myan/article/details/5877305

我（孟巖）主張，在具備基礎(chǔ)之后，學(xué)習(xí)任何新東西，都要抓住主線，突出重點(diǎn)。對(duì)于關(guān)鍵理論的學(xué)習(xí)，要集中精力，速戰(zhàn)速?zèng)Q。而旁枝末節(jié)和非本質(zhì)性的知識(shí)內(nèi)容，完全可以留給實(shí)踐去零敲碎打。

原因是這樣的，任何一個(gè)高級(jí)的知識(shí)內(nèi)容，其中都只有一小部分是有思想創(chuàng)新、有重大影響的，而其它很多東西都是瑣碎的、非本質(zhì)的。因此，集中學(xué)習(xí)時(shí)必須把握住真正重要那部分，把其它東西留給實(shí)踐。對(duì)于重點(diǎn)知識(shí)，只有集中學(xué)習(xí)其理論，才能確保體系性、連貫性、正確性，而對(duì)于那些旁枝末節(jié)，只有邊干邊學(xué)能夠讓你了解它們的真實(shí)價(jià)值是大是小，才能讓你留下更生動(dòng)的印象。如果你把精力用錯(cuò)了地方，比如用集中大塊的時(shí)間來學(xué)習(xí)那些本來只需要查查手冊(cè)就可以明白的小技巧，而對(duì)于真正重要的、思想性東西放在平時(shí)零敲碎打，那么肯定是事倍功半，甚至適得其反。

因此我對(duì)于市面上絕大部分開發(fā)類圖書都不滿——它們基本上都是面向知識(shí)體系本身的，而不是面向讀者的?？偸前严嚓P(guān)的所有知識(shí)細(xì)節(jié)都放在一堆，然后一堆一堆攢起來變成一本書。反映在內(nèi)容上，就是毫無重點(diǎn)地平鋪直敘，不分輕重地陳述細(xì)節(jié)，往往在第三章以前就用無聊的細(xì)節(jié)謀殺了讀者的熱情。

比如說操作系統(tǒng)，應(yīng)該把精力主要放在進(jìn)程管理與調(diào)度、內(nèi)存管理、并發(fā)編程與同步、高效的IO等等，而不要過于投入到初始化（從 BIOS 加載引導(dǎo)扇區(qū)、設(shè)置 GDT、進(jìn)入保護(hù)模式）這種一次性任務(wù)上。我發(fā)現(xiàn)國(guó)內(nèi)講 Linux 內(nèi)核的書往往把初始化的細(xì)節(jié)放在前幾章，而國(guó)外的書通常放附錄，你可以體會(huì)一下。初始化對(duì)操作系統(tǒng)本身而言當(dāng)然是重要的，但是對(duì)于在用戶態(tài)寫服務(wù)程序的人來說，弄清楚為什么要打開 PC 上的 A20 地址線真的有用處嗎？（這不過是個(gè)歷史包袱罷了。）

再比方說《計(jì)算機(jī)網(wǎng)絡(luò)》，關(guān)鍵之一是理解如何在底層有丟包、重包、亂序的條件下設(shè)計(jì)出可靠的網(wǎng)絡(luò)協(xié)議，這不算難。難一點(diǎn)的是這個(gè)可靠協(xié)議能達(dá)到“既能充分利用帶寬，又能做到足夠公平（并發(fā)連接大致平均分享帶寬）”。而不是學(xué)會(huì)手算 CRC32，這更適合放到信息論或別的課程里去講。

注意分清知識(shí)的層次。就好比造汽車與開汽車的區(qū)別，我認(rèn)為一個(gè)司機(jī)的技能主要體現(xiàn)在各種道路條件和天氣狀況下都能安全駕駛（城市道路、高速公路、鄉(xiāng)間公路 X 晴、雨、雪、霧），平安到達(dá)目的地。作為一名司機(jī)，了解汽車運(yùn)行的基本原理當(dāng)然是好事，可以有助于更好地駕駛和排除一些常見故障。但不宜喧賓奪主，只要你不真正從事汽車設(shè)計(jì)工作，你再怎么研究發(fā)動(dòng)機(jī)、傳動(dòng)、轉(zhuǎn)向，也不可能比汽車廠的工程師強(qiáng)，畢竟這是人家的全職工作。而且鉆研汽車構(gòu)造超過一定程度之后，對(duì)開好車就沒多大影響了，成了個(gè)人興趣愛好。“有的人學(xué)著學(xué)著成了語言專家，反而忘了自己原本是要解決問題來的?！保ㄕZ出孟巖 快速掌握一個(gè)語言最常用的50%）

對(duì)于并發(fā)編程來說，掌握 mutex、condition variable 的正確用法，避免誤用（例如防止 busy-waiting 和 data race）、避免性能 pitfalls，是一般服務(wù)端程序員應(yīng)該掌握的知識(shí)。而如何實(shí)現(xiàn)高效的 mutex 則是 libc 和 kernel 開發(fā)者應(yīng)該關(guān)心的事，隨著硬件的發(fā)展（CPU 與內(nèi)存之間互聯(lián)方式的改變、核數(shù)的增加），最優(yōu)做法也隨之改變。如果你不能持續(xù)跟進(jìn)這一領(lǐng)域的發(fā)展，那么你深入鉆研之后掌握的知識(shí)到了幾年之后可能反而成為累贅，當(dāng)年針對(duì)當(dāng)時(shí)硬件的最優(yōu)特殊做法（好比說定制了自己的 mutex 或 lock-free 數(shù)據(jù)結(jié)構(gòu)）在幾年后有可能反而會(huì)拖低性能。還不如按最清晰的方式寫代碼，利用好語言和庫的現(xiàn)成同步設(shè)施，讓編譯器和 libc 的作者去操心“與時(shí)俱進(jìn)”的事。

注意識(shí)別過時(shí)的知識(shí)。比方說《操作系統(tǒng)》講磁盤IO調(diào)度往往會(huì)講電梯算法，但是現(xiàn)在的磁盤普遍內(nèi)置了這一功能（NCQ），無需操作系統(tǒng)操心了。如果你在一個(gè)比較好的學(xué)校，操作系統(tǒng)課程的老師應(yīng)該能指出這些知識(shí)點(diǎn)，避免學(xué)生浪費(fèi)精力；如果你全靠自學(xué)，我也沒什么好辦法，盡量用新版的書吧。類似的例子還有《計(jì)算機(jī)體系結(jié)構(gòu)》中可能會(huì)講 RISC CPU 流水線中的 delay slot，現(xiàn)在似乎也都廢棄了。《計(jì)算機(jī)網(wǎng)絡(luò)》中類似的情況也不少，首先是 OSI 七層模型已經(jīng)被證明是扯淡的，現(xiàn)在國(guó)外流行的教材基本都按五層模型來講（Internet protocol suite），如果你的教材還鄭重其事地講 OSI （還描繪成未來的希望），扔了換一本吧。其次，局域網(wǎng)層面，以太網(wǎng)一家獨(dú)大（幾乎成了局域網(wǎng)的代名詞），F(xiàn)DDI/Token ring/ATM 基本沒啥公司在用了。就說以太網(wǎng)，現(xiàn)在也用不到 CSMA/CD 機(jī)制（因?yàn)?10M 的同軸電纜、10M/100M 的 hub 都過時(shí)了，交換機(jī)也早就普及了），因此碰撞檢測(cè)算法要求“以太網(wǎng)的最小幀長(zhǎng)大于最大傳播延遲的二倍”這種知識(shí)點(diǎn)了解一下就行了。

另外一點(diǎn)是 low level 優(yōu)化的知識(shí)非常容易過時(shí)，編碼時(shí)要避免過度擬合（overfitting）。比方說目前國(guó)內(nèi)一些教科書（特別是大一第一門編程語言的教程）還在傳授“乘除法比加減法慢、浮點(diǎn)數(shù)運(yùn)算比整數(shù)運(yùn)算慢、位運(yùn)算最快”這種過時(shí)的知識(shí)?，F(xiàn)代通用 CPU 上的實(shí)際情況是整數(shù)的加減法和乘法運(yùn)算幾乎一樣快，整數(shù)除法慢很多；浮點(diǎn)數(shù)的加減法和乘法運(yùn)算幾乎和整數(shù)一樣快，浮點(diǎn)數(shù)除法慢很多。因此用加減法代替乘法（或用位運(yùn)算代替算術(shù)運(yùn)算）不見得能提速，反而讓代碼難懂。而且現(xiàn)代編譯器可以把除數(shù)為小整數(shù)的整數(shù)除法轉(zhuǎn)變?yōu)槌朔▉碜?，無需程序員操心。（目前用浮點(diǎn)數(shù)乘法代替浮點(diǎn)數(shù)除法似乎還是值得一做的，例如除以10改為乘以0.1，因?yàn)楦↑c(diǎn)運(yùn)算的特殊性（不滿足結(jié)合律和分配率），阻止了編譯器優(yōu)化。）

類似的 low level 優(yōu)化過時(shí)的例子是早年用匯編語言寫了某流行圖像格式的編解碼器，但隨著 CPU 微架構(gòu)的發(fā)展，其并不比現(xiàn)代 C 語言（可能用上 SIMD）的版本更快，反而因?yàn)槭褂昧?32-bit 匯編語言，導(dǎo)致往 64-bit 移植時(shí)出現(xiàn)麻煩。如果不能派人持續(xù)維護(hù)更新這個(gè)私有庫，還不如用第三方的庫呢?，F(xiàn)在能用匯編語言寫出比 C 語言更快的代碼幾乎只有一種可能：使用 CPU 的面向特定算法的新指令，例如 Intel 的新 CPU （將會(huì)）內(nèi)置了 AES、CRC32、SHA1、SHA256 等算法的指令。不過主流的第三方庫（例如 OpenSSL）肯定會(huì)用上這些手段，及時(shí)跟進(jìn)即可，基本無需自己操刀。（再舉一個(gè)例子，假如公司早先用匯編語言寫了一個(gè)非常高效的大整數(shù)運(yùn)算庫，一直運(yùn)轉(zhuǎn)良好，原來寫這個(gè)庫的高人也升職或另謀高就了。Intel 在 2013 年發(fā)布了新微架構(gòu) Haswell，新增了 MULX 指令，可以進(jìn)一步提高大整數(shù)乘法的效率 GMP on Intel Haswell ，那么貴公司是否有人持續(xù)跟進(jìn)這些 CPU 的進(jìn)化，并及時(shí)更新這個(gè)大整數(shù)運(yùn)算庫呢？或者直接用開源的 GMP 庫，讓 GMP 的作者去操心這些事情？）

如果你要記住結(jié)論，一定要同時(shí)記住前提和適用條件。在錯(cuò)誤的場(chǎng)合使用原本正確的結(jié)論的搞笑例子舉不勝舉。

1. 《Linux內(nèi)核源碼情景分析》上分析內(nèi)核使用 GDT/LDT 表項(xiàng)的狀況，得出進(jìn)程數(shù)不超過 4090 的結(jié)論。如果你打算記住這個(gè)結(jié)論，一定要記住這是在 Linux 2.4.0 內(nèi)核，32-bit Intel x86 平臺(tái)上成立，新版的內(nèi)核和其他硬件平臺(tái)很可能不成立?？赐陼笄f不要張口就來“書上說 Linux 的最大進(jìn)程數(shù)是 4090”。
   

2. 一個(gè) Linux 進(jìn)程最多創(chuàng)建 300 余個(gè)線程，這個(gè)結(jié)論成立的條件是 3GB 用戶空間，線程棧為 10M 或 8M。在 64-bit 下不成立。

3. Reactor 模式只能支持不超過 64 個(gè) handle，這個(gè)結(jié)論成立的條件是 Windows 下使用 WaitForMultipleObjects 函數(shù)實(shí)現(xiàn)的 WFMO_Reactor，對(duì)于 Linux 下使用 poll/epoll 實(shí)現(xiàn)的 Reactor 則無此限制。

4. C STL 的 vector 容器在 clear() 之后不會(huì)釋放內(nèi)存，需要 swap(empty vector)，這是有意為之（C 11 里增加了 shrink_to_fit() 函數(shù)）。不要記成了所有 STL 容器都需要 swap(empty one) 來釋放內(nèi)存，事實(shí)上其他容器（map/set/list/deque）都只需要 clear() 就能釋放內(nèi)存。只有含 reserve()/capacity() 成員函數(shù)的容器才需要用 swap 來釋放空間，而 C 里只有 vector 和 string 這兩個(gè)符合條件。
   

最后一點(diǎn)小建議，服務(wù)端開發(fā)這幾年已經(jīng)普及 64-bit 多核硬件平臺(tái)，因此在學(xué)習(xí)操作系統(tǒng)的時(shí)候，可以不必太關(guān)心單核上特有的做法（在單核時(shí)代，內(nèi)核代碼進(jìn)入臨界區(qū)的辦法之一是關(guān)中斷，但到了多核時(shí)代，這個(gè)做法就行不通了），也不必太花精力在 32-bit 平臺(tái)上。特別是 32-bit x86 為了能支持大內(nèi)存，不得已有很多 work around 的做法（困難在于 32-bit 地址空間不夠?qū)⑷课锢韮?nèi)存映射入內(nèi)核），帶來了額外的復(fù)雜性，這些做法當(dāng)時(shí)有其積極意義，但現(xiàn)在去深入學(xué)似乎不太值得。

關(guān)于項(xiàng)目，我出兩個(gè)練手題目：

一、多機(jī)數(shù)據(jù)處理。有 10 臺(tái)機(jī)器，每臺(tái)機(jī)器上保存著 10 億個(gè) 64-bit 整數(shù)（不一定剛好 10 億個(gè)，可能有上下幾千萬的浮動(dòng)），一共約 100 億個(gè)整數(shù)（其實(shí)一共也就 80GB 數(shù)據(jù)，不算大，選這個(gè)量級(jí)是考慮了 VPS 虛擬機(jī)的容量，便于實(shí)驗(yàn)）。編程求出：

1. 這些數(shù)的平均數(shù)。

2. 這些數(shù)的中位數(shù)。

3. 出現(xiàn)次數(shù)最多的 100 萬個(gè)數(shù)。

*4. （附加題）對(duì)這 100 億個(gè)整數(shù)排序，結(jié)果順序存放到這 10 臺(tái)機(jī)器上。

*5. （附加健壯性要求）你的程序應(yīng)該能正確應(yīng)對(duì)輸入數(shù)據(jù)的各種分布（均勻、正態(tài)、Zipf）。

*6. （附加伸縮性要求）你的程序應(yīng)該能平滑擴(kuò)展到更多的機(jī)器，支持更大的數(shù)據(jù)量。比如 20 臺(tái)機(jī)器、一共 200 億個(gè)整數(shù)，或者 50 臺(tái)機(jī)器、一共 500 億個(gè)整數(shù)。

二、N-皇后問題的多機(jī)并行求解。利用多臺(tái)機(jī)器求出 N-皇后問題有多少個(gè)解。（注意目前的世界紀(jì)錄是 N = 26，A000170 - OEIS ）

1. 8 皇后問題在單機(jī)上的運(yùn)算時(shí)間是毫秒級(jí)，有 92 個(gè)解，編程實(shí)現(xiàn)之。

2. 研究 N-皇后問題的并行算法，寫一個(gè)單機(jī)多線程程序，爭(zhēng)取達(dá)到線性加速比（以 CPU 核數(shù)計(jì)）。再設(shè)法將算法擴(kuò)展到多機(jī)并行。

3. 用 10 臺(tái) 8 核的機(jī)器（一共 80 個(gè) CPU cores），求解 19-皇后和 20-皇后問題，看看分別需要多少運(yùn)行時(shí)間。你的方案能否平滑擴(kuò)展到更多的機(jī)器？

*4. （附加題）如果這 10 臺(tái)機(jī)器的型號(hào)不一，有 8 核也有 16 核，有舊 CPU 也有更快的新 CPU，你該采用何種負(fù)載均衡策略，以求縮短求解問題的時(shí)間（至少比 plain round-robin 算法要好）？

你可以用 Amazon EC2 或 Google GCE 來驗(yàn)證你的程序的正確性和性能，這兩家的虛擬機(jī)都是按小時(shí)（甚至更短）收費(fèi)，開 10 臺(tái)虛擬機(jī)做一個(gè)下午的實(shí)驗(yàn)也花不了多少錢。

往期推薦

如何設(shè)計(jì)結(jié)構(gòu)體

高端知識(shí)點(diǎn)：折疊表達(dá)式（我也是第一次知道）

cout和printf，選擇哪個(gè)更好？

我是怎么調(diào)試代碼的？

寫了一段高端C 代碼

我常用的10個(gè)C 新特性

編譯器如何實(shí)現(xiàn)lambda表達(dá)式？