非連續(xù)分配允許一個(gè)程序分散地裝入到不相鄰的內(nèi)存分區(qū)中，根據(jù)分區(qū)的大小是否固定分為分頁(yè)存儲(chǔ)管理方式和分段存儲(chǔ)管理方式。

分頁(yè)存儲(chǔ)管理方式中，又根據(jù)運(yùn)行作業(yè)時(shí)是否要把作業(yè)的所有頁(yè)面都裝入內(nèi)存才能運(yùn)行分為基本分頁(yè)存儲(chǔ)管理方式和請(qǐng)求分頁(yè)存儲(chǔ)管理方式。

1、基本分頁(yè)存儲(chǔ)管理方式

固定分區(qū)會(huì)產(chǎn)生內(nèi)部碎片，動(dòng)態(tài)分區(qū)會(huì)產(chǎn)生外部碎片，這兩種技術(shù)對(duì)內(nèi)存的利用率都比較低。我們希望內(nèi)存的使用能盡量避免碎片的產(chǎn)生。這就引入了分頁(yè)的思想：把主存空間劃分為大小相等且固定的塊，塊相對(duì)較小，作為主存的基本單位。每個(gè)進(jìn)程也以塊為單位進(jìn)行劃分，進(jìn)程在執(zhí)行時(shí)，以塊為單位逐個(gè)申請(qǐng)主存中的塊空間。

分頁(yè)的方法從形式上看賣(mài)相分區(qū)相等的固定分區(qū)技術(shù)，分區(qū)管理不會(huì)產(chǎn)生外部碎片。但它又有本質(zhì)的區(qū)別：塊的大小相對(duì)分區(qū)要小很多，而且進(jìn)程也按照塊進(jìn)行劃分，進(jìn)程運(yùn)行時(shí)按塊申請(qǐng)主存可用空間并執(zhí)行。這樣，進(jìn)程只會(huì)在為最后一個(gè)不完整的塊申請(qǐng)一個(gè)主存塊空間時(shí)，才產(chǎn)生主存碎片，所以盡管會(huì)產(chǎn)生內(nèi)部碎片，但是這種碎片相對(duì)進(jìn)程來(lái)說(shuō)也是很小的，每個(gè)進(jìn)程平均產(chǎn)生半個(gè)塊大小的內(nèi)部碎片（也稱(chēng)頁(yè)內(nèi)碎片）

（1）分頁(yè)存儲(chǔ)的幾個(gè)基本概念

①頁(yè)面和頁(yè)面大小

進(jìn)程中的塊稱(chēng)為頁(yè)（Page），內(nèi)存中的塊稱(chēng)為頁(yè)框（Page Frame，或頁(yè)幀）。外存也以同樣的單位進(jìn)行劃分，直接稱(chēng)為塊（Block）。進(jìn)程在執(zhí)行時(shí)需要申請(qǐng)主存空間，就是要為每個(gè)頁(yè)面分配主存中的可用頁(yè)框，這就產(chǎn)生了頁(yè)和頁(yè)框的一一對(duì)應(yīng)。

為方便地址轉(zhuǎn)換，頁(yè)面大小應(yīng)是2的整數(shù)冪。同時(shí)頁(yè)面大小應(yīng)該適中。如果頁(yè)面太小，會(huì)使進(jìn)程中的頁(yè)面過(guò)多，這樣頁(yè)表就過(guò)長(zhǎng)，占用大量?jī)?nèi)存，而且會(huì)增加硬件地址轉(zhuǎn)換的開(kāi)銷(xiāo)，降低頁(yè)面換入換出的效率；頁(yè)面過(guò)大又會(huì)使頁(yè)內(nèi)碎片增大，降低內(nèi)存的利用率。所以頁(yè)面的大小應(yīng)該適中，考慮到內(nèi)存效率和時(shí)間效率的權(quán)衡。

②地址結(jié)構(gòu)。分頁(yè)存儲(chǔ)管理的邏輯地址結(jié)構(gòu)：

地址結(jié)構(gòu)包含兩部分：前一部分為頁(yè)號(hào)P，后一部分為頁(yè)內(nèi)偏移量W。地址長(zhǎng)度為32位，其中0-11位為頁(yè)內(nèi)地址，即每頁(yè)大小為4KB；12-31位為頁(yè)號(hào)，地址空間最多允許有2^20頁(yè)。

