3.1 內(nèi)存管理概念

3.1.1 內(nèi)存管理的基本原理和要求

內(nèi)存可存放數(shù)據(jù)篡石。程序執(zhí)行前需要先放到內(nèi)存中才能被CPU處理，主要作用是緩和CPU與硬盤之間的速度矛盾

內(nèi)存管理的功能有

• 操作系統(tǒng)負(fù)責(zé)內(nèi)存空間的分配與回收
• 操作系統(tǒng)需要提供某種技術(shù)從邏輯上對內(nèi)存空間進(jìn)行擴(kuò)充
• 操作系統(tǒng)需要提供地址轉(zhuǎn)換功能西采，負(fù)責(zé)程序的邏輯地址與物理地址的轉(zhuǎn)換
• 操作系統(tǒng)需要提供內(nèi)存保護(hù)功能凰萨。保證各進(jìn)程在各自存儲空間內(nèi)運(yùn)行，互不干擾

為了使編程更方便，程序員寫程序時應(yīng)該只需要關(guān)注指令沟蔑、數(shù)據(jù)的邏輯地址湿诊。而邏輯地址到物理地址的轉(zhuǎn)換（這個過程稱為地址重定位）應(yīng)該由操作系統(tǒng)負(fù)責(zé)狱杰，這樣就保證了程序員寫程序時不需要關(guān)注物理內(nèi)存的實(shí)際情況瘦材。

3.1.1.1 內(nèi)存的裝入和連接

創(chuàng)建進(jìn)程首先要將程序和數(shù)據(jù)裝入內(nèi)存，將用戶源程序變?yōu)榭稍趦?nèi)存中執(zhí)行的程序仿畸，通常需要以下步驟

• 編譯：由編譯程序?qū)⒂脩粼创a編譯成若干個目標(biāo)模塊（編譯就是把高級語言翻譯為機(jī)器語言）
• 鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊食棕，以及所需庫函數(shù)鏈接在一起，形成一個完整的裝入模塊
• 裝入（裝載）：由裝入程序?qū)⒀b入模塊裝入內(nèi)存運(yùn)行

圖片.png

內(nèi)存的裝入模塊在裝入內(nèi)存時错沽，有以下三種方式

• 絕對裝入：在編譯時簿晓，如果知道程序?qū)⒎诺絻?nèi)存中的哪個位置，編譯程序?qū)a(chǎn)生絕對地址的目標(biāo)代碼千埃。裝入程序按照裝入模塊中的地址憔儿，將程序和數(shù)據(jù)裝入內(nèi)存。絕對裝入只適用于單道程序環(huán)境放可。程序中使用的絕對地址谒臼，可在編譯或匯編時給出，也可由程序員直接賦予耀里。通常情況下都是編譯或匯編時再轉(zhuǎn)換為絕對地址蜈缤。
• 靜態(tài)重定位：又稱可重定位裝入。編譯冯挎、鏈接后的裝入模塊的地址都是從0開始的底哥，指令中使用的地址、數(shù)據(jù)存放的地址都是相對于起始地址而言的邏輯地址房官≈夯眨可根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入到內(nèi)存的適當(dāng)位置翰守。裝入時對地址進(jìn)行“重定位”附较，將邏輯地址變換為物理地址（地址變換是在裝入時一次完成的）。靜態(tài)重定位的特點(diǎn)是在一個作業(yè)裝入內(nèi)存時潦俺，必須分配其要求的全部內(nèi)存空間拒课，如果沒有足夠的內(nèi)存，就不能裝入該作業(yè)事示。作業(yè)一旦進(jìn)入內(nèi)存后早像，在運(yùn)行期間就不能再移動，也不能再申請內(nèi)存空間肖爵。
• 動態(tài)重定位：又稱動態(tài)運(yùn)行時裝入卢鹦。編譯、鏈接后的裝入模塊的地址都是從0開始的。裝入程序把裝入模塊裝入內(nèi)存后冀自，并不會立即把邏輯地址轉(zhuǎn)換為物理地址揉稚，而是把地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行。因此裝入內(nèi)存后所有的地址依然是邏輯地址熬粗。這種方式需要一個重定位寄存器的支持搀玖。采用動態(tài)重定位時允許程序在內(nèi)存中發(fā)生移動。

鏈接的三種方式：

