內(nèi)存是計(jì)算機(jī)很重要的一個(gè)資源，因?yàn)槌绦蛑挥斜患虞d到內(nèi)存中才可以運(yùn)行；此外，CPU所需要的指令與數(shù)據(jù)也都是來(lái)自?xún)?nèi)存的。可以說(shuō)，內(nèi)存是影響計(jì)算機(jī)性能的一個(gè)很重要的因素。
隨著技術(shù)的發(fā)展，現(xiàn)在計(jì)算機(jī)的內(nèi)存容量已經(jīng)有了很大的增長(zhǎng)，但是程序大小的增長(zhǎng)速度比內(nèi)存容量的增長(zhǎng)速度要快得多。正如帕金森定律所指出，“不論存儲(chǔ)器有多大，程序都可以把它填滿”。所以問(wèn)題來(lái)了，當(dāng)一個(gè)程序大小超過(guò)內(nèi)存容量時(shí)，如何把調(diào)入內(nèi)存中？這篇文章將總結(jié)內(nèi)存管理的一些技術(shù)。

在介紹內(nèi)存管理的細(xì)節(jié)前，先要了解一下分層存儲(chǔ)器體系（一圖勝千言）。

計(jì)算機(jī)的性能指標(biāo)+3、存儲(chǔ)容量+現(xiàn)代計(jì)算機(jī)的存儲(chǔ)系統(tǒng)：+三級(jí)存儲(chǔ)體系：內(nèi)存、外存、緩存（cache）+CPU內(nèi)部、速度最快+Cache.jpg

分層存儲(chǔ)體系這個(gè)模型并不是一開(kāi)始就有的，而是隨著計(jì)算機(jī)的發(fā)展來(lái)一步步完善，最終才形成了現(xiàn)在的體系。所以，分層存儲(chǔ)體系的發(fā)展歷史也是這篇文章的一個(gè)線索。

無(wú)存儲(chǔ)器抽象

早期的計(jì)算機(jī)是沒(méi)有存儲(chǔ)器抽象的，直接將物理內(nèi)存暴露給程序。可以把內(nèi)存想象成中醫(yī)中放草藥的盒子，每個(gè)盒子都有標(biāo)記放的是哪種草藥，當(dāng)有兩種草藥同時(shí)放到一個(gè)盒子中去，就會(huì)出現(xiàn)醫(yī)療事故。
所以，這種情況下的內(nèi)存管理是有問(wèn)題的：

• 在內(nèi)存中同時(shí)運(yùn)行兩個(gè)程序是不可能的。一個(gè)程序在1000位置寫(xiě)入一個(gè)新的值，將會(huì)被新程序?qū)懙闹邓采w。這個(gè)跟一個(gè)盒子里是不能同時(shí)放兩種草藥是一樣的

• 重定位問(wèn)題：假設(shè)內(nèi)存中有兩個(gè)程序A、B，如果使用絕對(duì)物理地址，那么，在程序B
  執(zhí)行JMP 28指令時(shí)，就會(huì)跳轉(zhuǎn)到A程序的ADD指令，引發(fā)程序崩潰。B程序想要的跳的指令時(shí)CMP。CMP 指令地址是16412，而B(niǎo)使用了28,28是絕對(duì)地址。

  
  
  47352085344489238.jpg

存儲(chǔ)器抽象--地址空間

為了解決保護(hù)和重定位的問(wèn)題，人們創(chuàng)造了一個(gè)新的內(nèi)存抽象：地址空間。地址空間是一個(gè)進(jìn)程可用于尋址內(nèi)存的一套地址集合。每個(gè)進(jìn)程都有一個(gè)自己的地址空間，并且這個(gè)地址空間獨(dú)立于其他的地址空間。
地址空間在現(xiàn)實(shí)生活中有多的應(yīng)用。比如電話的區(qū)號(hào)，北京是010，上海是021。這樣即使同一個(gè)電話號(hào)碼，區(qū)號(hào)不同也能區(qū)分開(kāi)來(lái)。
考慮上個(gè)例子中的程序A、B，如果使用地址空間的話，B程序跳轉(zhuǎn)28，就不會(huì)跳轉(zhuǎn)到A程序的指令了。因?yàn)閮蓚€(gè)28分別屬于不同地址空間。

了解地址空間這個(gè)概念，接下來(lái)看一下計(jì)算機(jī)是如何實(shí)現(xiàn)將兩個(gè)28映射到不同地址空間里的。
經(jīng)典的辦法是給每個(gè)CPU配置兩個(gè)寄存---基址寄存器和界限寄存器?；芳拇嫫饔涗洺绦虻钠鹗嘉锢淼刂?，界限寄存器記錄程序的長(zhǎng)度。

memory.jpg

