操作系統精髓與設計原理讀書筆記7內存管理，虛擬內存

內存管理

基本概念

物理內存管理

夥伴系統

基本內存管理方案

交換技術（Swapping）

程序裝載到內存才可以運行

通常，程序以可執行文件格式保存在磁碟上

多道程序設計模型

允許多個程序同時進入內存

每個進程有自己的地址空間

一個進程執行時不能訪問另一個進程的地址空間

進程不能執行不適合的操作

地址重定位

邏輯地址（相對地址，虛擬地址）

用戶程序經過編譯、彙編後形成目標代碼，目標代碼通常採用相對地址的形式，其首地址為0，其餘地址都相對於首地址而編址，不能用邏輯地址在內存中讀取信息

物理地址（絕對地址，實地址）

內存中存儲單元的地址 可直接定址

為了保證CPU執行指令時可正確訪問內存單元，需要將用戶程序中的邏輯地址轉換為運行時可由機器直接定址的物理地址，這一過程稱為地址重定位

靜態重定位：

當用戶程序載入到內存時，一次性實現邏輯地址到物理地址的轉換 一般可以由軟體完成

動態重定位：

在進程執行過程中進行地址變換 → → 即逐條指令執行時完成地址轉換 需要硬體部件支持

空閑內存管理：

數據結構

點陣圖

每個分配單元對應於點陣圖中的一位，0表示空閑，1表示佔用（或者相反）

空閑區表、已分配區表

表中每一項記錄了空閑區（或已分配區）的起始地址、長度、標誌

空閑塊鏈表

內存分配演算法

首次適配 first fit

在空閑區表中找到第一個滿足進程要求的空閑區

下次適配 next fit

從上次找到的空閑區處接著查找

最佳適配 best fit

查找整個空閑區表，找到能夠滿足進程要求的最小空閑區

最差適配 worst fit

總是分配滿足進程要求的最大空閑區

夥伴系統

一種經典的內存分配方案

主要思想：將內存按2的冪進行劃分，組成若干空閑塊鏈表；查找該鏈表找到能滿足進程需求的最佳匹配塊

演算法：

首先將整個可用空間看作一塊： 2U

假設進程申請的空間大小為 s，如果滿足

2U-1 < s <= 2U，則分配整個塊

否則，將塊劃分為兩個大小相等的夥伴，大小為2U-1

一直劃分下去直到產生大於或等於 s 的最小塊

內存管理方案

1.單一連續區

頁式儲存管理方案

設計思想

用戶進程地址空間被劃分為大小相等的部分，稱為頁（page）或頁面，從0開始編號

內存空間按同樣大小劃分為大小相等的區域，稱為頁框（page frame），從0開始編號；也稱為物理頁面，頁幀，內存塊

內存分配（規則）

以頁為單位進行分配，並按進程需要的頁數來分配；邏輯上相鄰的頁，物理上不一定相鄰

典型頁面尺寸：4K 或 4M

段式儲存管理方案

設計思想

用戶進程地址空間：按程序自身的邏輯關係劃分為若干個程序段，每個程序段都有一個段名

內存空間被動態劃分為若干長度不相同的區域，稱為物理段，每個物理段由起始地址和長度確定

內存分配（規則）：以段為單位進行分配，每段在內存中佔據連續空間，但各段之間可以不相鄰

段表

每項記錄了段號、段首地址和段長度之間的關係

每個進程一個段表，存放在內存

段表起始地址保存在何處？

物理內存管理

地址轉換（硬體）

CPU取到邏輯地址，用段號查段表，得到該段在內存的起始地址，與段內偏移地址計算出物理地址

段頁式儲存管理方案

產生背景

綜合頁式、段式方案的優點，克服二者的缺點

設計思想

用戶進程劃分：先按段劃分，每一段再按頁面劃分

內存劃分：同頁式存儲管理方案

內存分配：以頁為單位進行分配

數據結構及有關操作

段表：記錄了每一段的頁表始址和頁表長度

頁表：記錄了邏輯頁號與頁框號的對應關係

每一段有一張頁表，一個進程有多個頁表

總結：

頁式