③頁(yè)表。為了便于在內(nèi)存中找到進(jìn)程的每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊，系統(tǒng)為每個(gè)進(jìn)程建立一張頁(yè)表，記錄頁(yè)面在內(nèi)存中對(duì)應(yīng)的物理號(hào)，頁(yè)表 一般存放在內(nèi)存中。

在配置了頁(yè)表后，進(jìn)程執(zhí)行時(shí)通過(guò)查找該表，即可找到每頁(yè)在內(nèi)存中的物理塊號(hào)?？梢?jiàn)，頁(yè)表的作用是實(shí)現(xiàn)頁(yè)號(hào)到物理塊號(hào)的地址映射。

（2）基本地址的變換機(jī)構(gòu)

地址變換機(jī)構(gòu)的任務(wù)是將邏輯地址轉(zhuǎn)換為內(nèi)存中物理地址，地址變換是借助于頁(yè)表實(shí)現(xiàn)的。

在系統(tǒng)中通常設(shè)置一個(gè)頁(yè)表寄存器（PTR），存放頁(yè)表在內(nèi)存的始址F和頁(yè)表長(zhǎng)度M,進(jìn)程未執(zhí)行時(shí)，頁(yè)表的始址和長(zhǎng)度存放在進(jìn)程控制塊中，當(dāng)進(jìn)程執(zhí)行時(shí)，才將頁(yè)表始址和長(zhǎng)度存入頁(yè)表寄存器。設(shè)頁(yè)面大小為L(zhǎng)，邏輯地址A到物理地址E的變換過(guò)程如下：

①計(jì)算頁(yè)號(hào)P(P=A/L)和頁(yè)內(nèi)偏移量W(w=A%L)

②比較頁(yè)號(hào)P和頁(yè)表長(zhǎng)度M，若P>=M,則產(chǎn)生越界中斷，否則繼續(xù)執(zhí)行。

③頁(yè)表中P對(duì)應(yīng)的頁(yè)表項(xiàng)地址=頁(yè)表起始地址F+頁(yè)號(hào)*頁(yè)表項(xiàng)長(zhǎng)度，取出該頁(yè)表項(xiàng)內(nèi)容b,即為物理塊號(hào)。

④計(jì)算E=b*L+W

以上整個(gè)地址變換過(guò)程均是由硬件自動(dòng)完成的。

假如，頁(yè)面大小L為1K字節(jié)，頁(yè)號(hào)2對(duì)應(yīng)的物理塊為b=8，計(jì)算邏輯地址A=2500的物理地址 E的過(guò)程如下

p=2500/1K=2;

w=2500%1K=452;

查找得到頁(yè)號(hào)2對(duì)應(yīng)的物理塊的塊號(hào)為8，E=8*1024+452=8644.

下面討論分頁(yè)管理方式存在的兩個(gè)主要問(wèn)題：

①每次訪存操作都需要進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換，地址轉(zhuǎn)換過(guò)程必須足夠快，否則訪存速度會(huì)降低。

②每個(gè)進(jìn)程引入了頁(yè)表，用于存儲(chǔ)映射機(jī)制，頁(yè)表不能太大，否則內(nèi)存利用率會(huì)降低。

(3)具有快表的地址變換機(jī)構(gòu)

由上面介紹的地址變換過(guò)程可知。若頁(yè)表全部放在內(nèi)存中，則存取一個(gè)數(shù)據(jù)或一條指令至少要訪問(wèn)兩次內(nèi)存

第一次是訪問(wèn)頁(yè)表，確定所存取的數(shù)據(jù)或指令的物理地址

第二次才根據(jù)該地址存取數(shù)據(jù)或指令。

顯然，這種方法比通常執(zhí)行指令的速度慢了一半。

為此，在地址變換機(jī)構(gòu)中增設(shè)了一個(gè)具有并行查找能力的高速緩存存儲(chǔ)器——塊表，又稱(chēng)為聯(lián)想寄存器（TLB），用來(lái)存放當(dāng)前訪問(wèn)的若干頁(yè)表項(xiàng)，以加速地址變換的過(guò)程。于此對(duì)應(yīng)，主存中的頁(yè)表也常稱(chēng)為慢表。

