虛擬記憶體的實作需要建立在離散分配的記憶體管理方式的基礎上,實作方法有3種:1、請求分頁儲存管理方式;2、請求分段儲存管理方式;3、段頁式儲存管理方式。不管哪種方式,都需要有一定的硬體支援:1、一定容量的記憶體和外存;2、頁表機制(或段表機制),作為主要的資料結構;3、中斷機構,當使用者程式要訪問的部分尚未調入內存,則產生中斷;4、地址變換機構,邏輯地址到物理地址的變換。
本教學操作環境:linux7.3系統、Dell G3電腦。
傳統儲存管理方式同時將多個進程保存在記憶體中以便允許多道程式設計。它們都具有以下兩個共同的特徵:
- #一次: 作業必須一次全部裝入記憶體後,方能開始運作。這會導致兩種情況發生:
1)當作業很大,不能全部裝入記憶體時,將使該作業無法運行;
2)當大量作業要求運行時,由於記憶體不足以容納所有作業,只能使少數作業先運行,導致多道程序度的下降。- 駐留性: 作業被裝入記憶體後,就一直駐留在記憶體中,其任何部分都不會被換出,直至作業運行結束。運行中的進程,會因等待 I/O 而被阻塞,可能處於長期等待狀態。
因此,許多在程式運行中不用或暫時不用的程式(資料)佔據了大量的記憶體空間,而一些需要運行的作業又無法裝入運行,顯然浪費了寶貴的內存資源。
1.1 虛擬記憶體的定義與特徵
#基於局部性原理,在程式裝入時,可以將程式的一部分裝入記憶體,而其餘部分留在外存,就可以啟動程式執行。在程式執行過程中,當所存取的資訊不在記憶體時,由作業系統將所需的部分調入記憶體,然後繼續執行程式。另一方面,作業系統將記憶體中暫時不使用的內容換出到外記憶體上,從而騰出空間存放將要調入記憶體的資訊。
這樣,由於系統提供了部分裝入、請求調入和置換功能後(對用戶完全透明),給用戶的感覺是好像存在一個比實際實體記憶體大得多的記憶器,稱為虛擬記憶體。
虛擬記憶體的大小由電腦的位址結構決定,並非是記憶體和外存的簡單相加。
虛擬記憶體有以下三個主要特徵:
1.2 虛擬記憶體技術的實作
虛擬記憶體中,允許將一個作業分多次調入內存。
釆用連續分配方式時,會使相當一部分記憶體空間都處於暫時或「永久」的空閒狀態,造成記憶體資源的嚴重浪費,也無法從邏輯上擴大記憶體容量。
因此,虛擬記憶體的實作需要建立在離散分配的記憶體管理方式的基礎上。虛擬記憶體的實作有以下三種方式:
硬體支援。一般需要的支援有以下幾個面向:
連續分配方式:指為一個使用者程式分配一個連續的記憶體空間。
- 固定分區分配:將記憶體空間劃分為若干個固定大小的區域,在每個分區中只裝入一道作業,便可以有多道作業並發執行。缺乏彈性,會產生大量的內部碎片,記憶體的利用率很低。
- 動態分割區分配:根據進程的實際需要,動態地為之分配記憶體空間。作業裝入記憶體時,把可用記憶體分出一個連續區域給作業,且分區的大小剛好適合作業大小的需要。會產生很多外部碎片。
離散分配方式:將一個行程分散地裝入到許多不相鄰的分區中,便可充分地利用記憶體。
分頁儲存的概念:
- 頁、頁框和區塊。 進程中的區塊稱為頁或頁面(Page),具有頁號;記憶體中的區塊稱為 頁框(Page Frame,頁框=記憶體區塊=物理區塊=物理頁面),具有頁框號。 外部記憶體也以相同的單位劃分,直接稱為區塊(Block)#。進程在執行時需要申請主存空間,就是要為每個頁面分配主記憶體中的可用頁框,這就產生了頁和頁框的一一對應。各頁不必連續存放,可以放到不相鄰的各頁框中。
- 位址結構:前一部分為頁號P,後一部分為頁內偏移量W。位址長度為32 位,其中0~11位為頁內位址,即每頁大小為4KB;12~31位為頁號,位址空間最多允許有2^20頁。
- 頁表。為了方便在記憶體中找到進程的每個頁面所對應的實體區塊,系統為每個行程建立一張頁表,記錄頁面在記憶體中對應的實體區塊號,頁表一般存放在記憶體中。在配置了頁表後,進程執行時,透過尋找該表,即可找到每頁在記憶體中的實體區塊號。可見,頁表的作用是實作從頁號到實體區塊號的位址對映。
## 請求分頁是目前最常用的一種實作虛擬記憶體的方法。
請求分頁系統建立在基本分頁系統基礎之上,為了支援虛擬記憶體功能而增加了請求調頁功能和頁面置換功能。
在請求分頁系統中,只要求將目前需要的一部分頁面裝入內存,便可以啟動作業運行。 在作業執行過程中,當所要存取的頁面不在記憶體時,再透過調頁功能將其調入,同時還可以透過置換功能將暫時不用的頁面換出到外存上,以便騰出記憶體空間。
一定容量的記憶體及外存的電腦系統,還需要有頁表機制、缺頁中斷機構、位址轉換機構。
2.1 頁表機制
請求分頁系統的頁表機制不同於基本分頁系統,請求分頁系統在一個作業運作前不要求全部一次性調入記憶體。 因此在作業的運作過程中,必然會出現要存取的頁面不在記憶體的情況,如何發現和處理這種情況是請求分頁系統必須解決的兩個基本問題。為此,在請求頁表項中增加了四個字段,分別為:頁號 | 物理區塊號 | 狀態位元P | 存取欄位A | 修改位元M | 外記憶體位址 |
#訪問頁面 | 7 | ##0#1 | 2 | 0 | 3 | 0 | ##4 | ##2#3 | 0 | 3 | 2 | 1 | 2 | 0 | ## 1 | 7 | 0 | 1 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 7 | 2 | #2 |
2 |
2 |
2 |
#7 |
|||||||||||||
#0 | 00 | 0 |
4 |
|
0 |
#0 |
|
0 |
||||||||||||
1 | 1##3 | |
3 |
#缺少頁否 |
||||||||||||||||
##√ |
√ |
√ |
√ |
|
#√ |
√ |
可以看到,發生缺頁中斷的次數為9,頁面置換的次數為6。
3.2 先進先出(FIFO)頁面置換演算法
#優先淘汰最早進入記憶體的頁面,亦即在記憶體中駐留時間最久的頁面。
此演算法實作簡單,只要把調入記憶體的頁面依照先後次序連結成佇列,設定一個指標總是指向最早的頁面。但該演算法與進程實際運行時的規律不適應,因為在進程中,有的頁面經常被存取。
存取頁面 | 7 | ##0 | 1 | 2 | 03 | 0 | #4 | 2 | 3 | 0 | 3 | 2 | 1 | # 2 | 0 | 1 | 7 | 0 | 1 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 7 | 7 | 2 | 2 | 4 | 44 | 0 | |
0 | 7 | 7 | |||||||||
0 | 0 | 3 |
##3 | #3 2 | 2 |
2 |
1 | #1 | ||||||||||||
1 | #00 |
物理區塊3 |
#1 | ##11 |
0 |
0 |
#0 | ##3##3 | #3 | 2 | ||||||||||
2 | 2 | 1 | 缺少頁否 ##√ | ##√#√ | √ | √ | #√ | ##√##√ |
##√ | ##√ | √ |
利用FIFO演算法時進行了 12 次頁面置換,比最佳置換演算法正好多一倍。
FIFO演算法也會產生當所分配的物理區塊數增加而頁故障數不減反增的異常現象,這是由 Belady於1969年發現,故稱為Belady異常,如下表所示。
存取頁面 | 1 | 2 | #3 | 4 | #1 | 2 | 5 | 1 | 2 | #3 | 4 | 5 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
物理區塊1 | 1 | #1 | 1 | ##4#4 | 4 | 5 | #5 | |||||
##2 | 2 | 1 | 1 | 1 |
#3 |
3 | ||||||
3 |
3 | 3 | 2 | #2 |
2 |
4 | ||||||
#√ | √ | √ | √ | √ | ##√ | √ | ||||||
1 | 1 | 1 | # 1 | #5 | 5 | 5 | 4 | 4 | ||||
#2 | 2 | ##1 | ##1#1 | 1 | 5 | 物理區塊3* | ||||||
3 | 3#3 ##3 | 2 | 2 | 2 | 2 | #物理區塊4* | ||||||
4 | 4 | 4 | 3 | 3 | #3 | |||||||
缺頁否 | √ | √ | √ | #√ | √ | √ | √ | √ | √ |
只有FIFO演算法可能出現Belady異常,而LRU和OPT演算法永遠不會出現Belady異常。
3.3 最近最久未使用(LRU)置換演算法
最近最久未使用(LRU,Least Recently Used )置換演算法選擇最近最長時間未訪問過的頁面被淘汰,它認為過去一段時間內未訪問過的頁面,在最近的將來可能也不會被訪問。
演算法為每個頁面設定一個訪問欄位,來記錄頁面自上次被造訪以來所經歷的時間,淘汰頁面時選擇現有頁面中位數最大的予以淘汰。
存取頁面 | 7 | 1 | 2 | 0 | 3 | 0 | #4 | 2 | 3 | 0 | 3 | 2 | 1 | # 2 | 0 | 1 | 7 | 0 | 1 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
物理區塊1 | 7 | 7 | 7 | 2 |
|
2 | 4 | #4 | 4 | #0 | 1 | #1 |
|
1 | ||||||
#物理區塊2 | 0 | 0 | 0 | #0 | 0 | 0 | 3 | 3 | 3 | 0 | 0 | |||||||||
物理區塊3 | 1 | ##1#3 | 2 | 2 | 2 | |||||||||||||||
# √ | √ | √ | √√ | √ | √ | √
LRU效能較好,但需要暫存器和堆疊的硬體支持,開銷更大。
LRU是堆疊類別的演算法。理論上可以證明,堆疊類別演算法不可能出現Belady異常。 FIFO演算法基於佇列實現,不是堆疊類別演算法。
3.4 時脈(CLOCK)置換演算法
LRU演算法的效能接近OPT,但是實作起來比較困難,且開銷大;FIFO演算法實作簡單,但效能差。所以作業系統的設計者嘗試了很多演算法,試著用比較小的開銷接近LRU的效能,這類演算法都是CLOCK演算法的變體。
簡單的CLOCK演算法是給每一幀關聯一個附加位,稱為使用位。當某一頁首次裝入主存,以及後續被存取時,使用位元被置為1。
對於頁替換演算法,用於替換的候選影格集合看做一個循環緩衝區,並且有一個指標與之相關聯。當某一頁被替換時,該指標被設定成指向緩衝區中的下一幀。
當需要替換一頁時,作業系統掃描緩衝區,以尋找第一個使用位元為0的一幀。每當遇到一個使用位元為1的訊框時,作業系統就會將該位元重新置為0;如果所有訊框的使用位元均為1,則指標在緩衝區中完整地循環一周,把所有使用位元都置為0,並且停留在最初的位置上,替換該幀中的頁。由於演算法會循環檢查各頁面的情況,故稱為CLOCK演算法,又稱為最近未用(Not Recently Used, NRU)演算法。
CLOCK演算法的效能比較接近LRU,而透過增加使用的位數目,可以使得CLOCK演算法更有效率。在使用位元used的基礎上再增加一個修改位元modified,則得到改進型的CLOCK置換演算法。
每一幀都處於以下四種情況之一:
最近未被訪問,也未被修改(u=0, m=0)。
最近被訪問,但未被修改(u=1, m=0)。
最近未被訪問,但被修改(u=0, m=1)。
最近被訪問,被修改(u=1, m=1)。
演算法執行以下操作步驟:
從指標的目前位置開始,掃描幀緩衝區。在這次掃描過程中,對使用位不做任何修改。選擇遇到的第一個幀(u=0, m=0)用於替換。
如果步驟1失敗,則重新掃描,找出(u=0, m=1)的訊框。選擇遇到的第一個這樣的幀用於替換。在這個掃描過程中,對每個跳過的幀,把它的使用位元設為0。
如果步驟2失敗,指標就會回到它的最初位置,並且集合中所有影格的使用位元均為0。重複第1步,並且如果有必要,重複第2步。這樣將可以找到供替換的畫面。
改良型的CLOCK演算法優於簡單CLOCK演算法之處在於替換時首選沒有變化的頁。由於修改過的頁面在被替換之前必須寫回,因而這樣做會節省時間。
4.1 駐留集合大小
對於分頁式的虛擬內存,在準備執行時,不需要也不可能把一個進程的所有頁都讀取到主存,因此,作業系統必須決定讀取多少頁。也就是說,給特定的程序分配多大的主存空間,這需要考慮以下幾點:
分配給一個行程的儲存量越小,在任何時候駐留在主記憶體中的進程數就越多,從而可以提高處理機的時間利用效率。
如果一個行程在主記憶體中的頁數過少,儘管有局部性原理,頁錯誤率仍然會相對較高。
如果頁數過多,由於局部性原理,給特定的進程分配更多的主存空間對該進程的錯誤率沒有明顯的影響。
基於這些因素,現代作業系統通常釆用三種策略:
#固定分配局部置換:它為每個進程分配一定數目的物理塊,在整個運行期間都不改變。若進程在執行中發生缺頁,則只能從該行程在記憶體中的頁面中選出一頁換出,然後再調入所需的頁面。實現這種策略難以確定每個程序應分配的實體區塊數目:太少會頻繁出現缺頁中斷,太多又會使CPU和其他資源利用率下降。
可變分配全域置換:這是最容易實現的物理區塊分配和置換策略,為系統中的每個程序分配一定數目的物理區塊,作業系統本身也保持一個空閒實體塊隊列。當某個行程發生缺頁時,系統會從空閒實體區塊佇列中取出一個實體區塊指派給該行程,並將欲調入的頁裝入其中。
可變分配局部置換:它為每個進程分配一定數目的物理區塊,當某進程發生缺頁時,只允許從該進程在記憶體的頁面中選出一頁換出,這樣就不會影響其他行程的運作。如果進程在運作中頻繁地缺頁,系統再分配若干物理塊給該進程,直至該進程缺頁率趨於適當程度;反之,若進程在運行中缺頁率特別低,則可適當減少分配給該行程的實體區塊。
4.2 調入頁面的時機
為確定係統將進程運行時所缺少的頁面調入內存的時機,可釆取以下兩種調頁策略:
#預調頁策略:根據局部性原理,一次調入若干個相鄰的頁可能會比一次調入一頁更有效率。但如果調入的一批頁面中大多數都未被訪問,則又是低效的。所以就需要釆用以預測為基礎的預調頁策略,將預期在不久後便會被造訪的頁面預先調入記憶體。但目前預調頁的成功率僅約50%。故這種策略主要用於進程的首次調入時,由程式設計師指出應該先調入哪些頁。
請求調頁策略:進程在運行中需要存取的頁面不在記憶體中提出請求,由系統將所需頁面調入記憶體。由這種策略調入的頁一定會被訪問,且這種策略比較易於實現,故在目前的虛擬記憶體中大多釆用此策略。它的缺點在於每次只調入一頁,調入調出頁面數多時會花費過多的I/O開銷。
4.3 從何處調入頁面
請求分頁系統中的外存分為兩部分:用於存放檔案的檔案區和用於存放對換頁面的對換區 。 對換區通常是釆用連續分配方式,而檔案區釆用離散分配方式,故對換區的磁碟I/O速度比檔案區的更快。這樣從何處調入頁面有三種情況:
系統擁有足夠的對換區空間:可以全部從對換區調入所需頁面,以提髙調頁速度。為此,在進程運行前,需將與該進程相關的檔案從檔案區複製到對換區。
系統缺少足夠的對換區空間:凡不會被修改的檔案都直接從檔案區調入(換出時不必寫回)。但對於那些可能被修改的部分,在將它們換出時須調到對換區,以後需要時再從對換區調入。
UNIX方式:與進程有關的檔案都放在檔案區,故未執行過的頁面,都應從檔案區調入。曾經運行過但又被換出的頁面,由於是被放在對換區,因此下次調入時應從對換區調入。進程請求的共享頁面若被其他進程調入內存,則無需再從對換區調入。
5.1 頁面抖動(顛簸)
在頁面置換過程中的一種最糟糕的情形是,剛剛換出的頁面馬上又要換入主存,剛剛換入的頁面馬上就要換出主存,這種頻繁的頁面調度行為稱為抖動,或顛簸。如果一個行程在換頁上花費的時間多於執行時間,那麼這個行程就在顛簸。
頻繁的發生缺頁中斷(抖動),其主要原因是某個進程頻繁存取的頁面數目高於可用的實體頁幀數目。虛擬記憶體技術可以在記憶體中保留更多的進程以提高系統效率。在穩定狀態,幾乎主存的所有空間都被進程塊佔據,處理機和作業系統可以直接存取到盡可能多的進程。但如果管理不當,處理機的大部分時間都將用於交換區塊,也就是請求調入頁面的操作,而不是執行進程的指令,這就會大大降低系統效率。
5.2 工作集(駐留集)
#工作集(或駐留集)是指在某段時間間隔內,進程要存取的頁面集合。經常被使用的頁面需要在工作集中,而長期不被使用的頁面要從工作集中被丟棄。為了防止系統出現抖動現象,需要選擇適當的工作集大小。
工作集模型的原理是:讓作業系統追蹤每個行程的工作集,並為進程分配大於其工作集的實體區塊。如果還有空閒實體區塊,則可以再調一個行程到記憶體以增加多道程式數。如果所有工作集總和增加以至於超過了可用實體區塊的總數,那麼作業系統會暫停一個進程,將其頁面調出並且將其物理區塊分配給其他進程,防止抖動現象。
正確選擇工作集的大小,對記憶體的使用率和系統吞吐量的提高,都將產生重要影響。
分頁管理方式和分段管理方式在很多地方相似,例如記憶體中都是不連續的、都有地址變換機構來進行地址映射等。但兩者也存在著許多區別,表3-20列出了分頁管理方式和分段管理方式在各個方面的比較。
#分頁 | ||
---|---|---|
# #目的 | ||
離散分配 | 方式,以消減記憶體的外零頭,提髙記憶體的利用率。或者說,分頁僅權是由於系統管理的需要而不是使用者的需要 | 是資訊的邏輯單位,它含有一組其意義相對完整的資訊。分段的目的是為了能更好地滿足使用者的需求 |
頁的 | 大小固定且由系統決定 | ,由系統把邏輯位址分成頁號和頁內位址兩部分,是由機器硬體實現的,因而在系統中只能有一種大小的頁面段的 |
位址空間 | 作業位址空間是一維的,即單一的線性位址空間,程式設計師只需利用一個記憶符,即可表示一個位址作業位址空間是二維的,程式設計師在識別一個位址時,既需給予段名,又需給出段內位址 | |
#有內部碎片,無外部碎片 |
以上是linux使用什麼實現虛擬內存的詳細內容。更多資訊請關注PHP中文網其他相關文章!