1 虛擬存儲技術（Virtual Memory）

1.1 概念

當進程運行時，先將其一部分裝入內存，另一部分暫留在磁盤，當要執行的指令或訪問的數據不在內存時，由操作系統自動完成將它們從磁盤調入內存的工作。
虛擬地址空間即為分配給進程的虛擬內存。
虛擬地址是在虛擬內存中指令或數據的位置，該位置可以被訪問。

1.2 存儲器的層次的結構

1.3 虛存與存儲體系

把內存與磁盤有機的結合起來使用，從而得到一個容量很大的“內存”，即虛存

虛存是對內存的抽象，構建在存儲體系之上，由操作系統協調各存儲器的使用

虛存提供了一個比物理內存大得多的地址空間。虛存的大小受到計算機系統的尋址機制和磁盤可用空間的限制。

1.4 地址保護

包括以下三個要點：

確保每個進程有獨立的地址空間

確保進程訪問合法的地址范圍（防止地址越界）

確保進程的操作是合法的（防止越權，如對只讀內存不能執行寫操作）

1.5 虛擬頁式（Paging）

虛擬頁式存儲管理系統：虛擬存儲技術+頁式存儲管理方案。
虛擬頁式的基本思想在于：

進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據進程運行的需要動態的裝入其他頁面，當內存已滿，而又要重新裝入新的頁面時，則根據某種算法置換內存中的某個頁面，以便裝入新的頁面。

具體有兩種方式：

請求調頁（demand paging）：只要在需要的時候才由OS調入內存

預先調頁（prepaging）：將可能用到的資源提前調入內存
虛擬頁式利用了資源轉換技術：即以CPU時間和磁盤空間來換取昂貴的內存空間。

2 虛擬頁式中的頁表及頁表項的設計

2.1 概念

頁表是由頁表項組成的。頁表項的設計是由硬件保證的，表項的組成如下表所示。
表2-1 頁表項的組成

屬性說明

頁框號	即內存塊號，也稱物理頁面號
有效位	也稱中斷位，表示該頁是在內存還是在磁盤，通常值為0表示相應內容尚未讀入內存
訪問位	引用位，表示該頁是否被訪問過
修改位	此頁在內存中是否被修改過
保護位	頁的讀/寫權限

2.2 關于頁表

2.2.1 頁表規模

1 關于32位虛擬地址空間的頁表規模？
頁面大小為4K，頁表項大小為4字節，則一個進程地址空間有【2³²/(4K)=2³²/2¹²=2²⁰】頁；其頁表需要占【4K/4=1K=1024】頁。
2 關于64位虛擬地址空間的頁表規模？
頁面大小為4K，頁表項大小為8字節；頁表規模達到32000TB。可想而知是多么大。因此需要實現將頁表頁在內存中不連續存放，基本思想是為頁表頁創建地址索引表，即頁目錄（Page Directory）。

2.2.2 多級頁表結構及地址映射

2.2.2.1 二級頁表結構及地址映射

2.2.2.2 多級頁表結構（Core I7為例）

2.2.3 頁目錄項和頁表項（I386為例）

2.3 反轉（倒排）頁表

2.3.1 基本思想

有上述的分析可知地址轉換的步驟是，從虛擬地址空間出發：虛擬地址–》查頁表–》得到頁框號–》形成物理地址。但每個進程一張頁表，資源消耗很大，所以引入倒排頁表，其基本思路是：

從物理地址空間出發，系統建立一張頁表；
頁表項記錄進程i的信息、進程i的某虛擬地址（虛頁號）與頁框號的映射關系。

2.3.2 設計

將虛擬地址的頁號部分映射到一個散列中（為了解決只有一張頁表時查詢過慢的問題）；

散列值指向一個反轉頁表；

反轉頁表大小與實際內存成固定比例，與進程個數無關。

3 地址映射過程及TLB的引入

3.1 地址映射過程

3.2 快表（TLB）的引入

3.2.1 上述地址映射的問題

在二級頁表或者多級頁表中，上述的地址映射過程存在至少兩次的內存訪問，這樣會導致CPU的指令處理速度與內存指令的訪問速度差異大，CPU的速度得不到充分利用。為了加快地址映射速度，改善系統性能，利用程序訪問的局部性原理引入了快表。

3.2.2 快表的概念