在具有快表的分頁(yè)機(jī)制中，地址的變換過(guò)程：

①CPU給出邏輯地址后，由硬件地址進(jìn)行地址轉(zhuǎn)換并將頁(yè)號(hào)送入高速地址緩沖寄存器，并將此頁(yè)號(hào)與快表中的所有頁(yè)號(hào)進(jìn)行比較。

②如果找到匹配的頁(yè)號(hào)， 說(shuō)明所要訪問(wèn)的頁(yè)表項(xiàng)在塊表中，則直接從中取出該頁(yè)所對(duì)應(yīng)的頁(yè)框號(hào)，與頁(yè)內(nèi)偏移量拼接成物理地址。這樣存取數(shù)據(jù)僅一次訪存便可實(shí)現(xiàn)。

③如果沒(méi)有找到，則需要訪問(wèn)主存中的頁(yè)表，在讀出頁(yè)表項(xiàng)后，應(yīng)同時(shí)將其存入快表，以便后面可能的再次訪問(wèn)。但若快表已滿(mǎn)，則必須按照一定的算法對(duì)舊的頁(yè)表進(jìn)行替換。

注意：有些處理機(jī)設(shè)計(jì)為塊表和慢表同時(shí)查找，如果在塊表中查找成功則終止慢表的查找。

一般塊表的命中率可以達(dá)到90%以上，這樣，分頁(yè)帶來(lái)的速度損失降低到10%以下。快表的有效性是基于局部性原理。這在后面的虛擬內(nèi)存中將具體討論。

（4）兩級(jí)頁(yè)表

第二個(gè)問(wèn)題：由于引入了分頁(yè)管理，進(jìn)程在執(zhí)行時(shí)不需要將所有頁(yè)調(diào)入內(nèi)存頁(yè)框中，而只要將保存有映射關(guān)系的頁(yè)表調(diào)入內(nèi)存即可。但是我們?nèi)匀恍枰紤]頁(yè)表的大小。以32位邏輯空間，頁(yè)面大小4KB，頁(yè)表項(xiàng)大小4B為例，若要實(shí)現(xiàn)進(jìn)程對(duì)全部邏輯空間的映射，則每個(gè)進(jìn)程需要（2^32/4KB）2^20,約100萬(wàn)個(gè)頁(yè)表項(xiàng)。也就是說(shuō)，每個(gè)進(jìn)程僅頁(yè)表這一項(xiàng)就需要4MB主存空間，這顯然是不切合實(shí)際的。

而即便不考慮對(duì)全部邏輯地址空間進(jìn)行映射的情況，一個(gè)邏輯地址空間稍大的進(jìn)程，其頁(yè)表大小也可能是過(guò)大的。

①進(jìn)程舉例(全部放入內(nèi)存)

以一個(gè)40MB的進(jìn)程為例，頁(yè)表項(xiàng)共40KB(40MB/4KB*4B)，如果將所有頁(yè)表項(xiàng)內(nèi)容保存在內(nèi)存中，那么需要（40KB/4KB）10個(gè)內(nèi)存頁(yè)框來(lái)把保存整個(gè)頁(yè)表。整個(gè)進(jìn)程大小約為（40MB/4KB）1萬(wàn)個(gè)頁(yè)面，而實(shí)際執(zhí)行時(shí)只需要幾十個(gè)頁(yè)面進(jìn)入內(nèi)存頁(yè)框就可以運(yùn)行，但如果要求10個(gè)頁(yè)面大小的頁(yè)表必須全部進(jìn)入內(nèi)存，這相對(duì)實(shí)際執(zhí)行的幾十個(gè)進(jìn)程頁(yè)面的大小來(lái)說(shuō)，肯定是降低了內(nèi)存利用率的；從另一方面來(lái)講，這10頁(yè)的頁(yè)表項(xiàng)也并不需要同時(shí)保存在內(nèi)存中，因?yàn)榇蠖鄶?shù)情況下，映射所需要的頁(yè)表項(xiàng)都在頁(yè)表的同一頁(yè)面中。

解決方案：

