頁式管理

頁式管理是一種記憶體空間存儲管理的技術，頁式管理分為靜態頁式管理和動態頁式管理。

基本介紹

• 中文名：頁式管理
• 作用：將各虛擬空間劃分為長度相等的頁
• 構成方法：位示圖，空閒頁面鍊表發
• 所屬類型：計算機

實現原理

將各進程的虛擬空間劃分成若干個長度相等的頁(page)，頁式管理把記憶體空間按頁的大小劃分成片或者頁面（page frame），然後把頁式虛擬地址與記憶體地址建立一一對應頁表，並用相應的硬體地址變換機構，來解決離散地址變換問題。頁式管理採用請求調頁或預調頁技術實現了內外存存儲器的統一管理。

頁的劃分

主要分類

靜態

記憶體頁面分配與回收

靜態分頁管理的第一步是為要求記憶體的作業或進程分配足夠的頁面。系統通過存儲頁面表、請求表以及頁表來完成記憶體的分配工作。

頁表：記憶體中的一塊固定存儲區。頁式管理時每個進程至少有一個頁表。

請求表：用來確定作業或進程的虛擬空間的各頁在記憶體中的實際對應位置；

存儲頁面表：整個系統有一個存儲頁面表，其描述了物理記憶體空間的分配使用狀況。

存儲頁面表有兩種構成方法：

1、位示圖法

2、空閒頁面鍊表法

分配算法

首先，請求表給出進程或作業要求的頁面數。然後，由存儲頁面表檢查是否有足夠的空閒頁面，如果沒有，則本次無法分配。如果有則首先分配設定頁表，並請求表中的相應表項後，按一定的查找算法搜尋出所要求的空閒頁面，並將對應的頁好填入頁表中。

頁面分配算法

地址變換

首先，需要有一個裝置頁表始址和頁表長度用的控制暫存器。系統所調度執行的進程頁表始址和長度從請求表中取出送入控制暫存器中。然後，由控制暫存器頁表始址可以找到頁表所在位置。

靜態頁式管理解決了分區管理時的碎片問題。但是，由於靜態頁式管理要求進程或作業在執行前全部裝入記憶體，如果可用頁面數小於用戶要求時，該作業或進程只好等待。而且作業和進程的大小仍受記憶體可用頁面數的限制。

動態

動態頁式管理是在靜態頁式管理的基礎上發展起來的。它分為請求頁式管理和預調入頁式管理。請求頁式管理和預調入頁式管理在作業或進程開始執行之前，都不把作業或進程的程式段和數據段一次性地全部裝入記憶體，而只裝入被認為是經常反覆執行和調用的工作區部分。其它部分則在執行過程中動態裝入。請求頁式管理與預調入頁式管理的主要區別在它們的調入方式上。請求頁式管理的調入方式是，當需要執行某條指令而又發現它不在記憶體時或當執行某條指令需要訪問其它的數據或指令時．這些指令和數據不在記憶體中，從而發生缺頁中斷，系統將外存中相應的頁面調入記憶體。

加入中斷處理後的頁表

預調入方式是，系統對那些在外存中的頁進行調入順序計算。估計出這些頁中指令和數據的執行和被訪問的順序，並按此順序將它們順次調入和調出記憶體。除了在調入方式上請求頁式管理和預調入管理有些區別之外，其它方面這兩種方式基本相同。因此，下面我們主要介紹請求頁式管理。

請求頁式管理的地址變換過程與靜態頁式管理時的相同，也是通過頁表查出相應的頁面號之後，由頁面號與頁內相對地址相加而得到實際物理地址，但是，由於請求頁式管理只讓進程或作業的部分程式和數據駐留在記憶體中，因此，在執行過程中，不可避免地會出現某些虛頁不在記憶體中的問題。怎樣發現這些不在記憶體中虛頁以及怎樣處理這種情況．是請求頁式管理必須解決的兩個基本問題。

第一個問題可以用擴充頁表的方法解決。即與每個虛頁號相對應，除了頁面號之外，再增設該頁是否在記憶體的中斷位以及該頁在外存中的副本起始地址。關於虛頁不在記憶體時的處理，涉及到兩個問題。第一，採用何種方式把所缺的頁調入記憶體。第二，如果記憶體中沒有空閒頁面時，把調進來的頁放在什麼地方。也就是說，採用什麼樣的策略來淘汰已占據記憶體的頁。還有，如果在記憶體中的某一頁被淘汰，且該頁曾因程式的執行而被修改，則顯然該頁是應該重新寫到外存上加以保存的。而那些未被訪問修改的頁、因為外存已保留有相同的副本，寫回外存是沒有必要的。因此，在頁表中還應增加一項以記錄該頁是否曾被改變。

動態頁式管理流程圖

