基本分頁存儲管理

假設(shè)是按字節(jié)編址

連續(xù)分配方式的缺點

考慮支持多道程序的兩種連續(xù)分配方式

固定分區(qū)分配：缺乏靈活性甥桂，會產(chǎn)生大量的內(nèi)部碎片黄选，內(nèi)存的利用率很低
動態(tài)分區(qū)分配：會產(chǎn)生很多外部碎片，雖然可以用“緊湊技術(shù)”處理貌夕，但是處理時間代價很高

原因：連續(xù)分配要求進(jìn)程占有的必須是一塊連續(xù)的內(nèi)存區(qū)域
能否講一個進(jìn)程分散地裝入到許多不相鄰的分區(qū)民镜，便可充分利用內(nèi)存

基本分頁存儲管理的思想：把內(nèi)存分為一個個相等的小分區(qū)，再按照分區(qū)大小把進(jìn)程拆分成一個個小部分

分頁存儲管理的基本概念

頁框/頁幀：內(nèi)存空間分成的一個個大小相等的分區(qū)（比如4KB）
頁框號：頁框的編號们童，從0開始慧库，從低地址開始

頁/頁面：用戶進(jìn)程的地址空間分為和頁框大小相等的一個個區(qū)域
頁號：頁/頁面的編號亥鬓，從0開始

進(jìn)程的最后一個頁面可能沒有一個頁框那么大，頁框不能太大，否則可能產(chǎn)生過大的內(nèi)部碎片

操作系統(tǒng)以頁框為單位為各個進(jìn)程分配內(nèi)存空間熟呛。進(jìn)程的每個頁面分別放入一個頁框中尉姨，也就是說，進(jìn)程的頁面與內(nèi)存的頁框有一一對應(yīng)的關(guān)系
每個頁面不必連續(xù)存放九府，也不必按照先后順序覆致，可以放到不相鄰的各個頁框中

如何實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換

進(jìn)程在內(nèi)存中連續(xù)存放時煌妈，通過動態(tài)重定位實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換。在裝入模塊之后汰蜘，內(nèi)存中指令使用的依然是邏輯地址之宿，直到指令執(zhí)行的時候才會進(jìn)行地址轉(zhuǎn)換。系統(tǒng)會設(shè)置一個重定位寄存器色难，用來存放裝入模塊存放的起始位置，重定位寄存器中的值加上邏輯地址就是該邏輯地址實際對應(yīng)的物理地址

如果采用分頁技術(shù)

算出邏輯地址對應(yīng)的頁號柠掂。頁號 = 邏輯地址/頁面長度
該頁號對應(yīng)頁面在內(nèi)存中的起始地址依沮。操作系統(tǒng)會使用數(shù)據(jù)結(jié)構(gòu)記錄進(jìn)程某個頁面的起始地址
邏輯地址在頁面中的偏移量危喉。頁內(nèi)偏移量 = 邏輯地址%頁面長度
物理地址 = 頁面地址 + 頁內(nèi)偏移量

頁框大小為4KB，地址空間為4GB的系統(tǒng)
頁號為前20位皇拣，頁內(nèi)偏移量為后12位

頁表：為了能知道進(jìn)程的每個頁面在內(nèi)存中存放的位置薄嫡，操作系統(tǒng)要為每個進(jìn)程建立一張頁表

一個進(jìn)程對應(yīng)一張頁表
進(jìn)程的每一頁對應(yīng)一個頁表項
每個頁表項由頁號和頁框號組成
頁表記錄進(jìn)程頁面和實際存放的頁框之間的對應(yīng)關(guān)系

每個頁表項的長度是相同的毫深，頁號是隱含的
各頁表項會按順序連續(xù)存放在內(nèi)存中，如果該頁表在內(nèi)存中的起始地址是X钉寝，4GB/4KB系統(tǒng)的頁框有

2^{20}

個嵌纲，需要至少三個字節(jié)才夠腥沽，所以M號頁對應(yīng)的頁表項在X+3M的位置
如果進(jìn)程有n個頁面，進(jìn)程的頁表總共占3n個字節(jié)
因此只需要知道頁表存放起始地址和頁表項長度言沐，就可以找到各個頁號對應(yīng)的頁表項存放的位置

基本地址變換機構(gòu)

用于實現(xiàn)邏輯地址到物理地址轉(zhuǎn)換的一組硬件機構(gòu)

