簡(jiǎn)介

內(nèi)存是計(jì)算機(jī)中最重要的資源之一,通常情況下，物理內(nèi)存無(wú)法容納下所有的進(jìn)程。雖然物理內(nèi)存的增長(zhǎng)現(xiàn)在達(dá)到了N個(gè)GB，但比物理內(nèi)存增長(zhǎng)還快的是程序，所以無(wú)論物理內(nèi)存如何增長(zhǎng)，都趕不上程序增長(zhǎng)的速度，所以操作系統(tǒng)如何有效的管理內(nèi)存便顯得尤為重要。本文講述操作系統(tǒng)對(duì)于內(nèi)存的管理的過(guò)去和現(xiàn)在，以及一些頁(yè)替換的算法的介紹。

對(duì)于進(jìn)程的簡(jiǎn)單介紹

在開(kāi)始之前,首先從操作系統(tǒng)的角度簡(jiǎn)單介紹一下進(jìn)程。進(jìn)程是占有資源的最小單位，這個(gè)資源當(dāng)然包括內(nèi)存。在現(xiàn)代操作系統(tǒng)中，每個(gè)進(jìn)程所能訪問(wèn)的內(nèi)存是互相獨(dú)立的（一些交換區(qū)除外）。而進(jìn)程中的線程所以共享進(jìn)程所分配的內(nèi)存空間。

在操作系統(tǒng)的角度來(lái)看，進(jìn)程=程序+數(shù)據(jù)+PCB(進(jìn)程控制塊)。這個(gè)概念略微有點(diǎn)抽象，我通過(guò)一個(gè)類比來(lái)說(shuō)吧：比如，你正在廚房做飯，你一邊看著菜譜一邊按照菜譜將原料做成菜，就在這時(shí)，你兒子進(jìn)來(lái)告訴你他擦破了腿，此時(shí)你停下手中的工作，將菜譜反扣過(guò)來(lái)，然后找來(lái)急救書(shū)按照書(shū)中的內(nèi)容給你兒子貼上創(chuàng)口貼，貼完后你繼續(xù)會(huì)去打開(kāi)菜譜，然后繼續(xù)做飯。在這個(gè)過(guò)程中，你就好比CPU，菜譜就好比程序，而做菜的原料就好比數(shù)據(jù)。你按照程序指令加工數(shù)據(jù)，而急救工作好比一個(gè)更高優(yōu)先級(jí)的進(jìn)程，中斷了你當(dāng)前做飯的工作,然后你將菜譜反扣過(guò)來(lái)（保護(hù)現(xiàn)場(chǎng)）,轉(zhuǎn)而去處理高優(yōu)先級(jí)的進(jìn)程，處理完畢后你繼續(xù)從剛才的頁(yè)讀菜譜(恢復(fù)現(xiàn)場(chǎng))，然后繼續(xù)執(zhí)行做菜這個(gè)進(jìn)程。

在簡(jiǎn)單介紹完進(jìn)程的概念后，我們來(lái)轉(zhuǎn)入內(nèi)存。

沒(méi)有內(nèi)存抽象的年代

在早些的操作系統(tǒng)中，并沒(méi)有引入內(nèi)存抽象的概念。程序直接訪問(wèn)和操作的都是物理內(nèi)存。比如當(dāng)執(zhí)行如下指令時(shí):

mov reg1,1000

這條指令會(huì)毫無(wú)想象力的將物理地址1000中的內(nèi)容賦值給寄存器。不難想象，這種內(nèi)存操作方式使得操作系統(tǒng)中存在多進(jìn)程變得完全不可能，比如MS-DOS，你必須執(zhí)行完一條指令后才能接著執(zhí)行下一條。如果是多進(jìn)程的話，由于直接操作物理內(nèi)存地址，當(dāng)一個(gè)進(jìn)程給內(nèi)存地址1000賦值后，另一個(gè)進(jìn)程也同樣給內(nèi)存地址賦值，那么第二個(gè)進(jìn)程對(duì)內(nèi)存的賦值會(huì)覆蓋第一個(gè)進(jìn)程所賦的值，這回造成兩條進(jìn)程同時(shí)崩潰。

沒(méi)有內(nèi)存抽象對(duì)于內(nèi)存的管理通常非常簡(jiǎn)單，除去操作系統(tǒng)所用的內(nèi)存之外，全部給用戶程序使用。或是在內(nèi)存中多留一片區(qū)域給驅(qū)動(dòng)程序使用，如圖1所示。

圖1.沒(méi)有內(nèi)存抽象時(shí)，對(duì)內(nèi)存的使用