• 靜態(tài)鏈接：在程序運(yùn)行之前驻呐，先將各目標(biāo)模塊及它們所需的庫函數(shù)連接成一個完整的可執(zhí)行文件（裝入模塊）灌诅，之后不再拆開。
• 裝入時動態(tài)鏈接：將各目標(biāo)模塊裝入內(nèi)存時含末，邊裝入邊鏈接的鏈接方式猜拾。
• 運(yùn)行時動態(tài)鏈接：在程序執(zhí)行中需要該目標(biāo)模塊時，才對它進(jìn)行鏈接佣盒。其優(yōu)點(diǎn)是便于修改和更新挎袜，便于實(shí)現(xiàn)對目標(biāo)模塊的共享。

3.1.1.2 內(nèi)存保護(hù)

在內(nèi)存分配前肥惭，需要保護(hù)操作系統(tǒng)不受用戶的影響盯仪，同時保護(hù)用戶進(jìn)程不受其他用戶進(jìn)程的影響。內(nèi)存保護(hù)可采取兩種方法：

• 在CPU中設(shè)置一對上务豺、下限寄存器磨总，存放進(jìn)程的上、下限地址笼沥。進(jìn)程的指令要訪問某個地址時蚪燕，CPU檢查是否越界。
• 采用重定位寄存器（又稱基址寄存器）和界地址寄存器（又稱限長寄存器）進(jìn)行越界檢查奔浅。重定位寄存器中存放的是進(jìn)程的起始物理地址馆纳。界地址寄存器中存放的是進(jìn)程的最大邏輯地址。

圖片.png

3.1.2 連續(xù)分配管理方式

連續(xù)分配：指為用戶進(jìn)程分配的必須是一個連續(xù)的內(nèi)存空間汹桦。

3.1.2.1 單一連續(xù)分配

在單一連續(xù)分配方式中鲁驶，內(nèi)存被分為系統(tǒng)區(qū)和用戶區(qū)。系統(tǒng)區(qū)通常位于內(nèi)存的低地址部分舞骆，用于存放操作系統(tǒng)相關(guān)數(shù)據(jù)钥弯；用戶區(qū)用于存放用戶進(jìn)程相關(guān)數(shù)據(jù)脆霎。內(nèi)存中只能有一道用戶程序睛蛛，用戶程序獨(dú)占整個用戶區(qū)空間戏仓。

優(yōu)點(diǎn)：實(shí)現(xiàn)簡單旭从；無外部碎片遇绞；可以采用覆蓋技術(shù)擴(kuò)充內(nèi)存；不一定需要采取內(nèi)存保護(hù)^[1]褐健。

缺點(diǎn)：只能用于單用戶澜汤、單任務(wù)的操作系統(tǒng)中俊抵；有內(nèi)部碎片徽诲；存儲器利用率極低。

3.1.2.2 固定分區(qū)分配

為了能在內(nèi)存中裝入多道程序偷溺，且這些程序之間又不會相互干擾挫掏，于是將整個用戶空間劃分為若干個固定大小的分區(qū)尉共，在每個分區(qū)中只裝入一道作業(yè)袄友，這樣就形成了最早的杠河、最簡單的一種可運(yùn)行多道程序的內(nèi)存管理方式。

分區(qū)大小相等：缺乏靈活性唾戚，但是很適合用于用一臺計算機(jī)控制多個相同對象的場合^[2]

分區(qū)大小不等：增加了靈活性叹坦，可以滿足不同大小的進(jìn)程需求测蹲。根據(jù)常在系統(tǒng)中運(yùn)行的作業(yè)大小情況進(jìn)行劃分^[3]

圖片.png

操作系統(tǒng)需要建立一個數(shù)據(jù)結(jié)構(gòu)——分區(qū)說明表扣甲，來實(shí)現(xiàn)各個分區(qū)的分配與回收琉挖。每個表項對應(yīng)一個分區(qū)示辈，通常按分區(qū)大小排列。每個表項包括對應(yīng)分區(qū)的大小纱耻、起始地址膝迎、狀態(tài)（是否已分配）限次。

優(yōu)點(diǎn)：實(shí)現(xiàn)簡單卖漫，無外部碎片羊始。

缺點(diǎn)：a.當(dāng)用戶程序太大時突委，可能所有的分區(qū)都不能滿足需求匀油，此時不得不采用覆蓋技術(shù)來解決敌蚜，但這又會降低性能弛车；b.會產(chǎn)生內(nèi)部碎片纷跛，內(nèi)存利用率低忽舟。

圖片.png

3.1.2.3 動態(tài)分區(qū)分配

