第3章-內(nèi)存管理-內(nèi)存管理基礎(chǔ)

• 內(nèi)存的基礎(chǔ)知識(shí)

• 絕對(duì)裝入

• 靜態(tài)重定位

• 動(dòng)態(tài)重定位

• 裝入的三種方式

• 從寫程序到程序運(yùn)行

• 內(nèi)存管理的概念

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

• 覆蓋與交換

• 覆蓋技術(shù)

• 交換技術(shù)

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

• 單一連續(xù)分配

• 固定分區(qū)分配

• 動(dòng)態(tài)分區(qū)分配

• 動(dòng)態(tài)分區(qū)分配算法

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

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

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

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

• 基本分頁存儲(chǔ)管理的概念

• 分頁存儲(chǔ)

• 頁表

• 實(shí)現(xiàn)地址的轉(zhuǎn)換

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

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

• 快表TLB

• 局部性原理

• 兩級(jí)頁表

• 解決問題一

• 解決問題二

• 采用多級(jí)列表需要注意的問題

• 基本分段存儲(chǔ)管理方式

• 段表

• 分段、分頁管理的對(duì)比

• 段頁式管理方式

• 段頁式管理的邏輯地址結(jié)構(gòu)

第3章-內(nèi)存管理-內(nèi)存管理基礎(chǔ)

內(nèi)存的基礎(chǔ)知識(shí)

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

如何把指令中的邏輯地址轉(zhuǎn)換為物理地址？

1. 絕對(duì)裝入

2. 可重定位裝入（靜態(tài)重定位）

3. 動(dòng)態(tài)運(yùn)行時(shí)裝入（動(dòng)態(tài)重定位）

裝入的三種方式

絕對(duì)裝入

在編譯時(shí)，如果知道程序?qū)⒎诺絻?nèi)存中的哪個(gè)位置，編譯程序?qū)a(chǎn)生絕對(duì)地址的目標(biāo)代碼。裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。

絕對(duì)裝入只適用于單道程序環(huán)境，也就是早期的沒有操作系統(tǒng)的階段

靜態(tài)重定位

又稱可重定位裝入。編譯、鏈接后的裝入模塊的地址都是從0開始的，指令中使用的地址、數(shù)據(jù)存放的地址都是相對(duì)于起始地址而言的邏輯地址。可根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入到內(nèi)存的適當(dāng)位置。裝入時(shí)對(duì)地址進(jìn)行“重定位”，將邏輯地址變換為物理地址（地址變換是在裝入時(shí)一次完成的）

靜態(tài)重定位的特點(diǎn)是在一個(gè)作業(yè)裝入內(nèi)存時(shí)，必須分配其要求的全部?jī)?nèi)存空間，如果沒有足夠的內(nèi)存，就不能裝入該作業(yè)。作業(yè)一旦進(jìn)入內(nèi)存后，在運(yùn)行期間就不能再移動(dòng)，也不能再申請(qǐng)內(nèi)存空間

動(dòng)態(tài)重定位

又稱動(dòng)態(tài)運(yùn)行時(shí)裝入。編譯、鏈接后的裝入模塊的地址都是從0開始的。裝入程序把裝入模塊裝入內(nèi)存后，并不會(huì)立即把邏輯地址轉(zhuǎn)化為物理地址，而是把地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。因此裝入內(nèi)存后所有的地址依然是邏輯地址。這種方式需要一個(gè)重定位寄存器的支持

現(xiàn)代操作系統(tǒng)往往采用這種方式，優(yōu)點(diǎn)：

1. 采用動(dòng)態(tài)重定位時(shí)允許程序在內(nèi)存中發(fā)生移動(dòng)，并且可以將程序分配到不連續(xù)地存儲(chǔ)區(qū)中

2. 在程序運(yùn)行前只需裝入它的部分代碼即可投入運(yùn)行，然后在程序運(yùn)行期間，根據(jù)動(dòng)態(tài)申請(qǐng)分配內(nèi)存