把用戶程序地址空間劃分成大小相等的部分，稱為頁。內存空間按頁的大小劃分為大小相等的區域，稱為內存塊（物理頁面，頁框，頁幀）。以頁為單位進行分配，邏輯上相鄰的頁，物理上不一定相鄰

段式

用戶程序地址空間按進程自身的邏輯關係劃分為若干段，內存空間被動態的劃分為若干個長度不相同的區域（可變分區）。以段為單位分配內存，每一段在內存中佔據連續空間，各段之間可以不連續存放

段頁式

用戶程序地址空間：段式；內存空間：頁式；分配單位：頁

如何解決在較小的內存空間運行較大的進程呢？

內存緊縮技術（例如：可變分區）

覆蓋技術 overlaying

交換技術 swapping

虛擬存儲技術 virtual memory

所謂虛擬存儲技術是指：當進程運行時，先將其一部分裝入內存，另一部分暫留在磁碟，當要執行的指令或訪問的數據不在內存時，由操作系統自動完成將它們從磁碟調入內存的工作

虛擬地址空間 即為 分配給進程的虛擬內存

虛擬地址 是 在虛擬內存中指令或數據的位置，該位置可以被訪問，彷彿它是內存的一部分

把內存與磁碟有機地結合起來使用，從而得到一個容量很大的「內存」，即虛存

虛存是對內存的抽象，構建在存儲體系之上，由操作系統協調各存儲器的使用

虛存提供了一個比物理內存空間大得多的地址空間

存儲保護

確保每個進程有獨立的地址空間

確保進程訪問合法的地址範圍

確保進程的操作是合法的

虛擬存儲技術 + 頁式存儲管理方案→ 虛擬頁式存儲管理系統

基本思想

進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面之後，根據進程運行的需要，動態裝入其他頁面當內存空間已滿，而又需要裝入新的頁面時，則根據某種演算法置換內存中的某個頁面，以便裝入新的頁面

頁表表項設計

頁表由頁表項組成

頁框號、有效位、訪問位、修改位、保護位

頁框號（內存塊號、物理頁面號、頁幀號）

有效位（駐留位、中斷位）：表示該頁是在內存還是在磁碟

訪問位：引用位

修改位：此頁在內存中是否被修改過

保護位：讀/可讀寫

如何加快地址映射速度，以改善系統性能？

程序訪問的局部性原理 → 引入快表(TLB)TLB — Translation Look-aside Buffers

在CPU中引入的高速緩存（Cache），可以匹配CPU的處理速率和內存的訪問速度

一種隨機存取型存儲器，除連線定址機制外，還有接線邏輯，能按特定的匹配標誌在一個存儲周期內對所有的字同時進行比較

頁面錯誤、頁故障、頁面失效

地址轉換過程中硬體產生的異常

具體原因

所訪問的虛擬頁面沒有調入物理內存

→ 缺頁異常

頁面訪問違反許可權（讀/寫、用戶/內核）

錯誤的訪問地址

駐留集

給每個進程分配多少頁框？

固定分配策略

進程創建時確定

可以根據進程類型（交互、批處理、應用類）或者基於程序員或系統管理員的需要來確定

可變分配策略

根據缺頁率評估進程局部性表現

缺頁率高→增加頁框數

缺頁率低→減少頁框數系統開銷

最佳演算法→先進先出→第二次機會→時鐘演算法→最近未使用→最近最少使用→最不經常使用→老化演算法→工作集→工作集時鐘

工作集演算法

基本思想：

根據程序的局部性原理，一般情況下，進程在一段時間內總是集中訪問一些頁面，這些頁面稱為活躍頁面，如果分配給一個進程的物理頁面數太少了，使該進程所需的活躍頁面不能全部裝入內存，則進程在運行過程中將頻繁發生中斷

如果能為進程提供與活躍頁面數相等的物理頁面數，則可減少缺頁中斷次數

工作集：一個進程當前正在使用的頁框集合

工作集W（t，Δ）

= 該進程在過去的Δ個虛擬時間單位中訪問到的頁面的集合

內容取決於三個因素：

訪頁序列特性

時刻t

工作集窗口長度(Δ)