模型的重要性

1、模型的重要性網(wǎng)絡(luò)算法學(xué)的一個(gè)中心難題是，它要求跨領(lǐng)域的知識(shí)，包括協(xié)議、硬件、體系架構(gòu)、操作系統(tǒng)、 算法等。 但是一個(gè)人不可能對(duì)所有這些領(lǐng)域都非常了解，因此需要不同領(lǐng)域的專家協(xié)作才能設(shè)計(jì)出高效的網(wǎng)絡(luò)系統(tǒng)。不同領(lǐng)域的專家之間如何進(jìn)行有效的對(duì)話呢？這時(shí)模型就很有用了，模型既可以把問(wèn)題講清楚，又不涉及不必要的細(xì)節(jié)。最低程度， 模型應(yīng)能定義所需要的術(shù)語(yǔ)，這樣不同領(lǐng)域的專家就能交流了（能聽(tīng)懂對(duì)方的話了）。最好情況：領(lǐng)域外的專家可以根據(jù)模型進(jìn)行設(shè)計(jì)，并可由領(lǐng)域內(nèi)的專家對(duì)設(shè)計(jì)進(jìn)行檢驗(yàn)。 比如，算法設(shè)計(jì)者雖然不懂得硬件，但能夠根據(jù)硬件專家給出的模型設(shè)計(jì)出與硬件相匹配的算法，并在硬件上進(jìn)行驗(yàn)證。這正是本章的目的。

2、下面給出幾個(gè)與網(wǎng)絡(luò)計(jì)算機(jī)系統(tǒng)性能有關(guān)的抽象模型。2.1 協(xié)議抽象模型協(xié)議是網(wǎng)絡(luò)的核心，各種網(wǎng)絡(luò)功能都是通過(guò)執(zhí)行協(xié)議來(lái)實(shí)現(xiàn)的。協(xié)議定義了對(duì)等實(shí)體之間通信的規(guī)則， 對(duì)等實(shí)體之間通過(guò)交換報(bào)文來(lái)實(shí)現(xiàn)通信。 網(wǎng)絡(luò)協(xié)議定義了報(bào)文的格式和交換次序， ，協(xié)議還定義了調(diào)用接口。因此，可將協(xié)議看成是一個(gè)加上了接口和報(bào)文格式的狀態(tài)機(jī)。 所有協(xié)議都可以抽象為圖中的狀態(tài)機(jī)模型： 。常見(jiàn)而耗時(shí)的功能這門課關(guān)注的是系統(tǒng)性能，而TCP/IP 協(xié)議是因特網(wǎng)的核心，所以我們把基于TCP/IP的協(xié)議狀態(tài)機(jī)需要經(jīng)常執(zhí)行而又非常耗時(shí)的功能抽象出來(lái)，這些功能正是我們優(yōu)化實(shí)現(xiàn)的重點(diǎn)。圖示的模型將貫穿于整個(gè)課程中。圖的中部是協(xié)議處理部分（傳

3、輸層、網(wǎng)絡(luò)層）；圖的下部是與網(wǎng)絡(luò)的接口部分，涉及數(shù)據(jù)包的收發(fā)；圖的上部是應(yīng)用程序部分，涉及應(yīng)用數(shù)據(jù)的交付。在圖的下部 （ Data Manipulation ）：協(xié)議狀態(tài)機(jī)必須從網(wǎng)絡(luò)接收和發(fā)送數(shù)據(jù)包。這涉及到數(shù)據(jù)操作， 即必須讀或?qū)憯?shù)據(jù)包中的每一個(gè)字節(jié)（當(dāng)操作時(shí)間與數(shù)據(jù)長(zhǎng)度成正比時(shí)，通常認(rèn)為這是一個(gè)高開(kāi)銷的操作）。在此過(guò)程中需要分配資源，如分配緩沖區(qū)、CPU 時(shí)間等（緩沖區(qū)分配、任務(wù)調(diào)度都需要操作系統(tǒng)參與）。圖的中部 （ Protocol processing ）描述了許多協(xié)議都需要的一些功能，協(xié)議處理開(kāi)銷隨著包數(shù)量的增加而增大：（ 1）很多協(xié)議允許將大塊數(shù)據(jù)分成小段傳輸，因而需要重組功能。（

