分段

基本方法

分段就是基于用戶視圖的內(nèi)存管理方案。邏輯地址空間是由一組段構(gòu)成的，每個(gè)段都有名稱和長(zhǎng)度。地址指定了段名稱和段內(nèi)偏移。因此用戶通過(guò)兩個(gè)量來(lái)指定地址：段名稱和段偏移。
為了簡(jiǎn)單，進(jìn)行對(duì)段的編號(hào)，是通過(guò)段號(hào)而不是段名稱來(lái)引用的，所以邏輯地址由有序?qū)M成：<段號(hào)，偏移>。

分段硬件

用戶是通過(guò)二位地址來(lái)引用程序內(nèi)的對(duì)象的，但是實(shí)際物理內(nèi)存仍然是一維的字節(jié)序列。所以我們需要定義一個(gè)實(shí)現(xiàn)方式，用來(lái)映射用戶定義的二維地址到一維的物理地址。這個(gè)地址是通過(guò)段表來(lái)實(shí)現(xiàn)的。段表的每個(gè)條目都有段基地址和段界限。段基地址包含該段在內(nèi)存中的開始物理地址，段界限指定該段的長(zhǎng)度。

段表的使用如上圖所示，每個(gè)邏輯地址由兩部分組成：段號(hào)s和段偏移d。段號(hào)用作段表的索引，邏輯地址的偏移d應(yīng)位于0和段界限之間。如果不是這樣，那么會(huì)陷入操作系統(tǒng)中(邏輯地址試圖訪問(wèn)段的外面)；如果d合法，那么就與基地址相加而得到所需字節(jié)的物理內(nèi)存地址。因此，段表實(shí)際上是基址寄存器值和界限寄存器值的對(duì)的數(shù)組。

分頁(yè)

分段允許進(jìn)程德爾物理地址空間是非連續(xù)的。分頁(yè)是提供這種優(yōu)勢(shì)的另一種內(nèi)存管理方案，使用分頁(yè)可以避免外部碎片和緊縮。

基本方法

實(shí)現(xiàn)分頁(yè)的基本方法涉及將物理內(nèi)存分為固定大小的塊，稱為幀或頁(yè)幀；而將邏輯內(nèi)存也分為同樣大小的塊，稱為頁(yè)或頁(yè)面。當(dāng)執(zhí)行一個(gè)進(jìn)程時(shí)，它的頁(yè)從文件系統(tǒng)或備份存儲(chǔ)等源處，加載到內(nèi)存的可用幀。備份存儲(chǔ)劃分為固定大小的塊，它與單個(gè)內(nèi)存幀或與多個(gè)內(nèi)存幀(簇)的大小一樣。
分頁(yè)的硬件如下圖所示，由CPU生成的每個(gè)地址分為兩部分：頁(yè)碼§和頁(yè)偏移(d)。頁(yè)碼作為頁(yè)表的索引。頁(yè)表包含每頁(yè)所在的物理內(nèi)存的基地址。這個(gè)基地址和頁(yè)偏移的組合就是物理內(nèi)存的內(nèi)存地址，可發(fā)送到物理單元。

頁(yè)大小是由硬件決定的。頁(yè)的大小為2的冪，如果邏輯地址空間為2m2^m2m，且頁(yè)大小為2n2^n2n字節(jié)，那么邏輯地址的高m-n位表示頁(yè)碼，而低n位表示頁(yè)偏移。

其中p為頁(yè)表的索引，d為頁(yè)的偏移。

采用分頁(yè)方案不會(huì)產(chǎn)生外部碎片：每個(gè)空閑幀都可以分配給需要他的進(jìn)程，但是，分頁(yè)有內(nèi)部碎片。分頁(yè)是以幀為單位進(jìn)行的，如果進(jìn)程所要求的內(nèi)存并不是頁(yè)的整數(shù)倍，那么最后一個(gè)幀就用不完。如果進(jìn)程大小與頁(yè)大小無(wú)關(guān)，那么每個(gè)進(jìn)程的內(nèi)部碎片的均值為半頁(yè)。

硬件支持

