內(nèi)存都沒了，還能運(yùn)行程序？

文章大綱

主存(RAM)是一件非常重要的資源，必須要小心對(duì)待內(nèi)存。雖然目前大多數(shù)內(nèi)存的增長速度要比 IBM 7094 要快的多，但是，程序大小的增長要比內(nèi)存的增長還快很多。正如帕金森定律說的那樣：不管存儲(chǔ)器有多大，但是程序大小的增長速度比內(nèi)存容量的增長速度要快的多。下面我們就來探討一下操作系統(tǒng)是如何創(chuàng)建內(nèi)存并管理他們的。

經(jīng)過多年的探討，人們提出了一種分層存儲(chǔ)器體系(memory hierarchy)，下面是分層體系的分類

頂層的存儲(chǔ)器速度最高，但是容量最小，成本非常高，層級(jí)結(jié)構(gòu)越向下，其訪問效率越慢，容量越大，但是造價(jià)也就越便宜。

操作系統(tǒng)中管理內(nèi)存層次結(jié)構(gòu)的部分稱為內(nèi)存管理器(memory manager)，它的主要工作是有效的管理內(nèi)存，記錄哪些內(nèi)存是正在使用的，在進(jìn)程需要時(shí)分配內(nèi)存以及在進(jìn)程完成時(shí)回收內(nèi)存。

下面我們會(huì)對(duì)不同的內(nèi)存管理模型進(jìn)行探討，從簡單到復(fù)雜，由于最低級(jí)別的緩存是由硬件進(jìn)行管理的，所以我們主要探討主存模型和如何對(duì)主存進(jìn)行管理。

無存儲(chǔ)器抽象

最簡單的存儲(chǔ)器抽象是沒有存儲(chǔ)。早期大型計(jì)算機(jī)（20 世紀(jì) 60 年代之前），小型計(jì)算機(jī)（20 世紀(jì) 70 年代之前）和個(gè)人計(jì)算機(jī)（20 世紀(jì) 80 年代之前）都沒有存儲(chǔ)器抽象。每一個(gè)程序都直接訪問物理內(nèi)存。當(dāng)一個(gè)程序執(zhí)行如下命令：

MOV REGISTER1, 1000
計(jì)算機(jī)會(huì)把位置為 1000 的物理內(nèi)存中的內(nèi)容移到REGISTER1中。因此，那時(shí)呈現(xiàn)給程序員的內(nèi)存模型就是物理內(nèi)存，內(nèi)存地址從 0 開始到內(nèi)存地址的最大值中，每個(gè)地址中都會(huì)包含一個(gè) 8 位位數(shù)的單元。

所以這種情況下的計(jì)算機(jī)不可能會(huì)有兩個(gè)應(yīng)用程序同時(shí)在內(nèi)存中。如果第一個(gè)程序向內(nèi)存地址 2000 的這個(gè)位置寫入了一個(gè)值，那么此值將會(huì)替換第二個(gè)程序在該位置上的值，所以，同時(shí)運(yùn)行兩個(gè)應(yīng)用程序是行不通的，兩個(gè)程序會(huì)立刻崩潰。

不過即使存儲(chǔ)器模型就是物理內(nèi)存，還是存在一些可選項(xiàng)的。下面展示了三種變體

在上圖 a 中，操作系統(tǒng)位于RAM(Random Access Memory)的底部，或像是圖 b 一樣位于ROM(Read-Only Memory)頂部；而在圖 c 中，設(shè)備驅(qū)動(dòng)程序位于頂端的 ROM 中，而操作系統(tǒng)位于底部的 RAM 中。圖 a 的模型以前用在大型機(jī)和小型機(jī)上，但現(xiàn)在已經(jīng)很少使用了；圖 b 中的模型一般用于掌上電腦或者是嵌入式系統(tǒng)中。第三種模型就應(yīng)用在早期個(gè)人計(jì)算機(jī)中了。ROM 系統(tǒng)中的一部分成為BIOS (Basic Input Output System)。模型 a 和 c 的缺點(diǎn)是用戶程序中的錯(cuò)誤可能會(huì)破壞操作系統(tǒng)，可能會(huì)導(dǎo)致災(zāi)難性的后果。

