09. 虛擬記憶體 (Virtual Memory)

虛擬記憶體 (Virtual Memory)

 

(一) 背景

虛擬記憶體是電腦系統記憶體管理的一種技術。它使得應用程式認為它擁有連續的可用的記憶體(一個連續完整的位址空間),而實際上,它通常是被分隔成多個實體記憶體碎片,還有部分暫時儲存在外部磁碟記憶體上,在需要時進行資料交換。與沒有使用虛擬記憶體技術的系統相比,使用這種技術的系統使得大型程式的編寫變得更容易,對真正的實體記憶體(例如RAM)的使用也更有效率。

 

(二) 分頁需求

需求分頁法就像一種使用置換法的分頁系統。行程存放在輔助記憶體(通常是磁碟中),當要執行某個行程的時候,就把那個行程置換至記憶體中。但是,並不是把整個行程都置換進來,而是使用一個懶惰置換程式。懶惰置換程式只有當需要某一頁的時候才把該頁置換進來。

 

 

 

(三) 寫入時複製

 
Copy-on-Write (COW) allows both parent and child processes to initially share the same pages in memory
 
If either process modifies a shared page, only then is the page copied
 
COW allows more efficient process creation as only modified pages are copied
 
Free pages are allocated from a pool of zeroed-out pages
 

fork時並不複製資料分頁,直到寫入時才複製

 

(四) 分頁替換

4.1 分頁替換介紹

若主記憶體內沒有空的框可以用時,我們可以找一個暫時不用的分頁,將其清除,供目前需求分頁使用。


4.2 FIFO分頁置換法

 

最簡單的頁替換演算法。

 

 

 

當要替換一頁時,我們就去選擇存在記憶體內最久的一個分頁,也就是最早被載入記憶體內的分頁,將它換掉,並載入所需求的分頁。可透過FIFO的佇列來掌握在記憶體中的所有頁。

 

舉例:
 

 

 

 

參考頁面編號

1

2

1

3

5

1

0

5

2

1

5

1

 

1

1

1

1

5

5

5

5

2

2

2

2

 

2

2

2

2

1

1

1

1

1

5

5

 

 

 

3

3

3

0

0

0

0

0

1

 

 

 

 

 

一共發生9次的分頁錯誤

 

 

 

 




4.3 最佳頁替換

是所有演算法中分頁錯誤比率最低的一種。當要替換一頁時,把未來最長時間之內不會被用到的那一頁替換掉。

舉例:

 

參考頁面編號

1

2

1

3

5

1

0

5

2

1

5

1

 

1

1

1

1

1

1

0

0

0

1

1

1

 

2

2

2

2

2

2

2

2

2

2

2

 

 

3

5

5

5

5

5

5

5

5

5

 

 

 

 

 

一共發生6次的分頁錯誤

 

 

 

4.4 LRU頁替換 (Least recently used page-replacement)

 

 

 

LRU 演算法的表現不錯,但是由於必須依靠特殊的硬體支援,很少系統能夠完整地實作。當要替換一頁時,把過去到現在最久時間未使用的那頁替換掉。

 

 

 

舉例:

 

 

 

 

 

參考頁面編號

1

2

1

3

5

1

0

5

2

1

5

1

 

1

1

1

1

1

1

1

1

2

2

2

2

 

2

2

2

5

5

5

5

5

5

5

5

 

 

 

3

3

3

0

0

0

1

1

1

 

 

 

 

 

一共發生7次的分頁錯誤

 

 

 

 

 

 

 

4.5 LRU近似換頁法 

 由於很少電腦能夠提供足夠的硬體來支援真正的LRU頁替換,而LRU近日換頁法是一種以「參考位元」的方式來執行分頁替換的方法,利用參考位元來記錄過去使用過哪些分頁;雖然無法知道被使用的先後次序,但知道哪些被使用過而哪些還沒被使用。這種部分排班資訊可使許多分頁替換演算法盡量接近LRU替換法。

4.6 計數基礎頁替換法

最不經常使用的法則 (LFU):最不經常使用的 (least frequently used, LFU)演算法讓次數最少的那一頁被替換掉。

最常使用的法則(MFU):最常被使用的 (most frequently used, MFU) 替換法認為次數最少的頁可能才被載入不久並且將要被使用。

4
.7頁緩衝法

