雖然內(nèi)存容量在不斷增長，但仍然不可能將所有用戶進(jìn)程和系統(tǒng)所需要的全部程序和數(shù)據(jù)放入主存中，因此操作系統(tǒng)必須將內(nèi)存空間進(jìn)行合理的劃分和有效的動態(tài)分配。
內(nèi)存管理包括：內(nèi)存的分配與回收，地址轉(zhuǎn)換，邏輯地址轉(zhuǎn)換成物理地址，利用虛擬存儲技術(shù)擴(kuò)充內(nèi)存等

內(nèi)容大綱

• 1、程序裝入和鏈接
• 2、連續(xù)分配管理方式
• 3、非連續(xù)分配管理方式
• 4、虛擬內(nèi)存管理

1 程序裝入和鏈接

(1)用戶程序的處理步驟

在多道程序環(huán)境下，要使程序運(yùn)行，必須創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程就要將程序和數(shù)據(jù)裝入內(nèi)存。一個用戶源程序要變?yōu)樵趦?nèi)存中可執(zhí)行的程序，通常要進(jìn)行以下處理：

• 編譯：由編譯程序?qū)⒂脩粼闯绦蚓幾g成若干個目標(biāo)模塊。
• 鏈接：由鏈接程序?qū)⒛繕?biāo)模塊和相應(yīng)的庫函數(shù)鏈接成裝入模塊。
• 裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存。

(2) 程序的鏈接

靜態(tài)鏈接方式—是一種事先鏈接方式，即在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫函數(shù)，鏈接成一個完整的裝入模塊(執(zhí)行文件)，以后不再拆開。
缺點(diǎn)：不便于對目標(biāo)模塊的修改和更新；無法實現(xiàn)對目標(biāo)模塊的共享。

image.png

裝入時動態(tài)鏈接方式— 指將一組目標(biāo)模塊在裝入內(nèi)存時，邊裝入邊鏈接的方式。
運(yùn)行時動態(tài)鏈接方式— 在程序運(yùn)行中需要某些目標(biāo)模塊時，才對它們進(jìn)行鏈接的方式。具有高效且節(jié)省內(nèi)存空間的優(yōu)點(diǎn)。便于實現(xiàn)對目標(biāo)木塊的共享、便于修改和更新。

(3) 程序的裝入

絕對裝入—編譯時根據(jù)目標(biāo)程序?qū)Ⅰv留在內(nèi)存中的某個位置，從而將產(chǎn)生絕對地址的目標(biāo)代碼。目標(biāo)代碼根據(jù)程序中的地址放入對應(yīng)的內(nèi)存中。此時邏輯地址和物理地址相同，絕對裝入指適用于單道程序環(huán)境。
可重定位裝入—多個程序的起始地址都從0開始，程序中的其他地址都是相對于起始地址的。裝入時將目標(biāo)程序中的指令和數(shù)據(jù)的相對地址轉(zhuǎn)換成裝入位置的物理地址，該過程成為重定位。這種地址變換是裝入時一次完成的，稱為靜態(tài)重定位。
動態(tài)運(yùn)行時裝入—程序裝入內(nèi)存時，不立即把相對地址轉(zhuǎn)換成絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行。故裝入內(nèi)存后的所有地址均為相對地址。

image.png

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

通常將主存劃分成兩個分區(qū):

• 低地址分區(qū)用于駐留操作系統(tǒng)，以及中斷向量。
• 用戶進(jìn)程駐留在高地址分區(qū)。

系統(tǒng)為程序分配的內(nèi)存都是一個連續(xù)的地址空間。又分為：單一連續(xù)分配，固定分區(qū)分配和動態(tài)分區(qū)分配。

(1) 單一連續(xù)分配

最簡單的一種存儲管理方式，但只能用于單用戶、單任務(wù)的OS中。

• 存儲管理方法：將內(nèi)存分為系統(tǒng)區(qū)（內(nèi)存低端，分配給OS用）和用戶區(qū)（內(nèi)存高端，分配給用戶用）。采用靜態(tài)分配方式，即作業(yè)一旦進(jìn)入內(nèi)存，就要等待它運(yùn)行結(jié)束后才能釋放內(nèi)存。
• 主要特點(diǎn)：管理簡單，只需小量的軟件和硬件支持，便于用戶了解和使用。但因內(nèi)存中只裝入一道作業(yè)運(yùn)行，內(nèi)存空間浪費(fèi)大，各類資源的利用率也不高。

(2) 固定分區(qū)分配

