目錄

一、存儲器的層次結(jié)構(gòu)

二、程序的裝入和鏈接

2.1 邏輯地址和物理地址

2.2?絕對裝入方式

2.3?可重定位裝入方式

2.4?動態(tài)運(yùn)行時裝入方式

2.5 靜態(tài)鏈接?

2.6 裝入時動態(tài)鏈接

2.7 運(yùn)行時動態(tài)鏈接

三、連續(xù)分配存儲器管理方式

3.1?單一連續(xù)分配

3.2?固定分區(qū)分配

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

3.3.1?分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)

3.3.2?分區(qū)分配算法

3.3.3?分區(qū)分配及回收操作

3.4?可重定位分區(qū)分配

四、對換

4.1?對換的引入

4.2?對換空間的管理

4.3?進(jìn)程的換出與換入

五、分頁存儲管理方式

5.1 頁表?

5.2 分頁存儲管理中的邏輯地址結(jié)構(gòu)

5.3 由邏輯地址求物理地址

5.4?地址變換機(jī)構(gòu)

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

5.6?兩級和多級頁表

六、分段存儲管理方式?

6.1 分段的邏輯結(jié)構(gòu)

6.2?段表

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

6.4 分段、分頁的對比

七、段頁式管理方式

八、結(jié)尾

Reference

一、存儲器的層次結(jié)構(gòu)

存儲器管理的主要對象是內(nèi)存，這也是本章重點(diǎn)，對外存的管理在文件管理那一章講解。

多級存儲器結(jié)構(gòu)：

主存儲器與寄存器：

• 主存儲器：可執(zhí)行存儲器
• 寄存器：訪問速度最快。

高速緩存和磁盤緩存：

• 高速緩存：訪問速度快于主存儲器
• 磁盤緩存：利用主存中的存儲空間。

二、程序的裝入和鏈接

用戶程序要在系統(tǒng)中運(yùn)行，必須先將它裝入內(nèi)存，然后才能將其轉(zhuǎn)變?yōu)橐粋€可以執(zhí)行的程序，通常要經(jīng)過以下幾個步驟：

1、編譯：由編譯程序?qū)⒂脩粼创a編譯成若干個目標(biāo)模塊

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

3、裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存

?

2.1 邏輯地址和物理地址

在進(jìn)行下面的講解前，一定要注意區(qū)分邏輯地址和物理地址，它們相互對應(yīng)，但并不相等，它們之間還需要經(jīng)過地址映射的過程。

邏輯地址：是指程序在運(yùn)行過程中使用的地址，也稱為虛擬地址。它是由CPU生成的，用于訪問內(nèi)存中的數(shù)據(jù)。它也是程序員編寫程序時所采用的一種地址，這些地址有可能會超過物理內(nèi)存可用的范圍。

因此，在內(nèi)存管理中，操作系統(tǒng)根據(jù)自己的算法，將邏輯地址轉(zhuǎn)換為物理地址，使得程序能夠正常地讀取和寫入內(nèi)存中的數(shù)據(jù)。

物理地址：是指內(nèi)存中實(shí)際的地址，也稱為實(shí)地址（Real Address。它是CPU直接訪問的硬件設(shè)備中的內(nèi)存單元地址。當(dāng)CPU訪問這樣的地址時，它可以直接引用到內(nèi)存中的數(shù)據(jù)。

將一個裝入模塊裝入內(nèi)存時，有三種方式：??

2.2?絕對裝入方式

在編譯時，如果知道程序駐留在內(nèi)存的什么位置，那么編譯程序?qū)a(chǎn)生絕對地址的目標(biāo)代碼。

裝入模塊裝入內(nèi)存后，程序中的邏輯地址與實(shí)際內(nèi)存地址完全相同，不須對程序和數(shù)據(jù)的地址進(jìn)行修改。

程序中所使用的絕對地址，可在編譯或匯編時給出，也可由程序員賦予。通常在程序中采用符號地址，然后在編譯或匯編時，再將這些符號地址轉(zhuǎn)換為絕對地址。

注意：這種方式主要由編譯器負(fù)責(zé)地址轉(zhuǎn)換，用于單道程序階段（即無操作系統(tǒng)階段）?。?

2.3?可重定位裝入方式

又叫靜態(tài)重定位。?

絕對裝入方式只能將目標(biāo)模塊裝入到內(nèi)存中事先指定的位置。在多道程序環(huán)境下，編譯程序不能預(yù)知所編譯的目標(biāo)模塊應(yīng)放在內(nèi)存何處，因此絕對裝入方式只適用于單道程序環(huán)境下。

在多道程序環(huán)境下，目標(biāo)模塊的起始地址通常從0開始，程序中的其他地址都是相對于起始地址計(jì)算的。因此應(yīng)采用可重定位裝入方式，根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入到內(nèi)存的適當(dāng)位置。