動態(tài)分區(qū)分配又稱為可變分區(qū)分配叮阅。這種分配方式不會預(yù)先劃分內(nèi)存分區(qū)浩姥，而是在進(jìn)程裝入內(nèi)存時勒叠，根據(jù)進(jìn)程的大小動態(tài)地建立分區(qū)眯分，并使分區(qū)的大小正好適合進(jìn)程的需要。因此系統(tǒng)分區(qū)的大小和數(shù)目是可變的飘诗。^[4]

把一個新作業(yè)裝入內(nèi)存時昆稿，須按照一定的動態(tài)分區(qū)分配算法溉潭，從空閑分區(qū)表（或空閑分區(qū)鏈）中選出一個分區(qū)分配給該作業(yè)喳瓣。由于分配算法算法對系統(tǒng)性能有很大的影響夫椭，因此人們對它進(jìn)行了廣泛的研究蹭秋。

動態(tài)分區(qū)分配沒有內(nèi)部碎片仁讨，但是有外部碎片洞豁。如果內(nèi)存中空閑空間的總和本來可以滿足某進(jìn)程的要求刁卜，但由于進(jìn)程需要的是一整塊連續(xù)的內(nèi)存空間蛔趴，因此這些“碎片”不能滿足進(jìn)程的需求孝情◇锏矗可以通過緊湊（拼湊，Compaction）技術(shù)來解決外部碎片婉弹。

內(nèi)部碎片终吼，分配給某進(jìn)程的內(nèi)存區(qū)域中，如果有些部分沒有用上商佛。
外部碎片喉钢，是指內(nèi)存中的某些空閑分區(qū)由于太小而難以利用。

動態(tài)分區(qū)分配算法：在動態(tài)分區(qū)分配方式中良姆，當(dāng)很多個空閑分區(qū)都能滿足需求時税课，應(yīng)該選擇哪個分區(qū)進(jìn)行分配

• 首次適應(yīng)算法

算法思想：每次都從低地址開始查找陆馁，找到第一個能滿足大小的空閑分區(qū)叮贩。

如何實(shí)現(xiàn)：空閑分區(qū)以地址遞增的次序排列。每次分配內(nèi)存時順序查找空閑分區(qū)鏈（或空閑分區(qū)表），找到大小能滿足要求的第一個空閑分區(qū)互婿。

• 最佳適應(yīng)算法

算法思想：由于動態(tài)分區(qū)分配是一種連續(xù)分配方式刮萌，為各進(jìn)程分配的空間必須是連續(xù)的一整片區(qū)域。因此為了保證當(dāng)“大進(jìn)程”到來時能有連續(xù)的大片空間猜绣，可以盡可能多地留下大片的空閑區(qū)，即掰伸，優(yōu)先使用更小的空閑區(qū)多搀。

如何實(shí)現(xiàn)：空閑分區(qū)按容量遞增次序鏈接廊谓。每次分配內(nèi)存時順序查找空閑分區(qū)鏈（或空閑分區(qū)表）呛哟，找到大小能滿足要求的第一個空閑分區(qū)。

缺點(diǎn)：每次都選最小的分區(qū)進(jìn)行分配，會留下越來越多的黄鳍、很小的增炭、難以利用的內(nèi)存塊。因此這種方法會產(chǎn)生很多的外部碎片蔫敲。

• 最壞適應(yīng)算法，又稱最大適應(yīng)算法（Largest Fit）

算法思想：為了解決最佳適應(yīng)算法的問題——即留下太多難以利用的小碎片，可以在每次分配時優(yōu)先使用最大的連續(xù)空閑區(qū)践图，這樣分配后剩余的空閑區(qū)就不會太小德崭，更方便使用兽狭。

如何實(shí)現(xiàn)：空閑分區(qū)按容量遞減次序鏈接销钝。每次分配內(nèi)存時順序查找空閑分區(qū)鏈（或空閑分區(qū)表）婉商，找到大小能滿足要求的第一個空閑分區(qū)。

缺點(diǎn)：每次都選最大的分區(qū)進(jìn)行分配箫攀，雖然可以讓分配后留下的空閑區(qū)更大梢睛，更可用藏畅，但是這種方式會導(dǎo)致較大的連續(xù)空閑區(qū)被迅速用完航瞭。如果之后有“大進(jìn)程”到達(dá)滨彻，就沒有內(nèi)存分區(qū)可用了辜羊。

• 鄰近適應(yīng)算法

算法思想：首次適應(yīng)算法每次都從鏈頭開始查找的昔驱。這可能會導(dǎo)致低地址部分出現(xiàn)很多小的空閑分區(qū)，而每次分配查找時朴艰，都要經(jīng)過這些分區(qū)毁嗦，因此也增加了查找的開銷袭祟。如果每次都從上次查找結(jié)束的位置開始檢索胆绊，就能解決上述問題种冬。

