前言

正在學習作業系統，記錄筆記。

參考資料：

《作業系統（精髓與設計原理第8版）》

第八章：虛拟記憶體

在正式開始前先介紹一下本章要用到的術語：

術語	解釋
虛拟記憶體（Virtual memory）	一種存儲器配置設定方案，在這種配置設定方案中，輔助存儲器可以被尋址，就好像它是主存儲器的一部分一樣。程式可用于引用記憶體的位址與記憶體系統用于辨別實體存儲站點的位址相差別，程式生成的位址自動轉換為相應的機器位址。虛拟存儲器的大小受到計算機系統尋址方案和可用輔助存儲器數量的限制，而不受主存儲器位置的實際數量的限制
虛拟位址（Virtual address）	在虛拟記憶體中配置設定給某一位置的位址，它使得該位置可被通路，就好像是主存的一部分那樣
虛拟位址空間（Virtual address space）	配置設定給程序的虛拟存儲
位址空間（Address space）	用于某程序的記憶體位址範圍
實位址（Real address）	記憶體中存儲位置的位址

硬體和控制結構

由上一章我們可以了解到分頁和分段機制在記憶體管理中取得的根本性突破：

程序中的所有記憶體通路都是邏輯位址，這些邏輯位址會在運作時動态地轉換為實體位址。這意味着一個程序可被換入或換出記憶體，是以程序可在執行過程的不同時刻占據記憶體中的不同區域。
一個程序可劃分為許多塊（頁和段），在執行過程中，這些塊不需要連續地位于記憶體中。

那麼我們由此可以思考：如果保有上述這兩個特點，在程式執行中，不需要程序的所有部分（頁或段）都被加載到記憶體中，如果記憶體中儲存有待取的下一條指令的所在塊（頁或段）以及待通路的下一個資料單元所在的塊，那麼程序可以持續運作下去。

接着就來描述一下程式如何以這樣的方式在記憶體中運作：

一個新程序被載入記憶體，作業系統在最初隻是載入新程式最開處的一個或幾個塊（頁或段），而非全部。
**常駐集：**程序執行的任何時候都在記憶體的部分稱為程序的常駐集。

隻要所有記憶體通路都是通路常駐集中的單元，執行就可以順利進行。
當處理器需要通路一個不在記憶體中的邏輯位址時：
- 會産生一個中斷（缺頁中斷），即出現了記憶體通路故障。
- 作業系統會将此程序置于阻塞态。
作業系統會把包含引發通路故障的邏輯位址的程序塊讀入記憶體，具體流程如下：
- 作業系統産生一個磁盤I/O讀請求。
- 在執行磁盤I/O期間，作業系統可以排程另一個程序運作。
- 當需要的塊讀入記憶體後，再産生一個中斷，作業系統把之前由于缺少程序塊而被阻塞的程序置位就緒态。
程序繼續執行。

這種執行程序的政策有以下優點（暫且不考慮由于中斷、載入新塊所帶來的效率影響）：

在記憶體中保留多個程序：
- 對于任何特定程序，都隻載入某些部分到記憶體中，這樣記憶體會有足夠的空間運作多個程序。
- 由于記憶體中存在的程序數量增加，那麼在任意時刻總會有至少一個程序處于就緒态，進而使得處理器沒有閑置狀态，提高了效率。
支援運作大于主存的程式：
- 大程式可以分成小塊，通過某種覆寫政策分别加載。（基于分段或分頁的虛拟記憶體）

實存儲器（簡稱：實存，real memory）：就是主存（main memory），程序隻能在此運作。

虛拟記憶體（簡稱：虛存，virtual memory）：

通常配置設定在磁盤上
支援更有效的系統并發度
可以解除使用者與記憶體之間沒有必要的緊密限制

下表總結了使用和不使用虛存情況下分頁和分段的特點：