在裝入時，對目標(biāo)程序中指令和數(shù)據(jù)的修改過程稱為重定位。地址變換在裝入時一次完成，以后不再改變，稱為靜態(tài)重定位。

例如：

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

注意：裝入程序負(fù)責(zé)地址轉(zhuǎn)換，主要用于早期多道批處理階段。

2.4?動態(tài)運(yùn)行時裝入方式

前瞻：重定位裝入方式，可將裝入模塊裝入到內(nèi)存中任何允許的位置，故可用于多道程序環(huán)境；但并不允許程序運(yùn)行時在內(nèi)存中移動位置。

實(shí)際上，在運(yùn)行過程中程序在內(nèi)存中的位置可能經(jīng)常要改變。

動態(tài)運(yùn)行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行。因此，裝入內(nèi)存后的所有地址都仍是相對地址（邏輯地址）。為使地址轉(zhuǎn)換不影響指令的執(zhí)行速度，應(yīng)設(shè)置一個重定位寄存器。

例如，采用動態(tài)運(yùn)行時裝入方式將其裝入邏輯地址與內(nèi)存中物理地址一樣的位置，當(dāng)程序開始執(zhí)行指令0時，通過重定位寄存器中保存的起始位置100，將其與指令0中的邏輯地址79相加，即可得到正確的物理地址位置，程序方可正確運(yùn)行下去。

采用動態(tài)可重定位時，允許程序在內(nèi)存中發(fā)生移動。并且可將程序分配到不連續(xù)的存儲區(qū)中，在程序運(yùn)行前只需裝入它的部分代碼即可投入運(yùn)行，然后在程序運(yùn)行期間，根據(jù)需要動態(tài)申請分配內(nèi)存；便于程序段的共享，可以向用戶提供一個比存儲空間大得多的地址空間。

注意：運(yùn)行時才進(jìn)行地址轉(zhuǎn)換，主要用于現(xiàn)代操作系統(tǒng)

程序經(jīng)過編譯后得到一組目標(biāo)模塊，再利用鏈接程序?qū)⒛繕?biāo)模塊鏈接，形成裝入模塊。

根據(jù)鏈接時間的不同，把鏈接分成三種：

2.5 靜態(tài)鏈接?

在程序運(yùn)行前，將目標(biāo)模塊及所需的庫函數(shù)鏈接成一個完整的裝配模塊（可執(zhí)行文件），以后不再拆開。

2.6 裝入時動態(tài)鏈接

指將用戶源程序編譯后所得的一組目標(biāo)模塊，在裝入內(nèi)存時，采用邊裝入邊鏈接的鏈接方式。

即在裝入一個目標(biāo)模塊時，若發(fā)生一個外部模塊調(diào)用事件，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存，還要修改目標(biāo)模塊中的相對地址。

優(yōu)點(diǎn)：

• 便于修改和更新
• 便于實(shí)現(xiàn)對目標(biāo)模塊的共享

2.7 運(yùn)行時動態(tài)鏈接

指對某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該目標(biāo)模塊時，才對它進(jìn)行鏈接。

在許多情況下，應(yīng)用程序要運(yùn)行的模塊可能不同，事先不知道要運(yùn)行哪些模塊，只能全部裝入，裝入時全部鏈接在一起，效率低。

而運(yùn)行時動態(tài)鏈接是將對某些模塊的鏈接推遲到執(zhí)行時才執(zhí)行，即在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。凡執(zhí)行過程中未被用到的目標(biāo)模塊，不會調(diào)入內(nèi)存和鏈接。

優(yōu)點(diǎn)：這樣不僅加快程序的裝入過程，而且節(jié)省大量的內(nèi)存空間。

這是對裝入時動態(tài)鏈接的一種改進(jìn)，當(dāng)然也具備它所擁有的優(yōu)點(diǎn)。

三、連續(xù)分配存儲器管理方式

連續(xù)分配方式，是指為一個用戶程序分配一個連續(xù)的內(nèi)存空間。

3.1?單一連續(xù)分配

最簡單的一種存儲管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。

采用這種存儲管理方式時，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常放在內(nèi)存低址部分，用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。

由于內(nèi)存中只能有一道用戶程序，用戶程序獨(dú)占整個用戶區(qū)空間。導(dǎo)致有很大一部分用戶區(qū)空閑，內(nèi)存利用率低，有大量內(nèi)部碎片，存儲器利用率極低。

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

3.2?固定分區(qū)分配

為了能夠支持多道程序的系統(tǒng)，內(nèi)存用戶空間被劃分為若干個固定大小的區(qū)域，在每個分區(qū)中只裝入一道作業(yè)，這樣把用戶空間劃分為幾個分區(qū)，便允許有幾道作業(yè)并發(fā)執(zhí)行。當(dāng)有一空閑分區(qū)時，便可以再從外存的后備作業(yè)隊(duì)列中，選擇一個適當(dāng)大小的作業(yè)裝入該分區(qū)，當(dāng)該作業(yè)結(jié)束時，可再從后備作業(yè)隊(duì)列中找出另一作業(yè)調(diào)入該分區(qū)。?