4、 2）協(xié)議都需要查找或者修改一些狀態(tài)。例如，每個(gè)TCP 包到來(lái)都會(huì)導(dǎo)致TCP 去查找 TCP 連接表并修改連接狀態(tài)，每個(gè)IP 包到來(lái)都會(huì)導(dǎo)致 IP 去查找轉(zhuǎn)發(fā)表等。（ 3）協(xié)議都需要設(shè)置定時(shí)器。（ 4）如果協(xié)議模塊需要處理多個(gè)不同的客戶程序，它需要有效地調(diào)度這些客戶，例如TCP 必須調(diào)度對(duì)不同連接的處理。在圖的上部：協(xié)議狀態(tài)機(jī)必須將數(shù)據(jù)包交付（Demultiplex ）給某個(gè)客戶程序。在某些情況下，客戶程序程序需被激活，產(chǎn)生開(kāi)銷較大的控制切換（control transfer ）。比如，當(dāng)TCP收到一個(gè)web 頁(yè)時(shí)，根據(jù)端口號(hào)將數(shù)據(jù)包交給web 瀏覽器程序，并可能需要喚醒運(yùn)行瀏覽器的進(jìn)程。當(dāng)目

5、標(biāo)程序很多的時(shí)候，解復(fù)用和控制切換都會(huì)產(chǎn)生很大的開(kāi)銷。本課程的主要內(nèi)容就是仔細(xì)研究這些功能的實(shí)現(xiàn)。我們會(huì)看到， 盡管這些常見(jiàn)功能一般來(lái)說(shuō)開(kāi)銷很大，但是通過(guò)正確的技術(shù)是可以降低它們的開(kāi)銷的。重要的性能度量網(wǎng)絡(luò)中兩個(gè)最重要的性能指標(biāo)：吞吐量，延遲。我們比較熟悉比特速率這個(gè)指標(biāo)，但在某些情況下我們更關(guān)注包速率這個(gè)指標(biāo)。比如，對(duì)于路由器來(lái)說(shuō)，每個(gè)包的處理開(kāi)銷是差不多的，包括包頭檢查、IP 地址表查找等。包的長(zhǎng)度越短， 單位時(shí)間內(nèi)包的數(shù)量就越多，路由器的負(fù)擔(dān)就越重，因此包速率是更能夠反映路由器處理能力的指標(biāo)。因此在做路由器壓力測(cè)試時(shí)，輸入的都是最小長(zhǎng)度的包。當(dāng)然，如果我們關(guān)注與數(shù)據(jù)處理有關(guān)的功能，比如內(nèi)

6、容掃描、加密/解密等，那么長(zhǎng)包的處理壓力大，這時(shí)我們會(huì)采用比特速率這個(gè)指標(biāo)。線速處理是網(wǎng)絡(luò)系統(tǒng)優(yōu)化的重要目標(biāo)之一。為滿足線速處理要求（當(dāng)前數(shù)據(jù)包必須在下一個(gè)包到來(lái)前處理完） ，必須限制最壞情況下數(shù)據(jù)包的處理時(shí)間。所以，往往我們對(duì)最壞情況延遲更感興趣。性能測(cè)量分為全局性能測(cè)量（如端到端延遲和帶寬）和本地性能測(cè)量 （如路由器查找速度）。盡管全局性能測(cè)量對(duì)于整個(gè)網(wǎng)絡(luò)的性能很重要，但本課程只關(guān)注本地性能測(cè)量。大多數(shù)網(wǎng)絡(luò)管理工具（如HP 的 OpenView ）用于全局測(cè)量，本地測(cè)量需要的工具是在計(jì)算機(jī)內(nèi)部測(cè)量性能的工具，比如英特爾的VTune 。因特網(wǎng)環(huán)境的特點(diǎn)當(dāng)我們優(yōu)化任何一個(gè)系統(tǒng)時(shí)，都要考慮它的運(yùn)