簡單分頁虛存分頁簡單分段虛存分段記憶體劃分為大小固定的小塊，稱為頁框記憶體劃分為大小固定的小塊，稱為頁框記憶體未劃分記憶體未劃分程式被編譯器或記憶體管理系統劃分為頁程式被編譯器或記憶體管理系統劃分為頁由程式員給編譯器指定程式段（即由程式員決定）由程式員給編譯器指定程式段（即由程式員決定）頁框中有内部碎片頁框中有内部碎片無内部碎片無内部碎片無外部碎片無外部碎片有外部碎片有外部碎片作業系統須為每個程序維護一個頁表，以說明每頁對應的頁框作業系統須為每個程序維護一個頁表，以說明每頁對應的頁框作業系統須為每個程序維護一個段表，以說明每段中的加載位址和長度作業系統須為每個程序維護一個段表，以說明每段中的加載位址和長度作業系統須維護一個空閑頁框清單作業系統須維護一個空閑頁框清單作業系統須維護一個記憶體中的空閑空洞清單作業系統須維護一個記憶體中的空閑空洞清單處理器使用頁号和偏移量來計算絕對位址處理器使用頁号和偏移量來計算絕對位址處理器使用段号和偏移量來計算絕對位址處理器使用段号和偏移量來計算絕對位址程序運作時，它的所有頁必須都在記憶體中，除非使用了覆寫技術程序運作時，并非所有頁都須在記憶體頁框中。僅在需要時才讀入頁程序運作時，其所有段都須在記憶體中，除非使用了覆寫技術程序運作時，并非其所有段都須在記憶體中。僅在需要時才讀入段把一頁讀入記憶體可能需要把另一頁寫出到磁盤把一段讀入記憶體可能需要把另外一段或幾段寫出到磁盤

系統抖動/系統颠簸（Thrashing）：當作業系統讀入一個塊時，必須将另一個塊換出，如果被換出的塊在不遠的将來會用到，那麼該塊又會被重新換入。如果這種情況經常發生，導緻處理器的大部分時間都用來處理交換塊而非執行指令。這樣的現象被稱為系統抖動。

局部性和虛拟記憶體

虛存的優勢确實很有吸引力，但是曾經對于虛存的方案有過争論，其關鍵點就在于程序塊的切換：如何有效地加載部分塊到記憶體中，以及避免系統抖動。但是局部性原理表明虛拟記憶體的方案是切實可行的。

局部性原理：

一個程序中的程式和資料引用存在集簇傾向。
在一個很短的時間内僅需要程序的一部分塊是合理的。
可以對未來可能會通路的塊進行預測，進而避免系統抖動。

事實上在衆多作業系統的經驗也已經證明了虛拟記憶體的可行性，但是要使虛存比較實用且有效，還需要兩方面的因素：

必須有對所采用分頁或分段方案的硬體支援
作業系統必須能夠管理頁或段在記憶體和輔助存儲器（簡稱：輔存）之間的移動

分頁

頁表

每個程序都有自己的頁表
**頁表項（Page Table Entry，PTE）**包含有與記憶體中的頁框相對應的頁框号
每個頁表項需要有一個P位來表示它所對應的頁目前是否在記憶體中

一個程序可能隻有一部分頁在記憶體中
每個頁表項需要有一個M位來表示相應頁的内容從上次裝入記憶體到現在是否已改變
- 若未改變，則在需要把該頁換出時，無須用頁框中的内容更新該頁（無需寫入磁盤）

位址轉換系統：

從記憶體中讀取一個字需要頁表從虛拟位址（邏輯位址）到實體位址的轉換

說明：

虛拟位址/邏輯位址由頁号和偏移量組成；實體位址由頁框号和偏移量組成
當程序運作時，一個寄存器儲存該程序頁表的起始位址
虛拟位址的頁号（Page #，n位）用于檢索頁表，以查找相應的頁框号（Frame，m位）
查找到的頁框号作為實體位址的頁号，再與虛拟位址的偏移量結合起來形成最終的實體位址。（頁框号|偏移量）
- 一般情況下，頁号域長于頁框号域（n > m）
- 由于頁表長度是變化的，因而不能期望在寄存器儲存它。寄存器隻能儲存一個指向頁表起始位址的頁表指針（Page Table Rtr）

考慮這樣一個情景：如果每個程序的虛存空間可達 231 = 2GB，如果頁大小為 29 = 512位元組，那麼則每個程序需要 231 / 29 = 222 個頁表項。這反映出整個頁表的大小與虛拟位址空間的大小成正比，而導緻的後果就是：将耗費大量的記憶體空間去放置頁表。

兩級層次頁表

為了解決這個問題，思考一下是否可以将頁表也存儲于虛拟記憶體中。于是有了兩級層次頁表的結構：

說明：