可用兩種方法將內(nèi)存的用戶空間劃分為若干個固定大小的分區(qū)：

(1) 分區(qū)大小相等：缺乏靈活性，用于一臺計(jì)算機(jī)控制多個相同對象的場合

(2) 分區(qū)大小不等：把內(nèi)存區(qū)劃分成含有多個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)，可根據(jù)程序的大小為之分配適當(dāng)?shù)姆謪^(qū)。

為便于內(nèi)存分配，通常將分區(qū)按大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表，其中各表項(xiàng)包括每個分區(qū)的起始地址、大小及狀態(tài)(是否已分配)。

有一用戶程序要裝入時，由內(nèi)存分配程序檢索該表，從中找出一個能滿足要求的、尚未分配的分區(qū)，將之分配給該程序，然后將該表項(xiàng)中的狀態(tài)置為“已分配”；若未找到大小足夠的分區(qū)，則拒絕為該用戶程序分配內(nèi)存。?

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

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

缺點(diǎn)：內(nèi)存利用率較低，會產(chǎn)生內(nèi)部碎片。

內(nèi)部碎片和外部碎片的區(qū)別：

內(nèi)部碎片：分配出去但有些沒用上

外部碎片：沒分配出去但本身無法使用（太小了，難以利用）。?

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

動態(tài)分區(qū)分配不會預(yù)先劃分內(nèi)存分區(qū)，而是根據(jù)進(jìn)程的實(shí)際需要，動態(tài)地為之分配內(nèi)存空間。作業(yè)裝入內(nèi)存時，把可用內(nèi)存分出一個連續(xù)區(qū)域給作業(yè)，且分區(qū)的大小正好適合作業(yè)大小的需要。分區(qū)的大小和個數(shù)依裝入作業(yè)的需要而定。?

在實(shí)現(xiàn)過程中，將涉及如下問題：

1、分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)

2、分區(qū)分配算法

3、分區(qū)分配及回收操作

3.3.1?分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)

常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式：?

空閑分區(qū)表：記錄每個空閑分區(qū)的情況。每個空閑分區(qū)占一個表目。表目中包括：分區(qū)序號、分區(qū)始址、分區(qū)的大小等。

空閑分區(qū)鏈：在每個分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針；在分區(qū)尾部則設(shè)置一后向指針，在分區(qū)末尾重復(fù)設(shè)置狀態(tài)位和分區(qū)大小表目。

3.3.2?分區(qū)分配算法

為把一個新作業(yè)裝入內(nèi)存，需按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。

常用的分配算法：

(1) 首次適應(yīng)算法FF

(2) 循環(huán)首次適應(yīng)算法

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

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

當(dāng)有很多個空閑分區(qū)都能夠滿足需求時，應(yīng)該選擇哪個分區(qū)進(jìn)行分配呢？?這就取決于你選擇的算法了。

【1】首次適應(yīng)算法FF

FF算法要求空閑分區(qū)表以地址遞增的次序排列。在分配內(nèi)存時，從表首開始順序查找，直至找到一個大小能滿足要求的空閑分區(qū)為止；然后按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑分區(qū)表中。若從頭到尾不存在滿足要求的分區(qū)，則分配失敗。

優(yōu)點(diǎn)：優(yōu)先利用內(nèi)存低址部分的內(nèi)存空間

缺點(diǎn)：低址部分不斷劃分，產(chǎn)生外碎片；每次查找從低址部分開始，增加了查找的開銷。地址密集，高址空閑。

【2】?循環(huán)首次適應(yīng)算法

在分配內(nèi)存空間時，空閑分區(qū)表以地址遞增的次序排列，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到一個能滿足要求的空閑分區(qū)，從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。

為實(shí)現(xiàn)算法，需要：

1、設(shè)置一個起始查尋指針

2、采用循環(huán)查找方式（當(dāng)最后一個空閑分區(qū)也不能滿足要求，則應(yīng)回到第一個空閑分區(qū)）

優(yōu)點(diǎn)：使內(nèi)存空閑分區(qū)分布均勻，減少查找的開銷

缺點(diǎn)：缺乏大的空閑分區(qū)

【3】 最佳適應(yīng)算法

所謂“最佳”是指每次為作業(yè)分配內(nèi)存時，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。

要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈。

缺點(diǎn)：產(chǎn)生許多難以利用的小空閑區(qū)，即外部碎片。

【4】最壞適應(yīng)算法

算法思想：為了解決最佳適應(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ū)可用了。

3.3.3?分區(qū)分配及回收操作

【1】分配內(nèi)存

