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

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

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

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

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

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

①頁面和頁面大小

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

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

②地址結構。分頁存儲管理的邏輯地址結構：

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

③頁表。為了便于在內存中找到進程的每個頁面所對應的物理塊，系統為每個進程建立一張頁表，記錄頁面在內存中對應的物理號，頁表 一般存放在內存中。

在配置了頁表后，進程執行時通過查找該表，即可找到每頁在內存中的物理塊號。可見，頁表的作用是實現頁號到物理塊號的地址映射。

（2）基本地址的變換機構

地址變換機構的任務是將邏輯地址轉換為內存中物理地址，地址變換是借助于頁表實現的。

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

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

②比較頁號P和頁表長度M，若P>=M,則產生越界中斷，否則繼續執行。

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

④計算E=b*L+W

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

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

p=2500/1K=2;

w=2500%1K=452;

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

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

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

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

(3)具有快表的地址變換機構

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

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

第二次才根據該地址存取數據或指令。

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

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

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

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

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

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

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

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

（4）兩級頁表

第二個問題：由于引入了分頁管理，進程在執行時不需要將所有頁調入內存頁框中，而只要將保存有映射關系的頁表調入內存即可。但是我們仍然需要考慮頁表的大小。以32位邏輯空間，頁面大小4KB，頁表項大小4B為例，若要實現進程對全部邏輯空間的映射，則每個進程需要（2^32/4KB）2^20,約100萬個頁表項。也就是說，每個進程僅頁表這一項就需要4MB主存空間，這顯然是不切合實際的。

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

①進程舉例(全部放入內存)

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

解決方案：

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

②系統舉例（頁表理論占用最大內存）

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

解決方案：

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

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

二級頁表實際上就是在原有頁表結構上再加了一層頁表

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