通常會在系統(tǒng)中設(shè)置一個頁表寄存器(PTR)险胰，存放頁表在內(nèi)存中的起始地址F和頁表長度M（M個頁表項）
進(jìn)程未執(zhí)行時矿筝，頁表的起始地址和頁表長度放在進(jìn)程控制塊(PCB)中，當(dāng)進(jìn)程被調(diào)度時榆综，操作系統(tǒng)內(nèi)核會把他們放到頁表寄存器中

根據(jù)邏輯地址A計算出頁號P和頁內(nèi)偏移量W（如果是十進(jìn)制給出，取商怯伊、取模）
根據(jù)頁表寄存器中的頁表長度檢查頁號是否合法耿芹，不合法（P≥M）拋出越界中斷
查詢頁表挪哄，找到頁號對應(yīng)的頁表項，確定頁面存放的頁框號（頁表起始地址+頁號*頁表項長度）
用頁框號和頁內(nèi)偏移量得到物理地址
訪問物理地址

例子：
若頁面大小L為1KB砸彬，頁號2對應(yīng)的內(nèi)存塊號b = 8斯入，將邏輯地址A = 2500轉(zhuǎn)換為物理地址E
等價描述：某系統(tǒng)按字節(jié)尋址，邏輯地址結(jié)構(gòu)中绽淘，頁內(nèi)偏移量占10位闹伪，頁號2對應(yīng)的內(nèi)存塊號b = 8偏瓤，將邏輯地址A = 2500轉(zhuǎn)換為物理地址E

頁號和頁內(nèi)偏移量：p = A/L = 2500/1024 = 2椰憋；w = A%L = 2500%1024 = 452
沒有越界，頁號2的頁框號為b = 8
物理地址E = b * L + w = 8 * 1024 + 452 = 8644

基本分頁存儲管理中地址是一維的橙依，即只要給出一個邏輯地址，系統(tǒng)就可以自動計算出頁號女责、偏移量创译，不需要顯式告訴系統(tǒng)偏移量是多少

理論上，頁表項長度為3即可表示內(nèi)存塊號的范圍刷喜，但是為了方便頁表查詢，會讓頁面恰好能裝得下整數(shù)個頁表項初茶，令每個頁表項占4字節(jié)
4KB頁面浊闪，可以放4096/3 =1365個頁表項，有4096%3 =1B的碎片桥氏，訪問1365及之后的頁表項時猛铅，還要考慮前面的頁框中的碎片，才能得到頁表項的物理地址堕伪，比較麻煩

進(jìn)程頁表通常存放在連續(xù)的頁框中栗菜，這樣就能用統(tǒng)一的計算方式得到想要得到的頁表項存儲的位置

地址變換過程中有兩次訪存操作：查詢頁表、訪問目標(biāo)內(nèi)存單元

具有快表的地址變換機構(gòu)

局部性原理

int i = 0;
int a[100];
while(i < 100){
    a[i] = i;
    i++;
}

如果這個程序?qū)⒊绦驅(qū)?yīng)的指令存放在10號內(nèi)存塊富俄，將程序中定義的變量存放在23號內(nèi)存塊而咆，當(dāng)這個程序執(zhí)行時，會很頻繁地反問10悠瞬、23號內(nèi)存塊

時間局部性：如果執(zhí)行了程序中的某條指令浅妆，那么不久后這條指令很有可能被再次執(zhí)行障癌；如果某個數(shù)據(jù)被訪問過，不久之后該數(shù)據(jù)很有可能再次被訪問（因為程序存在大量循環(huán)）
空間局部性：一旦程序訪問了某個存儲單元趴乡，在不久之后，其附近的存儲單元也很有可能被訪問（因為很多數(shù)據(jù)在內(nèi)存中連續(xù)存放）

基本地址變換機構(gòu)中晾捏，每次要訪問一個邏輯地址惦辛，都要查詢頁表，由于局部性原理胖齐，可能連續(xù)多次查詢同一個頁表項

快表：又稱聯(lián)想寄存器（TLB），是一種訪問速度比內(nèi)存塊很多的高速緩存补履，用來存放當(dāng)前訪問的若干頁表項箫锤，以加速地址變換的過程雨女。內(nèi)存中的頁表常稱為慢表

引入快表后地址的變換過程

