操作系統入門 -- 內存管理

操作系統入門 – 內存管理

1.內存種類

1.1 虛擬內存（VIRT）

進程需要的虛擬內存大小，包括進程使用的庫、代碼、數據以及malloc、new分配的堆空間和棧空間等。
若進程申請了10MB內存但實際使用了1MB，則物理空間會增長10MB。

1.2 常駐內存（RES）

進程當前使用的內存大小，包括使用中的malloc、new分配的堆空間和棧空間，不包括sawp out量。其中還包含其他進程的共享。
若申請10MB則實際使用1MB

1.3 共享內存（SHR）

除了自身進程的共享內存，也包括其他進程的共享內存。
進程只使用了幾個共享庫的函數，但包含了整個共享庫大小。
計算某個進程所占物理內存大小為RES - SHR.
swap后會降下來。

2.操作系統內存管理

2.1 內存管理的意義

目前計算機硬件發展很快，內存容量也越來越大。但是仍然不可能將所有用戶進程和系統所需要的全部程序和數據放入主存中，所以操作系統必須將內存空間進行合理地劃分和有效地動態分配。操作系統對內存的劃分和動態分配，就是內存管理的概念。

2.2 內存管理的內容

操作系統中內存管理主要負責內存分配與回收（malloc：申請內存， free：釋放內存），同時將邏輯地址映射到物理空間也是內存管理的內容。其中主要有以下四個功能：

內存空間分配與回收：由操作系統完成主存儲器空間的分配和管理，使程序員擺脫存儲分配的麻煩，提高編程效率。
地址轉換：在多道程序環境下，程序中的邏輯地址與內存中的物理地址不可能一致，因此存儲管理必須提供地址變換功能，把邏輯地址轉換成相應的物理地址。
內存空間擴充：利用虛擬存儲技術或自動覆蓋技術，從邏輯上擴充內存。
存儲保護：保證各道作業在各自的存儲空間內運行，.互不干擾。

2.3 內存管理目的

提高內存利用率。所謂提高利用率就是盡可能讓更多進程沾滿內存。進程在內存中的分布又可以分為連續和非連續。

2.4 程序裝入與鏈接

2.4.1 程序裝入過程

創建進程首先要將程序和數據裝入內存。將用戶源程序變為能在內存中執行的程序需要以下步驟：

編譯：由編譯程序將用戶源代碼編譯為若干個 目標模塊。
鏈接：由鏈接程序將編譯后形成的一組目標模塊，以及所需庫函數鏈接在一起，形成一個完整的 裝入模塊。
裝入：由裝入程序將模塊裝入內存運行。

2.4.2 程序鏈接

靜態鏈接：在程序運行之前，先將各個目標模塊及所需函數庫鏈接成一個完整的可執行程序，以后不再拆開。
裝入時動態鏈接：將用戶源程序編譯后所得到的一組目標模塊，在裝入內存時，采用變裝入邊鏈接的方式。
運行時動態鏈接：對某些目標模塊的連接，是在程序執行中需要該目標模塊時，才對其進行鏈接。優點在于便于修改和更新，便于實現對目標模塊的共享。

2.5 地址映射

程序在編譯后，每個目標模塊都是從0號單元開始編址，稱為該目標模塊的相對地址（邏輯地址）。當鏈接程序將各個模塊鏈接為一個完整可執行的目標程序時，鏈接程序順序依次按各個模塊的相對地址構成統一的從0號單元開始編址的邏輯地址空間。簡單來說就是該條鏈接是從0號開始順序往下編址。

物理地址空間是指內存中物理單元的集合，它是地址轉換后的最終結果。進程在運行時執行指令和訪問數據最后都需要通過物理地址從主存中存取。當裝入程序將可執行代碼裝入內存中時，必須通過地址轉換將邏輯地址轉換為物理地址。

2.5 內存保護

內存在分配前，需要保護操作系統進程不受影響，同時保護用戶進程不受其他用戶進程影響。采用重定位寄存器和界地址寄存器來實現這種保護。重定位寄存器含有最小的物理地址值，界地址寄存器含邏輯地址值。每個邏輯地址值必須小于界地址寄存器。內存管理機構動態地將邏輯地址與界地址寄存器比較，若未發生越界，則加上重定位寄存器的值后映射為物理地址，最后送交內存單元。

3.內存覆蓋與交換

3.1 內存覆蓋

3.1.1 問題產生

早期計算機內存空間較小，且其中需要存放一道用戶程序，但由于內存空間有時連用戶進程都放不下，因此采用覆蓋來解決。

3.1.2 實現過程

程序運行時不是任何時候都要訪問程序和數據的各個部分，因此可以把用戶空間分為一個固定區域和若干覆蓋區域。將經常活躍的部分放在固定區，其余部分按調用關系分段。首先把將要方位的段放入覆蓋區，其余部分放入外存，在需要調用前載入覆蓋區替換原來的數據。

3.2 內存交換

3.2.1 實現過程

交換是把等待狀態下的進程從內存中換出至外存，騰出內存空間，把就緒的進程從外存換入內存中準備執行。

3.2.2 注意事項