利用某種分配算法，從空閑分區(qū)鏈(表)中找到所需大小的分區(qū)。設(shè)請求的分區(qū)大小為u.size，表中每個空閑分區(qū)的大小表示為m.size，若m.size- u.size <=?size(規(guī)定的不再切割的分區(qū)大小)，將整個分區(qū)分配給請求者，否則從分區(qū)中按請求的大小劃出一塊內(nèi)存空間分配出去，余下部分留在空閑鏈中，將分配區(qū)首址返回給調(diào)用者。?

【2】回收內(nèi)存

當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)首址（釋放區(qū)首址），在空閑分區(qū)鏈(表)中找到相應(yīng)插入點(diǎn)，此時可能有四種情況：

(1) 如上圖A，釋放區(qū)與插入點(diǎn)的前一個空閑分區(qū)F1鄰接：將該回收區(qū)與F1合并，修改F1的表項(xiàng)的分區(qū)大小。

(2) 如上圖B，回收區(qū)與插入點(diǎn)的后一個空閑分區(qū)F2鄰接：將回收區(qū)與F2合并，修改F2的表項(xiàng)的首址、分區(qū)大小。

(3) 如上圖C，回收區(qū)與插入點(diǎn)的前后兩個空閑分區(qū)F1、F2鄰接：將三個分區(qū)合并，使用F1的表項(xiàng)和F1的首址，取消F2的表項(xiàng)，大小為三者之和。

(4) 如上圖D，回收區(qū)不和任何空閑區(qū)鄰接，那么就要為該回收區(qū)單獨(dú)建立新表項(xiàng)，填寫回收區(qū)的首址與大小，根據(jù)其首址插到空閑鏈中的適當(dāng)位置。

3.4?可重定位分區(qū)分配

在連續(xù)分配方式中，必須把系統(tǒng)或用戶程序裝入一連續(xù)的內(nèi)存空間。如果在系統(tǒng)中只有若干個小分區(qū)，即使它們的容量總和大于要裝入的程序，但由于這些分區(qū)不相鄰，所以無法將程序裝入內(nèi)存。

解決方法：將內(nèi)存中的所有作業(yè)進(jìn)行移動，使它們?nèi)苦徑樱@樣可把原來分散的小分區(qū)拼接成大分區(qū)，這種方法稱為“拼接”或“緊湊”。

缺點(diǎn)：用戶程序在內(nèi)存中的地址發(fā)生變化，必須重定位。

動態(tài)重定位分區(qū)分配算法與動態(tài)分區(qū)分配算法基本相同，差別在于增加了緊湊的功能。

前面講的動態(tài)分區(qū)分配：無內(nèi)部碎片，有外部碎片。

但是利用可重定位分區(qū)分配的緊湊功能，可以解決外部碎片。?

四、對換

4.1?對換的引入

多道程序環(huán)境下存在的問題：

1、阻塞進(jìn)程占據(jù)大量內(nèi)存空間

2、許多作業(yè)在外存而不能進(jìn)入內(nèi)存運(yùn)行

對換：把內(nèi)存中暫時不能運(yùn)行的進(jìn)程或者暫時不用的程序和數(shù)據(jù)，調(diào)到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程和進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。?

而對換的這種功能可以很好的解決這些問題！

對換的分類：

• 整體對換(或進(jìn)程對換)：以整個進(jìn)程為單位（這也沒啥可介紹的）
• 頁面對換或分段對換：以頁或段為單位（在下一章虛擬存儲器中介紹）

實(shí)現(xiàn)進(jìn)程對換，系統(tǒng)必須具備的功能：

1、對換空間的管理

2、進(jìn)程的換出

3、進(jìn)程的換入?

4.2?對換空間的管理

一般從磁盤上劃出一塊空間作為對換區(qū)使用，其余空間用作文件區(qū)?：

在系統(tǒng)中設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)以記錄外存的使用情況，并且對換空間的分配與回收，與動態(tài)分區(qū)方式時的內(nèi)存分配與回收雷同，所以就不闡述了。

4.3?進(jìn)程的換出與換入

進(jìn)程的換出：

換出過程：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進(jìn)程作為換出進(jìn)程，然后啟動盤塊，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。

進(jìn)程的換入：

換入過程：系統(tǒng)應(yīng)定時查看所有進(jìn)程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程，將換出進(jìn)程最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無可換入的進(jìn)程或無可換出的進(jìn)程為止。

五、分頁存儲管理方式

連續(xù)分配方式會形成“碎片”，雖然可以通過“緊湊”解決，但開銷大。如果允許將一個進(jìn)程直接分散地裝入許多不相鄰的分區(qū)中，則無需“緊湊”，由此產(chǎn)生離散分配方式。

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

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

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

當(dāng)然進(jìn)程不可能每次都能恰好等分成與頁框大小相等的一個個部分，即進(jìn)程的最后一頁可能與頁框大小不等，因此會因?yàn)檠b不滿而形成“頁內(nèi)碎片”。但做題時，不用考慮這些，一般都是可以等分的。

5.1 頁表?

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

注：頁表通常存在PCB?(進(jìn)程控制塊)中

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

考點(diǎn)1：