3. 便于程序段的共享，可以向用戶提供一個(gè)比存儲(chǔ)空間大得多的地址空間

從寫程序到程序運(yùn)行

• 編譯：由編譯程序?qū)⒂脩粼创a編譯成若干個(gè)目標(biāo)模塊（編譯就是把高級(jí)語言翻譯為機(jī)器語言）

• 鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊，以及所需庫函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊

• 裝入（裝載）：由裝入程序?qū)⒀b入模塊裝入內(nèi)存運(yùn)行

其中，鏈接由三種方式

1. 靜態(tài)鏈接：在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫函數(shù)連接成一個(gè)完整的可執(zhí)行文件（裝入模塊），之后不再拆開

2. 裝入時(shí)動(dòng)態(tài)鏈接：將各目標(biāo)模塊裝入內(nèi)存時(shí)，邊裝入邊鏈接的鏈接方式

3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接：在程序執(zhí)行中需要該目標(biāo)模塊時(shí)，才對(duì)它進(jìn)行鏈接，用不到的模塊不需要裝入內(nèi)存。其優(yōu)點(diǎn)是便于修改和更新，便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。

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

操作系統(tǒng)需要對(duì)內(nèi)存管些什么呢？

1. 操作系統(tǒng)負(fù)責(zé)內(nèi)存空間的分配與回收

2. 操作系統(tǒng)需要提供某種技術(shù)從邏輯上對(duì)內(nèi)存空間進(jìn)行擴(kuò)充

3. 操作系統(tǒng)需要提供地址轉(zhuǎn)換功能，負(fù)責(zé)程序的邏輯地址與物理地址的轉(zhuǎn)換

4. 操作系統(tǒng)需要提供內(nèi)存保護(hù)功能，保證各進(jìn)程在各自存儲(chǔ)空間內(nèi)運(yùn)行，互不干擾

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

內(nèi)存保護(hù)可采取兩種方法

• 方法1：在CPU中設(shè)置一對(duì)上、下限寄存器，存放進(jìn)程的上、下限地址。進(jìn)程的指令要訪問某個(gè)地址時(shí)，CPU檢查是否越界

• 方法2：采用重定位寄存器（又稱基址寄存器）和界地址寄存器（又稱限長(zhǎng)寄存器）進(jìn)行越界檢查。重定位寄存器中存放的是進(jìn)程的起始物理地址。界地址寄存器中存放的是進(jìn)程的最大邏輯地址

覆蓋與交換

覆蓋技術(shù)

早期的計(jì)算機(jī)內(nèi)存很小，比如IBM推出的第一臺(tái)PC機(jī)最大只支持1MB大小的內(nèi)存，因此常常會(huì)出現(xiàn)內(nèi)存大小不夠的情況

后來人們引入了覆蓋技術(shù)，用來解決“程序大小超過物理內(nèi)存總和”的問題

覆蓋技術(shù)的思想：將程序分為多個(gè)段（多個(gè)模塊），常用的段常駐內(nèi)存，不常用的段在需要時(shí)調(diào)入內(nèi)存。內(nèi)存中分為一個(gè)“固定區(qū)”和若干個(gè)“覆蓋區(qū)”需要常駐內(nèi)存的段放在“固定區(qū)”中，調(diào)入后就不再調(diào)出（除非運(yùn)行結(jié)束）不常用的段放在“覆蓋區(qū)”，需要用到時(shí)調(diào)入內(nèi)存，用不到時(shí)調(diào)出內(nèi)存

必須由程序員聲明覆蓋結(jié)構(gòu)，操作系統(tǒng)完成自動(dòng)覆蓋。

缺點(diǎn)：對(duì)用戶不透明，增加了用戶編程負(fù)擔(dān)

覆蓋系統(tǒng)只用于早期的操作系統(tǒng)中，現(xiàn)在已退出歷史舞臺(tái)