當一個程序正在運作時，它的頁表至少有一部分須在記憶體中，這一部分包括正在運作的頁的頁表項
頁目錄：其中的每項指向一個頁表
- 如果頁目錄的長度為X，且一個頁表的最大長度為Y，則一個程序可以有XY頁
分析上圖執行個體（用于32位位址的兩級方案）：
- 頁大小為：4KB（212）；虛拟位址空間大小為：4GB（232）
- 則該虛拟位址空間由 232 / 212 = 220 個頁組成
- 規定每個頁都由一個4位元組的頁表項映射，則可以建立一個由220頁組成的一個頁表，這時需要220 × 22 = 222 = 4MB 的記憶體空間
  - 我們可以将這部分内容保留到虛存中，那麼該部分虛拟記憶體空間又由222 / 212 = 210 個頁組成
  - 這210 個頁又可以組成一個新的根頁表，其占據的記憶體為：210 × 22 = 212 = 4KB
- 如此一來，我們便可僅在記憶體中存放一個4KB大小的根頁表，去通路一個4GB大小的虛拟記憶體中的資料

兩級層次頁表方案所對應的虛拟位址到實體位址的轉換流程如下：

說明：

虛拟位址的前10位用于檢索根頁表，查找關于使用者頁表的頁的頁表項
- 若該頁不在記憶體中，則發生一次缺頁中斷
若該頁在記憶體中，則用虛拟位址中接下來的10位檢索使用者頁表項頁，查找該虛拟位址引用的頁的頁表項
最終查找到的頁框号作為實體位址的頁号，再與虛拟位址的偏移量結合起來形成最終的實體位址。（頁框号|偏移量）[同之前的方案一緻]

反向頁表/倒排頁表

替代一級或多級頁表的一種方法是，使用一個反向頁表結構（Inverted Page Table）。

虛拟位址的頁号部分被映射成一個hash值（散列函數映射），hash映射值構成一個散清單
hash值指向反向頁表

散清單包含指向反向表的指針，反向表中含有頁表項
得益于散列技術，多個虛拟位址可能映射到同一個散清單項中，可以減少表的容量

多對一的映射關系可能導緻資料通路沖突，但是也有相應的解決通路沖突的算法，這裡先不考慮

頁表結構稱為“倒排/反向”的原因是，它使用頁框号而非虛拟頁号來索引頁表項

反向頁表的每項都包含如下内容：

頁号（Page number）：虛拟位址的頁号部分
程序辨別符（Process identifier）：使用該頁的程序

頁号和程序标志符共同标志一個特定程序的虛拟位址空間的一頁
控制位（Control bits）：該域包含一些标記，比如有效、通路和修改，以及保護和鎖定資訊
鍊指針（Chain pointer）：
- 若某項沒有鍊項，則該域為空（或用一個單獨的位來表示）
- 否則，該域包含鍊中下一項的索引值（0 ~ 頁框數量-1 之間的數字）

執行個體：

分析：

實體記憶體中有2m個頁框，反向頁表包含2m項
虛拟位址前n位表示頁号，且 n > m
散列函數映射n位頁号到m位數，用這m位數去索引反向頁表
由此得頁框号作為實體位址的頁号，再與虛拟位址的偏移量結合起來形成最終的實體位址

轉移後備緩沖器/旁視緩沖器

原則上，每次虛存通路都可能會引起兩次實體記憶體通路：

一次取相應的頁表項
另一次取需要的資料

是以，簡單的虛拟記憶體方案會導緻記憶體通路時間加倍。為了解決這個問題，引入轉移後備緩沖器。

轉移後備緩沖器/旁視緩沖器（Translation Lookaside Buffer，TLB）：大多數虛拟記憶體方案都為頁表項使用了一個特殊的高速緩存，它包含有最近用過的頁表項。

具體虛拟位址轉換為實體位址的流程如下：

說明：

給定一個虛拟位址，處理器首先檢查TLB
- 若需要的頁表項在其中（TLB命中），則檢索頁框号并形成實位址
- 若未找到需要的頁表項（TLB未命中），則處理器用頁号檢索程序頁表，并檢查相應的頁表項
  - 若“存在位”已置位（表示該頁在記憶體中），處理器從頁表項中檢索頁框号以形成實位址。同時更新TLB，使其包含這個新頁表項。
  - 若“存在位”未置位（表示該頁不在記憶體中），這時會産生缺頁故障中斷，會去磁盤尋找資料。最後更新頁表和TLB
詳細流程見下圖（包括關于缺頁處理的細節）：

最後，虛拟存儲機制需要與記憶體中的高速緩存進行互動（如下圖）：

