內(nèi)存管理的基本思想

每個進程都擁有自己的地址空間( Address space),包括這個進程可以使用的全部地址和其中存儲的所有數(shù)據(jù)详囤；為防止不同進程修改彼此的地址空間吗货，操作系統(tǒng)需要將進程的邏輯地址轉(zhuǎn)換為物理內(nèi)存中的實際地址,這一過程可以由不同方法實現(xiàn)服傍。
在早期的計算機中,同一時間在機器上運行的只有一個作業(yè),因此這個進程的地址空間與實際物理內(nèi)存是完全重合的,不需要進行地址轉(zhuǎn)換。

在多道程序設(shè)計與操作系統(tǒng)逐漸形成后,操作系統(tǒng)必須將多個程序相互不覆蓋地放入物理內(nèi)存仰担。為了達到這一目的,多種連續(xù)內(nèi)存管理方法和非連續(xù)內(nèi)存管理方法都逐漸被發(fā)眀和采用统阿。

在介紹連連續(xù)內(nèi)存管理和非連續(xù)內(nèi)存管理的不同實現(xiàn)方法之前,我們必須先了解“碎片”( fragmentation)的概念和評價一個內(nèi)存管理方法的標(biāo)準(zhǔn),這樣每學(xué)習(xí)個新的實現(xiàn)方法后,我們都可以依照這個標(biāo)準(zhǔn)來評價其優(yōu)缺點,對這個方法有更完全的認(rèn)識炊林。

碎片即在內(nèi)存中無法有效利用的部分,分為外部碎片和內(nèi)部碎片姥卢。

• 外部碎片( external fragmentation)指的是因為長度過短而無法被使用的未分配內(nèi)存；換句話說是因為太短了不中用渣聚。
• 內(nèi)部碎片( internal fragmentation)指的是已分配內(nèi)存中因為分配長度過長而沒有被進程有效利用的內(nèi)存独榴。分到的空間太長了，根本用不了那么多奕枝。

在評價一個用來實現(xiàn)地址轉(zhuǎn)換和內(nèi)存分配的方法時棺榔，我們需要考慮到這個方法是否會造成大量碎片的出現(xiàn)，或者在實際實現(xiàn)的過程中過于復(fù)雜隘道、占用過多內(nèi)存症歇。理想的內(nèi)存分配和地址轉(zhuǎn)換方法能夠達到保護進程不被其它惡意進程讀取其內(nèi)容、保護進程不能修改自己的代碼谭梗、方便進程在運行過程中獲取更多內(nèi)存或與其它進程共享一部分內(nèi)存的目的忘晤，又不需要過多的內(nèi)存空間存儲地址轉(zhuǎn)換需要的信息或長的時間實現(xiàn)地址轉(zhuǎn)換或內(nèi)存分配，同時又不產(chǎn)生內(nèi)部碎片和外部碎片激捏；下面就讓我們在一個題目中應(yīng)用一下我們新學(xué)到的評價標(biāo)準(zhǔn)吧设塔！

測試題

蒜頭君覺得設(shè)計操作系統(tǒng)的內(nèi)存管理方法是一件很簡單的事情，于是設(shè)計了下面這個內(nèi)存管理方法給姜小姐炫耀远舅，請你替姜小姐評價一下這個內(nèi)存管理方法闰蛔，指出其三個優(yōu)缺點。

• 給每個進入系統(tǒng)的進程恰好等于它所需內(nèi)存大小的內(nèi)存图柏，進程與進程之間不留空閑的內(nèi)存區(qū)域
• 一個進程運行完畢后就將它的內(nèi)存回收钞护，將所有它之后的內(nèi)存都往前移動，直到跟前一個進程無縫銜接為止爆办；
• 在每個進程的進程控制塊中都儲存這個進程所獲得的內(nèi)存的起始地址和終結(jié)地址，在移動進程對應(yīng)的內(nèi)存時改變這兩個地址课梳，每次進程對內(nèi)存進行操作時都需要用這兩個地址來確認(rèn)它沒有超范圍使用內(nèi)存距辆；
• 一個進程和另一個進程所占的內(nèi)存不能重疊。

評價

連續(xù)內(nèi)存管理

固定分區(qū)存儲管理

為實現(xiàn)多道程序在系統(tǒng)中同時運行暮刃，必須設(shè)計一個內(nèi)存管理方法使不同程序的數(shù)據(jù)可以同時存在于內(nèi)存中而不互擾跨算。早期計算機中為達此目的使用的是連續(xù)內(nèi)存管理。

