作業系統-6——虛拟記憶體

一、基本概念

• 虛拟記憶體：用輔助存儲器（一般指磁盤）作為記憶體的補充。虛拟記憶體允許程序執行時隻将部分程式放入記憶體，是以程式可以比實體記憶體大。虛拟記憶體的大小**受計算機尋址機制和可用的輔助存儲器容量大限制，而不受記憶體容量的限制。

  特征：①運作程序時隻把現在要執行的頁/段裝入記憶體，其餘頁/段放在外存，需要時再利用請求調入頁/段功能和置換功能将其調入記憶體。

  ②在邏輯上擴充記憶體容量

  ③通路速度接近于記憶體，沒位(bit)成本接近于外存。

• 虛拟位址：即邏輯位址，虛拟記憶體中某個位元組的位址，仿佛該位元組在記憶體中（其實可能位于磁盤，但這對使用者是透明的）。
• 虛拟位址空間：配置設定給某個程序（程式）的虛拟位址範圍。
• 實位址：即實體位址。實體記憶體中某個位元組的位址。
• 駐留集：程序運作時裝入記憶體的部分。
• 工作集：在 t 時刻，程序在過去的N個時間機關内通路的頁面集合(活躍頁面)

• 記憶體管理單元MMU：內建在CPU中，或作為一個協處理器。

  功能：分解邏輯位址；邏輯位址到實體位址的轉換；查找更新快表TLB；程序切換時清空TLB；發出缺頁中斷或越界中斷；設定和檢查頁表中各個特征位等。

!#當通路一個不再記憶體的邏輯位址時，産生缺頁中斷/缺段中斷；OS阻塞該程序；啟動磁盤I/O；裝入所需的頁/段後，将阻塞程序設定為就緒态。

?#就緒挂起态和阻塞挂起态程序的換入/換出記憶體和虛拟存儲的換入/換出記憶體有什麼差別？

答：挂起态程序的所有記憶體駐留頁/段全部被換出，解除挂起時，所有以前的駐留頁/段再重新讀回記憶體。且CPU不會排程就緒挂起态程序。

虛拟記憶體将任一程序（運作态。就緒态和阻塞态）的部分頁/段換入和換出記憶體。

二、分頁

虛拟頁式管理中的頁表：

缺頁中斷（頁錯誤）Page Fault：

- 在一條指令執行期間，當要範圍的頁不在記憶體是，産生和處理缺頁中斷，然後重新執行該指令。

- 一條指令的執行可能會引起多次缺頁中斷。

2.1虛、實位址轉換

• 虛拟位址<頁号，頁内偏移> ——>實位址<頁框号，頁内偏移>

  

2.2兩級頁表

• 兩級頁表中的位址轉換

2.3 倒排頁表（反置頁表）

• 倒排頁表為記憶體的每一頁框設定了一個頁表項。
• 内容為該幀所屬程序辨別和頁号（<-pid,page>)
• 簡單倒排頁表：

  

• 利用哈希函數的倒排頁表

  對虛拟位址的<-pid,page#>用哈希函數映射到散列鍊中。具有相同哈希值的表象被鍊在一起，可減少收縮時間。

  

2.4 TLB（快表）

轉換檢測緩沖區TLB，也稱快表。為了解決上述頁式記憶體管理帶來的每次通路資料都需要通路兩次記憶體的低效率問題。

- 将頁表中程序運作最常用的部分放入TLB。

- TLB內建與CPU内部的MMU中。（TLB不同于Cache）

- 位址轉換時：

①若要通路的頁号位于TLB，則從TLB中取出幀号。

②否則從記憶體中的頁表取出幀号，且添加到TLB中。

③當TLB滿時，淘汰舊表項，在寫入新表項。

!#若TLB缺頁時，會從記憶體的頁表找到指定幀号并送入TLB中，再由TLB傳入記憶體。即

- 5頁尺寸

• 業内碎片：頁越小，碎片雖小。
• 頁表長度：頁越大，頁表越大。
• 磁盤開銷：頁越大，磁盤I/O開銷越小。
• 記憶體容量和程式大小：記憶體越大，頁也可以越大。

• 程式局部性：

  ①頁越小，局部性越好，且可以裝入更多的頁，缺頁率低。

  ②頁增大時，局部性被削弱，缺頁率增加。當繼續增大頁則缺頁率降低。

  

三、分段

• 以段為機關配置設定記憶體及内外存交換。段不等長。
• 當發生缺段中斷時，可能需要移動或淘汰多個段才能滿足新段的需要。
• 每個程序一張段表。段表結構：

  

-駐留位：該段是否在記憶體中。

-修改位：該段裝入記憶體後是否被修改過。

-通路字段：訓示最近被通路次數或距上次通路的時間間隔。

-存取權限：本段的存取權限是可寫、隻讀或執行。-擴充位：訓示此段是否可動态增長。越界時如果該段不可擴充則出錯，否則增加段長并配置設定下方空閑記憶體。

四、段頁式

• 使用者程式劃分為段，段再劃分為大小相等的頁。
• 記憶體劃分和頁同樣大小的這女（頁框），以幀為機關離散配置設定記憶體。每段最後一頁有内碎片。無碎片。
• 邏輯位址結構：

  

• 段頁式位址轉換：

  

4.1保護共享

簡單分段和虛拟分段易于保護和共享。

• 存取權限：隔斷有執行、讀、寫等權限。
• 位址轉換通過各自的段表進行，防止越界。
• 共享段再多個程序段表的起址和長度相同

？#在這些存儲管理方法中：簡單頁式，簡單段式，虛存頁式，虛存段頁式，虛存段式，動态分區，固定分區