如何實(shí)現(xiàn)：空閑分區(qū)以地址遞增的順序排列（可排成一個循環(huán)鏈表）。每次分配內(nèi)存時從上次查找結(jié)束的位置開始查找空閑分區(qū)鏈（或空閑分區(qū)表）跟匆，找到大小能滿足要求的第一個空閑分區(qū)讽营。

首次適應(yīng)算法每次都要從頭查找，每次都需要檢索低地址的小分區(qū)模捂。但是這種規(guī)則也決定了當(dāng)?shù)偷刂凡糠钟懈〉姆謪^(qū)可以滿足需求時，會更有可能用到低地址部分的小分區(qū)并淋，也會更有可能把高地址部分的大分區(qū)保留下來（最佳適應(yīng)算法的優(yōu)點(diǎn)）

鄰近適應(yīng)算法的規(guī)則可能會導(dǎo)致無論低地址寓搬、高地址部分的空閑分區(qū)都有相同的概率被使用，也就導(dǎo)致了高地址部分的大分區(qū)更可能被使用县耽，劃分為小分區(qū)句喷，最后導(dǎo)致無大分區(qū)可用（最大適應(yīng)算法的缺點(diǎn)）綜合來看，四種算法中兔毙，首次適應(yīng)算法的效果反而更好

3.1.3 非連續(xù)分配管理方式

非連續(xù)分配：為用戶進(jìn)程分配的可以是一些分散的內(nèi)存空間猪钮。

3.1.3.1 基本分頁存儲管理方式

3.1.3.1.1 分頁存儲的幾個基本概念

將內(nèi)存空間分為一個個大小相等的分區(qū)（比如：每個分區(qū)4KB），每個分區(qū)就是一個“頁框”（頁框=頁幀=內(nèi)存塊=物理塊=物理頁面）胆建。每個頁框有一個編號烤低，即“頁框號”（頁框號=頁幀號=內(nèi)存塊號=物理塊號=物理頁號），頁框號從0開始眼坏。將進(jìn)程的邏輯地址空間也分為與頁框大小相等的一個個部分拂玻，每個部分稱為一個“頁”或“頁面”。每個頁面也有一個編號宰译，即“頁號”檐蚜，頁號也是從0開始。^[5]

操作系統(tǒng)以頁框?yàn)閱挝粸楦鱾€進(jìn)程分配內(nèi)存空間沿侈。進(jìn)程的每個頁面分別放入一個頁框中闯第。也就是說，進(jìn)程的頁面與內(nèi)存的頁框有一一對應(yīng)的關(guān)系缀拭。各個頁面不必連續(xù)存放咳短，可以放到不相鄰的各個頁框中。（注：進(jìn)程的最后一個頁面可能沒有一個頁框那么大蛛淋。也就是說咙好，分頁存儲有可能產(chǎn)生內(nèi)部碎片，因此頁框不能太大褐荷，否則可能產(chǎn)生過大的內(nèi)部碎片造成浪費(fèi)）

為了能知道進(jìn)程的每個頁面在內(nèi)存中存放的位置勾效，操作系統(tǒng)要為每個進(jìn)程建立一張頁表。頁表通常存在PCB（進(jìn)程控制塊）中

1. 一個進(jìn)程對應(yīng)一張頁表
2. 進(jìn)程的每個頁面對應(yīng)一個頁表項
3. 每個頁表項由“頁號”和“塊號”組成
4. 頁表記錄進(jìn)程頁面和實(shí)際存放的內(nèi)存塊之間的映射關(guān)系
5. 每個頁表項的長度是相同的

圖片.png

Eg：假設(shè)某系統(tǒng)物理內(nèi)存大小為4GB叛甫，頁面大小為4KB层宫，則
每個頁表項至少應(yīng)該為多少字節(jié)？
內(nèi)存塊大小=頁面大小=4KB= 2¹² B
4GB的內(nèi)存總共會被分為2³² / 2¹² = 220個內(nèi)存塊
內(nèi)存塊號的范圍應(yīng)該是0 ~ 2²⁰ -1
內(nèi)存塊號至少要用20 bit來表示
至少要用3B來表示塊號（3*8=24bit）

頁表項連續(xù)存放其监，因此頁號可以是隱含的萌腿，不占存儲空間（類比數(shù)組）

J號內(nèi)存塊的起始地址= J * 內(nèi)存塊大小

i號頁表項的存放地址= X + 3*I

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