交換技術(shù)

設(shè)計(jì)思想：內(nèi)存空間緊張時(shí)，系統(tǒng)將內(nèi)存中某些進(jìn)程暫時(shí)換出外存，把外存中某些已具備運(yùn)行條件的進(jìn)程換入內(nèi)存（進(jìn)程在內(nèi)存與磁盤間動(dòng)態(tài)調(diào)度）

進(jìn)程的PCB是需要常駐內(nèi)存的，無論是否調(diào)出

中級(jí)調(diào)度（內(nèi)存調(diào)度），就是決定將哪個(gè)處于掛起狀態(tài)的進(jìn)程重新調(diào)入內(nèi)存

1. 應(yīng)該在外存（磁盤）的什么位置保存被換出的進(jìn)程？具有對(duì)換功能的操作系統(tǒng)中，通常把磁盤空間分為文件區(qū)和對(duì)換區(qū)兩部分。文件區(qū)主要用于存放文件，主要追求存儲(chǔ)空間的利用率，因此對(duì)文件區(qū)空間的管理采用離散分配方式；對(duì)換區(qū)空間只占磁盤空間的小部分，被換出的進(jìn)程數(shù)據(jù)就存放在對(duì)換區(qū)。由于對(duì)換的速度直接影響到系統(tǒng)的整體速度，因此對(duì)換區(qū)空間的管理主要追求換入換出速度，因此通常對(duì)換區(qū)采用連續(xù)分配方式。總之，對(duì)換區(qū)的IO速度比文件區(qū)的更快

2. 什么時(shí)候應(yīng)該交換？交換通常在許多進(jìn)程運(yùn)行且內(nèi)存吃緊時(shí)進(jìn)程，而系統(tǒng)負(fù)荷降低就暫停。例如：在發(fā)現(xiàn)許多進(jìn)程運(yùn)行時(shí)經(jīng)常發(fā)生缺頁，就說明內(nèi)存緊張，此時(shí)可以換出一些進(jìn)程；如果缺頁率明顯下降，就可以暫停換出

3. 應(yīng)該換出哪些進(jìn)程？可以換出阻塞進(jìn)程、優(yōu)先級(jí)低的進(jìn)程。為了防止優(yōu)先級(jí)低的進(jìn)程在被調(diào)入內(nèi)存后很快又被換出，有的系統(tǒng)還會(huì)考慮進(jìn)程在內(nèi)存的駐留時(shí)間（注意：PCB會(huì)常駐內(nèi)存，不會(huì)被換出外存）

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

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

內(nèi)部碎片：分配給某進(jìn)程的內(nèi)存區(qū)域中，有些部分沒有用上

外部碎片：指內(nèi)存中的某些分區(qū)由于太小而難以利用

單一連續(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ú)占整個(gè)用戶區(qū)空間

• 優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單；無外部碎片；可以采用覆蓋技術(shù)擴(kuò)充內(nèi)存；不一定需要采取內(nèi)存保護(hù)（如早期的PC操作系統(tǒng)MS-DOS）

• 缺點(diǎn)：只能用于單用戶、單任務(wù)的操作系統(tǒng)中；有內(nèi)部碎片（分配給某進(jìn)程的內(nèi)存區(qū)域中，如果有些部分沒有用上，就是“內(nèi)部碎片”）；存儲(chǔ)器利用率極低

固定分區(qū)分配

20世紀(jì)60年代出現(xiàn)了支持多道程序的系統(tǒng)，為了能在內(nèi)存中裝入多道程序，且這些程序之間又不會(huì)互相干擾，于是將整個(gè)用戶空間劃分為若干個(gè)固定大小的分區(qū)，每個(gè)分區(qū)中只裝入一道作業(yè)，這樣就形成了最早的、最簡(jiǎn)單的一種可運(yùn)行多道程序的內(nèi)存管理方式

固定分區(qū)分配：

