目錄

• 1 虛擬內存的背景
• • 1.1 局部性原理
  • 1.2 虛擬內存
• 2 請求調頁
• • 2.1 頁面調入策略
• 3 頁面置換
• 4 頁面置換算法
• • 4.1 最佳算法（OPT, optimal）
  • 4.2 先進先出置換算法（FIFO）
  • 4.3 最近最久未使用置換算法（LRU）
• 5 幀（頁）分配

1 虛擬內存的背景

無論是分頁還是分段，程序運行的基本要求就是必須全部放入內存后方可運行，如果進程大于內存的容量或者內存中同時運行多個進程，那么進程就無法執行了，解決這個問題有兩種方法，即覆蓋和動態加載，但是這兩種工作都是由程序員手動來做而且實現很復雜。

上面的問題究其本質就是內存不夠用了，那么很容易想到的就是擴充內存，可以從物理上擴充內存容量，但是是受限的，如32位操作系統支持的內存最大為4GB，64位操作系統支持的內存最大為128GB，并且購買內存也較為昂貴。那么是否可以從邏輯上擴充內存容量呢？答案是可以的，本文內容就是講解如何從邏輯上擴充內存。

---

常規的存儲方式具有如下特征：

• 一次性：作業在運行前需要一次性的全部裝入內存；
• 駐留性：作業裝入內存后，便一直駐留在內存中，直到作業結束。

正是由于一次性和駐留性，使得程序中暫時不用的數據占用了大量的內存空間，從而需要運行的作業無法裝入內存。那么一次性和駐留性是必需的嗎？人們對程序做了很多的研究發現程序在執行過程中其實不是要運行所有部分：

• 程序通常有處理異常錯誤的代碼，很少執行
• 數組、鏈表和表通常分配了比實際需要更多的內存
• 程序的某些選項或特點可能很少使用
• 即使需要完整的程序，也并不是同時需要所有的程序

通過上述四個特點，我們可以發現程序運行時往往只運行了一部分，這個特點我們叫做局部性原理。

1.1 局部性原理

局部性原理的定義是在一段時間內，程序的執行僅局限于某個部分；相應地，它所訪問的存儲空間也局限于某個區域內。出現局部性原理有如下原因：

• 程序在執行時，除了少部分的轉移和過程調用指令外，大多數仍是順序執行的；
• 子程序調用將會使程序的執行由一部分內存區域轉至另一部分區域，也就是說程序只是從一個局部跳躍到另一個局部而已；
• 程序中存在許多循環結構，循環體中的指令被多次執行；
• 程序中還包括許多對數據結構的處理，如對連續的存儲空間——數組的訪問，往往局限于很小的范圍內。

因此我們說程序是具有局部性的，局部性主要體現在兩個方面：

• 時間局部性： 如果程序中的某條指令一旦執行，則不久的將來該指令可能再次被執行；如果某個存儲單元被訪問，則不久以后該存儲單元可能再次被訪問；產生時間局限性的典型原因是在程序中存在著大量的循環操作；
• 空間局部性： 一旦程序訪問了某個存儲單元，則在不久的將來，其附近的存儲單元也最有可能被訪問。 即程序在一段時間內所訪問的地址，可能集中在一定的范圍內，其典型原因是程序是順序執行的。

1.2 虛擬內存

虛擬內存是一種允許進程部分裝入內存就可以執行的技術，它基于的原理就是局部性原理，因為程序具有局部性，所以只需要把當前需要執行的程序內容裝入內存即可，這個時候用戶看到的邏輯地址空間就比物理地址空間大，要實現這個功能就必須允許頁面能夠被換入和換出。

如下圖，虛擬內存virtual memory顯然是比實際內存physical memory大的，只需要把當前要執行的部分裝入內存即可；用memory map來映射當前哪些部分是要裝入內存的，類似頁表，當運行到某個位置的時候就可以查詢它在內存還是在外存；當要運行新的程序時或當前內存不足時就要和外存進行頁面的換入和換出：