說明：

記憶體系統檢視TLB中是否存在比對的頁表項
- 若存在，就組合頁框号和偏移量，形成實體位址
- 若不存在，則從頁表中讀取頁表項。産生由一個标記（tag）和其餘部分組成的實位址後，檢視高速緩存中是否存在包含這個字的塊
  - 若有，則把它傳回給CPU
  - 若沒有，則從記憶體中檢索這個字

先來一個小梳理：

虛拟位址轉換為實位址時，需要通路頁表項，而頁表項可能在TLB中，也可能在記憶體中或磁盤中，且被通路的字可能在高速緩存中、記憶體中或磁盤中。若被通路的字隻在磁盤中，則包含該字的頁必須裝入記憶體，且它所在的塊須裝入高速緩存。此外，包含該字的頁所對應的頁表項必須更新。

頁尺寸

頁尺寸是一個重要的硬體設計決策，它需要考慮多方面的因素：

頁越小，内部碎片的總量越少
頁越小，每個程序需要的頁的數量就越多，這就意味着更大的頁表
對于大程式，活動程序有一部分頁表在虛存而非記憶體中，進而導緻一次記憶體通路可能産生兩次缺頁中斷：
- 第一次讀取所需的頁表部分
- 第二次讀取程序頁
又基于大多數輔存裝置的實體特性，為了實作更為有效的資料塊傳送，它們更希望頁尺寸比較大

頁尺寸對缺頁中斷發生機率的影響使得這些問題變得更為複雜：

如果頁尺寸非常小，那麼每個程序在記憶體中就有較多數量的頁

一段時間後，記憶體中的頁都包含有最近通路的部分，是以缺頁率較低
當頁尺寸增加時，每頁包含的單元和任何一個最近通路過的單元越來越遠（削弱局部性原理）

這會導緻缺頁率增長

但是，當頁尺寸接近整個程序的大小時，缺頁率開始下降。當一頁包含整個程序時，不會發生缺頁中斷（如下圖(a)，這很好了解）

更為複雜的是，缺頁率還取決于配置設定給一個程序的頁框的數量（如上圖(b)），該圖表明：對固定的頁尺寸，當記憶體中的頁數量增加時，缺頁率會下降（這也不難了解）

分段

段的大小不等，并且是動态的
簡化了對不斷增長的資料結構的處理

特定的資料結構（程式員并不知曉最後會變得多大）可以配置設定到它自己的段，需要時作業系統可以擴大或縮小這個段。

若擴大的段需要在記憶體中，且記憶體中已無足夠的空間，作業系統則把這個段移到記憶體中的一個更大區域（如果可以得到），或把它換出。對于後一種情況，擴大的段會在下次有機會時換回。
允許程式獨立地改變或重新編譯，而不要求整個程式集重新連結和重新加載
有助于程序間的共享

程式員可以在段中放置一個實用工具程式或一個有用的資料表，供其他程序通路
有助于保護

由于一個段可被構造成包含一個明确定義的程式或資料集，因而程式員或系統管理者可以更友善地指定通路權限

每個程序都有自己的段表，每個段表項包含：

相應段在記憶體中的起始位址（段基址）
段的長度
有一個P位來表示它所對應的段目前是否在記憶體中
有一個M位來表示相應段的内容從上次裝入記憶體到現在是否已改變

虛拟位址到實體位址的轉換：

說明：

當一個程序正在運作時，有一個寄存器為該程序儲存段表的起始位址
虛拟位址中的段号（Seg #）用于檢索段表，查找得到該段起始點的相應的記憶體位址（Base）
将得到的基位址與虛拟位址中的偏移量（offset）相加，得到最終的實體位址

段頁式

分頁和分段各有優勢：

分頁對程式員是透明的，它消除了外部碎片，因而能更有效地使用記憶體
分段對程式員是可見的，它具有處理不斷增長的資料結構的能力，及支援共享和保護的能力

結合這二者的優點，引出了段頁式結構。

先來介紹段表項以及頁表項的結構：

段表項：
- 包含段的長度
- 包含一個指向一個頁表的基域
- 無存在位和修改位
頁表項：
- 與純粹的分頁系統中的頁表項相同

虛拟位址到實體位址的轉化：

說明：

