前言

??閱讀前請先閱讀內(nèi)存管理基礎(chǔ)摄咆。從本文開始就介紹不連續(xù)分配的幾種方式凡蚜，本文主要介紹基本分頁存儲管理。

1 將連續(xù)分配改造成非連續(xù)分配版本

??假設(shè)進(jìn)程A的大小為23MB，但是每個分區(qū)的大小只有10MB涩金，如果進(jìn)程只能占用一個分區(qū)谱醇，顯然是放不下的。
??解決思路：如果允許進(jìn)程占用多個分區(qū)步做，那么可以把進(jìn)程拆分成10MB + 10MB + 3MB三個部分副渴，再把這三個部分別放在三個分區(qū)中（這些分區(qū)不要求連續(xù)）.....

2 分頁存儲

??將內(nèi)存空間分為一個個大小相等的分區(qū)（如每個分區(qū)4KB，每個分區(qū)就是一個“頁框”凸克，或稱“內(nèi)存塊”议蟆、“物理塊”。每個頁框有一個編號萎战，即“頁框號”咐容，或“內(nèi)存塊號”、“物理塊號”蚂维，頁框號從0開始）戳粒。將用戶進(jìn)程的地址空間也分為與頁框大小相等的一個個區(qū)域，稱為頁面或頁虫啥。頁框的大小不能太大蔚约，否則可能會產(chǎn)生過大的內(nèi)存碎片。
??操作系統(tǒng)以頁框?yàn)閱挝粸楦鱾€進(jìn)程分配內(nèi)存空間涂籽。進(jìn)程的每個頁面分別放入一個頁框中苹祟，即進(jìn)程的頁面和內(nèi)存的頁框有一一對應(yīng)的關(guān)系。

3 地址轉(zhuǎn)換

??進(jìn)程分頁后，進(jìn)程的各個頁面可以放在不連續(xù)的頁框中砂轻，所以如何實(shí)現(xiàn)邏輯地址到物理的地址的轉(zhuǎn)換箕般？
??如下圖，將下面的進(jìn)程分頁舔清，假設(shè)每頁大小為50B，那么就分為4個頁面曲初。

(1) 要算出邏輯地址對應(yīng)的頁號故响。
(2) 要知道該頁號對應(yīng)的頁面在內(nèi)存中的起始地址。
(3) 計(jì)算出邏輯地址在頁面內(nèi)的偏移量颁独。
(4) 物理地址 = 頁面起始地址 + 偏移量彩届。

??手動計(jì)算方法：
??頁號 = 邏輯地址 / 頁面長度（取整數(shù)部分）。
??頁內(nèi)偏移量= 邏輯地址 % 頁面長度
??頁面在內(nèi)存中的起始位置：操作系統(tǒng)需要用某種數(shù)據(jù)結(jié)構(gòu)記錄進(jìn)程各個頁面的起始位置誓酒。
??對于計(jì)算機(jī)樟蠕，通常將頁面的大小劃分為2的整數(shù)次冪。假設(shè)用32個二進(jìn)制位表示邏輯地址靠柑，頁面大小為取2¹²B = 4096B = 4KB寨辩。

??如邏輯地址2，用二進(jìn)制表示00000000 00000000 00000000 00000010歼冰，前24位二進(jìn)制對應(yīng)的十進(jìn)制值就是邏輯地址2對應(yīng)的頁號靡狞，即0號頁，而后12二進(jìn)制位對應(yīng)的十進(jìn)制值就是偏移量隔嫡。如果0號頁在內(nèi)存中的起始地址為X甸怕，那么邏輯地址2對應(yīng)的物理地址就是 X + 2.
??同理，邏輯地址4097畔勤，用二進(jìn)制表示00000000 00000000 00010000 00000001蕾各，前24位二進(jìn)制對應(yīng)的十進(jìn)制值就是邏輯地址4097對應(yīng)的頁號，即1號頁庆揪，而后12二進(jìn)制位對應(yīng)的十進(jìn)制值就是偏移量式曲。如果0號頁在內(nèi)存中的起始地址為Y，那么邏輯地址4097對應(yīng)的物理地址就是 Y + 1.
??結(jié)論：如果每個頁面的大小為2^kB，用二進(jìn)制表示邏輯地址吝羞，則末尾的K位表示頁內(nèi)偏移量兰伤，其余部分就是頁號。
??因此钧排，如果讓每個頁面的大小為2的整數(shù)次冪敦腔，計(jì)算機(jī)就可以很方便的得出一個邏輯地址對應(yīng)的頁號和頁內(nèi)偏移量。
??如果一個頁面的大小為2KB恨溜，那分頁存儲管理的邏輯地址結(jié)構(gòu)為：