虛擬內存具有如下特征：

• 離散性：在內存分配時采用離散的分配方式，是虛擬存儲器的最基本的特征；
• 多次性：一個作業被分成多次調入內存運行，即在作業運行時沒有必要將其全部裝入，只須將當前要運行的那部分程序和數據裝入內存即可。是虛擬存儲器最重要的特征；
• 對換性：作業運行過程中信息在內存和外存的對換區之間換進、換出；
• 虛擬性：從邏輯上擴充內存容量，使用戶所看到的內存容量遠大于實際內存容量。

2 請求調頁

實現虛擬存儲器要解決如下三個問題 ：

• 程序部分運行可以嗎? 是可以的，依照程序局部性原理，取出要用的頁，然后裝入內存即可；
• 發現程序不在內存時，如何將其裝入后繼續運行? 用請求調頁技術，當發生缺頁時，產生缺頁中斷，將外存上的頁調入內存；
• 內存無空間時怎么辦? 用頁面置換，將部分頁面換出內存。

2.1 頁面調入策略

為能使進程運行，事先需將一部分要執行的程序和數據調入內存，有兩種調頁的策略：

• 預調頁策略：主動的頁面調入策略，即把那些預計很快會被訪問的程序或數據所在的頁面，預先調入內存；這個策略的性能取決于預測的準確率，預測的準確率不高（50%），主要用于進程的首次調入。也有的系統將預調頁策略用于請求調頁。
• 請求調頁策略：當進程在運行中發生缺頁時，由系統將缺頁調入內存；目前虛擬存儲器系統大多采用此策略；但在調頁時須花費較大的系統開銷，如需頻繁啟動磁盤I/O。

請求調頁只有在一個頁需要的時候才把它換入內存，這是請求調頁的好處，或者說是虛擬內存的好處。它需要需要很少的I/O，需要很少的內存，能夠快速響應，并且可以支持多用戶。當需要某個頁的時候判斷它是否在內存中是需要進行查閱的，通常存在一個bit位表示它是不是在內存，若不在內存中就要調入內存。

---

在具體實現的時候需要對進程頁表的修改，也需要缺頁中斷的支持。請求分頁的頁表機制是在純分頁的頁表機制上形成的，由于只將應用程序的一部分調入內存，還有一部分仍在磁盤上，故需在頁表中再增加若干項，供程序(數據)在換進、換出時參考。在請求分頁系統中的每個頁表項如下圖所示：

其中增加的各字段說明如下：

• 狀態位(存在位P) ：用于指示該頁是否已調入內存，供程序訪問時參考；
• 訪問字段A：用于記錄本頁在一段時間內被訪問的次數，或最近已有多長時間未被訪問，提供給置換算法選擇換出頁面時參考；
• 修改位M：表示該頁在調入內存后是否被修改過。由于內存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不需將該頁寫回到外存上，以減少系統的開銷和啟動磁盤的次數；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本；
• 外存地址：用于指出該頁在外存上的地址，通常是物理塊號，供調入該頁時使用。

---

完成頁面調頁還需要缺頁中斷機構的支持，在請求分頁系統中，每當所要訪問的頁面不在內存時，便要產生一缺頁中斷，請求操作系統將所缺頁調入內存。與一般中斷的主要區別在于：

• 缺頁中斷在指令執行期間產生和處理中斷信號，而一般中斷在一條指令執行完后檢查和處理中斷信號；
• 缺頁中斷返回到該指令的開始重新執行該指令，而一般中斷返回到該指令的下一條指令執行；
• 一條指令在執行期間，可能產生多次缺頁中斷；

下圖是缺頁中斷的處理過程，現在要加載一個程序 M，?首先要查詢頁表，發現該頁在頁表中是 i (invalid)，表示不在內存，?這個時候就產生一個缺頁中斷，?操作系統就會根據在頁表中指向的外存的地址找到它，?隨后從外存放入內存，放入的時候要找一個空閑頁，一旦放進去了以后，?頁表就要更新，此時中斷就結束了，?接著就要返回到這個程序重新執行：