顧名思義,連續(xù)內(nèi)存管理會將同一個進程的地址空間映射到一段連續(xù)的物理內(nèi)存上椭懊。早期被用來實現(xiàn)連續(xù)內(nèi)存管理的方法是固定分區(qū)存儲管理( fixed partition),即將內(nèi)存空間分為數(shù)目固定的分區(qū),其中每個分區(qū)大小都與其它分區(qū)不同,一個分區(qū)只對應(yīng)一個迸程,處于不同分區(qū)中的進程將并發(fā)執(zhí)行诸蚕。顯然,為了能夠有效地將為新進入系統(tǒng)的作業(yè)選擇分區(qū),我們需要一種記錄未被使用的分區(qū)的方法,這就是內(nèi)存分配表。內(nèi)存分配表中記錄了內(nèi)存中所有被劃分的分區(qū)的大小及使用情況,可以幫助我們?yōu)樾逻M入系統(tǒng)的進程選擇分區(qū)。

當(dāng)進程就緒隊列不為空背犯，且出現(xiàn)了一個新的可使用分區(qū)時坏瘩，我們有兩種選擇下一個進程的方法：

• 我們可以讓每一個進入系統(tǒng)的進程排在可以容納該進程的最小分區(qū)的隊列中，在該分區(qū)空閑時選擇隊列的第一個進程運行漠魏；
  但是主要問題是倔矾，如果大部分進程所需的內(nèi)存都處于同一大小區(qū)間內(nèi)，那么等待時間就會很長柱锹；
• 我們也可以讓所有進程排在同一隊列中哪自，在一個分區(qū)空閑后我們進入隊列，尋找第一個分區(qū)可以容納的進程或分區(qū)長度所能容納的最大進程進入該分區(qū)禁熏。
  問題是如果我們選擇第一個可容納進程壤巷，那么如果該進程所需的內(nèi)存很小，我們分配的分區(qū)中就會產(chǎn)生較大的內(nèi)部碎片瞧毙，而如果我們選擇后一種胧华，則我們可能面臨和前一種方法類似的問題。

不難看出升筏，合理劃分內(nèi)存分區(qū)對提高固定分區(qū)存儲管理的效率非常重要撑柔。這一工作往往由系統(tǒng)管理員和操作系統(tǒng)共同完成，但這仍不能完全避免內(nèi)部碎片問題您访。更糟糕的是铅忿，如果一個進程所需的內(nèi)存大小大于最大分區(qū)的大小，那么系統(tǒng)就必須合并多個分區(qū)灵汪，而這是需要很多工作來實現(xiàn)的檀训。另一方面，如果系統(tǒng)管理員事先知道最大作業(yè)的大小享言，而將一個分區(qū)設(shè)為該大小峻凫，那么該分區(qū)在運行其它進程時很可能產(chǎn)生很大的內(nèi)部碎片。另外览露，如果一個進程在運行時發(fā)現(xiàn)需要更多空間荧琼，那么固定分區(qū)的存儲方式很難給這個進程分配新的分區(qū)。最后差牛，我們知道在現(xiàn)代系統(tǒng)中很多時候進程的數(shù)量是很少的命锄，而少部分時候進程數(shù)量會很多，造成擁堵偏化，固定分區(qū)的管理方法限制了分區(qū)的數(shù)量脐恩，因此不適于處理這種情況。

可變分區(qū)存儲管理

為了解決前面提到的內(nèi)部碎片和無法容納過大進程的問題侦讨，我們可以采取一種更具有變通性的方法實現(xiàn)連續(xù)內(nèi)存管理驶冒；這種方法就是可變分區(qū)存儲管理（variable partition）苟翻。
這種管理方式按照不同進程所需的內(nèi)存大小劃分分區(qū)，并將所有未分配分區(qū)存放在一個鏈表中骗污。
在一個進程結(jié)束崇猫、被系統(tǒng)撤銷后，它所占的分區(qū)將被標(biāo)記為可用身堡，加入未分配分區(qū)的鏈表邓尤；如果其毗鄰的分區(qū)也為未分配分區(qū)，那么它們就會被合為一個更大的未分配分區(qū)加入鏈表贴谎。
在一個新的進程進入系統(tǒng)時汞扎，系統(tǒng)將沿鏈表尋找可以容納該進程的未分配分區(qū)，將進程需要的大小分配給該進程擅这，將該分區(qū)中剩余的內(nèi)存作為一個新的未分配分區(qū)加入鏈表澈魄。下面的圖片表示的是可變分區(qū)存儲管理中分區(qū)的回收和合并：