TLB——Translation Look-aside Buffers，在CPU中引入的高速緩存，可以匹配CPU的處理速率和內存訪問的速度。TLB是一種存取型存儲器，除連線尋址機制外，還有接線邏輯，能按特定的匹配標志在一個存儲周期內對所有的字同時進行比較。TLB也稱為相聯存儲器（associative memory），特點是按內容并行查找，保存正在運行的進程的頁表的部分頁表項。

3.2.3 引入快表后的地址映射過程

如上圖所示，由虛擬地址映射到物理地址主要還在于求取頁框號，因為物理地址的頁內偏移量和虛擬地址的頁內偏移相同。MMU每次處理的時候都先從TLB中匹配，如果命中了則獲得頁框號，否則到頁表中去查詢頁框號，此時要注意有效位，如果是1表示頁框內容已經讀入內存中了，如果有效位是0則出現Page fault異常，進而轉入操作系統，由操作系統從磁盤將相應頁面調入內存。

4 缺頁異常Page fault

4.1 概念及產生原因

又稱頁面錯誤、頁面失效，是地址映射過程中硬件產生的異常。產生原因：

所訪問的虛擬頁面沒有調入物理內存，即缺頁異常

頁面違反權限（讀/寫、用戶/內核）

錯誤的訪問地址

4.2 缺頁異常處理

是指地址映射過程中，硬件檢查頁表時發現所要訪問的頁面不在內存，則產生該異常。

操作系統執行缺頁異常處理程序：獲取磁盤地址，啟動磁盤將該頁調入內存。

如果內存中有空閑頁框，則分配一個將新調入頁裝入，同時修改相應頁的有效位及相應的頁框號；

若內存中沒有空閑頁框，則要置換內存中某一頁框；若該頁框內容被修改過，則要將其寫回磁盤。

5 軟件相關策略

5.1 駐留集

表示給每個進程分配的頁框的數量。包括固定分配策略和可變分配策略。
表5-1 駐留集分配策略

分配策略特征

固定分配策略	進程創建時確定
可變分配策略	根據缺頁率評估進程局部性表現進而決定增加還是減少頁框數，但是增減頁框數會帶來系統開銷

5.2 置換問題

當內存中沒有空閑頁框，需要將一些頁框換出去，這個就叫置換。置換一個頁框包含兩個核心問題：置換范圍和置換策略。

5.2.1 置換范圍

表5-2 置換范圍

置換范圍特征

局部置換策略	僅在產生本次缺頁的進程的駐留集中選擇
全局置換策略	將內存中所有未鎖定的頁框都作為置換的候選

這里以可變分配策略的局部置換作為例子說明流程：
1）、當一個新進程裝入內存時，分配一定數目的頁框，然后填滿這些頁框；
2）、當發生一定缺頁異常時，從發生異常的進程的駐留集中選擇一頁用于置換；
3）、不斷評估進程頁框分配情況，增加或減少分配給它的頁框以提高整體性能。

5.2.2 置換策略

確定了置換范圍，就要進一步確定究竟該置換哪一個頁框，這就需要置換策略。無論是何置換策略，核心的目標都在于置換最近最不可能訪問的頁，因此大多數置換策略都是基于過去的行為來預測未來的行為。但要注意：置換策略設計得越精致復雜，實現所需要的軟硬件開銷就越大。
置換的約束：不能置換被鎖定的頁框。

5.2.3 頁框鎖定

由于采用的虛存技術有可能調用磁盤，需要額外的開銷，這就使得程序運行時間不確定。為了使得運行時間可預測，所以為每一頁框增加一個鎖定位，實現不讓操作系統將進程使用的頁面換出內存。
例如操作系統的核心代碼、關鍵數據結構、I/O緩沖區，特別是正在I/O的內存頁面都需要設置鎖定位。

5.2.4 清除策略

