文章目錄
- 前言
- 連續分配
- 單一連續分配
- 分區式分配
- 固定分區分配
- 動態分區分配
- 可重定位分區分配
- 離散分配
- 分段
- 分頁
- 多級頁表
- 快表(TLB)
- 段頁式
- Linux
前言
Linux 內存管理 | 虛擬內存管理：虛擬內存空間、虛擬內存分配
Linux 內存管理 | 物理內存、內存碎片、伙伴系統、SLAB分配器
在之前的兩篇博客中，分別介紹了虛擬內存與物理內存的管理方式，那么對于操作系統來說，它是如何管理它們兩個之間的關系的呢？如何進行地址的映射呢？
內存的分配方式有兩種：
-
連續分配： 每個進程分配一段地址空間連續的內存空間。
連續內存分配的方式有：- 單一連續分配
- 分區式分配
- 固定分區分配
- 動態分區分配
- 可重定位分區分配
-
離散分配： 允許將一個進程分散的分配到許多不相鄰的分區中，程序全部裝入內存。
現在用到的更多的是離散的分配方式，因此我們簡單介紹一下連續分配，再對離散分配加以詳解。
連續分配
單一連續分配
使用這種內存分配方式，內存空間會被分成 系統區 和 用戶區 兩部分，系統區僅提供給OS使用，系統區外的用戶區提供給用戶使用。
特點：
- 只適用于 單道程序 的情況。
- 若用戶作業比用戶區大，則無法運行
- 若用戶作業比用戶區小，則造成內存浪費
- 設置界限寄存器，限制用戶程序訪問操作系統
單道程序的特點：
- 資源獨占性： 任何時候，位于內存中的程序可以使用系統中的一切資源，不可能有其他程序與之競爭。
- 執行的順序性： 內存中只有一個程序，各個程序是按次序執行的。在做完一個程序的過程中，不可能夾雜進另一個程序執行。
- 結果的可再現性： 只要執行環境和初始條件相同，重復執行一個程序，獲得的結果總是一樣的。
- 運行結果的無關性： 程序的運行結果與程序執行的速度無關。系統中的作業以串行的方式被處理，CPU、內存的利用率低。
分區式分配
固定分區分配
固定分區分配是最簡單的一種可以運行在 多道程序 的存儲管理方式。
多道程序： 是指在計算機內存中同時存放幾道相互獨立的程序，使它們在管理程序控制下，相互穿插運行，兩個或兩個以上程序在計算機系統中同處于開始到結束之間的狀態, 這些程序共享計算機系統資源。當然，對于一個單CPU系統來說，程序同時處于運行狀態只是一種宏觀上的概念，他們雖然都已經開始運行，但就微觀而言，任意時刻，CPU上運行的程序只有一個。
基本原理：
- 將內存空間劃分為若干個固定大小的分區（大小可以不等）；
- 每個分區中只可以裝入一道作業；
- 當有空閑分區時，選擇一個適當大小的作業裝入該分區；
- 當作業結束時，釋放該分區。
缺點：
- 程序的大小受分區大小的限制；程序數受分區數限制；
- 每個分區都有可能產生 內部碎片，引起內存的浪費。
動態分區分配
基本思想：
- 作業要求裝入內存時，依照作業的大小劃分分區。
- 每個分區容納一個進程。
可變分區的管理與組織方式：
- 表格法：將內存按是否空心啊分別存在 空閑分區表 和 已分配分區表 中。管理簡單，但是需要占用一部分內存空間。
- 鏈表法：維護一個鏈首指針，每個空閑區在首地址記錄兩個數據：本空閑區的大小、下個空閑區的起始地址。
動態分區分配的內存回收方式： - 上鄰空閑區（F1）：合并，改大小
- 下鄰空閑區（F2）：合并，改大小，首址。
- 上、下鄰空閑區（F1、F2）：合并，改大小。
- 不鄰接，則建立一新表項。
動態分配分區內存分配算法：
- 首次適應算法： 將空閑分區按 地址順序 排列，進行內存分配時，從低地址開始順序查找，分配第一個足夠大的分區。
- 優點：優先分配低地址部分的空閑分區，保留高地址部分；
- 缺點： 在低址部分集中了許多小分區，難以利用。
- 循環首次適應算法： 首次適應算法的改進版本。將空閑分區按地址順序構成循環鏈表，進行內存分配時，不再從鏈首開始查找，而是從 上次找到的空閑分區的下一個空閑分區 開始查找，循環查找。
- 優點：內存中的空閑分區分布均勻，比起首次適應算法減少了查找空閑分區時的開銷；
- 缺點：缺乏大的空閑分區。
- 最佳適應算法： 空閑分區按大小 遞增排序 構成隊列，從隊列頭開始查找，當找到第一個滿足要求的空閑區時，則停止查找。
- 優點：找到的空閑分區最接近要求的大小；
- 缺點：會產生非常小的碎片，難以利用。
- 最差適應算法： 空閑分區按大小遞增排序構成隊列，查找最大的空閑區。與上面三個同屬 順序搜索法 。
- 優點：剩余的分區空間最大；
- 缺點：在空間利用率方面較差。
可重定位分區分配
假設現在有這樣一個情況，用戶內存空間中有幾個較小的空閑分區，但是現在有一個作業請求連續的內存空間，這幾個較小的空閑分區任何一個都不能單獨滿足請求空間的大小。 現在一種可行的辦法就是：移動內存，使所有空閑區域合并為一整塊空閑區域。
這種通過移動內存中的作業位置，將原來分散的小分區拼接成一個大分區的思想就是 緊湊 。 說的直白一點，可重定位分區分配就是 動態分區分配+緊湊 。
動態重定位的實現：
作業裝入內存后的所有地址都是相對地址，在程序將要執行的時候，才會將相對地址轉換為物理地址。為了不影響指令執行的速度，系統中增設了一個 重定位寄存器（即段寄存器、基址寄存器） ，用它來存放程序（數據）在內存中的起始地址。
程序真正執行時訪問的地址是 重定位寄存器中的地址+相對地址 。
離散分配
分段
為了簡化地址管理，所以將虛擬內存空間中的 虛擬內存 按照其邏輯劃分為代碼段、數據段、堆段、棧段幾部分。編譯、連接、加載過程都以段為單位。
段的特點：
- 虛擬內存空間是段的集合。
- 每個段都有其名稱和長度。
- 地址是由段名（段號）和段內偏移構成。
地址結構：
- 虛擬地址是二維的：
[段號，段內位移]。 - 32位地址結構中，
- 段號s：16位表示，216 個段
- 段內位移d：16位表示，每段最大長度是64KB。
通過 段寄存器 中的 段表 ，將虛擬地址與物理地址進行映射。段表由三部分組成：
- 段號：用于區別每個段。
- 段基址（segment base）：該段在物理內存中的首地址。
- 段長（segment limit ）：記錄該段的實際長度。
因此虛擬地址與物理地址的轉換方式如下：
- 根據虛擬地址中的段號查詢段表，得到對應的段的物理內存起始地址；
- 物理內存起始地址加上段內偏移，即為其對應的物理地址。
分段存儲方式解決了兩個問題 —— 地址空間不隔離 和 程序運行的地址無法確定。但還存在 內存使用效率低 的問題。內存使用效率低主要是因為兩個原因造成的：內存碎片 和 內存交換的效率低 。
內存碎片問題
例如我們有 1G 的物理內存，倘若我們運行了 512M 的程序A，接著運行了 128M 的程序B，128M 的程序C。剩余內存為 256M 。
倘若我們此時結束程序B，釋放內存，此時總剩余空間為 384M 。
倘若我們此時需要運行 300M 的進程D，但是這時候就會因為剩余空間不連續，導致我們的程序無法運行，這也就是我們常說的 內存外碎片 問題。
那么如何解決這個問題呢？這就會使用到類似于 緊湊 的思想。先將程序C寫入硬盤的 SWAP分區 (交換分區，用于內存和硬盤的空間交換)。緊接著再將其從硬盤中讀取回來，讓其緊挨著程序A的那塊內存，這樣就能保證后面的空閑內存都是連續的了。
內存交換效率低
由于分段對物理內存的映射是以 程序 為單位，按照其邏輯進行分段映射，如果我們的內存不足，那么被換入換出到硬盤中的都是整個程序，這樣就必然會造成大量的磁盤訪問操作，總所周知，磁盤IO的速度特別慢，因此就會嚴重影響我們的訪問速度。
而且，當一個程序在運行時，在某個時間段內，它只是 頻繁地用到了一小部分數據 ，也就是說程序中的很多數據其實在一個時間段內都是不會被用到的。因此我們將整個程序裝入內存其實是對內存的一種浪費。
分頁
總結一下，分段技術仍未解決的問題有：
- 雖然分段式存儲方式不畏懼 內存外碎片，但將內存中的數據暫時寫入到硬盤中，之后再重新寫回來這樣的換入換出操作在程序很大時是很廢時間的。值得一提的是，兩者都無法擺脫 內碎片 的桎梏。
- 而且分段需要將程序全部裝入內存，這就對程序的大小有了限制——不能超過剩余空閑內存的大小。
而分頁技術解決上述兩個問題的方法是：
- 使用頁為單位后，即使我們還是需要進行磁盤IO，但是由于我們交換的容量僅僅只有幾個頁，所以也不會花費過多的時間。
- 分頁技術下并不需要將程序整個裝入內存。在建立了虛擬內存空間后并不會直接分配物理內存，而是在程序運行中需要訪問物理內存的時候，再將其加載進內存中。所以如果在頁表中查找不到時，此時就會由內核的 請求分頁機制 產生 缺頁中斷 ，然后進入 內核態 中分配物理內存、更新進程頁表，最后再返回用戶態，恢復進程的運行。
基本概念：
- 幀/物理塊/頁框(frame)： 物理內存分為固定大小的塊。
- 頁(page)： 邏輯內存分為同樣大小的塊，在
Linux中，一頁是4KB。 - 頁表(page table)：
MMU(內存管理單元)中的頁面映射表，記錄了 頁 和 頁框 的映射關系。
頁表中不僅保存了頁號，物理內存地址，還保留了該物理頁的 訪問權限 ，用以實現對頁的訪問控制。
在分頁機制下，虛擬地址由 頁號 以及 頁內偏移 組成
因此在分頁機制下，虛擬地址與物理地址的轉換方式如下：
- 根據虛擬地址中的頁號查詢頁表，獲得對應的頁的物理內存起始地址；
- 物理內存起始地址加上頁內偏移，即為其對應的物理地址。
多級頁表
在上面所介紹的 頁表 有一個非常致命的缺點，就是空間占用大。
在 Linux 中，可以并發的執行多個進程，而每個進程都有其自己的虛擬內存空間，那么也自然都有自己獨有的頁表。在32位Linux系統下，我們的虛擬內存空間的大小為 4G ，而每頁的大小為 4K ，這也就意味著我們至少有 220 個內存頁，倘若每個頁表項為 4Byte ，那么每個頁表大小也至少為 4M 。
倘若我們此時并發了兩百個進程，那么占用則高達 800M ，即使對于如今的操作系統而言，這個數字也是非常龐大的，因為并發數百個進程是非常常見的情況，更別提64位的操作系統，隨著尋址范圍的增加，頁表將更為龐大。
為了解決這個問題，就引入了多級頁表。
我們將 一級頁表 再進行分頁，分成 1024 個 二級頁表 ，并且每個 二級頁表 中存有 1024 個頁表項，形成如下的 二級分頁 的結構。
對于已分配的頁表項，如果存在最近一定時間未訪問的頁表，在物理內存緊張的情況下，操作系統會將頁面換出到硬盤，也就是說不會占用物理內存。
如果某個一級頁表的頁表項沒有被用到，也就不需要創建這個頁表項對應的二級頁表了，即可以在需要時才創建二級頁表。
如果一級頁表所有表項都被用到，那么此時二級頁表大小為
4M(1024 * 4K)，假設我們只是用了一級頁表的20%。
在這種情況下，頁表所占用的物理內存就只有 4K(一級頁表大小) + 20% * 4M（存在的二級頁表） ，即 0.804M ，比起只用了二級頁表的 4M （一級頁表沒有用到的表項不用創建對應的二級頁表，因此此時存在的二級頁表共 20% * 4M ，但單極頁表時，二級頁表必須建滿 4M），大大的節約了內存。
而在64位系統中，兩級頁表是肯定不夠用的，因此又演變成了四級目錄：
- 全局頁目錄項 PGD
- 上層頁目錄項 PUD
- 中間頁目錄項 PMD
- 頁表項 PTE
快表(TLB)
多級頁表雖然解決了空間占用大的問題，但是由于其復雜化了地址的轉換，因此也帶來了 大量的時間開銷 ，使得地址轉換速度減慢。
解決這個問題最簡單的方式就是降低查詢頁表的頻率，那么如何實現呢？這時候就需要用到 緩存 的技術
對于熱點資源，我們可以將其提前緩存下來，到以后使用時就可以直接到緩存中查找。對于操作系統來說，也是這么一個道理。
在操作系統中，這個緩存就是 CPU 中的 TLB ，也就是我們通常所說的 快表 。我們將 最常訪問的幾個頁表項存儲到 TLB 中 ，在之后進行尋址時， CPU 就會先到 TLB 中進行查找，如果沒有找到，這時才會去查詢頁表。
段頁式
雖然分段和分頁各有優缺點，但他們直接并不是對立的，所以如今大部分的內存管理方式，都是將分段與分頁相結合，也就是我們常說的段頁式。
它的原理非常簡單，就是先對 虛擬內存空間進行分段管理，然后再對每一個段進行分頁管理。 如下圖：
所以此時的虛擬地址結構，就由 段號、段內頁號、頁內偏移 所組成。此時對于每個進程來說，都會建立一個段表，而對于段表中的每一個段，又會再分別建立一個頁表：
以此時的虛擬地址轉換為物理地址，就需要以下三個步驟：
- 訪問段表，得到頁表的起始地址；
- 訪問頁表，得到物理頁的起始地址；
- 訪問物理頁，加上頁內偏移，得到實際的物理地址。
這種方法雖然增加了系統開銷以及硬件成本，但是內存的利用率得到了巨大的提升。
Linux
由于硬件問題的限制，Linux 內存主要采用的是頁式內存管理，但同時也不可避免地涉及了段機制。
在往常的機制中，地址的轉換流程如下：
但是在 Linux 中，并沒有邏輯地址這一說(所有段起始地址相同)，因為其將段機制進行了弱化，此時段只用于進行訪問控制以及內存保護。
Linux 系統中的每個段都是從 0 地址開始的整個 4GB 虛擬空間（32 位環境下），也就是所有的段的起始地址都是一樣的。
這意味著，Linux 系統中的代碼，包括操作系統本身的代碼和應用程序代碼，所面對的地址空間都是線性地址空間（虛擬地址），這種做法相當于屏蔽了處理器中的邏輯地址概念，段只被用于訪問控制和內存保護。