第一種情況操作系統(tǒng)存于RAM中，放在內(nèi)存的低地址，第二種情況操作系統(tǒng)存在于ROM中，存在內(nèi)存的高地址，一般老式的手機(jī)操作系統(tǒng)是這么設(shè)計(jì)的。

如果這種情況下，想要操作系統(tǒng)可以執(zhí)行多進(jìn)程的話，唯一的解決方案就是和硬盤(pán)搞交換，當(dāng)一個(gè)進(jìn)程執(zhí)行到一定程度時(shí)，整個(gè)存入硬盤(pán)，轉(zhuǎn)而執(zhí)行其它進(jìn)程，到需要執(zhí)行這個(gè)進(jìn)程時(shí)，再?gòu)挠脖P(pán)中取回內(nèi)存，只要同一時(shí)間內(nèi)存中只有一個(gè)進(jìn)程就行，這也就是所謂的交換（Swapping）技術(shù)。但這種技術(shù)由于還是直接操作物理內(nèi)存，依然有可能引起進(jìn)程的崩潰。

所以，通常來(lái)說(shuō)，這種內(nèi)存操作往往只存在于一些洗衣機(jī)，微波爐的芯片中，因?yàn)椴豢赡苡械诙€(gè)進(jìn)程去征用內(nèi)存。

內(nèi)存抽象

在現(xiàn)代的操作系統(tǒng)中，同一時(shí)間運(yùn)行多個(gè)進(jìn)程是再正常不過(guò)的了。為了解決直接操作內(nèi)存帶來(lái)的各種問(wèn)題，引入的地址空間(Address Space),這允許每個(gè)進(jìn)程擁有自己的地址。這還需要硬件上存在兩個(gè)寄存器，基址寄存器(base register)和界址寄存器(limit register),第一個(gè)寄存器保存進(jìn)程的開(kāi)始地址，第二個(gè)寄存器保存上界，防止內(nèi)存溢出。在內(nèi)存抽象的情況下，當(dāng)執(zhí)行

mov reg1,20

這時(shí)，實(shí)際操作的物理地址并不是20，而是根據(jù)基址和偏移量算出實(shí)際的物理地址進(jìn)程操作，此時(shí)操作的實(shí)際地址可能是:

mov reg1,16245

在這種情況下，任何操作虛擬地址的操作都會(huì)被轉(zhuǎn)換為操作物理地址。而每一個(gè)進(jìn)程所擁有的內(nèi)存地址是完全不同的，因此也使得多進(jìn)程成為可能。

但此時(shí)還有一個(gè)問(wèn)題，通常來(lái)說(shuō)，內(nèi)存大小不可能容納下所有并發(fā)執(zhí)行的進(jìn)程。因此，交換(Swapping)技術(shù)應(yīng)運(yùn)而生。這個(gè)交換和前面所講的交換大同小異,只是現(xiàn)在講的交換在多進(jìn)程條件下。交換的基本思想是，將閑置的進(jìn)程交換出內(nèi)存，暫存在硬盤(pán)中，待執(zhí)行時(shí)再交換回內(nèi)存，比如下面一個(gè)例子，當(dāng)程序一開(kāi)始時(shí)，只有進(jìn)程A，逐漸有了進(jìn)程B和C，此時(shí)來(lái)了進(jìn)程D，但內(nèi)存中沒(méi)有足夠的空間給進(jìn)程D，因此將進(jìn)程B交換出內(nèi)存，分給進(jìn)程D。如圖2所示。

圖2.交換技術(shù)

通過(guò)圖2，我們還發(fā)現(xiàn)一個(gè)問(wèn)題，進(jìn)程D和C之間的空間由于太小無(wú)法另任何進(jìn)程使用，這也就是所謂的外部碎片。一種方法是通過(guò)緊湊技術(shù)(Memory Compaction)解決，通過(guò)移動(dòng)進(jìn)程在內(nèi)存中的地址，使得這些外部碎片空間被填滿。還有一些討巧的方法，比如內(nèi)存整理軟件，原理是申請(qǐng)一塊超大的內(nèi)存，將所有進(jìn)程置換出內(nèi)存，然后再釋放這塊內(nèi)存，從而使得重新加載進(jìn)程，使得外部碎片被消除。這也是為什么運(yùn)行完內(nèi)存整理會(huì)狂讀硬盤(pán)的原因。另外，使用緊湊技術(shù)會(huì)非常消耗CPU資源，一個(gè)2G的CPU沒(méi)10ns可以處理4byte,因此多一個(gè)2G的內(nèi)存進(jìn)行一次緊湊可能需要好幾秒的CPU時(shí)間。

