前言
在操作系統(tǒng)出現(xiàn)之前，程序曾經(jīng)存放在卡片上，計(jì)算機(jī)每讀一張卡片，就運(yùn)行一條指令，這個(gè)時(shí)候程序是直接從卡片到執(zhí)行；但這種從外部存儲(chǔ)媒介上直接執(zhí)行指令的做法效率極低，且靈活性很差，一次只能一個(gè)卡片來(lái)處理；因此人們發(fā)明了內(nèi)存存儲(chǔ)器，來(lái)將需要運(yùn)行的程序先行加載，再自動(dòng)執(zhí)行，從而提高效率和靈活性。 由于內(nèi)存的出現(xiàn)，出現(xiàn)了“存儲(chǔ)的程序”概念的出現(xiàn)，而存儲(chǔ)的程序概念又導(dǎo)致計(jì)算機(jī)及軟件系統(tǒng)的革命性變化，此后人們對(duì)內(nèi)存的要求越來(lái)越高。
背景
理想的情況下，程序員或用戶對(duì)內(nèi)存的要求是：大容量，高速度和持久性。但程序員面臨的物理現(xiàn)實(shí)卻是一個(gè)由緩存、主存、硬盤(pán)等組成的內(nèi)存架構(gòu)。 緩存的特點(diǎn)：低容量、高速度、高價(jià)格； 主存的特點(diǎn)：中容量、中速度、中價(jià)格； 硬盤(pán)的特點(diǎn)：大容量、低速度、低成本； 這樣的存儲(chǔ)架構(gòu)和程序員、用戶的期望相差較大；要以現(xiàn)在的架構(gòu)為程序員所需的內(nèi)存抽象，需要一個(gè)巧妙有效的內(nèi)存管理機(jī)制。
內(nèi)存管理相關(guān)
內(nèi)存管理把緩存、主存、硬盤(pán)都當(dāng)成一樣的內(nèi)存，因?yàn)椴还苡脩舻某绦蚴窃诰彺孢€是在主存或者硬盤(pán)，反正運(yùn)行計(jì)算輸出結(jié)果都是一樣的。 內(nèi)存管理怎么把緩存、主存和硬盤(pán)當(dāng)成是一樣的呢？？？這個(gè)時(shí)候就需要抽象（就像人類喜歡把香蕉和桃子都叫做水果），緩存、主存和硬盤(pán)被抽象為“虛擬內(nèi)存”；通過(guò)虛擬內(nèi)存，程序員和用戶不關(guān)心底層的實(shí)現(xiàn)，只知道程序存在虛擬內(nèi)存中。 虛擬內(nèi)存本身獨(dú)立于物理內(nèi)存，因此概念提出的瞬間，內(nèi)存管理機(jī)制便天然擁有一個(gè)目標(biāo)：地址獨(dú)立。那內(nèi)存管理機(jī)制還有沒(méi)有其他目標(biāo)了？？？ 在當(dāng)今的多道程序操作系統(tǒng)中，虛擬內(nèi)存中會(huì)運(yùn)行著大量的程序，程序與程序之間是要相互獨(dú)立的，因此內(nèi)存管理的另一個(gè)目標(biāo)就在于地址保護(hù)：一個(gè)程序不能去訪問(wèn)另一個(gè)程序的內(nèi)存地址。 由于虛擬內(nèi)存屏蔽了緩存、主存、硬盤(pán)的差異性，因此虛擬內(nèi)存可以看做是操作系統(tǒng)提供的大容量，高速度的內(nèi)存。 本文從種地的角度來(lái)解釋操作系統(tǒng)內(nèi)存管理機(jī)制的演變以及演變中的哲學(xué)原理，知識(shí)來(lái)源于生活。
種地（本故事純屬虛構(gòu)）
漢朝時(shí)期，老王出身貧寒，遂從軍，歷時(shí)十載，軍功赫赫，國(guó)內(nèi)一片繁榮；老王怕功高震主，遂請(qǐng)辭回家養(yǎng)老，由于老王的軍功，皇帝賜了一塊封地給他頤養(yǎng)天年；老王美滋滋的踏上了去封地的旅程~~ 老王到了封地，果然是一片很大的封地，但是一片荒涼，啥都沒(méi)有；老王把這塊地叫做“物理內(nèi)存”，給它標(biāo)記了地址，一開(kāi)始的地址為0，不停的增長(zhǎng)到封地盡頭N；
蓋房子（操作系統(tǒng)內(nèi)存位置）
老王決定先建一個(gè)房子住，不然都沒(méi)地方住，他把自己的房子命名為“操作系統(tǒng)”；問(wèn)題產(chǎn)生了：房子建在哪邊（操作系統(tǒng)應(yīng)該放在物理內(nèi)存哪邊）？可以是地址0~N的任何地址位置。 計(jì)算機(jī)中的清零操作很方便，并且開(kāi)始地址0很容易索引，因此老王決定把操作系統(tǒng)建在地址0處。
老王未雨綢繆，怕將來(lái)有仇家尋上門(mén)，因此在房子下面建立了地下密室，用于藏身，命名為ROM； 計(jì)算機(jī)體系中分為RAM和ROM，物理內(nèi)存就是RAM，RAM斷電內(nèi)容消失，因此操作系統(tǒng)一部分是放在ROM上，另一部分加載到RAM中。 最后，老王的房子分為了地上的部分和地下密室的部分。
單一作物（單道編程）
老王很喜歡吃土豆，因此老王決定挑選一塊地種土豆；這個(gè)時(shí)候封地上除了房子只有一個(gè)農(nóng)作物：土豆；相當(dāng)于計(jì)算機(jī)中的單道編程，用戶程序永遠(yuǎn)只有一個(gè)；這樣老王可以隨機(jī)挑選一個(gè)固定的地址T；每次在T地址上種植土豆；這種運(yùn)行前即將物理地址計(jì)算好的方式叫做“靜態(tài)地址翻譯”。這種情況下，虛擬地址永遠(yuǎn)映射到固定的物理內(nèi)存地址上；因此單道編程的情況下很容易達(dá)到內(nèi)存管理機(jī)制的兩個(gè)目標(biāo)。
單道編程的缺點(diǎn)很多，只能運(yùn)行一個(gè)程序，并行度很低；此外加載程序的大小不能超過(guò)物理內(nèi)存空間；而且程序不能移植到不同的操作系統(tǒng)，因?yàn)椴煌僮飨到y(tǒng)的內(nèi)存空間大小不一樣。
多個(gè)作物（多道編程）
老王吃多了土豆，生病了，大夫讓老王吃點(diǎn)其他蔬菜，營(yíng)養(yǎng)均衡，因此老王想在土豆的基礎(chǔ)上種植其他的蔬菜（青菜，番茄等。。。）；老王也不知道要吃多少中蔬菜才能補(bǔ)營(yíng)養(yǎng)，因此老王不能很好的規(guī)劃種植的地址；
因?yàn)槎嗟谰幊痰那闆r下，程序無(wú)法再加載到固定的內(nèi)存地址上，這就無(wú)法使用靜態(tài)地址翻譯；計(jì)算機(jī)必須在程序加載完畢后才能計(jì)算物理地址，這種就叫做“動(dòng)態(tài)地址翻譯”。
固定分區(qū)
面對(duì)如此多的蔬菜作物，老王想了個(gè)辦法，一批批的補(bǔ)充營(yíng)養(yǎng)；老王將封地分為大小不同的分區(qū)（為啥大小不同，因?yàn)橛行├贤鯋?ài)吃，多種點(diǎn)），分區(qū)數(shù)為M；不同的分區(qū)種上不同的蔬菜；這樣封地有多少分區(qū)，老王就可以種多少蔬菜，等其中分區(qū)的蔬菜吃完就可以在分區(qū)種另一種蔬菜。
計(jì)算機(jī)系統(tǒng)將內(nèi)存分為大小不同的多個(gè)分區(qū)；因?yàn)槌绦虻拇笮〔煌?，不同的程序分配到不同的分區(qū)；操作系統(tǒng)用一個(gè)隊(duì)列保存了操作系統(tǒng)的程序，當(dāng)有空白分區(qū)的時(shí)候，把程序加入空白分區(qū)里； 老王知道喜愛(ài)的菜多種些，讓分區(qū)物盡其用；但是計(jì)算機(jī)如果把小程序分配到大分區(qū)里，會(huì)造成大量空間的浪費(fèi)；因此可以每個(gè)分區(qū)都有自己獨(dú)立的隊(duì)列，把適合該分區(qū)的程序存放在隊(duì)列中，當(dāng)分區(qū)空白時(shí)，加載相應(yīng)的程序，這樣空間浪費(fèi)率相對(duì)低點(diǎn)。 不管是單隊(duì)列，還是分區(qū)多隊(duì)列，都有很大的問(wèn)題，但隊(duì)列的話，會(huì)造成大量的空間浪費(fèi)；多隊(duì)列會(huì)造成有空白分區(qū)，但是其他隊(duì)列的程序再等待，不能運(yùn)行。
那固定分區(qū)的這種情況下，老王怎么統(tǒng)計(jì)農(nóng)作物的地址；老王記錄了每個(gè)分區(qū)在封地的起始地址；然后記錄了農(nóng)作物在分區(qū)里的虛擬地址；因此封地的物理地址=虛擬地址+分區(qū)的起始地址。
這就是固定分區(qū)，計(jì)算機(jī)的地址翻譯；對(duì)于內(nèi)存管理的兩個(gè)目標(biāo)，地址保護(hù)可以通過(guò)地址翻譯來(lái)判斷程序是否超出了分區(qū)的地址；因此計(jì)算機(jī)只需要保存一個(gè)基址和一個(gè)極限就可以達(dá)到地址保護(hù)的目的；可以通過(guò)基址寄存器和極限寄存器來(lái)保存；地址獨(dú)立是虛擬內(nèi)存自帶的概念；因此固定分區(qū)完全符合內(nèi)存管理的設(shè)計(jì)。
非固定分區(qū)
經(jīng)過(guò)了固定分區(qū)的規(guī)劃，老王美滋滋的幻想起了以后美好的生活；但是老王忽略了一點(diǎn)，就是自己的種植能力；大的分區(qū)全種植了自己愛(ài)吃的番茄，但由于自己種植不當(dāng)，大部分番茄沒(méi)長(zhǎng)出來(lái)，今年造成了大量的土地浪費(fèi)；老王很心痛，痛則思變； 老王想了很久，還是決定靈活處理，不固定分區(qū)，而是把封地除了操作系統(tǒng)房子外都當(dāng)成一個(gè)整體；如果要種青菜，則分出一塊地中青菜；如果又要種番茄，則在剩下的封地中再分出一塊地種番茄；依次類推，當(dāng)?shù)夭蛔銜r(shí)，就等其中的蔬菜成熟收割后，把地空出來(lái)后再種剩下的蔬菜。 老王一想，這樣就不會(huì)有地浪費(fèi)了，當(dāng)種不出來(lái)的時(shí)候，老王就可以種其他蔬菜，充分利用封地；
老王的思想在操作系統(tǒng)中叫做非固定分區(qū)內(nèi)存管理；當(dāng)程序來(lái)的時(shí)候，會(huì)在空白內(nèi)存中挑選一塊給程序執(zhí)行。 由于固定分區(qū)的時(shí)候我們知道，用基址和極限兩個(gè)寄存器就可以表示每個(gè)程序的位置；因此在非固定分區(qū)下，為每個(gè)程序配置基址和極限寄存器就可以識(shí)別程序的物理地址。
乍一看，好像問(wèn)題都解決了，但是老王忽略了一個(gè)很?chē)?yán)重的問(wèn)題；有些蔬菜有很強(qiáng)的侵略性，像蒲公英一樣，種子會(huì)到處傳播；導(dǎo)致其他土地上也長(zhǎng)滿這樣的蔬菜，這樣就不能很好的隔開(kāi)種植，規(guī)劃封地了。
計(jì)算機(jī)程序在運(yùn)行過(guò)程中，會(huì)出現(xiàn)動(dòng)態(tài)增長(zhǎng)的情況；程序空間增值的主要來(lái)源：數(shù)據(jù)和棧。那么怎么處理程序的增長(zhǎng)呢？？？ 解決辦法就是為增長(zhǎng)的程序預(yù)留出增長(zhǎng)的空間，因此數(shù)據(jù)和棧的增長(zhǎng)就如圖所示。 數(shù)據(jù)和棧增長(zhǎng)的方向可以是相同，也可以是相反；誕生不同的策略。
預(yù)留空間是正常的做法，就像生活中不知道數(shù)量的情況下會(huì)多留點(diǎn)空間；但是這個(gè)有個(gè)致命的缺點(diǎn)，就是很難預(yù)測(cè)究竟需要預(yù)留多大的空間，預(yù)留多了是種浪費(fèi)；預(yù)留少了沒(méi)解決根本問(wèn)題；老王苦思冥想，終于想出了個(gè)辦法，參考家里的密室，橫截面不能擴(kuò)張，那就往高度上擴(kuò)張；老王在土地上搭建一層架子，架子上也鋪上土，當(dāng)種菜溢出自己地盤(pán)的時(shí)候，就把蔬菜移植到架子上面，這樣就便于管理了。
那類比到計(jì)算機(jī)系統(tǒng)中，內(nèi)存地址不夠了怎么辦？？？我們不能在上面搭建一層架子；但是我們考慮搭建架子的本質(zhì)是把蔬菜放到另一片內(nèi)存中，相當(dāng)于擴(kuò)展了內(nèi)存，因此我們想起來(lái)硬盤(pán)；我們可以把程序整個(gè)加載到硬盤(pán)上，當(dāng)物理內(nèi)存有足夠的空間時(shí)，再把程序加載回內(nèi)存運(yùn)行，這就是所謂的“交換”。 交換的這種方式存在這很大的問(wèn)題，一個(gè)程序被置換出去后，不知道要等多久才能等到足夠的空間運(yùn)行；效率低下；還有個(gè)問(wèn)題，如果超出了整個(gè)物理內(nèi)存，再怎么置換也沒(méi)用。 如果可以把程序變成一個(gè)個(gè)可執(zhí)行的單元，執(zhí)行完一個(gè)單元，后面的單元就把前面單元地址覆蓋掉；這樣就不會(huì)出現(xiàn)程序空間不夠的情況，這個(gè)辦法就是所謂的“重疊”；但是程序的切分需要用戶管控，相當(dāng)于把內(nèi)存管理機(jī)制暴露給了用戶，這是很危險(xiǎn)的，這個(gè)辦法行不通。
閑置空間管理
老王是個(gè)追求完美的人，他種了很多蔬菜，但是封地依然有很多沒(méi)有利用的空地，老王需要很好的統(tǒng)計(jì)，規(guī)劃這些空地。老王想了良兩種辦法： （1）位圖法： 老王為每個(gè)種植蔬菜的地址單元分配一個(gè)字位，用1表示已占用；0表示空閑，這樣就形成了一個(gè)位圖；0表示所有的空閑地址；當(dāng)空閑地址種植蔬菜時(shí)，由0改為1，變成已占用；當(dāng)蔬菜生熟收割后，地址回收，相應(yīng)的字位由1變?yōu)?，表示空閑。 （2）鏈表法： 老王將分配的地址用鏈表連接在一起；比如，青菜-->空地-->番茄-->空地；每個(gè)節(jié)點(diǎn)記錄節(jié)點(diǎn)的地址；當(dāng)需要種植蔬菜時(shí)，則遍歷鏈表找到空閑的地址種植，鏈表進(jìn)行相應(yīng)的修改。
問(wèn)題暴露
經(jīng)歷了一年的時(shí)光，老王也種植了一年蔬菜，老王決定做下總結(jié)，把經(jīng)驗(yàn)分享給后來(lái)人；從固定分區(qū)到非固定分區(qū)到交換內(nèi)存管理；固定分區(qū)用于單道編程，而非固定分區(qū)和交換等用于多道編程，實(shí)現(xiàn)方式都是基于基址和極限的做法。 老王總結(jié)了半天，根據(jù)統(tǒng)計(jì)：不管是固定分區(qū)，還是非固定分區(qū)；這些策略都存在著重大的問(wèn)題；其中最重要的就是空間浪費(fèi)和程序大小受限。隨著不停的回收分配，內(nèi)存中的碎片越來(lái)越多；很多小碎片無(wú)法滿足種植的需求，浪費(fèi)了；
由于這些碎片處于進(jìn)程空間的外面，因此這種碎片化過(guò)程也叫做“外部碎片化”。隨著進(jìn)程的進(jìn)進(jìn)出出，外部碎片將浪費(fèi)大量的內(nèi)存空間；當(dāng)然可以采取一定的策略降低外部碎片，比如每次分配新進(jìn)程的時(shí)候，挑選最合適的空間分配，這可以在一定程度上減輕外部碎片。 還有種辦法是可以進(jìn)行碎片整理，通過(guò)交換，把碎片合并在一起；但交換效率非常低。
分頁(yè)管理
上述整個(gè)的做法，都是把程序整個(gè)加載到內(nèi)存里。老王把整個(gè)區(qū)域都種植一種蔬菜，但是每種蔬菜的種子數(shù)量不相同，這就會(huì)導(dǎo)致外部碎片的存在；老王想到了一種辦法，為啥每次都要以蔬菜種子的數(shù)量來(lái)要求土地，而不是用土地來(lái)要求蔬菜種子的數(shù)量。
想到這里，老王開(kāi)始實(shí)施自己的想法，他把整個(gè)封地按照一定的大小，劃分成很多塊，每一小塊叫做一個(gè)分頁(yè)。此外，上述程序增長(zhǎng)的極限在于物理內(nèi)存的大小；如果一部分一部分的加載程序，程序的增長(zhǎng)極限就被擴(kuò)大了。
有了分頁(yè)之后，老王的種植變的更加容易管理；他可以在每一頁(yè)上種植任何自己想吃的蔬菜；比如在第1號(hào)頁(yè)上種植土豆，在第2號(hào)頁(yè)上種植番茄，如果老王需要土豆種植量增大，但又沒(méi)有額外空間了，那么可以把2號(hào)頁(yè)上的番茄移植成土豆。
在計(jì)算機(jī)操作系統(tǒng)中；程序被分成一頁(yè)頁(yè)的，每個(gè)程序都可以運(yùn)行一部分頁(yè)在內(nèi)存中，當(dāng)需要運(yùn)行程序其他部分時(shí)，會(huì)把其他也加載到內(nèi)存；如果沒(méi)有額外的內(nèi)存空間，則會(huì)把當(dāng)前一些頁(yè)置換到硬盤(pán)中，空出內(nèi)存給運(yùn)行的程序使用；這種方法下，程序可以超出物理內(nèi)存實(shí)際的限制大小。
分頁(yè)地址翻譯
有了分頁(yè)后，老王如果管理這些分頁(yè)，并且知道每個(gè)分頁(yè)上種植的蔬菜，而不是每天都要走一遍整個(gè)封地。老王對(duì)頁(yè)面進(jìn)行編號(hào)，從0開(kāi)始；從上述的基址和極限，我們知道，分頁(yè)的地址主要分為兩塊：頁(yè)面號(hào)和頁(yè)內(nèi)偏移地址。
分頁(yè)系統(tǒng)首先要知道的是該頁(yè)面是否存在物理內(nèi)存中，如果存在，對(duì)應(yīng)的物理頁(yè)面號(hào)是哪個(gè)？如果不存在，則產(chǎn)生缺頁(yè)中斷，并將虛頁(yè)從磁盤(pán)加載到內(nèi)存，然后將分配的物理頁(yè)面號(hào)返回。 由于虛頁(yè)和物理內(nèi)存真實(shí)的頁(yè)面是同樣大小，因此地址翻譯只需要把虛頁(yè)轉(zhuǎn)換到物理頁(yè)，頁(yè)內(nèi)偏移地址無(wú)需改變。 分頁(yè)內(nèi)存管理中，不光需要知道頁(yè)號(hào)，還需要知道該頁(yè)面是否在物理內(nèi)存中；此外頁(yè)面有沒(méi)有修改過(guò)，有沒(méi)有被訪問(wèn)過(guò)，都需要保存這些信息；因此誕生了頁(yè)表的概念； 頁(yè)表在內(nèi)存管理的地位十分重要，根本功能是提供從虛擬頁(yè)面到物理頁(yè)面的映射。比如32位尋址的虛擬地址，如果頁(yè)面大小為4KB，則虛擬頁(yè)面最多可以達(dá)到
，也就是頁(yè)表記錄條數(shù)最大為：
現(xiàn)在老王有了自己的頁(yè)表，頁(yè)表里記錄了虛擬頁(yè)面號(hào)到物理頁(yè)面號(hào)的映射，并且記錄了頁(yè)面的偏移地址；比如老王的頁(yè)面上記載了虛擬頁(yè)面0種植了土豆，并且土豆的偏移地址為頁(yè)面的一半；這條記錄就代表了物理頁(yè)面a上面種植了土豆，并且整個(gè)頁(yè)面從起始地址到頁(yè)面一半處種植了土豆，剩余的一半頁(yè)面空閑著；
通過(guò)這個(gè)案例，可以看出，分頁(yè)管理把外部的碎片轉(zhuǎn)移到了頁(yè)內(nèi)，由于分頁(yè)的粒度比分區(qū)的更細(xì)，從數(shù)學(xué)上看，平均浪費(fèi)空間為半個(gè)分頁(yè)，因此浪費(fèi)的空間比分區(qū)要好很多。
那分頁(yè)系統(tǒng)還有其他缺點(diǎn)嗎？？？ 有，缺點(diǎn)就是頁(yè)表很大，占用了大量的內(nèi)存空間。漢朝沒(méi)有紙張，都是通過(guò)竹簡(jiǎn)和綿帛來(lái)記錄的，老王一窮二白，只有封地，因此只能把頁(yè)表記錄在土地上；因此頁(yè)表太大也會(huì)占用大量的內(nèi)存空間。
頁(yè)表
老王參考分頁(yè)的做法，把頁(yè)表也進(jìn)行了分頁(yè)；就是“多級(jí)頁(yè)表”的概念。
操作系統(tǒng)中，頂級(jí)頁(yè)表映射到一級(jí)頁(yè)表，然后一級(jí)頁(yè)表映射到二級(jí)頁(yè)表，依次映射；這樣當(dāng)加載頁(yè)表時(shí)，可以先加載頂級(jí)頁(yè)表，根據(jù)一層層映射把需要的頁(yè)表加載到內(nèi)存，不用的頁(yè)表放在硬盤(pán)上，這樣就可以支持多級(jí)頁(yè)表； 但是多級(jí)頁(yè)表增加了地址翻譯的次數(shù)，每次操作數(shù)據(jù)，都需要進(jìn)行多級(jí)的地址翻譯；內(nèi)存訪問(wèn)的速度明顯下降。 多級(jí)頁(yè)表通過(guò)增加級(jí)數(shù)來(lái)降低頁(yè)表的內(nèi)存空間；有辦法不增加級(jí)數(shù)來(lái)降低頁(yè)表的內(nèi)存空間嗎？？？使用反轉(zhuǎn)頁(yè)表，正常頁(yè)表存儲(chǔ)的是虛擬內(nèi)存到物理內(nèi)存的映射，但是虛擬內(nèi)存空間要遠(yuǎn)遠(yuǎn)大于物理內(nèi)存；這個(gè)時(shí)候反轉(zhuǎn)頁(yè)表，保存物理內(nèi)存到虛擬內(nèi)存的映射，由于物理內(nèi)存較小，這樣空間大大減少；但是CPU發(fā)出的地址是虛擬地址，反轉(zhuǎn)列表造成了查詢的困難；這時(shí)候可以通過(guò)虛擬頁(yè)面到物理頁(yè)面的散列來(lái)提升查詢效率。 頁(yè)表的形式也是不斷的演變，針對(duì)不同的系統(tǒng)需求頁(yè)表會(huì)有不同的演變需求。
翻譯快表
在多級(jí)頁(yè)表的情況下，地址翻譯的速度大大降低，影響了內(nèi)存的訪問(wèn)速度；由于程序的時(shí)空局限性，我們可以將頁(yè)表的翻譯結(jié)果存在緩存中，緩存的速度要高于內(nèi)存的速度，在緩存命中的情況下，內(nèi)存的讀寫(xiě)速度將會(huì)提高；這種將翻譯結(jié)果放在緩存的結(jié)果，就叫“翻譯快表”。在翻譯快表的情況下，如果快速的查找到虛擬頁(yè)面是否存在翻譯快表中；這個(gè)時(shí)候只能一個(gè)記錄一個(gè)記錄的按順序查詢，如果翻譯快表中不存在頁(yè)面，則每次都需要按順序查詢；時(shí)間消耗巨大。 基于這種情況，軟件已經(jīng)無(wú)法解決根本問(wèn)題，只能把問(wèn)題交給硬件；硬件為每條記錄配備一套電路，當(dāng)翻譯快表比對(duì)時(shí)，是同一時(shí)間比對(duì)所有記錄；這樣會(huì)在第一時(shí)間獲得比對(duì)結(jié)果。
頁(yè)面更換算法
老王現(xiàn)在已經(jīng)有了頁(yè)表，有了頁(yè)面內(nèi)存管理；老王又出現(xiàn)了一個(gè)問(wèn)題：土地有了，房子有了，蔬菜也有了，但是沒(méi)有錢(qián)，買(mǎi)不了衣服等生活用品；為了賺更多的錢(qián)滿足生活需要，老王決定把種的蔬菜賣(mài)掉；為了利益最大化，老王需要賣(mài)掉當(dāng)季流行的蔬菜，但當(dāng)季流行的蔬菜變化很快；老王需要一種策略可以很快的替換頁(yè)面，種植流行的蔬菜。
老王的問(wèn)題就涉及到了頁(yè)面置換算法，頁(yè)面置換算法的根本目的，是要增加頁(yè)面的命中率；從人類哲學(xué)的層次來(lái)看，頁(yè)面置換算法主要分為兩類：公平算法和非公平算法。 公平算法：
隨機(jī)算法
先來(lái)先出算法
第二次機(jī)會(huì)算法
時(shí)鐘算法
非公平算法：
最有算法
NRU算法
LRU算法
工作集算法
這些算法就不一一解釋了。
段式內(nèi)存管理
老王把封地管理的有條不紊；分頁(yè)內(nèi)存管理被老王用的爐火純青；一切都很順利，但是這個(gè)時(shí)候問(wèn)題又來(lái)了；老王又病了，大夫說(shuō)長(zhǎng)期不吃肉，抵抗力下降。老王尋思著大夫的話，決定在封地上養(yǎng)寫(xiě)雞鴨。 于是，老王劃了兩塊連在一起的地來(lái)養(yǎng)雞鴨；雞鴨各占一塊；由于缺少養(yǎng)家禽的經(jīng)驗(yàn)，雞鴨繁殖的速度很快，導(dǎo)致劃分的土地不夠雞鴨生存，雞鴨把周?chē)氖卟硕荚闾Ａ恕?/p>
在操作系統(tǒng)中，編譯器的工作過(guò)程經(jīng)常需要保持多個(gè)數(shù)據(jù)結(jié)構(gòu)：常數(shù)表，語(yǔ)法分析樹(shù)，代碼段，調(diào)用棧等；每個(gè)數(shù)據(jù)結(jié)構(gòu)都是獨(dú)立的增長(zhǎng)，從而造成了內(nèi)存空間的變化。如果編譯器只在一個(gè)虛擬空間中活動(dòng)，那么所有數(shù)據(jù)結(jié)構(gòu)的增長(zhǎng)可能會(huì)相互碰撞，導(dǎo)致無(wú)法增長(zhǎng)，編譯失敗。 這就是分頁(yè)系統(tǒng)的缺點(diǎn)；虛擬空間的大小受尋址寬度的限制而無(wú)法增長(zhǎng)；那剩下的辦法就是讓一個(gè)程序使用多個(gè)虛擬空間。
老王把封地參考分區(qū)的做法，分為多個(gè)段；一個(gè)段占用一個(gè)虛擬地址空間；把一個(gè)程序分為多個(gè)段，不同的段運(yùn)行在不同的虛擬內(nèi)存中；為了區(qū)分不同的段，我們有了段號(hào)和段內(nèi)偏移地址。段的個(gè)數(shù)非常少，因此段表的尺寸非常小。
分段的優(yōu)點(diǎn)十分明顯，程序每個(gè)邏輯單元可單獨(dú)占一個(gè)虛擬地址空間，這樣可使編寫(xiě)的程序的空間大為增長(zhǎng)；不會(huì)出現(xiàn)分頁(yè)系統(tǒng)一個(gè)頁(yè)面里可能同時(shí)包含數(shù)據(jù)和代碼而造成增長(zhǎng)極限和共享的問(wèn)題； 分段的感覺(jué)像是又回到了分區(qū)時(shí)代；缺點(diǎn)十分明顯；外部碎片以及一個(gè)段必須全部加載到內(nèi)存。
段頁(yè)式內(nèi)存管理
老王既琢磨出來(lái)分頁(yè)管理，又琢磨出了分段管理；到底用哪個(gè)，老王一拍腦袋，為啥不組合下，把優(yōu)點(diǎn)結(jié)合下，這就出來(lái)了段頁(yè)式存儲(chǔ)。 把一個(gè)段內(nèi)存按頁(yè)來(lái)分，就是段表映射到頁(yè)表；這種段頁(yè)式結(jié)合了段式和頁(yè)式的優(yōu)點(diǎn)，現(xiàn)在大部分商業(yè)系統(tǒng)都使用段頁(yè)式內(nèi)存管理方式。
后記
由于老王在管理上的卓越貢獻(xiàn)，皇帝特封其為農(nóng)國(guó)公。知識(shí)源于生活，老王用生活的經(jīng)驗(yàn)沉淀出了一套操作系統(tǒng)內(nèi)存管理的機(jī)制。