特點(diǎn)：雖然進(jìn)程的各個頁面是離散存放的，但是頁面內(nèi)部是連續(xù)存放的

圖片.png

通常會在系統(tǒng)中設(shè)置一個頁表寄存器（PTR）抖苦，存放頁表在內(nèi)存中的起始地址F和頁表長度M毁菱。進(jìn)程未執(zhí)行時米死，頁表的始址和頁表長度放在進(jìn)程控制塊（PCB）中，當(dāng)進(jìn)程被調(diào)度時鼎俘，操作系統(tǒng)內(nèi)核會把它們放到頁表寄存器中哲身。

如果要訪問邏輯地址A，則

1. 確定邏輯地址A對應(yīng)的“頁號”P,頁號=邏輯地址/頁面長度（取除法的整數(shù)部分）贸伐，即

2. 找到P號頁面在內(nèi)存中的起始地址（需要查頁表）
3. 確定邏輯地址A的“頁內(nèi)偏移量”W,頁內(nèi)偏移量=邏輯地址%頁面長度（取除法的余數(shù)部分）,即

邏輯地址A對應(yīng)的物理地址= P號頁面在內(nèi)存中的起始地址+頁內(nèi)偏移量W

若頁面大小L為1KB，頁號2對應(yīng)的物理塊b=8怔揩，計算邏輯地址A=2500的物理地址E

P=2500/1K=2
W=2500%1K=452
E=8×1024+452=8644

在計算機(jī)內(nèi)部捉邢，地址是用二進(jìn)制表示的，如果頁面大小剛好是2的整數(shù)冪商膊，則計算機(jī)硬件可以很快速的把邏輯地址拆分成（頁號伏伐，頁內(nèi)偏移量）

假設(shè)某計算機(jī)用32個二進(jìn)制位表示邏輯地址，頁面大小為4KB = 2¹²B = 4096B
0號頁的邏輯地址范圍應(yīng)該是0~4095晕拆，用二進(jìn)制表示應(yīng)該是：
00000000000000000000000000000000 ~ 00000000000000000000111111111111
1號頁的邏輯地址范圍應(yīng)該是4096~8191藐翎，用二進(jìn)制表示應(yīng)該是：
00000000000000000001000000000000 ~ 00000000000000000001111111111111
2號頁的邏輯地址范圍應(yīng)該是8192~12287，用二進(jìn)制表示應(yīng)該是：
00000000000000000010000000000000 ~ 00000000000000000010111111111111

Eg：邏輯地址2实幕，用二進(jìn)制表示應(yīng)該是00000000000000000000000000000010
頁號= 2/4096 = 0 = 00000000000000000000吝镣，頁內(nèi)偏移量= 2%4096 = 2 = 000000000010
Eg：邏輯地址4097，用二進(jìn)制表示應(yīng)該是00000000000000000001000000000001
頁號= 4097/4096 = 1 = 00000000000000000001昆庇，頁內(nèi)偏移量= 4097%4096 = 1 = 000000000001

如果每個頁面大小為2^KB末贾，用二進(jìn)制數(shù)表示邏輯地址，則末尾K位即為頁內(nèi)偏移量整吆，其余部分就是頁號

假設(shè)物理地址也用32個二進(jìn)制位表示拱撵，則由于內(nèi)存塊的大小=頁面大小，因此：
0號內(nèi)存塊的起始物理地址是00000000000000000000000000000000
1號內(nèi)存塊的起始物理地址是00000000000000000001000000000000
2號內(nèi)存塊的起始物理地址是00000000000000000010000000000000
3號內(nèi)存塊的起始物理地址是00000000000000000011000000000000

根據(jù)頁號可以查詢頁表表蝙，而頁表中記錄的只是內(nèi)存塊號番川，而不是內(nèi)存塊的起始地址！

假設(shè)通過查詢頁表得知1號頁面存放的內(nèi)存塊號是9（1001）嗤攻，則
9號內(nèi)存塊的起始地址= 9*4096 = 00000000000000001001000000000000
則邏輯地址4097對應(yīng)的物理地址=頁面在內(nèi)存中存放的起始地址+頁內(nèi)偏移量=（00000000000000001001000000000001）

如果頁面大小剛好是2的整數(shù)冪泳赋，則只需把頁表中記錄的物理塊號拼接上頁內(nèi)偏移量就能得到對應(yīng)的物理地址

如果有K位表示“頁內(nèi)偏移量”，則說明該系統(tǒng)中一個頁面的大小是2^K個內(nèi)存單元
如果有M位表示“頁號”欲诺，則說明在該系統(tǒng)中抄谐，一個進(jìn)程最多允許有2^M個頁面