7、行環(huán)境。不要試圖做出一個(gè)在各種情況下都最優(yōu)的系統(tǒng)，因?yàn)橥ㄓ煤妥顑?yōu)也是一對(duì)矛盾。就像我們前面介紹過(guò)的DIR24-8算法，它充分利用了因特網(wǎng)中絕大多數(shù)路由表項(xiàng)的前綴不超過(guò)24 位、24 位索引表消耗內(nèi)存空間不大這個(gè)特點(diǎn)設(shè)計(jì)的，對(duì)于長(zhǎng)度為128 位的 IPv6 地址就不適用。（將來(lái)你們做研究時(shí)也要注意這個(gè)問(wèn)題）因此，我們要設(shè)計(jì)因特網(wǎng)中的高效網(wǎng)絡(luò)系統(tǒng)，那么一定要了解因特網(wǎng)環(huán)境的特點(diǎn)。因此鏈路速度：鏈路速度高意味著包的最大處理時(shí)間在縮短。TCP 占主導(dǎo)：傳統(tǒng)應(yīng)用主要使用TCP，P2P 文件共享等也使用TCP 優(yōu)化很重要。TCP（要求可靠傳輸） ，小包：研究表明，路由器收到的包中大約一半為最小長(zhǎng)度（40

8、字節(jié)）的TCP 響應(yīng)包。在移動(dòng)互聯(lián)網(wǎng)應(yīng)用中，大量的都是小包。延遲很長(zhǎng)： 網(wǎng)絡(luò)中的實(shí)際來(lái)回延遲遠(yuǎn)遠(yuǎn)超過(guò)光的傳輸延遲。測(cè)量發(fā)現(xiàn)， 數(shù)據(jù)包穿過(guò)美國(guó)的延遲時(shí)間平均為 241ms，而光的傳輸延遲不超過(guò) 30ms。延遲增大可能是由追求高吞吐量造成的，比如在調(diào)制解調(diào)器上的批量壓縮和在路由器中的流水處理，也可能因?yàn)閾砣斐?。局部性很差?骨干網(wǎng)上的流量研究表明，在一個(gè)非常短的時(shí)間內(nèi)大約有一百萬(wàn)個(gè)并發(fā)流（具有不同的<源，目的 >對(duì)）經(jīng)過(guò)一個(gè)路由器，因此局部性很小。也就是說(shuō)，在一個(gè)包上執(zhí)行的計(jì)算在未來(lái)短時(shí)間內(nèi)重用到另一個(gè)包上的可能性很小， 因此路由緩存不奏效。 正因?yàn)槿绱耍酚删彺嬖诂F(xiàn)在的高速路由器中

9、已經(jīng)不用了，轉(zhuǎn)而使用高速的 IP 地址查找技術(shù)，如硬件實(shí)現(xiàn)的 DIR24-8 算法。從因特網(wǎng)環(huán)境的特點(diǎn)，我們可以看到網(wǎng)絡(luò)系統(tǒng)面臨的挑戰(zhàn)：高速高速 +大規(guī)模并發(fā)流量=局部性差， cache 用不上； TCP 很重要，但+ 小包 =包速率很快； TCP 開(kāi)銷大、處理復(fù)雜。2.2 存儲(chǔ)器在現(xiàn)代計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)中，訪存是最大的性能瓶頸，因?yàn)樵L存延遲比指令執(zhí)行時(shí)間長(zhǎng)很多，而且處理器速度和訪存速度之間的鴻溝越來(lái)越寬，使得訪存瓶項(xiàng)問(wèn)題更加突出。在端節(jié)點(diǎn)和路由器中，數(shù)據(jù)包、狀態(tài)信息、指令等都是保存在內(nèi)存中，因此，訪存構(gòu)成了端節(jié)點(diǎn)和路由器的主要性能瓶頸。許多的系統(tǒng)優(yōu)化工作都是圍繞該問(wèn)題的解決而展開(kāi)的。為了優(yōu)化訪存

10、性能，必須了解不同類型存儲(chǔ)器的特性。存儲(chǔ)器的種類（1）寄存器寄存器由一組有序的觸發(fā)器構(gòu)成。大多數(shù)現(xiàn)代處理器中都有一組片上寄存器。一個(gè)電路邏輯訪問(wèn)同一個(gè)片上的寄存器是很快的，大約為0.5-1ns。（ 2） SRAM靜態(tài)隨機(jī)訪問(wèn)存儲(chǔ)器（ SRAM ）由一組寄存器組成。如果有 N 個(gè)寄存器，則使用 log2N 個(gè)地址位進(jìn)行尋址。由于地址解碼延遲，訪問(wèn)片上 SRAM 只比訪問(wèn)片上寄存器慢一點(diǎn)點(diǎn)。一般情況下，片上 SRAM 的訪問(wèn)時(shí)間為 1-2ns，片外 SRAM 的訪問(wèn)時(shí)間為 5-10ns?，F(xiàn)在的高端多核處理器的 cache 可以達(dá)到三級(jí)，每個(gè)核擁有獨(dú)立的 L1 和 L2 cache，一個(gè)芯片內(nèi)的所有