在上面的討論中痹扇，沒提到兩個問題：

• 在所有大小不小于進程需求的分區(qū)中，我們?nèi)绾芜x擇一個合適的分區(qū)分配給這個進程溯香？
• 如果進程所需的內(nèi)存大小已經(jīng)超出系統(tǒng)中最大的未分配分區(qū)的代銷或系統(tǒng)中未分配內(nèi)存的總量鲫构，我們有沒有辦法讓進程不等待而直接開始運行呢？

以后將講解實現(xiàn)可變內(nèi)存分配的算法和內(nèi)存不足時的處理辦法玫坛。

可變分區(qū)存儲管理的實現(xiàn)

為了在可變分區(qū)存儲管理中最有效地分配分區(qū)结笨，使新進程在進入系統(tǒng)時即可以找到適合其大小的分區(qū)而不產(chǎn)生過多碎片，我們可以采取不同的方法排列未分配分區(qū)鏈表中的分區(qū)并選擇相應(yīng)的算法來分配分區(qū)湿镀。針對未分配分區(qū)的分配有五種不同的算法炕吸，下面我們將向你一一介紹。

最先適應(yīng)（first fit）

順序查找未分配分區(qū)的鏈表勉痴，選擇第一個能滿足長度要求的分區(qū)赫模。采取這種算法時未分配區(qū)表中的空閑區(qū)往往按照地址從低到高排列，這樣高地址部分的內(nèi)存盡量不被分割蒸矛，可以被留給內(nèi)存需求大的進程瀑罗。
盡管這種算法使低地址空間的使用率遠(yuǎn)高于高地址空間并在低地址空間產(chǎn)生了許多小的未分配分區(qū)，在實際的系統(tǒng)中雏掠，這種算法由于其快速廓脆、便于實現(xiàn)的特點被廣泛應(yīng)用。

下次適應(yīng)（next fit）

這種算法會保留一個搜索指針磁玉，每次總是從上次未分配分區(qū)的掃描結(jié)束處開始掃描，直到找到第一個能滿足長度要求的空閑區(qū)驾讲。
這種算法相比第一種對存儲空間的利用率較為均衡蚊伞，不會使碎片化的空閑區(qū)集中在低地址部分席赂。

最優(yōu)適應(yīng)（best fit）

在每一個新進程進入系統(tǒng)時都掃描整個未分配分區(qū)鏈表，尋找最小的可滿足該進程內(nèi)存需求的未分配分區(qū)时迫。使用這種算法時往往把分區(qū)按大小升序排列颅停，方便找到符合要求的最小分區(qū)。
這種算法的問題是每次分配分區(qū)后掠拳，該分區(qū)中大于進程所需內(nèi)存大小的部分可能很小癞揉，因此會在未分配分區(qū)鏈表中加入很多很小的分區(qū)，不能被任何進程使用溺欧，而導(dǎo)致外部碎片的產(chǎn)生喊熟。

最壞適應(yīng)（worst fit）

與上一種相反，這種算法總是將最大的未分配分區(qū)分割給作業(yè)使用姐刁，這樣分配的分區(qū)中剩下的分區(qū)總不會過小芥牌。
使用這種算法時，我們總是將未分配分區(qū)按大小降序排列聂使，使找到最長的分區(qū)非潮诶快速。

快速適應(yīng)（quick fit）

快速適應(yīng)( quick fit):這種算法給一些常用的分區(qū)長度設(shè)立了單獨的鏈表(如:2KB,4KB和8KB的分區(qū)可能分別對應(yīng)一個單獨的鏈表)柏靶。我們把大小接近這些分區(qū)的分區(qū)也放在這些分區(qū)的鏈表中(如:5KB分區(qū)可以放在4KB的鏈表中)弃理。這樣,在一個新進程進入系統(tǒng)中時,我們可以將可以容納該進程的最小長度的鏈表的第一個分區(qū)分給它。這種算法非呈候眩快速,但在歸還分區(qū)和合并未分配分區(qū)時非常復(fù)雜痘昌。

內(nèi)存不足的解決辦法

連續(xù)內(nèi)存的存儲面臨一個比較大的問題，即難以獲得大小足夠的連續(xù)內(nèi)存用于分配給一個進程梆靖。這種情況又可以被細(xì)分為兩種情況：