當一個程序正在運作時，使用一個寄存器記錄該程序段表的起始位址
處理器利用虛拟位址中的段号（Seg #）來檢索程序段表以尋找該段的頁表
虛拟位址中的頁号（page #）用于檢索頁表并查找相應的頁框号
最後得到的頁框号就是實體位址的頁号，結合虛拟位址的偏移量，得到最終的實體位址

保護和共享

分段有助于實作保護與共享機制。由于每個段表項包括一個長度和一個基位址，因而程式不會不經意地通路超出該段的記憶體單元。為實作共享，一個段可能會在多個程序的段表中引用。當然，在分頁系統中也可得到同樣的機制。但是，這種情況下由于程式的頁結構和資料對程式員不可見，是以更難說明共享和保護需求。（下圖說明了這類系統中可以實施的保護關系的類型）

作業系統軟體

在實作記憶體管理的時候，需要考慮三方面的因素：

是否支援虛拟存儲
虛拟存儲的具體實作方式（分頁、分段、段頁式）
作業系統在記憶體配置設定時的具體算法

前兩個因素取決于硬體部分，而第三個因素屬于作業系統軟體領域的問題，以下将會介紹虛拟存儲考慮的六種政策。

讀取政策

讀取政策（Fetch Policy）決定一個頁何時被取入記憶體，常用到的有以下兩種方法：

請求分頁式（Demand paging）：隻有當通路到某頁中的一個單元時才将該頁取入記憶體。
- 當一個程序首次啟動時，會在一段時間出現大量的缺頁中斷
  
  取入越來越多的頁後，局部性原理表明大多數将來通路的頁都是最近讀取的頁。是以，在一段時間後錯誤會逐漸減少，缺頁中斷的數量會降到很低。
預約分頁式（Prepaging）：啟動程序時一次讀取頁的數量要比實際需要通路的多。
- 更為有效的做法是一次讀取輔存裝置（如磁盤）中連續的頁
  
  由于該政策本身的原因，可能會導緻大部分讀取的頁執行程序不會通路，在這種情況下該政策其實是低效的。

為了有效地提高效率，可以采用兩種政策相結合的方式：在程序首次啟動時以及發生缺頁中斷時采用預約分頁式政策，在正常執行時采用請求分頁式政策。

放置政策

放置政策（Placement Policy）決定一個程序塊駐留在實存中的什麼位置。

在分段系統以及非一緻存儲通路（NonUniform Memory Access，NUMA）系統中很重要
對于分頁和段頁式系統，放置政策通常無關緊要

位址轉換硬體和記憶體通路硬體能以相同的效率為任何頁框組合執行相應的功能，是以分頁和段頁式系統對于放置不敏感

置換政策

當記憶體已滿，在程序必須讀取一個新頁時，不得不置換出記憶體中的一頁，關于如何置換頁，置換政策（Replacement Policy）給出了一些方法。

首先我們要考慮置換頁時，我們應該選擇哪些頁被換出：

置換的目标應該聚焦在那些在未來一段時間内不會被程序通路到或是通路次數很少的頁（這不難了解）

這裡需要聲明一點（包括在以後的章節中也有此類問題）：關于未來程序的執行需要哪些通路，程式員以及作業系統都是無法預測的。

（很多設計之初是這樣的，在最開始有一個理想的目标或定位。但是在實作起來卻發現在實際操作中會遇到緻命的問題。要麼采用一些手段去想辦法解決，要麼退而求其次，修改一下目标實作）
大多數政策都基于過去的行為來預測将來的行為

好在智慧的人們總結出來這麼一條規律：以曆史去推測未來。

局部性原理告訴我們：最近的通路曆史和最近将要通路的模式間有很大的相關性。

（既然我們無法站在現在去預測未來，那我們就站在曆史的角度去觀測現在）
值得注意的是，置換政策設計得越精緻、越複雜，實作它的軟硬體開銷就越大

頁框鎖定

在置換頁時需要注意的是，置換政策有一個限制條件——頁框鎖定（Frame Locking）。

記憶體中的某些頁框可能是被鎖定的，當一個頁框被鎖定時，目前儲存在該頁框中的頁就不能被置換。例如以下内容：

作業系統的核心
重要的控制結構
I/O緩沖區以及一些其他對時間要求嚴格的區域

鎖定是通過給每個頁框關聯一個“鎖定”位實作的，這一位可以包含在頁框表和目前的頁表中。

基本算法：不論采用哪種駐留集管理政策，都有一些用于選擇置換頁的基本算法。包括以下四種：