按照這種方式組織系統(tǒng)時(shí)，通常同一個(gè)時(shí)刻只能有一個(gè)線程正在運(yùn)行。一旦用戶鍵入了一個(gè)命令，操作系統(tǒng)就把需要的程序從磁盤復(fù)制到內(nèi)存中并執(zhí)行；當(dāng)進(jìn)程運(yùn)行結(jié)束后，操作系統(tǒng)在用戶終端顯示提示符并等待新的命令。收到新的命令后，它把新的程序裝入內(nèi)存，覆蓋前一個(gè)程序。

在沒有存儲(chǔ)器抽象的系統(tǒng)中實(shí)現(xiàn)并行性的一種方式是使用多線程來編程。由于同一進(jìn)程中的多線程內(nèi)部共享同一內(nèi)存映像，那么實(shí)現(xiàn)并行也就不是問題了。

運(yùn)行多個(gè)程序

但是，即便沒有存儲(chǔ)器抽象，同時(shí)運(yùn)行多個(gè)程序也是有可能的。操作系統(tǒng)只需要把當(dāng)前內(nèi)存中所有內(nèi)容保存到磁盤文件中，然后再把程序讀入內(nèi)存即可。只要某一時(shí)間只有一個(gè)程序，那么就不會(huì)產(chǎn)生沖突。

在額外特殊硬件的幫助下，即使沒有交換功能，也可以并行的運(yùn)行多個(gè)程序。IBM 360 的早期模型就是這樣解決的

System/360是 IBM 在1964年4月7日，推出的劃時(shí)代的大型電腦，這一系列是世界上首個(gè)指令集可兼容計(jì)算機(jī)。

在 IBM 360 中，內(nèi)存被劃分為 2KB 的區(qū)域塊，每塊區(qū)域被分配一個(gè) 4 位的保護(hù)鍵，保護(hù)鍵存儲(chǔ)在 CPU 的特殊寄存器中。一個(gè)內(nèi)存為 1 MB 的機(jī)器只需要 512 個(gè)這樣的 4 位寄存器，容量總共為 256 字節(jié) (這個(gè)會(huì)算吧。)PSW(Program Status Word, 程序狀態(tài)字)中有一個(gè) 4 位碼。一個(gè)運(yùn)行中的進(jìn)程如果訪問鍵與其 PSW 碼不同的內(nèi)存，360 硬件會(huì)發(fā)現(xiàn)這種情況，因?yàn)橹挥胁僮飨到y(tǒng)可以修改保護(hù)鍵，這樣就可以防止進(jìn)程之間、用戶進(jìn)程和操作系統(tǒng)之間的干擾。

這種解決方式是有一個(gè)缺陷。如下所示，假設(shè)有兩個(gè)程序，每個(gè)大小各為 16 KB

從圖上可以看出，這是兩個(gè)不同的 16KB 程序的裝載過程，a 程序首先會(huì)跳轉(zhuǎn)到地址 24，那里是一條MOV指令，然而 b 程序會(huì)首先跳轉(zhuǎn)到地址 28，地址 28 是一條CMP指令。這是兩個(gè)程序被先后加載到內(nèi)存中的情形，假如這兩個(gè)程序被同時(shí)加載到內(nèi)存中從 0 地址處開始執(zhí)行，內(nèi)存的狀態(tài)就如上面 c 圖所示，程序裝載完畢開始運(yùn)行，第一個(gè)程序首先從 0 地址處開始運(yùn)行，執(zhí)行 JMP 24 指令，然后依次執(zhí)行后面的指令（許多指令沒有畫出），一段時(shí)間后第一個(gè)程序執(zhí)行完畢，然后開始執(zhí)行第二個(gè)程序。第二個(gè)程序的第一條指令是 28，這條指令會(huì)使程序跳轉(zhuǎn)到第一個(gè)程序的ADD處，而不是事先設(shè)定的跳轉(zhuǎn)指令 CMP，由于內(nèi)存地址的不正確訪問，這個(gè)程序可能在 1秒內(nèi)就崩潰了。