1. 計(jì)算內(nèi)存塊的數(shù)量
2. 頁表項(xiàng)中塊號至少占多少字節(jié)
   ?

e.g： 假設(shè)某系統(tǒng)物理內(nèi)存大小為4GB，?頁面大小為4KB，?計(jì)算內(nèi)存塊的數(shù)量？計(jì)算每個頁表項(xiàng)至少應(yīng)該為多少字節(jié)?（注意是字節(jié)）

解：
→ 內(nèi)存塊大小=頁面大小=4KB=212B
→ 4GB的內(nèi)存總共會被分為232/212=22?個內(nèi)存塊
→ 所以內(nèi)存塊號的范圍應(yīng)該是0～22?-1
→ 那么內(nèi)存塊號至少要用20?bit來表示
→ 因此至少要用3B來表示塊號( 3×8=24bit)
→ 由于頁號是隱含，并不占存儲空間，因此每個頁表項(xiàng)占3B，存儲整個頁表至少需要

? ? ?3*(n+1)B

之所以頁號不占存儲空間，是因?yàn)轫摫砀黜?xiàng)本身就是連續(xù)存放的（頁表這種結(jié)構(gòu)就類似一維數(shù)組，頁號是下標(biāo)，塊號是數(shù)組值）?。

就拿上面那個例題而言：假設(shè)頁表中的各頁表項(xiàng)從邏輯地址為?X?的地方開始連續(xù)存放...
如何找到頁號為i的頁表項(xiàng)?
那么 i 號頁表項(xiàng)的存放地址為：X + 3 * i

5.2 分頁存儲管理中的邏輯地址結(jié)構(gòu)

?考點(diǎn)2：

1. 如何確定一個邏輯地址對應(yīng)的頁號、頁內(nèi)偏移量?

這是有公式的：

• 頁號 = 邏輯地址/頁面長度?(取除法的整數(shù)部分)
• 頁內(nèi)偏移量 = 邏輯地址%頁面長度(取除法的余數(shù)部分)

（1）通過一個簡單的圖形介紹一下：

頁號 = 110 / 50= 2
頁內(nèi)偏移量 = 110 % 50 = 10?

（2）從二進(jìn)制的角度理解：

?5.3 由邏輯地址求物理地址

• 邏輯地址 = 頁號 + 頁內(nèi)地址
• （適用頁面大小剛好是2的整數(shù)次冪）物理地址 = 內(nèi)存塊號 + 頁內(nèi)地址
• （超級萬能）物理地址 = 頁面在內(nèi)存中存放的起始地址 + 頁內(nèi)地址

通過下面兩個經(jīng)典題型，讓你瞬間秒懂！

題型一：通過十進(jìn)制計(jì)算（用超級萬能）。

已知某個分頁系統(tǒng)，頁面大小為1K(即1024字節(jié))，某一個作業(yè)有4個頁面，分別裝入到主存的第3、4、6、8塊中，求邏輯地址2100對應(yīng)的物理地址。

解：

1. 求該邏輯地址的頁號 = 2100 / 1024=2 （整除）
2. 求它的頁內(nèi)偏移量 = 2100 % 1024 =52 （取余）
3. 根據(jù)題目產(chǎn)生頁表：
   頁號????頁框號/幀號
   ???0???????????3
   ???1???????????4
   ???2???????????6?
   ???3???????????8
4. 如上圖，邏輯地址的第2頁對應(yīng)物理地址的第6塊。
5. 頁面在內(nèi)存中存放的起始地址 = 內(nèi)存塊號 * 頁面大小
6. 求出物理地址 = 6*1024 + 52 = 6196

題型二：（一般會給你8進(jìn)制或16進(jìn)制，建議先轉(zhuǎn)成2進(jìn)制計(jì)算）通過二進(jìn)制計(jì)算。

（因?yàn)?span style="color:#fe2c24;">頁面大小剛好是2的整數(shù)次冪，并且是采用2進(jìn)制計(jì)算，所以用這個公式：物理地址 = 內(nèi)存塊號 + 頁內(nèi)地址）?

已知分頁存儲管理系統(tǒng)中邏輯地址長度為16位，頁面大小為4KB字節(jié)，現(xiàn)有一邏輯地址為3C20H，且第0、1、2、3頁依次存放在物理塊2、3、5、6中。求邏輯地址3C20H對應(yīng)的物理地址?
解：?

1. 將邏輯地址3C20H轉(zhuǎn)換為二進(jìn)制為：0011?1100?0010?0000
2. 由于頁面大小為4KB字節(jié)，（4KB=2^12）。所以邏輯地址的后12位為“頁內(nèi)地址”，那么剩下的前4位為頁號：即0011為頁號?
3. 根據(jù)頁表可知，0011(十進(jìn)制為3)對應(yīng)的頁框號（內(nèi)存塊號）為6(二進(jìn)制為0110)?
4. 所以最終的物理地址為：0110 1100?0010?0000?
   即 6C20H