11、核共用一個(gè) L3 cache，它們的訪存延遲要看產(chǎn)品手冊(cè)。（3） DRAMDRAM 內(nèi)部將存儲(chǔ)單元組成成行、列二維結(jié)構(gòu)，先提供行地址，再提供列地址，因此，DRAM 的訪問(wèn)速度比SRAM 低。另外，由于預(yù)充電的需要，DRAM 連續(xù)讀之間需要一點(diǎn)延遲，所以連續(xù)讀的延遲要大一些。以上三種存儲(chǔ)器，容量依次增大， 但訪存速度依次降低?，F(xiàn)在又出現(xiàn)了許多新型的存儲(chǔ)器，如非易失性存儲(chǔ)器，即當(dāng)電源關(guān)閉后所存儲(chǔ)的數(shù)據(jù)不會(huì)消失。ROM/EPROM也是非易失型存儲(chǔ)器， 但它們一旦寫入數(shù)據(jù)后不可更改，新型非易失性存儲(chǔ)器是允許動(dòng)態(tài)讀寫的。這類存儲(chǔ)器中有的只能順序讀寫、有的可以隨機(jī)讀寫，有的讀快寫慢等，在使用時(shí)需要了解這些

12、存儲(chǔ)器的新特性。在這里我們大致有個(gè)量級(jí)的概念就可以了，即片外 SRAM 比寄存器慢10 倍，片外 DRAM又比片外SRAM 慢 10 倍。（ 4）快頁(yè)內(nèi)存（ page-mode DRAM ）頁(yè)模式 DRAM（快頁(yè)內(nèi)存） 使用 DRAM 的結(jié)構(gòu)特點(diǎn)來(lái)優(yōu)化對(duì)相鄰存儲(chǔ)單元的連續(xù)訪問(wèn)。DRAM 控制器先提供行地址，再提供列地址。當(dāng)提供行地址時(shí)，選中的那一行數(shù)據(jù)（4字節(jié)）進(jìn)入到 row buffer 中；再提供列地址，選中要讀取的字節(jié)。（ DRAM 的做法）快頁(yè)內(nèi)存的做法：如果要訪問(wèn)的4 個(gè)字節(jié)剛好位于同一行 （頁(yè)）中， 則提供行地址后這些數(shù)據(jù)就全部進(jìn)入了row buffer 中，不需要再給出列地址，因

13、此可以加快對(duì)局部性好的數(shù)據(jù)的連續(xù)訪問(wèn)（不需要讀4 次）。知道快頁(yè)內(nèi)存具有這個(gè)特性后，我們就可以有意識(shí)地組織數(shù)據(jù)，讓那些要被讀取的數(shù)據(jù)保存在連續(xù)位置，這樣可以顯著加快訪問(wèn)速度。（ 5）交織內(nèi)存（ Interleaved DRAM ）假定 DRAM的讀寫周期為100ns，即在地址線上輸出地址后，將在 100ns 后得到要訪問(wèn)的數(shù)據(jù)。假定輸出一個(gè)地址只需要10ns，那么在等待數(shù)據(jù)到來(lái)的過(guò)程中，可以在地址線上輸出其它bank 中的地址。 當(dāng)輸出了10 個(gè) bank 中的地址后， 在數(shù)據(jù)線上將依次出現(xiàn)這10 個(gè)bank 中要訪問(wèn)的數(shù)據(jù)。如果一個(gè) DRAM 的字長(zhǎng)為 32 位，讀寫周期為 100ns，則單

14、個(gè) DRAM bank 的最大吞吐量約為 40MB 。采用以上的交織內(nèi)存，如果能夠合理安排讀操作，則內(nèi)存吞吐量可以達(dá)到400MB 。盡管很早就有了使用多個(gè)內(nèi)存bank 的想法，但是直到 2000 年左右才有這樣的產(chǎn)品出現(xiàn)。在每個(gè) bank 內(nèi)還允許快頁(yè)訪問(wèn)。基于這些核心思想的內(nèi)存技術(shù)有很多，不同在于容量大小、讀寫協(xié)議、bank 數(shù)等，典型的例子包括具有2 個(gè) bank 的 SDRAM 和具有 16 個(gè) bank 的 RDRAM 。舉例：流ID 的流水化查找下面舉一個(gè)例子，說(shuō)明如何利用存儲(chǔ)器的特點(diǎn)設(shè)計(jì)高效的算法。設(shè)計(jì)方案考慮由于有線速處理的要求，我們必須限制最壞情況下的查找時(shí)間（查找流ID 的最