是最早使用的一種可運(yùn)行多道程序的存儲管理方法。

• 內(nèi)存空間的劃分：將內(nèi)存空間劃分為若干個固定大小的分區(qū)，每個分區(qū)可裝入一道用戶進(jìn)程。分區(qū)的大小可以相等，也可以不等，但事先必須確定，在運(yùn)行時不能改變。即分區(qū)大小及邊界在運(yùn)行時不能改變。
• 系統(tǒng)需建立一張分區(qū)說明表或使用表，以記錄分區(qū)號、分區(qū)大小、分區(qū)的起始地址及狀態(tài)（已分配或未分配）。

image.png

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

不事先將內(nèi)存劃分成一塊塊的分區(qū)，而是在作業(yè)進(jìn)入內(nèi)存時，根據(jù)作業(yè)的大小動態(tài)地建立分區(qū)，并使分區(qū)的大小正好適應(yīng)作業(yè)的需要。因此系統(tǒng)中分區(qū)的大小是可變的，分區(qū)的數(shù)目也是可變的。

image.png

• 動態(tài)分區(qū)最開始分配時是很好的，但是之后會導(dǎo)致內(nèi)存中出現(xiàn)很多小的內(nèi)存塊。稱為外部碎片。
• 孔/空閑區(qū)（Hole） – 可用內(nèi)存塊；內(nèi)存中遍布不同大小的空閑區(qū)。
• 當(dāng)進(jìn)程進(jìn)入系統(tǒng)時，就為其尋找足夠大的空閑區(qū)。
• 操作系統(tǒng)需要維護(hù)的信息包括：?a) 已分配分區(qū)（表） b) 自由分區(qū) (hole)

按照一定的分配算法從空閑分區(qū)中選出一個滿足作業(yè)需求的分區(qū)分配給作業(yè)，如果這個空閑分區(qū)的容量比作業(yè)申請的空間要大，則將該分區(qū)一分為二，一部分分配給作業(yè)，剩下的部分仍然留在空閑分區(qū)表（鏈）中，同時修改空閑分區(qū)表（鏈）中相應(yīng)的信息。目前常用分配算法有：

• 首次適應(yīng)算法
• 最佳適應(yīng)算法
• 最大適應(yīng)算法
• 鄰近適應(yīng)算法

首次適應(yīng)算法

• 將空閑分區(qū)（塊）按地址遞增的順序排列，每次分配內(nèi)存時，總是從空閑分區(qū)表（鏈）首開始順序查找，直到找到第一個滿足其大小要求的空閑分區(qū)為止。然后再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑分區(qū)表（鏈）中。
• 優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū),從而保留了高地址部分的大空閑區(qū)。但由于低地址部分不斷被劃分,致使低地址端留下許多難以利用的很小的空閑分區(qū)(碎片或零頭),而每次查找又都是從低地址部分開始,這無疑增加了查找可用空閑分區(qū)的開銷。

最佳適應(yīng)算法

空閑分區(qū)表/鏈按容量大小遞增的次序排列。在進(jìn)行內(nèi)存分配時，從空閑分區(qū)表/鏈的首開始順序查找，直到找到第一個滿足其大小要求的空閑分區(qū)為止。
按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。如果該空閑分區(qū)大于作業(yè)的大小，則與首次適應(yīng)算法相同，將剩余空閑分區(qū)仍留在空閑分區(qū)表/鏈中。

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

(1) 引入原因

在連續(xù)分區(qū)存儲管理中，要求把進(jìn)程放在一個連續(xù)的存儲區(qū)中，因而會產(chǎn)生許多碎片。解決方法代價高。
允許將作業(yè)/進(jìn)程離散放到多個不相鄰接的分區(qū)中，就可以避免拼接?；谶@一思想產(chǎn)生了以下的離散分配方式：

• 分頁存儲管理
• 分段存儲管理
• 段頁式存儲管理

(2)分頁存儲管理-基本概念

• 進(jìn)程物理地址空間可以不連續(xù)；
• 將內(nèi)存物理空間劃分成固定大小的塊 (大小通常為2的若干次冪，如 512B，4096B)，稱為頁框。
• 將邏輯空間分成與物理塊同樣大小的頁（pages）。
• 系統(tǒng)建立一張空閑頁框表，用以維護(hù)系統(tǒng)中的自由空間。
• 當(dāng)需要執(zhí)行一個大小為 n 頁的進(jìn)程時，就在內(nèi)存中尋找 n 自由頁框，并將進(jìn)程裝入其中。
• 為進(jìn)程設(shè)置一張頁表，記錄頁編號和頁框編號的對應(yīng)關(guān)系。實現(xiàn)邏輯地址向物理地址的轉(zhuǎn)換。