1. 分區(qū)大小相等缺乏靈活性，但是很適用于一臺(tái)計(jì)算機(jī)控制多個(gè)相同對(duì)象的場(chǎng)合（比如：煉鋼廠有n個(gè)相同的煉鋼爐，就可以把內(nèi)存分為n個(gè)大小相等的區(qū)域存放n個(gè)煉鋼爐控制程序）

2. 分區(qū)大小不等增加了靈活性，可以滿足大小不同的進(jìn)程需求。根據(jù)常在系統(tǒng)中運(yùn)行的作業(yè)大小情況進(jìn)行劃分（比如：劃分多個(gè)小分區(qū)、適量中等分區(qū)）

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

當(dāng)某應(yīng)用程序要裝入內(nèi)存時(shí)，由操作系統(tǒng)內(nèi)核程序根據(jù)用戶程序大小檢索該表，從中找到一個(gè)能滿足大小的、未分配的分區(qū)，將之分配給該程序，然后修改狀態(tài)為“已分配”

• 優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，無外部碎片

• 缺點(diǎn)：

1. 當(dāng)用戶程序太大時(shí)，可能所有的分區(qū)都不能滿足需求，此時(shí)不得不采用覆蓋技術(shù)來解決，但這又會(huì)降低性能

2. 會(huì)產(chǎn)生內(nèi)部碎片，內(nèi)存利用率低（比如一個(gè)應(yīng)用程序需要10MB但是只有12MB的分區(qū)6可供使用）

動(dòng)態(tài)分區(qū)分配

動(dòng)態(tài)分區(qū)分配又稱為可變分區(qū)分配，這種分配方式不會(huì)預(yù)先劃分內(nèi)存區(qū)域，而是在進(jìn)程裝入內(nèi)存時(shí)，根據(jù)進(jìn)程的大小動(dòng)態(tài)地建立分區(qū)，并使分區(qū)的大小正好適合進(jìn)程的需要。因此系統(tǒng)分區(qū)的大小和數(shù)目是可變的

1. 系統(tǒng)要用什么樣的數(shù)據(jù)結(jié)構(gòu)記錄內(nèi)存的使用情況？兩種常用的數(shù)據(jù)結(jié)構(gòu)：空閑分區(qū)表、空閑分區(qū)鏈

• 空閑分區(qū)表：每個(gè)空閑分區(qū)對(duì)應(yīng)一個(gè)表項(xiàng)，表項(xiàng)中包含分區(qū)號(hào)、分區(qū)大小、分區(qū)起始地址等信息

• 空閑分區(qū)鏈：每個(gè)分區(qū)的起始部分和末尾部分分別設(shè)置前項(xiàng)指針和后向指針。起始部分還可記錄分區(qū)大小等信息

2. 當(dāng)有很多個(gè)空閑分區(qū)都能滿足需求時(shí)，應(yīng)該選擇哪個(gè)分區(qū)進(jìn)行分配？把一個(gè)新作業(yè)裝入內(nèi)存時(shí)，需按照一定的動(dòng)態(tài)分區(qū)分配算法，從空閑分區(qū)表（或空閑分區(qū)鏈）中選出一個(gè)分區(qū)分配給該作業(yè)。由于分配算法對(duì)系統(tǒng)性能有很大的影響，因此人們做了廣泛研究。下一節(jié)會(huì)介紹四種動(dòng)態(tài)分區(qū)分配算法

3. 如何進(jìn)行分區(qū)的分配與回收操作？

• 分配時(shí)可能遇到的兩種情況如果進(jìn)程5需要4MB空間，將其分配給分區(qū)大小為20MB的空閑分區(qū)1號(hào)，重新修改空閑分區(qū)表的分區(qū)大小與起始地址

  如果進(jìn)程5需要4MB空間，將其分配給分區(qū)大小剛好為4MB的空閑分區(qū)三號(hào)，在空閑分區(qū)表中刪除3號(hào)分區(qū)對(duì)應(yīng)的表項(xiàng)

