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