上面的理論都是基于進(jìn)程所占的內(nèi)存空間是固定的這個(gè)假設(shè)，但實(shí)際情況下，進(jìn)程往往會(huì)動(dòng)態(tài)增長(zhǎng)，因此創(chuàng)建進(jìn)程時(shí)分配的內(nèi)存就是個(gè)問(wèn)題了，如果分配多了，會(huì)產(chǎn)生內(nèi)部碎片，浪費(fèi)了內(nèi)存，而分配少了會(huì)造成內(nèi)存溢出。一個(gè)解決方法是在進(jìn)程創(chuàng)建的時(shí)候，比進(jìn)程實(shí)際需要的多分配一點(diǎn)內(nèi)存空間用于進(jìn)程的增長(zhǎng)。一種是直接多分配一點(diǎn)內(nèi)存空間用于進(jìn)程在內(nèi)存中的增長(zhǎng)，另一種是將增長(zhǎng)區(qū)分為數(shù)據(jù)段和棧（用于存放返回地址和局部變量）,如圖3所示。

圖3.創(chuàng)建進(jìn)程時(shí)預(yù)留空間用于增長(zhǎng)

當(dāng)預(yù)留的空間不夠滿足增長(zhǎng)時(shí)，操作系統(tǒng)首先會(huì)看相鄰的內(nèi)存是否空閑，如果空閑則自動(dòng)分配，如果不空閑，就將整個(gè)進(jìn)程移到足夠容納增長(zhǎng)的空間內(nèi)存中，如果不存在這樣的內(nèi)存空間，則會(huì)將閑置的進(jìn)程置換出去。

當(dāng)允許進(jìn)程動(dòng)態(tài)增長(zhǎng)時(shí)，操作系統(tǒng)必須對(duì)內(nèi)存進(jìn)行更有效的管理，操作系統(tǒng)使用如下兩種方法之一來(lái)得知內(nèi)存的使用情況，分別為1)位圖(bitmap) 2)鏈表

使用位圖，將內(nèi)存劃為多個(gè)大小相等的塊，比如一個(gè)32K的內(nèi)存1K一塊可以劃為32塊，則需要32位（4字節(jié)）來(lái)表示其使用情況，使用位圖將已經(jīng)使用的塊標(biāo)為1，未使用的標(biāo)為0.而使用鏈表，則將內(nèi)存按使用或未使用分為多個(gè)段進(jìn)行連接，這個(gè)概念如圖4所示。

圖4.位圖和鏈表表示內(nèi)存的使用情況

使用鏈表中的P表示進(jìn)程，從0-2是進(jìn)程，H表示空閑，從3-4表示是空閑。

使用位圖表示內(nèi)存簡(jiǎn)單明了，但一個(gè)問(wèn)題是當(dāng)分配內(nèi)存時(shí)必須在內(nèi)存中搜索大量的連續(xù)0的空間，這是十分消耗資源的操作。相比之下，使用鏈表進(jìn)行此操作將會(huì)更勝一籌。還有一些操作系統(tǒng)會(huì)使用雙向鏈表，因?yàn)楫?dāng)進(jìn)程銷毀時(shí)，鄰接的往往是空內(nèi)存或是另外的進(jìn)程。使用雙向鏈表使得鏈表之間的融合變得更加容易。

還有，當(dāng)利用鏈表管理內(nèi)存的情況下，創(chuàng)建進(jìn)程時(shí)分配什么樣的空閑空間也是個(gè)問(wèn)題。通常情況下有如下幾種算法來(lái)對(duì)進(jìn)程創(chuàng)建時(shí)的空間進(jìn)行分配。

• 臨近適應(yīng)算法(Next fit)---從當(dāng)前位置開(kāi)始，搜索第一個(gè)能滿足進(jìn)程要求的內(nèi)存空間
• 最佳適應(yīng)算法(Best fit)---搜索整個(gè)鏈表，找到能滿足進(jìn)程要求最小內(nèi)存的內(nèi)存空間
• 最大適應(yīng)算法(Wrost fit)---找到當(dāng)前內(nèi)存中最大的空閑空間
• 首次適應(yīng)算法(First fit) ---從鏈表的第一個(gè)開(kāi)始，找到第一個(gè)能滿足進(jìn)程要求的內(nèi)存空間

虛擬內(nèi)存(Virtual Memory)

