====更新日記====
update1: 20160211 更新了部分標(biāo)題， 增加了lab1的介紹。
===============

閑扯

吶， Introduction to Computer Systems (課號15213) 就是鄙校 CMU 的招牌課程了。 15213 在 CMU 是如此受歡迎， 以至于幾乎每個人都會選這門課； 實在選不到的人會在暑假上這么課的 online 版。 相當(dāng)巧合的是， 15213 正好是 CMU 的郵編（zip code）。 因此，這門課在 CMU 又被親切地稱為『The course that gives CMU its ZIP !』

相信我，不要被這個“Introduction”騙到： 15213 跟國內(nèi)那些“大學(xué)計算機(jī)基礎(chǔ)”完全不是一個量級。 這門課的內(nèi)容非常扎實， 可以說是涵蓋了計算機(jī)系統(tǒng)的方方面面； 配套的編程練習(xí)也相當(dāng)有挑戰(zhàn)性， 絕對不會讓人有昏昏欲睡的感覺。

213 還有配套的教材 —— 大名鼎鼎的 CSAPP。 如果要列一個“程序員必讀書單”的話， 那么CSAPP一定會出現(xiàn)在前三的位置 ; ) 課程內(nèi)容跟教材是完全對應(yīng)的： 每一章著重講解一個重要的概念， 并配以練習(xí)題。 CSAPP 第一章介紹了計算機(jī)執(zhí)行一個程序的過程；第二章介紹了計算機(jī)存儲各種數(shù)據(jù)的方式，包括整型數(shù)和浮點數(shù)。第三章是一個重點，介紹了現(xiàn)代計算機(jī)的堆棧結(jié)構(gòu)。本章涉及很多匯編語言，因此可能會有點難啃。第四章分析了內(nèi)存性能。第五章教你提高程序的性能。第六章忘了。第七章忘了。第八章是關(guān)于系統(tǒng)中斷的。第九章涉及內(nèi)存管理，包括虛擬內(nèi)存，內(nèi)存分配等等。第十章到第十二章淺嘗輒止講了concurrency和network programming的基礎(chǔ)內(nèi)容。

難度

213 的難度中等，每個周大約需要15小時時間。 相信我， 這15小時絕對沒有水分。 對于那些計算機(jī)基礎(chǔ)不太好的人來說，甚至可能需要20-30個小時。

如果僅僅是把教材里的東西講一遍，那么 213 絕對不會成為 CMU 的神課。 213 最精華的部分在于它的七個 lab。 在上課+看教材的基礎(chǔ)上，再獨立將這七個 lab 搞定， 那么編程功力一定會有很大的提升哈哈哈。

labs

lab1: datalab

datalab 的核心是 bit manipulation。 為了讓學(xué)生更好地理解數(shù)據(jù)在計算機(jī)內(nèi)的存儲形式， datalab 要求用有限數(shù)量的操作符來實現(xiàn)一些位操作。 比如， 在我那個學(xué)期， lab1 里有一道題目是將一個浮點數(shù)乘以0.5。 以下是這道題目的要求以及我的解答：

/* 
 * float_half - Return bit-level equivalent of expression 0.5*f for
 * floating point argument f.
 * Both the argument and result are passed as unsigned int's, but
 * they are to be interpreted as the bit-level representation of
 * single-precision floating point values.
 * When argument is NaN, return argument
 * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 * Max ops: 30
 * Rating: 4
 */
unsigned float_half(unsigned uf) {
/* use masks to extract the sign, exp, frac of a fp number
 * if exp is 0xFF, means infinity or nan, just return uf
 * if exp is 0 or 1, according to the table of denormalized and normalized fp numbers
 * shift the temp right by 1, meaning that divide by 2, and if frac's last two bits are 11, there is a round problem, deal with it
 * in general cases, just subtract exp by one indicate half
 */
    int s_mask = 0x80000000;
    int exp_mask = 0x7F800000;
    int frac_mask = 0x007FFFFF;
    int s = uf & s_mask;
    int exp = (uf & exp_mask) >> 23;
    int frac = uf & frac_mask;
    int temp = 0;
    int mask_1 = 0x00FFFFFF;
    if (exp == 0xFF) return uf;//inf and nan
    else if (exp == 0 || exp == 1) {
        temp = (uf & mask_1) >> 1;
        if ((frac & 3) == 3) temp ++;
        return s | temp;
    }
    else return s | ((exp - 1) << 23) | frac;
}

上完這個課之后， 我還看了一下同學(xué)們的代碼， 真是八仙過海各顯神通。 為了搞定這個作業(yè)， 大家毫不留情地用了各種奇技淫巧。 有的人甚至去查服務(wù)器（每個lab的評分都是在服務(wù)器上進(jìn)行的）的 CPU 型號， 試圖找到 CPU 的某條隱藏指令， 從而用更少的操作符數(shù)量來實現(xiàn)函數(shù)功能。 說到這兒， 你可能會問， 為什么大家這么拼？ 功能實現(xiàn)了不就行了嗎？ 這就涉及 213 的另一個有趣之處： scoreboard 機(jī)制。