• 回收時(shí)可能遇到的情況

  進(jìn)程4的4MB空間需要回收，且與某個(gè)空閑分區(qū)相鄰，將這兩塊空間合并為1個(gè)如果與前后的空閑分區(qū)都相鄰，則將三塊空間合并為1個(gè)

  如果前后都沒有相鄰的空閑分區(qū)，則新增一個(gè)表項(xiàng)

動(dòng)態(tài)分區(qū)分配沒有內(nèi)部碎片，但是有外部碎片

如果內(nèi)存中的空閑區(qū)間總和本來可以滿足某進(jìn)程的需求，但由于進(jìn)程需要的是一塊連續(xù)的內(nèi)存空間，因此這些“碎片”不能滿足進(jìn)程的需求，可以通過緊湊（拼湊）技術(shù)來解決外部碎片

動(dòng)態(tài)分區(qū)分配算法

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

首次適應(yīng)算法

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

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

最佳適應(yīng)算法

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

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

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

最壞適應(yīng)算法

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

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

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

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

臨近適應(yīng)算法

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

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

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

• 臨近適應(yīng)算法的規(guī)則可能會(huì)導(dǎo)致無論低地址、高地址部分的空閑分區(qū)都有相同的概率被使用，也就導(dǎo)致了高地址部分的大分區(qū)更可能被使用，劃分為小分區(qū)，最后導(dǎo)致無大分區(qū)可用（最大適應(yīng)算法的缺點(diǎn)）

綜合來看，四種算法中，首次適應(yīng)算法的效果反而更好

基本分頁存儲(chǔ)管理的概念

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

分頁存儲(chǔ)

將內(nèi)存空間分為一個(gè)個(gè)大小相等的分區(qū)（比如：每個(gè)分區(qū)4KB），每個(gè)分區(qū)就是一個(gè)“頁框”（頁框=頁幀=內(nèi)存塊=物理塊=物理頁面）。每個(gè)頁框有一個(gè)編號(hào)，即“頁框號(hào)”（頁框號(hào)=頁幀號(hào)=內(nèi)存塊號(hào)=物理塊號(hào)=物理頁號(hào)），頁框號(hào)從0開始

將進(jìn)程的邏輯地址空間也分為與頁框大小相等的一個(gè)個(gè)部分，每個(gè)部分稱為一個(gè)“頁”或“頁面”。每個(gè)頁面有一個(gè)編號(hào)，即“頁號(hào)”，頁號(hào)也是從0開始

注意：頁不等于頁框

操作系統(tǒng)以頁框?yàn)閱挝粸楦鱾€(gè)進(jìn)程分配內(nèi)存空間。進(jìn)程的每個(gè)頁面分別放入一個(gè)頁框中。也就是說，進(jìn)程的頁面與內(nèi)存的頁框有一一對(duì)應(yīng)的關(guān)系

各個(gè)頁面不必連續(xù)存放，可以放到不相鄰的各個(gè)頁框中

頁表

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

頁表通常存在于PCB（進(jìn)程控制塊）中

1. 每個(gè)進(jìn)程對(duì)應(yīng)一張頁表

2. 進(jìn)程的每個(gè)頁面對(duì)應(yīng)一個(gè)頁表項(xiàng)

3. 每個(gè)頁表項(xiàng)由“頁號(hào)”和“塊號(hào)”組成

4. 頁表記錄進(jìn)程頁面實(shí)際存放的內(nèi)存塊之間的映射關(guān)系

頁表項(xiàng)連續(xù)存放，因此頁號(hào)可以是隱含的，不占存儲(chǔ)空間（類比數(shù)組）

實(shí)現(xiàn)地址的轉(zhuǎn)換

將進(jìn)程地址空間分頁后，操作系統(tǒng)該如何實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換？

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

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

1. 確定邏輯地址A對(duì)應(yīng)的“頁號(hào)”P