最佳（Optimal policy，OPT）
最近最少使用（Least Recently Used ，LRU）
先進先出（First In First Out，FIFO）
時鐘（Clock）

最佳（OPT）

OPT政策選擇置換下次通路距目前時間最長的那些頁。

這種算法導緻的缺頁中斷最少
但是要求作業系統需要預測未來通路

最近最少使用（LRU）

LRU政策選擇置換記憶體中最長時間未被引用的頁。

如何了解“最近最少使用”：即在短時間的未來最少被程序通路的頁。

同樣根據局部性原理，在記憶體中最長時間未被引用的頁，也是短時間内未來最不可能通路到的頁。

實作方法是：

給每頁添加一個最後一次通路的時間戳，并在每次通路記憶體時更新這個時間戳。
- 這種方案需要硬體的支援，會造成大量的開銷
維護一個關于通路頁的棧
- 依然會造成大量的開銷

先進先出（FIFO）

将配置設定給程序的一個頁框視為一個循環緩沖區，以順次循環的方式替換頁。

隻需要一個指針，該指針在程序的頁框中循環
這是最簡單的一種算法
該方法會将駐留在記憶體中最久的頁替換出去，但是有可能該頁會在未來的不久被通路到

時鐘政策（Clock）

給每一個頁框關聯一個稱為

使用位

的附加位，整個緩沖區（也是循環的）有一個指針：

當一個頁首次被加入到記憶體中時，使用位被置為1（首次加載當然會被通路）
- 随後被通路到（在通路産生缺頁中斷後）時也會置為1。（簡單講：隻要被程序通路，使用位就置位1）
當一個頁面被置換時，指針指向緩沖區的下一個頁框
考慮如何置換（程序的頁框已被占滿）：
- 需要置換一頁時，作業系統從指針指向的頁框順次掃描整個緩沖區，如果找到第一個使用位為0的頁框，就将該頁置換出去，并将使用位置為1，指針指向下一個頁框
- 在指針掃描過程中，如果遇到使用位為1的頁框，将其置為0，繼續掃描，直到找到使用位為0的頁框，進行替換
- 緩沖區是循環的，用圖像具象化展示該種政策也不難了解為什麼稱之為時鐘政策
具體執行個體如下圖：

下圖給出了四種政策的例子：

假設該程式所需要的頁位址順序為：2、3、2、1、5、2、4、5、3、2、5、2
假設為該程序配置設定了3個頁框（駐留集大小固定）

說明：

F 表示産生缺頁中斷
始終政策中：有符号 * 表示該頁框的使用位被置位1，沒有标記則表示0

針對上述四種算法的相關實驗結果如下圖：

說明：假設配置設定給一個程序的頁框數量是固定的。該實驗結果基于在一個FORTRAN程式中執行 0.25 × 106次通路，頁尺寸為256個字

縱軸表示每1000次通路的缺頁；橫軸表示配置設定的頁框數
當配置設定的頁框比較少時，四種政策的差别非常顯著
結果表明，為了更高效的執行，我們希望：
- 能處于拐點的右側（即缺頁率小）
- 同時又希望處于拐點左側（即保證小頁框的配置設定）
- 是以表明需要的操作模式應位于曲線的拐點處

增強型時鐘

之前讨論的算法中，隻考慮到了如何置換，而當頁被修改時，并未讨論。

基于時鐘政策，考慮到頁修改的情況，于是有了增強型時鐘政策：在原有使用位的基礎上，新增添了一個修改位。

修改位是必須的，若某頁被修改，則在它被寫回外存前不會被置換出。

考慮以下四種情形（使用位用

表示，修改位用

表示）：

最近未被通路，也未被修改（u=0；m=0）
最近被通路，但未被修改（u=1；m=0）
最近未被通路，但被修改（u=0；m=1）
最近被通路，且被修改（u=1；m=1）

根據以上分類，時鐘算法對于使用位的政策不變，具體流程如下：

先掃描 u=0；m=0 的頁，如果遇到，則置換該頁
若上一步失敗，則掃描 u=1；m=0 的頁，如果遇到，則置換該頁
若上一步失敗，則傳回第一步（指針回到其最初的位置），此時便有u=0的頁了

頁緩沖

考慮開銷的問題，無疑FIFO的政策是最簡單的，但是很明顯它可能造成抖動，這是不被接受的。于是在考慮能否以FIFO政策為基礎提出一種改進算法，這便有了頁緩沖（Page Buffering）。