頁表

image.png

地址結(jié)構(gòu)及頁表

CPU生成的邏輯地址被自動分成:

• 頁號 (p) – 用作訪問頁表的索引，頁表內(nèi)保存每頁在內(nèi)存中的物理地址（塊號）
• 頁內(nèi)偏移量 (w) – 與物理塊號一同構(gòu)成實際的內(nèi)存物理地址。
  
  image.png

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

為了能將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址，在系統(tǒng)中必須設(shè)置地址變換機(jī)構(gòu)。
地址變換結(jié)構(gòu)的基本任務(wù)為：實現(xiàn)邏輯地址向物理地址的轉(zhuǎn)換（頁號->頁框號）。地址變換借助頁表來完成。

image.png

存在的問題

• 采用純分頁內(nèi)存分配方式， CPU每存取一個指令/數(shù)據(jù)時，需要兩次訪問內(nèi)存，一次訪問頁表，一次物理地址存取數(shù)據(jù)。
• 引入一種能快速搜索的高速緩沖存儲器--快表。
• 快表：一種特殊高速緩沖存儲器；內(nèi)容--為頁表中的一部分或全部。
• CPU產(chǎn)生的邏輯地址的頁首先在快表中尋找，若找到（命中），就找出其對應(yīng)的物理塊；若未找到（未命中），再到頁表中找其對應(yīng)的物理塊，并將之復(fù)制到快表。
• 若快表中內(nèi)容滿，則按某種算法淘汰某些頁。

快表

有些處理器設(shè)計為快表和主存同時查找，如果快表命中，則主存查找終止。
一般塊表的命中率達(dá)90%以上。

image.png

(3)段式存儲管理

• 引入分段存儲管理方式， 主要是為了滿足用戶和程序員。
• 程序是程序段的集合：程序段可以是：main program, procedure/ method, object等。因此進(jìn)程地址形成了一個二維空間，段名和段內(nèi)偏移量。
• 分段的優(yōu)點(diǎn)：
  （1）方便編程：按邏輯關(guān)系分為若干個段，每個段從0編址，并有名字和長度，訪問的邏輯地址由段名和段內(nèi)偏移量決定。
  （2）信息共享和保護(hù)：共享和保護(hù)是以信息為邏輯單位，頁是存儲信息的物理單位，段卻是信息的邏輯單位。
  （3）動態(tài)增長：實際應(yīng)用中，某些段（數(shù)據(jù)段）會不斷增長，前面的存儲管理方法均難以實現(xiàn)。

地址結(jié)構(gòu)及段表

每個進(jìn)程都有一張邏輯空間與主存空間映射的段表。
段表項記錄該段在主存中的起始地址和段的長度。

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

為了能將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址，在系統(tǒng)中必須設(shè)置地址變換機(jī)構(gòu)。

image.png

(4)段頁式存儲管理

段頁式存儲管理是分段和分頁原理的結(jié)合，即先將用戶程序分成若干個段（段式），并為每一個段賦一個段名，再把每個段分成若干個頁（頁式）。其地址結(jié)構(gòu)由段號、段內(nèi)頁號、及頁內(nèi)位移三部分所組成。

image.png

地址映射

image.png

4 虛擬內(nèi)存管理

(1)基本概念

• 傳統(tǒng)存儲管理方式的特征：一次性（ 作業(yè)一次性全部裝入內(nèi)存后，才能運(yùn)行。作業(yè)很大，作業(yè)很多？）；駐留性（運(yùn)行完之前，作業(yè)任何部分都不能換出）。
• Bill Joy（sun CEO）說：“在研究所時，我經(jīng)常開玩笑說高速緩存是計算機(jī)科學(xué)中唯一重要的思想?！?廣義來說，快表、頁高速緩存、虛擬內(nèi)存技術(shù)都屬于高速緩存技術(shù)。
• 高速緩存技術(shù)都依賴于局部性原理。時間局限性。如果程序中的某條指令一旦執(zhí)行， 則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過， 則不久以后該數(shù)據(jù)可能再次被訪問。空間局限性。一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問。

