虛拟記憶體
計算機系統使用的各種記憶體管理政策。所有這些政策都為同一目的：同時将多個程序存放在記憶體中，以便多道程式設計。不過，這些政策都需要在程序執行之前将整個程序放在記憶體中。
虛拟記憶體技術允許執行程序不必完全在記憶體中。這種方案的一個顯著優點是程式可以比實體記憶體大。而且，虛拟記憶體将記憶體抽象成一個巨大，統一的存儲數組，進而将使用者看到的邏輯記憶體與實體記憶體分開。這種技術允許程式員不受記憶體的限制。虛拟記憶體也允許程序很容易地共享檔案和位址空間。還為建立程序提供了有效的機制。但是，虛拟記憶體的實作并不容易，如果使用不當可能會大大的降低性能。
背景
上一節介紹的記憶體管理算法都基于一個基本要求：執行指令必須在實體記憶體中。滿足這一要求的第一種方法是将整個程序放在記憶體中。動态載入能幫助減輕這一限制，但是它需要程式員特别小心并且需要一些額外的工作。
指令必須都在實體記憶體的這一限制，這似乎是必須和合理的，但也是不幸的，因為這使得程式的大小被限制在實體記憶體的大小以内。事實上，研究實際程式會發現，在許多情況下并不需要将整個程式放在記憶體中。
能夠執行隻有部分在記憶體中的程式可帶來很多好處：
程式不再受現有的實體記憶體空間限制。使用者可以為一個巨大的虛拟位址空間(virtual address space)寫程式，簡化工作量。
因為每個使用者程式使用了更少的實體記憶體，是以更多的程式可以同時執行，CPU使用率也相應增加，而響應時間或周轉時間并不增加。
由于載入或交換每個使用者程式到記憶體内所需的I/O會更少，使用者程式會運作得更快。
虛拟記憶體（virtual memory）将使用者邏輯記憶體與實體記憶體分開。
程序的虛拟位址空間就是程序如何在記憶體中存放的邏輯（或虛拟）視圖。通常，該視圖為程序從某一邏輯位址（如位址0）開始，連續存放。實體位址可以按頁幀來組織，且配置設定給程序的實體頁幀也可能不是連續的。這就需要記憶體管理單元（MMU）将邏輯頁映射到實體頁幀。
如下圖所示，允許随着動态記憶體配置設定，堆可向上生長。類似地，還允許随着子程式的不斷調用，棧可以向下生長。堆與棧之間的巨大空白空間（或洞）為虛拟位址的一部分，隻有在堆與棧生長時，才需要實際的實體頁。包括空白的虛拟位址空間稱為稀位址空間。采用稀位址空間的優點是：随着程式的執行，堆或棧的生長或需要載入動态連結庫或（共享對象）時，這些空白可以填充。
除了将邏輯記憶體與實體記憶體分開，虛拟記憶體也允許檔案和記憶體通過共享頁而為兩個或多個程序所共享。
通過将共享對象映射到虛拟位址空間，系統庫可為多個程序所共享。雖然每個程序都認為共享庫是其虛拟位址空間的一部分，而共享所用的實體記憶體的實際頁是為所有程序所共享。通常庫是按隻讀方式來連結每個程序的空間。
類似的，虛拟記憶體允許程序共享記憶體。兩個或多個程序之間可以通過使用共享記憶體來通信。虛拟記憶體允許一個程序建立記憶體區域，以便與其他程序共享。共享記憶體區域的程序認為它是其虛拟位址空間的一部分，而事實上這部分是共享的。
虛拟記憶體可允許在用系統調用fork()建立程序期間共享頁，進而加快程序建立。
按需調頁
看看一個執行程式是如何從磁盤載入記憶體的。一種選擇是在程式執行時，将整個程式載入到記憶體。不過，這種方法的問題是可能開始并不需要整個程式在記憶體。如有的程式開始時帶有一組使用者的可選的選項。載入整個程式，也就将所有選項的執行代碼都載入到記憶體中，而不管這些選項是否使用。另一種選擇是在需要時才調入相應的頁。這種技術稱為按需調頁（demand paging）, 常為虛拟記憶體系統所采用。對于按需調頁虛拟記憶體，隻有程式執行需要時才載入頁，那些從未通路的頁不會調入到實體記憶體。
按需調頁系統類似于使用交換的分頁系統，程序駐留在第二級存儲器上（通常為磁盤）。當需要執行程序時，将它換入記憶體。不過，不是将整個程序換入記憶體，而是使用懶惰交換（lazy swapper）。懶惰較厚安隻有在需要頁時，才将它調入記憶體。由于将程序看做是一系列的頁，而不是一個大的連續空間，是以使用交換從技術上來講并不正确。交換程式（swapper）對整個程序操作，而調頁程式（paper）隻是對程序的單個頁進行操作。是以，在讨論有關按需調頁，需要使用調頁程式而不是交換程式。
基本概念
當換入程序時，調頁程式推測在該程序再次換出之前會用到哪些頁。調頁程式不是調入整個程序，而是把那些必須的頁調入記憶體。這樣，調頁程式就避免了讀入那些不使用的頁，也減少了交換時間和所需的實體記憶體空間。
對于這種方案，需要一定形式的硬體支援來區分那些頁在記憶體中，哪些頁在磁盤上。可以通過有效-無效位來設定。當該位設定為"有效"時，該值表示相關的頁即合法也在記憶體中。當該位設定為"無效"時，該值表示相關的頁為無效（也就是，不在程序的邏輯位址空間内），或者有效但是在磁盤上。對于調入記憶體的頁，其也表條目的設定與平常一樣；但是對于不在記憶體的頁，其頁表條目設定為無效，或包含該頁在磁盤上的位址。
如果程序從不試圖通路标記為無效的頁，那麼并沒有什麼影響。是以，如果推測正确并且隻調入所有真正需要的頁，那麼程序就如同所有頁都已調入一樣正常運作。當程序執行和通路那些駐留在記憶體中的頁時，執行會正常進行。
但是當程序試圖通路那些尚未調入到記憶體的頁時，對标記為無效的通路會産生頁錯誤陷阱（page-fault trap）。分頁硬體，在通過頁表轉換位址時，将發現已設定了無效位，會陷入作業系統。這種陷阱時由于作業系統未能将所需的頁調入記憶體引起的。
處理這種頁錯誤的程式比較簡單：
- 檢查程序的内部頁表（通常與PCB一起儲存），以确定該引用時合法還是非法的位址通路。
- 如果引用非法，那麼終止程序。如果引用有效但是尚未調入頁面，那麼現在應調入。
- 找到一個空閑幀（例如，從空閑幀連結清單中選取一個）。
- 排程一個磁盤操作，以便将所需要的頁調入剛配置設定的幀。
- 當磁盤讀操作完成後，修改程序的内部表和頁表，以表示該頁已在記憶體中。
- 重新開始因陷阱而中斷的指令。程序現在能通路所需的頁，就好像它似乎總在記憶體中。
存粹按需調頁：所有的頁都不在記憶體中，就開始執行。
支援按需調頁的硬體與分頁和交換的硬體一樣：
頁表：該表能夠通過有效-無效位或保護位的特定值，将條目設為無效。
次級存儲器：該次級存儲器用來儲存不在記憶體中的頁。次級存儲其通常位快速磁盤。它通常稱為交換裝置，用于交換的這部分磁盤稱為交換空間（swap space）。
請求調頁的關鍵要求是能夠在頁錯誤後重新執行指令。在出現頁錯誤時，儲存中斷程序的狀态（寄存器，條件代碼，指令計數器），必須能夠按完全相同的位置和位址重新開始執行進，隻不過現在所需的頁已在記憶體中且可以通路。對絕大多數情況來說，這種要求容易滿足。也錯誤可能出現在任何記憶體引用中。如果也錯誤出現在指令擷取時，那麼可以再次擷取指令。如果頁錯誤出現擷取操作數時，那麼可以再次擷取指令、再次譯碼指令，然後再次擷取操作數。
按需調頁的性能
按需調頁對計算機系統的性能有重要影響。為了說明起見，下面計算一下關于按需調頁記憶體的有效通路時間（effective access time）。隻要沒有出現頁錯誤，那麼有效通路時間等于記憶體通路時間（用ma表示）。然而，如果出現頁錯誤，那麼就必須從磁盤中讀入相關頁，再通路所需要的字。
設p為頁錯誤的機率(0<p<1)。如果p接近與0，即頁錯誤很少。那麼有效通路時間為：
有效通路時間=(1-p)*ma+p*頁錯誤時間
為了計算有效時間，必須知道處理頁錯誤需要多少時間。頁錯誤會引起如下序列的動作産生：
- 陷入作業系統。
- 儲存使用者寄存器和程序狀态。
- 确定中斷是否為頁錯誤。
- 檢查頁引用是否合法并确定頁所在磁盤的位置。
- 從磁盤讀入頁到空閑幀中。
- 在該磁盤隊列中等待，直到處理完請求。
- 等待磁盤的尋道和/或延遲時間。
- 開始将磁盤的頁傳到空閑幀。
- 在等待時，将CPU配置設定給其他使用者（CPU排程，可選）。
- 從I/O子系統接收到中斷（以示I/O完成）。
- 儲存其他使用者的寄存器和程序狀态。
- 确定中斷是否來自磁盤。
- 修正頁表和其他表以表示所需頁現已在記憶體中。
- 等待CPU再次配置設定給本程序。
- 恢複使用者寄存器、程序狀态和新頁表，再重新執行中斷的指令。
主要經曆了兩次上下文切換，以及磁盤的讀取等待。
寫時複制
通過采用類似頁面共享的技術，采用系統調用fork建立程序的開始階段可能需要按需調頁。這種技術提供了快速程序建立，且最小化新建立程序必須配置設定的新頁面的數量。
系統調用fork()是将子程序建立為父程序的複制品。傳統上，fork()為子程序建立一個父程序位址空間的副本，複制屬于父程序的頁。然而，由于許多子程序在建立之後通常馬上會執行系統調用exec(),是以父程序位址空間的複制可能沒有必要。是以，可以使用一種稱為寫時複制（copy-on -write）的技術。這種技術允許父程序與子程序開始時共享同一頁面。這些頁面标記為寫時複制頁，即如果任何一個程序需要對頁進行寫操作，那麼就建立一個共享頁的副本。
例如，假設子程序試圖修改含有部分棧的頁，且作業系統能識别該頁被設定為寫時複制頁，那麼作業系統就會建立一個該頁的副本，并将它映射到子程序的位址空間内。這樣，子程序會修改其複制的頁，而不是父程序的頁。采用寫時複制技術，很顯然隻有能被程序修改的頁才會被複制；所有非修改頁可為父程序和子程序所共享。
當确定一個頁采用寫時複制時，從哪些配置設定空閑頁是很重要的。許多作業系統為這類請求提供空閑緩沖池（pool）。這些空閑頁在程序棧或堆必須擴充時可用于配置設定。或用于管理寫時複制頁。作業系統通常采用按需填零(zero-fill-on-demand)的技術以配置設定這些頁。按需填零頁在需要配置設定之前先填零，是以清除了以前的内容。
頁面置換
基本頁置換
頁置換采用如下方法。如果沒有空閑幀，那麼就查找目前沒有使用的幀，并将其釋放。可采用這樣的方式來釋放一個幀：将其内容寫到交換空間，并改變頁表（和所有其他表）以表示該頁不在記憶體中。現在可使用空閑幀來儲存程序出錯的頁。修改頁錯誤處理程式以包括頁置換：
- 查找所需要頁在磁盤上的位置。
- 查找一個空閑幀
- 如果有空閑幀，那麼就使用它。
- 如果沒有空閑幀，那麼就是用頁置換算法以選擇一個"犧牲"幀（victim frame）。
- 将"犧牲"幀的内容寫到磁盤上，改變頁表和幀表。
- 将所需頁讀入（新）空閑幀，改變頁表和幀表。
- 重新開機使用者程序。
注意，如果沒有空閑幀，那麼需要采用兩個頁傳輸（一個換出，一個換入）。這種情況實際上把也錯誤處理時間加倍了，且也相應地增加了有效通路時間。
可以通過使用修改位（modify bit）或髒位（dirty bit）以降低額外開銷。每頁或幀可以有一個修改位，通過硬體與之相關聯。每當頁内的任何字或位元組被寫入時，硬體就會設定該頁的修改位以表示頁已修改。如果修改位已設定，那麼就可以知道自從磁盤讀入後該頁已發生了修改。在這種情況下，如果該頁被選擇位替換頁，就必須要把該頁寫到磁盤上去。然而，如果修改位沒有設定，那麼也就知道自從磁盤讀入都該頁并沒有發生修改。是以，磁盤上頁的副本的内容沒有必要重寫，是以就避免了将記憶體頁寫回磁盤上：它已經在那裡了。
為了實作按需調頁，必須解決兩個主要問題：必須開發幀配置設定算法（frame-allocation algorithm）和頁置換算法（page-replacement algorithm）。
可以采用這樣來評估一個算法：針對特定記憶體引用序列，運作某個置換算法，并計算出頁錯誤的數量。記憶體的引用序列稱為引用串（reference string）。為了降低數量量，可利用以下兩個事實。
第一：對給定頁大小（頁大小通常由硬體或系統來決定），隻需要考慮頁碼，而不需要完整位址。
第二：如果有一個對頁p的引用，那麼任何緊跟着對頁p的引用決不會産生頁錯誤。頁p第一次引用時已在記憶體中，任何緊跟着的引用不會出錯。
針對某一特定引用串和頁置換算法，為了确定頁錯誤的數量，還需知道可用幀的數量。顯然，随着可用幀數量的增加，頁錯誤的數量會相應地減少。
為了讨論頁置換算法，将采用如下引用串：
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
而可用幀的數量位3.
FIFO頁置換
最簡單的頁置換算法時FIFO算法。FIFO頁置換算法為每個頁記錄着該頁調入記憶體的時間。當必須置換一頁時，将選擇最舊的頁。注意并不需要記錄調入一頁的确切時間。可以建立一個FIFO隊列來管理記憶體中的所有頁。隊列中的首頁将被置換。當需要調入頁時，将它加到隊列的尾部。
FIFO頁置換算法性能并不總是很好。
為了說明與FIFO頁置換算法相關可能問題，考慮如下引用串：
頁錯誤對現有幀數的曲線，這種最為令人難以置信的結果稱為Belady異常（Belady's anomaly）:對有的頁置換算法，頁錯誤率可能會随着所配置設定的幀數的增加而增加，而原期望為程序增加記憶體會改善其性能。在早期研究中，研究人員注意到這種推測并不總是正确的。是以，發現了Belady異常。
最優置換
Belady異常發現的結果之一是對最優頁置換算法（optimal page-replacement algorithm）的搜尋。最優置換算法是所有算法中産生錯誤率最低的，且絕沒有Belady異常的問題。這種算法确實存在，它被稱為OPT或MIN。它會置換将來最長時間不會使用的頁。使用這種頁置換算法確定對于給定數量的幀會産生最低可能的頁錯誤率。
最優置換算法難以實作，因為需要引用串的未來知識。是以，最優算法主要用于比較研究。如果知道一個算法不是最優的，但是與最優相比最壞不差于12.3%,平均不差于4.7%,那麼也是很有用的。
LRU頁置換
FIFO和OPT算法的關鍵差別在于，FIFO算法使用的是頁調入記憶體的時間，OPT算法使用的是頁将來使用的時間。如果使用離過去最近作為不遠将來的近似，那麼可置換最長沒有使用的頁，這種方法稱為最近最少使用算法（least-recently-used(LRU) algorithm）
LRU政策經常用做頁置換算法，且被認為相當不錯。其主要問題是如何實作LRU置換。LRU頁置換算法可能需要一定的硬體支援。它的問題是為頁幀确定一個排序序列，這個序列按頁幀上次使用的時間來定。有兩種可行實作。
計數器：最為簡單的情況是，為每個頁表關聯一個使用時間域，并為CPU增加一個邏輯時鐘或計數器。對每次記憶體引用，計數器都會增加。每次記憶體引用時，始終寄存器的内容會被複制到相應頁所對應頁表項的使用時間域内。用這種方式就得到每頁的最近引用時間。置換具有最小時間的頁。這種方案需要搜尋頁表以查找LRU頁，且每次記憶體通路都要寫入記憶體（到頁表的使用時間域）。在頁表改變時（因CPU排程）也必須保持時間。
棧：實作LRU置換的另一個方法時采用頁碼棧。每當引用一個頁，該頁就從棧中删除并放在頂部。這樣，棧頂總是最近使用的頁，棧底部總是LRU頁。由于必須從棧中部删除項，是以該棧可實作為具有頭指針和尾指針的雙向連結清單。這樣，删除一頁 并放在棧頂部在最壞情況下需要改變6個指針。雖然說更新有點費時，但是置換不需要搜尋；尾指針指向棧底部，就是LRU頁。
最優置換和LRU置換都沒有Belady異常。這兩個都屬于同一類算法，稱為棧算法（stack algorithm）,都絕不可能有Belady異常。
近似LRU頁置換
頁表内的每項都關聯着一個引用位（reference bit）。每當引用一個頁時（無論是對頁的位元組進行讀或寫），相應頁表的引用位就被硬體置位。
開始，作業系統會将所有引用位清零。随着使用者程序的執行，與引用頁相關聯的引用位被硬體置位（置為1）。之後，通過檢查引用位，能夠确定那些頁使用過而那些頁未使用過。雖然不知道使用順序，但是知道那些頁用過而那些頁未用過。這些資訊是許多近似LRU頁置換算法的基礎。
附加引用位算法：可以為位于記憶體内的每個表中的頁保留一個8位的位元組。在規定時間間隔内，時鐘定時器産生中斷并将控制轉交給作業系統。作業系統把每個頁的引用位轉移到其8位位元組的高位，而将其他位向右移一位，并抛棄最低位。這些8位移位寄存器包含着頁在最近8個時間周期内的使用情況。如果将這8位位元組作為無符号整數，那麼具有最小值的頁位LRU頁，且可以被置換。注意這些數字并不唯一。可以置換所有具有最小值的頁，或在這些頁之間采用FIFO來選擇置換。
在極端情況下，隻有引用位本身。這種算法稱為第二次機會頁置換算法（second-chance page-replacement algorithm）。
二次機會算法
二次機會置換的基本算法是FIFO置換算法。當要選擇一個頁時，檢查其引用位。如果其值為0，那麼就直接置換該頁。如果引用位為1，那麼就給該頁第二次機會，并選擇下一個FIFO頁。當一個頁獲得第二次機會時，其引用位清零，且其到達時間設為目前時間。獲得第二次機會的頁在所有其他頁置換（或獲得第二次機會）之前，是不會被置換的。另外，如果一個頁經常使用以緻其引用位總是被設定，那麼它就不會被置換。
一種實作二次機會算法（有時稱為時鐘算法）的方法是采用循環隊列。用一個指針表示下次要置換哪一頁。當需要一個幀時，指針向前移動直到找到一個引用位位0的頁。在向前移動時，它将清除引用位。一旦找到犧牲頁，就置換該頁，新頁就插入到循環隊列的該位置。
注意：在最壞情況下，所有位均已設定，指針會周遊整個循環隊列，以便給每個頁第二次機會。它将清除所有引用位後再選擇頁來置換。這樣，如果所有位均已設定，那麼第二次機會置換就變成了FIFO置換。
增強二次機會算法：通過将引用位和修改位作為一有序對來考慮，可以改進二次機會算法。采用這兩個位，有下面四種可能類型：
（0，0）最近沒有使用且也沒有修改-----用于置換的最佳頁。
（0，1）最近沒有使用但修改過——不是很好，因為在置換之前需要将頁寫出到磁盤
（1，0）最近使用過但沒有修改——它有可能很快又要被使用
（1，1）最近使用過且修改過——它有可能很快又要被使用，且置換之前需要将頁寫出到磁盤。
每個頁都屬于這四種類型之一。當頁需置換時，可使用時鐘算法，不是檢查所指頁的引用位是否設定，而是檢查所指頁屬于哪個類型。置換在低非空類中所碰到的頁。注意在找到要置換頁之前，可能要多次搜尋整個循環隊列。
這種方法與簡單時鐘算法的主要差别時這裡給那些已經修改過的頁以更高的級别，進而降低了所需I/O的數量。
基于計數的頁置換
還有許多其他算法可用于頁置換。例如，可以為每個頁保留一個用于記錄其引用次數的計數器，并可形成如下兩個方案。
最不經常使用頁置換算法（least frequently used(LFU) page-replacement algorithm）要求置換計數最小的頁。這種選擇的理由是活動頁應該有更大的引用次數。這種算法會産生如下問題：一個頁在程序開始時使用很多，但以後就不再使用。由于其使用過很多，是以它有較大次數，是以即使不再使用仍然會在記憶體中。解決方法之一時定期地将次數寄存器右移一位，以形成指數衰減的平均使用次數。
最常使用頁置換算法（most frequently used(MFU) page-replacement algorithm）是基于如下理論：具有最小次數的頁可能剛剛調進來，且還沒有使用。
頁緩沖算法
除了特定頁置換算法外，還經常采用其他措施。例如，系統通常保留一個空閑幀緩沖池。當出現頁錯誤時，會像以前一樣選擇一個犧牲幀。然而，在犧牲幀寫出之前，所需要的頁就從緩沖池中讀到空閑記憶體。這種方法允許程序盡可能快地啟動，而無須等待犧牲幀頁地寫出。當在犧牲幀以後寫出時，它再加入到空閑幀池。
這種方法地擴充之一是維護一個已修改頁地清單。每當調頁裝置空閑時，就選擇一個修改頁并寫到磁盤上，接着重新設定其修改位。這種方法增加了當需要選擇置換時幹淨頁地機率而不必寫出。
另一個修改是保留一個空閑幀池，但是要記住哪些頁再哪些幀中。由于當幀寫到磁盤上時其内容并沒有修改，是以再該幀被重用之前如果需要使用原來頁，那麼原來頁可直接從空閑幀池中取出來使用。這時并不需要I/O。當一個頁錯誤發生時，先檢查所需要頁是否在空閑幀池中。如果不在，那麼才必須選擇一個空閑幀來讀入所需頁。
幀配置設定
如何在各個程序之間配置設定一定地空閑記憶體？如果有93個空閑幀和2個程序，那麼每個程序各得到多少幀？
幀的最少數量
配置設定至少最少數量地幀地原因之一時性能。顯然，随着配置設定給每個程序地幀數量地減少，頁錯誤會增加，進而減慢程序的執行。另外，記住：當在指令完成之前出現頁錯誤時，該指令必須重新執行。是以，必須有足夠的幀來容納所有單個指令所引用的頁。
配置設定算法
在n個程序之間配置設定m個幀的最為容易的方法是給每個一個平均值，即m/n幀。例如，如果有93個幀和5個程序，那麼每個程序可得到18個幀，剩餘3個幀可以放在空閑幀緩存池中。這種方案稱為平均配置設定（equal allocation）。
也可以使用比例配置設定（proportional allocation）。根據程序大小，而将可用記憶體配置設定給每個程序。設程序Pi的虛拟記憶體大小位Si，且定義
這樣，如果可用幀的總數為m，那麼程序pi可配置設定到ai個幀，這裡ai近似為：
全局配置設定與局部配置設定
為各個程序配置設定幀的另一個重要因素是頁置換。當多有個程序競争幀時，可将頁置換算法分為兩個大類：全局置換（global replacement）和局部置換（local replacement）。全局置換允許一個程序從所有幀集合中選擇一個置換幀，而不管該幀是否已配置設定給其他程序，即一個程序可以從另一個程序中拿到幀。局部置換要求每個程序僅從其自己的配置設定幀中進行選擇。全局置換允許高優先級程序從低優先級程序中選擇幀以便置換。一個程序可以從自己的幀中或任何低優先級程序中選擇置換幀。這種方法允許高優先級程序增加其幀配置設定而以損失低優先級程序為代價。因為局部置換不能使用其他程序的不常用的記憶體，是以阻礙一個程序。是以，全局置換通常會有更好的系統吞吐量，且更為常用。
系統颠簸
如果低優先級程序所配置設定的幀數量少于計算機體系結構所要求的最少數量，那麼必須暫停程序執行。接着應換出其他所有剩餘頁，以便使其所有配置設定的幀空閑。這引入了中程CPU排程的換進換出層。
沒有"足夠"幀的程序。如果程序沒有它所需要的活躍使用的幀，那麼它會很快産生頁錯誤。這時，必須置換某個頁。然而，其所有頁都在使用，它置換一個頁，但又立刻再次需要這個頁。是以，它會一而再地産生頁錯誤，置換一個頁，而該頁又立刻出錯且需要立即調進來。
這種頻繁地頁排程行為稱為颠簸（thrashing）。如果一個程序在換頁上用的時間要多餘執行時間，那麼這個程序就在颠簸。
系統颠簸的原因
在早期調頁系統中，作業系統在監視CPU的使用率，如果CPU使用率太低，那麼向系統中引入新程序，以增加多道程式的程式。采用全局置換算法，它會置換頁而不管這些頁是屬于哪個程序的。現在假設一個程序進入一個新執行階段，需要更多的幀。它開始出現頁錯誤，并從其他程序中拿到幀。然而，這些程序也需要這些頁，是以它們也會出現頁錯誤，進而從其他程序中拿到幀。這些頁錯誤程序必須使用調頁裝置以換進和換出頁。随着它們排隊等待換頁裝置，就緒隊列會變空，而程序等待調頁裝置，CPU使用率就會降低。CPU排程程式發現CPU使用率降低，是以會增加多道程式的程式。新程序試圖從其他運作程序中拿到幀，進而引起更多頁錯誤，形成更長的調頁裝置的隊列。
通過局部置換算法（local replacement algorithm）(或優先置換算法（priority replacement algorithm）)能限制系統颠簸。采用局部置換，如果一個程序開始颠簸，那麼它不能從其他程序拿到幀，且不能使後者也颠簸。然而這個問題還沒有完全得到解決，如果程序颠簸，那麼絕大多數時間内也會排隊來等待調頁裝置。由于調頁裝置的更長的平均隊列，也錯誤的平均等待時間也會增加。是以，即使對沒有颠簸的程序，其有效通路時間也會增加。
為了防止颠簸，必須提供程序所需的足夠多的幀。但是如何知道程序"需要"多少幀呢？有多種技術。工作集合政策是研究一個程序實際正在使用多少幀。這種方法定義了程序執行的局部模型（locality model）。
局部模型說明，當程序執行時，它從一個局部移向另一個局部。局部是一個經常使用頁的集合，一個程式通常由多個不同局部組成，它們可能重疊。
例如，當一個子程式被調用時，它就定義了一個新局部。在這個局部裡，記憶體引用包括該子程式的指令、其全局變量和全局變量的子集。當該子程式退出時，因為子程式的局部變量和指令現已不再使用，程序離開該局部。也可能在後面再次傳回該局部。
可以看到局部是由程式結構和資料結構來定義的。局部模型說明了所有程式都具有這種基本的記憶體引用結構。局部模型是緩存的基礎。如果對任何資料結構的通路是随機的而沒有一定的模型，那麼緩存就沒有用了。
工作集合模型
工作集合模型（working-set model）是基于局部性假設的。該模型使用參數定義工作集合視窗（working-set window）。其思想是檢查最近個頁的引用。這最近個引用過的頁集合稱為工作集合（working set）。如果一個頁正在使用中，那麼它就在工作集合内。如果它不再使用，那麼它會在其上次引用的時間機關後從工作集合中删除。是以，工作集合是程式局部的近似。
最為重要的工作集合的屬性是其大小。如果經計算而得到系統内每個程序的工作集合為，那麼就得到
其中D為總的幀需求量。每個程序都經常要使用位于其工作集合内的頁。是以，程序i需要幀。如果總的需求大于可用幀的數量（D>m），那麼有的程序就會得不到足夠得幀，進而出現颠簸。
一旦确定了，那麼工作集合模型得使用就較為簡單。作業系統跟蹤每個程序的工作集合，并為程序配置設定大于其工作集合的幀數。如果還有空閑幀，那麼可啟動另一個程序。如果所有工作集合之和的增加超過了可用幀的總數，那麼作業系統會選擇暫停一個程序。該程序的頁被寫出，且其幀可配置設定給其他程序。挂起的程序可以在以後重新開機。
這種工作集合政策防止了颠簸，并盡可能提高了多道程式的程式。是以，它優化了CPU使用率。工作集合模型的困難是跟蹤工作集合。工作集合視窗是移動視窗。在每次引用時，會增加新引用，而最老的引用會失去。如果一個頁在工作集合視窗内被引用過，那麼它就處于工作集合内。
頁錯誤頻率
工作集合模型是成功的，工作集合知識能用于預先調頁，但是用于控制颠簸有點不太靈活。一種更為直接的方法是采用頁錯誤頻率（page-fault frequency,PFF）政策。
這裡的問題是如何防止颠簸，颠簸具有高的也錯誤率。是以，需要控制頁錯誤率。當也錯誤率太高時，程序需要更多幀。類似地，如果頁錯誤率太低，那麼程序可能有太多的幀。可以為所期望的頁錯誤率設定上限和下限。如果實際頁錯誤率超過上限，那麼為程序配置設定更多的幀；如果實際頁錯誤率低于下限，那麼可從該程序中移走幀。是以，可以直接測量和控制頁錯誤率以防止颠簸。
與工作集合政策一樣，也可能必須暫停一個程序。如果頁錯誤增加且沒有可用幀，那麼必須選擇一個程序暫停。接着，可将釋放的幀配置設定給那些具有高頁錯誤率的程序。
記憶體映射檔案
考慮一下采用标準系統調用open(),read()和write()，并在磁盤上對檔案進行一系列的讀操作。檔案每次通路時都需要一個系統調用和磁盤通路。另外一種方法時，可使用所讨論的虛拟記憶體技術來将檔案I/O作為普通記憶體通路。這種方法稱為檔案的記憶體映射（memory mapping）,它允許一部分虛拟記憶體與檔案邏輯相關聯。
基本機制
檔案的記憶體映射可将一磁盤塊映射成記憶體的一頁（或多頁）。開始的檔案通路按普通請求頁面排程來進行，會産生頁錯誤。這樣，一頁大小的部分檔案從檔案系統讀入實體頁（有的系統會一次讀入多個一頁大小的内容）。以後檔案的讀寫就按通常的記憶體通路來處理，由于是通過記憶體操作檔案而不是使用系統調用read()和write()，進而簡化了檔案通路和使用。
多個程序可以允許将同一檔案映射到各自的虛拟記憶體中，以允許資料共享。其中任一程序修改虛拟記憶體中的資料，都會為其他映射相同檔案部分的程序所見。每個共享程序的虛拟記憶體表都指向實體記憶體的同一頁，該頁有磁盤塊的複制。記憶體映射系統調用還支援寫時複制功能，允許程序共享隻讀模式的檔案，但也有它們所修改資料的各自副本。
核心記憶體的配置設定
當使用者态程序需要額外記憶體時，可以從核心所維護的空閑頁幀連結清單中擷取頁。該連結清單通常由頁替換算法來更新，且如前所述，這些頁幀通常分散在實體記憶體中。另外，請記住，如果使用者程序隻需要一個位元組的記憶體，那麼會産生内部碎片，這是因為程序會得到整個頁幀。
但是，核心記憶體的配置設定通常是從空閑記憶體池中擷取的，而并不是從滿足普通使用者模式程序的記憶體連結清單中擷取的。這主要有兩個原因：
- 核心需要為不同大小的資料結構配置設定記憶體，其中有的不到一頁。是以，核心必須謹慎使用記憶體，并試圖減低碎片浪費。這一點非常重要，因為許多作業系統的核心代碼與資料不受分頁系統控制。
- 使用者程序所配置設定的頁不必要在連續的實體記憶體中。然而，有的硬體要直接與實體記憶體打交道，而不需要經過虛拟記憶體接口，是以需要記憶體常駐在連續的實體頁中。
slab配置設定
核心配置設定的另一種方案是slab配置設定。Slab是由一個或多個實體上連續的頁組成的。高速緩存（cache）含有一個或多個slab。每個核心資料結構都有一個cache，如程序描述符、檔案對象、信号量等。每個cache含有核心資料結構的對象執行個體。例如，信号量cache存儲着信号量對象，程序描述符cache存儲着程序描述對象。下圖描述了slab，cache以及對象三者之間的關系。Slab配置設定算法采用cache存儲記憶體對象。當建立cache時，起初包括若幹标記為空閑的對象。對象的數量與slab的大小有關。
Slab配置設定器有兩個主要優點：
- 沒有因碎片而引起的記憶體浪費。碎片不是問題，這時因為每個核心資料結構都有相應的cache，而每個cache都由若幹slab組成，而每個slab又分為若幹個與對象大小相同的部分。是以，當核心請求對象記憶體時，slab配置設定器可以傳回剛好可以表示對象所需的記憶體。
- 記憶體請求可以快速滿足。Slab配置設定器對于需要經常不斷配置設定記憶體、釋放記憶體來說特别有效，而作業系統經常這樣做。記憶體配置設定與釋放可能費時。然而，由于對象預先建立，是以可從cache上快速配置設定。另外，當用完對象并釋放時，隻需要标記為空閑并傳回給cache，以便下次再用。
小結
需要能執行這樣一個程序，其邏輯位址大于可用實體位址空間。虛拟記憶體允許将大邏輯位址空間映射到小的實體記憶體。虛拟記憶體允許極大的程序運作，且提高了多道程式的程式，增加CPU使用率。再者，它使得程式員不必考慮記憶體可用性。另外，虛拟記憶體允許程序共享系統庫與記憶體。當父子程序共享記憶體頁時，虛拟記憶體也允許采用寫時複制來建立程序。
虛拟記憶體通常采用按需調頁方式來實作。純按需調頁隻有再引用頁時才調入頁。第一次引用就會使作業系統産生頁錯誤。作業系統檢查内部表以确定該頁再備份倉庫上的位置。接着，它找到空閑幀并從備份倉庫中讀入頁。更新頁表以反映這一修改，并重新執行産生頁錯誤的指令。這種方法允許一個程序運作，即使完整記憶體影像不能同時在記憶體中。隻要頁錯誤率足夠低，那麼性能就可以被接受。
使用按需調頁以降低配置設定給程序的幀數。這種安排能增加多道程式的程度（允許更多程序同時執行），且增加系統CPU使用率。即使程序記憶體需要超過總的實體記憶體，也能允許程序運作。這些程序可以在虛拟記憶體中運作。
如果總的記憶體需求超過了實體記憶體，那麼有可能必須置換記憶體中的頁以便為新頁所用。可以使用各種頁置換算法。FIFO頁置換算法容易程式設計，但有Belady異常。最優頁置換算法需要将來的知識。LRU頁置換能近似最優算法，但是它也很難實作。絕大多數頁置換算法，如二次機會算法，都是LRU置換的近似。
除了頁置換算法，還需要幀配置設定政策。配置設定可以是固定的，如局部頁置換算法；或動态的，如全局置換。工作集合模型假定程序在局部内執行。工作集是位于目前局部所有頁的集合。相應地，每個程序應該為其目前工作集合配置設定足夠多地記憶體以避免颠簸，可能需要程序交換和排程。