內存換出的重要性及與換入的關系

現在我們講第25講，主題是內存的換出（swipe out）。實際上，上一講我們講的是內存的換入，而這一節聚焦于內存的換出。
換入和換出必須合在一起工作，不能只有換入而沒有換出。上節課也提到，換入換出合在一起的目的是實現虛擬內存。我們有一個0 - 4g的完整虛擬內存空間，但物理內存可能只有1g。這就好比倉庫很大，而門店空間有限。當我們訪問虛擬地址、需要虛擬頁時，就要從磁盤上把這一頁換到內存中。然而，如果只進行換入，不斷地將內容從磁盤換到內存，遲早內存會滿。所以，有換入就必須有換出，這樣才能空出物理內存，讓新的內容換入，保證系統合理工作。

內存換出算法的引出

換出操作涉及到選擇哪一頁淘汰的算法，這個算法與get free page相關。
get free page用于獲取物理空閑頁，它出現在頁面中斷處理程序do no page（14號中斷的處理程序）中。在這個程序里，首先會申請一個空閑頁，然后從磁盤上讀入。但內存有限，并非總有新的空閑頁，所以在申請空閑頁時，如果空閑頁不夠，就需要找一頁換出去，再進行申請，這部分代碼就應該放在這里。接下來我們就來探討有哪些算法可以用于選擇換出的頁面。

常見的頁面置換算法

1. 先來先出（FIFO）算法

   • 最開始能想到的頁面置換算法就是先來先出。這種調度方法本質上和資源分配、剝奪相關，和最大化、最小化問題沒有本質區別。我們通常從最簡單的先來先服務問題開始思考調度算法，然后分析其問題，逐步提出更好的算法。
   • 例如，我們分配了三個頁框，頁面訪問序列為A、B、C、A、B、D。A來了放入1號頁框，B來了放入，C來了也放入。此時A又來，由于頁框已滿，按照先來先出原則，把最先進入的A換出。接著D來了，再把B換出。但這里存在問題，D剛把A換出去，A馬上又來，導致頻繁換入換出，增加了磁盤讀寫操作，降低了指令執行速度。這說明先來先服務算法存在缺點，我們需要改進。

2. 最優（OPT）算法

   • 為了改進FIFO算法的不足，我們引出了最優算法（OPT）。還是以上面的例子，當D要換入時，我們往后看，發現A和B馬上會被使用，而C是未來才會使用，所以換出C是最合適的。這樣操作后，產生缺頁的次數從原來的7次減少到5次，效果變優。
   • 然而，最優算法存在一個嚴重問題，它需要知道將來會訪問哪一頁，但在實際執行過程中，我們無法預知程序將來會執行哪一頁，所以這個算法理論上很完美，但在實際中無法使用。

3. 最近最少使用（LRU）算法

   • 由于無法預知未來，人們想到用過去的歷史去預測未來，這就是LRU算法的核心思想。程序往往具有局部性，在一段時間內會在一定范圍內不斷訪問某些頁面。例如在while循環中，會反復訪問相關頁面。所以，歷史上最近一段時間老使用的頁面，待會兒也很可能會使用；而最近一段時間沒有使用的頁面，我們可以預測未來也不太可能使用，就將其淘汰。
   • 同樣以A、B、C、A、B、D的訪問序列為例，當D要換入時，最近最少使用的是C，所以把C換出。后續操作中，LRU算法的缺頁次數也是5次，效果不錯。在實際系統中通過實驗驗證，LRU算法確實是公認的很好的頁面置換算法。

4. LRU算法的實現及問題

   • 時間戳實現：最常想到的LRU算法實現方式是使用時間戳。為每個頁面維護一個時間戳，記錄頁面的使用時刻。每次訪問頁面時，更新其時間戳。當需要換出頁面時，選擇時間戳最小的頁面。但這種方法在實際操作系統中代價太大，因為每執行一條指令，都要訪問邏輯頁，查頁表進行地址翻譯，此時都需要針對當前在內存中的頁面維護時間戳，不僅要修改時間戳，還可能面臨時間戳溢出的問題，會極大地降低計算機運行速度，不可行。

   • 頁面棧實現：另一種實現方式是使用頁面棧。棧的頂部始終保留最近使用的頁面，其他頁面按照使用順序排列。每次訪問頁面時，將該頁面移動到棧頂。當需要換出頁面時，選擇棧底的頁面。但這種方式同樣存在問題，每次訪問頁面都需要調整棧中頁面的位置，即使使用指針實現，也需要修改多次指針，實現代價也很大，在實際系統中也不實用。

   • 因此，LRU算法雖然理論上優秀，但準確實現困難，需要進行近似實現。