• 一種情況是控汉，系統(tǒng)中未分配內(nèi)存的總量大于進程需要的內(nèi)存；
  我們可以通過合并分區(qū)解決內(nèi)存不足的問題
• 另一種情況是返吻，系統(tǒng)中未分配內(nèi)存的總量小于進程需要的內(nèi)存姑子。
  我們必須將一部分現(xiàn)在處于內(nèi)存中的東西移到外存中。

我們將先講解解決第一種問題的辦法测僵，即移動技術(shù)街佑。
移動技術(shù)就是通過讀出已分配內(nèi)存中的全部數(shù)據(jù)并寫回內(nèi)存中的另一位置將進程的內(nèi)存分區(qū)移動到一起，使未分配分區(qū)集中到一個位置合為一個大的未分配分區(qū)捍靠，分配給新進程沐旨。
這種方法的問題是很明顯的：

• 如果一個進程正在讀寫它的分區(qū)，那么系統(tǒng)就不能移動這個分區(qū)；
• 移動過程中，進程也不能讀寫其內(nèi)存描焰，這將延長所有進程的響應(yīng)時間小槐。

因此系統(tǒng)一般會盡量避免移動暑刃，只在必須通過移動分區(qū)來容納新進程梅猿，或進程撤銷后釋放出的空閑分區(qū)與其它未分配分區(qū)不相鄰時才移動分區(qū)來合并未分配分區(qū)仍稀。

當(dāng)系統(tǒng)中的未分配內(nèi)存總量已經(jīng)小于進程所需的內(nèi)存總量時夺荒，我們就必須將一部分?jǐn)?shù)據(jù)移出內(nèi)存统诺。在這種情況下我們經(jīng)常使用的技術(shù)是覆蓋技術(shù)和對換技術(shù)歪脏，這里我們先來解釋覆蓋技術(shù)。

覆蓋技術(shù)

覆蓋技術(shù)要求程序開發(fā)者將自己的程序分為幾個“覆蓋段”粮呢，每個覆蓋段中含有多個相對獨立的程序部分婿失，稱為“覆蓋”。處于同一覆蓋段中的覆蓋相互沒有依賴關(guān)系啄寡，所以不需要同時處于內(nèi)存中豪硅。我們以每個覆蓋段中最大的覆蓋的大小來規(guī)定該覆蓋段的大小这难；在每個覆蓋段中舟误，所有覆蓋按一定的順序進入內(nèi)存，這樣系統(tǒng)在給這個進程分配內(nèi)存時姻乓，就只需要分配大小等于該進程所有覆蓋段大小之和的內(nèi)存嵌溢，節(jié)省了很多空間。

對換技術(shù)

這個技術(shù)給程序開發(fā)者提高了程序設(shè)計的難度蹋岩，因為他們必須能夠?qū)⒊绦蚍譃榛ハ嗖灰蕾嚨哪K赖草，并設(shè)計不同模塊進入內(nèi)存的順序，這是十分困難的剪个。因此秧骑，這種技術(shù)只在早期的計算機中被使用，現(xiàn)在經(jīng)常被使用的是我們下面要提到的這種技術(shù)——對換技術(shù)（swapping）扣囊。

對換技術(shù)的概念非常簡單乎折，即將內(nèi)存中的一部分移出內(nèi)存，然后將總量小于等于被移出部分的大小的數(shù)據(jù)從外存移到內(nèi)存中侵歇，但是我們面臨著一個很重要的問題骂澄，即哪一部分內(nèi)存應(yīng)該被移出呢？

在連續(xù)內(nèi)存管理中惕虑，由于每個進程都只有一塊連續(xù)的內(nèi)存坟冲，我們只能將整個進程都移出內(nèi)存，因此我們一般會選擇處于等待態(tài)的進程移出內(nèi)存溃蔫。如果我們選擇運行態(tài)或就緒態(tài)的進程移出內(nèi)存健提，那么這個進程的響應(yīng)時間就會被延長，影響系統(tǒng)效率伟叛。但是如果沒有進程處于等待態(tài)私痹，我們應(yīng)該把哪一部分內(nèi)存移出呢？參考上面的覆蓋技術(shù)我們可以知道，一個進程并不是同時需要其地址空間的所有部分都處于內(nèi)存中紊遵，因此理想狀態(tài)下雹锣，我們應(yīng)該可以只把運行需要的部分留在內(nèi)存中，而系統(tǒng)將自動把其它部分移出癞蚕。這就是非連續(xù)存儲管理的意義。