每當分頁用的裝置閒置了之後,就選出曾經被修改過的一頁並將它寫入磁碟中。該頁的修改位元就被重置為0。

這個方法可以增加我們要做替換時任選一頁出來而其為未被修改過的機率,而且不需要寫出。

4.8    應用程式和分頁替換

應用程式經由作業系統的虛擬記憶體存取資料,則較如果作業系統全然不提供緩衝表現地更差。一個典型的例子,一個資料庫提供它自己的記憶管理和輸出入緩衝。像這樣的應用程式瞭解他們的記憶體使用與磁碟使用比一般用途製作演算法作業系統來的好。如果作業系統正在緩衝輸出入,而且應用程式也正在這麼做,那麼對一組輸出入使用兩次記憶體。

在另一個例子,資料倉庫時常表現大量的序列磁碟讀取,接著計算以及寫入。LRU演算法則將會除去舊的分頁而且保存新的分頁,雖然應用程式更有可能訊取較舊的分頁。(當再一次的序列讀取)。在這異,MFU實際上將會比LRU有效率。

 

 

 

 

 

 

(五) 欄的配置法則 Allocation of Frames

5.1 最少量的欄數(Minimum Number of Frames)
 
配置最少量的欄數其中一個理由是性能。
當分配給每個行程的欄數減少之後,分頁錯誤比率就會增加,而減緩行程的執行。要記著當一個分頁錯誤在一項指令執行完畢之前發生的話,這個指令就必須重新執行一次。
 
5.2 配置演算法(Allocation Algorithms)
 
將用m個欄分給n個行程的最簡單方法就是令每個行程都能分到一樣多的m/n個欄。舉例來說,如果有93個欄和5個行程,那麼每個行程可以分到 18個欄。剩下的3個欄可以當做一個空白欄緩衝區的庫存。這就稱為同等分配(Equal Allocate)。
 
使用比例分配(Proportional Allocation)。每個行程分配可用記憶體時可以按照它的大小分配。令行程pi的虛擬記憶體大小為si並且定義S=Σ si ,那麼如果可用欄的總數是m,我們分配ai個欄給行程pi其中ai近似約為ai=(si/S)×m
 
Fixed Allocation 
 
5.3  全體和區域的配置(Global versus Local Allocation)
 
另外一種影響分配給不同行程時所採用方法的重要因素是頁替換。在許多行程競爭欄數時,可以把頁替換法分成兩大類:全體替換法 (global replacement)和區域替換法 (local replacement)。全體替換法允許一個行程從所有欄數中選出一個替換,即使目前該欄正分配給其它某個行程使用中;換言之,一個行程可以從其它行程獲得一欄區域替換法要求每一行程只能從它自己選出欄。
 
 
5.4 不一致的記憶體存取(Non-Uniform Memory Access)
 
在一個系統中,某個特定板上的CPU存取同塊板上記憶體的延遲時間比存取其他板上的記憶體來的短。凡是記憶體存取時間有很大差別的系統,其統稱為不一致的記憶體存取(NUMA)系統。
 
有系統的規則改變,包含了使排班器去追蹤在每個行程執行上最後的CPU。如果排班器試圖將每個行程排進以前的CPU,那麼記憶體管理系統試圖配置欄給接近被排班的CPU的行程,然後將會有提高快取命中率和降低記憶體存取時間的結果。
 
 
 

(六) 輾轉現象 Thrashing

9.6.1 原因

如果CPU利用率太低,我們就藉由一個新行程來增加多元程式規劃的程度。這些新的行程從其他正在執行的行程中搶一些頁來開始工作,但這樣又造成更多的分頁錯誤,以及更長時間等待,結果,CPU的使用率又更降低了。輾轉現象已經出現並且使得系統的產量突然下降。因為行程把所有時間都花在分頁上,最後什麼工作也沒完成。

假設我們分配足夠的欄給某行程以提供他目前的局部區域,他會因為這些在這個局部區域中但未存入記憶體的頁而產生分頁錯誤,但當這些頁已存入記憶體中,除非更改局部區域,否則不會有分頁錯誤出現。如果無法分配出足夠的欄提供目前局部區域的大小,就會因為無法將他所要的頁存入記憶體中而產生輾轉現象。

 

9.6.2 工作組模式(Working-Set Model)