提供了兩個表，當頁發生置換時：
- 若頁未被修改，則配置設定到空閑頁表（Free page list）中
- 若已被修改，則配置設定到修改頁表（Modified page list）中
- 這些操作的一個重要特點是，被置換的頁仍然留在記憶體中。是以，若程序通路該頁，則可迅速傳回該程序的駐留集，且代價很小。
- 實際上，空閑頁連結清單和修改頁連結清單充當着頁的高速緩存的角色。
- 修改頁表還有另外一種很有用的功能：已修改的頁按簇寫回，而不是一次隻寫一頁，是以大大減少了I/O操作的數量，進而減少了磁盤通路時間。

高速緩存

置換政策和高速緩存大小如前所述，随着記憶體越來越大，應用的局部性特性逐漸降低。作為補償，高速緩存的大小也相應增加。較大的高速緩存，甚至是幾兆位元組的高速緩存，現在也是合理的設計選擇。

駐留集管理

駐留集大小

駐留集（Resident Set）大小對于分頁式虛拟記憶體，在準備執行時，不需要也不可能把一個程序的所有頁都讀入記憶體。是以，作業系統必須決定讀取多少頁，即決定給特定的程序配置設定多大的記憶體空間。這需要考慮以下幾個因素：

配置設定給一個程序的記憶體越少，在任何時候駐留在記憶體中的程序數就越多。

這增加了作業系統至少找到一個就緒程序的可能性，減少了由于交換而消耗的處理器時間。
若一個程序在記憶體中的頁數較少，盡管有局部性原理，缺頁率仍相對較高。
給特定程序配置設定的記憶體空間超過一定大小後，由于局部性原理，該程序的缺頁率沒有明顯的變化。

基于以上因素，當代作業系統通常采取以下兩種政策：

固定配置設定政策（Fixed-allocation）：
- 在程序執行時，為其在記憶體中配置設定固定數量的頁框（這一數量在程序建立時就被确定）
- 一旦在程序的執行過程中發生缺頁中斷，該程序的一頁就必須被它所需要的頁面置換
可變配置設定政策（Variable-allocation）：
- 允許配置設定給一個程序的頁框在該程序的生命周期中不斷地發生變化。
  
  理論上：
  - 若一個程序的缺頁率一直比較高，則表明在該程序中局部性原理表現較弱，應給它多配置設定一些頁框以減小缺頁率；
  - 若一個程序的缺頁率特别低，則表明從局部性的角度看該程序的表現非常好，可在不明顯增大缺頁率的前提下減少配置設定給它的頁框。
  看起來的優勢政策必然會導緻開銷：可變配置設定政策要求作業系統對活動程序進行評估；除此之外還包括硬體上的開銷。

置換範圍

置換政策的範圍分為以下兩類：

局部置換政策（Local Replace Policy）：在替換頁時，僅在産生這次缺頁的程序的駐留頁中選擇。
全局置換政策（Global Replace Policy）：把記憶體中所有未被鎖定的頁都作為置換的候選頁，而不管它們屬于哪個程序。

置換範圍和駐留集大小之間存在一定的聯系（如下表）：

局部置換	全局置換
固定配置設定	配置設定給一個程序的頁框數是固定的從配置設定給該程序的頁框中選擇被置換的頁	無此方案
可變配置設定	配置設定給一個程序的頁框數不時變化，用于儲存該程序的工作集從配置設定給該程序的頁框中選擇被置換的頁	從記憶體中的所有可用頁框中選擇被置換的頁；這将導緻程序駐留集的大小不斷變化

下面來一一詳細介紹：

固定配置設定、局部置換

配置設定給在記憶體中運作的程序的頁框數固定

總頁數配置設定得過少時，會産生很高的缺頁率
總頁數配置設定得過多時，記憶體中隻能有很少的幾個程式，處理器會有很多空閑時間，并把大量時間花費在交換上

可變配置設定、全局置換

該種組合方式最容易實作，并被許多作業系統使用
作業系統除了為每個程序配置設定了一定數量的頁框，還維護有一個空閑頁框清單，發生一次缺頁中斷時，一個空閑頁框會被添加到程序的駐留集，并讀入該頁。是以發生缺頁中斷的程序的大小會逐漸增大
- 如果沒有空閑頁框可用時，作業系統必須選擇一個目前位于記憶體中的頁框進行置換（不包括被鎖定的頁框）