5. Clock算法（二次機會算法）

   • 基本思想：為了近似實現LRU算法，我們引入引用位（reference bit）。每訪問一頁，就將其引用位置為1，表示該頁被訪問過。當需要淘汰頁面時，如果引用位為1，就將其置為0，不淘汰該頁，再給它一次機會；如果引用位為0，說明該頁最近沒有被訪問過，就將其淘汰。這是對LRU算法的一種近似，它不是嚴格的最近最少使用，而是基于最近是否使用來決定是否淘汰頁面。

   • 效率與問題：這種算法的效率相對較高，因為每訪問一頁，只需要修改一位引用位，而且MMU查頁表時可以自動將訪問頁面的引用位置為1。然而，它對LRU的近似效果不好。由于程序具有局部性，缺頁通常很少發生。當缺頁很少時，頁面會被頻繁訪問，引用位會一直保持為1，導致指針掃描時，所有頁面的引用位都為1。一旦缺頁，指針掃描會將所有引用位都置為0，然后按順序換出頁面，這樣就退化成了FIFO算法，失去了LRU算法的思想，頁面置換效果變差。

6. 改進的Clock算法

   • 問題分析與解決：為了解決上述Clock算法的問題，我們需要分析原因。二次機會算法退化成FIFO的原因是引用位記錄了太長的歷史信息，指針掃描速度太慢，無法體現“最近”的概念。所以，解決的核心在于定時清除引用位，縮短其記錄信息的時間。我們可以使用一個掃描指針定時將引用位置為0，這樣就能體現最近一段時間內頁面是否被使用。當淘汰頁面的指針掃描時，如果發現頁面引用位為0，就將其淘汰，這樣更符合LRU算法的思想。
   • 命名由來：這種改進后的算法，一個指針快速清除引用位，一個指針慢速掃描淘汰頁面，就像時鐘的指針轉動，所以被稱為Clock算法。在實際系統中，將定時清除引用位的操作放在時鐘中斷中，淘汰頁面的操作放在缺頁時get free page前面，通過這些程序的相互配合，實現了對LRU算法的近似，完成頁面換出操作。

進程頁面分配數量問題

在解決了頁面換出算法后，還需要考慮一個附帶問題，即應該給一個進程分配多少個頁框。分配的頁框數量過多，會浪費系統內存；分配過少，會產生顛簸問題。

1. 顛簸現象：當進程數量過多時，給每個進程分配的頁框就會減少，導致每個進程的缺頁率增加。例如，一個進程本需要4頁內存，但只分配了3頁。在執行過程中，剛把第4頁換出，馬上又需要使用，再換入第4頁時，又會導致其他某一頁被換出，如此反復，不停缺頁。每次缺頁都要啟動磁盤進行頁面換入換出，CPU需要等待磁盤操作完成，導致CPU利用率急劇下降，這種現象就是系統顛簸。系統一旦出現顛簸，效率會變得很低，用戶程序無法正常推進，用戶體驗變差。
2. 合理分配數量：為了避免顛簸，分配給進程的頁框個數應該能夠覆蓋住程序訪問內存的局部。但這個局部的大小很難確定，因為程序的執行情況復雜，包含循環、條件語句等多種結構。雖然有一些算法可以計算工作集來確定局部大小，進而確定合理的頁框分配數量，但在一些基本的操作系統中，也可以采用近似算法，根據缺頁情況動態調整頁框分配數量。例如，如果缺頁較多，就多分配幾個頁框；如果缺頁較少，就少分配幾個頁框。總之，要合理調整給進程分配的頁框數量，避免顛簸現象的發生。

換入換出與操作系統整體架構

當我們確定好給進程分配的頁框數量后，就可以形成一個Clock的環形數組，應用Clock算法進行頁面淘汰和內存換出操作。結合之前講的內存換入（當訪問地址缺頁時，進行缺頁中斷，從磁盤讀入一頁，若頁框不足，使用Clock算法換出一頁，再將新頁換入），這就構成了完整的內存換入換出過程，也就是著名的swap分區的工作原理。在安裝Linux時，通常會讓用戶安裝swap分區，它的工作就是進行內存的換入換出。
實現換入換出是為了實現虛擬內存，而虛擬內存又是為了實現分頁，分頁是操作系統管理內存的重要思想，目的是讓程序能夠載入并執行起來，最終落實到進程的運行。內存管理和進程管理是操作系統的核心部分，再加上外圍的設備驅動、文件系統、系統接口以及系統初始化和引導等模塊，就構成了一個完整的操作系統。如果能夠深入理解這些內容，將其融會貫通，就能對操作系統有更深刻的認識，甚至有可能自己設計和實現一個操作系統，或者在實際操作系統中進行模塊設計和修改 。