通過題型就能說明一切，對于題型二，如果頁面大小不是2的整數(shù)次冪，那么就很難將邏輯地址拆分成：頁號 + 頁內(nèi)地址。但是如果頁面大小不是2的整數(shù)次冪，我們可以用超級萬能解決，只是對于這種二進(jìn)制的計(jì)算比較麻煩一點(diǎn)，需要先將其轉(zhuǎn)成題型一那樣。

大部分題型的頁面大小都是2的整數(shù)次冪，除非你們老師喜歡刁鉆的出題，hh。

5.4?地址變換機(jī)構(gòu)

上面講的是手算實(shí)現(xiàn)邏輯地址向物理地址的轉(zhuǎn)換，如果你理解了上述思想，那么下面講的地址變換機(jī)構(gòu)，就是從計(jì)算機(jī)的角度實(shí)現(xiàn)這個變換。

由于寄存器成本高，系統(tǒng)頁表可能很大，所以頁表大多常駐內(nèi)存。

在系統(tǒng)中只設(shè)置一個頁表寄存器PTR，在其中存放頁表在內(nèi)存中的始址和頁表的長度（即多少頁）。

實(shí)現(xiàn)步驟如下：

詳細(xì)介紹：（前提：頁面大小是2的整數(shù)冪）

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

設(shè)頁面大小為L，邏輯地址A?到 物理地址E的變換過程如下;

① 計(jì)算頁號P?和 頁內(nèi)偏移量W

② 比較頁號P?和頁表長度M，若 P ≥ M,則產(chǎn)生越界中斷，否則繼續(xù)執(zhí)行。

• 注意：頁號是從0開始的，而頁表長度至少是1，因此P=N時也會越界

③?頁表中頁號P對應(yīng)的頁表項(xiàng)地址=頁表起始地址F+頁號P*頁表項(xiàng)長度，取出該頁表項(xiàng)內(nèi)容b，即為內(nèi)存塊號。

• 注意區(qū)分頁表項(xiàng)長度、頁表長度、頁面大小的區(qū)別。
• 頁表長度指的是這個頁表中總共有幾個頁表項(xiàng)，即總共有幾個頁；
• 頁表項(xiàng)長度指的是每個頁表項(xiàng)占多大的存儲空間；
• 頁面大小指的是一個頁面占多大的存儲空間

④ 計(jì)算E = b * L + W，用得到的物理地址E去訪存。

• 如果內(nèi)存塊號、頁面偏移量是用二進(jìn)制表示的，那么把二者拼接起來就是最終的物理地址了

看到這里，是不是和我們手算幾乎一模一樣啊，只是計(jì)算機(jī)算的更快！

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

上述介紹的基本地址變換機(jī)構(gòu)中，每次要訪問一個邏輯地址，都需要查詢內(nèi)存中的頁表。由于局部性原理，可能連續(xù)很多次查到的都是同一個頁表項(xiàng) ，我們難道不能把第一次查到的信息存下來嘛？因此塊表就誕生了！

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

有點(diǎn)Cache的味道了~

若第一個（0，0）的邏輯地址被訪存后，會向 快表 里記錄頁號為0對應(yīng)的內(nèi)存塊號，接下來，如果還有同一頁號的邏輯地址，就不需要再去訪問內(nèi)存中的頁表，查詢內(nèi)存塊號了。?

詳細(xì)步驟如下：

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

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

③?如果沒有找到匹配的頁號，則需要訪問內(nèi)存中的頁表，找到對應(yīng)頁表項(xiàng)，得到頁面存放的內(nèi)存塊號，再將內(nèi)存塊號與頁內(nèi)偏移量拼接形成物理地址，最后，訪問該物理地址對應(yīng)的內(nèi)存單元。因此，若快表未命中，則訪問某個邏輯地址需要兩次訪存。（即訪存頁表 +?訪存目標(biāo)頁面）

• 注意：在找到頁表項(xiàng)后，應(yīng)同時將其存入快表，以便后面可能的再次訪問。但若快表已滿，則必須按照一定的算法對舊的頁表項(xiàng)進(jìn)行替換

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

例：某系統(tǒng)使用基本分頁存儲管理，并采用了具有快表的地址變換機(jī)構(gòu)。訪問一次快表耗時1us，訪問一次內(nèi)存耗時100us。若快表的命中率為90%，那么訪問一個邏輯地址的平均耗時是多少?

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

