<P>　</P>
<P>Hash table可用于加速常用的數(shù)據(jù)結(jié)構(gòu)的訪問，在Linux里常用hash 
table來實(shí)現(xiàn)緩沖。緩沖是需要快速存取的信息，是全部可用信息的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)被放在緩沖區(qū)并保留在那里，因?yàn)楹诵慕?jīng)常訪問這些結(jié)構(gòu)。使用緩沖區(qū)也有副作用，因?yàn)槭褂闷饋肀群?jiǎn)單鏈表或者散列表更加復(fù)雜。如果數(shù)據(jù)結(jié)構(gòu)可以在緩沖區(qū)找到（這叫做緩沖命中），那么一切很完美。但是如果數(shù)據(jù)結(jié)構(gòu)不在緩沖區(qū)中，那么必須查找所用的相關(guān)的數(shù)據(jù)結(jié)構(gòu)，如果找到，那么就加到緩沖區(qū)中。增加新的數(shù)據(jù)結(jié)構(gòu)到緩沖區(qū)中可能需要廢棄一個(gè)舊的緩沖入口。Linux必須決定廢棄那一個(gè)數(shù)據(jù)結(jié)構(gòu)，風(fēng)險(xiǎn)在于廢棄的可能使Linux下一個(gè)要訪問的數(shù)據(jù)結(jié)構(gòu)。</P>
<P>　</P>
<P>2.3.3 Abstract Interfaces（抽象接口）</P>
<P>　</P>
<P>Linux核心經(jīng)常將它的接口抽象化。接口是以特定方式工作的一系列例程和數(shù)據(jù)結(jié)構(gòu)。比如：所有的網(wǎng)絡(luò)設(shè)備驅(qū)動(dòng)程序都必須提供特定的例程來處理特定的數(shù)據(jù)結(jié)構(gòu)。用抽象接口的方式可以用通用的代碼層來使用底層特殊代碼提供的服務(wù)（接口）。例如網(wǎng)絡(luò)層是通用的，而它由底層符合標(biāo)準(zhǔn)接口的同設(shè)備相關(guān)的代碼提供支持。</P>
<P>通常這些底層在啟動(dòng)時(shí)向高一層登記。這個(gè)登記過程常通過在鏈接表中增加一個(gè)數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。例如，每一個(gè)連結(jié)到核心的文件系統(tǒng)在核心啟動(dòng)時(shí)進(jìn)行登記（或者如果你使用模塊，在文件系統(tǒng)第一次使用時(shí)向核心登記）。你可以查看文件/proc/filesystems來檢查那些文件系統(tǒng)進(jìn)行了登記。登記所用的數(shù)據(jù)結(jié)構(gòu)通常包括指向函數(shù)的指針。這是執(zhí)行特定任務(wù)的軟件函數(shù)的地址。再一次用文件系統(tǒng)登記的例子，每一個(gè)文件系統(tǒng)登記時(shí)傳遞給Linux核心的數(shù)據(jù)結(jié)構(gòu)都包括一個(gè)和具體文件系統(tǒng)相關(guān)的例程地址，在安裝文件系統(tǒng)時(shí)必須調(diào)用。</P>
<P>　</P>
<P>　</P>
<P>Chapter 3 </P>
<P>Memory Management （內(nèi)存管理）</P>
<P>　</P>
<P>內(nèi)存管理子系統(tǒng)是操作系統(tǒng)的重要部分。從計(jì)算機(jī)發(fā)展早期開始，就存在對(duì)于大于系統(tǒng)中物理能力的內(nèi)存需要。為了克服這種限制，開發(fā)了許多種策略，其中最成功的就是虛擬內(nèi)存。虛擬內(nèi)存通過在競(jìng)爭(zhēng)進(jìn)程之間共享內(nèi)存的方式使系統(tǒng)顯得擁有比實(shí)際更多的內(nèi)存。</P>
<P>虛擬內(nèi)存不僅僅讓你的計(jì)算機(jī)內(nèi)存顯得更多，內(nèi)存管理子系統(tǒng)還提供：</P>
<P>　</P>
<P>Large Address Spaces（巨大的地址空間）操作系統(tǒng)使系統(tǒng)顯得擁有比實(shí)際更大量的內(nèi)存。虛擬內(nèi)存可以比系統(tǒng)中的物理內(nèi)存大許多倍。</P>
<P>Protection（保護(hù)）系統(tǒng)中的每一個(gè)進(jìn)程都有自己的虛擬地址空間。這些虛擬的地址空間是相互完全分離的，所以運(yùn)行一個(gè)應(yīng)用程序的進(jìn)程不會(huì)影響另外的進(jìn)程。另外，硬件的虛擬內(nèi)存機(jī)制允許對(duì)內(nèi)存區(qū)寫保護(hù)。這可以防止代碼和數(shù)據(jù)被惡意的程序覆蓋。</P>
<P>Memory Mapping（內(nèi)存映射）內(nèi)存映射用來將映像和數(shù)據(jù)映射到進(jìn)程的地址空間。用內(nèi)存映射，文件的內(nèi)容被直接連結(jié)到進(jìn)程的虛擬地址空間。</P>
<P>Fair Physics Memory Allocation（公平分配物理內(nèi)存）內(nèi)存管理子系統(tǒng)允許系統(tǒng)中每一個(gè)運(yùn)行中的進(jìn)程公平地共享系統(tǒng)的物理內(nèi)存</P>
<P>Shared Virtual 
Memory（共享虛擬內(nèi)存）雖然虛擬內(nèi)存允許進(jìn)程擁有分離（虛擬）的地址空間，有時(shí)你也需要進(jìn)程之間共享內(nèi)存。例如，系統(tǒng)中可能有多個(gè)進(jìn)程運(yùn)行命令解釋程序bash。雖然可以在每一個(gè)進(jìn)程的虛擬地址空間都擁有一份bash的拷貝，更好的是在物理內(nèi)存中只擁有一份拷貝，所有運(yùn)行bash的進(jìn)程共享代碼。動(dòng)態(tài)連接庫是多個(gè)進(jìn)程共享執(zhí)行代碼的另一個(gè)常見例子。共享內(nèi)存也可以用于進(jìn)程間通訊(IPC)機(jī)制，兩個(gè)或多個(gè)進(jìn)程可以通過共同擁有的內(nèi)存交換信息。Linux系統(tǒng)支持系統(tǒng)V的共享內(nèi)存IPC機(jī)制。</P>
<P>　</P>
<P>3.1 An Abstract Model of Virtual Memory（虛擬內(nèi)存的抽象模型）</P>
<P>　</P>
<P>在考慮Linux支持虛擬內(nèi)存的方法之前，最好先考慮一個(gè)抽象的模型，以免被太多的細(xì)節(jié)搞亂。</P>
<P>　</P>
<P>在進(jìn)程執(zhí)行程序的時(shí)候，它從內(nèi)存中讀取指令并進(jìn)行解碼。解碼指令也許需要讀取或者存儲(chǔ)內(nèi)存特定位置的內(nèi)容，然后進(jìn)程執(zhí)行指令并轉(zhuǎn)移到程序中的下一條指令。進(jìn)程不管是讀取指令還是存取數(shù)據(jù)都要訪問內(nèi)存。 
　</P>
<P>在一個(gè)虛擬內(nèi)存系統(tǒng)中，所有的地址都是虛擬地址而非物理地址。處理器通過操作系統(tǒng)保存的一組信息將虛擬地址轉(zhuǎn)換為物理地址。</P>
<P>　</P>
<P>為了讓這種轉(zhuǎn)換更簡(jiǎn)單，將虛擬內(nèi)存和物理內(nèi)存分為適當(dāng)大小的塊，叫做頁（page）。頁的大小一樣。（當(dāng)然可以不一樣，但是這樣一來系統(tǒng)管理起來比較困難）。Linux在Alpha 
AXP系統(tǒng)上使用8K字節(jié)的頁，而在Intel x86系統(tǒng)上使用4K字節(jié)的頁。每一頁都賦予一個(gè)唯一編號(hào)：page frame number(PFN 
頁編號(hào))。在這種分頁模型下，虛擬地址由兩部分組成：虛擬頁號(hào)和頁內(nèi)偏移量。假如頁大小是4K，則虛擬地址的位11到0包括頁內(nèi)偏移量，位12和以上的位是頁編號(hào)。每一次處理器遇到虛擬地址，它必須提取出偏移和虛擬頁編號(hào)。處理器必須將虛擬頁編號(hào)轉(zhuǎn)換到物理的頁，并訪問物理頁的正確偏移處。為此，處理器使用了頁表（page 
tables）。</P>
<P>圖3.1顯示了兩個(gè)進(jìn)程的虛擬地址空間，進(jìn)程X和進(jìn)程Y，每一個(gè)進(jìn)程擁有自己的頁表。這些頁表將每一個(gè)進(jìn)程的虛擬頁映射到內(nèi)存的物理頁上。圖中顯示進(jìn)程X的虛擬頁號(hào)0映射到物理頁號(hào)1，而進(jìn)程Y的虛擬頁編號(hào)1映射到物理頁號(hào)4。理論上頁表每一個(gè)條目包括以下信息：</P>
<P>　</P>
<P>有效標(biāo)志 表示頁表本條目是否有效</P>
<P>本頁表?xiàng)l目描述的物理頁編號(hào) 訪問控制信息 描述本頁如何使用：是否可以寫？是否包括執(zhí)行代碼？</P>
<P>　</P>
<P>頁表通過虛擬頁標(biāo)號(hào)作為偏移來訪問。虛擬頁編號(hào)5是表中的第6個(gè)元素（0是第一個(gè)元素）</P>
<P>要將虛擬地址轉(zhuǎn)換到物理地址，處理器首先找出虛擬地址的頁編號(hào)和頁內(nèi)偏移量。使用2的冪次的頁尺寸，可以用掩碼或移位簡(jiǎn)單地處理。再一次看圖3.1，假設(shè)頁大小是0x2000（十進(jìn)制8192），進(jìn)程Y的虛擬地址空間的地址是0x2194，處理器將會(huì)把地址轉(zhuǎn)換為虛擬頁編號(hào)1內(nèi)的偏移量0x194。</P>
<P>　</P>
<P></P>
<P>　</P>
<P>處理器使用虛擬頁編號(hào)作為索引在進(jìn)程的頁表中找到它的頁表的條目。如果該條目有效，處理器從該條目取出物理的頁編號(hào)。如果本條目無效，就是進(jìn)程訪問了它的虛擬內(nèi)存中不存在的區(qū)域。在這種情況下，處理器無法解釋地址，必須將控制權(quán)傳遞給操作系統(tǒng)來處理。</P>
<P>處理器具體如何通知操作系統(tǒng)進(jìn)程在訪問無法轉(zhuǎn)換的無效的虛擬地址，這個(gè)方式是和處理器相關(guān)的。處理器將這種信息（page 
fault）進(jìn)行傳遞，操作系統(tǒng)得到通知，虛擬地址出錯(cuò)，以及出錯(cuò)的原因。</P>
<P>　</P>
<P>假設(shè)這是一個(gè)有效的頁表?xiàng)l目，處理器取出物理頁號(hào)并乘以頁大小，得到了物理內(nèi)存中本頁的基礎(chǔ)地址。最后，處理器加上它需要的指令或數(shù)據(jù)的偏移量。</P>
<P>　</P>
<P>再用上述例子，進(jìn)程Y的虛擬頁編號(hào)1映射到了物理頁編號(hào)4（起始于0x8000 ， 4x 
0x2000），加上偏移0x194，得到了最終的物理地址0x8194。</P>
<P>　</P>
<P>通過這種方式將虛擬地址映射到物理地址，虛擬內(nèi)存可以用任意順序映射到系統(tǒng)的物理內(nèi)存中。例如，圖3.1 
中，虛擬內(nèi)存X的虛擬頁編號(hào)映射到了物理頁編號(hào)1而虛擬頁編號(hào)7雖然在虛擬內(nèi)存中比虛擬頁0要高，卻映射到了物理頁編號(hào)0。這也演示了虛擬內(nèi)存的一個(gè)有趣的副產(chǎn)品：虛擬內(nèi)存頁不必按指定順序映射到物理內(nèi)存中。</P>
<P>　</P>
<P>3.1.1 Demand Paging</P>
<P>　</P>
<P>因?yàn)槲锢韮?nèi)存比虛擬內(nèi)存少得多，操作系統(tǒng)必須避免無效率地使用物理內(nèi)存。節(jié)省物理內(nèi)存的一種方法是只加載執(zhí)行程序正在使用的虛擬頁。例如：一個(gè)數(shù)據(jù)庫程序可能正在數(shù)據(jù)庫上運(yùn)行一個(gè)查詢。在這種情況下，并非所有的數(shù)據(jù)必須放到內(nèi)存中，而只需要正被檢查的數(shù)據(jù)記錄。如果這是個(gè)查找型的查詢，那么加載程序中增加記錄的代碼就沒什么意義。這種進(jìn)行訪問時(shí)才加載虛擬頁的技術(shù)叫做demand 
paging。</P>
<P>　</P>
<P>當(dāng)一個(gè)進(jìn)程試圖訪問當(dāng)前不在內(nèi)存中的虛擬地址的時(shí)候處理器無法找到引用的虛擬頁對(duì)應(yīng)的頁表?xiàng)l目。例如：圖3.1中進(jìn)程X的頁表中沒有虛擬頁2 
的條目，所以如果進(jìn)程X試圖從虛擬頁2中的地址讀取時(shí)，處理器無法將地址轉(zhuǎn)換為物理地址。這時(shí)處理器通知操作系統(tǒng)發(fā)生page fault。</P>
<P>　</P>
<P>如果出錯(cuò)的虛擬地址無效意味著進(jìn)程試圖訪問它不應(yīng)該訪問的虛擬地址。也許是程序出錯(cuò)，例如向內(nèi)存中任意地址寫。這種情況下，操作系統(tǒng)會(huì)中斷它，從而保護(hù)系統(tǒng)中其他的進(jìn)程。</P>
<P>如果出錯(cuò)的虛擬地址有效但是它所在的頁當(dāng)前不在內(nèi)存中，操作系統(tǒng)必須從磁盤映像中將相應(yīng)的頁加載到內(nèi)存中。相對(duì)來講磁盤存取需要較長(zhǎng)時(shí)間，所以進(jìn)程必須等待直到該頁被取到內(nèi)存中。如果當(dāng)前有其他系統(tǒng)可以運(yùn)行，操作系統(tǒng)將選擇其中一個(gè)運(yùn)行。取到的頁被寫到一個(gè)空閑的頁面，并將一個(gè)有效的虛擬頁條目加到進(jìn)程的頁表中。然后這個(gè)進(jìn)程重新運(yùn)行發(fā)生內(nèi)存錯(cuò)誤的地方的機(jī)器指令。這一次虛擬內(nèi)存存取進(jìn)行時(shí)，處理器能夠?qū)⑻摂M地址轉(zhuǎn)換到物理地址，所以進(jìn)程得以繼續(xù)運(yùn)行。</P>
<P>　</P>
<P>Linux使用demand 
paging技術(shù)將可執(zhí)行映像加載到進(jìn)程的虛擬內(nèi)存中。當(dāng)一個(gè)命令執(zhí)行時(shí)，包含它的文件被打開，它的內(nèi)容被映射到進(jìn)程的虛擬內(nèi)存中。這個(gè)過程是通過修改描述進(jìn)程內(nèi)存映射的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，也叫做內(nèi)存映射（memory 
mapping）。但是，實(shí)際上只有映像的第一部分真正放在了物理內(nèi)存中。映像的其余部分仍舊在磁盤上。當(dāng)映像執(zhí)行時(shí)，它產(chǎn)生page 
fault，Linux使用進(jìn)程的內(nèi)存映像表來確定映像的那一部分需要加載到內(nèi)存中執(zhí)行。 　</P>
<P>3.1.2 Swapping（交換）</P>
<P>　</P>
<P>如果進(jìn)程需要將虛擬頁放到物理內(nèi)存中而此時(shí)已經(jīng)沒有空閑的物理頁，操作系統(tǒng)必須廢棄物理空間中的另一頁，為該頁讓出空間。</P>
<P>　</P>
<P>如果物理內(nèi)存中需要廢棄的頁來自磁盤上的映像或者數(shù)據(jù)文件，而且沒有被寫過所以不需要存儲(chǔ)，則該頁被廢棄。如果進(jìn)程又需要該頁，它可以從映像或數(shù)據(jù)文件中再次加載到內(nèi)存中。</P>
<P>但是，如果該頁已經(jīng)被改變，操作系統(tǒng)必須保留它的內(nèi)容以便以后進(jìn)行訪問。這種也叫做dirty 
page，當(dāng)它從物理內(nèi)存中廢棄時(shí)，被存到一種叫做交換文件的特殊文件中。因?yàn)樵L問交換文件的速度和訪問處理器以及物理內(nèi)存的速度相比很慢，操作系統(tǒng)必須判斷是將數(shù)據(jù)頁寫到磁盤上還是將它們保留在內(nèi)存中以便下次訪問。 
　</P>
<P>如果決定哪些頁需要廢棄或者交換的算法效率不高，則會(huì)發(fā)生顛簸（thrashing）。這時(shí)，頁不斷地被寫到磁盤上，又被讀回，操作系統(tǒng)過于繁忙而無法執(zhí)行實(shí)際的工作。例如在圖3.1中，如果物理頁號(hào)1經(jīng)常被訪問，那么就不要將它交換到硬盤上。進(jìn)程正在使用的也叫做工作集(working 
set)。有效的交換方案應(yīng)該保證所有進(jìn)程的工作集都在物理內(nèi)存中。</P>
<P>　</P>
<P>Linux使用LRU（Least Recently 
Used最近最少使用）的頁面技術(shù)來公平地選擇需要從系統(tǒng)中廢棄的頁面。這種方案將系統(tǒng)中的每一頁都賦予一個(gè)年齡，這個(gè)年齡在頁面存取時(shí)改變。頁面訪問越多，年紀(jì)越輕，越少訪問，年紀(jì)越老越陳舊。陳舊的頁面是交換的好候選。</P>
<P>　</P>
<P>3.1.3 Shared Vitual Memory（共享虛擬內(nèi)存）</P>
<P>　</P>
<P>虛擬內(nèi)存使多個(gè)進(jìn)程可以方便地共享內(nèi)存。所有的內(nèi)存訪問都是通過頁表，每一個(gè)進(jìn)程都有自己的頁表。對(duì)于兩個(gè)共享一個(gè)物理內(nèi)存頁的進(jìn)程，這個(gè)物理頁編號(hào)必須出現(xiàn)在兩個(gè)進(jìn)程的頁表中。</P>
<P>圖3.1顯示了兩個(gè)共享物理頁號(hào)4的進(jìn)程。對(duì)于進(jìn)程X虛擬頁號(hào)是4，而對(duì)于進(jìn)程Y虛擬頁號(hào)是6。這也表明了共享頁的一個(gè)有趣的地方：共享的物理頁不必存在共享它的進(jìn)程的虛擬內(nèi)存空間的同一個(gè)地方。</P>
<P>　</P>
<P>3.1.4 Physical and Vitual Addressing Modes（物理和虛擬尋址模式）</P>
<P>　</P>
<P>對(duì)于操作系統(tǒng)本身而言，運(yùn)行在虛擬內(nèi)存中沒有什么意義。如果操作系統(tǒng)必須維護(hù)自身的頁表，這將會(huì)是一場(chǎng)噩夢(mèng)。大多數(shù)多用途的處理器同時(shí)支持物理地址模式和虛擬地址模式。物理尋址模式不需要頁表，處理器在這種模式下不需要進(jìn)行任何地址轉(zhuǎn)換。Linux核心運(yùn)行在物理地址模式。</P>
<P>　</P>
<P>Alpha 
AXP處理器沒有特殊的物理尋址模式。它將內(nèi)存空間分為幾個(gè)區(qū)，將其中兩個(gè)指定為物理映射地址區(qū)。核心的地址空間叫做KSEG地址空間，包括從0xfffffc0000000000向上的所有地址。為了執(zhí)行連接在KSEG的代碼（核心代碼）或者訪問那里的數(shù)據(jù)，代碼必須在核心態(tài)執(zhí)行。Alpha 
上的Linux核心連接到從地址0xfffffc0000310000執(zhí)行。</P>