??地址結(jié)構(gòu)包括兩個部分：前一個部分表示頁號符衔，后一個部分表示頁內(nèi)偏移量W。

4 頁表

??在知道如何計(jì)算頁號和偏移量后糟袁，要計(jì)算實(shí)際的物理地址判族，還需要知道頁號在內(nèi)存中的起始地址，如何知道每個頁面在內(nèi)存中存放的位置——操作系統(tǒng)要為每個進(jìn)程建立一張頁表项戴。

(1) 一個進(jìn)程對應(yīng)一張頁表形帮。
(2) 進(jìn)程的每一頁對應(yīng)一個頁表項(xiàng)。
(3) 每個頁表項(xiàng)由頁號和塊號組成周叮。
(4) 頁表記錄進(jìn)程頁面和實(shí)際存放的內(nèi)存塊之間的對應(yīng)關(guān)系辩撑。
(5) 每個頁表項(xiàng)的長度都是相同的，頁號是隱含的（下小節(jié)）仿耽。

??按照之前的方法計(jì)算出邏輯地址所對應(yīng)的頁號N合冀，然后根據(jù)頁表區(qū)查詢實(shí)際的內(nèi)存塊號M，由于每個內(nèi)存塊號的大小都是相等的氓仲，所以實(shí)際地址 = M * 內(nèi)存塊大小 + 偏移量水慨。

5 頁號隱含

??在實(shí)際上，頁表中是沒有頁號的敬扛，那怎么找到實(shí)際對應(yīng)的內(nèi)存塊號呢晰洒？
??假設(shè)某系統(tǒng)物理內(nèi)存大小為4GB，頁面大小為4KB啥箭，則每個頁表項(xiàng)至少應(yīng)該占用多少字節(jié)谍珊？

4GB = 2³²B，4KB = 2¹²B急侥。
??因此4GB的內(nèi)存一共被分為2³²/2¹² = 2²⁰個內(nèi)存塊砌滞，所以頁表中塊號的值是0~2²⁰-1。那么如果用二進(jìn)制要表示最大的塊號2²⁰-1需要20個二進(jìn)制位坏怪，所以至少需要3個字節(jié)（24個二進(jìn)制位）贝润。

??各頁表項(xiàng)會按順序連續(xù)地存放在內(nèi)存中，如果該頁表在內(nèi)存中存放的地址為X铝宵，則M號頁對應(yīng)的頁表項(xiàng)存放的地址為：X + M * 3B
??因此打掘，頁表的頁號可以是隱含的华畏。只需要知道頁表存放的起始地址和頁表項(xiàng)長度，即可找到各個頁號對應(yīng)的頁表項(xiàng)存放的位置尊蚁，找到位置后就可以讀取該位置的值亡笑，即實(shí)際內(nèi)存塊號。
??舉個例子横朋，如果按照邏輯地址計(jì)算出了偏移量為20仑乌，頁號為1，頁表中的頁號是隱藏的琴锭，那么根據(jù)頁表在內(nèi)存中的起始地址20（假設(shè)的值）晰甚，以及頁表項(xiàng)長度3B，那么頁號為1所對應(yīng)的實(shí)際內(nèi)存塊號的值所在的地址就是：20 + 3 * 1 = 23的位置决帖，然后在該位置的值压汪，該值就是實(shí)際內(nèi)存塊號，如果是4的話古瓤，那么實(shí)際地址就是： 4 * 頁面大小（4096B） + 20 = 16404腺阳。

6 基本分頁小結(jié)

7 基本地址變換結(jié)構(gòu)

??基本地址變換結(jié)構(gòu)可以借助進(jìn)程的頁表將邏輯地址轉(zhuǎn)換為物理地址落君。
??通常在系統(tǒng)中設(shè)置一個頁表寄存器（PTR Page-Table Register），存放頁表在內(nèi)存中起始地址F和頁表長度M亭引。
??進(jìn)程在未執(zhí)行時绎速，頁表的起址和頁表長度放在進(jìn)程控制塊（PCB）中，當(dāng)進(jìn)程被調(diào)度時焙蚓，操作系統(tǒng)內(nèi)核會把它們放在頁表寄存器中纹冤。

??邏輯地址到物理地址變換的過程：

(1) 計(jì)算頁號P和頁內(nèi)偏移量W。
(2) 比較頁號P和頁表長度M购公，如果P>= M萌京，則會拋出越界異常。
(3) 頁表中頁號P對應(yīng)的頁表項(xiàng)地址 = 頁表始址 + 頁號 * 頁表項(xiàng)長度宏浩，取出該頁表項(xiàng)內(nèi)容b知残，即內(nèi)存塊號。
(4) 計(jì)算實(shí)際物理地址 = b * L + W 比庄。