上面兩個(gè)程序同時(shí)執(zhí)行最核心的問題是都引用了絕對(duì)物理地址。這不是我們想要看到的。我們想要的是每一個(gè)程序都會(huì)引用一個(gè)私有的本地地址。IBM 360 在第二個(gè)程序裝載到內(nèi)存中的時(shí)候會(huì)使用一種稱為靜態(tài)重定位(static relocation)的技術(shù)來修改它。它的工作流程如下：當(dāng)一個(gè)程序被加載到 16384 地址時(shí)，常數(shù) 16384 被加到每一個(gè)程序地址上（所以JMP 28會(huì)變?yōu)镴MP 16412）。雖然這個(gè)機(jī)制在不出錯(cuò)誤的情況下是可行的，但這不是一種通用的解決辦法，同時(shí)會(huì)減慢裝載速度。更近一步來講，它需要所有可執(zhí)行程序中的額外信息，以指示哪些包含（可重定位）地址，哪些不包含（可重定位）地址。畢竟，上圖 b 中的 JMP 28 可以被重定向（被修改），而類似MOV REGISTER1,28會(huì)把數(shù)字 28 移到 REGISTER 中則不會(huì)重定向。所以，裝載器(loader)需要一定的能力來辨別地址和常數(shù)。

一種存儲(chǔ)器抽象：地址空間

把物理內(nèi)存暴露給進(jìn)程會(huì)有幾個(gè)主要的缺點(diǎn)：第一個(gè)問題是，如果用戶程序可以尋址內(nèi)存的每個(gè)字節(jié)，它們就可以很容易的破壞操作系統(tǒng)，從而使系統(tǒng)停止運(yùn)行（除非使用 IBM 360 那種 lock-and-key 模式或者特殊的硬件進(jìn)行保護(hù)）。即使在只有一個(gè)用戶進(jìn)程運(yùn)行的情況下，這個(gè)問題也存在。

第二點(diǎn)是，這種模型想要運(yùn)行多個(gè)程序是很困難的（如果只有一個(gè) CPU 那就是順序執(zhí)行），在個(gè)人計(jì)算機(jī)上，一般會(huì)打開很多應(yīng)用程序，比如輸入法、電子郵件、瀏覽器，這些進(jìn)程在不同時(shí)刻會(huì)有一個(gè)進(jìn)程正在運(yùn)行，其他應(yīng)用程序可以通過鼠標(biāo)來喚醒。在系統(tǒng)中沒有物理內(nèi)存的情況下很難實(shí)現(xiàn)。

地址空間的概念

如果要使多個(gè)應(yīng)用程序同時(shí)運(yùn)行在內(nèi)存中，必須要解決兩個(gè)問題：保護(hù)和重定位。我們來看 IBM 360 是如何解決的：第一種解決方式是用保護(hù)密鑰標(biāo)記內(nèi)存塊，并將執(zhí)行過程的密鑰與提取的每個(gè)存儲(chǔ)字的密鑰進(jìn)行比較。這種方式只能解決第一種問題，但是還是不能解決多進(jìn)程在內(nèi)存中同時(shí)運(yùn)行的問題。

還有一種更好的方式是創(chuàng)造一個(gè)存儲(chǔ)器抽象：地址空間(the address space)。就像進(jìn)程的概念創(chuàng)建了一種抽象的 CPU 來運(yùn)行程序，地址空間也創(chuàng)建了一種抽象內(nèi)存供程序使用。地址空間是進(jìn)程可以用來尋址內(nèi)存的地址集。每個(gè)進(jìn)程都有它自己的地址空間，獨(dú)立于其他進(jìn)程的地址空間，但是某些進(jìn)程會(huì)希望可以共享地址空間。

基址寄存器和變址寄存器

最簡單的辦法是使用動(dòng)態(tài)重定位(dynamic relocation)，它就是通過一種簡單的方式將每個(gè)進(jìn)程的地址空間映射到物理內(nèi)存的不同區(qū)域。從CDC 6600(世界上最早的超級(jí)計(jì)算機(jī))到Intel 8088(原始 IBM PC 的核心)所使用的經(jīng)典辦法是給每個(gè) CPU 配置兩個(gè)特殊硬件寄存器，通常叫做基址寄存器(basic register)和變址寄存器(limit register)。當(dāng)使用基址寄存器和變址寄存器時(shí)，程序會(huì)裝載到內(nèi)存中連續(xù)的空間位置并且在裝載期間無需重定位。當(dāng)一個(gè)進(jìn)程運(yùn)行時(shí)，程序的起始物理地址裝載到基址寄存器中，程序的長度則裝載到變址寄存器中。在上圖 c 中，當(dāng)一個(gè)程序運(yùn)行時(shí)，裝載到這些硬件寄存器中的基址和變址寄存器的值分別是 0 和 16384。當(dāng)?shù)诙€(gè)程序運(yùn)行時(shí)，這些值分別是 16384 和 32768。如果第三個(gè) 16 KB 的程序直接裝載到第二個(gè)程序的地址之上并且運(yùn)行，這時(shí)基址寄存器和變址寄存器的值會(huì)是 32768 和 16384。那么我們可以總結(jié)下