固定分區支援多道程式設計，算法簡單，但内碎片多；

态分區無無内碎片，但用于外碎片的壓縮處理時間長；

頁式克服克服了碎片多和壓縮處理時間長的缺點，但不支援虛拟記憶體；

虛拟頁式支援虛拟存儲，離散配置設定記憶體，無外碎片，但不能以自然的方式提供記憶體的共享和存取保護機制；

易于共享易于共享保護，記憶體碎片多，支援虛拟記憶體。

易于共享保易于共享保護，記憶體碎片少，支援虛拟記憶體。

五、虛拟記憶體的實作政策

CPU必須支援分頁和分段，才能實作虛拟記憶體。

虛拟存儲管理需考慮的問題：

• 讀取政策：某一頁何時調入記憶體（請求調入/預調入）
• 置換政策：選擇哪一頁換出記憶體（FIFO/LRU等）。
• 駐留集管理：給程序配置設定多少幀（固定/可變幀數），置換時犧牲誰的幀（全局置換/局部置換）
• 清除政策：何時将髒頁寫回磁盤（請求清除/預清除）。
• 加載控制：調整系統并發度，防止抖動。

5.1讀取政策

請求調入：僅把需要通路的頁調入記憶體；

- 調入：：考慮到啟動磁盤的尋道和延遲開銷，在調入所需頁的同時，也調入若幹可能馬上通路的頁面(通常是所需頁的後面幾頁)。

5.2放置政策

程序的頁/段放在記憶體哪個位置：

- 頁：離散放在記憶體任意幀；

- 段：首次/下次/最佳适配等算法配置設定

5.3置換政策

當記憶體所有幀都已被配置設定、又必須裝入一個新頁時，選擇在記憶體的哪一頁被置換出記憶體。

政策目的：基于局部性原理，根據程序過去的通路行為預測将來通路的行為，置換那些最近一段時間内最不可能通路的頁。

算法：

• 最佳置換（OPT）

  淘汰永不再使用或下次通路距目前時間最長的頁面。 （最佳，但不可能實作。用于衡量其他置換算法性能）

  

• 最近最少使用（LRU）

  淘汰在最近一段時間内最久未使用的一頁。

  實作：可為每頁添加“上次通路時間戳”。開銷大

  

• 先進先出（FIFO）

  淘汰駐留記憶體時間最久的一頁。

  實作：将頁面按調入記憶體的時間先後排成一個隊列，每次淘汰對首頁。性能差

  

• 時鐘（Clock）

簡單時鐘算法

- 每個頁表項設一個使用位：

- 某程序的所有頁面(或整個記憶體的頁框)排成一循環緩沖鍊；某頁被裝入或通路時，其使用位U置1；

- 置換時順序查找循環鍊：U=0，置換該頁；U=1，将U置0；替換指針前移。下次置換時從替換指針處開始查找。

缺頁率性能優劣遞減：OPT>LRU>CLOCK>FIFO

時鐘算法改進

每個頁表項設定“使用位U——修改位M”，通路某頁時U置1；被修改時M置1。

① U=0，M=0 (最佳淘汰頁) 最近未通路，且從未修改

② U=0，M=1 最近未通路，但曾被修改

③ U=1，M=0 最近被通路，但從未修改

④ U=1，M=1 (最不該淘汰) 最近被通路，且曾被修改

淘汰順序優先級：①②③④

5.4駐留集管理

• 為程序配置設定主存時：

  -每個程序的幀越少，記憶體中程序就越多，并發度越高。

  -如果程序隻有小部分在記憶體裡，缺頁率會相當高。為程序增加一些記憶體幀将降低缺頁率。

  -當分給程序的記憶體幀超過一線限度後，繼續增加幀，也不會明顯亮度程序的缺頁率。

• 配置設定給一哥程序的幀最小數量：至少一哥指令要用到的頁應該同時在記憶體。

5.4.1 缺頁率

• 缺頁率 = 不成功通路次數/總通路次數
• 達到“可接受的”缺頁率
  • 如果缺頁率太高，将增加程序幀數
  • 如果缺頁率态度，将減少程序幀數

    

    

5.4.2 頁面配置設定

• 固定配置設定：程序分得的頁框數固定不變。
• 可變配置設定：根據缺頁率，程序分得的頁框數可動态增加或減少。

5.4.3置換範圍

• 局部置換：每個程序隻從它自己的已配置設定幀中選擇置換幀。
• 全局置換：程序在整個記憶體範圍内選擇置換幀。

5.4.4清除政策

• 請求式清除：僅當需要換這個髒頁時把它寫回，之後再調入新頁。
• 預約式清除：即使還不需要置換髒頁，也呈批地把他們寫回（例如當磁盤空閑或髒頁達到一定數量時，可降低磁盤I/O開銷。）

5.4.6加載控制

- 抖動：當系統并發度過高，缺頁頻繁，用于調頁的時間比程序實際運作時間還多，CPU使用率急劇下降，成為抖動。

- 采取哪些措施可以預防抖動？

①在排程程式中引入工作集算法：當各程序的記憶體駐 留集足夠大時，才調入新作業

②L=S準則：調整并發度，使得産生缺頁的平均時間 (即缺頁中斷之間的平均時間)等于處理一次缺頁中 斷的平均時間，此時CPU使用率高。

③ 50%準則：磁盤使用率50%時，CPU使用率高。

④當系統并發度較高時，挂起若幹程序（如優先級低 的、年輕的、發生缺頁的、占空間少的、占空間 多的、剩餘運作時間長的程序）。