在上一篇介紹的幾種多道程式設計的記憶體管理模式中，以交換記憶體管理最為靈活和先進。但是這種政策也存在很多重大問題，而其中最重要的兩個問題就是空間浪費和程式大小受限。那麼有什麼辦法可以解決交換記憶體存在的這些問題呢？答案是分頁，它是我們解決交換缺陷的“不二法門”。分頁系統的核心在于：将虛拟記憶體空間和實體記憶體空間皆劃分為大小相同的頁面，如4KB、8KB或16KB等，并以頁面作為記憶體空間的最小配置設定機關，一個程式的一個頁面可以存放在任意一個實體頁面裡。
在上一篇介紹的幾種多道程式設計的記憶體管理模式中，以交換記憶體管理最為靈活和先進。但是這種政策也存在很多重大問題，而其中最重要的兩個問題就是空間浪費和程式大小受限。那麼有什麼辦法可以解決交換記憶體存在的這些問題呢？答案是分頁，它是我們解決交換缺陷的“不二法門”。
一、分頁記憶體管理
1.1 解決問題之道
為了解決交換系統存在的缺陷，分頁系統橫空出世。分頁系統的核心在于：将虛拟記憶體空間和實體記憶體空間皆劃分為大小相同的頁面，如4KB、8KB或16KB等，并以頁面作為記憶體空間的最小配置設定機關，一個程式的一個頁面可以存放在任意一個實體頁面裡。
（1）解決空間浪費碎片化問題
由于将虛拟記憶體空間和實體記憶體空間按照某種規定的大小進行配置設定，這裡我們稱之為頁（Page），然後按照頁進行記憶體配置設定，也就克服了外部碎片的問題。
（2）解決程式大小受限問題
程式增長有限是因為一個程式需要全部加載到記憶體才能運作，是以解決的辦法就是使得一個程式無須全部加載就可以運作。使用分頁也可以解決這個問題，隻需将目前需要的頁面放在記憶體裡，其他暫時不用的頁面放在磁盤上，這樣一個程式同時占用記憶體和磁盤，其增長空間就大大增加了。而且，分頁之後，如果一個程式需要更多的空間，給其配置設定一個新頁即可（而無需将程式倒出倒進進而提高空間增長效率）。
1.2 虛拟位址的構成與位址翻譯
（1）虛拟位址的構成
在分頁系統下，一個程式發出的虛拟位址由兩部分組成：頁面号和頁内偏移值，如下圖所示：
例如，對于32位尋址的系統，如果頁面大小為4KB，則頁面号占20位，頁内偏移值占12位。
（2）位址翻譯：虛拟位址→實體位址
分頁系統的核心是頁面的翻譯，即從虛拟頁面到實體頁面的映射（Mapping）。該翻譯過程如下僞代碼所示：
if(虛拟頁面非法、不在記憶體中或被保護)
{
陷入到作業系統錯誤服務程式
}
else
{
将虛拟頁面号轉換為實體頁面号
根據實體頁面号産生最終實體位址
} 而這個翻譯過程由記憶體管理單元（MMU）完成，MMU接收CPU發出的虛拟位址，将其翻譯為實體位址後發送給記憶體。記憶體管理單元按照該實體位址進行相應通路後讀出或寫入相關資料，如下圖所示：
那麼，這個翻譯是怎麼實作的呢？答案是查頁表，對于每個程式，記憶體管理單元MMU都為其儲存一個頁表，該頁表中存放的是虛拟頁面到實體頁面的映射。每當為一個虛拟頁面尋找到一個實體頁面之後，就在頁表裡增加一條記錄來保留該映射關系。當然，随着虛拟頁面進出實體記憶體，頁表的内容也會不斷更新變化。
1.3 頁表
頁表的根本功能是提供從虛拟頁面到實體頁面的映射。是以，頁表的記錄條數與虛拟頁面數相同。此外，記憶體管理單元依賴于頁表來進行一切與頁面有關的管理活動，這些活動包括判斷某一頁面号是否在記憶體裡，頁面是否受到保護，頁面是否非法空間等等。
頁表的一個記錄所包括的内容如下圖所示：
由于頁表的特殊地位，決定了它是由硬體直接提供支援，即頁表是一個硬體資料結構。
1.4 分頁系統的優缺點
優點：
（1）分頁系統不會産生外部碎片，一個程序占用的記憶體空間可以不是連續的，并且一個程序的虛拟頁面在不需要的時候可以放在磁盤中。
（2）分頁系統可以共享小的位址，即頁面共享。隻需要在對應給定頁面的頁表項裡做一個相關的記錄即可。
缺點：頁表很大，占用了大量的記憶體空間。
1.5 缺頁中斷處理
在分頁系統中，一個虛拟頁面既有可能在實體記憶體，也有可能儲存在磁盤上。如果CPU發出的虛拟位址對應的頁面不在實體記憶體，就将産生一個缺頁中斷，而缺頁中斷服務程式負責将需要的虛拟頁面找到并加載到記憶體。缺頁中斷的處理步驟如下，省略了中間很多的步驟，隻保留最核心的幾個步驟：
二、頁面置換算法
如果發生了缺頁中斷，就需要從磁盤上将需要的頁面調入記憶體。如果記憶體沒有多餘的空間，就需要在現有的頁面中選擇一個頁面進行替換。使用不同的頁面置換算法，頁面更換的順序也會各不相同。如果挑選的頁面是之後很快又要被通路的頁面，那麼系統将很開再次産生缺頁中斷，因為磁盤通路速度遠遠記憶體通路速度，缺頁中斷的代價是非常大的。是以，挑選哪個頁面進行置換不是随随便便的事情，而是有要求的。
2.1 頁面置換的目标
頁面置換時挑選頁面的目标主要在于降低随後發生缺頁中斷的次數或機率。
是以，挑選的頁面應當是随後相當長時間内不會被通路的頁面，最好是再也不會被通路的頁面。BTW，如果可能，最好選擇一個沒有修改過的頁面，這樣替換時就無須将被替換頁面的内容寫回磁盤，進而進一步加快缺頁中斷的響應速度。
是以，為了達到這個目的，先驅們設計出了各種各樣的頁面置換算法，下面就來看看這些算法。
2.2 随機更換算法
在需要替換頁面的時候，産生一個随機頁面号，進而替換與該頁面号對應的實體頁面。遺憾的是，随機選出的被替換的頁面不太可能是随後相當長時間内不會被通路的頁面。也就是說，這種算法難以保證最小化随後的缺頁中斷次數。事實上，這種算法的效果相當差。
2.3 先進先出算法
顧名思義，先進先出（FIFO，First In First Out）算法的核心是更換最早進入記憶體的頁面，其實作機制是使用連結清單将所有在記憶體中的頁面按照進入時間的早晚連結起來，然後每次置換連結清單頭上的頁面就行了，而新加進來的頁面則挂在連結清單的末端，如下圖所示：
FIFO的優點是簡單且容易實作，缺點是如果最先加載進來的頁面是經常被通路的頁面，那麼就可能造成被通路的頁面替換到磁盤上，導緻很快就需要再次發生缺頁中斷，進而降低效率。
2.4 第二次機會算法
由于FIFO隻考慮進入記憶體的時間，不關心一個頁面被通路的頻率，進而有可能造成替換掉一個被經常通路的頁面而造成效率低下。那麼，可以對FIFO進行改進：在使用FIFO更換一個頁面時，需要看一下該頁面是否在最近被通路過，如果沒有被通路過，則替換該頁面。反之，如果最近被通路過（通過檢查其通路位的取值），則不替換該頁面，而是将該頁面挂到連結清單末端，并将該頁面進入記憶體的時間設定為目前時間，并将其通路位清零。這樣，對于最近被通路過的頁面來說，相當于給了它第二次機會。
例如，當A頁面最近被通路過，即其通路位R的值為1，則使用第二次機會算法之後，連結清單的格局如下圖所示：
第二次機會算法簡單、公平且容易實作。但是，每次給予一個頁面第二次機會時，将其移動到連結清單末端需要耗費時間。此外，頁面的通路位隻在頁面替換進行掃描時才可能清零，是以其時間局域性展現得不好，通路位為1的頁面可能是很久以前通路的，時間上的分辨粒度太粗，進而影響頁面替換的效果。
2.5 時鐘算法
為了改善第二次機會算法的缺點，先驅們提出了時鐘算法。時鐘算法的核心思想是：将頁面排成一個時鐘的形狀，該時鐘有一個針臂，每次需要更換頁面時，我們從針臂所指的頁面開始檢查。如果目前頁面的通路位為0，即從上次檢查到這次，該頁面沒有被通路過，将該頁面替換。反之，就将其通路位清零，并順時針移動指針到下一個頁面。重複這些步驟，直到找到一個通路位為0的頁面。
例如下圖所示的一個時鐘，指針指向的頁面是F，是以第一個被考慮替換的頁面是F。如果頁面F的通路位為0，F将被替換。如果F的通路位為1，則F的通路位清零，指針移動到頁面G。
從表面上看，它和第二次機會算法類似，都是通路位為0就更換，反之則再給一次機會。但是，它和第二次機會算法還是有幾點不同：
（1）他們的資料結構不一樣，第二次機會使用的是連結清單，時鐘算法使用的是索引（整數指針）。這樣，其使用的記憶體空間不一樣。
（2）第二次機會需要使用額外的記憶體，而時鐘算法可以直接使用頁表。使用頁表的好處是無需額外的空間，更大的好處是頁面的通路位會定期自動清零，這樣将使得時鐘算法的時間分辨粒度較第二次機會算法高，進而取得更好的頁面替換效果。
時鐘算法的精髓是第二次機會，其缺點也就和第二次機會算法一樣：過于公平，沒有考慮到不同頁面調用頻率的不同，有可能換出不應該或不能換出的頁面，還可能造成無限循環。
PS：至此，随機、FIFO、第二次機會與時鐘算法的介紹就到此結束，這四種算法都是屬于“公平算法”，即所有的頁面都或多或少地給予公平待遇，沒有頁面獲得特殊待遇。但是這種公平實作方式，會使效率受到一定影響，這時因為個體對于整個系統的貢獻沒有被差別對待，造成貢獻大的和貢獻小的待遇一樣，自然會影響整個系統的效率。
2.6 最優更換算法
我們知道，最理想的頁面替換算法是選擇一個再也不會被通路的頁面進行替換。如果不存在這樣的頁面，那至少選擇一個在随後最長時間内不會被通路的頁面進行替換。這樣，我們就可以保證在随後發生缺頁中斷的次數最小或機率最低，這種算法就是最有替換算法。
但是，我們沒法知道一個頁面随後多長時間不會被通路，是以最優更換算法在實際中沒法實作，那麼為什麼要介紹最有更換算法呢？這是為了定義一個标杆，以此來評判其他算法的優劣。
2.7 NRU（最近未被使用）算法
顧名思義，NRU就是選擇一個在最近一段時間内沒有被通路過的頁面進行替換，這是基于程式通路的時空局域性。因為根據時空局域性原理，一個最近沒有被通路的頁面，在随後的時間裡也不太可能被通路，而NRU的實作方式就是利用頁面的通路和修改位。
每個頁面都有一個通路位和一個修改位，凡是對頁面進行讀寫操作時，通路位被設定為1。當程序對頁面進行讀寫操作時，修改位設定為1。根據這兩個位的狀态來對頁面進行分類的話，可以分成以下四種頁面類型：1、2、3、4。
有了這個分類，NRU算法就按照這四類頁面的順序依次尋找可以替換的頁面。如果所有頁面皆被通路和修改過，那也隻能從中替換掉一個頁面，是以NRU算法總是會終結的。
當然，這種分類比較籠統，在同一類頁面裡，我們沒有辦法分辨出哪一類被通路的時間更近一些。即在某些情況下，我們替換的可能并不是最近沒有被使用的頁面。
2.8 LRU（最近最少使用）算法
與NRU算法相比，LRU算法不僅考慮最近是否用過，還要考慮最近使用的頻率。這裡是基于過去的資料預測未來：如果一個頁面被通路的頻率低，那麼以後很可能也用不到。
LRU算法的實作必須以某種方式記錄每個頁面被通路的次數，這是個相當大的工作量。最簡單的方式就是在頁表的記錄項裡增加一個計數域，一個頁面被通路一次，這個計數器的值就增加1。于是，當需要更換頁面時，隻需要找到計數域值最小的頁面替換即可，該頁面即是最近最少使用的頁面。另一種簡單實作方式就是用一個連結清單将所有頁面連結起來，最近被使用的頁面在連結清單頭，最近未被使用的放在連結清單尾。在每次頁面通路時對這個連結清單進行更新，使其保持最近被使用的頁面在連結清單頭。
LRU算法雖然很好，但是實作成本高（需要分辨出不同頁面中哪個頁面時最近最少使用的），并且時間代價大（每次頁面通路發生時都需要更新記錄）。是以，一般的商業作業系統都沒有采納LRU頁面更新算法。
2.9 工作集算法
由于不可能精确地确定那個頁面是最近最少使用的，那就幹脆不花費這個力氣，隻維持少量的資訊使得我們選出的替換頁面不太可能是馬上又會使用的頁面即可。這種少量的資訊就是工作集資訊。
工作集概念來源于程式通路的時空局限性，即在一段時間内，程式通路的頁面将局限在一組頁面集合上。例如，最近k次通路均發生在某m個頁面上，那麼m就是參數為k時的工作集。我們用w(k,t)來表示在時間t時k次通路所涉及的頁面數量。
顯然，随着k的增長，w(k,t)的值也随之增長；但是當k增長到某個數值之後，w(k,t)的值将增長極其緩慢甚至接近停滞，并維持一段時間的穩定，如下圖所示：
由上圖可以看出，如果一個程式在記憶體裡面的頁面數與其工作集大小相等或者超過工作集，則該程式可在一段時間内不會發生缺頁中斷。如果其在記憶體的頁面數小于工作集，則發生缺頁中斷的頻率将增加，甚至發生記憶體抖動。
是以，工作計算法的目标就是維持目前的工作集的頁面在實體記憶體裡面。每次頁面更換時，尋找一個不屬于目前工作集的頁面替換即可。這樣，我們再尋找頁面時隻需要将頁面分離為兩大類即可：目前工作集内頁面和目前工作集外頁面。如此，隻要找到一個飛目前工作集的頁面，将其替換即可。
工作集算法的優點：實作簡單，隻需要在頁表的每個記錄增加一個虛拟時間域即可。而且，這個時間域不是每次發生通路時都需要更新，而是在需要更換頁面時，頁面更換算法對其進行修改，是以時間成本也不大。
工作集算法的缺點：每次掃描頁面進行替換時，有可能需要掃描整個頁表。然而，并不是所有頁面都記憶體裡，是以掃描過程中的一大部分時間将是無用功。另外，由于其資料結構是線性的，會造成每次都按同樣的順序進行掃描，顯得不太公平。
2.10 工作集時鐘算法
鑒于工作集算法的缺點，先驅們将工作集算法與時鐘算法結合起來，設計出了工作集時鐘算法，即使用工作集算法的原理，但是将頁面的掃描順序按照時鐘的形式組織起來。這樣每次需要替換頁面時，從指針指向的頁面開始掃描，進而達到更加公平的狀态。而且，按時鐘組織的頁面隻是在記憶體裡面的頁面，在記憶體外的頁面不放在時鐘圈裡，進而提高實作效率。
鑒于其時間與空間上的優勢，工作集時鐘算法被大多商業作業系統所采納。
參考資料
鄒恒明，《作業系統之哲學原理》，機械工業出版社
作者：周旭龍
出處：http://edisonchou.cnblogs.com
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連結。