<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Hash table</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>是一個(gè)指向數(shù)據(jù)結(jié)構(gòu)的指針的數(shù)組，它的索引來(lái)源于數(shù)據(jù)結(jié)構(gòu)中的信息。如果你用一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)描述一個(gè)村莊的人口，你可以用年齡作為索引。要找出一個(gè)指定的人的數(shù)據(jù)，你可以用他的年齡作為索引在人口散列表中查找，通過(guò)指針找到包括詳細(xì)信息的數(shù)據(jù)結(jié)構(gòu)。不幸的是，一個(gè)村莊中可能很多人年齡相同，所以散列表的指針指向另一個(gè)鏈表數(shù)據(jù)結(jié)構(gòu)，每一個(gè)元素描述同齡人。即使這樣，查找這些較小的鏈表仍然比查找所有的數(shù)據(jù)結(jié)構(gòu)要快。</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Hash table</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>可用于加速常用的數(shù)據(jù)結(jié)構(gòu)的訪(fǎng)問(wèn)，在</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>里常用</FONT><FONT SIZE=3>hash table</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>來(lái)實(shí)現(xiàn)緩沖。緩沖是需要快速存取的信息，是全部可用信息的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)被放在緩沖區(qū)并保留在那里，因?yàn)楹诵慕?jīng)常訪(fǎng)問(wèn)這些結(jié)構(gòu)。使用緩沖區(qū)也有副作用，因?yàn)槭褂闷饋?lái)比簡(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è)舊的緩沖入口。</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>必須決定廢棄那一個(gè)數(shù)據(jù)結(jié)構(gòu)，風(fēng)險(xiǎn)在于廢棄的可能使</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>下一個(gè)要訪(fǎng)問(wèn)的數(shù)據(jù)結(jié)構(gòu)。</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">2.3.3 Abstract Interfaces</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（抽象接口）</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>核心經(jīng)常將它的接口抽象化。接口是以特定方式工作的一系列例程和數(shù)據(jù)結(jié)構(gòu)。比如：所有的網(wǎng)絡(luò)設(shè)備驅(qū)動(dòng)程序都必須提供特定的例程來(lái)處理特定的數(shù)據(jù)結(jié)構(gòu)。用抽象接口的方式可以用通用的代碼層來(lái)使用底層特殊代碼提供的服務(wù)（接口）。例如網(wǎng)絡(luò)層是通用的，而它由底層符合標(biāo)準(zhǔn)接口的同設(shè)備相關(guān)的代碼提供支持。</P>
<P ALIGN="JUSTIFY">通常這些底層在啟動(dòng)時(shí)向高一層登記。這個(gè)登記過(guò)程常通過(guò)在鏈接表中增加一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。例如，每一個(gè)連結(jié)到核心的文件系統(tǒng)在核心啟動(dòng)時(shí)進(jìn)行登記（或者如果你使用模塊，在文件系統(tǒng)第一次使用時(shí)向核心登記）。你可以查看文件</FONT><FONT SIZE=3>/proc/filesystems</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>來(lái)檢查那些文件系統(tǒng)進(jìn)行了登記。登記所用的數(shù)據(jù)結(jié)構(gòu)通常包括指向函數(shù)的指針。這是執(zhí)行特定任務(wù)的軟件函數(shù)的地址。再一次用文件系統(tǒng)登記的例子，每一個(gè)文件系統(tǒng)登記時(shí)傳遞給</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>核心的數(shù)據(jù)結(jié)構(gòu)都包括一個(gè)和具體文件系統(tǒng)相關(guān)的例程地址，在安裝文件系統(tǒng)時(shí)必須調(diào)用。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Chapter 3 </P>
<P ALIGN="JUSTIFY">Memory Management </FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（內(nèi)存管理）</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">內(nèi)存管理子系統(tǒng)是操作系統(tǒng)的重要部分。從計(jì)算機(jī)發(fā)展早期開(kāi)始，就存在對(duì)于大于系統(tǒng)中物理能力的內(nèi)存需要。為了克服這種限制，開(kāi)發(fā)了許多種策略，其中最成功的就是虛擬內(nèi)存。虛擬內(nèi)存通過(guò)在競(jìng)爭(zhēng)進(jìn)程之間共享內(nèi)存的方式使系統(tǒng)顯得擁有比實(shí)際更多的內(nèi)存。</P>
<P ALIGN="JUSTIFY">虛擬內(nèi)存不僅僅讓你的計(jì)算機(jī)內(nèi)存顯得更多，內(nèi)存管理子系統(tǒng)還提供：</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Large Address Spaces</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（巨大的地址空間）操作系統(tǒng)使系統(tǒng)顯得擁有比實(shí)際更大量的內(nèi)存。虛擬內(nèi)存可以比系統(tǒng)中的物理內(nèi)存大許多倍。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Protection</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（保護(hù)）系統(tǒng)中的每一個(gè)進(jìn)程都有自己的虛擬地址空間。這些虛擬的地址空間是相互完全分離的，所以運(yùn)行一個(gè)應(yīng)用程序的進(jìn)程不會(huì)影響另外的進(jìn)程。另外，硬件的虛擬內(nèi)存機(jī)制允許對(duì)內(nèi)存區(qū)寫(xiě)保護(hù)。這可以防止代碼和數(shù)據(jù)被惡意的程序覆蓋。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Memory Mapping</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（內(nèi)存映射）內(nèi)存映射用來(lái)將映像和數(shù)據(jù)映射到進(jìn)程的地址空間。用內(nèi)存映射，文件的內(nèi)容被直接連結(jié)到進(jìn)程的虛擬地址空間。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Fair Physics Memory Allocation</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（公平分配物理內(nèi)存）內(nèi)存管理子系統(tǒng)允許系統(tǒng)中每一個(gè)運(yùn)行中的進(jìn)程公平地共享系統(tǒng)的物理內(nèi)存</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Shared Virtual Memory</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（共享虛擬內(nèi)存）雖然虛擬內(nèi)存允許進(jìn)程擁有分離（虛擬）的地址空間，有時(shí)你也需要進(jìn)程之間共享內(nèi)存。例如，系統(tǒng)中可能有多個(gè)進(jìn)程運(yùn)行命令解釋程序</FONT><FONT SIZE=3>bash</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>。雖然可以在每一個(gè)進(jìn)程的虛擬地址空間都擁有一份</FONT><FONT SIZE=3>bash</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>的拷貝，更好的是在物理內(nèi)存中只擁有一份拷貝，所有運(yùn)行</FONT><FONT SIZE=3>bash</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>的進(jìn)程共享代碼。動(dòng)態(tài)連接庫(kù)是多個(gè)進(jìn)程共享執(zhí)行代碼的另一個(gè)常見(jiàn)例子。共享內(nèi)存也可以用于進(jìn)程間通訊</FONT><FONT SIZE=3>(IPC)</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>機(jī)制，兩個(gè)或多個(gè)進(jìn)程可以通過(guò)共同擁有的內(nèi)存交換信息。</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>系統(tǒng)支持系統(tǒng)</FONT><FONT SIZE=3>V</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>的共享內(nèi)存</FONT><FONT SIZE=3>IPC</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>機(jī)制。</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">3.1 An Abstract Model of Virtual Memory</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（虛擬內(nèi)存的抽象模型）</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">在考慮</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>支持虛擬內(nèi)存的方法之前，最好先考慮一個(gè)抽象的模型，以免被太多的細(xì)節(jié)搞亂。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">在進(jìn)程執(zhí)行程序的時(shí)候，它從內(nèi)存中讀取指令并進(jìn)行解碼。解碼指令也許需要讀取或者存儲(chǔ)內(nèi)存特定位置的內(nèi)容，然后進(jìn)程執(zhí)行指令并轉(zhuǎn)移到程序中的下一條指令。進(jìn)程不管是讀取指令還是存取數(shù)據(jù)都要訪(fǎng)問(wèn)內(nèi)存。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">在一個(gè)虛擬內(nèi)存系統(tǒng)中，所有的地址都是虛擬地址而非物理地址。處理器通過(guò)操作系統(tǒng)保存的一組信息將虛擬地址轉(zhuǎn)換為物理地址。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">為了讓這種轉(zhuǎn)換更簡(jiǎn)單，將虛擬內(nèi)存和物理內(nèi)存分為適當(dāng)大小的塊，叫做頁(yè)（</FONT><FONT SIZE=3>page</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>）。頁(yè)的大小一樣。（當(dāng)然可以不一樣，但是這樣一來(lái)系統(tǒng)管理起來(lái)比較困難）。</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>在</FONT><FONT SIZE=3>Alpha AXP</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>系統(tǒng)上使用</FONT><FONT SIZE=3>8K</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>字節(jié)的頁(yè)，而在</FONT><FONT SIZE=3>Intel x86</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>系統(tǒng)上使用</FONT><FONT SIZE=3>4K</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>字節(jié)的頁(yè)。每一頁(yè)都賦予一個(gè)唯一編號(hào)：</FONT><FONT SIZE=3>page frame number(PFN </FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>頁(yè)編號(hào)</FONT><FONT SIZE=3>)</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>。在這種分頁(yè)模型下，虛擬地址由兩部分組成：虛擬頁(yè)號(hào)和頁(yè)內(nèi)偏移量。假如頁(yè)大小是</FONT><FONT SIZE=3>4K</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>，則虛擬地址的位</FONT><FONT SIZE=3>11</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>到</FONT><FONT SIZE=3>0</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>包括頁(yè)內(nèi)偏移量，位</FONT><FONT SIZE=3>12</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>和以上的位是頁(yè)編號(hào)。每一次處理器遇到虛擬地址，它必須提取出偏移和虛擬頁(yè)編號(hào)。處理器必須將虛擬頁(yè)編號(hào)轉(zhuǎn)換到物理的頁(yè)，并訪(fǎng)問(wèn)物理頁(yè)的正確偏移處。為此，處理器使用了頁(yè)表（</FONT><FONT SIZE=3>page tables</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>）。</P>
<P ALIGN="JUSTIFY">圖</FONT><FONT SIZE=3>3.1</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>顯示了兩個(gè)進(jìn)程的虛擬地址空間，進(jìn)程</FONT><FONT SIZE=3>X</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>和進(jìn)程</FONT><FONT SIZE=3>Y</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>，每一個(gè)進(jìn)程擁有自己的頁(yè)表。這些頁(yè)表將每一個(gè)進(jìn)程的虛擬頁(yè)映射到內(nèi)存的物理頁(yè)上。圖中顯示進(jìn)程</FONT><FONT SIZE=3>X</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>的虛擬頁(yè)號(hào)</FONT><FONT SIZE=3>0</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>映射到物理頁(yè)號(hào)</FONT><FONT SIZE=3>1</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>，而進(jìn)程</FONT><FONT SIZE=3>Y</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>的虛擬頁(yè)編號(hào)</FONT><FONT SIZE=3>1</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>映射到物理頁(yè)號(hào)</FONT><FONT SIZE=3>4</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>。理論上頁(yè)表每一個(gè)條目包括以下信息：</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">有效標(biāo)志</FONT><FONT SIZE=3>  </FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>表示頁(yè)表本條目是否有效</P>
<P ALIGN="JUSTIFY">本頁(yè)表?xiàng)l目描述的物理頁(yè)編號(hào)</P>
<P ALIGN="JUSTIFY">訪(fǎng)問(wèn)控制信息</FONT><FONT SIZE=3> </FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>描述本頁(yè)如何使用：是否可以寫(xiě)？是否包括執(zhí)行代碼？</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">頁(yè)表通過(guò)虛擬頁(yè)標(biāo)號(hào)作為偏移來(lái)訪(fǎng)問(wèn)。虛擬頁(yè)編號(hào)</FONT><FONT SIZE=3>5</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>是表中的第</FONT><FONT SIZE=3>6</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>個(gè)元素（</FONT><FONT SIZE=3>0</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>是第一個(gè)元素）</P>
<P ALIGN="JUSTIFY">要將虛擬地址轉(zhuǎn)換到物理地址，處理器首先找出虛擬地址的頁(yè)編號(hào)和頁(yè)內(nèi)偏移量。使用</FONT><FONT SIZE=3>2</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>的冪次的頁(yè)尺寸，可以用掩碼或移位簡(jiǎn)單地處理。再一次看圖</FONT><FONT SIZE=3>3.1</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>，假設(shè)頁(yè)大小是</FONT><FONT SIZE=3>0x2000</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（十進(jìn)制</FONT><FONT SIZE=3>8192</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>），進(jìn)程</FONT><FONT SIZE=3>Y</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>的虛擬地址空間的地址是</FONT><FONT SIZE=3>0x2194</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>，處理器將會(huì)把地址轉(zhuǎn)換為虛擬頁(yè)編號(hào)</FONT><FONT SIZE=3>1</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>內(nèi)的偏移量</FONT><FONT SIZE=3>0x194</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY"><IMG SRC="Image2.gif" WIDTH=553 HEIGHT=386></P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">處理器使用虛擬頁(yè)編號(hào)作為索引在進(jìn)程的頁(yè)表中找到它的頁(yè)表的條目。如果該條目有效，處理器從該條目取出物理的頁(yè)編號(hào)。如果本條目無(wú)效，就是進(jìn)程訪(fǎng)問(wèn)了它的虛擬內(nèi)存中不存在的區(qū)域。在這種情況下，處理器無(wú)法解釋地址，必須將控制權(quán)傳遞給操