頁(yè)表的硬件實(shí)現(xiàn)有多種方法，最簡(jiǎn)單的一種方法就是：將頁(yè)表作為一組專用的寄存器來(lái)實(shí)現(xiàn)。這些寄存器應(yīng)用告訴邏輯電路來(lái)構(gòu)造，以高效的進(jìn)行分頁(yè)地址的轉(zhuǎn)換。CPU分派器在加載其他寄存器的時(shí)候，也需要加載這些寄存器。注意，這種方法適用于頁(yè)表比較小的情況下。
大多數(shù)的現(xiàn)代計(jì)算機(jī)都允許頁(yè)表非常大，對(duì)于這種情況，需要將頁(yè)表放在內(nèi)存中，并將頁(yè)表基址寄存器指向頁(yè)表。改變頁(yè)表只需要改變這一寄存器就行了。注意，如果采用這種方法，訪問(wèn)一個(gè)字節(jié)需要兩次訪問(wèn)內(nèi)存(一次用于頁(yè)表?xiàng)l目，一次用于字節(jié))。
標(biāo)準(zhǔn)方法是：采用轉(zhuǎn)換表緩沖區(qū)(TLB)，TLB是關(guān)聯(lián)的高速內(nèi)存，TLB條目是由兩部分組成：鍵(標(biāo)簽)和值。當(dāng)關(guān)聯(lián)內(nèi)存根據(jù)給定值查找時(shí)，它會(huì)同時(shí)與所有的鍵進(jìn)行比較。如果找到條目，就得到相應(yīng)值的字段。
TLB和頁(yè)表一起使用的方法是：TLB只包含少數(shù)的頁(yè)表?xiàng)l目。當(dāng)CPU產(chǎn)生一個(gè)邏輯地址后，它的頁(yè)碼就發(fā)送到TLB。如果找到這個(gè)頁(yè)碼，它的幀碼就立即可用，可用基于訪問(wèn)內(nèi)存。如果頁(yè)碼不在TLB中，也就是TLB未命中。那么就需要訪問(wèn)頁(yè)表。有的TLB在每個(gè)TLB條目中還保存地址空間標(biāo)識(shí)符(ASID)，ASID唯一標(biāo)識(shí)每個(gè)進(jìn)程，并為進(jìn)程提供地址空間的保護(hù)。

保護(hù)

分頁(yè)情況下的內(nèi)存保護(hù)是通過(guò)與每個(gè)幀關(guān)聯(lián)的保護(hù)位來(lái)實(shí)現(xiàn)的。用一個(gè)位可以定義一個(gè)頁(yè)是可讀可寫的還是只可讀。每次內(nèi)存引用都要通過(guò)頁(yè)表，來(lái)查找正確的幀碼。在計(jì)算物理地址的同時(shí)，可以通過(guò)檢查保護(hù)位來(lái)驗(yàn)證與沒有對(duì)只讀頁(yè)進(jìn)行操作。
還有一個(gè)位通常與頁(yè)表中的每一條目相關(guān)聯(lián)：有效-無(wú)效位。當(dāng)該位為有效時(shí)，該值表示相關(guān)的頁(yè)在進(jìn)程的邏輯地址空間內(nèi)，因此是合法的頁(yè)。當(dāng)該位是無(wú)效的時(shí)候，該值表示先關(guān)的頁(yè)不在進(jìn)程的邏輯地址空間內(nèi)。通過(guò)使用有效-無(wú)效位，非法地址會(huì)被捕捉到。
還有一個(gè)問(wèn)題，一個(gè)進(jìn)程很少會(huì)使用的它的所有地址空間，如果為地址范圍內(nèi)的所有頁(yè)都在頁(yè)表中建立一個(gè)條目，這將是非常浪費(fèi)的。有的系統(tǒng)會(huì)提供硬件來(lái)解決這個(gè)問(wèn)題，如**頁(yè)表長(zhǎng)度寄存器(PTLR)**來(lái)表示頁(yè)表的大小，該寄存器的值可用于檢查每個(gè)邏輯地址以驗(yàn)證其是否位于進(jìn)程的有效范圍內(nèi)。

共享頁(yè)
分頁(yè)的優(yōu)點(diǎn)之一就是可以共享公共代碼。
注意：代碼必須是可重入代碼或純代碼才可以共享。可重入代碼是不能自我修改的代碼，他在執(zhí)行期間不會(huì)改變