交換需要備份存儲，需要磁盤空間足夠大，并提供對內存映像的直接訪問。
為有效使用CPU，需要每個進程的執行時間比較長，影響交換時間的是轉移時間。轉移時間與所交換的內存空間成正比
換出進程必須確保該進程完全處于空閑狀態。
交換的空間通常為磁盤上一整塊區域，且獨立于文件系統。
內存交換一般發生于內存空間不足的時候，當內存負荷降低后暫停。

3.3 總結

交換主要是不同進程之間，而覆蓋則是在同一程序或進程中。目前操作系統主流采用內存交換技術。

4.內存分配

4.1 內存連續分配

連續分配方式，是指為一個用戶程序分配一個連續的內存空間。它主要包括單一連續分配、固定分區分配和動態分區分配。

4.1.1 單一連續分配

內存在該分配模式下分為系統區和用戶區，系統區為操作系統提供使用，通常為低地址部分、用戶區為除系統區外的內存空間。

優點：簡單、無外部碎片、可以采用覆蓋技術，無需額外技術支持。
缺點：只能用于單用戶、單任務的操作系統，內部有碎片，存儲利用率低。

4.1.2 固定分區分配

固定分區分配是最簡單的一種多道程序存儲管理方式，它將用戶內存空間劃分為若干個固定大小的區域，每個分區只裝入一道作業。當存在空閑分區時，便可以再從外存的后備作業隊列中選擇適當大小的作業裝入該分區。

分區方式
- 分區大小相等：用于一臺計算機控制多個相同對象的場合，缺乏靈活性。
- 分區大小不等：劃分為含多個較小的分區、適量的中等分區及少量大分區
  但這種存儲方式存在以下問題：
- 程序可能太大而無法放進任一分區，此時只能使用覆蓋技術
- 主存利用率低，當程序體積小于固定分區大小時，放進去也需要占用這一分區，造成浪費。

4.1.3 動態分區分配

動態分區分配不會先劃分內存，而是在進程裝入內存時動態分配空間，分區大小和數量是可變的。動態分區剛開始沒有什么問題但之后會出現許多小內存塊，隨著內存塊增多，利用率下降。

如果內存空間足夠大，則操作系統必須明確分配哪個內存給進程使用，即動態分區分配策略，其算法如下：

首次適應算法：空閑分區以地址遞增的次序鏈接。分配內存時順序查找，找到第一個能滿足大小的分區。
最佳適應算法：空閑分區安容量遞增形成分區鏈。找到第一個能滿足大小的分區。
最壞適應算法：空閑分區按容量遞減次序鏈接。找到第一個能滿足要求的空閑分區。
鄰近適應算法：由首次適應算法演變。不同之處是分配內存時從上次查找結束的位置開始繼續查找。

4.2 內存非連續分配

非連續分配允許一個程序分散地裝入不相鄰的內存分區中，根據分區的大小是否固定分為分頁存儲管理方式和分段存儲管理方式。

4.2.1 基本分頁存儲管理方式

分頁是將主存空間劃分為大小相等且固定的塊，塊相對較小，作為主存的基本單位。每個進程也以塊為單位進行劃分，進程在執行時，以塊為單位逐個申請主存中的塊空間。分頁本身不會產生外部碎片，但是塊的大小相對分區要小很多，且進程也按照塊進行劃分，進程運行按塊申請內存。因此進程只會在為最后一個不完整的塊申請一個主存儲塊時才會產生碎片。

4.2.2 分頁存儲的基本概念

頁面和頁面大小：進程中的塊稱為頁，內存中的塊稱為頁框。外存也以同樣方式劃分，稱為塊。進程執行時申請內存空間，即為每個頁面分配頁框。
頁面大小：為方便地址轉換，頁面大小應是2的整數冪。頁面大小適中，若頁面過小則進程頁面數過多，頁表會過長，占用大量內存。頁面過大則頁內碎片增多，降低利用率。
地址結構：由兩部分組成，前一部分為頁號P，后一部分為頁內偏移量W，地址長度為32 位，其中0_{11位為頁內地址，即每頁大小為4KB；12}31位為頁號，地址空間最多允許有2²⁰頁。
頁表：為了便于在內存中找到進程的每個頁面所對應的物理塊，系統為每個進程建立一張頁表，記錄頁面在內存中對應的物理塊號，頁表一般存放在內存中。

4.2.3 基本地址變換機構

地址變換機構的任務是將邏輯地址轉為內存中的物理地址，該機構通過頁表實現。

alt text

4.2.4 基于快表的地址變換機構

若頁表全部放在內存中，則存取一個數據或一條指令至少要訪問兩次內存，因此在地址變換機構中增加一個高速緩沖器即快表來存放當前訪問的若干頁表項，以加速地址變換的過程。
alt text

4.2.4 多級頁表

于引入了分頁管理，進程在執行時不需要將所有頁調入內存頁框中，而只要將保存有映射關系的頁表調入內存中即可。但是我們仍然需要考慮頁表的大小。
以32 位邏輯地址空間、頁面大小4KB、頁表項大小4B為例，若要實現進程對全部邏輯地址空間的映射，則每個進程需要2²⁰，約100萬個頁表項。也就是說，每個進程僅頁表這一項就需要4MB主存空間，這顯然是不切實際的。而即便不考慮對全部邏輯地址空間進行映射的情況，一個邏輯地址空間稍大的進程，其頁表大小也可能是過大的。
alt text