理論上，頁表項長度為3B即可表示內(nèi)存塊號的范圍扰法，但是蛹含，為了方便頁表的查詢，常常會讓一個頁表項占更多的字節(jié)塞颁，使得每個頁面恰好可以裝得下整數(shù)個頁表項浦箱。

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

快表吸耿，又稱聯(lián)想寄存器（TLB，translation lookaside buffer ）酷窥，是一種訪問速度比內(nèi)存快很多的高速緩存（TLB不是內(nèi)存Ｑ拾病），用來存放最近訪問的頁表項的副本蓬推，可以加速地址變換的速度妆棒。與此對應(yīng)，內(nèi)存中的頁表常稱為慢表沸伏。

圖片.png

引入快表后糕珊，地址的變換過程如下，

1. CPU給出邏輯地址毅糟，由某個硬件算得頁號红选、頁內(nèi)偏移量，將頁號與快表中的所有頁號進(jìn)行比較喇肋。
2. 如果找到匹配的頁號蝶防，說明要訪問的頁表項在快表中有副本，則直接從中取出該頁對應(yīng)的內(nèi)存塊號，再將內(nèi)存塊號與頁內(nèi)偏移量拼接形成物理地址贺喝，最后菱鸥，訪問該物理地址對應(yīng)的內(nèi)存單元。因此鹊漠，若快表命中躯概，則訪問某個邏輯地址僅需一次訪存即可。
3. 如果沒有找到匹配的頁號塔鳍，則需要訪問內(nèi)存中的頁表，找到對應(yīng)頁表項掌唾，得到頁面存放的內(nèi)存塊號郑兴，再將內(nèi)存塊號與頁內(nèi)偏移量拼接形成物理地址叽粹，最后锤灿，訪問該物理地址對應(yīng)的內(nèi)存單元。因此状囱，若快表未命中，則訪問某個邏輯地址需要兩次訪存（注意：在找到頁表項后，應(yīng)同時將其存入快表升敲，以便后面可能的再次訪問。但若快表已滿设江，則必須按照一定的算法對舊的頁表項進(jìn)行替換）

由于查詢快表的速度比查詢頁表的速度快很多，因此只要快表命中歼捏，就可以節(jié)省很多時間。因?yàn)榫植啃栽恚话銇碚f快表的命中率可以達(dá)到90%以上。

時間局部性：如果執(zhí)行了程序中的某條指令悯蝉，那么不久后這條指令很有可能再次執(zhí)行；如果某個數(shù)據(jù)被訪問過，不久之后該數(shù)據(jù)很可能再次被訪問讨彼。（因?yàn)槌绦蛑写嬖诖罅康难h(huán)）

空間局部性：一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也很有可能被訪問重荠。（因?yàn)楹芏鄶?shù)據(jù)在內(nèi)存中都是連續(xù)存放的）

例：某系統(tǒng)使用基本分頁存儲管理，并采用了具有快表的地址變換機(jī)構(gòu)诈乒。訪問一次快表耗時1us，訪問一次內(nèi)存耗時100us。若快表的命中率為90%导饲，那么訪問一個邏輯地址的平均耗時是多少浓体？
(1+100) * 0.9 + (1+100+100) * 0.1 = 111 us
有的系統(tǒng)支持快表和慢表同時查找，如果是這樣生闲，平均耗時應(yīng)該是(1+100) * 0.9 + (100+100) * 0.1 =110.9 us
若未采用快表機(jī)制扯躺，則訪問一個邏輯地址需要100+100 = 200us
顯然倍啥，引入快表機(jī)制后，訪問一個邏輯地址的速度快多了伍派。

3.1.3.1.4 兩級頁表

單極頁表存在以下問題

• 頁表必須連續(xù)存放，因此當(dāng)頁表很大時倍踪，需要占用很多個連續(xù)的頁框椒惨。
• 沒有必要讓整個頁表常駐內(nèi)存领斥，因?yàn)檫M(jìn)程在一段時間內(nèi)可能只需要訪問某幾個特定的頁面。

為了解決以上問題，把頁表再分頁并離散存儲，然后再建立一張頁表記錄頁表各個部分的存放位置碎节，稱為頁目錄表，或稱外層頁表，或稱頂層頁表

圖片.png

若分為兩級頁表后，頁表依然很長总滩，則可以采用更多級頁表，一般來說各級頁表的大小不能超過一個頁面