2. 找到P號(hào)頁面在內(nèi)存中的起始地址（需要查頁表）

3. 確定邏輯地址A的“頁面偏移量”W

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

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

基本地址變換機(jī)構(gòu)可以借助進(jìn)程的頁表將邏輯地址轉(zhuǎn)換為物理地址

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

注意：頁面大小是2的整數(shù)冪設(shè)頁面大小為L(zhǎng)，將邏輯地址A到物理地址E的變換過程如下：

1. 計(jì)算頁號(hào)P和頁內(nèi)偏移量W（如果用十進(jìn)制數(shù)手算，則P=A/L，W=A%L；但是在計(jì)算機(jī)實(shí)際運(yùn)行時(shí)，邏輯地址結(jié)構(gòu)是固定不變的，因此計(jì)算機(jī)硬件可以更快地得到二進(jìn)制表示的頁號(hào)、頁內(nèi)偏移量）

2. 比較頁號(hào)P和頁表長(zhǎng)度M，若P\geM，則產(chǎn)生越界中斷，否則繼續(xù)執(zhí)行。（注意：頁號(hào)是從0開始的，而頁表長(zhǎng)度至少是1，因此P=M時(shí)也會(huì)越界）

3. 頁表中頁號(hào)P對(duì)應(yīng)的頁表項(xiàng)地址=頁表起始地址F+頁號(hào)P*頁表項(xiàng)長(zhǎng)度。取出該頁表項(xiàng)內(nèi)容b，即為內(nèi)存塊號(hào)。（注意區(qū)分頁表項(xiàng)長(zhǎng)度、頁表長(zhǎng)度、頁面大小的區(qū)別。頁表長(zhǎng)度指的是這個(gè)頁表中總共有幾個(gè)頁表項(xiàng)，即總共有幾個(gè)頁；頁表項(xiàng)長(zhǎng)度指的是每個(gè)頁表項(xiàng)占多大的存儲(chǔ)空間；頁面大小指的是一個(gè)頁面占多大的存儲(chǔ)空間）

4. 計(jì)算E=b*L+W，用得到的物理地址E去訪存。（如果內(nèi)存塊號(hào)、頁面偏移量是用二進(jìn)制表示的，那么把二者拼接起來就是最終的物理地址了）

為了方便頁表的查詢，常常會(huì)讓一個(gè)頁表項(xiàng)占2的整數(shù)次冪個(gè)字節(jié)，使每個(gè)頁面恰好可以裝得下整數(shù)個(gè)頁表項(xiàng)

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

快表TLB

快表，又稱聯(lián)想寄存器（TLB，translation lookaside buffer），是一種訪問速度比內(nèi)存快很多的高速緩存（TLB不是內(nèi)存?。?，用來存放最近訪問的頁表項(xiàng)的副本，可以加速地址變換的速度。與之對(duì)應(yīng)，內(nèi)存中的頁表常稱為慢表

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

1. CPU給出邏輯地址，由某個(gè)硬件算得頁號(hào)、頁內(nèi)偏移量，將頁號(hào)與快表中的所有頁號(hào)進(jìn)行比較

2. 如果找到匹配的頁號(hào)，說明要訪問的頁表項(xiàng)在快表中有副本，則直接從中取出該頁對(duì)應(yīng)的內(nèi)存塊號(hào)，再將內(nèi)存塊號(hào)與頁內(nèi)偏移量拼接形成物理地址，最后訪問該物理地址對(duì)應(yīng)的內(nèi)存單元。因此，若快表命中，則訪問某個(gè)邏輯地址僅需一次訪存即可