頁(yè)表結(jié)構(gòu)

分層分頁(yè)

現(xiàn)代操作系統(tǒng)支持大邏輯地址空間，在這種情況下頁(yè)表本身可以非常的大。比如一個(gè)位邏輯地址空間的計(jì)算機(jī)操作系統(tǒng)。如果系統(tǒng)的頁(yè)大小為4KB(2122^{12}212)，那么頁(yè)表可以多達(dá)100萬(wàn)的條目，假設(shè)每個(gè)條目有4字節(jié)，那么每個(gè)進(jìn)程需要4MB物理地址空間來(lái)存儲(chǔ)頁(yè)表本身。
常用的解決方法就是分層分頁(yè)。比如兩層分頁(yè)算法，就是將頁(yè)表在分頁(yè)。

其中p1p_1p1?是用來(lái)訪問(wèn)外部頁(yè)表的索引，p2p_2p2?是內(nèi)部頁(yè)表的頁(yè)偏移，這種方案一般稱為向前映射頁(yè)表。
對(duì)于64位的架構(gòu)，分層分頁(yè)是不適用的，因?yàn)槊恳粚拥捻?yè)表分完之后還是太大了。

哈希頁(yè)表

處理大于32位地址空間的常用方法就是使用哈希頁(yè)表。采用虛擬頁(yè)碼作為哈希值。哈希頁(yè)表的每一個(gè)條目都包括一個(gè)鏈表，該鏈表的元素哈希到同一位置(該鏈表用來(lái)解決碰撞)。每個(gè)元素由三個(gè)字段組成：

虛擬頁(yè)碼

映射的幀碼

指向鏈表內(nèi)下一個(gè)元素的指針

該算法的工作：虛擬地址的虛擬頁(yè)碼哈希到哈希表。用虛擬頁(yè)碼與鏈表內(nèi)的第一個(gè)元素的第一個(gè)字段相匹配。如果匹配，那么相應(yīng)的幀碼就用來(lái)形成物理地址；如果不匹配，那么與鏈表內(nèi)的后續(xù)節(jié)點(diǎn)的第一個(gè)字段進(jìn)行比較，以查找匹配的頁(yè)碼。

基于哈希頁(yè)表的一個(gè)變體采用聚簇頁(yè)表，哈希表中的每個(gè)條目引用多個(gè)頁(yè)而不是單個(gè)頁(yè)，因此單個(gè)頁(yè)表?xiàng)l目可以映射到多個(gè)物理幀。聚簇頁(yè)表對(duì)于稀疏地址空間特別有用，這里的引用是不連續(xù)的并且散步在整個(gè)地址空間中。

倒置頁(yè)表

通常情況下每個(gè)進(jìn)程都有一個(gè)頁(yè)表，該進(jìn)程使用的每個(gè)頁(yè)都是該頁(yè)表的一項(xiàng)。但是這種方法的缺點(diǎn)就是會(huì)造成每個(gè)頁(yè)表可能包含數(shù)以百萬(wàn)記的條目，占用大量的內(nèi)存。
所以有了倒置頁(yè)表。對(duì)于每個(gè)真正的內(nèi)存頁(yè)或幀，倒置頁(yè)表才有一個(gè)條目。每個(gè)條目包含保存在真正內(nèi)存位置上的頁(yè)的虛擬地址以及擁有該頁(yè)進(jìn)程的信息。所以在一個(gè)系統(tǒng)中只有一個(gè)頁(yè)表，并且每物理內(nèi)存的頁(yè)只有一條相應(yīng)的條目。
由于一倒置頁(yè)表通常包含多個(gè)不同的映射物理內(nèi)存的地址空間，通常要求它的每個(gè)條目保存一個(gè)地址空間標(biāo)識(shí)符，用來(lái)確保具體進(jìn)程的每個(gè)邏輯頁(yè)可映射道德相應(yīng)的物理幀。

參考：《操作系統(tǒng)概念》（第九版）

轉(zhuǎn)載于:https://www.cnblogs.com/lishanlei/p/10707669.html

總結(jié)

以上是生活随笔為你收集整理的OS之内存管理 ---基本的内存管理策略（二）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。