例：某系統(tǒng)按字節(jié)編址，采用40位邏輯地址，頁面大小為4KB，頁表項大小為4B录煤，假設(shè)采用純頁式存儲泪漂，則要采用（）級頁表夹囚，頁內(nèi)偏移量為（）位假哎？

頁面大小= 4KB =2¹²B劣砍，按字節(jié)編址香嗓，因此頁內(nèi)偏移量為12位
頁號= 40 - 12 = 28位
頁面大小= 2¹²B，頁表項大小= 4B ，則每個頁面可存放2¹² / 4 = 2¹⁰ 個頁表項
因此各級頁表最多包含2¹⁰ 個頁表項，需要10 位二進(jìn)制位才能映射到2¹⁰ 個頁表項闲礼，因此每一級的頁
表對應(yīng)頁號應(yīng)為10位嫁蛇。總共28位的頁號至少要分為三級

兩級頁表的訪存次數(shù)分析（假設(shè)沒有快表機(jī)構(gòu)）

1. 第一次訪存：訪問內(nèi)存中的頁目錄表
2. 第二次訪存：訪問內(nèi)存中的二級頁表
3. 第三次訪存：訪問目標(biāo)內(nèi)存單元

3.1.3.2 基本分段存儲管理方式

基本分段存儲管理方式與“分頁”最大的區(qū)別就是離散分配時所分配地址空間的基本單位不同

3.1.3.2.1 分段

進(jìn)程的地址空間：按照程序自身的邏輯關(guān)系劃分為若干個段，每個段都有一個段名（在低級語言中，程序員使用段名來編程），每段從0開始編址。分段系統(tǒng)的邏輯地址結(jié)構(gòu)由段號（段名）和段內(nèi)地址（段內(nèi)偏移量）所組成政冻。

圖片.png

在上述例子中询筏，若系統(tǒng)是按字節(jié)尋址的，則
段號占16位，因此在該系統(tǒng)中，每個進(jìn)程最多有2¹⁶ = 64K個段
段內(nèi)地址占16位，因此每個段的最大長度是2¹⁶ = 64KB。

內(nèi)存分配規(guī)則：以段為單位進(jìn)行分配，每個段在內(nèi)存中占據(jù)連續(xù)空間，但各段之間可以不相鄰。

由于是按邏輯功能模塊劃分茧妒，用戶編程更方便，程序的可讀性更高

段號的位數(shù)決定了每個進(jìn)程最多可以分幾個段
段內(nèi)地址位數(shù)決定了每個段的最大長度是多少

3.1.3.2.2 段表

程序分多個段除破，各段離散地裝入內(nèi)存丹莲，為了保證程序能正常運(yùn)行，就必須能從物理內(nèi)存中找到各個邏輯段的存放位置。為此，需為每個進(jìn)程建立一張段映射表后德，簡稱“段表”赫蛇。每個段對應(yīng)一個段表項，其中記錄了該段在內(nèi)存中的起始位置（又稱“基址”）和段的長度。各個段表項的長度是相同的

例如：某系統(tǒng)按字節(jié)尋址管行，采用分段存儲管理，邏輯地址結(jié)構(gòu)為（段號16位,段內(nèi)地址16位）邪媳，因此用16位即可表示最大段長捐顷。物理內(nèi)存大小為4GB（可用32位表示整個物理內(nèi)存地址空間）荡陷。因此迅涮，可以讓每個段表項占16+32 = 48位废赞，即6B。由于段表項長度相同叮姑，因此段號可以是隱含的唉地，不占存儲空間。若段表存放的起始地址為M戏溺，則K號段對應(yīng)的段表項存放的地址為M + K*6

圖片.png

3.1.3.2.3 地址變換

圖片.png

1. 根據(jù)邏輯地址得到段號渣蜗、段內(nèi)地址
2. 判斷段號是否越界。若S≥M旷祸，則產(chǎn)生越界中斷耕拷，否則繼續(xù)執(zhí)行
3. 查詢段表，找到對應(yīng)的段表項托享，段表項的存放地址為F+S*段表項長度骚烧，檢查段內(nèi)地址是否超過段長。若W≥C闰围，則產(chǎn)生越界中斷赃绊，否則繼續(xù)執(zhí)行
4. 計算得到物理地址，訪問目標(biāo)內(nèi)存單元

3.1.3.3 分段羡榴、分頁管理的對比