練習(xí)

分段內(nèi)存管理

分段存儲管理會將進程的邏輯地址分為兩部分辉哥，段號和段內(nèi)位移桦山。每一個進入系統(tǒng)的進程都會擁有自己的段表，表中的每一行都對應(yīng)著段號等于行號的段的段長和基址醋旦，以及一些用于限制這一段的操作權(quán)限的保護位（如是否可讀恒水、可寫）。這樣我們就可以通過段號獲取邏輯地址所對應(yīng)的段的基址饲齐，然后將段長與位移作比較钉凌，如果位移未超過段長則將位移與基質(zhì)相加，得到實際的物理地址捂人。由于系統(tǒng)對于段號和段內(nèi)位移的尾數(shù)做出了限制御雕，如果在32位系統(tǒng)中段號由i位組成，則用戶進程在設(shè)計分段時不能設(shè)計超出2^i個段滥搭，酸纲，每段長度不能超過2^(32-i)個字節(jié)。

每次進程在對內(nèi)存進行操作時瑟匆，都必須用段號作為行號進入該進程的段表闽坡，獲取基址和段長；如果段號大于該進程的最大段號愁溜，或進程對這一地址的操作不被該段允許疾嗅，或邏輯地址中的段內(nèi)位移大于段長，則硬件會觸發(fā)異常冕象，這就是你在寫 C 程序時可能會見到的段錯誤（Segmentation fault）代承。

下面的圖片可以給你一個對于分段存儲管理的更加直觀的理解：

分段存儲的優(yōu)點是，不同進程間可以共享一段邏輯上相對獨立的內(nèi)存交惯，比如兩個運行同一程序的進程可以共享代碼分段次泽，兩個公用一個庫的進程可以共享只包含這個庫的段。但分段存儲也有一個明顯的缺點——與可變分區(qū)存儲管理相似席爽，它的每一個段大小不固定意荤，因此可能面臨內(nèi)存中存在很多外部碎片，需要移動已有進程才能運行新進程的局面只锻。為了解決這一問題玖像，我們可能希望每一個段都有相同的大小，或可以被分為大小相同的更小單位來存儲，這就是我們即將介紹的分頁存儲管理（Paging）

分頁存儲管理（Paging）

在介紹分頁管理的方法以前,讓我們先定義頁和頁框捐寥。

頁與段類似,都是進程地址空間中的一部分,但不同于段的是,一個系統(tǒng)中所有頁面的大小都是固定笤昨、相等的。頁面的一般大小都是2的整數(shù)次冪字節(jié),因此如果一個頁面的大小是2字節(jié),那么在32位系統(tǒng)中,我們就可以用地址最右側(cè)的j位表示頁內(nèi)位移,左側(cè)的32一j位表示頁號握恳。為了區(qū)分進程地址空間和物理內(nèi)存,我們將物理內(nèi)存中同樣大小的內(nèi)存單位稱為頁框;你可以把地址空間里的頁想象成照片,那物理內(nèi)存就像一個相冊,中間有很多大小相同的相框,而相框中包含有什么照片就取決于現(xiàn)在是哪個進程在用這本相冊瞒窒。

為了將地址空間中的頁與物理內(nèi)存里的頁框相對應(yīng),每一個進程有自己的頁表,長度由進程所需的頁面數(shù)決定,我們可以在第b行查看頁面號(邏輯地址)等于b的頁面在物理內(nèi)存中對應(yīng)的實際頁框號。第b行中同時也包含一些其他的信息,

如讀寫權(quán)限位( read bit and write bit)乡洼、表示頁面是否實際存在于內(nèi)存中的有效位( valid bit)崇裁、表示頁面是否被修改過的頁面重寫標(biāo)志位( dirty bit)等等,我們會在講到請求分頁虛虛擬存儲管理時更具體地講到這些內(nèi)容。從頁表中獲得頁框號后,我們可以將頁框號與位移合成該邏輯地址對應(yīng)的物理地址束昵。為了分配頁面給不同的進程,系統(tǒng)將需要一個內(nèi)存物理塊表,用來記錄頁框狀態(tài),即哪些頁框還未被分配,已分配的頁框?qū)儆谀男┻M程等等;在新進程進入系統(tǒng)后,我們將在內(nèi)存物理塊表中尋找未被分配的頁框給這個進程使用下面的圖片表示了分頁存儲管理中通過邏輯地址獲得物理地址的過程拔稳。