• 基址寄存器：存儲(chǔ)數(shù)據(jù)內(nèi)存的起始位置

  
  

• 變址寄存器：存儲(chǔ)應(yīng)用程序的長度。

  
  

每當(dāng)進(jìn)程引用內(nèi)存以獲取指令或讀取或?qū)懭霐?shù)據(jù)字時(shí)，CPU 硬件都會(huì)自動(dòng)將基址值添加到進(jìn)程生成的地址中，然后再將其發(fā)送到內(nèi)存總線上。同時(shí)，它檢查程序提供的地址是否等于或大于變址寄存器中的值。如果程序提供的地址要超過變址寄存器的范圍，那么會(huì)產(chǎn)生錯(cuò)誤并中止訪問。這樣，對(duì)上圖 c 中執(zhí)行JMP 28這條指令后，硬件會(huì)把它解釋為JMP 16412，所以程序能夠跳到 CMP 指令，過程如下

使用基址寄存器和變址寄存器是給每個(gè)進(jìn)程提供私有地址空間的一種非常好的方法，因?yàn)槊總€(gè)內(nèi)存地址在送到內(nèi)存之前，都會(huì)先加上基址寄存器的內(nèi)容。在很多實(shí)際系統(tǒng)中，對(duì)基址寄存器和變址寄存器都會(huì)以一定的方式加以保護(hù)，使得只有操作系統(tǒng)可以修改它們。在CDC 6600中就提供了對(duì)這些寄存器的保護(hù)，但在Intel 8088中則沒有，甚至沒有變址寄存器。但是，Intel 8088 提供了許多基址寄存器，使程序的代碼和數(shù)據(jù)可以被獨(dú)立的重定位，但是對(duì)于超出范圍的內(nèi)存引用沒有提供保護(hù)。

所以你可以知道使用基址寄存器和變址寄存器的缺點(diǎn)，在每次訪問內(nèi)存時(shí)，都會(huì)進(jìn)行ADD和CMP運(yùn)算。比較可以執(zhí)行的很快，但是加法就會(huì)相對(duì)慢一些，除非使用特殊的加法電路，否則加法因進(jìn)位傳播時(shí)間而變慢。

交換技術(shù)

如果計(jì)算機(jī)的物理內(nèi)存足夠大來容納所有的進(jìn)程，那么之前提及的方案或多或少是可行的。但是實(shí)際上，所有進(jìn)程需要的 RAM 總?cè)萘恳h(yuǎn)遠(yuǎn)高于內(nèi)存的容量。在 Windows、OS X、或者 Linux 系統(tǒng)中，在計(jì)算機(jī)完成啟動(dòng)（Boot）后，大約有 50 - 100 個(gè)進(jìn)程隨之啟動(dòng)。例如，當(dāng)一個(gè) Windows 應(yīng)用程序被安裝后，它通常會(huì)發(fā)出命令，以便在后續(xù)系統(tǒng)啟動(dòng)時(shí)，將啟動(dòng)一個(gè)進(jìn)程，這個(gè)進(jìn)程除了檢查應(yīng)用程序的更新外不做任何操作。一個(gè)簡單的應(yīng)用程序可能會(huì)占用5 - 10MB的內(nèi)存。其他后臺(tái)進(jìn)程會(huì)檢查電子郵件、網(wǎng)絡(luò)連接以及許多其他諸如此類的任務(wù)。這一切都會(huì)發(fā)生在第一個(gè)用戶啟動(dòng)之前。如今，像是Photoshop這樣的重要用戶應(yīng)用程序僅僅需要 500 MB 來啟動(dòng)，但是一旦它們開始處理數(shù)據(jù)就需要許多 GB 來處理。從結(jié)果上來看，將所有進(jìn)程始終保持在內(nèi)存中需要大量內(nèi)存，如果內(nèi)存不足，則無法完成。