頁是信息的物理單位碧查。分頁的主要目的是為了實(shí)現(xiàn)離散分配，提高內(nèi)存利用率校仑。分頁僅僅是系統(tǒng)管理上的需要忠售，完全是系統(tǒng)行為，對用戶是不可見的迄沫；段是信息的邏輯單位稻扬。分段的主要目的是更好地滿足用戶需求。一個段通常包含著一組屬于一個邏輯模塊的信息羊瘩。分段對用戶是可見的泰佳，用戶編程時需要顯式地給出段名。

頁的大小固定且由系統(tǒng)決定尘吗。段的長度卻不固定逝她，決定于用戶編寫的程序。

分頁的用戶進(jìn)程地址空間是一維的睬捶，程序員只需給出一個記憶符即可表示一個地址黔宛；分段的用戶進(jìn)程地址空間是二維的，程序員在標(biāo)識一個地址時侧戴，既要給出段名宁昭，也要給出段內(nèi)地址。

分段比分頁更容易實(shí)現(xiàn)信息的共享和保護(hù)酗宋。不能被修改的代碼稱為純代碼或可重入代碼（不屬于臨界資源）积仗，這樣的代碼是可以共享的⊥擅ǎ可修改的代碼是不能共享的

分頁（單級頁表）：第一次訪存—查內(nèi)存中的頁表寂曹，第二次訪存—訪問目標(biāo)內(nèi)存單元』赜遥總共兩次訪存隆圆；分段：第一次訪存—查內(nèi)存中的段表，第二次訪存—訪問目標(biāo)內(nèi)存單元翔烁，總共兩次訪存渺氧。與分頁系統(tǒng)類似，分段系統(tǒng)中也可以引入快表機(jī)構(gòu)蹬屹，將近期訪問過的段表項放到快表中侣背，這樣可以少一次訪問，加快地址變換速度慨默。

3.1.3.4 段頁式管理方式

段頁式系統(tǒng)的邏輯地址結(jié)構(gòu)由段號虾攻、頁號铡买、頁內(nèi)地址（頁內(nèi)偏移量）組成

圖片.png

段號的位數(shù)決定了每個進(jìn)程最多可以分幾個段
頁號位數(shù)決定了每個段最大有多少頁
頁內(nèi)偏移量決定了頁面大小、內(nèi)存塊大小是多少

在上述例子中台谢，若系統(tǒng)是按字節(jié)尋址的寻狂，則
段號占16位，因此在該系統(tǒng)中朋沮，每個進(jìn)程最多有2¹⁶ = 64K個段
頁號占4位蛇券，因此每個段最多有2⁴ = 16頁
頁內(nèi)偏移量占12位，因此每個頁面\每個內(nèi)存塊大小為2¹² = 4096 = 4KB

每個段對應(yīng)一個段表項樊拓，每個段表項由段號纠亚、頁表長度、頁表存放塊號（頁表起始地址）組成筋夏。每個段表項長度相等蒂胞，段號是隱含的。

每個頁面對應(yīng)一個頁表項条篷，每個頁表項由頁號骗随、頁面存放的內(nèi)存塊號組成蛤织。每個頁表項長度相等，頁號是隱含的鸿染。

圖片.png

實(shí)現(xiàn)地址變換的過程：

1. 根據(jù)邏輯地址得到段號指蚜、頁號、頁內(nèi)偏移量
2. 判斷段號是否越界涨椒。若S≥M摊鸡，則產(chǎn)生越界中斷，否則繼續(xù)執(zhí)行
3. 查詢段表蚕冬，找到對應(yīng)的段表項免猾，段表項的存放地址為F+S*段表項長度
4. 檢查頁號是否越界，若頁號≥頁表長度囤热，則發(fā)生越界中斷猎提，否則繼續(xù)執(zhí)行
5. 根據(jù)頁表存放塊號、頁號查詢頁表赢乓，找到對應(yīng)頁表項
6. 根據(jù)內(nèi)存塊號忧侧、頁內(nèi)偏移量得到最終的物理地址，訪問目標(biāo)內(nèi)存單元

1. eg：早期的PC操作系統(tǒng)MS-DOS ?

2. 鋼鐵廠有n個相同的煉鋼爐牌芋，就可把內(nèi)存分為n個大小相等的區(qū)域存放n個煉鋼爐控制程序 ?

3. 劃分多個小分區(qū)蚓炬、適量中等分區(qū)、少量大分區(qū) ?

4. 假設(shè)某計算機(jī)內(nèi)存大小為64MB躺屁，系統(tǒng)區(qū)8MB肯夏，用戶區(qū)共56 MB… ?

5. 初學(xué)易混——頁、頁面vs頁框犀暑、頁幀枪芒、物理頁 ?