分頁存儲的優(yōu)點是，由于內(nèi)存大小是頁面大小的整數(shù)倍锹雏，內(nèi)存中永遠(yuǎn)不會像分段處理那樣出現(xiàn)外部碎片巴比。不僅如此，由于每個進程無法不通過頁表獲得物理地址礁遵，用戶進程自然不能接觸其它進程未與之共享的物理地址轻绞；而共享本身也變得簡單了許多，只需要將不同進程中的兩個頁面指向同一個頁框榛丢。當(dāng)然铲球，它也面臨著很嚴(yán)重的問題——頁表本身需要很大的空間儲存，可能占去很多內(nèi)存空間晰赞。為了解決這個問題稼病，我們將在后幾節(jié)中介紹多級頁表、反置頁表和分段與分頁結(jié)合的存儲管理掖鱼。

分段與分頁作為非連續(xù)內(nèi)存管理的兩種實現(xiàn)方法在一開始可能比較難區(qū)分然走，因此我們這里將專門對兩種方法進行對比：

• 分段與分頁都會將一個進程的地址空間分為幾個小段，將這些小段分別存儲在連續(xù)的一段內(nèi)存中戏挡，但同一進程的不同段可能存儲在不連續(xù)的內(nèi)存中芍瑞；
• 它們的不同點在于，分頁完全根據(jù)一個固定的大小將內(nèi)存分為大小相等的段褐墅，與內(nèi)存中所存儲的內(nèi)容無關(guān)拆檬，而分段存儲管理是根據(jù)內(nèi)存的邏輯結(jié)構(gòu)將內(nèi)存分為幾個部分。

一種常見的分段方法是將進程內(nèi)存分為代碼妥凳、數(shù)據(jù)竟贯、棧和堆四部分，然后將這幾個部分分別存放在幾段可能相互不連續(xù)的內(nèi)存中逝钥；而在分頁的存儲模式中屑那，棧可能會分布在幾個在物理內(nèi)存中不連續(xù)的頁面中。另一點不同是持际，在分頁存儲管理中沃琅，頁的劃分是用戶進程不可見的；而在分段存儲管理中蜘欲，段的劃分是用戶進程可見的益眉，可以根據(jù)自己的需求和邏輯地址結(jié)構(gòu)的限制來自行劃分段。

分段和分頁也可以被結(jié)合起來使用：我們可以將每個段對應(yīng)一個頁表姥份，這樣每次需要將內(nèi)存中的一些部分與外存中的部分對換時呜叫，我們可以只對換某一段中的一頁，而不是將整個段移出內(nèi)存殿衰，這就解決了分段內(nèi)存中由段落大小不同造成的外部碎片問題。

練習(xí)

虛擬存儲盛泡、多級頁表闷祥、反置頁表

在上一節(jié)中我們已經(jīng)看到,32位的系統(tǒng)中使用4KB的頁面會導(dǎo)致每個進程的頁表可以消耗2MB的內(nèi)存。這對于32位系統(tǒng)2^32字節(jié),也就是4GB的內(nèi)存來講已經(jīng)很大了傲诵。在現(xiàn)代的計算機系統(tǒng)的發(fā)展中,人們意識到一個進程可能并不隨時需要
其全部的程序和數(shù)據(jù)來運行,因此可以進一步擴大進程的地址空間,將地址空間的一部分儲存到磁盤上,只將運行用到的部分放在物理內(nèi)存中凯砍。這種想法允許一個迸程擁有與物理內(nèi)存大小相同甚至大于物理內(nèi)存大小的地址空間;因此虛擬存儲器誕生了。在將虛擬存儲中的邏輯地址轉(zhuǎn)換為物理內(nèi)存的實際地址時,我們需要的頁表的大小是與虛擬存儲中的總頁面數(shù)量成正比的;由于虛擬存儲很可能大于物理內(nèi)存,一個頁表消耗的內(nèi)存可能遠(yuǎn)高于2MB拴竹。為了解決這種過度的內(nèi)存消耗,我們接下來將介紹兩種能夠更節(jié)約空間地將頁面號轉(zhuǎn)換為頁框號的方法悟衩。