3. 如果沒有找到匹配的頁號(hào)，則需要訪問內(nèi)存中的頁表，找到對(duì)應(yīng)頁的表項(xiàng)，得到頁面存放的內(nèi)存塊號(hào)，再將內(nèi)存塊號(hào)與頁內(nèi)偏移量拼接形成物理地址，最后訪問該物理地址對(duì)應(yīng)的內(nèi)存單元。因此，若快表未命中，則訪問某個(gè)邏輯地址需要兩次訪存（注意：在找到頁表項(xiàng)后，應(yīng)同時(shí)將其存入快表，以便后面可能得再次訪問。但若快表已滿，則必須按照一定的算法對(duì)舊的頁表項(xiàng)進(jìn)行替換）

由于查詢快表的速度比查詢頁表的速率快很多，因此只要快表命中，就可以節(jié)省很多時(shí)間。

局部性原理

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

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

兩級(jí)頁表

單級(jí)頁表存在的兩個(gè)問題

1. 頁表必須連續(xù)存放，因此當(dāng)頁表很大時(shí)，需要占用很多個(gè)連續(xù)的頁框

2. 沒有必要讓整個(gè)頁表常駐內(nèi)存，因?yàn)檫M(jìn)程在一段時(shí)間內(nèi)可能只需要訪問其中幾個(gè)特定的頁面

思考：我們是如何解決進(jìn)程在內(nèi)存中必須連續(xù)存儲(chǔ)的問題的？

將進(jìn)程地址空間分頁，并為其建立一張頁表，記錄各頁面的存放位置

同樣的思路也可用于解決“頁表必須連續(xù)存放”的問題，把必須連續(xù)存放的頁表再分頁

解決問題一

為了解決問題一：可將長(zhǎng)長(zhǎng)的頁表進(jìn)行分組，使每個(gè)內(nèi)存塊剛好可以放入一個(gè)分組（比如上個(gè)例子中，頁面大小4KB，每個(gè)頁表項(xiàng)4B，每個(gè)頁面可存放1K個(gè)頁表項(xiàng)，因此將每1K個(gè)連續(xù)的頁表項(xiàng)為一組，每組剛好占一個(gè)內(nèi)存塊，再將各組離散地放到各個(gè)內(nèi)存塊中）

另外，要為離散分配的頁表再建立一張頁表，成為頁目錄表，或稱外層頁表、頂層頁表

1. 按照地址結(jié)構(gòu)將邏輯地址拆分為三個(gè)部分

2. 從PCB中讀取頁目錄表的地址，再根據(jù)一級(jí)頁號(hào)查頁目錄表，找到下一級(jí)頁表再內(nèi)存中的存放位置

3. 根據(jù)二級(jí)頁號(hào)查表，找到最終想訪問的內(nèi)存塊號(hào)

4. 結(jié)合頁內(nèi)偏移量得到物理地址

解決問題二

問題2：沒有必要讓整個(gè)頁表常駐內(nèi)存，因?yàn)檫M(jìn)程在一段時(shí)間內(nèi)可能只需要訪問其中幾個(gè)特定的頁面

可以在需要訪問頁面時(shí)才把頁面調(diào)入內(nèi)存（虛擬存儲(chǔ)技術(shù)），可以在頁表項(xiàng)中增加一個(gè)標(biāo)志位，用于表示該頁面是否已經(jīng)調(diào)入內(nèi)存

若想訪問的頁面不在內(nèi)存中，則產(chǎn)生缺頁中斷（內(nèi)中斷），然后將目標(biāo)頁面從外存調(diào)入內(nèi)存

采用多級(jí)列表需要注意的問題

1. 各級(jí)頁表的大小不能超過一個(gè)頁面

2. 兩級(jí)頁表需要3次訪存，n級(jí)列表需要n+1次訪存

基本分段存儲(chǔ)管理方式

進(jìn)程的地址空間：按照程序自身地邏輯關(guān)系劃分為若干個(gè)段，每個(gè)段都有一個(gè)段名（在低級(jí)語言中，程序使用段名來編程），每段從0開始編址

段表