虛擬內(nèi)存是現(xiàn)代操作系統(tǒng)普遍使用的一種技術(shù)。前面所講的抽象滿足了多進(jìn)程的要求，但很多情況下，現(xiàn)有內(nèi)存無(wú)法滿足僅僅一個(gè)大進(jìn)程的內(nèi)存要求(比如很多游戲，都是10G+的級(jí)別)。在早期的操作系統(tǒng)曾使用覆蓋(overlays)來(lái)解決這個(gè)問(wèn)題，將一個(gè)程序分為多個(gè)塊，基本思想是先將塊0加入內(nèi)存，塊0執(zhí)行完后，將塊1加入內(nèi)存。依次往復(fù)，這個(gè)解決方案最大的問(wèn)題是需要程序員去程序進(jìn)行分塊，這是一個(gè)費(fèi)時(shí)費(fèi)力讓人痛苦不堪的過(guò)程。后來(lái)這個(gè)解決方案的修正版就是虛擬內(nèi)存。

虛擬內(nèi)存的基本思想是，每個(gè)進(jìn)程有用獨(dú)立的邏輯地址空間，內(nèi)存被分為大小相等的多個(gè)塊,稱為頁(yè)(Page).每個(gè)頁(yè)都是一段連續(xù)的地址。對(duì)于進(jìn)程來(lái)看,邏輯上貌似有很多內(nèi)存空間，其中一部分對(duì)應(yīng)物理內(nèi)存上的一塊(稱為頁(yè)框，通常頁(yè)和頁(yè)框大小相等)，還有一些沒(méi)加載在內(nèi)存中的對(duì)應(yīng)在硬盤(pán)上，如圖5所示。

圖5.虛擬內(nèi)存和物理內(nèi)存以及磁盤(pán)的映射關(guān)系

由圖5可以看出，虛擬內(nèi)存實(shí)際上可以比物理內(nèi)存大。當(dāng)訪問(wèn)虛擬內(nèi)存時(shí)，會(huì)訪問(wèn)MMU（內(nèi)存管理單元）去匹配對(duì)應(yīng)的物理地址（比如圖5的0，1，2），而如果虛擬內(nèi)存的頁(yè)并不存在于物理內(nèi)存中（如圖5的3,4），會(huì)產(chǎn)生缺頁(yè)中斷，從磁盤(pán)中取得缺的頁(yè)放入內(nèi)存，如果內(nèi)存已滿，還會(huì)根據(jù)某種算法將磁盤(pán)中的頁(yè)換出。

而虛擬內(nèi)存和物理內(nèi)存的匹配是通過(guò)頁(yè)表實(shí)現(xiàn)，頁(yè)表存在MMU中，頁(yè)表中每個(gè)項(xiàng)通常為32位，即4byte,除了存儲(chǔ)虛擬地址和頁(yè)框地址之外，還會(huì)存儲(chǔ)一些標(biāo)志位，比如是否缺頁(yè)，是否修改過(guò)，寫(xiě)保護(hù)等。可以把MMU想象成一個(gè)接收虛擬地址項(xiàng)返回物理地址的方法。

因?yàn)轫?yè)表中每個(gè)條目是4字節(jié)，現(xiàn)在的32位操作系統(tǒng)虛擬地址空間會(huì)是2的32次方，即使每頁(yè)分為4K，也需要2的20次方*4字節(jié)=4M的空間，為每個(gè)進(jìn)程建立一個(gè)4M的頁(yè)表并不明智。因此在頁(yè)表的概念上進(jìn)行推廣，產(chǎn)生二級(jí)頁(yè)表,二級(jí)頁(yè)表每個(gè)對(duì)應(yīng)4M的虛擬地址，而一級(jí)頁(yè)表去索引這些二級(jí)頁(yè)表，因此32位的系統(tǒng)需要1024個(gè)二級(jí)頁(yè)表，雖然頁(yè)表?xiàng)l目沒(méi)有減少，但內(nèi)存中可以僅僅存放需要使用的二級(jí)頁(yè)表和一級(jí)頁(yè)表，大大減少了內(nèi)存的使用。

頁(yè)面替換算法

因?yàn)樵谟?jì)算機(jī)系統(tǒng)中，讀取少量數(shù)據(jù)硬盤(pán)通常需要幾毫秒，而內(nèi)存中僅僅需要幾納秒。一條CPU指令也通常是幾納秒，如果在執(zhí)行CPU指令時(shí)，產(chǎn)生幾次缺頁(yè)中斷，那性能可想而知，因此盡量減少?gòu)挠脖P(pán)的讀取無(wú)疑是大大的提升了性能。而前面知道，物理內(nèi)存是極其有限的，當(dāng)虛擬內(nèi)存所求的頁(yè)不在物理內(nèi)存中時(shí)，將需要將物理內(nèi)存中的頁(yè)替換出去，選擇哪些頁(yè)替換出去就顯得尤為重要，如果算法不好將未來(lái)需要使用的頁(yè)替換出去，則以后使用時(shí)還需要替換進(jìn)來(lái)，這無(wú)疑是降低效率的，讓我們來(lái)看幾種頁(yè)面替換算法。