所以針對(duì)上面內(nèi)存不足的問題，提出了兩種處理方式：最簡單的一種方式就是交換(swapping)技術(shù)，即把一個(gè)進(jìn)程完整的調(diào)入內(nèi)存，然后再內(nèi)存中運(yùn)行一段時(shí)間，再把它放回磁盤?？臻e進(jìn)程會(huì)存儲(chǔ)在磁盤中，所以這些進(jìn)程在沒有運(yùn)行時(shí)不會(huì)占用太多內(nèi)存。另外一種策略叫做虛擬內(nèi)存(virtual memory)，虛擬內(nèi)存技術(shù)能夠允許應(yīng)用程序部分的運(yùn)行在內(nèi)存中。下面我們首先先探討一下交換

交換過程

下面是一個(gè)交換過程

剛開始的時(shí)候，只有進(jìn)程 A 在內(nèi)存中，然后從創(chuàng)建進(jìn)程 B 和進(jìn)程 C 或者從磁盤中把它們換入內(nèi)存，然后在圖 d 中，A 被換出內(nèi)存到磁盤中，最后 A 重新進(jìn)來。因?yàn)閳D g 中的進(jìn)程 A 現(xiàn)在到了不同的位置，所以在裝載過程中需要被重新定位，或者在交換程序時(shí)通過軟件來執(zhí)行；或者在程序執(zhí)行期間通過硬件來重定位?；芳拇嫫骱妥冎芳拇嫫骶瓦m用于這種情況。

交換在內(nèi)存創(chuàng)建了多個(gè)空閑區(qū)(hole)，內(nèi)存會(huì)把所有的空閑區(qū)盡可能向下移動(dòng)合并成為一個(gè)大的空閑區(qū)。這項(xiàng)技術(shù)稱為內(nèi)存緊縮(memory compaction)。但是這項(xiàng)技術(shù)通常不會(huì)使用，因?yàn)檫@項(xiàng)技術(shù)會(huì)消耗很多 CPU 時(shí)間。例如，在一個(gè) 16GB 內(nèi)存的機(jī)器上每 8ns 復(fù)制 8 字節(jié)，它緊縮全部的內(nèi)存大約要花費(fèi) 16s。

有一個(gè)值得注意的問題是，當(dāng)進(jìn)程被創(chuàng)建或者換入內(nèi)存時(shí)應(yīng)該為它分配多大的內(nèi)存。如果進(jìn)程被創(chuàng)建后它的大小是固定的并且不再改變，那么分配策略就比較簡單：操作系統(tǒng)會(huì)準(zhǔn)確的按其需要的大小進(jìn)行分配。

但是如果進(jìn)程的data segment能夠自動(dòng)增長，例如，通過動(dòng)態(tài)分配堆中的內(nèi)存，肯定會(huì)出現(xiàn)問題。這里還是再提一下什么是data segment吧。從邏輯層面操作系統(tǒng)把數(shù)據(jù)分成不同的段(不同的區(qū)域)來存儲(chǔ)：

• 代碼段（codesegment/textsegment）：

  
  

又稱文本段，用來存放指令，運(yùn)行代碼的一塊內(nèi)存空間

此空間大小在代碼運(yùn)行前就已經(jīng)確定

內(nèi)存空間一般屬于只讀，某些架構(gòu)的代碼也允許可寫

在代碼段中，也有可能包含一些只讀的常數(shù)變量，例如字符串常量等。

• 數(shù)據(jù)段（datasegment）：

  
  

可讀可寫

存儲(chǔ)初始化的全局變量和初始化的 static 變量

數(shù)據(jù)段中數(shù)據(jù)的生存期是隨程序持續(xù)性（隨進(jìn)程持續(xù)性）
隨進(jìn)程持續(xù)性：進(jìn)程創(chuàng)建就存在，進(jìn)程死亡就消失

• bss段（bsssegment）：

  
  

可讀可寫

存儲(chǔ)未初始化的全局變量和未初始化的 static 變量

bss 段中數(shù)據(jù)的生存期隨進(jìn)程持續(xù)性

bss 段中的數(shù)據(jù)一般默認(rèn)為0

• rodata段：

  
  

只讀數(shù)據(jù)
比如 printf 語句中的格式字符串和開關(guān)語句的跳轉(zhuǎn)表。也就是常量區(qū)。例如，全局作用域中的 const int ival = 10，ival 存放在 .rodata 段；再如，函數(shù)局部作用域中的 printf("Hello world %d\n", c); 語句中的格式字符串 "Hello world %d\n"，也存放在 .rodata 段。