是基於局部區域的假設而設定的。裡面有一個參數 △ ,來定義工作組欄框(working-set window)。在最近 △ 頁參考中的頁所組成的就是工作組(working-set)。

工作組的精確度依 △ 而定,太小,將無法包含整個工作組;太大,則會重疊許多部分。

工作組最重要的性質就是其大小。如果要計算每個行程的工作組大小 WSSi ,可寫成 :

D = Σ WSSi

D是對欄的需求。每個行程實際在使用的是在工作組的頁。如果總需求量比可用的欄數大(D > m),則會產生輾轉現象。

 

9.6.3 分頁錯誤頻率

工作組模式(Working-Set Model)是非常有用的,而了解工作組模式會對預先分頁相當有幫助。但卻是用來控制輾轉現象相對較笨拙的方法,分頁錯誤頻率(page-fault frequency,PFF)則是更直接的方法。

輾轉現象有高分頁錯誤率,因此,我們要去控制住分頁錯誤率。當他太高時,就可以得知需要更多的欄,就把另一個行程的欄分給該行程;同樣地,如果太低,就表示該行程擁有太多欄,所以移走一個欄。因此可以直接測量與控制分頁錯誤率以防止輾轉現象的發生。

(七) 記憶體對映檔案 Memory-Mapped Files

想使用標準系統呼叫 open(), read(), write() 對磁碟上檔案執行循序讀取,每次被讀取時需要一次系統呼叫和一次磁碟的存取,取而代之的是,可以使用目前所討論的將檔案 I/O視為經常性的記憶體存取。這就稱為記憶體對映(Memory-Mapped)。

9.7.1 基本功能

記憶體對映檔案是由對映磁碟區段到記憶體分頁達成。對於檔案第一次存取是使用一般的需求分頁進行,並造成分頁錯誤,然而,一個分頁大小的檔案部分從檔案系統讀入到實體分頁隨從對檔案的讀寫被當成一般記憶體存取,因為檔案處理經由記憶體,而非 read(), write() ,所以簡化了檔案的存取與使用。

寫入記憶體中的檔案對映時,可能不需要立即寫入磁碟上的檔案,有些系統可能會選擇在作業系統週期性檢查記憶體中對映檔案分頁是否被修改時,更新實際的檔案。關閉檔案時會造成所有記憶體對映的資料都被寫回磁碟,並從行程中的虛擬記憶體中移除。

 

9.7.2 Shared Memory in the Windows API

在 Windows API 產生一個使用記憶體對映檔案的共同記憶體區域,首先產生一個為對映的檔案用來對映檔案(file mapping),然後在行程的虛擬位址空間建立對映的 view。第二個行程在他的虛擬位址空間開啟與產生對映檔案的view,對映檔案表示共同記憶體物件能在行程之間相互通訊。

為了建立記憶體對映檔案,行程以 Createfile() 開啟被對映的檔案,歸還 HANDLE 給被開啟的檔案。然後用 CreateFileMapping() 產生 HANDLE 的對映,一旦建立對映的檔案,以 MapViewOfFile() 在他的虛擬位址空間建立映對檔案的view。
9.7.3 Memory-Mapped I/O

通常,特殊的I/O指令讓資料在暫存器與記憶體之間轉移,為了讓存取更方便,許多電腦架構提供記憶體映對I/O(memory-mapped I/O)。記憶體位址的範圍被留存,而且映對到暫存器,這些記憶體位址的讀寫使資料在暫存器間來回轉移,適合有快速回應的裝置。

為了經由記憶體映對序列送出長位元字串,CPU寫入資料位元到暫存器中,並在控制暫存器中設定一個位元表示是可以使用的,裝置讀取資料位元,然後清除在控制暫存器中的位元,表示他為下一位元組做好準備,CPU 能轉移下一個位元。這稱為可編程I/O(programmed I/O),如果中央處理器不登記控制位元,當裝置位下一個位元組做好準備時,改為接受一個interrupt,此稱為中斷驅動式(interrupt driven)。

(八) 核心記憶體的配置

 

9.8.1 Buddy System

  1. 夥伴系統的一個優點是利用一種稱為合併(coalescing)的技巧,可以將毗連的夥伴聯合形成更大的區段。舉例來說,在圖9.26中當核心釋放配置的CL,單位,系統能合併 CL和 CR  成為一個64KB的區段。區段BL能繼續與它的夥伴BR一起合併形成一個 128KB的區段。最後,我們能以最初的256KB的區段作為結束。