15、長(zhǎng)時(shí)間不能超過(guò)128ns），考慮使用一個(gè)平衡二叉樹(shù)。遍歷一棵樹(shù)的邏輯是很簡(jiǎn)單的，關(guān)鍵是把樹(shù)保存在什么地方？為了獲得高速度，理想情況下流 ID 和計(jì)數(shù)器應(yīng)保存在SRAM 中。然而，當(dāng)前的核心路由器中大約有100 萬(wàn)條并發(fā)的網(wǎng)絡(luò)流，在SRAM 中保持 100 萬(wàn)條流的狀態(tài)是很昂貴的。（假設(shè)計(jì)數(shù)器為16 比特，則100萬(wàn)條流至少需求（96+16） *1M=14MB ）如果使用普通的DARM實(shí)現(xiàn)分支因子為2的二叉樹(shù)，查找一個(gè)流ID需要log 21000000=20 次訪存。 即使按照最樂(lè)觀的 DRAM 訪存周期 50ns 來(lái)計(jì)算， 整個(gè)的查找時(shí)間為1微秒。使用 RDRAM實(shí)現(xiàn)二分查找為了縮短查找時(shí)間，

16、 可以考慮使用交織內(nèi)存，多個(gè)包一起查。 RDRAM 集成了 16 個(gè) bank，可以使用 RDRAM實(shí)現(xiàn)一棵高度為16 的二叉樹(shù)。講課時(shí)畫(huà)一個(gè)圖。RDRAM 一次讀操作的時(shí)間約為60ns。盡管一個(gè)流ID 的查找需要16*60ns 的時(shí)間，但查找芯片可以同時(shí)查找 16 個(gè)包，使得總的查找性能為每個(gè)數(shù)據(jù)包 60ns，可以滿足查找時(shí)間的要求。但是，層次為 16 的二叉樹(shù)只能有 216=64K 個(gè)流 ID ，不能滿足規(guī)模的要求！需要增加每個(gè)節(jié)點(diǎn)保存的流 ID 。網(wǎng)絡(luò)存儲(chǔ)子系統(tǒng)設(shè)計(jì)技術(shù)流 ID 查找使用了在網(wǎng)絡(luò)芯片的存儲(chǔ)子系統(tǒng)設(shè)計(jì)中經(jīng)常使用的一些技術(shù)（前2 項(xiàng)）。（ 1）交錯(cuò)內(nèi)存和流水線：類似的技術(shù)也可

17、用于IP 查找、包分類和包調(diào)度等。多個(gè)bank 可以用多個(gè)外部存儲(chǔ)來(lái)實(shí)現(xiàn)。（ 2）寬字并行：為了一次讀入更多的數(shù)據(jù)，使用可并行處理的寬內(nèi)存字。這可以使用 DRAM ，并利用其快頁(yè)模式；或者使用SRAM ，并使得每個(gè)內(nèi)存字更寬。（ 3）組合 DRAM和 SRAM ：由于 SRAM 快而貴，而DRAM 便宜卻慢，因此將這兩種技術(shù)組合起來(lái)可以得到一個(gè)最佳的平衡。將SRAM 作為 DRAM數(shù)據(jù)庫(kù)的緩存是很經(jīng)典的做法。2.3 端節(jié)點(diǎn)架構(gòu)本課程關(guān)注端節(jié)點(diǎn)， 因此我們看一下端節(jié)點(diǎn)的架構(gòu)。 端節(jié)點(diǎn)就是通用計(jì)算機(jī)， 由處理器、存儲(chǔ)器、總線、 I/O 設(shè)備組成。如果處理器的狀態(tài)只保存在DRAM 中，則一條指令將花

