作業系統記憶體管理之虛拟記憶體
1、虛拟記憶體概念：
在前面的讨論我們知道，在計算機作業系統中，我們使用者看到的記憶體和計算機中的實際實體記憶體是不一樣的，我們需要将計算機的邏輯位址一對一的映射到實體記憶體中，但是我們在實際程序執行過程中，我們會發現，調入記憶體的一些頁我們并不使用，也就是說我們沒必要把這些頁調入記憶體，這就是按需調用的概念，那麼，這樣的話，我們的邏輯位址與實體位址就可以不是一對一的關系了，是以我們提出虛拟記憶體的概念，此時我們的邏輯位址的空間可以大于實體位址的空間，但是在調入記憶體的時候，我們的邏輯位址所占的空間不能大于實體位址的空間，這會出錯，但是在調入記憶體之前的邏輯位址空間可以大于實體位址空間。在程序執行過程中，需要執行的時候，調入記憶體即可。
2、虛拟記憶體技術的實作
虛拟記憶體中，允許将一個作業分多次調入記憶體。釆用連續配置設定方式時，會使相當一部分記憶體空間都處于暫時或“永久”的空閑狀态，造成記憶體資源的嚴重浪費，而且也無法從邏輯上擴大記憶體容量。是以，虛拟記憶體的實作需要建立在離散配置設定的記憶體管理方式的基礎上。虛拟記憶體的實作有以下三種方式：
- 請求分頁存儲管理。
- 請求分段存儲管理。
- 請求段頁式存儲管理。
不管哪種方式，都需要有一定的硬體支援。一般需要的支援有以下幾個方面：
- 一定容量的記憶體和外存。
- 頁表機制（或段表機制），作為主要的資料結構。
- 中斷機構，當使用者程式要通路的部分尚未調入記憶體，則産生中斷。
- 位址變換機構，邏輯位址到實體位址的變換
3、請求分頁管理方式實作虛拟記憶體
請求分頁系統建立在基本分頁系統基礎之上，為了支援虛拟存儲器功能而增加了請求調頁功能和頁面置換功能。請求分頁是目前最常用的一種實作虛拟存儲器的方法。
在請求分頁系統中，隻要求将目前需要的一部分頁面裝入記憶體，便可以啟動作業運作。在作業執行過程中，當所要通路的頁面不在記憶體時，再通過調頁功能将其調入，同時還可以通過置換功能将暫時不用的頁面換出到外存上，以便騰出記憶體空間。
為了實作請求分頁，系統必須提供一定的硬體支援。除了需要一定容量的記憶體及外存的計算機系統，還需要有頁表機制、缺頁中斷機構和位址變換機構。
3.1、頁表機制
請求分頁系統的頁表機制不同于基本分頁系統，請求分頁系統在一個作業運作之前不要求全部一次性調入記憶體，是以在作業的運作過程中，必然會出現要通路的頁面不在記憶體的情況，如何發現和處理這種情況是請求分頁系統必須解決的兩個基本問題。為此，在請求頁表項中增加了四個字段。
請求分頁系統中的頁表項
增加的四個字段說明如下：
- 狀态位P：用于訓示該頁是否已調入記憶體，供程式通路時參考。
- 通路字段A：用于記錄本頁在一段時間内被通路的次數，或記錄本頁最近己有多長時間未被通路，供置換算法換出頁面時參考。
- 修改位M：辨別該頁在調入記憶體後是否被修改過。
- 外存位址：用于指出該頁在外存上的位址，通常是實體塊号，供調入該頁時參考。
3.2、缺頁中斷機構
在請求分頁系統中，每當所要通路的頁面不在記憶體時，便産生一個缺頁中斷，請求作業系統将所缺的頁調入記憶體。此時應将缺頁的程序阻塞（調頁完成喚醒)，如果記憶體中有空閑塊，則配置設定一個塊，将要調入的頁裝入該塊，并修改頁表中相應頁表項，若此時記憶體中沒有空閑塊，則要淘汰某頁（若被淘汰頁在記憶體期間被修改過，則要将其寫回外存)。
缺頁中斷作為中斷同樣要經曆，諸如保護CPU環境、分析中斷原因、轉入缺頁中斷處理程式、恢複CPU環境等幾個步驟。但與一般的中斷相比，它有以下兩個明顯的差別：
- 在指令執行期間産生和進行中斷信号，而非一條指令執行完後，屬于内部中斷。一條指令在執行期間，可能産生多次缺頁中斷。
3.3、位址變換機構
請求分頁系統中的位址變換機構，是在分頁系統位址變換機構的基礎上，為實作虛拟記憶體，又增加了某些功能而形成的。
請求分頁中的位址變換過程
在進行位址變換時，先檢索快表：
- 若找到要通路的頁，便修改頁表項中的通路位（寫指令則還須重置修改位)，然後利用頁表項中給出的實體塊号和頁内位址形成實體位址。
- 若未找到該頁的頁表項，應到記憶體中去查找頁表，再對比頁表項中的狀态位P，看該頁是否已調入記憶體，未調入則産生缺頁中斷，請求從外存把該頁調入記憶體。
4、頁面置換算法
程序運作時，若其通路的頁面不在記憶體而需将其調入，但記憶體已無空閑空間時，就需要從記憶體中調出一頁程式或資料，送入磁盤的對換區。
選擇調出頁面的算法就稱為頁面置換算法。好的頁面置換算法應有較低的頁面更換頻率，也就是說，應将以後不會再通路或者以後較長時間内不會再通路的頁面先調出。
常見的置換算法有以下四種。
4.1、最佳置換算法(OPT)
最佳(Optimal, OPT)置換算法所選擇的被淘汰頁面将是以後永不使用的，或者是在最長時間内不再被通路的頁面,這樣可以保證獲得最低的缺頁率。但由于人們目前無法預知程序在記憶體下的若千頁面中哪個是未來最長時間内不再被通路的，因而該算法無法實作。
最佳置換算法可以用來評價其他算法。假定系統為某程序配置設定了三個實體塊，并考慮有以下頁面号引用串：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
程序運作時，先将7, 0, 1三個頁面依次裝入記憶體。程序要通路頁面2時，産生缺頁中斷，根據最佳置換算法，選擇第18次通路才需調入的頁面7予以淘汰。然後，通路頁面0時，因為已在記憶體中是以不必産生缺頁中斷。通路頁面3時又會根據最佳置換算法将頁面1淘汰……依此類推，如下圖所示。從圖中可以看出釆用最佳置換算法時的情況。
可以看到，發生缺頁中斷的次數為9，頁面置換的次數為6。
| 通路頁面 | 7 | 1 | 2 | 3 | 4 | 2 | 3 | 3 | 2 | 1 | 2 | 1 | 7 | 1 |
| 實體塊1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 7 | |||||
| 實體塊2 | 4 | |||||||||||||
| 實體塊3 | 1 | 1 | 3 | 3 | 3 | 1 | 1 | |||||||
| 缺頁否 | √ | √ | √ | √ | √ | √ | √ | √ |
利用最佳置換算法時的置換圖
4.2、先進先出(FIFO)頁面置換算法
優先淘汰最早進入記憶體的頁面，亦即在記憶體中駐留時間最久的頁面。該算法實作簡單，隻需把調入記憶體的頁面根據先後次序連結成隊列，設定一個指針總指向最早的頁面。但該算法與程序實際運作時的規律不适應，因為在程序中，有的頁面經常被通路。
| 通路頁面 | 7 | 1 | 2 | 3 | 4 | 2 | 3 | 3 | 2 | 1 | 2 | 1 | 7 | 1 | |
| 實體塊1 | 7 | 7 | 7 | 2 | 2 | 2 | 4 | 4 | 4 | 7 | 7 | 7 | |||
| 實體塊2 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | 1 | 1 | ||||||
| 實體塊3 | 1 | 1 | 1 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | |||||
| 缺頁否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
利用FIFO置換算法時的置換圖
這裡仍用上面的執行個體，釆用FIFO算法進行頁面置換。程序通路頁面2時，把最早進入記憶體的頁面7換出。然後通路頁面3時，再把2, 0, 1中最先進入記憶體的頁換出。可以看出，利用FIFO算法時進行了 12次頁面置換，比最佳置換算法正好多一倍。
FIFO算法還會産生當所配置設定的實體塊數增大而頁故障數不減反增的異常現象，這是由 Belady于1969年發現，故稱為Belady異常，隻有FIFO算法可能出現Belady 異常，而LRU和OPT算法永遠不會出現Belady異常。
| 通路頁面 | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
| 實體塊1 | 1 | 1 | 1 | 4 | 4 | 4 | 5 | ,5\' | 5 | |||
| 實體塊2 | 2 | 2 | 2 | 1 | 1 | 1 | 3 | 3 | ||||
| 實體塊3 | 3 | 3 | 3 | 2 | 2 | 2 | 4 | |||||
| 缺頁否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | |||
| 1 | 1 | 1 | 5 | 5 | 5 | 5 | 4 | 4 | ||||
| 實體塊2* | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 5 | |||
| 實體塊3* | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | ||||
| 實體塊4* | 4 | 4 | 4 | 4 | 3 | 3 | 3 | |||||
| 缺頁否 | √ | √ | √ | √ | √ | √ | √ | √ | √ |
Belady 異常
4.3、最近最久未使用(LRU)置換算法
選擇最近最長時間未通路過的頁面予以淘汰，它認為過去一段時間内未通路過的頁面，在最近的将來可能也不會被通路。該算法為每個頁面設定一個通路字段，來記錄頁面自上次被通路以來所經曆的時間，淘汰頁面時選擇現有頁面中值最大的予以淘汰。
再對上面的執行個體釆用LRU算法進行頁面置換，程序第一次對頁面2通路時，将最近最久未被通路的頁面7置換出去。然後通路頁面3時，将最近最久未使用的頁面1換出。
| 通路頁面 | 7 | 1 | 2 | 3 | 4 | 2 | 3 | 3 | 2 | 1 | 2 | 1 | 7 | 1 |
| 實體塊1 | 7 | 7 | 7 | 2 | 2 | 4 | 4 | 4 | 1 | 1 | 1 | |||
| 實體塊2 | 3 | 3 | 3 | |||||||||||
| 實體塊3 | 1 | 1 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 7 | ||||
| 缺頁否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
LRU頁面置換算法時的置換圖
前5次置換的情況與最佳置換算法相同，但兩種算法并無必然聯系。實際上，LRU算法根據各頁以前的情況，是“向前看”的，而最佳置換算法則根據各頁以後的使用情況，是“向後看”的。
LRU性能較好，但需要寄存器和棧的硬體支援。LRU是堆棧類的算法。理論上可以證明，堆棧類算法不可能出現Belady異常。FIFO算法基于隊列實作，不是堆棧類算法。
5、頁面抖動(颠簸)
在頁面置換過程中的一種最糟糕的情形是，剛剛換出的頁面馬上又要換入主存，剛剛換入的頁面馬上就要換出主存，這種頻繁的頁面排程行為稱為抖動，或颠簸。如果一個程序在換頁上用的時間多于執行時間，那麼這個程序就在颠簸。
頻繁的發生缺頁中斷（抖動），其主要原因是某個程序頻繁通路的頁面數目高于可用的實體頁幀數目。虛拟記憶體技術可以在記憶體中保留更多的程序以提髙系統效率。在穩定狀态，幾乎主存的所有空間都被程序塊占據，處理機和作業系統可以直接通路到盡可能多的程序。但如果管理不當，處理機的大部分時間都将用于交換塊，即請求調入頁面的操作，而不是執行程序的指令，這就會大大降低系統效率。