內存管理總覽

先籠統(tǒng)地總結下內存管理到底是干啥的，下面這段話摘自《現(xiàn)代操作系統(tǒng) - 第 3 版》：

內存管理的任務就是有效地管理內存，即記錄哪些內存是正確使用的，哪些內存是空閑的，在進程需要時為其分配內存，在進程使用完后釋放內存。

眾所周知，當前計算機都是基于馮·偌依曼存儲程序式的計算機，程序和數(shù)據(jù)在運行和使用時都需要存放在內存中。

設計操作系統(tǒng)的重要目標之一就是提高計算機資源的利用率，而隨著多核 CPU 的盛行，多道程序設計技術大行其道。因此，必須合理地管理內存空間，使盡量多的進程/作業(yè)能夠同時存放于內存中以提高 CPU 的利用率。

通俗來說，內存管理所研究的內容無外乎以下這三個方面：

• 取 Fetch
• 放 Placement
• 替換 Replacement

所謂 “取” 研究的就是，應該將哪個進程（或進程的某些部分）從外存（磁盤）調入內存。

“放” 研究的則是，將從外存（磁盤）中 “取” 來的進程（或進程的某部分）按照何種方式放在內存的什么地方。

很顯然，“放” 是內存管理的基礎，目前 “放” 的技術可歸結成兩類：

1）一類是連續(xù)分配，即運行的程序和數(shù)據(jù)必須放在內存的一片連續(xù)空間中。

連續(xù)分配管理方式包括單一連續(xù)分配、固定分區(qū)分配和動態(tài)分區(qū)分配。

2）另一類是不連續(xù)分配，即運行的程序和數(shù)據(jù)可以放在內存的多個不相鄰的塊中。

不連續(xù)分配管理方式包括基本分頁管理、基本分段管理和基本段頁式管理。

看到這里，各位不妨想一想，如果只有 “取” 操作和 “放” 操作，那么會導致什么問題？

隨著用戶程序功能的增加，進程所需要的內存空間越來越大，進程空間很容易就突破了物理內存的實際大小，導致進程無法運行。

因此，為了解決內存不足的情況，緩和大程序與小內存之間的矛盾，擴充內存容量勢在必行。

可以從物理和邏輯兩方面來考慮擴充內存容量，物理擴容沒啥技術含量，需要我們研究的自然是如何從邏輯上擴充內存容量。

所謂邏輯擴充，就是說實際上物理內存的容量沒有發(fā)生改變，但是它能裝的東西卻變多了。

對內存的邏輯擴充技術主要有三種：覆蓋技術、交換技術、以及虛擬內存。事實上，這些邏輯擴充技術的核心理念都是一致的，我覺得用一個詞來總結就是 “替換”：

所謂 “替換” 和 “取” 操作正好相反，它研究的是將哪個進程（或進程的某部分）暫時從內存移到外存（磁盤），以騰出內存空間供其他進程（或進程的某部分）占用。

前兩種邏輯擴充技術已經(jīng)成為歷史，虛擬內存技術是目前的主流。所以也有很多人把內存管理這塊的內容直接區(qū)分為物理內存管理和虛擬內存管理，一目了然。

對于虛擬內存的管理是建立在不連續(xù)分配管理方式之上的，包括請求分頁管理、請求分段管理和請求段頁式管理。這幾個概念和上文所說的基本分頁管理、基本分段管理和基本段頁式管理非常容易混淆。

其實很容易區(qū)分，記住這句話就 OK，摘自百度百科：

如果不具備頁面置換的功能，則稱為基本分頁管理（或稱為純分頁管理），它不具有支持實現(xiàn)虛擬內存的功能，它要求把每個作業(yè)（進程）全部裝入內存后方能運行。

內存管理整部分總覽如上，而本文，內存管理第一部曲，講的僅是物理內存管理這塊。

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