18、費(fèi)60ns 去讀或?qū)懸淮蝺?nèi)存，這會(huì)非常慢。事實(shí)上，處理器使用cache 來(lái)提高速度。Cache 的使用效果與局部性由于每個(gè)包最多只經(jīng)過(guò) I/O 總線兩次（收和發(fā)） ，而包處理過(guò)程中需要訪存很多次，所以我們關(guān)注訪存瓶頸。為了填補(bǔ)處理速度和訪存速度的鴻溝，現(xiàn)代計(jì)算機(jī)系統(tǒng)充分利用是， cache 的使用效果與應(yīng)用的時(shí)空局部性有關(guān)。cache 來(lái)提高性能。但時(shí)間局部性：一個(gè)存儲(chǔ)位置在短時(shí)間內(nèi)被再次訪問(wèn)。由于數(shù)據(jù)被訪問(wèn)時(shí)會(huì)進(jìn)入cache，當(dāng)短時(shí)間內(nèi)再次訪問(wèn)該數(shù)據(jù)時(shí)，該數(shù)據(jù)很大可能仍在cache 中，從而可以顯著減少訪存時(shí)間。空間局部性： 一個(gè)存儲(chǔ)位置被訪問(wèn)后，其鄰近位置在短時(shí)間內(nèi)被訪問(wèn)。X86 處理器基

19、于空間局部性假設(shè)實(shí)現(xiàn)了預(yù)?。好慨?dāng)讀取一個(gè)32 比特的字時(shí)， 處理器預(yù)取連續(xù)的128 比特（一個(gè) cache 行）到 cache 中，這樣訪問(wèn)其余的96 比特將不會(huì)產(chǎn)生cache miss。高速數(shù)據(jù)包流基本不呈現(xiàn)時(shí)間局部性：一方面，數(shù)據(jù)包本身不會(huì)被反復(fù)處理；另一方面，同一個(gè)流的數(shù)據(jù)包往往被大量其它的流隔開(kāi)，前一個(gè)包的查找結(jié)果（如下一跳、 分類 ID 等）很快被踢出cache，無(wú)法重用。提高算法及數(shù)據(jù)結(jié)構(gòu)的空間局部性端節(jié)點(diǎn)網(wǎng)絡(luò)功能的高效實(shí)現(xiàn)通常將重點(diǎn)放在提高算法及數(shù)據(jù)結(jié)構(gòu)的空間局部性上。比如， 1）設(shè)計(jì)緊湊的數(shù)據(jù)結(jié)構(gòu)，使其能夠常駐cache 不被換出； 2）將隨機(jī)訪問(wèn)（鏈表、樹(shù)）變?yōu)轫樞蛟L問(wèn) （數(shù)

20、組），如 DHash 的工作； 3）對(duì)相同 /相近位置的數(shù)據(jù)操作盡可能放在一起；4）將經(jīng)常要被一起訪問(wèn)的數(shù)據(jù)放在連續(xù)位置，且與cache 行對(duì)齊，如數(shù)據(jù)結(jié)構(gòu)中成員的長(zhǎng)度及存放位置。這些措施很簡(jiǎn)單，但是往往會(huì)有顯著的效果。舉別體偉（相同位置的操作放在一起）和王燕飛（用戶態(tài)驅(qū)動(dòng)中包緩沖區(qū)長(zhǎng)度定義， 1518B vs 2KB ，跨頁(yè)）的例子。有經(jīng)驗(yàn)的程序員會(huì)非常注意這些問(wèn)題， 他們通常不會(huì)使用復(fù)雜的算法， 但寫出的程序非常高效。 我們的學(xué)生一遇到性能問(wèn)題，往往就會(huì)從算法上找原因，但其實(shí)是不得要領(lǐng)。順便說(shuō)一下學(xué)生在優(yōu)化 checksum 時(shí)遇到的問(wèn)題： 用了較多的 if-else 語(yǔ)句，代碼行數(shù)少，但

21、運(yùn)行慢。原因：增加了指令 cache miss。因此，以代碼行數(shù)（指令數(shù)）來(lái)衡量代碼效率是不準(zhǔn)確的，關(guān)鍵是訪存是否高效。以上例子說(shuō)明， 體系結(jié)構(gòu)知識(shí)對(duì)于編寫高質(zhì)量的軟件是非常有用的。 沒(méi)有體系結(jié)構(gòu)背景的人，根本不知道這里面有這么多的陷阱。2.4 操作系統(tǒng)對(duì)端節(jié)點(diǎn)上的應(yīng)用性能進(jìn)行優(yōu)化， 一定要了解操作系統(tǒng)對(duì)應(yīng)用性能的影響， 因?yàn)樗呛艽笠徊糠珠_(kāi)銷的來(lái)源。為什么要設(shè)計(jì)操作系統(tǒng)呢？操作系統(tǒng)是為了解決在裸機(jī)上編程困難而設(shè)計(jì)的。好的抽象提高了程序員的生產(chǎn)效率，但卻帶來(lái)了兩個(gè)代價(jià)。 （ 1）實(shí)現(xiàn)抽象的機(jī)制是有代價(jià)的，比如，調(diào)度進(jìn)程會(huì)產(chǎn)生開(kāi)銷，管理虛擬內(nèi)存會(huì)產(chǎn)生開(kāi)銷。（ 2）抽象阻礙程序員對(duì)資源的充分利用，