上面整個過程主要是執行以下三個操作：

• 處理缺頁中斷；
• 從磁盤讀入所需的頁；
• 重新開始被中斷的進程。

其中最大的一部分時間開銷為第二步，即從磁盤讀入所需的頁，因此我們希望減少讀入的次數，也就是降低缺頁率。

缺頁率 = 訪問內存次數 / 不成功訪問次數

3 頁面置換

隨著裝入內存的程序越來越多，內存可能會有裝滿的情況下，這個時候如果來了新的程序想要進入內存，就必須執行頁面置換，將內存中暫不使用的程序先從內存調出到外存。

如下圖的兩個用戶程序，其中用戶程序1需要載入程序M，用戶程序2需要載入程序B，而此時M載入到內存后，內存已經滿了，程序B再要裝入內存已經沒有位置了，所以此時要將現在內存中的某個程序置換出去。

現在置換有如下幾種方法：

• 終止用戶進程：一旦終止用戶進程，進程就會釋放內存空間，那么內存就騰出位置來了，這種方法的代價是比較大的；
• 交換進程：中級調度，釋放其所有幀，降低多道程序的度，這種方法的代價也是比較大的，因為是以整個進程為單位，進行的 I/O 操作開銷較大；
• 頁面置換：以頁為單位做交換，這種方法的開銷相比是最小的。

頁面置換的執行步驟如下：

• 找到頁面在磁盤中的位置，找到之后便要把它讀入內存，就要找到一個空閑的幀；
• 若有空閑的幀遍可以直接裝入，若沒有空閑的幀就要選擇一個頁調換出去，同時修改頁表，再把頁面裝入內存；

頁面置換過程如下圖所示，?犧牲當前內存中的某個頁， 置換到外存上，?修改頁表標志位，?將頁面置換進內存中，?更新頁表：

可以發現在頁面置換過程中，需要兩個頁面傳輸，一個換出，一個換入。但是有時候只需要一次置換就可以，因為有些程序在內存中并沒有被修改過，所以它不需要換到外存去更新數據，只用犧牲它，將新調入的程序覆蓋它即可，這里用到的方法就是前面提到的修改位。

頁面置換的總的流程圖如下圖所示，圖中的快表指的是聯想寄存器：

4 頁面置換算法

在進程運行過程中，如果發生缺頁, , 而內存中又無空閑塊時可以將內存中的某一頁換到磁盤的對換區。那么到底選擇調出哪一個頁，可以根據頁面置換算法來確定，置換算法的好壞將直接影響系統的性能，不適當的算法可能會導致進程發生 “抖動” (Thrashing) 。

抖動 (Thrashing)：如果進程分配到的幀數量小于計算機體系結構所要求的最小數量，那么必須暫停進行執行。并將其置換出去，使其所有分配幀空閑。這么做的原因就是如果進程沒有這些必需的幀，那么很快會出現缺頁，此時需置換某個頁，然而，其所有頁都在使用，置換出去的頁立刻又需要置換進來，因此，會不斷的產生缺頁。這種頻繁的調頁行為稱作抖動 (Thrashing)，也叫顛簸。

頁面置換最大的問題就是到底換哪一個頁，若換出的某個頁很快就又要用到又要換進來，這樣的效率是很低的，所以我們希望我們換出的頁是今后很長一段時間內不再用到的頁，這樣就能降低系統的缺頁率，我們來衡量一個頁面置換算法的好壞主要是通過缺頁率的大小，從理論上講 ， 應將那些以后不再被訪問的頁面換出，或把那些在較長時間內不會再被訪問的頁面換出，在實際的過程中有很多的置換算法能夠接近理論目標，為什么說是理論上的，因為我們人是不知道哪些頁面是要換的。

我們通過運行一個內存訪問的特殊序列（訪問序列），計算這個序列的缺頁次數來評估算法。這個序列我們假定為 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1，后面討論算法時都會用到這個序列。