為了壓縮頁(yè)表，我們將頁(yè)表映射的思想進(jìn)一步延伸，就可以得到二級(jí)分頁(yè)，即使用層次結(jié)構(gòu)的頁(yè)表：將頁(yè)表的10頁(yè)空間也進(jìn)行地址映射，建立上一級(jí)頁(yè)表，用于存儲(chǔ)頁(yè)表的映射關(guān)系。這里對(duì)頁(yè)表的10個(gè)頁(yè)面進(jìn)行映射只需要10個(gè)頁(yè)表項(xiàng)，所以上一級(jí)頁(yè)表只需要1頁(yè)就足夠（可以存儲(chǔ)2^10=1024個(gè)頁(yè)表項(xiàng)）。在進(jìn)程執(zhí)行時(shí)，只需要將1頁(yè)的上一級(jí)頁(yè)表調(diào)入內(nèi)存即可，進(jìn)程的頁(yè)表和進(jìn)程本身的頁(yè)面，可以在后面的執(zhí)行中再調(diào)入內(nèi)存。

②系統(tǒng)舉例（頁(yè)表理論占用最大內(nèi)存）

以上面提到的條件：32位邏輯地址空間、頁(yè)面大小4kB、頁(yè)表項(xiàng)大小4B，以字節(jié)為編址單位，我們就這個(gè)條件來(lái)構(gòu)造一個(gè)合適這個(gè)條件的頁(yè)表結(jié)構(gòu)。頁(yè)面大小為4KB,則頁(yè)內(nèi)偏移址為log2 4K=12位，頁(yè)號(hào)部分為20位，若不采用分級(jí)頁(yè)表，那么光頁(yè)表就要占用2^20*4B/4KB=1024頁(yè)（頁(yè)框），而這大大超過(guò)了許多進(jìn)程自身需要的頁(yè)面，對(duì)于內(nèi)存來(lái)說(shuō)是非常浪費(fèi)資源的，而且查詢(xún)頁(yè)表工作也變得十分不便，試想若把這些頁(yè)表放在連續(xù)的空間中，查詢(xún)對(duì)應(yīng)的物理頁(yè)號(hào)的時(shí)候可以通過(guò)頁(yè)表首頁(yè)地址+頁(yè)號(hào)*4B的形式得到，而這種方法查詢(xún)起來(lái)雖然相對(duì)方便，但是連續(xù)的1024頁(yè)對(duì)于內(nèi)存的要求實(shí)在太高，并且上面說(shuō)到了其中大多數(shù)頁(yè)面都是不會(huì)用到的，所以這種方法并不具有可行性。

解決方案：

如果不把這些頁(yè)表放在連續(xù)的空間中，我們就需要一張索引表來(lái)告訴我們第幾張應(yīng)該去哪找，這就能解決頁(yè)表的查詢(xún)問(wèn)題，并且不用把所有的頁(yè)表都調(diào)入內(nèi)存，只有需要它的時(shí)候才調(diào)入（虛擬存儲(chǔ)器思想），這就能解決占用內(nèi)存空間過(guò)大的問(wèn)題。

你也許會(huì)發(fā)現(xiàn)了這個(gè)方案和當(dāng)初引進(jìn)頁(yè)表機(jī)制的方式一模一樣，實(shí)際上就是構(gòu)建一個(gè)頁(yè)表的頁(yè)表，也就是二級(jí)頁(yè)表。為了查詢(xún)的方便，頂級(jí)頁(yè)表大小設(shè)立一個(gè)頁(yè)面，那么頂級(jí)頁(yè)表共可以容納4KB/4B=1K個(gè)頁(yè)表項(xiàng)，則它占用的地址位數(shù)為log2 1K=10位，而之前計(jì)算過(guò)頁(yè)內(nèi)偏移地址占用了12位，那么32位的邏輯地址空間就剩下10位，正好使得二級(jí)頁(yè)表的大小在一頁(yè)之內(nèi)，這樣我們就得到了路基地址空間的格式：

二級(jí)頁(yè)表實(shí)際上就是在原有頁(yè)表結(jié)構(gòu)上再加了一層頁(yè)表

建立多級(jí)頁(yè)表的目的在于建立索引，這樣不用浪費(fèi)主存空間去存儲(chǔ)無(wú)用的頁(yè)表項(xiàng)，也不用盲目地順序式查找頁(yè)表項(xiàng)，而建立索引的要求是最高一級(jí)頁(yè)表項(xiàng)不超過(guò)一頁(yè)的大小。