22、比如，操作系統(tǒng)不允許程序員將查找數(shù)據(jù)結(jié)構(gòu)一直保持在cache 中。下面我們給出這三種抽象的底層機(jī)制與代價(jià)的模型。（ 1） 依靠進(jìn)程實(shí)現(xiàn)不間斷計(jì)算的抽象由于外部中斷的頻繁到來(lái)， 處理器上的程序運(yùn)行不了多久就會(huì)被打斷。 但是，操作系統(tǒng)通過(guò)進(jìn)程提供給程序員不間斷、順序計(jì)算的抽象。進(jìn)程抽象是通過(guò)三個(gè)機(jī)制實(shí)現(xiàn)的：上下文切換，調(diào)度，保護(hù)。圖 2.11 給出了上下文切換和調(diào)度的示意圖。在進(jìn)程 P1 的運(yùn)行過(guò)程中遇到一個(gè)中斷；P1的狀態(tài)（上下文）被保存到內(nèi)存中，運(yùn)行中斷程序；然后調(diào)度器程序運(yùn)行，選擇進(jìn)程P2 運(yùn)行； P2 的狀態(tài)被恢復(fù)，P2 運(yùn)行，；最后，調(diào)度器又調(diào)度P1 運(yùn)行。在此過(guò)程中，P1 覺(jué)得自己一直

23、獨(dú)占CPU 在運(yùn)行。但是我們看到， 處理器的時(shí)間線包含了進(jìn)程之間的上下文切換（狀態(tài)保存及恢復(fù)）以及調(diào)度器的運(yùn)行，這些就是進(jìn)程抽象帶來(lái)的開(kāi)銷。另外，操作系統(tǒng)的保護(hù)機(jī)制確保應(yīng)用進(jìn)程不會(huì)對(duì)操作系統(tǒng)內(nèi)核產(chǎn)生影響，以及確保進(jìn)程隔離。 比如，操作系統(tǒng)使用保護(hù)環(huán)來(lái)規(guī)定不同進(jìn)程的最高權(quán)限，對(duì)于應(yīng)用進(jìn)程無(wú)權(quán)訪問(wèn)的資源，可以向操作系統(tǒng)發(fā)送一個(gè)請(qǐng)求，請(qǐng)求通過(guò)調(diào)用系統(tǒng)服務(wù)來(lái)處理。這種保護(hù)機(jī)制也會(huì)引入開(kāi)銷。進(jìn)程的三種類型作為計(jì)算代理，進(jìn)程有三種常見(jiàn)的類型：（ 1）中斷處理程序是非常短小的程序，只用于處理緊急請(qǐng)求，比如數(shù)據(jù)包的到來(lái)。中斷處理程序只使用少量的狀態(tài)，典型地只使用幾個(gè)寄存器，因此開(kāi)銷最?。ㄉ舷挛淖钚。＃?2）

24、用戶進(jìn)程使用計(jì)算機(jī)的全部狀態(tài)，比如內(nèi)存和寄存器，因此，在用戶進(jìn)程之間切換的代價(jià)是很高的。 （上下文最大）（ 3）線程是輕量級(jí)的進(jìn)程，只需要較少的狀態(tài)。另外，由于同一個(gè)進(jìn)程內(nèi)的線程是共享內(nèi)存的（即相同的變量） ，因此，線程切換不需要重新映射。以上三種類型的進(jìn)程，其開(kāi)銷依次增大。舉例：接收端活鎖下面我們用一個(gè)例子說(shuō)明進(jìn)程優(yōu)先級(jí)不同產(chǎn)生的問(wèn)題。圖示為數(shù)據(jù)包在BSD UNIX中的處理過(guò)程。數(shù)據(jù)包的到來(lái)產(chǎn)生一個(gè)硬件中斷，CPU 響應(yīng)中斷，保存當(dāng)前正在運(yùn)行的進(jìn)程的狀態(tài)，例如一個(gè)java 程序，然后CPU 執(zhí)行中斷處理程序（為快速響應(yīng)繞過(guò)了調(diào)度器）。中斷處理程序?qū)?shù)據(jù)包描述符拷貝到一個(gè)內(nèi)核IP 隊(duì)列（數(shù)據(jù)包