問題：選擇的置換頁可以屬于任何一個駐留程序，而沒有任何原則用于确定哪個程序應從其駐留集中失去一頁。是以，駐留集大小減小的那個程序可能并不是最适合被置換的。

解決此問題的一種方法是使用頁緩沖：按照這種方法，選擇置換哪一頁并不重要，因為如果在下次重寫這些頁之前通路到了這一頁，則這一頁仍可回收。

可變配置設定、局部置換

為了解決可變配置設定、全局置換的潛在問題，引入了另一種組合：可變配置設定、局部置換。

當一個新程序被裝入記憶體時，根據應用類型、程式要求或其他原則，給它配置設定一定數量的頁框作為其駐留集
- 使用預先分頁或請求分頁填滿這些頁框
發生一次缺頁中斷時，從産生缺頁中斷的程序的駐留集中選擇一頁用于置換
不時地重新評估程序的頁框配置設定情況，增加或減少配置設定給它的頁框，以提高整體性能

清除政策

與讀取政策相反，清除政策（Clearing Policy）用于确定何時将已修改的一頁寫回輔存，通常有以下兩種選擇：

請求式清除（Demand cleaning）：隻有當頁被選擇用于置換時才被寫回輔存。
預約式清除（Precleaning）：将這些已修改的多頁在需要使用它們所占據的頁框之前成批寫回輔存。

分析：

完全使用任何一種政策都存在問題：
- 對于請求式清除：寫回已修改的頁和讀入新頁是成對出現的，且寫回在讀入之前。這就意味着當發生缺頁中斷的程序在解除阻塞之前必須等待兩次頁傳送，可能降低處理器效率。
- 對于預約式清除：需要被寫回輔存的頁可能仍然留在記憶體中，直到頁面置換算法訓示它被移出。預約式清除允許成批地寫回頁，但是這樣意義不大，因為這些頁中地大部分通常在置換前又被修改。

由于單純使用某一種政策都會有潛在的問題，一種比較好的方式就是結合頁緩沖技術。具體政策：隻清除可用于置換的頁，但去除了清除和置換操作間的成對關系。

被置換的頁會放在如下兩個頁表中：
- 修改表：修改表中的頁可以周期性地成批寫出，并移入未修改表中。
- 未修改表：未修改表中的一頁要麼因為被重新通路而被回收，要麼在其頁框配置設定給另一頁時被淘汰。

加載控制

加載控制（Load Control）會影響到駐留在記憶體中的程序數量，這稱為系統并發度。

如何控制系統并發度是一個值得思考的問題，因為有以下兩種情況影響着處理器使用率：

如果駐留程序太少，那麼所有程序都處于阻塞态的機率就較大。
如果駐留程序太多，那麼平均每個程序的駐留集大小将會不夠用，此時會頻繁發生缺頁中斷，導緻系統抖動。

最好能夠保證并發度達到圖中虛線位置，使處理器效率達到最大

工作集或PFF算法都隐含了加載控制。

隻允許執行那些駐留集足夠大的程序。
在為每個活動程序提供需要的駐留集大小時，該政策會自動并動态地确定活動程式的數量。

程序挂起

系統并發度減小時，一個或多個目前駐留程序須被挂起（換出）。具體為以下六種情況：

最低優先級程序：實作排程政策決策，與性能問題無關。
缺頁中斷程序：原因在于很有可能是缺頁中斷任務的工作集還未駐留，因而挂起它對性能的影響最小。

此外，由于它阻塞了一個一定會被阻塞的程序，并且消除了頁面置換和I/O操作的開銷，因而該選擇可以立即收到成效。
最後一個被激活的程序：這個程序的工作集最有可能還未駐留。
駐留集最小的程序：在将來再次裝入時的代價最小，但不利于局部性較小的程式。
最大空間的程序：可在過量使用的記憶體中得到最多的空閑頁框，使它不會很快又處于去活（deactivation）狀态。
具有最大剩餘執行視窗的程序：在大多數程序排程方案中，一個程序在被中斷或放置在就緒隊列末尾之前，隻運作一定的時間。這近似于最短處理時間優先的排程原則。

後記

本篇已完結

通過本章細細品味一下作業系統為何在計算機學課中是具有那麼一些哲學味道的學課🤔🤔🤔🤔

（如有修改或補充歡迎評論）

作業系統學習筆記-虛拟記憶體前言第八章：虛拟記憶體後記

前言