問題：程序分為多個(gè)段，各個(gè)段離散地裝入內(nèi)存，為了保證程序能正常運(yùn)行，就必須能從物理內(nèi)存中找到各個(gè)邏輯段的存放位置。為此，需要為每個(gè)進(jìn)程建立一張段映射表，簡(jiǎn)稱“段表”

1. 每個(gè)段對(duì)應(yīng)一個(gè)段表項(xiàng)，其中記錄了該段在內(nèi)存中的起始位置（基址）和段的長(zhǎng)度

2. 各個(gè)段表項(xiàng)的長(zhǎng)度是相同的。

分段、分頁管理的對(duì)比

頁是信息的物理單位。分頁的主要目的是為了實(shí)現(xiàn)離散分配，提高內(nèi)存利用率。分頁僅僅是系統(tǒng)管理上的需要，完全是系統(tǒng)行為，對(duì)用戶是不可見的

段時(shí)信息的邏輯單位。分段的主要目的是更好地滿足用戶需求。一個(gè)段通常包含著一組屬于一個(gè)邏輯模塊的信息。分段對(duì)用戶是可見的，用戶編程時(shí)需要顯式地給出段名

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

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

分段比分頁更容易實(shí)現(xiàn)信息的共享和保護(hù)

訪問一個(gè)邏輯地址需要幾次訪存？

分頁（單級(jí)頁表）：第一次訪存：查內(nèi)存中的頁表；第二次訪存：訪問目標(biāo)內(nèi)內(nèi)存單元?？偣矁纱?/span>

分段：第一次訪存：查內(nèi)存中的段表；第二次訪存：訪問目標(biāo)內(nèi)存單元?？偣矁纱?/span>

與分頁系統(tǒng)類似，分段系統(tǒng)也可以引入快表幾個(gè)，將近期訪問過的段表項(xiàng)放到快表中，這樣可以減少一次訪問

段頁式管理方式

分頁、分段的優(yōu)缺點(diǎn)分析：

• 分頁管理：

• 優(yōu)點(diǎn)：內(nèi)存利用率高，不會(huì)產(chǎn)生外部碎片，只有少量的頁內(nèi)碎片

• 缺點(diǎn)：不方便按照邏輯模塊實(shí)現(xiàn)信息的共享和保護(hù)

• 分段管理

• 優(yōu)點(diǎn)：很方便按照邏輯模塊實(shí)現(xiàn)信息的共享和保護(hù)

• 如果段長(zhǎng)過大，為其分配很大的連續(xù)空間會(huì)很不方便。另外，段式管理會(huì)產(chǎn)生外部碎片

段頁式管理的邏輯地址結(jié)構(gòu)

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

分段對(duì)用戶是可見的，程序員編程時(shí)需要顯式地給出段號(hào)、段內(nèi)地址。而將各段分頁對(duì)用戶是不可見的，系統(tǒng)會(huì)根據(jù)段內(nèi)地址自動(dòng)地劃分頁號(hào)和頁內(nèi)偏移量。

因此段頁式管理的地址結(jié)構(gòu)是二維的

一個(gè)進(jìn)程對(duì)應(yīng)一個(gè)段表，但是每個(gè)段會(huì)對(duì)應(yīng)一個(gè)頁表，因此一個(gè)進(jìn)程可能對(duì)應(yīng)多個(gè)頁表

往期文章：
王道操作系統(tǒng)第2章-進(jìn)程管理-死鎖 - 嗶哩嗶哩 (bilibili.com)

王道操作系統(tǒng)第2章-進(jìn)程管理-進(jìn)程的同步與互斥 - 嗶哩嗶哩 (bilibili.com)

王道操作系統(tǒng)第2章-進(jìn)程管理-調(diào)度 - 嗶哩嗶哩 (bilibili.com)

王道操作系統(tǒng)第2章-進(jìn)程管理-進(jìn)程與線程 - 嗶哩嗶哩 (bilibili.com)

王道操作系統(tǒng)第1章-操作系統(tǒng)概述 - 嗶哩嗶哩 (bilibili.com)