內(nèi)存管理總覽

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

內(nèi)存管理的任務(wù)就是有效地管理內(nèi)存，即記錄哪些內(nèi)存是正確使用的，哪些內(nèi)存是空閑的，在進(jìn)程需要時(shí)為其分配內(nèi)存，在進(jìn)程使用完后釋放內(nèi)存。

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

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

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

取Fetch

放Placement

替換Replacement

所謂 “取” 研究的就是，應(yīng)該將哪個(gè)進(jìn)程（或進(jìn)程的某些部分）從外存（磁盤）調(diào)入內(nèi)存。

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

很顯然，“放” 是內(nèi)存管理的基礎(chǔ)，目前 “放” 的技術(shù)可歸結(jié)成兩類：

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

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

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

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

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

隨著用戶程序功能的增加，進(jìn)程所需要的內(nèi)存空間越來越大，進(jìn)程空間很容易就突破了物理內(nèi)存的實(shí)際大小，導(dǎo)致進(jìn)程無法運(yùn)行。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

單一連續(xù)分配

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

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

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

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

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

固定分區(qū)分配

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

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

分區(qū)大小相等：缺乏靈活性。但是適合用于一臺計(jì)算機(jī)控制多個(gè)相同對象的場合（比如鋼鐵廠有 n 個(gè)相同的煉鋼爐，就可以把內(nèi)存空間分為 n 個(gè)大小相等的區(qū)域存放 n 個(gè)煉鋼控制程序）

分區(qū)大小不等：增加了靈活性，可以滿足不同大小的進(jìn)程需求

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

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

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

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

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

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

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

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

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

基本分頁管理

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

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

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

操作系統(tǒng)以頁框?yàn)閱挝粸楦鱾€(gè)進(jìn)程分配內(nèi)存空間。進(jìn)程的每個(gè)頁面分別放入一個(gè)頁框中。也就是說，進(jìn)程的頁面與內(nèi)存的頁框有一一對應(yīng)的關(guān)系。各個(gè)頁面不必連續(xù)存放，可以放到不相鄰（離散）的各個(gè)頁框中。

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

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

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

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

一個(gè)進(jìn)程對應(yīng)一張頁表，進(jìn)程的每個(gè)頁面對應(yīng)一個(gè)頁表項(xiàng)，每個(gè)頁表項(xiàng)由頁號和塊號（頁框號）組成，記錄著進(jìn)程頁面和實(shí)際存放的內(nèi)存塊之間的映射關(guān)系。

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

頁式管理中的兩個(gè)重要問題

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

問題 1：如何保證虛擬地址到物理地址的轉(zhuǎn)換足夠快 — 使用快表解決

問題 2：如何解決虛擬地址空間大，頁表也會(huì)很大的問題（頁表項(xiàng)多了，頁表自然也就大了）— 使用多級頁表解決

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

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

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

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

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

當(dāng)然不。

TLB 僅僅包含少量的表項(xiàng)，每個(gè)表項(xiàng)記錄了一個(gè)頁面的相關(guān)信息

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

TLB 中存放的就是那些會(huì)被反復(fù)讀取的頁表項(xiàng)。換句話說，TLB 中存放的只是頁表中的一部分副本。

若 TLB 命中，就不需要再訪問內(nèi)存了；若 TLB 中沒有目標(biāo)頁表項(xiàng)，則還需要去查詢內(nèi)存中的頁表（慢表），從頁表中得到物理頁框地址，同時(shí)將頁表中的該表項(xiàng)添加到 TLB 中。

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

當(dāng) TLB 填滿后又要登記新頁時(shí)，就會(huì)按照一定的淘汰策略淘汰掉快表中的一個(gè)頁。

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

用來壓縮頁表的常用方法就是使用層次結(jié)構(gòu)的頁表。

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

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

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

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

基本分段管理

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

而分頁完全可能把不屬于同一段的兩塊分到同一頁中。

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

為此，段式管理應(yīng)運(yùn)而生。

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

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

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

基本段頁管理

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

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

簡單來說，就是對虛擬地址空間先進(jìn)行段的劃分，然后在每一段內(nèi)再進(jìn)行頁的劃分。

原文標(biāo)題：內(nèi)存管理兩部曲之物理內(nèi)存管理

文章出處：【微信公眾號：Linux愛好者】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

責(zé)任編輯：haq