• 棧（stack）：

  
  

可讀可寫

存儲(chǔ)的是函數(shù)或代碼中的局部變量(非 static 變量)

棧的生存期隨代碼塊持續(xù)性，代碼塊運(yùn)行就給你分配空間，代碼塊結(jié)束，就自動(dòng)回收空間

• 堆（heap）：

  
  

可讀可寫

存儲(chǔ)的是程序運(yùn)行期間動(dòng)態(tài)分配的 malloc/realloc 的空間

堆的生存期隨進(jìn)程持續(xù)性，從 malloc/realloc 到 free 一直存在

下面是我們用 Borland C 編譯過后的結(jié)果

_TEXT    segment dword public use32 'CODE'
_TEXT    ends
_DATA    segment dword public use32 'DATA'
_DATA    ends
_BSS    segment dword public use32 'BSS'
_BSS    ends

段定義( segment ) 是用來區(qū)分或者劃分范圍區(qū)域的意思。匯編語言的 segment 偽指令表示段定義的起始，ends 偽指令表示段定義的結(jié)束。段定義是一段連續(xù)的內(nèi)存空間

所以內(nèi)存針對(duì)自動(dòng)增長的區(qū)域，會(huì)有三種處理方式

• 如果一個(gè)進(jìn)程與空閑區(qū)相鄰，那么可把該空閑區(qū)分配給進(jìn)程以供其增大。

  
  

• 如果進(jìn)程相鄰的是另一個(gè)進(jìn)程，就會(huì)有兩種處理方式：要么把需要增長的進(jìn)程移動(dòng)到一個(gè)內(nèi)存中空閑區(qū)足夠大的區(qū)域，要么把一個(gè)或多個(gè)進(jìn)程交換出去，已變成生成一個(gè)大的空閑區(qū)。

  
  

• 如果一個(gè)進(jìn)程在內(nèi)存中不能增長，而且磁盤上的交換區(qū)也滿了，那么這個(gè)進(jìn)程只有掛起一些空閑空間（或者可以結(jié)束該進(jìn)程）

  
  

上面只針對(duì)單個(gè)或者一小部分需要增長的進(jìn)程采用的方式，如果大部分進(jìn)程都要在運(yùn)行時(shí)增長，為了減少因內(nèi)存區(qū)域不夠而引起的進(jìn)程交換和移動(dòng)所產(chǎn)生的開銷，一種可用的方法是，在換入或移動(dòng)進(jìn)程時(shí)為它分配一些額外的內(nèi)存。然而，當(dāng)進(jìn)程被換出到磁盤上時(shí)，應(yīng)該只交換實(shí)際上使用的內(nèi)存，將額外的內(nèi)存交換也是一種浪費(fèi)，下面是一種為兩個(gè)進(jìn)程分配了增長空間的內(nèi)存配置。

如果進(jìn)程有兩個(gè)可增長的段，例如，供變量動(dòng)態(tài)分配和釋放的作為堆(全局變量)使用的一個(gè)數(shù)據(jù)段(data segment)，以及存放局部變量與返回地址的一個(gè)堆棧段(stack segment)，就如圖 b 所示。在圖中可以看到所示進(jìn)程的堆棧段在進(jìn)程所占內(nèi)存的頂端向下增長，緊接著在程序段后的數(shù)據(jù)段向上增長。當(dāng)增長預(yù)留的內(nèi)存區(qū)域不夠了，處理方式就如上面的流程圖(data segment 自動(dòng)增長的三種處理方式)一樣了。

空閑內(nèi)存管理

在進(jìn)行內(nèi)存動(dòng)態(tài)分配時(shí)，操作系統(tǒng)必須對(duì)其進(jìn)行管理。大致上說，有兩種監(jiān)控內(nèi)存使用的方式

• 位圖(bitmap)

  
  

• 空閑列表(free lists)

  
  

下面我們就來探討一下這兩種使用方式

使用位圖的存儲(chǔ)管理

使用位圖方法時(shí)，內(nèi)存可能被劃分為小到幾個(gè)字或大到幾千字節(jié)的分配單元。每個(gè)分配單元對(duì)應(yīng)于位圖中的一位，0 表示空閑， 1 表示占用（或者相反）。一塊內(nèi)存區(qū)域和其對(duì)應(yīng)的位圖如下