9.8.2 Slab Allocation

  1. 配置核心記憶體的第二個策略稱為平版配置(slab allocation)。平板由一個或更多個實體連續分頁組成。一個快取 (cache)由一個或更多個平板所組成。

 

(九) 其他的考慮因素

 

9.9.1  Prepaging

  1. 在純需求分頁系統中的一項明顯特徵就是當一個行程開始執行的時候就會出現一大堆分頁錯誤。這個情況乃是因為嘗試要將起始局部區域 (initial locality)載入記憶體所造成的。相同的事情可能在其它時間發生。例如,當一個被置換出去的行程想要重新啟動的時候,它所有的頁都存在備用儲存體中並且必須藉著各個分頁錯誤才能把所有的頁都載入記憶體。
  2. 預先分頁 (prepaging)就是想要防止這種高度的起始分頁。其策略就是把所有需要的頁在同一時間都載入記憶體中。有些系統 (特別是 Solaris)為較小檔案預先分頁其分頁欄。

9.9.2  Page Size

  1. 對於現有機器的作業系統設計師來說,他們很少有能力對分頁大小做選擇的標會。但是,當我們要設計新機器的時候,我們就必須對於最佳頁的大小做一個決定。
  2. 有些因素 (內部斷裂,局部區域)贊成使用較小的頁,然而其它因素 (表格大小,VO時間)則T成使用較大的頁

9.9.3  TLB Reach

  1. 和擊中率(hit ratio)相關的是一個相似的量尺:TLB範圍(TLB reach)。TLB範圍是指TLB可以存取的記憶體數量,而且只是TLB的項數乘上分頁的大小。理想上,一個行程的工作組是存放在TLB中。如果不是的話,此行將花費可觀的時間去解決分頁表 (而非TLB)的記憶體參考。

9.9.4  Inverted Page Table

 

  1. 這種分頁管理格式的目的是為了減少實禮記憶體的數量,它必須知道虛擬對貫體的記檔體位址轉換。藉由設立具有每一個實體記憶體分頁項的表,可以達成節省的目的,而它是用(Process-id, page-number)作指標。在每一個實體欄位中,可以藉由保存關於虛擬記憶體分頁的資訊之方法來儲存它。反轉分頁表可以大量地減少儲存這些資訊所需的實體記憶體。不論如何,假如參考的分頁不能經常在記憶體之中時,反轉分頁表不再含有關於行程的遠輯位址空間的完整訊息是必須的。

9.9.5  Program Structure

 

  1. 需求分頁(demand paging)被設計為對使用者程式來說十分簡明的型式。如果能對基本的需求分頁有所瞭解的話,將會對系統的性能上有很大的幫助。

 

9.9.6  I/O Interlock and Page Locking

  1. 當我們使用需求分頁法的時候,有時候需要使它的某些頁被鎖 (locked)在記憶體中。其中一種情況就是和使用者 (虛擬)記憶體有關的I/O。I/O經常是由一個獨立的I/O處理程式來執行。舉例來說,我們一般必須給予磁帶控制器我們所要轉移的文字 (或位元組)數量以及緩衝區在記憶體中的位址 (圖9.28)。當轉移工作做完之後,CPU就被中斷了。

 

 

 

 

(十) 摘要

 

虛擬記憶體是一種允許將大型邏輯位置空間映射到較小實體記憶體空間的技術。這項技術讓我能執行非常大的行程,
增加CPU使用率。
虛擬記憶體普遍被需求分頁製作。首次參考會對作業系統常駐程市產生一個分頁錯誤。作業系統就常尋一個內部表格
找出該頁在備用儲存體的確實位置。然後找一一個空白欄然後將該頁從備用儲存體讀入。分頁表將被更新。
這種方法允許一個行程即使他整個記憶體映射不是在完全在主記憶體中也可以被執行。只要分頁錯誤率低於某個合理的程度就可以被接受。

 

如果記憶體的一切要求超過實體記憶體的容量,那就需要重記憶體中替換掉一些頁。我們使用一些方法像是
FIFO,最佳分頁替換法,LRU演算法。