在動態頁管理的流程中，有關地址變換部分是由硬體自動完成的。當硬體變換機構發現所要求的頁不在記憶體時，產生缺頁中斷信號，由中斷處理程式做出相應的處理。中斷處理程式是由軟體實現的。除了在沒有空閒頁面時要按照置換算法選擇出被淘汰頁面之外，還要從外存讀入所需要的虛頁。這個過程要啟動相應的外存和涉及到檔案系統。因此，請求頁式管理是一個十分複雜的處理過程，記憶體的利用率的提高是以犧牲系統開銷的代價換來的。

置換算法

功能：需要調入頁面時，選擇記憶體中哪個物理頁面被置換。稱為replacement policy。

出發點：把未來不再使用的或短期內較少使用的頁面調出，通常只能在局部性原理指導下依據過去的統計數據進行預測。

頁面鎖定(frame locking)：用於描述必須常駐記憶體的作業系統的關鍵部分或時間關鍵(time-critical)的套用進程。實現方法為在頁表中加上鎖定標誌位(lock bit)。

隨機淘汰

隨機淘汰算法(random golongram):在系統設計人員認為無法確定哪些頁被訪問的機率較低時，隨機地選擇某個用戶的頁面並將其換出將是一種明智的作法。

輪轉法

輪轉法(RR,round robin)和先進先出算法(FIFO,first in first out):輪轉法循回換出記憶體可用區內一個可以被換出的頁，無論該頁是剛被換進或已換進記憶體很長時間。FIFO算法總是選擇在記憶體駐留時間最長的一員將其淘汰。

先進先出

FIFO算法認為先調入記憶體的頁不再被訪問的可能性要比其它頁大，因而選擇最先調入記憶體的頁換出。實現FIFO算法需要把各個已分配頁面按分配時間順序連結起來，組成FIFO佇列，並設定一置換指針指向FIFO佇列的隊首頁面。這樣，當要進行置換時，只需把置換指針所指的FIFO佇列前頭的頁順次換出，而把換入的頁連結在FIFO隊尾即可。

由實驗和測試發現FIPO算法和RR算法的記憶體利用率不高。這是因為，這兩種算法都是基於CPU按線性順序訪問地址空間這一假設。事實上，許多時候．CPU不是按線性順序訪問地址空間的。

Belady現象:一般來說，對於任一作業或進程，如果給它分配的記憶體頁面數越接近於它所要求的頁面數，則發生缺頁的次數會越少。在極限情況下，這個推論是成立的。因為如果給一個進程分配了它所要求的全部頁面，則不會發生缺頁現象。但是，使用FIFO算法時，在未給進程或作業分配足它所要求的頁面數時，有時會出現分配的頁面數增多，缺頁次數反而增加的奇怪現象。這種現象稱為Belady現象。

最近最久

最近最久未使用頁面置換算法(LRU, Least Recently Used):

選擇記憶體中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。但由於需要記錄頁面使用時間的先後關係，硬體開銷太大。硬體機構如：

(1) 一個特殊的棧：把被訪問的頁面移到棧頂，於是棧底的是最久未使用頁面。

(2) 每個頁面設立移位暫存器：被訪問時左邊最高位置1，定期右移並且最高位補0，於是暫存器數值最小的是最久未使用頁面。

比較常用的近似算法有：

(a) 最不經常使用頁面淘汰算法(LFU, Least Frequently Used)

(b) 最近沒有使用頁面淘汰(NRU, Not Recently Used)

理想型淘汰

理想型淘汰算法（OPT,Optimal Replacement Algorithm）

該算法淘汰在訪問串中將來再也不出現的或是離當前最遠的位置上出現的頁。它是一種理想化的算法，性能最好，但在實際上難於實現。

存儲保護

頁式管理可以為記憶體提供兩種方式的保護。一種是地址越界保護，另一種是通過頁表控制對記憶體信息的操作方式以提供保護。

地址越界保護可由地址變換機構中的控制暫存器的值一一頁表長度和所要訪問的慮地址相比較完成。

存取控制保護的實現則是在頁表中增加相應的保護位即可。

優缺點

優點

1、由於它不要求作業或進程的程式段和數據在記憶體中連續存放，從而有效地解決了碎片問題。

2、動態頁式管理提供了記憶體和外存統一管理的虛存實現方式，使用戶可以利用的存儲空間大大增加。這既提高了主存的利用率，又有利於組織多道程式執行。

缺點

1、要求有相應的硬體支持。例如地址變換機構，缺頁中斷的產生和選擇淘汰頁面等都要求有相應的硬體支持。這增加了機器成本。

2、增加了系統開銷，例如缺頁中斷處理機，

3、請求調頁的算法如選擇不當，有可能產生抖動現象。

4、雖然消除了碎片，但每個作業或進程的最後一頁內總有一部分空間得不到利用果頁面較大，則這一部分的損失仍然較大。