在開始介紹以前，我們要先澄清一個有關(guān)虛擬存儲器的問題栓拜。在國內(nèi)的很多教材中座泳，虛擬地址，即虛擬存儲器所用的地址幕与，和邏輯地址挑势，即進程地址空間中的地址，是兩個不同的概念啦鸣。這種區(qū)分主要來源于 x86 架構(gòu)對于分段存儲的實現(xiàn)潮饱。在 x86 架構(gòu)中，邏輯地址使用的是“段：段內(nèi)位移”的形式诫给，與我們常見的 0xFFFFFFFF 這種形式的地址是不同的香拉。后一種地址與地址空間中每一個位置一一對應(yīng)，因此如一跟線一樣中狂，被稱為線性地址凫碌。虛擬地址都是針對進程的虛擬地址空間的線性地址，與 x86 架構(gòu)中的邏輯地址有明顯不同吃型；處理器使用的是邏輯地址证鸥，但我們也可以通過一定的方式由邏輯地址獲得虛擬地址。在本課程中，由于不同的架構(gòu)不是我們關(guān)注的重點枉层，我們將以“邏輯地址”來表示進程地址空間的線性地址泉褐，而不把邏輯地址當(dāng)作“段：段內(nèi)位移”的形式。

• 我們要介紹的第一種存儲方法就是多級頁表鸟蜡。多級頁表的想法很簡單膜赃，即將原來的頁號分為兩部分，用第一部分將原來的大頁表分為幾個小頁表揉忘，稱為頁表頁跳座，將每個頁表頁分別存在內(nèi)存的一個位置，然后將這些位置與我們用來區(qū)分頁表頁的頁面號的第一部分一一對應(yīng)泣矛，形成一個頁目錄表疲眷。我們在轉(zhuǎn)換地址時先通過頁號的第一部分頁表目錄找到一個頁表頁，然后再用頁號的第二部分在該頁表頁中找到頁框號您朽；因此我們將頁號的第一部分稱為頁目錄位移狂丝，頁號的第二部分稱為頁表頁位移。
• 我們還剩下一個問題,我們該如何決定頁目錄位移包含多少位呢?
  假設(shè)在一個32位系統(tǒng)中,每個頁面為2^iKB,頁表中每行為2^jB,那么內(nèi)存中總共有2^(22-i)個頁面,每個頁表頁可以裝下2^(10+i-j)個頁表項哗总。因此我們需要
  2^(22-i-10-i+j)=2^(12-2i+j)個頁表頁來包含所有頁面几颜。因此,我們需要12-2+j位來表示頁目錄位移,10+i-j位來表示頁表頁位移,10+i位來表示頁位移。我們可以驗證一下我們的計算12-2i+j+10+i-j+10+i=32讯屈。

多級頁表相對于單級頁表的優(yōu)勢是蛋哭，我們不需要將所有頁表頁留在內(nèi)存中——我們只需要那些近期使用過或正在使用的頁表留在內(nèi)存中，而這可以幫我們節(jié)約大量內(nèi)存涮母。
但多級頁表也面臨著一個問題——即使一個頁面和它對應(yīng)的頁表頁都存在于內(nèi)存中谆趾，我們也需要三次訪問內(nèi)存，才能獲得我們需要的數(shù)據(jù)——

• 第一次訪問內(nèi)存我們從頁目錄表中獲取了該頁表頁的起始地址叛本，
• 第二次訪問內(nèi)存時我們從頁表頁獲得了頁框號棺妓，
• 第三次訪問內(nèi)存時我們才獲得了我們需要的實際數(shù)據(jù)。

這本身就需要很多時間炮赦；如果在這個過程中怜跑，我們發(fā)現(xiàn)其中一個頁面不在內(nèi)存中，那么我們還要花更多的時間將頁面從磁盤中復(fù)制到內(nèi)存中吠勘，多級頁表的缺陷就體現(xiàn)出來了性芬。

反置頁表

與多級頁表并列的另一種方法是反置頁表( averted Page Table),它的特點是所有進程都被包含在一張表中。這種方法將邏輯地址中的頁號與該進程的進程標(biāo)識符結(jié)合起來作為哈希函數(shù)的輸入,被哈希函數(shù)映射到一個反置頁表項上剧防。一個反置頁表項包括進程標(biāo)識符植锉、頁號和哈希鏈指針;哈希指針是一個指向反置頁表中的其它項的指針,它被用來解決哈希函數(shù)中不同進程的不同邏輯頁面指向同一個反置頁表項的問題。
如果反置頁表項中的進程標(biāo)識符合頁號與邏輯地址中的進程標(biāo)識符和頁號相同,這說明物理內(nèi)存中的這一頁框確實對應(yīng)著邏輯地址空間中的這一頁面,我們可以直接將頁框號與頁內(nèi)位移組合在起,獲得物理地址峭拘。反之,我們就必須沿哈希指針尋找符合該邏輯地址的進程標(biāo)識符和頁號的項,如果我們找不到這樣一個項,那就說明該頁面不在物理內(nèi)存中,此時系統(tǒng)就會觸發(fā)缺頁異常,將頁面從磁盤中復(fù)制到內(nèi)存中俊庇。

