頁式管理

將各進程的虛擬空間劃分成若干個長度相等的頁(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、雖然消除了碎片，但每個作業或進程的最後一頁內總有一部分空間得不到利用果頁面較大，則這一部分的損失仍然較大。