25、已通過(guò)DMA傳輸?shù)絻?nèi)存），調(diào)用一個(gè)軟中斷（請(qǐng)求一個(gè)操作系統(tǒng)線程）后返回。中斷處理程序一般只做最少的、必需的事情。假定隨后沒(méi)有硬件中斷產(chǎn)生，則控制權(quán)會(huì)交給調(diào)度器。調(diào)度器一般會(huì)調(diào)度CPU 執(zhí)行軟中斷，因?yàn)檐浿袛嗟膬?yōu)先級(jí)高于用戶進(jìn)程。內(nèi)核線程對(duì)數(shù)據(jù)包進(jìn)行TCP 和 IP 處理，然后將數(shù)據(jù)包放入相應(yīng)的應(yīng)用隊(duì)列，稱socket隊(duì)列。 假定該應(yīng)用程序是一個(gè)瀏覽器，瀏覽器正在等待數(shù)據(jù)包的到來(lái)。軟中斷退出后， 控制權(quán)重新交給調(diào)度器。調(diào)度器可能決定運(yùn)行瀏覽器，而不是早先的java 程序。現(xiàn)在假設(shè)網(wǎng)絡(luò)負(fù)載很高，一系列的包連續(xù)到來(lái)，這時(shí)只有最高優(yōu)先級(jí)的中斷處理程序能夠運(yùn)行，很可能沒(méi)有多少時(shí)間留給軟中斷，當(dāng)然更沒(méi)有時(shí)

26、間留給瀏覽器程序。這樣，最終IP 包隊(duì)列或socket 隊(duì)列會(huì)填滿，導(dǎo)致這些數(shù)據(jù)包在消耗了資源之后被丟棄，我們稱這時(shí)計(jì)算機(jī)進(jìn)入接收端活鎖：即計(jì)算機(jī)將所有的時(shí)間都用來(lái)處理中斷、協(xié)議處理等較高優(yōu)先級(jí)的任務(wù)，卻因?yàn)闆](méi)有時(shí)間運(yùn)行較低優(yōu)先級(jí)的應(yīng)用程序，導(dǎo)致這些已被處理的數(shù)據(jù)包被丟棄。這個(gè)現(xiàn)象在高速網(wǎng)絡(luò)環(huán)境下很常見(jiàn)。（ 2）通過(guò)虛擬內(nèi)存實(shí)現(xiàn)無(wú)限存儲(chǔ)的抽象在虛擬內(nèi)存系統(tǒng)中， 程序員使用的內(nèi)存抽象是一個(gè)線性的存儲(chǔ)空間， 存儲(chǔ)空間的大小只受指令地址長(zhǎng)度的限制，而不受物理內(nèi)存大小的限制。任何一個(gè)對(duì)虛擬地址的訪問(wèn)必須映射到一個(gè)物理地址上。 現(xiàn)代計(jì)算機(jī)系統(tǒng)使用基于頁(yè)的映射方法。 .頁(yè)表映射可以避免分配很大的連續(xù)內(nèi)存空間， 請(qǐng)求調(diào)頁(yè)可以使程序員可以使用的虛擬內(nèi)存空間不受物理內(nèi)存大小的限制，只受磁盤大小以及指令地址長(zhǎng)度的限制。虛擬內(nèi)存抽象帶來(lái)的開(kāi)銷采用虛擬內(nèi)存后，到虛擬地址的訪問(wèn)可能涉及到兩次內(nèi)存訪問(wèn)：。為降低訪問(wèn)延遲， 現(xiàn)代處理器將最近使用過(guò)的虛擬地址到物理地址的映射緩存在處理器的一個(gè)片上cache（稱 TLB ）中，實(shí)際的地址轉(zhuǎn)換由稱為MMU 的硬件完成。TLB miss和調(diào)頁(yè)是最影響內(nèi)存訪問(wèn)速度的兩個(gè)因素。頁(yè)表映射也提供了進(jìn)程之間的一種保護(hù)機(jī)制。當(dāng)進(jìn)程