反置頁表相對于多級頁表的優(yōu)勢是很明顯的——對于在物理內(nèi)存中的頁面狮暑，我們可能只需要訪問一次內(nèi)存；相對于普通頁表辉饱，它的大小是與物理內(nèi)存中的頁面數(shù)量成正比的搬男，因此所占的內(nèi)存遠(yuǎn)小于普通頁表。但它的問題也非常明顯——表中包含的只有在物理內(nèi)存中的頁面彭沼，對于不在物理內(nèi)存中的頁面缔逛，進程仍需建立普通頁表存儲，而且反置頁表相對其它方式需要更復(fù)雜的硬件結(jié)構(gòu)來實現(xiàn)姓惑。

總結(jié)

固定分區(qū)存儲管理

• 內(nèi)存被分為大小不同的固定的幾個分區(qū),每個分區(qū)只能被分配給一個進程
• 缺點是可能有很多內(nèi)部碎片,
• 且當(dāng)進程內(nèi)存需求大于任何一個分區(qū)的大小時需要采用復(fù)雜的技術(shù)解決這一問題褐奴。

可變分區(qū)存儲管理

• 內(nèi)存分區(qū)大小可變,由進程需要的內(nèi)存大小決定。
• 空閑的分區(qū)按一定順序被排列在一個鏈表中,在新進程進入系統(tǒng)時被分配給進程
• 配給進程的空閑分區(qū)包含的進程需要的大小以外的內(nèi)存將作為新的空閑分區(qū)加入鏈表于毙。
• 一個進程撤銷后其分區(qū)重新成為空閑分區(qū)
• 與周圍的空閑分區(qū)合并后進入鏈表敦冬。
• 主要缺點是一段時間后會產(chǎn)生很多外部碎片,需要移動所有進程來產(chǎn)生足夠大的空閑分區(qū)分配給新進程。

單級分頁存儲管理

• 將邏輯地址分為頁號與頁內(nèi)位移兩部分
• 在轉(zhuǎn)換邏輯地址的過程中,系統(tǒng)將頁號作為索引進入每個進程的頁表,尋找對應(yīng)的頁框號
• 將頁框號與頁內(nèi)位移合成物理地址
• 其優(yōu)點是不會產(chǎn)生外部碎片,且易于保護進程和在不同進程間共享頁面
• 缺點是頁表所占的空間與邏輯地址空間大小成正比,所占內(nèi)存過大

分段存儲管理

• 將進程的邏輯地址空間按照程序結(jié)構(gòu)分為幾段,每一段在內(nèi)存中獲得一段連續(xù)的內(nèi)存唯沮。
• 優(yōu)點是便于共享,缺點是由于每段的長度不同,容易產(chǎn)生外部碎片匪补。

多級分頁存儲管理

• 將單級分頁存儲管理中邏輯地址里的頁號進一步分為頁目錄位移和頁表頁位移
• 將頁目錄位移相同的邏輯地址放入同一頁表頁。
• 通過頁目錄位移找到頁表頁起始地址后再從頁表頁中尋找頁框號烂翰。
• 其優(yōu)點是,可以不將所有頁表頁都留在內(nèi)存中,節(jié)省空
• 其缺點是,每訪問一次內(nèi)存實際都對應(yīng)三次訪問內(nèi)存,因此效率較低。

反置頁表

• 以進程標(biāo)識符和頁號作為哈希函數(shù)的輸入值,用哈希函數(shù)的輸出值找到一個反量頁表項蚤氏。
• 對比進程標(biāo)識符與頁號是否相同,如果不同則跟隨哈希指針查看甘耿。
• 如果相同則將對應(yīng)的頁框號與頁內(nèi)位移組合,獲得物理地址。
• 其優(yōu)點是反置頁表的大小與物理內(nèi)存大小成正比,所占空間遠(yuǎn)小于一般頁表;
• 缺點是反置頁表中只存儲存在于物理內(nèi)存中的頁面,其他頁面仍需設(shè)立一般頁表來存儲竿滨。