圖 a 表示一段有 5 個(gè)進(jìn)程和 3 個(gè)空閑區(qū)的內(nèi)存，刻度為內(nèi)存分配單元，陰影區(qū)表示空閑（在位圖中用 0 表示）；圖 b 表示對(duì)應(yīng)的位圖；圖 c 表示用鏈表表示同樣的信息

分配單元的大小是一個(gè)重要的設(shè)計(jì)因素，分配單位越小，位圖越大。然而，即使只有 4 字節(jié)的分配單元，32 位的內(nèi)存也僅僅只需要位圖中的 1 位。32n位的內(nèi)存需要 n 位的位圖，所以1 個(gè)位圖只占用了 1/32 的內(nèi)存。如果選擇更大的內(nèi)存單元，位圖應(yīng)該要更小。如果進(jìn)程的大小不是分配單元的整數(shù)倍，那么在最后一個(gè)分配單元中會(huì)有大量的內(nèi)存被浪費(fèi)。

位圖提供了一種簡單的方法在固定大小的內(nèi)存中跟蹤內(nèi)存的使用情況，因?yàn)槲粓D的大小取決于內(nèi)存和分配單元的大小。這種方法有一個(gè)問題是，當(dāng)決定把具有 k 個(gè)分配單元的進(jìn)程放入內(nèi)存時(shí)，內(nèi)容管理器(memory manager)必須搜索位圖，在位圖中找出能夠運(yùn)行 k 個(gè)連續(xù) 0 位的串。在位圖中找出制定長度的連續(xù) 0 串是一個(gè)很耗時(shí)的操作，這是位圖的缺點(diǎn)。（可以簡單理解為在雜亂無章的數(shù)組中，找出具有一大長串空閑的數(shù)組單元）

使用鏈表進(jìn)行管理

另一種記錄內(nèi)存使用情況的方法是，維護(hù)一個(gè)記錄已分配內(nèi)存段和空閑內(nèi)存段的鏈表，段會(huì)包含進(jìn)程或者是兩個(gè)進(jìn)程的空閑區(qū)域。可用上面的圖 c 來表示內(nèi)存的使用情況。鏈表中的每一項(xiàng)都可以代表一個(gè)空閑區(qū)(H)或者是進(jìn)程(P)的起始標(biāo)志，長度和下一個(gè)鏈表項(xiàng)的位置。

在這個(gè)例子中，段鏈表(segment list)是按照地址排序的。這種方式的優(yōu)點(diǎn)是，當(dāng)進(jìn)程終止或被交換時(shí)，更新列表很簡單。一個(gè)終止進(jìn)程通常有兩個(gè)鄰居（除了內(nèi)存的頂部和底部外）。相鄰的可能是進(jìn)程也可能是空閑區(qū)，它們有四種組合方式。

當(dāng)按照地址順序在鏈表中存放進(jìn)程和空閑區(qū)時(shí)，有幾種算法可以為創(chuàng)建的進(jìn)程（或者從磁盤中換入的進(jìn)程）分配內(nèi)存。我們先假設(shè)內(nèi)存管理器知道應(yīng)該分配多少內(nèi)存，最簡單的算法是使用首次適配(first fit)。內(nèi)存管理器會(huì)沿著段列表進(jìn)行掃描，直到找個(gè)一個(gè)足夠大的空閑區(qū)為止。除非空閑區(qū)大小和要分配的空間大小一樣，否則將空閑區(qū)分為兩部分，一部分供進(jìn)程使用；一部分生成新的空閑區(qū)。首次適配算法是一種速度很快的算法，因?yàn)樗鼤?huì)盡可能的搜索鏈表。

首次適配的一個(gè)小的變體是下次適配(next fit)。它和首次匹配的工作方式相同，只有一個(gè)不同之處那就是下次適配在每次找到合適的空閑區(qū)時(shí)就會(huì)記錄當(dāng)時(shí)的位置，以便下次尋找空閑區(qū)時(shí)從上次結(jié)束的地方開始搜索，而不是像首次匹配算法那樣每次都會(huì)從頭開始搜索。Bays(1997)證明了下次算法的性能略低于首次匹配算法。