基于局部性原理，程序在運(yùn)行之前，沒有必要全部裝入內(nèi)存，僅須將當(dāng)前要運(yùn)行的頁（段）裝入內(nèi)存即可。
運(yùn)行時，如訪問的頁（段）在內(nèi)存中，則繼續(xù)執(zhí)行，如訪問的頁未在內(nèi)存中（缺頁或缺段），則利用OS的請求調(diào)頁（段）功能，將該頁（段）調(diào)入內(nèi)存。
如內(nèi)存已滿，則利用OS的頁（段）置換功能，按某種置換算法將內(nèi)存中的某頁（段）調(diào)至外存，從而調(diào)入需訪問的頁。
虛擬存儲的實現(xiàn)技術(shù)：

• 請求分頁（Demand paging）
• 請求分段（Demand segmentation）

虛擬存儲器是指僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行作業(yè)的存儲管理系統(tǒng)，它具有請求調(diào)入功能和部分置換功能，能從邏輯上對內(nèi)存容量進(jìn)行擴(kuò)充，其邏輯容量由外存容量和內(nèi)存容量之和決定，其運(yùn)行速度接近于內(nèi)存，成本接近于外存。

(2)請求分頁管理

分頁請求系統(tǒng)—在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁面置換功能所形成的頁式虛擬存儲器系統(tǒng)。允許只裝入若干頁的用戶程序和數(shù)據(jù)，便可啟動運(yùn)行，以后在硬件支持下通過調(diào)頁功能和置換頁功能，陸續(xù)將要運(yùn)行的頁面調(diào)入內(nèi)存，同時把暫不運(yùn)行的頁面換到外存上，置換時以頁面為單位。
系統(tǒng)須設(shè)置相應(yīng)的硬件支持和軟件：
硬件支持：請求分頁的頁表機(jī)制、缺頁中斷機(jī)構(gòu)和地址變換機(jī)構(gòu)。
軟件：請求調(diào)頁功能和頁置換功能的軟件。

請求分頁的頁表機(jī)制

image.png

缺頁中斷機(jī)構(gòu)

在請求分頁系統(tǒng)中，當(dāng)訪問的頁不在內(nèi)存，便產(chǎn)生一缺頁中斷，請求OS將所缺頁調(diào)入內(nèi)存空閑塊，若無空閑塊，則需置換某一頁，同時修改相應(yīng)頁表表目。
缺頁中斷與一般中斷的區(qū)別：
（1）在指令執(zhí)行期間產(chǎn)生和處理中斷信號
（2）一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷

image.png

image.png

頁面置換算法

實施頁面置換 – 按照某種策略從內(nèi)存中尋找某頁，將其換出，以騰出空間裝入請求頁面。
希望得到一個算法，能保證系統(tǒng)的缺頁率最低。
剛被淘汰出內(nèi)存的頁面，過后不久又要訪問它，需要再次將其調(diào)入，而該頁調(diào)入內(nèi)存后不入又再次被淘汰出內(nèi)存，然后又要訪問它，如此反復(fù)，使得系統(tǒng)把大部分時間用在了頁面的調(diào)進(jìn)換出上，而幾乎不能完成任何有效的工作，這種現(xiàn)象稱為抖動（又稱顛簸）。
利用修改位 （modify /dirty bit ）降低頁面?zhèn)鬏旈_銷 – 只需把發(fā)生修改的頁面寫回磁盤。

常用的頁面置換算法：
最佳置換算法：選擇永遠(yuǎn)不再需要的頁面或最長時間以后才需要訪問的頁面予以淘汰。
先進(jìn)先出置換算法：選擇先進(jìn)入內(nèi)存的頁面予以淘汰。
最近最久未使用置換算法LRU：選擇最近一段時間最長時間沒有被訪問過的頁面予以淘汰。

最佳置換

選擇被淘汰的頁面是以后永不使用，或是在最長時間內(nèi)不再被訪問的頁面，從而得到最低的缺頁率。
例如：系統(tǒng)為某進(jìn)程分配了三個物理塊，若有下列頁面號引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

image.png

先進(jìn)先出

算法總是淘汰最先調(diào)入主存的那一頁，或者說在主存中駐留時間最長的那一頁（常駐的除外）。

image.png

LRU算法

算法思想：如果某個頁面被訪問了，則它可能馬上還要訪問。反之，如果很長時間未被訪問，則它在最近一段時間也不會被訪問。

image.png

LRU的性能接近于最佳算法，但實現(xiàn)起來較困難。因為要找出最近最久未使用的頁面，必須為每一頁設(shè)置相關(guān)記錄項，用于記錄頁面的訪問情況，并且每訪問一次頁面都須更新該信息。這將使系統(tǒng)的開銷加大，所以在實際系統(tǒng)中往往使用該算法的近似算法。