1 分頁守護進程
從進程的駐留集中收回頁框。實際上，虛擬頁式系統的最佳狀態是當發生缺頁異常時，系統中有大量的空閑頁框。所以要在系統中保存一定數目的頁框供給比使用所有內存且在需要時搜索并置換一個頁框有更好的性能。
清除策略的實現機制是：
1）、設計一個分頁守護進程paging daemon，多數時候睡眠著，可定期喚醒以檢查內存的狀態；
2）、如果空閑頁框過少，分頁守護進程通過預定的頁面置換算法選擇頁面換出內存；
3）、如果頁面裝入內存后被修改過，則將它們寫回磁盤。因此分頁守護進程可保證所有的空閑頁框是“干凈”的。
2 頁緩沖技術
當進程需要使用一個已經被置換出的頁框時，如果該頁框還沒有被新的內容覆蓋，將它從空閑頁框集合中移出即可恢復該頁面。這就是也緩沖機制，具體實現為：
1）、不丟棄置換出的頁，將它們放入兩個表之一：如果未被修改過則放到空閑頁鏈表，否則放到修改頁鏈表中；
2）、被修改的頁定期寫回磁盤（不是每次修改都寫，減少I/O的次數，提升性能）
3）、被置換的頁仍然保留在內存中，一旦進程又要訪問該頁，可以迅速將它加入該進程的駐留集合。

6 頁面置換算法（Replacement）

又稱頁面淘汰算法。

6.1 最佳頁面置換算法OPT

6.1.1 設計思想

置換以后不再需要的或在最遠的將來才會用到的頁面。

6.1.2 意義

但是由于進程運行過程并不知道以后用到的頁面，所以該算法難以實現。該算法的最佳意義在于作為一種標準來衡量其他算法的性能。

6.2 先進先出算法FIFO

6.2.1 設計思想

置換在內存中駐留時間最長的頁。通過頁面鏈表法，每次置換鏈表頭的頁面。

6.2.2 Belady現象

FIFO頁面置換算法會產生Belady異常現象，即：當分配給進程的物理頁面數增加時，缺頁次數反而增加。

6.3 第二次機會算法（SCR）

6.3.1 設計思想

全稱Second Chance 。是對FIFO算法改進，按照先進先出算法從鏈表頭選擇一個頁框，檢查其訪問位R，如果為0（表示近期未被訪問），則置換該頁；如果為1，則給第二次機會，將該頁放置到鏈表末尾并將訪問位置0。

6.3.2 實現機制——時鐘算法（Clock）

SCR的思想基于鏈表，如果訪問R為1，要將該頁框從鏈表頭取出加入表尾，這個摘鏈和掛鏈的過程有消耗，所以采用基于循環鏈表的時鐘算法。通過移動指針選擇要被置換的頁框。

6.4 最近未使用算法（NRU）

6.4.1 設計思想

全稱Not Recently Used，是指置換在最近一段時間內未使用過的一頁。
設置頁表表項的兩位：訪問位R、修改位M。啟動一個進程時，R、M為置0，R位被定期清零（復位）。
表6-1 NRU算法的R、M的可能值

編號RM描述

1	0	0	無訪問，無修改
2	0	1	無訪問，有修改
3	1	0	有訪問，無修改
4	1	1	有訪問，有修改

如上表所示，NRU算法的思想在于：從編號最小的非空類中隨機選擇一頁置換。如果編號為1的類中為空，則從編號為2的類中尋找。

6.4.2 實現機制——時鐘算法

1、從指針的當前位置開始，掃描頁框緩沖區，選擇遇到的第一個頁框（R=0，M=0）用戶置換；
2、如果第1步失敗，則重新掃描，選擇第一個（R=0，M=1）的頁框（如果R=1則跳過），掃描過程中將其跳過的頁框的訪問位R置0；
3、如果第2步也失敗了，指針將回到最初的位置，并且集合中所有的頁框的訪問位R都為0了。此時再重復第1步，如果有必要接著重復第2步，這樣就能找到需要置換的頁框。

6.5 最近最少使用算法（LRU）

6.5.1 設計思想

全稱Least Recently Used，是指置換最后一次訪問時間距離當前時間最長的一頁，即置換未使用時間最長的一項。

6.5.2 實現機制

基本實現是利用時間戳或維護一個訪問頁的棧。該算法優點在于性能最接近OPT，缺點是開銷較大。

6.6 最不經常使用算法（NFU）

6.6.1 設計思想

全稱Not Frequently Used，是指選擇訪問次數最少的頁面置換。

6.6.2 實現機制

NFU算法實際上市LRU算法的一種軟件解決方案。其基本實現機制在于：
1）、維護一個軟件計數器，每頁有一個，初值為0；
2）、每次時鐘中斷時，計數器加R；
3）、發生缺頁中斷時，選擇計數器值最小的一頁置換。

6.7 老化算法（Aging）

6.7.1 設計思想

老化算法實際上是對NFU算法的一種改進，也是一種LRU的模擬算法。基本思想是：計數器在加R前先右移一位，并將R位加到計數器的最左端。