還是用這個(gè)圖舉例，程序A的基址為0，界限為16384，程序B基址為16384，界限值為32768。每次一個(gè)進(jìn)程訪問(wèn)內(nèi)存時(shí)，取一條指令，讀或?qū)懸粋€(gè)數(shù)據(jù)字，CPU硬件會(huì)把地址發(fā)送到內(nèi)存總線前自動(dòng)把基址值加到進(jìn)程發(fā)出的地址上。比如，進(jìn)程A發(fā)出的訪問(wèn)地址是28，而A的基址是0，那么，A實(shí)際訪問(wèn)的物理地址就是28，而進(jìn)程B的基址為16384，加上28，得到的地址為16412，進(jìn)程B實(shí)際訪問(wèn)的地址是16412.這樣就解決了之前提到過(guò)的絕對(duì)物理地址所帶來(lái)的問(wèn)題。

按照帕金森定律，“不論存儲(chǔ)器有多大，程序都可以把它填滿”。當(dāng)程序大小超過(guò)內(nèi)存容量時(shí)，計(jì)算機(jī)應(yīng)該如何管理內(nèi)存？
有兩種處理內(nèi)存超載的通用方法。一種是交換技術(shù)，即把一個(gè)進(jìn)程完整調(diào)入內(nèi)存，使該進(jìn)程運(yùn)行一段數(shù)據(jù)啊in，然后存回磁盤(pán)?？臻e進(jìn)程主要存在于磁盤(pán)上，所以，當(dāng)他們不運(yùn)行的時(shí)候不會(huì)占用內(nèi)存。另一種是虛擬內(nèi)存，該策略允許程序在只有一部分被調(diào)入內(nèi)存的情況下運(yùn)行。
我們重點(diǎn)關(guān)注虛擬內(nèi)存。大體包含以下內(nèi)容：

• 分頁(yè)
• 頁(yè)面置換算法
• 分頁(yè)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)問(wèn)題
• 分段
• 分段的問(wèn)題
• 分段與分頁(yè)的結(jié)合

虛擬內(nèi)存基本思想是每個(gè)程序都有自己的地址空間，這個(gè)空間被分割成多個(gè)塊。每個(gè)塊稱(chēng)作一頁(yè)或頁(yè)面。每一頁(yè)有連續(xù)的地址范圍。這些頁(yè)被映射到物理內(nèi)存，但是并不是所有的頁(yè)都必須在內(nèi)存中才能運(yùn)行程序。當(dāng)程序引用到一部分在物理內(nèi)存中的地址空間時(shí)，由硬件執(zhí)行必要的映射。當(dāng)程序引用到一部分不在物理內(nèi)存中的的地址空間時(shí)，由操作系統(tǒng)負(fù)責(zé)將缺失的部分裝入物理內(nèi)存并重新執(zhí)行失敗的指令。

• 分頁(yè)：
  1、虛擬地址空間：由程序產(chǎn)生的地址稱(chēng)為虛擬地址，它們構(gòu)成了一個(gè)虛擬地址空間。在使用虛擬內(nèi)存的情況下，虛擬地址被送到內(nèi)存管理單元，然后內(nèi)存管理單元將虛擬地址映射為物理內(nèi)存地址。
  2、虛擬地址空間按照固定大小劃分成稱(chēng)為頁(yè)面的若干單元。在物理內(nèi)存中對(duì)應(yīng)的單元稱(chēng)為頁(yè)框。記錄頁(yè)面與頁(yè)框?qū)?yīng)關(guān)系的叫作頁(yè)表。
  3、舉例說(shuō)明虛擬地址到物理地址的映射過(guò)程：
  a.程序訪問(wèn)如下指令：MOV REG， 0
  b.將虛擬地址送到MMU
  c.MMU通過(guò)虛擬地址找到對(duì)應(yīng)的頁(yè)表項(xiàng),比如虛擬地址0落在頁(yè)表項(xiàng)0（0~4095）
  d.通過(guò)頁(yè)表中虛擬地址與物理地址的映射關(guān)系，找到對(duì)應(yīng)的頁(yè)框，比如頁(yè)框可能是2（8192~12287）。MMU把地址變換為8192，并把地址8192送到總線上。
  這樣就完成了虛擬地址到物理地址的轉(zhuǎn)換。
  4、總結(jié)：虛擬地址被劃分成虛擬頁(yè)號(hào)（高位部分）和偏移量（地位部分）。虛擬頁(yè)號(hào)可以用作頁(yè)表項(xiàng)的索引，以找到虛擬頁(yè)面對(duì)應(yīng)的頁(yè)表項(xiàng)。由頁(yè)表項(xiàng)找到頁(yè)框號(hào)（如果有的話），然后把頁(yè)框號(hào)拼接到 偏移量的高位端，已替換掉虛擬頁(yè)號(hào)，形成物理地址。
  一圖勝千言
  
  address.jpg