??比較頁表長度求妹，頁表項(xiàng)長度和頁面大小三個概念：

??(1) 頁面大小指一個頁面占多大的內(nèi)存空間。
??(2) 頁表長度是指頁表最多能有多少個頁表項(xiàng)佳窑。
??(3) 頁表項(xiàng)長度指每個頁表項(xiàng)所占用的內(nèi)存大小制恍。

??在分頁存儲管理（頁式管理）系統(tǒng)中，只要確定了每個頁面的大小神凑，邏輯地址結(jié)構(gòu)就確定了净神。因此，頁式管理中地址是一維的。即只要給出一個邏輯地址强挫，系統(tǒng)就可以自動算出頁號岔霸、頁內(nèi)偏移量兩個部分，并不需要顯示告系統(tǒng)這個邏輯地址中俯渤，頁內(nèi)偏移量占多少位呆细。
??基本地址變換結(jié)構(gòu)需要訪問兩次內(nèi)存：第一次訪問內(nèi)存查找頁表；第二次訪問物理內(nèi)存對應(yīng)的內(nèi)存單元八匠。

8 具有快表的地址變換結(jié)構(gòu)

?? 8.1 局部性原理

??對于上圖絮爷，會很頻繁地訪問10號塊中的指令、23號塊梨树。
??時間局部性：如果執(zhí)行了程序中的某條指令坑夯，那么不久后這條指令很有可能再次執(zhí)行：如果某個數(shù)據(jù)被訪問過，不久之后該數(shù)據(jù)很有可能再次被訪問抡四。（因此程序中存在大量循環(huán)）柜蜈。
??空間局限性：一旦程序訪問了某個存儲單元，在不久之后指巡，其附近的存儲單元也很有可能被訪問淑履。（因?yàn)楹芏鄶?shù)據(jù)在內(nèi)存中都是連續(xù)存放的。如上面的數(shù)組藻雪，每次循環(huán)一次都會訪問鄰近的下一個元素地址）秘噪。
??在基本地址變換機(jī)構(gòu)中，每次訪問一個邏輯地址勉耀，都需要查詢內(nèi)幕才能中的頁表指煎。由于局部性原理，可能連續(xù)很多次查找到的都是一個頁表項(xiàng)便斥。既然如此至壤，就可以利用這個特性減少訪問頁表的次數(shù)——快表。

?? 8.2 快表

??快表枢纠，又稱聯(lián)想寄存器（TLB）崇渗，是一種訪問速度比內(nèi)存快很多的高速緩沖存儲器，用來存儲當(dāng)前訪問的若干頁表項(xiàng)京郑，以加速地址變換的過程宅广。與此對應(yīng)，內(nèi)存中的頁表常稱為慢表些举。
??快表的地址包換過程：
??(1) CPU給出邏輯地址跟狱，由某個硬件算得頁號、頁內(nèi)偏移量户魏，將頁號與快表中的所有頁號進(jìn)行比較驶臊。
??(2) 如果找到匹配的頁號挪挤，說明要訪問的頁表項(xiàng)在快表中有副本，則直接從中取出該頁對應(yīng)的內(nèi)存塊號关翎，再根據(jù)內(nèi)存塊號中與頁內(nèi)偏移量算地物理地址扛门。最后訪問該物理地址對應(yīng)的內(nèi)存單元。因此如果快表命中纵寝，則訪問某個邏輯地址只需一次訪問內(nèi)存即可论寨。
??(3) 如果沒有找到匹配的頁號，則就需要訪問頁表爽茴，需要兩次訪問內(nèi)存葬凳，在第一次訪問內(nèi)存查詢得到頁號后，需要將頁號添加到快表中室奏，以便后面再次被訪問火焰。如果快表已滿，則必須按照一定的算法對舊的頁表項(xiàng)進(jìn)行替換胧沫。
??由于查詢快表比查詢頁表的速度快很多昌简，因此只要快表命中，就可以節(jié)省很多時間绒怨。因?yàn)榫植啃栽斫。话銇碚f快表的命中率可以達(dá)到90%以上。

例如窖逗，某系統(tǒng)使用基本分頁存儲管理，并采用具有快表的地址變換機(jī)構(gòu)餐蔬，訪問一次快表耗時1us碎紊，訪問內(nèi)存耗時100us，若快表的命中率為90%樊诺，則訪問一個邏輯地址的平均耗時是多少仗考？
（1 + 100） * 0.9 + （1 + 100 +100） * 0.1 = 111us。
若沒有使用快表則訪問耗時：100 + 100 = 200us词爬。
可見引入快表機(jī)制秃嗜，訪問速度可以提高近一倍。

9 小結(jié)

??本文完