其實在早期的操作系統(tǒng)中，采用的都是連續(xù)內存空間分配的策略。那時還沒有引入進程概念，內存分配還是以作業(yè)（相當于進程）為單位，而所謂連續(xù)分配呢就是將作業(yè)分配到一段連續(xù)的內存空間。

連續(xù)分配管理并非本文的重點，面試中更是冷門，但事實上，這些方法對任何形式的內存空間分配都具有參考意義。因此，還是有必要做個簡單的了解。

連續(xù)分配管理方式包括單一連續(xù)分配、固定分區(qū)分配和動態(tài)分區(qū)分配。

單一連續(xù)分配

在沒有操作系統(tǒng)的時期，勿容置疑，整個內存空間由單個用戶使用。而隨著操作系統(tǒng)的出現(xiàn)，內存管理也隨之出現(xiàn)了，用戶再無法獨占內存資源。

當時的內存管理十分簡單，僅將內存空間分成兩塊：系統(tǒng)區(qū)（用于存放操作系統(tǒng)相關數(shù)據(jù)）和用戶區(qū)（用于存放用戶進程相關數(shù)據(jù)）。

操作系統(tǒng)可以在低地址部分，也可以在高地址部分，假設操作系統(tǒng)在低地址部分，如圖所示：

單一連續(xù)分配的管理方式確實有點過于簡單了，內存中只能有一道用戶程序，用戶程序獨占整個用戶區(qū)空間。

缺點自然是顯而易見：只能用于單用戶、單任務的操作系統(tǒng)中；有內部碎片（分配給某進程的內存區(qū)域 中，如果有些部分沒有用上，就是“內部碎片”）；內存利用率極低。

固定分區(qū)分配

20 世紀 60 年代出現(xiàn)了支持多道程序的系統(tǒng)，為了能在內存中裝入多道程序，且這些程序之間又不會相互干擾， 于是考慮將整個用戶空間劃分為若干個固定大小的分區(qū)，在每個分區(qū)中只裝入一道作業(yè)，這樣就形成了最早的、最簡單的一種可運行多道程序的內存管理方式。

至于這些分區(qū)大小是否需要相等，各有各的適用場景：

• 分區(qū)大小相等：缺乏靈活性。但是適合用于一臺計算機控制多個相同對象的場合（比如鋼鐵廠有 n 個相同的煉鋼爐，就可以把內存空間分為 n 個大小相等的區(qū)域存放 n 個煉鋼控制程序）
• 分區(qū)大小不等：增加了靈活性，可以滿足不同大小的進程需求

遺憾的是，雖然固定分區(qū)分配的方式支持了多道程序，但是仍然會產(chǎn)生內部碎片，內存利用率依然比較低。為此，人們又引入了動態(tài)分區(qū)分配，這種方法對用戶區(qū)域實施動態(tài)分割，從而改善了內存空間的利用效果。

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

動態(tài)分區(qū)分配又稱為可變分區(qū)分配。這種分配方式不會預先劃分內存分區(qū)，而是在進程裝入內存時， 根據(jù)進程的大小動態(tài)地建立分區(qū)，并使分區(qū)的大小正好適合進程的需要。因此系統(tǒng)分區(qū)的大小和數(shù)目是可變的。

動態(tài)分區(qū)分配比較復雜，需要用特殊的數(shù)據(jù)結構記錄內存的使用情況，具體的細節(jié)這里就不再詳細介紹了。

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

可以看出來，連續(xù)的內存分配具有易理解、訪問效率高等優(yōu)點。但是，由于其要求把作業(yè)（進程）放在內存的一片連續(xù)區(qū)域中，很容易出現(xiàn)大段的連續(xù)內存空間因為不足夠容納作業(yè)或進程而不可用。因此，為了充分利用內存空間資源而引入了非連續(xù)分配策略。

所謂非連續(xù)分配就是說作業(yè)（進程）可以放在內存的多個不相鄰的塊中。