另外一個(gè)著名的并且廣泛使用的算法是最佳適配(best fit)。最佳適配會(huì)從頭到尾尋找整個(gè)鏈表，找出能夠容納進(jìn)程的最小空閑區(qū)。最佳適配算法會(huì)試圖找出最接近實(shí)際需要的空閑區(qū)，以最好的匹配請(qǐng)求和可用空閑區(qū)，而不是先一次拆分一個(gè)以后可能會(huì)用到的大的空閑區(qū)。比如現(xiàn)在我們需要一個(gè)大小為 2 的塊，那么首次匹配算法會(huì)把這個(gè)塊分配在位置 5 的空閑區(qū)，而最佳適配算法會(huì)把該塊分配在位置為 18 的空閑區(qū)，如下

那么最佳適配算法的性能如何呢？最佳適配會(huì)遍歷整個(gè)鏈表，所以最佳適配算法的性能要比首次匹配算法差。但是令人想不到的是，最佳適配算法要比首次匹配和下次匹配算法浪費(fèi)更多的內(nèi)存，因?yàn)樗鼤?huì)產(chǎn)生大量無用的小緩沖區(qū)，首次匹配算法生成的空閑區(qū)會(huì)更大一些。

最佳適配的空閑區(qū)會(huì)分裂出很多非常小的緩沖區(qū)，為了避免這一問題，可以考慮使用最差適配(worst fit)算法。即總是分配最大的內(nèi)存區(qū)域（所以你現(xiàn)在明白為什么最佳適配算法會(huì)分裂出很多小緩沖區(qū)了吧），使新分配的空閑區(qū)比較大從而可以繼續(xù)使用。仿真程序表明最差適配算法也不是一個(gè)好主意。

如果為進(jìn)程和空閑區(qū)維護(hù)各自獨(dú)立的鏈表，那么這四個(gè)算法的速度都能得到提高。這樣，這四種算法的目標(biāo)都是為了檢查空閑區(qū)而不是進(jìn)程。但這種分配速度的提高的一個(gè)不可避免的代價(jià)是增加復(fù)雜度和減慢內(nèi)存釋放速度，因?yàn)楸仨殞⒁粋€(gè)回收的段從進(jìn)程鏈表中刪除并插入空閑鏈表區(qū)。

如果進(jìn)程和空閑區(qū)使用不同的鏈表，那么可以按照大小對(duì)空閑區(qū)鏈表排序，以便提高最佳適配算法的速度。在使用最佳適配算法搜索由小到大排列的空閑區(qū)鏈表時(shí)，只要找到一個(gè)合適的空閑區(qū)，則這個(gè)空閑區(qū)就是能容納這個(gè)作業(yè)的最小空閑區(qū)，因此是最佳匹配。因?yàn)榭臻e區(qū)鏈表以單鏈表形式組織，所以不需要進(jìn)一步搜索。空閑區(qū)鏈表按大小排序時(shí)，首次適配算法與最佳適配算法一樣快，而下次適配算法在這里毫無意義。

另一種分配算法是快速適配(quick fit)算法，它為那些常用大小的空閑區(qū)維護(hù)單獨(dú)的鏈表。例如，有一個(gè) n 項(xiàng)的表，該表的第一項(xiàng)是指向大小為 4 KB 的空閑區(qū)鏈表表頭指針，第二項(xiàng)是指向大小為 8 KB 的空閑區(qū)鏈表表頭指針，第三項(xiàng)是指向大小為 12 KB 的空閑區(qū)鏈表表頭指針，以此類推。比如 21 KB 這樣的空閑區(qū)既可以放在 20 KB 的鏈表中，也可以放在一個(gè)專門存放大小比較特別的空閑區(qū)鏈表中。

快速匹配算法尋找一個(gè)指定代銷的空閑區(qū)也是十分快速的，但它和所有將空閑區(qū)按大小排序的方案一樣，都有一個(gè)共同的缺點(diǎn)，即在一個(gè)進(jìn)程終止或被換出時(shí)，尋找它的相鄰塊并查看是否可以合并的過程都是非常耗時(shí)的。如果不進(jìn)行合并，內(nèi)存將會(huì)很快分裂出大量進(jìn)程無法利用的小空閑區(qū)。

文章參考：

https://baike.baidu.com/item/內(nèi)存/103614?fr=aladdin

https://baike.baidu.com/item/數(shù)據(jù)段/5136260?fromtitle=data segment