• 頁(yè)面置換
  當(dāng)程序訪問(wèn)到一個(gè)未被映射的頁(yè)面時(shí)，就會(huì)引發(fā)缺頁(yè)中斷。操作系統(tǒng)找到一個(gè)頁(yè)框并將它的內(nèi)容寫(xiě)入磁盤(pán)中。然后將需要訪問(wèn)的頁(yè)面讀到剛剛回收的頁(yè)框中，并重新啟引起缺頁(yè)中斷的指令。
  那么，操作系統(tǒng)在選擇頁(yè)框時(shí)，依據(jù)的原則是什么呢？這就是頁(yè)面置換算法。
  1、最優(yōu)頁(yè)面置換算法：替換掉下次訪問(wèn)距離當(dāng)前時(shí)間最長(zhǎng)的頁(yè)框。該算法無(wú)法實(shí)現(xiàn)，因?yàn)楫?dāng)缺頁(yè)中斷發(fā)生時(shí)，操作系統(tǒng)無(wú)法知道下一個(gè)頁(yè)面將在什么時(shí)候被訪問(wèn)
  2、最近未使用頁(yè)面置換算法：替換掉最久沒(méi)有使用的頁(yè)面
  3、先進(jìn)先出頁(yè)面置換算法：這個(gè)很好理解，就是替換掉存在時(shí)間最長(zhǎng)的頁(yè)面。這個(gè)算法有一個(gè)缺點(diǎn)就是可能拋棄重要的頁(yè)面
  4、最近最少使用頁(yè)面置換算法：置換未使用時(shí)間最長(zhǎng)的頁(yè)面。這個(gè)算法非常優(yōu)秀，但是很難實(shí)現(xiàn)。為了完全實(shí)現(xiàn)該算法，需要在內(nèi)存中維護(hù)一個(gè)所有頁(yè)面的鏈表，最近最多使用的頁(yè)面在表頭，最近最少使用的頁(yè)面在表尾。困難的是在每次訪問(wèn)內(nèi)存時(shí)都必須更新整個(gè)鏈表。在鏈表中找到一個(gè)頁(yè)面，刪除它，然后把它移動(dòng)到表頭是一個(gè)非常費(fèi)時(shí)的操作，即使使用硬件實(shí)現(xiàn)也一樣費(fèi)時(shí)。
  5、時(shí)鐘頁(yè)面置換算法：后續(xù)補(bǔ)充。
  6、工作集時(shí)鐘算法：好的有效算法。后續(xù)補(bǔ)充。

• 分頁(yè)置換存在的問(wèn)題
  1、頁(yè)面大小帶來(lái)的問(wèn)題：如果頁(yè)面太大，容易造成內(nèi)部碎片；而頁(yè)面太小，則需要的頁(yè)表越大。

• 分段：
  概念：分段允許程序員將內(nèi)存看成由多個(gè)地址空間或段組成，段的大小是不相等的，并且是動(dòng)態(tài)的。段的優(yōu)點(diǎn)是動(dòng)態(tài)的，比如堆棧段的長(zhǎng)度在數(shù)據(jù)被壓入時(shí)會(huì)增長(zhǎng)，在數(shù)據(jù)被彈出時(shí)會(huì)減小。
  分段系統(tǒng)中的地址轉(zhuǎn)換過(guò)程如下圖
  
  485849422475090016.jpg

• 分段的問(wèn)題：
  1、分段會(huì)造成外部碎片。
  2、如果一個(gè) 段太大，把它整個(gè)保存在內(nèi)存中可能不方便甚至是不可能的

• 段頁(yè)結(jié)合：
  結(jié)合分段與分頁(yè)的優(yōu)點(diǎn)：分頁(yè)對(duì)程序員是透明的，它消除了外部碎片，因而可以更有效地使用內(nèi)存。此外，由于移入或移出內(nèi)存的塊是固定的、大小不等的，因而有可能開(kāi)發(fā)出更精致的存儲(chǔ)管理算法。分段對(duì)程序員是可見(jiàn)的，它具有處理不斷增長(zhǎng)的數(shù)據(jù)結(jié)構(gòu)的能力以及支持共享和保護(hù)的能力。
  段頁(yè)式地址轉(zhuǎn)換過(guò)程如下圖：
  
  507791915898811223.jpg
  
  過(guò)程：
  1、根據(jù)段號(hào)找到段描述符
  2、檢查該段的頁(yè)表是否在內(nèi)存中。如果在，就找到它的位置。如果不在，就產(chǎn)生一個(gè)段錯(cuò)誤。
  3、檢查所請(qǐng)求虛擬頁(yè)面的頁(yè)表項(xiàng)，如果該頁(yè)面不在內(nèi)存中就產(chǎn)生一個(gè)缺頁(yè)中斷，如果在內(nèi)存就從頁(yè)表項(xiàng)中取出這個(gè)頁(yè)面在內(nèi)存中的起始地址。
  4、把偏移量加到頁(yè)面的起始地址上，得到要訪問(wèn)的字在內(nèi)存中的地址。
  5、進(jìn)行讀寫(xiě)操作

至此，對(duì)操作系統(tǒng)中的內(nèi)存管理有了一個(gè)大體的了解，如內(nèi)存模型對(duì)象的發(fā)展過(guò)程，每種內(nèi)存管理的優(yōu)缺點(diǎn)。同時(shí)我感受到了提出問(wèn)題，解決問(wèn)題這條線索也是閱讀計(jì)算機(jī)書(shū)籍的一個(gè)思路。