非連續(xù)分配管理方式包括頁式管理、段式管理和段頁式管理。

在閱讀本段之前，需要先了解虛擬地址（邏輯地址）與物理地址的概念，可以參考這篇文章：你看到的所有地址都不是真的

基本分頁管理

所謂頁式管理，我們需要先解釋一下什么是 “頁”？

首先，將內存空間分為一個個大小相等的分區(qū)，每個分區(qū)就稱為一個 “頁框（page frame）”。每個頁框有一個編號，即“頁框號”（也成為物理頁框號、內存塊號），頁框號從 0 開 始 。

將進程的虛擬地址空間也分為與頁框大小相等的一個個分區(qū)， 每個分區(qū)就稱為一個 “頁（page）” 或 “頁面” 。每個頁面也有一個編號， 即“頁號”（也稱為虛擬頁號），頁號也是從 0 開始。

操作系統(tǒng)以頁框為單位為各個進程分配內存空間。進程的每個頁面分別放入一個頁框中。也就是說，進程的頁面與內存的頁框有一一對應的關系。各個頁面不必連續(xù)存放，可以放到不相鄰（離散）的各個頁框中。

舉個例子，如下圖，每個頁面和頁框的大小都是 4KB，我們擁有 64KB 的虛擬地址空間和 32KB 的物理內存，因此可以得到 16 個頁面和 8 個頁框：

前文說過，指令真正執(zhí)行的時候會將虛擬地址最終轉換為物理地址。

那么，頁式管理中是如何將虛擬地址（頁面）和物理地址（頁框）進行映射的呢？換句話說，如何根據(jù)虛擬地址計算得到物理地址？

為此，操作系統(tǒng)為每個進程建立了一張頁表，這是一個十分重要的數(shù)據(jù)結構！頁表通常存在進程控制塊（PCB）中。

一個進程對應一張頁表，進程的每個頁面對應一個頁表項，每個頁表項由頁號和塊號（頁框號）組成，記錄著進程頁面和實際存放的內存塊之間的映射關系。

從數(shù)學角度來說，頁表是一個函數(shù)，它的參數(shù)是虛擬頁號，結果是物理頁框號。

頁式管理中的兩個重要問題

在任何分頁式系統(tǒng)中，都不可避免地要考慮下面這兩個問題：

• 問題 1：如何保證虛擬地址到物理地址的轉換足夠快 — 使用快表解決
• 問題 2：如何解決虛擬地址空間大，頁表也會很大的問題（頁表項多了，頁表自然也就大了）— 使用多級頁表解決

先來看第一個問題，由于每次訪問內存，都需要進行虛擬地址到物理地址的轉換，因此，每條指令進行一兩次或更多頁表訪問是必要的，而頁表又是存在于內存中的。

那么，既然訪問頁表（內存）次數(shù)太多導致其成為了一個性能瓶頸，那我們想個方法使得這個地址映射不用訪問內存，訪問一個比內存快得多的東西不就行了？

計算機的設計者給出的解決方案大致如此，為計算機設置了一個小型的硬件設備，將虛擬地址直接映射成物理地址，而不必再訪問頁表。這個設備就是轉換檢測緩沖區(qū)（Translation Lookaside Buffer，TLB），也被稱為快表。

為啥說他快呢？因為 TLB 通常內置在 CPU 的 MMU（內存管理單元） 中，這訪問速度跟內存不是一個檔次的。內存中的頁表一般被稱為慢表。

那么，擁有了 TLB 就可以一勞永逸直接放棄頁表了嗎？

當然不。

TLB 僅僅包含少量的表項，每個表項記錄了一個頁面的相關信息，其表結構大致如下：

事實上，TLB 的出現(xiàn)是基于這樣一種現(xiàn)象的：大多數(shù)程序總是對少量的頁面進行多次的訪問。因此，只有很少的頁表項會被反復讀取，而其他的頁表項很少被訪問。