有的系統(tǒng)支持快表和慢表同時查找，如果是這樣，平均耗時應(yīng)該是((1+100)*0.9+(100+100)*0.1=110.9?us

若未采用快表機(jī)制，則訪問一個邏輯地址需要100+100=200us

總結(jié)?：

5.6?兩級和多級頁表

例子：一個具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4KB即B，則每個進(jìn)程頁表的頁表項(xiàng)可達(dá)1M個，若每個頁表項(xiàng)占用一個字節(jié)，則每個進(jìn)程的頁表就要占據(jù)1MB的內(nèi)存空間，而且要求連續(xù)存放。?

內(nèi)存想要做到上述條件是比較吃力的！?。?/p>

解決方法：

1. 采用離散方式
2. 只將當(dāng)前所需頁表項(xiàng)調(diào)入內(nèi)存

這里只介紹第一種方法，對于第二種方法在下一章介紹（主要運(yùn)用虛擬存儲技術(shù)）。?

當(dāng)然對于第一種方式，我們也只介紹兩級頁表，無限套娃沒有意思~

兩級頁表定義：?

將頁表分頁，并離散地將各個頁面分別存放在不同的物理塊中，同時為離散分配的頁表在建立一張頁表，稱為外層頁表（或頁目錄表），其每個頁表項(xiàng)記錄了頁表頁面的物理塊號。

其邏輯地址結(jié)構(gòu)，其實(shí)就是將其頁號在進(jìn)一步劃分為一級頁號和二級頁號。

例如： 32位邏輯地址空間，頁面大小為4KB(即12位)，若采用一級頁表機(jī)構(gòu)，應(yīng)有20位頁號，即頁表項(xiàng)應(yīng)有1M個；在采用兩級頁表機(jī)構(gòu)時，再對頁表進(jìn)行分頁，使每頁包含(即1024)個頁表項(xiàng)，最多允許有個頁表分頁。即：

例題：就拿上述那個圖為例，將邏輯地址（0000000000 0000000001 111111111111）轉(zhuǎn)換為物理地址（用十進(jìn)制表示）。

解：

一級頁號為：0（從內(nèi)存塊號1011讀出第0頁頁表），二級頁號為：1，那么就能快速定位到4號內(nèi)存塊，然后用超級萬能解題：
→ 4號內(nèi)存塊的起始地址為：4 * 4096 = 16384

→ 頁內(nèi)偏移量為4095

→ 最終的物理地址為：16384 + 4095

注意：兩級頁表的訪存次數(shù)（假設(shè)沒有快表）為：3次

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

六、分段存儲管理方式?

分頁存儲管理的缺點(diǎn)：無論信息內(nèi)容如何，按頁長分割，分割后裝入內(nèi)存，有可能主程序未能全部進(jìn)入內(nèi)存，-----執(zhí)行速度降低。

因此基于以上問題，分段存儲管理方式考慮以邏輯單位分配內(nèi)存。如：

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

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

6.1 分段的邏輯結(jié)構(gòu)

每個段定義了一組邏輯信息，都有自己的名字。通常用段號代替段名。

邏輯地址由段號(段名)和段內(nèi)地址所組成：

段號決定了每個進(jìn)程最多可以分幾個段。

段內(nèi)地址決定了每個進(jìn)程的最大長度。

?假設(shè)上述按字節(jié)尋址。那么該地址結(jié)構(gòu)允許一個作業(yè)最長有64K個段，每段的最大長度為64KB。

6.2?段表

在分段式存儲管理系統(tǒng)中，系統(tǒng)為每個分段分配一個連續(xù)的分區(qū)，而進(jìn)程中的各個段可以離散地移入內(nèi)存中不同的分區(qū)中。

為使程序正常運(yùn)行，須在系統(tǒng)中為每個進(jìn)程建立一張段映射表，簡稱“段表”。每個段在表中占有一個表項(xiàng)。

段表結(jié)構(gòu)：段號；段在內(nèi)存中的起始地址(基址)；段長。

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

在系統(tǒng)中設(shè)置段表寄存器，用于存放段表始址和段表長度，以實(shí)現(xiàn)從進(jìn)程的邏輯地址到物理地址的變換。

有了上面分頁的基礎(chǔ)，這個也就沒什么可講的了，唯一要注意的是，有兩項(xiàng)檢測：

1. 判斷段號是否越界
2. 判斷段內(nèi)地址是否超過段長

當(dāng)然還有具有 快表 的地址變換機(jī)構(gòu)，這里就不做介紹了，和分頁雷同！?

6.4 分段、分頁的對比

相似點(diǎn)：

1. 采用離散分配方式，通過地址映射機(jī)構(gòu)實(shí)現(xiàn)地址變換

不同點(diǎn)：（已經(jīng)盡量幫大家精煉了，這樣好記好寫）

1. 頁是信息的物理單位，分頁對用戶不可見；段是信息的邏輯單位，分段對用戶可見
2. 頁的大小固定且由系統(tǒng)確定；段的長度不固定，取決于用戶程序
3. 分頁的作業(yè)地址空間是一維的；分段的作業(yè)地址空間是二維的
4. 分段比分頁更容易實(shí)現(xiàn)信息的共享和保護(hù)

對于上述不同點(diǎn)，有些可能對同學(xué)來說很難理解，因此有必要解釋一下：

【1】對于不同點(diǎn)1，分頁僅僅是系統(tǒng)管理上的需要，完全是系統(tǒng)行為，用戶不可見；而分段主要滿足用戶需求，用戶編程時需要顯式地給出段名（比如某個子函數(shù)名）

【2】對于不同點(diǎn)3，通過分頁來確定物理地址，我們只需要知道邏輯地址就可以，因?yàn)轫撁娲笮∈枪潭ǖ模ㄍㄟ^整除和取余可以得到頁號和頁內(nèi)偏移量），所以分頁是一維的；而通過分段確定地址時，只給出邏輯地址沒有辦法通過整除和取余可以得到頁號和頁內(nèi)偏移量（因?yàn)槎未笮〔煌枰绦騿T顯示給出段名和段內(nèi)地址。

