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

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

1、基本分頁存儲管理方式

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

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

（1）分頁存儲的幾個基本概念

①頁面和頁面大小

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

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

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

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

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

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

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

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

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

①計算頁號P(P=A/L)和頁內(nèi)偏移量W(w=A%L)

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

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

④計算E=b*L+W

以上整個地址變換過程均是由硬件自動完成的。

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

p=2500/1K=2;

w=2500%1K=452;

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

下面討論分頁管理方式存在的兩個主要問題：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（4）兩級頁表

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

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

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

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

解決方案：

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

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

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

解決方案：

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

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

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

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