CPU給出邏輯地址，由某個硬件計算出頁號馏臭、頁內(nèi)偏移量讼稚，將頁號與快表中的所有頁號比較
如果找到匹配的頁號锐想，說明要訪問的頁表項在快表中有副本，直接從快表中取出該頁對應(yīng)的內(nèi)存塊號，再將內(nèi)存塊號與頁內(nèi)偏移量拼接形成物理地址澜躺，最后，訪問該物理地址對應(yīng)的內(nèi)存單元耘戚。因此如果快表命中操漠，訪問某個邏輯地址僅需一次訪存
如果沒有找到匹配的頁號饿这，需要訪問內(nèi)存中的頁表长捧，找到對應(yīng)頁表項吻贿，得到頁面存放的內(nèi)存塊號，將內(nèi)存塊號和頁內(nèi)偏移量拼接形成物理地址肌割，訪問物理地址對應(yīng)的存儲單元；找到頁表項后把敞，同時也會將該頁表項存入快表奋早，若快表已滿，會按照一定的算法對舊的頁表項進(jìn)行替換伸蚯。因此如果快表未命中剂邮，訪問某個邏輯地址需要兩次訪存

一般來說挥萌，快表的命中率可以達(dá)到90%以上

例子：
某系統(tǒng)使用基本分頁存儲，采用具有快表的地址變換機構(gòu)引瀑，訪問一次快表耗時1us憨栽，訪問一次內(nèi)存耗時100us屑柔，若快表的命中率為90%，那么訪問一個邏輯地址的平均耗時是多少掸宛？

$(1+100) * 0.9 + (1 + 100 + 100) * 0.1 = 111(us)$

有的系統(tǒng)支持快慢表同時查詢

$(1+100) * 0.9 + (100+100) * 0.1 = 110.9(us)$

多級頁表

單級頁表存在的問題

頁表必須連續(xù)存放唧瘾，因此當(dāng)頁表很大時，需要占用很多個連續(xù)的頁框
沒有必要讓整個頁表常駐內(nèi)存领虹，因為進(jìn)程在一段時間內(nèi)可能只需要訪問某幾個特定的頁面（局部性原理）

對問題1

可將頁表進(jìn)行分組菌羽，使每個內(nèi)存塊剛好可以放入一個分組注祖。為離散分配的頁表再建立一張頁表，稱為頁目錄表肚菠，或外層頁表
各級頁表的大小不能超過一個頁面

例子：
某系統(tǒng)按字節(jié)編址蚊逢，采用40位邏輯地址箫章，頁面大小為4KB，需要采用幾級頁表终抽，頁內(nèi)偏移量是多少位桶至？

頁框總數(shù)為
$2^{40} / 2^{12} = 2^{28}$

镣屹，需要
$28$

位來索引頁框號，
$ceil(28/8) = 4B$

持舆，所以一個頁表項占
$4$

字節(jié)吏廉。一個頁框能夠存放
$4K/4 = 1K$

個頁表項惰许，所以各級頁表最多包含
$1K$

個頁表項汹买，需要
$10$

個二進(jìn)制位才能映射到
$1K$

個頁表項晦毙，因此每級頁表對應(yīng)頁號為
$10$

位，
$28$

位的頁號需要至少分為
$3$

級

針對兩級頁表

按照地址結(jié)構(gòu)將邏輯地址拆分為三部分：一級頁號孤荣、二級頁號盐股、頁內(nèi)偏移量
從PCB中讀出頁目錄表起始地址疯汁，再根據(jù)一級頁號查找頁目錄表卵酪，找到下一級頁表在內(nèi)存中的位置
根據(jù)二級頁號查表溃卡，找到最終想訪問的內(nèi)存塊號
結(jié)合頁內(nèi)偏移量得到物理地址

對問題2

可以在需要訪問頁面時，才把頁面調(diào)入內(nèi)存（虛擬存儲技術(shù)）漩仙，可以在頁表項中增加一個標(biāo)志位讯赏，用于表示該頁面是否已經(jīng)調(diào)入內(nèi)存
若想訪問的頁面不在內(nèi)存中漱挎，會產(chǎn)生缺頁中斷（內(nèi)中斷）雀哨，然后將目標(biāo)頁面從外存調(diào)入內(nèi)存
之后的文章會有展開

兩級頁表訪存次數(shù)分析：如果沒有TLB，第一次訪存是訪問內(nèi)存中的頁目錄表膊夹，第二次訪存是訪問內(nèi)存中的二級頁表捌浩，第三次訪存是訪問目標(biāo)內(nèi)存單元