.jpg)
虛擬內(nèi)存的實(shí)現(xiàn)需要建立在離散分配的內(nèi)存管理方式的基礎(chǔ)上，實(shí)現(xiàn)方法有3種：1、請(qǐng)求分頁(yè)存儲(chǔ)管理方式；2、請(qǐng)求分段存儲(chǔ)管理方式；3、段頁(yè)式存儲(chǔ)管理方式。不管哪種方式，都需要有一定的硬件支持：1、一定容量的內(nèi)存和外存；2、頁(yè)表機(jī)制（或段表機(jī)制），作為主要的數(shù)據(jù)結(jié)構(gòu)；3、中斷機(jī)構(gòu)，當(dāng)用戶程序要訪問(wèn)的部分尚未調(diào)入內(nèi)存，則產(chǎn)生中斷；4、地址變換機(jī)構(gòu)，邏輯地址到物理地址的變換。
本教程操作環(huán)境：linux7.3系統(tǒng)、Dell G3電腦。
1. 虛擬內(nèi)存概述
傳統(tǒng)存儲(chǔ)管理方式同時(shí)將多個(gè)進(jìn)程保存在內(nèi)存中以便允許多道程序設(shè)計(jì)。它們都具有以下兩個(gè)共同的特征：
- 一次性：?作業(yè)必須一次性全部裝入內(nèi)存后，方能開(kāi)始運(yùn)行。這會(huì)導(dǎo)致兩種情況發(fā)生：
1）當(dāng)作業(yè)很大，不能全部被裝入內(nèi)存時(shí)，將使該作業(yè)無(wú)法運(yùn)行；
2）當(dāng)大量作業(yè)要求運(yùn)行時(shí)，由于內(nèi)存不足以容納所有作業(yè)，只能使少數(shù)作業(yè)先運(yùn)行，導(dǎo)致多道程序度的下降。- 駐留性：?作業(yè)被裝入內(nèi)存后，就一直駐留在內(nèi)存中，其任何部分都不會(huì)被換出，直至作業(yè)運(yùn)行結(jié)束。運(yùn)行中的進(jìn)程，會(huì)因等待 I/O 而被阻塞，可能處于長(zhǎng)期等待狀態(tài)。
因此，許多在程序運(yùn)行中不用或暫時(shí)不用的程序（數(shù)據(jù)）占據(jù)了大量的內(nèi)存空間，而一些需要運(yùn)行的作業(yè)又無(wú)法裝入運(yùn)行，顯然浪費(fèi)了寶貴的內(nèi)存資源。
?1.1 虛擬存儲(chǔ)器的定義和特征
基于局部性原理，在程序裝入時(shí)，可以將程序的一部分裝入內(nèi)存，而將其余部分留在外存，就可以啟動(dòng)程序執(zhí)行。在程序執(zhí)行過(guò)程中，當(dāng)所訪問(wèn)的信息不在內(nèi)存時(shí)，由操作系統(tǒng)將所需要的部分調(diào)入內(nèi)存，然后繼續(xù)執(zhí)行程序。另一方面，操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的內(nèi)容換出到外存上，從而騰出空間存放將要調(diào)入內(nèi)存的信息。
這樣，由于系統(tǒng)提供了部分裝入、請(qǐng)求調(diào)入和置換功能后（對(duì)用戶完全透明），給用戶的感覺(jué)是好像存在一個(gè)比實(shí)際物理內(nèi)存大得多的存儲(chǔ)器，稱為虛擬存儲(chǔ)器。
虛擬存儲(chǔ)器的大小由計(jì)算機(jī)的地址結(jié)構(gòu)決定，并非是內(nèi)存和外存的簡(jiǎn)單相加。
虛擬存儲(chǔ)器有以下三個(gè)主要特征：
- 多次性：無(wú)需在作業(yè)運(yùn)行時(shí)一次性地全部裝入內(nèi)存，而是允許被分成多次調(diào)入內(nèi)存運(yùn)行。
- 對(duì)換性：無(wú)需在作業(yè)運(yùn)行時(shí)一直常駐內(nèi)存，而是允許在作業(yè)的運(yùn)行過(guò)程中，進(jìn)行換進(jìn)和換出。
- 虛擬性：從邏輯上擴(kuò)充內(nèi)存的容量，使用戶所看到的內(nèi)存容量，遠(yuǎn)大于實(shí)際的內(nèi)存容量。
?1.2 虛擬內(nèi)存技術(shù)的實(shí)現(xiàn)
虛擬內(nèi)存中，允許將一個(gè)作業(yè)分多次調(diào)入內(nèi)存。
釆用連續(xù)分配方式時(shí)，會(huì)使相當(dāng)一部分內(nèi)存空間都處于暫時(shí)或“永久”的空閑狀態(tài)，造成內(nèi)存資源的嚴(yán)重浪費(fèi)，而且也無(wú)法從邏輯上擴(kuò)大內(nèi)存容量。
因此，虛擬內(nèi)存的實(shí)現(xiàn)需要建立在離散分配的內(nèi)存管理方式的基礎(chǔ)上。虛擬內(nèi)存的實(shí)現(xiàn)有以下三種方式：
- 請(qǐng)求分頁(yè)存儲(chǔ)管理
- 請(qǐng)求分段存儲(chǔ)管理
- 段頁(yè)式存儲(chǔ)管理
不管哪種方式，都需要有一定的硬件支持。一般需要的支持有以下幾個(gè)方面：
- 一定容量的內(nèi)存和外存。
- 頁(yè)表機(jī)制（或段表機(jī)制），作為主要的數(shù)據(jù)結(jié)構(gòu)。
- 中斷機(jī)構(gòu)，當(dāng)用戶程序要訪問(wèn)的部分尚未調(diào)入內(nèi)存，則產(chǎn)生中斷。
- 地址變換機(jī)構(gòu)，邏輯地址到物理地址的變換。
連續(xù)分配方式：指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。
- 固定分區(qū)分配：將內(nèi)存空間劃分為若干個(gè)固定大小的區(qū)域，在每個(gè)分區(qū)中只裝入一道作業(yè)，便可以有多道作業(yè)并發(fā)執(zhí)行。缺乏靈活性，會(huì)產(chǎn)生大量的內(nèi)部碎片，內(nèi)存的利用率很低。
- 動(dòng)態(tài)分區(qū)分配：根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。作業(yè)裝入內(nèi)存時(shí)，把可用內(nèi)存分出一個(gè)連續(xù)區(qū)域給作業(yè)，且分區(qū)的大小正好合適作業(yè)大小的需要。會(huì)產(chǎn)生很多外部碎片。
離散分配方式：將一個(gè)進(jìn)程分散地裝入到許多不相鄰的分區(qū)中，便可充分地利用內(nèi)存。
?分頁(yè)存儲(chǔ)的概念：
- 頁(yè)面、頁(yè)框和塊。進(jìn)程中的塊稱為頁(yè)或頁(yè)面(Page)，具有頁(yè)號(hào)；內(nèi)存中的塊稱為頁(yè)框（Page Frame，頁(yè)框=內(nèi)存塊=物理塊=物理頁(yè)面），具有頁(yè)框號(hào)。外存也以同樣的單位進(jìn)行劃分，直接稱為塊(Block)。進(jìn)程在執(zhí)行時(shí)需要申請(qǐng)主存空間，就是要為每個(gè)頁(yè)面分配主存中的可用頁(yè)框，這就產(chǎn)生了頁(yè)和頁(yè)框的一一對(duì)應(yīng)。各個(gè)頁(yè)面不必連續(xù)存放，可以放到不相鄰的各個(gè)頁(yè)框中。
- 地址結(jié)構(gòu)：前一部分為頁(yè)號(hào)P，后一部分為頁(yè)內(nèi)偏移量W。地址長(zhǎng)度為32 位，其中0~11位為頁(yè)內(nèi)地址，即每頁(yè)大小為4KB；12~31位為頁(yè)號(hào)，地址空間最多允許有2^20頁(yè)。
- 頁(yè)表。為了便于在內(nèi)存中找到進(jìn)程的每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊，系統(tǒng)為每個(gè)進(jìn)程建立一張頁(yè)表，記錄頁(yè)面在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)，頁(yè)表一般存放在內(nèi)存中。在配置了頁(yè)表后，進(jìn)程執(zhí)行時(shí)，通過(guò)查找該表，即可找到每頁(yè)在內(nèi)存中的物理塊號(hào)。可見(jiàn)，頁(yè)表的作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。
2. 請(qǐng)求分頁(yè)管理方式實(shí)現(xiàn)虛擬內(nèi)存
請(qǐng)求分頁(yè)是目前最常用的一種實(shí)現(xiàn)虛擬存儲(chǔ)器的方法。
請(qǐng)求分頁(yè)系統(tǒng)建立在基本分頁(yè)系統(tǒng)基礎(chǔ)之上，為了支持虛擬存儲(chǔ)器功能而增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能。
在請(qǐng)求分頁(yè)系統(tǒng)中，只要求將當(dāng)前需要的一部分頁(yè)面裝入內(nèi)存，便可以啟動(dòng)作業(yè)運(yùn)行。
在作業(yè)執(zhí)行過(guò)程中，當(dāng)所要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，再通過(guò)調(diào)頁(yè)功能將其調(diào)入，同時(shí)還可以通過(guò)置換功能將暫時(shí)不用的頁(yè)面換出到外存上，以便騰出內(nèi)存空間。
為了實(shí)現(xiàn)請(qǐng)求分頁(yè)，系統(tǒng)必須提供一定的硬件支持。除了需要一定容量的內(nèi)存及外存的計(jì)算機(jī)系統(tǒng)，還需要有頁(yè)表機(jī)制、缺頁(yè)中斷機(jī)構(gòu)、地址變換機(jī)構(gòu)。
2.1 頁(yè)表機(jī)制
請(qǐng)求分頁(yè)系統(tǒng)的頁(yè)表機(jī)制不同于基本分頁(yè)系統(tǒng)，請(qǐng)求分頁(yè)系統(tǒng)在一個(gè)作業(yè)運(yùn)行之前不要求全部一次性調(diào)入內(nèi)存。
因此在作業(yè)的運(yùn)行過(guò)程中，必然會(huì)出現(xiàn)要訪問(wèn)的頁(yè)面不在內(nèi)存的情況，如何發(fā)現(xiàn)和處理這種情況是請(qǐng)求分頁(yè)系統(tǒng)必須解決的兩個(gè)基本問(wèn)題。為此，在請(qǐng)求頁(yè)表項(xiàng)中增加了四個(gè)字段，分別為：
| 頁(yè)號(hào) | 物理塊號(hào) | 狀態(tài)位 P | 訪問(wèn)字段 A | 修改位 M | 外存地址 |
- 狀態(tài)位 P：用于指示該頁(yè)是否已調(diào)入內(nèi)存，供程序訪問(wèn)時(shí)參考。
- 訪問(wèn)字段 A：用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)，或記錄本頁(yè)最近己有多長(zhǎng)時(shí)間未被訪問(wèn)，供置換算法換出頁(yè)面時(shí)參考。
- 修改位 M：標(biāo)識(shí)該頁(yè)在調(diào)入內(nèi)存后是否被修改過(guò)。
- 外存地址：用于指出該頁(yè)在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)參考。
2.2 缺頁(yè)中斷機(jī)構(gòu)
在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，便產(chǎn)生一個(gè)缺頁(yè)中斷，請(qǐng)求操作系統(tǒng)將所缺的頁(yè)調(diào)入內(nèi)存。
此時(shí)應(yīng)將缺頁(yè)的進(jìn)程阻塞（調(diào)頁(yè)完成喚醒)，如果內(nèi)存中有空閑塊，則分配一個(gè)塊，將要調(diào)入的頁(yè)裝入該塊，并修改頁(yè)表中相應(yīng)頁(yè)表項(xiàng)；若此時(shí)內(nèi)存中沒(méi)有空閑塊，則要淘汰某頁(yè)（若被淘汰頁(yè)在內(nèi)存期間被修改過(guò)，則要將其寫(xiě)回外存)。
缺頁(yè)中斷作為中斷同樣要經(jīng)歷，諸如保護(hù)CPU環(huán)境、分析中斷原因、轉(zhuǎn)入缺頁(yè)中斷處理程序、恢復(fù)CPU環(huán)境等幾個(gè)步驟。但與一般的中斷相比，它有以下兩個(gè)明顯的區(qū)別：
- 在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)，而非一條指令執(zhí)行完后，屬于內(nèi)部中斷。
- 一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。
2.3 地址變換機(jī)構(gòu)
請(qǐng)求分頁(yè)系統(tǒng)中的地址變換機(jī)構(gòu)，是在分頁(yè)系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上，為實(shí)現(xiàn)虛擬內(nèi)存，又增加了某些功能而形成的。
在進(jìn)行地址變換時(shí)，先檢索快表：
- 若找到要訪問(wèn)的頁(yè)，便修改頁(yè)表項(xiàng)中的訪問(wèn)位（寫(xiě)指令則還須重置修改位)，然后利用頁(yè)表項(xiàng)中給出的物理塊號(hào)和頁(yè)內(nèi)地址形成物理地址。
- 若未找到該頁(yè)的頁(yè)表項(xiàng)，應(yīng)到內(nèi)存中去查找頁(yè)表，再對(duì)比頁(yè)表項(xiàng)中的狀態(tài)位P，看該頁(yè)是否已調(diào)入內(nèi)存，未調(diào)入則產(chǎn)生缺頁(yè)中斷，請(qǐng)求從外存把該頁(yè)調(diào)入內(nèi)存。
頁(yè)表指出邏輯地址中的頁(yè)號(hào)與所占主存物理塊號(hào)的對(duì)應(yīng)關(guān)系。頁(yè)式存儲(chǔ)管理在用動(dòng)態(tài)重定位方式裝入作業(yè)時(shí)，要利用頁(yè)表做地址轉(zhuǎn)換工作。
快表(TLB，Translation Lookaside Buffer)就是存放在高速緩沖存儲(chǔ)器的部分頁(yè)表。作為當(dāng)前進(jìn)程頁(yè)表的Cache，它的作用與頁(yè)表相似，但加快了地址映射速度，提高了訪問(wèn)速率。
由于采用頁(yè)表做地址轉(zhuǎn)換，讀寫(xiě)內(nèi)存數(shù)據(jù)時(shí)CPU要訪問(wèn)兩次主存（查詢頁(yè)表、訪問(wèn)目的地址）。
有了快表，有時(shí)只要訪問(wèn)一次高速緩沖存儲(chǔ)器，一次主存，這樣可加速查找并提高指令執(zhí)行速度。
3. 頁(yè)面置換算法
進(jìn)程運(yùn)行時(shí)，若其訪問(wèn)的頁(yè)面不在內(nèi)存而需將其調(diào)入，但內(nèi)存已無(wú)空閑空間時(shí)，就需要從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)，送入磁盤的對(duì)換區(qū)。
選擇調(diào)出頁(yè)面的算法就稱為頁(yè)面置換算法。好的頁(yè)面置換算法應(yīng)有較低的頁(yè)面更換頻率，也就是說(shuō)，應(yīng)將以后不會(huì)再訪問(wèn)或者以后較長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問(wèn)的頁(yè)面先調(diào)出。
3.1 最佳置換算法（OPT）
最佳(Optimal, OPT)置換算法所選擇的被淘汰頁(yè)面將是以后永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面，這樣可以保證獲得最低的缺頁(yè)率。
但由于人們目前無(wú)法預(yù)知進(jìn)程在內(nèi)存下的若千頁(yè)面中哪個(gè)是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，因而該算法無(wú)法實(shí)現(xiàn)，但最佳置換算法可以用來(lái)評(píng)價(jià)其他算法。
假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下頁(yè)面號(hào)引用串：
7, 0, 1, 2, 0, 3, 0,?4,?2,?3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
進(jìn)程運(yùn)行時(shí)，先將7, 0, 1三個(gè)頁(yè)面依次裝入內(nèi)存。進(jìn)程要訪問(wèn)頁(yè)面2時(shí)，產(chǎn)生缺頁(yè)中斷，根據(jù)最佳置換算法，選擇第18次訪問(wèn)才需調(diào)入的頁(yè)面7予以淘汰。然后，訪問(wèn)頁(yè)面0時(shí)，因?yàn)橐言趦?nèi)存中所以不必產(chǎn)生缺頁(yè)中斷。訪問(wèn)頁(yè)面3時(shí)又會(huì)根據(jù)最佳置換算法將頁(yè)面1淘汰……依此類推。從圖中可以看出釆用最佳置換算法時(shí)的情況。
| 訪問(wèn)頁(yè)面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理塊1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 7 | |||||||||||
| 物理塊2 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | ||||||||||||
| 物理塊3 | 1 | 1 | 3 | 3 | 3 | 1 | 1 | |||||||||||||
| 缺頁(yè)否 | √ | √ | √ | √ | √ | √ | √ | √ |
可以看到，發(fā)生缺頁(yè)中斷的次數(shù)為9，頁(yè)面置換的次數(shù)為6。
3.2 先進(jìn)先出(FIFO)頁(yè)面置換算法
優(yōu)先淘汰最早進(jìn)入內(nèi)存的頁(yè)面，亦即在內(nèi)存中駐留時(shí)間最久的頁(yè)面。
該算法實(shí)現(xiàn)簡(jiǎn)單，只需把調(diào)入內(nèi)存的頁(yè)面根據(jù)先后次序鏈接成隊(duì)列，設(shè)置一個(gè)指針總指向最早的頁(yè)面。但該算法與進(jìn)程實(shí)際運(yùn)行時(shí)的規(guī)律不適應(yīng)，因?yàn)樵谶M(jìn)程中，有的頁(yè)面經(jīng)常被訪問(wèn)。
| 訪問(wèn)頁(yè)面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理塊1 | 7 | 7 | 7 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 7 | 7 | 7 | |||||
| 物理塊2 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | 1 | 1 | 0 | 0 | ||||||
| 物理塊3 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | |||||||
| 缺頁(yè)否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
利用FIFO算法時(shí)進(jìn)行了?12 次頁(yè)面置換，比最佳置換算法正好多一倍。
FIFO算法還會(huì)產(chǎn)生當(dāng)所分配的物理塊數(shù)增大而頁(yè)故障數(shù)不減反增的異常現(xiàn)象，這是由?Belady于1969年發(fā)現(xiàn)，故稱為Belady異常，如下表所示。
| 訪問(wèn)頁(yè)面 | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理塊1 | 1 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | |||
| 物理塊2 | 2 | 2 | 2 | 1 | 1 | 1 | 3 | 3 | ||||
| 物理塊3 | 3 | 3 | 3 | 2 | 2 | 2 | 4 | |||||
| 缺頁(yè)否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | |||
| 增加物理塊數(shù)后對(duì)比 | ||||||||||||
| 物理塊1* | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 4 | 4 | ||
| 物理塊2* | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 5 | |||
| 物理塊3* | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | ||||
| 物理塊4* | 4 | 4 | 4 | 4 | 3 | 3 | 3 | |||||
| 缺頁(yè)否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | ||
只有FIFO算法可能出現(xiàn)Belady異常，而LRU和OPT算法永遠(yuǎn)不會(huì)出現(xiàn)Belady異常。
3.3 最近最久未使用(LRU)置換算法
最近最久未使用(LRU，Least Recently Used)置換算法選擇最近最長(zhǎng)時(shí)間未訪問(wèn)過(guò)的頁(yè)面予以淘汰，它認(rèn)為過(guò)去一段時(shí)間內(nèi)未訪問(wèn)過(guò)的頁(yè)面，在最近的將來(lái)可能也不會(huì)被訪問(wèn)。
該算法為每個(gè)頁(yè)面設(shè)置一個(gè)訪問(wèn)字段，來(lái)記錄頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間，淘汰頁(yè)面時(shí)選擇現(xiàn)有頁(yè)面中值最大的予以淘汰。
| 訪問(wèn)頁(yè)面 | 7 | 0 | 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 | 3 | 2 | 2 | 2 | 2 | 2 | 7 | ||||||||||
| 缺頁(yè)否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
LRU性能較好，但需要寄存器和棧的硬件支持，開(kāi)銷更大。
LRU是堆棧類的算法。理論上可以證明，堆棧類算法不可能出現(xiàn)Belady異常。FIFO算法基于隊(duì)列實(shí)現(xiàn)，不是堆棧類算法。
3.4?時(shí)鐘(CLOCK)置換算法
LRU算法的性能接近于OPT,但是實(shí)現(xiàn)起來(lái)比較困難，且開(kāi)銷大；FIFO算法實(shí)現(xiàn)簡(jiǎn)單，但性能差。所以操作系統(tǒng)的設(shè)計(jì)者嘗試了很多算法，試圖用比較小的開(kāi)銷接近LRU的性能，這類算法都是CLOCK算法的變體。
簡(jiǎn)單的CLOCK算法是給每一幀關(guān)聯(lián)一個(gè)附加位，稱為使用位。當(dāng)某一頁(yè)首次裝入主存，以及后續(xù)被訪問(wèn)時(shí)，使用位被置為1。
對(duì)于頁(yè)替換算法，用于替換的候選幀集合看做一個(gè)循環(huán)緩沖區(qū)，并且有一個(gè)指針與之相關(guān)聯(lián)。當(dāng)某一頁(yè)被替換時(shí)，該指針被設(shè)置成指向緩沖區(qū)中的下一幀。
當(dāng)需要替換一頁(yè)時(shí)，操作系統(tǒng)掃描緩沖區(qū)，以查找第一個(gè)使用位為0的一幀。每當(dāng)遇到一個(gè)使用位為1的幀時(shí)，操作系統(tǒng)就將該位重新置為0；如果所有幀的使用位均為1，則指針在緩沖區(qū)中完整地循環(huán)一周，把所有使用位都置為0，并且停留在最初的位置上，替換該幀中的頁(yè)。由于該算法循環(huán)地檢查各頁(yè)面的情況，故稱為CLOCK算法，又稱為最近未用(Not Recently Used, NRU)算法。
CLOCK算法的性能比較接近LRU，而通過(guò)增加使用的位數(shù)目，可以使得CLOCK算法更加高效。在使用位used的基礎(chǔ)上再增加一個(gè)修改位modified，則得到改進(jìn)型的CLOCK置換算法。
每一幀都處于以下四種情況之一：
-
最近未被訪問(wèn)，也未被修改(u=0, m=0)。
-
最近被訪問(wèn)，但未被修改(u=1, m=0)。
-
最近未被訪問(wèn)，但被修改(u=0, m=1)。
-
最近被訪問(wèn)，被修改(u=1, m=1)。
算法執(zhí)行如下操作步驟：
-
從指針的當(dāng)前位置開(kāi)始，掃描幀緩沖區(qū)。在這次掃描過(guò)程中，對(duì)使用位不做任何修改。選擇遇到的第一個(gè)幀(u=0, m=0)用于替換。
-
如果第1步失敗，則重新掃描，查找(u=0, m=1)的幀。選擇遇到的第一個(gè)這樣的幀用于替換。在這個(gè)掃描過(guò)程中，對(duì)每個(gè)跳過(guò)的幀，把它的使用位設(shè)置成0。
-
如果第2步失敗，指針將回到它的最初位置，并且集合中所有幀的使用位均為0。重復(fù)第1步，并且如果有必要，重復(fù)第2步。這樣將可以找到供替換的幀。
改進(jìn)型的CLOCK算法優(yōu)于簡(jiǎn)單CLOCK算法之處在于替換時(shí)首選沒(méi)有變化的頁(yè)。由于修改過(guò)的頁(yè)在被替換之前必須寫(xiě)回，因而這樣做會(huì)節(jié)省時(shí)間。
4. 頁(yè)面分配策略
4.1 駐留集大小
對(duì)于分頁(yè)式的虛擬內(nèi)存，在準(zhǔn)備執(zhí)行時(shí)，不需要也不可能把一個(gè)進(jìn)程的所有頁(yè)都讀取到主存，因此，操作系統(tǒng)必須決定讀取多少頁(yè)。也就是說(shuō)，給特定的進(jìn)程分配多大的主存空間，這需要考慮以下幾點(diǎn)：
-
分配給一個(gè)進(jìn)程的存儲(chǔ)量越小，在任何時(shí)候駐留在主存中的進(jìn)程數(shù)就越多，從而可以提高處理機(jī)的時(shí)間利用效率。
-
如果一個(gè)進(jìn)程在主存中的頁(yè)數(shù)過(guò)少，盡管有局部性原理，頁(yè)錯(cuò)誤率仍然會(huì)相對(duì)較高。
-
如果頁(yè)數(shù)過(guò)多，由于局部性原理，給特定的進(jìn)程分配更多的主存空間對(duì)該進(jìn)程的錯(cuò)誤率沒(méi)有明顯的影響。
基于這些因素，現(xiàn)代操作系統(tǒng)通常釆用三種策略：
-
固定分配局部置換：它為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，在整個(gè)運(yùn)行期間都不改變。若進(jìn)程在運(yùn)行中發(fā)生缺頁(yè)，則只能從該進(jìn)程在內(nèi)存中的頁(yè)面中選出一頁(yè)換出，然后再調(diào)入需要的頁(yè)面。實(shí)現(xiàn)這種策略難以確定為每個(gè)進(jìn)程應(yīng)分配的物理塊數(shù)目：太少會(huì)頻繁出現(xiàn)缺頁(yè)中斷，太多又會(huì)使CPU和其他資源利用率下降。
-
可變分配全局置換：這是最易于實(shí)現(xiàn)的物理塊分配和置換策略，為系統(tǒng)中的每個(gè)進(jìn)程分配一定數(shù)目的物理塊，操作系統(tǒng)自身也保持一個(gè)空閑物理塊隊(duì)列。當(dāng)某進(jìn)程發(fā)生缺頁(yè)時(shí)，系統(tǒng)從空閑物理塊隊(duì)列中取出一個(gè)物理塊分配給該進(jìn)程，并將欲調(diào)入的頁(yè)裝入其中。
-
可變分配局部置換：它為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，當(dāng)某進(jìn)程發(fā)生缺頁(yè)時(shí)，只允許從該進(jìn)程在內(nèi)存的頁(yè)面中選出一頁(yè)換出，這樣就不會(huì)影響其他進(jìn)程的運(yùn)行。如果進(jìn)程在運(yùn)行中頻繁地缺頁(yè)，系統(tǒng)再分配若干物理塊給該進(jìn)程，直至該進(jìn)程缺頁(yè)率趨于適當(dāng)程度； 反之，若進(jìn)程在運(yùn)行中缺頁(yè)率特別低，則可適當(dāng)減少分配給該進(jìn)程的物理塊。
4.2 調(diào)入頁(yè)面的時(shí)機(jī)
為確定系統(tǒng)將進(jìn)程運(yùn)行時(shí)所缺的頁(yè)面調(diào)入內(nèi)存的時(shí)機(jī)，可釆取以下兩種調(diào)頁(yè)策略：
-
預(yù)調(diào)頁(yè)策略：根據(jù)局部性原理，一次調(diào)入若干個(gè)相鄰的頁(yè)可能會(huì)比一次調(diào)入一頁(yè)更高效。但如果調(diào)入的一批頁(yè)面中大多數(shù)都未被訪問(wèn)，則又是低效的。所以就需要釆用以預(yù)測(cè)為基礎(chǔ)的預(yù)調(diào)頁(yè)策略，將預(yù)計(jì)在不久之后便會(huì)被訪問(wèn)的頁(yè)面預(yù)先調(diào)入內(nèi)存。但目前預(yù)調(diào)頁(yè)的成功率僅約50%。故這種策略主要用于進(jìn)程的首次調(diào)入時(shí)，由程序員指出應(yīng)該先調(diào)入哪些頁(yè)。
-
請(qǐng)求調(diào)頁(yè)策略：進(jìn)程在運(yùn)行中需要訪問(wèn)的頁(yè)面不在內(nèi)存而提出請(qǐng)求，由系統(tǒng)將所需頁(yè)面調(diào)入內(nèi)存。由這種策略調(diào)入的頁(yè)一定會(huì)被訪問(wèn)，且這種策略比較易于實(shí)現(xiàn)，故在目前的虛擬存儲(chǔ)器中大多釆用此策略。它的缺點(diǎn)在于每次只調(diào)入一頁(yè)，調(diào)入調(diào)出頁(yè)面數(shù)多時(shí)會(huì)花費(fèi)過(guò)多的I/O開(kāi)銷。
4.3 從何處調(diào)入頁(yè)面
請(qǐng)求分頁(yè)系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對(duì)換頁(yè)面的對(duì)換區(qū)。對(duì)換區(qū)通常是釆用連續(xù)分配方式，而文件區(qū)釆用離散分配方式，故對(duì)換區(qū)的磁盤I/O速度比文件區(qū)的更快。這樣從何處調(diào)入頁(yè)面有三種情況：
-
系統(tǒng)擁有足夠的對(duì)換區(qū)空間：可以全部從對(duì)換區(qū)調(diào)入所需頁(yè)面，以提髙調(diào)頁(yè)速度。為此，在進(jìn)程運(yùn)行前，需將與該進(jìn)程有關(guān)的文件從文件區(qū)復(fù)制到對(duì)換區(qū)。
-
系統(tǒng)缺少足夠的對(duì)換區(qū)空間：凡不會(huì)被修改的文件都直接從文件區(qū)調(diào)入（換出時(shí)不必寫(xiě)回）。但對(duì)于那些可能被修改的部分，在將它們換出時(shí)須調(diào)到對(duì)換區(qū)，以后需要時(shí)再?gòu)膶?duì)換區(qū)調(diào)入。
-
unix方式：與進(jìn)程有關(guān)的文件都放在文件區(qū)，故未運(yùn)行過(guò)的頁(yè)面，都應(yīng)從文件區(qū)調(diào)入。曾經(jīng)運(yùn)行過(guò)但又被換出的頁(yè)面，由于是被放在對(duì)換區(qū)，因此下次調(diào)入時(shí)應(yīng)從對(duì)換區(qū)調(diào)入。進(jìn)程請(qǐng)求的共享頁(yè)面若被其他進(jìn)程調(diào)入內(nèi)存，則無(wú)需再?gòu)膶?duì)換區(qū)調(diào)入。
5.?頁(yè)面抖動(dòng)(顛簸)和工作集(駐留集)
5.1 頁(yè)面抖動(dòng)（顛簸）
在頁(yè)面置換過(guò)程中的一種最糟糕的情形是，剛剛換出的頁(yè)面馬上又要換入主存，剛剛換入的頁(yè)面馬上就要換出主存，這種頻繁的頁(yè)面調(diào)度行為稱為抖動(dòng)，或顛簸。如果一個(gè)進(jìn)程在換頁(yè)上用的時(shí)間多于執(zhí)行時(shí)間，那么這個(gè)進(jìn)程就在顛簸。
頻繁的發(fā)生缺頁(yè)中斷（抖動(dòng)），其主要原因是某個(gè)進(jìn)程頻繁訪問(wèn)的頁(yè)面數(shù)目高于可用的物理頁(yè)幀數(shù)目。虛擬內(nèi)存技術(shù)可以在內(nèi)存中保留更多的進(jìn)程以提高系統(tǒng)效率。在穩(wěn)定狀態(tài)，幾乎主存的所有空間都被進(jìn)程塊占據(jù)，處理機(jī)和操作系統(tǒng)可以直接訪問(wèn)到盡可能多的進(jìn)程。但如果管理不當(dāng)，處理機(jī)的大部分時(shí)間都將用于交換塊，即請(qǐng)求調(diào)入頁(yè)面的操作，而不是執(zhí)行進(jìn)程的指令，這就會(huì)大大降低系統(tǒng)效率。
5.2 工作集（駐留集）
工作集（或駐留集）是指在某段時(shí)間間隔內(nèi)，進(jìn)程要訪問(wèn)的頁(yè)面集合。經(jīng)常被使用的頁(yè)面需要在工作集中，而長(zhǎng)期不被使用的頁(yè)面要從工作集中被丟棄。為了防止系統(tǒng)出現(xiàn)抖動(dòng)現(xiàn)象，需要選擇合適的工作集大小。
工作集模型的原理是：讓操作系統(tǒng)跟蹤每個(gè)進(jìn)程的工作集，并為進(jìn)程分配大于其工作集的物理塊。如果還有空閑物理塊，則可以再調(diào)一個(gè)進(jìn)程到內(nèi)存以增加多道程序數(shù)。如果所有工作集之和增加以至于超過(guò)了可用物理塊的總數(shù)，那么操作系統(tǒng)會(huì)暫停一個(gè)進(jìn)程，將其頁(yè)面調(diào)出并且將其物理塊分配給其他進(jìn)程，防止出現(xiàn)抖動(dòng)現(xiàn)象。
正確選擇工作集的大小，對(duì)存儲(chǔ)器的利用率和系統(tǒng)吞吐量的提高，都將產(chǎn)生重要影響。
6. 總結(jié)
分頁(yè)管理方式和分段管理方式在很多地方相似，比如內(nèi)存中都是不連續(xù)的、都有地址變換機(jī)構(gòu)來(lái)進(jìn)行地址映射等。但兩者也存在著許多區(qū)別，表3-20列出了分頁(yè)管理方式和分段管理方式在各個(gè)方面的對(duì)比。
| 分頁(yè) | 分段 | |
|---|---|---|
| 目 的 | 頁(yè)是信息的物理單位，分頁(yè)是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提髙內(nèi)存的利用率。或者說(shuō)，分頁(yè)僅權(quán)是由于系統(tǒng)管理的需要而不是用戶的需要 | 是信息的邏輯單位，它含有一組其意義相對(duì)完整的信息。分段的目的是為了能更好地滿足用戶的需要 |
| 長(zhǎng) 度 | 頁(yè)的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，是由機(jī)器硬件實(shí)現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁(yè)面 | 段的長(zhǎng)度不固定，決定于用戶所編寫(xiě)的程序， 通常由編譯程序在對(duì)流程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來(lái)劃分 |
| 地址空間 | 作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個(gè)記憶符，即可表示 一個(gè)地址 | 作業(yè)地址空間是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，既需給出段名，又需給出段內(nèi)地址 |
| 碎 片 | 有內(nèi)部碎片，無(wú)外部碎片 | 有外部碎片，無(wú)內(nèi)部碎片 |
| ”共享“和“動(dòng)態(tài)鏈接” | 不容易實(shí)現(xiàn) | 容易實(shí)現(xiàn) |
相關(guān)推薦：《Linux視頻教程》
.png)
