第二十一天 Virtual Memory(虛擬記憶體)--(一)

今天要講的虛擬記憶體，騎士也是記憶體管理的一部份，但因為比較多重點，所以多一個章節出來講述。
先來說說他的背景，先前提過基本上邏輯跟實體記憶體空間是一樣大，但實際上實體記憶體空間的大小不一定，可能會小一點，但如果跑的程式比較大，這時就會需要虛擬記憶體的幫助。虛擬記憶體是讓程式以為有連續的記憶體空間可以使用，但事實上有些會存放在disk上，當有需要時再交換進來，因為程式在執行時，並不是所有的code都會用到，所以可以將某部分放到virtual memory中。以下有參考圖：

Virtual memory的好處：

1. 部分program在記憶體中執行即可，其餘的部分可以給其他program執行，提高CPU的效率
2. Logical address space的空間會因此大於physical address space
3. 記憶體空間可以和許多process共享，提高process的輸出
4. 較少的I/O要load或是要把process搬上搬下
   Virtual address space是以logical的觀點看process如何存放在記憶體，而virtual memory的實作方式有兩種，demand paging跟demand segmentation。

Demand paging：

如同他的名字一般，是以paging為基礎來應用，這個方式是使用lazy swapper的方法，當page被需要時，才把page swap進去，而這個是由pager所決定的。簡單來說，process在執行前，pager會先猜測process會用到哪些page，然後只載入那些page。

在demand paging裡的page table，會加入一個valid-invalid bit的值，來確認page是不是在memory內(因為有些page或許是中途才需要，或是一開始pager並沒有猜測到)。如果有在記憶體內，則valid-invalid bit的值設為v，沒有則設為i，初始直接設為i。如果要經過MMU轉換時，還是i就會發生page fault。以下有張參考圖：

Page fault發生的處理方式：

1. 作業系統會先去確認其他的table，決定這是一個無效的參考，還是單純不在記憶體內。如果是無效的參考，會直接砍掉處理; 單存不在記憶體內則執行第二步
2. 找到一個free frame
3. 通過disk管理的安排swap進入free frame
4. 將table的valid-invalid bit的值標示為valid
5. 繼續執行因為page fault出錯的指令
   以下是他的執行圖：
   
   如果一開始執行process時，沒有任何一個page存在於memory中，那就會一直發生page fault，一直到frame滿了會恢復正常。這種就叫做pure demand paging，他沒有任何預測的動作，只有在需要page時才會載入記憶體內。
   還有當給一個指令執行存取多個page時，有可能會發生多個page fault，這時可以運用locality of reference，他是當有一個page被存取時，附近的資料也會很快被存取，類似物以類聚的概念，相似的page一定都在附近。

而demand paging的有效運用時間，由以下公式可以計算出來：

Effective Access Time(EAT) = (1-p) x memory access + p(page-fault service time)
p代表page fault的機率

例如：
記憶體存取時間為200 nanoseconds
平均page fault處理時間為8 milliseconds
p ＝ 1/1000
EAT ＝ (1-1/1000) x 200 + 1/1000 x 8000000 = 8.2 microseconds
這對記憶體來說效率並不好，因為page fault發生的機率太高了！

剩下的我們明天繼續！！