4.1 最佳算法（OPT, optimal）

最佳算法中被置換的頁將是之后最長時間不被使用的頁，其置換過程如下：

上述過程的缺頁次數是 $9$，置換次數是 $6$。這個算法的缺點就是在實際過程中，我們并不知道這個內存訪問序列，尤其是在多道批處理系統中，更是無法預測，所以最佳算法只是理論上最優的算法，現實中是無法實現的，我們通常用它來衡量其他算法的性能。

4.2 先進先出置換算法（FIFO）

先進先出置換算法中是按照內存先來先得，先進來的先出去這種方式來選擇置換的頁，其置換過程如下：

上述過程的缺頁次數是 $15$，置換次數是 $12$。這個算法的性能幾乎是比最佳算法差了一倍了，導致性能不好的原因是剛剛換出去的頁，很可能又要被換進來，于是增加了缺頁率，因此有了下面第三種置換算法。

4.3 最近最久未使用置換算法（LRU）

雖然并不知道頁面未來的使用情況，但是可以使用離過去最近的情況作為不遠將來的近似，可以選擇最近最少使用的頁進行置換，其置換過程如下：

上述過程的缺頁次數是 $12$，置換次數是 $9$。這個算法的性能顯然比先進先出置換算法要好，但是實現LRU算法需要硬件支持，記錄物理頁的使用情況。

但是實際上可能沒有足夠的硬件支持，所以就有了LRU的近似算法，如基于訪問位的算法，二次機會算法。

• 訪問位算法：每個頁都與一個位相關聯，初始值為0，每當這個頁被訪問的時候就把這個頁置位1，所以在選擇置換的頁時就可以看這個訪問位，看誰是未被訪問過的。但是這個算法有不足的地方就在于我們并不知道這個置換順序，因為有可能有的頁時很久都沒有使用過的，有的頁只是最近未被使用過的，理論上來說很久未被使用的頁大概率以后不會再使用了，而最近未使用的頁很可能再被使用歐冠。
• 二次機會算法 (clock算法)：同樣它也需要訪問位的支持，它會把所有的頁組成一個環，同樣未被訪問時，訪問位置0，訪問位就置1，在要置換時，我們以順時針的方向遍歷這個環來尋找訪問位為0的頁換出去，若找到訪問位為1的頁，就把它置位0，代表著給它一次機會，這也是二次機會算法名字的由來。如果所有頁的訪問位都為1，則此算法退化為FIFO算法。二次機會算法執行過程如下圖所示：
  

5 幀（頁）分配

前面提到每個進程要運行則必須給它分配一定的內存空間，它才能把需要的內容放到內存去執行，那么如何給進程分配內存空間呢？首先我們要保證給它分配的空間是能夠讓它正常的運行的，即保證進程正常運行所需的最小物理塊數，若系統為某進程所分配的物理塊數少于此值時，進程將無法正常運行(頻繁發生缺頁)，這個數目取決于指令的格式、功能和尋址方式。

具體分配多個頁，有如下的分配方式：

• 平均分配：比如有100個頁，和5個進程，則每個進程分給20個頁；
• 按比例分配：根據每個進程的大小比例來分配；
• 優先分配：根據優先級而不是大小來使用比率分配策略。

如果進程 $P_i$ 產生了一個缺頁，我們知道這個時候需要使用頁面替換算法來替換一個頁面，所替換頁面的位置分為如下兩種：

• 全局替換：進程在所有的頁中選擇一個替換頁面；一個進程可以從另一個進程中獲得頁面；
• 局部替換：每個進程只從屬于它自己的頁中選擇。

所以當進行全局置換的時候，進程所分配的頁數是可以變化的，因為它占用了其他進程的頁，因此使用全局置換可能造成其他進程的運行錯誤；當進行局部置換的時候，進程所分配的頁數是固定不變的，因為它只在自己所屬的范圍內置換。

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的操作系统原理第九章：虚拟内存的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。