【3】對于不同點(diǎn)4，

• 分段比分頁更容易共享：分頁實(shí)現(xiàn)共享肯定很困難，因?yàn)槟悴荒鼙ＷC一個頁里面只有非臨界資源，因?yàn)槠浯笮」潭?，所以不像段那么靈活。
• 分段比分頁更容易實(shí)現(xiàn)信息的保護(hù)：和上面的理由一樣，分頁大小固定，可能這個頁面既包含一點(diǎn)臨界資源，也包含一點(diǎn)非臨界資源，這是不能允許的。
• 補(bǔ)充：可重入代碼又稱為純代碼，是一種允許多個進(jìn)程同時訪問的代碼（共享），可重入代碼不允許任何進(jìn)程對它進(jìn)行修改（記著就行，應(yīng)付填空題）。

七、段頁式管理方式

分段和分頁存儲管理方式各有優(yōu)缺點(diǎn)。

把兩者結(jié)合成一種新的存儲管理方式——段頁式存儲管理方式，具有兩者的長處。

基本原理：先將用戶程序分成若干段，并為每個段賦予一個段名，再把每個段分成若干頁。

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

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

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

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

對應(yīng)關(guān)系如下
?

?一句話總結(jié)：一個進(jìn)程分為多個段 ，一個段對應(yīng)一個頁表， 一個進(jìn)程就對應(yīng)多個頁表。

再來介紹下它的段表和頁表：就拿上述0號段為例子

每個段對應(yīng)一個段表項(xiàng)，每個段表項(xiàng)由段號、頁表長度、頁表存放塊號(頁表起始地址)組成。每個段表項(xiàng)長度相等，段號是隱含的。

每個頁面對應(yīng)一個頁表項(xiàng)，每個頁表項(xiàng)由頁號、頁面存放的內(nèi)存塊號組成。每個頁表項(xiàng)長度相等，頁號是隱含的。

地址變換機(jī)構(gòu)如下：

看圖就能很輕松理解。

在段頁式系統(tǒng)中，為了獲得一條指令或數(shù)據(jù)，需訪問三次內(nèi)存：

第一次：訪問內(nèi)存中的段表，取得頁表始址（頁表存放塊號）

第二次：訪問內(nèi)存中的頁表，取得該頁所在的物理塊號，將塊號與頁內(nèi)地址形成物理地址

第三次：訪問第二次所得的地址，取出指令或數(shù)據(jù)

當(dāng)然也可引入快表（如果命中，則只需要一次訪存）。

格外的課后知識：

現(xiàn)代操作系統(tǒng)主要采用分頁存儲，段（頁）式存儲已經(jīng)基本見不到，因?yàn)槎问酱鎯Φ膬?yōu)點(diǎn)幾乎沒有體現(xiàn)了，現(xiàn)在沒有人在編程的時候還考慮程序分段。并且段頁式也會增加系統(tǒng)的復(fù)雜度。當(dāng)然也有段的思想在里面，但是現(xiàn)代操作系統(tǒng)通過巧妙的設(shè)置，已經(jīng)“ 屏蔽 ”了段的存在。

當(dāng)然這也不在本章的探討范圍內(nèi)，并且博主實(shí)力也有限，不能做更多詳細(xì)解釋，就當(dāng)做一個課外知識吧！

八、結(jié)尾

最后，非常感謝大家的閱讀。我接下來還會更新第五章：【虛擬存儲器】 ，如果本文有錯誤或者不足的地方請?jiān)谠u論區(qū)(或者私信)留言，一定盡量滿足大家，如果對大家有幫助，還望三連一下啦！

我的個人博客，歡迎訪問 !

Reference

【1】?湯子瀛, 哲鳳屏, 湯小丹，梁紅兵. 計(jì)算機(jī)操作系統(tǒng)[第四版]. 西安電子科技大學(xué)出版社

【2】王道計(jì)算機(jī)考研 操作系統(tǒng)_嗶哩嗶哩_bilibili文章來源地址http://www.zghlxwxcb.cn/news/detail-859515.html

到了這里，關(guān)于【操作系統(tǒng)復(fù)習(xí)之路】存儲器管理（第四章 &超詳細(xì)講解）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！