6.7.2 實現機制說明

如下圖所示，每次時鐘中斷的時候，根據訪問位R的值修改技術器的值：如果訪問位是1，則右移一位然后最高位置1；如果訪問位是0，則右移一位。當發生缺頁中斷的時候，則選擇計數器值最小的頁框置換出去。

6.8 工作集算法

6.8.1 缺頁次數的影響因素

頁面置換算法
頁面尺寸的大小
程序的編制方法
分配給進程的頁框數量

顛簸（Thrashing，也稱抖動）：在虛存中，頁面在內存與磁盤之間頻繁調度，使得調度頁面所需的時間比進程實際運行的時間還多，這樣導致系統效率急劇下降，這就是顛簸現象。

6.8.2 頁面尺寸

需要考慮的因素：
1、內部碎片
2、頁表長度
3、輔存的物理特性
大頁面換進換出內存的頻率低一些，但是容易產生內部碎片，小頁面則剛好相反。一般情況最優頁面大小公式為：2*(進程平均規模*頁表項的長度)的二分之一次方。不過一般操作系統會采用常用頁面尺寸，如4K、4M等。

6.8.3 工作集（Working Set）算法

6.8.3.1 基本思想

根據局部性原理，一般情況下，進程在一段時間內總是集中訪問一些頁面，這些頁面稱為活躍頁面，如果分配給一個進程的物理頁面數太少了，則該進程所需的活躍頁面不能全部裝入內存，則進程在運行過程中將頻繁發生缺頁中斷。如果應該為進程提供與活躍頁面數相等的物理頁面數，這樣可以大大減少缺頁中斷次數。

6.8.3.2 基本概念

工作集：一個進程當前正在使用的頁框集合。
工作集W(t,△)=該進程在過去的△個虛擬時間單位中訪問到的頁面的集合。
內容取決于三個因素：
1、訪頁的序列特性；
2、時刻t；
3、工作集窗口長度△，越長工作集越大。

6.8.3.3 工作集算法實現機制

在工作集算法中，基本思路是找出一個不在工作集中的頁面并置換，為此每個頁表項中有一個字段記錄該頁面最近一次被訪問的時間。實現流程如下。
掃描所有的頁表項，依次執行如下操作：
1、如果一個頁面的R位是1，則將該頁面的最后一次被訪問的時間設為當前時間，將R位清零；
2、如果R位是0，則檢查該頁面的被訪問時間是否在“當前時間-T”之前，
1）、如果是，則該頁面為被置換頁面；
2）、若不是，記錄當前所有被掃描過頁面的最后訪問時間里面的最小值，掃描下一個頁面并重復第1步和第2步。

6.9 頁面置換算法小結

如下表所示。
表6-2 頁面置換算法小結

算法評價

OPT	不可實現，但可作為其他算法的衡量基準
NRU	LRU算法很粗略的近似
FIFO	可能置換出重要的頁面，引起Belady異常
Second Chance	相較FIFO有很大的改善
Clock	實現的
LRU	很優秀，但很難實現
NFU	LRU的相對粗略的近似
Aging	非常近似LRU的有效算法
Working set	實現起來開銷很大

7 小結

在對以上重點內容學習之后，再對兩個概念進行補充說明。

7.1 內存映射文件

進程通過一個系統調用（mmap）將一個文件映射到其虛擬地址空間的一部分，訪問這個文件就像訪問內存中的一個大數組，而不是對文件進行讀寫。在多數實現中，并非一次性讀入所有頁面的內容而是在訪問頁面的時候以一次一頁的方式讀入。

7.2 寫時復制技術

例如進程T1、T2共享了物理內存的三個頁面P1、P2、P3，由于頁面被共享，所以每個頁面都被標記成了寫時復制（由只讀標記加上另一個標記組合而成）。當T2試圖改變P2頁面的數據后，但是和只讀標記產生了沖突，產生Page Fault異常，進入了操作系統，操作系統檢查出了該頁面是個寫時復制的頁面，于是在內存中在物理內存中另開辟了一個頁面P2-Copy，把相應內容寫入該頁中。復制的頁面P2-Copy對于執行寫操作的進程是私有的，對其它所有共享寫時復制頁面的進程是不可見的。

總結

以上是生活随笔為你收集整理的【操作系统】存储模型（二）：虚拟存储技术和置换算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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