TLB 中存放的就是那些會被反復讀取的頁表項。換句話說，TLB 中存放的只是頁表中的一部分副本。

若 TLB 命中，就不需要再訪問內存了；若 TLB 中沒有目標頁表項，則還需要去查詢內存中的頁表（慢表），從頁表中得到物理頁框地址，同時將頁表中的該表項添加到 TLB 中。

那么問題又隨之而來了，如果 TLB 填滿了怎么辦？

當 TLB 填滿后又要登記新頁時，就會按照一定的淘汰策略淘汰掉快表中的一個頁。

再來看第二個問題，現(xiàn)代大多數(shù)計算機系統(tǒng)，一般都支持非常大的虛擬地址空間，從而使頁表變得十分龐大且需要占用相對可觀的內存空間（頁表項多了，頁表自然也就大了）。我們假設系統(tǒng)中只有一個頁表，那即使我們使用的只是虛擬地址空間中的一小部分，也總是需要一整個頁表全部駐留在內存中。

用來壓縮頁表的常用方法就是使用層次結構的頁表。

以最常見的二級頁表舉例，我們來看多級頁表的處理思路：

把頁表再分頁并離散存儲，然后再建立一張頁表記錄頁表各個部分的存放位置，稱為 “頁目錄表”（或稱外層頁表、頂層頁表）。

若分為兩級頁表后，頁表依然很長，則可以對外層頁表再分頁形成三級以上的多級頁表。

多級頁表技術不但突破了頁表必須連續(xù)存放的限制，同時當有大片虛擬地址空間未使用時，可以不分配對應頁表空間，因此可節(jié)省內存。另外，多級頁表增加了訪存次數(shù)，因此外層頁表的頁表項應該盡可能保持在 TLB 中，以減少訪存開銷。

基本分段管理

頁式管理雖具有內存空間利用率高、管理方法簡單等特點，但是將內存空間按頁進行劃分對用戶來說不是很自然。用戶看待程序是以自然段為單位的，比如主程序段、子程序段、數(shù)據(jù)段等。若用戶要求對數(shù)據(jù)進行保護，那么受到保護的基本單位也是自然段。例如，某段只能讀，另一段可執(zhí)行等。

而分頁完全可能把不屬于同一段的兩塊分到同一頁中。如下圖，第 4 頁中既包含程序段（可執(zhí)行），又包含數(shù)據(jù)段（可讀、可寫）：

換句話說，雖然頁式管理提高了內存利用率，但是頁式管理劃分出來的頁并無任何實際意義。

為此，段式管理應運而生。

段式系統(tǒng)是按照用戶作業(yè)（進程）中的自然段來劃分邏輯空間的。比如說，用戶作業(yè)（進程）由主程序、兩個子程序、棧和一段數(shù)據(jù)組成，于是可將這個用戶作業(yè)（進程）劃分成 5 段，顯然，頁面是定長的而段不是：

從圖中可以看出來，段與段之間可以不連續(xù)存儲，但是段的內部仍然是連續(xù)的。

另外，和基本分頁管理一樣，基本分段管理也需要一個數(shù)據(jù)結構來記錄虛擬地址和物理地址之間的映射，這個數(shù)據(jù)結構就是段表。

基本段頁管理

如果一個段比較大，把它整個保存在內存中可能很不方便甚至不可能的，因此對它產(chǎn)生了分頁的想法。

對段進行分頁的支持，這就是段頁式管理的基本思想。

簡單來說，就是對虛擬地址空間先進行段的劃分，然后在每一段內再進行頁的劃分。例如，若用戶進程由主程序、子程序和數(shù)據(jù)段組成，則通過段、頁劃分后如圖所示：

References

• 《操作系統(tǒng) - 第 3 版 - 羅宇》
• 《現(xiàn)代操作系統(tǒng) - 第 3 版》
• 《深入理解計算機系統(tǒng) - 第 3 版》