簡單來說， 每次作業(yè)都有一個對應(yīng)的scoreboard， 上面顯示每個人的分?jǐn)?shù)。 對于那些有性能要求的作業(yè)（比如lab1）， scoreboard 會根據(jù)代碼的性能來排名； 對于那些沒有性能要求的作業(yè)， scoreboard 則會按照提交時間的早晚來排名。 為了能在 scoreboard 上占到一個好名次， 常常有人通宵達(dá)旦地優(yōu)化自己的代碼。 剛才提到的lab1， 滿分是63分。 我用大約190個操作符便達(dá)到滿分， 而排名第一的居然只用了108個操作符， 簡直令人發(fā)指。

扯遠(yuǎn)了。 總而言之 lab1 對于理解計算機(jī)數(shù)據(jù)的格式有相當(dāng)大的幫助。 做完作業(yè)后， 我對 int 以及 float 的理解加深了一個層次， 在后來的面試中碰到 bit manipulation 的題一點都不會害怕， 反而會感到一點興奮。

lab2: bomb lab

bomb lab 的內(nèi)容是『拆炸彈』。 當(dāng)然， 這里的炸彈不是真的炸彈， 而是一個編譯好的 linux 程序。 要想拆掉這個炸彈， 需要連續(xù)輸入六個特定的字符串（key）。 如果你輸錯了任何一個 key， 程序就會“爆炸”， 并自動登錄課程服務(wù)器， 扣除一定的分?jǐn)?shù)。

拆彈過程需要用到簡單的逆向工程。 具體方法是用 gdb 來調(diào)試。 為了避免扣分， 需要在爆炸模塊前面設(shè)置斷點 —— 這樣一來， 即使輸錯字符串， 程序也不會運行到爆炸模塊。 為了找到那key， 學(xué)生得一行一行分析反匯編出來的匯編代碼， 搞明白代碼的控制流， 并找到以字符串形式存儲在程序中的key。 整個拆彈的過程非常驚險刺激， 玩得我簡直停不下來 XD。

lab3: attack lab

第三個lab比較邪惡，是 stack overflow 攻擊。 這個lab包含兩個程序： 正常的程序 A 和惡意的程序 B。 正常情況下， 在執(zhí)行程序 A 的時候， 是不會調(diào)用程序 B 的。 我們的任務(wù)是讓程序 A 執(zhí)行程序 B。 怎么樣， 是不是聽上去很黑客很厲害？ 具體的內(nèi)容就不劇透了。 總之， 搞定這個lab之后， 我對x86的stack frame以及程序的調(diào)用過程有了深刻的了解。

lab4: cache lab

第四個lab的目的是實現(xiàn)一個Least Recently Used Cache (LRU Cache)。

Cache 是提升計算機(jī)存儲系統(tǒng)性能的利器。 要理解cache，首先要理解現(xiàn)代計算機(jī)的存儲 hierarchy： 寄存器-內(nèi)存-硬盤。 從上往下， 價格越來越便宜，存儲容量越來越大， 但速度越來越慢。

既然寄存器最快， 那么為什么不全部采用寄存器作為存儲器呢？ 原因很簡單： 寄存器的價格太過昂貴。 反之亦然： 我們也不能一味貪圖便宜而全部用硬盤， 否則整機(jī)性能會大打折扣。 因此， 我們需要在價格和性能之間做一個tradeoff， 為不同的計算機(jī)配置不同的存儲器系統(tǒng)。

lab5: shell lab

shell lab 的任務(wù)是實現(xiàn)一個 shell。 不過， 這個shell是高度簡化的。 我們不需要 build from scratch； 我們可以在現(xiàn)有的bash的基礎(chǔ)上寫自己的shell。 涉及的知識有 system call，interrupt handler 和各種 signal。

lab6: malloc lab

傳說中最難的一個 lab。 任務(wù)是寫一個 malloc 函數(shù)。要實現(xiàn)一個 malloc 是不難的； 難的是benchmark。 以后再說。

lab7: proxy lab

第七個lab是proxylab。這個proxy需要支持 http1.0 協(xié)議。做完這個lab后對多線程有更深入的理解了哈。

相關(guān)資源

配套slides

CMU 15213課程網(wǎng)站上可以下載到。

視頻

CMU 貌似沒有加入任何 MOOC，也不允許學(xué)生上課時錄影，因此沒法在網(wǎng)上找到213的教學(xué)視頻。但是，coursera上有一門 Hardware Software Interface課，用的是213的教材，lab也是完全照搬213。據(jù)說老師講得非常好（UW的老師），甚至比CMU版本還要好。想學(xué)的話推薦去注冊這門課。