4.6虛擬存儲(chǔ)系統(tǒng)虛擬存儲(chǔ)器的基本概念指具有請(qǐng)求調(diào)入功能和置換功能，能夠利用外存儲(chǔ)器的空余空間從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。進(jìn)程的局部性特征時(shí)間局部性。若某個(gè)指令或者數(shù)據(jù)被訪問(wèn)了，那么在不久的將來(lái)將會(huì)再次訪問(wèn)該指令或者數(shù)據(jù)。這是由于程序中的循環(huán)結(jié)構(gòu)導(dǎo)致的?？臻g局部性。若某個(gè)指令或者數(shù)據(jù)被訪問(wèn)了，那么它附近的指令或者數(shù)據(jù)可能馬上會(huì)被訪問(wèn)。這是程序順序執(zhí)行的方式和線性數(shù)據(jù)結(jié)構(gòu)（如數(shù)組）所導(dǎo)致的。虛擬存儲(chǔ)器的引入在以下兩方面進(jìn)行了改變：將進(jìn)程調(diào)入的一次性或者整體性改為多次性將進(jìn)程的駐留性改為置換性圖4-20虛擬存儲(chǔ)系統(tǒng)示意圖請(qǐng)求分頁(yè)存儲(chǔ)管理方式基于頁(yè)面系統(tǒng)的擴(kuò)充方式是虛擬存儲(chǔ)器系統(tǒng)的一種實(shí)現(xiàn)方式。虛擬存儲(chǔ)器只是把一部分程序內(nèi)容裝入內(nèi)存，而把其他的部分放置在輔存（硬盤(pán)）中。當(dāng)要執(zhí)行的部分頁(yè)面不在內(nèi)存中時(shí)，需要及時(shí)把這部分頁(yè)面調(diào)入內(nèi)存。頁(yè)面調(diào)入的時(shí)候可能還需要考慮置換的問(wèn)題。兩種頁(yè)式系統(tǒng)①

簡(jiǎn)單頁(yè)式系統(tǒng)：裝入一個(gè)程序的全部頁(yè)面才能投入運(yùn)行。

②

請(qǐng)求頁(yè)式系統(tǒng)：裝入一個(gè)程序的部分頁(yè)面即可投入運(yùn)行。擴(kuò)充頁(yè)表功能

狀態(tài)位：標(biāo)識(shí)該頁(yè)是否在主存訪問(wèn)字段：記錄頁(yè)面被訪問(wèn)的情況，修改位：頁(yè)面裝入內(nèi)存后是否被修改過(guò)，供頁(yè)面置換時(shí)參考。外存地址：該頁(yè)面在外存的位置缺頁(yè)處理

頁(yè)面置換策略可變分配全局置換固定分配局部置換可變分配局部置換頁(yè)面置換算法選擇淘汰頁(yè)面的規(guī)則叫做置換算法（淘汰算法）置換算法直接影響到請(qǐng)求分頁(yè)系統(tǒng)的性能最佳置換算法OPT先進(jìn)先出法FIFO最近最久未使用法LRU最近最少使用法LFU時(shí)鐘算法CLOCK

頁(yè)面置換的相關(guān)問(wèn)題顛簸（thrashing）——抖動(dòng)在主存和輔存之間的頻繁頁(yè)面置換的現(xiàn)像稱為頁(yè)面“顛簸”或者“抖動(dòng)”，這種情況會(huì)導(dǎo)致系統(tǒng)效率急劇下降。缺頁(yè)中斷率假定程序p共有n頁(yè)，系統(tǒng)分配m塊，有；

若程序p在運(yùn)行中：成功的訪問(wèn)次數(shù)為s，不成功的訪問(wèn)次數(shù)為f；缺頁(yè)中斷率：

r：置換算法；m：系統(tǒng)分配的塊數(shù)；p：程序特征置換算法最佳算法（OPT算法）當(dāng)要調(diào)入一新頁(yè)而必須先淘汰一舊頁(yè)時(shí)，所淘汰的那一頁(yè)應(yīng)是以后不再要用，或者是在最長(zhǎng)的時(shí)間以后才會(huì)用到的那頁(yè)。頁(yè)走向41327354132361012302144444

4

4

2

2

2

2

2

1127

5

1

1

1

1

3

3

333

3

3

3

6

0

0

缺頁(yè)+++++

+++

+

+

+

+

基于OPT置換算法的情況基于OPT算法時(shí)，發(fā)生缺頁(yè)中斷的次數(shù)為12，頁(yè)面置換的次數(shù)為9，缺頁(yè)率為12/20。最佳算法（OPT算法）是一個(gè)理論算法。為什么該方法無(wú)法實(shí)現(xiàn)？進(jìn)程真正的頁(yè)面走向是未知的，無(wú)法全部預(yù)知頁(yè)面之后進(jìn)行全局最優(yōu)化。常用的置換算法①

先進(jìn)先出淘汰算法(FIFO——FirstInFirstOut)

思路：總是選擇在主存中最早進(jìn)入主存（即居留時(shí)間最長(zhǎng)）的一頁(yè)淘汰。頁(yè)走向41327354132361012302144422

24442

220

00

2

1117

77111

666

22

3

333

55533

311

13

缺頁(yè)+++++

+++++

+++

++

基于FIFO算法時(shí)，缺頁(yè)15次，置換12次，缺頁(yè)率15/20。問(wèn)題：如何實(shí)現(xiàn)找到先進(jìn)入的頁(yè)面？Belady現(xiàn)象在FIFO淘汰算法中的一種特殊現(xiàn)象思考：增加進(jìn)程的主存塊數(shù)量對(duì)缺頁(yè)率會(huì)有怎樣的影響？例：在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，假如一個(gè)作業(yè)的頁(yè)面走向?yàn)?，2，3，4，1，2，5，1，2，3，4，5,當(dāng)分給該作業(yè)的物理塊數(shù)M分別為3和4時(shí)，請(qǐng)用FIFO計(jì)算缺頁(yè)次數(shù)和缺頁(yè)率，并比較所得的結(jié)果。使用FIFO算法——物理塊數(shù)為3:頁(yè)走向123412512345111144

4555

2

2221

1133

3

333

2224

缺頁(yè)+++++++++

缺頁(yè)次數(shù)：9，缺頁(yè)率：9/12。使用FIFO算法——物理塊數(shù)為4:缺頁(yè)次數(shù)：10，缺頁(yè)率：10/12，這種異?，F(xiàn)象稱為Belady現(xiàn)象。頁(yè)走向12341251234511111

5555442

222

2111153

33

33222244444333缺頁(yè)++++++++++先進(jìn)先出淘汰算法(FIFO算法)

容易實(shí)現(xiàn)適合按線性順序訪問(wèn)地址空間的程序有的頁(yè)面經(jīng)常被訪問(wèn)，但是可能因?yàn)榇媪魰r(shí)間久而換出缺頁(yè)中斷率大概是OPT法的三倍存在Belady現(xiàn)象最近最久未使用淘汰算法（LRU算法）總是選擇最長(zhǎng)時(shí)間未被使用的那一頁(yè)淘汰。頁(yè)走向41327354132361012302144422

55533

330

033

2

1117

74442

211

110

3

333

33111

666

222

缺頁(yè)+++++

+++++

+++

+++

缺頁(yè)次數(shù)：16，缺頁(yè)率：16/20。Clock置換算法

(1)

簡(jiǎn)單的clock置換算法：每頁(yè)設(shè)置一位訪問(wèn)位。當(dāng)某頁(yè)被訪問(wèn)了，則訪問(wèn)位置“1”。內(nèi)存中的所有頁(yè)鏈接成一個(gè)循環(huán)隊(duì)列；置換算法：循環(huán)檢查各頁(yè)面的使用情況。若訪問(wèn)位為“0”，選擇該頁(yè)淘汰；若訪問(wèn)位為“1”，復(fù)位訪問(wèn)位為“0”，查詢指針前進(jìn)一步。又稱為“最近未使用”置換算法（NRU）(2)改進(jìn)型Clock置換算法：訪問(wèn)位A、修改位M，共同表示一個(gè)頁(yè)面的狀態(tài)頁(yè)面的四種狀態(tài)：

00：(A=0;M=0)最近未被訪問(wèn)也未被修改

01：(A=0;M=1)最近未被訪問(wèn)但已被修改

10：(A=1;M=0)最近已被訪問(wèn)但未被修改

11：(A=1;M=1)最近已被訪問(wèn)且被修改(2)改進(jìn)型Clock置換算法：三輪掃描：第一輪：查找A=0,M=0頁(yè)面，未找到，下一步；第二輪：查找A=0,M=1頁(yè)面，A位復(fù)位為“0”，未找到，下一步；第三輪：把所有A置為“0”，重復(fù)第一輪，必要時(shí)再重復(fù)第二輪。補(bǔ)充：頁(yè)面緩沖置換算法算法：可變分配局部置換策略，F(xiàn)IFO頁(yè)面置換算法空閑頁(yè)面鏈表：已修改頁(yè)面鏈表：空閑內(nèi)存塊空白內(nèi)存塊或未修改淘汰頁(yè)所在內(nèi)存塊已修改淘汰頁(yè)

所在內(nèi)存塊淘汰頁(yè)未被修改已被修改Windows2000空閑塊鏈表：（1）零初始化鏈表；（2）空閑鏈表；（3）后備鏈表：未修改淘汰頁(yè)；（4）修改鏈表：已修改淘汰頁(yè)修改頁(yè)面寫(xiě)回器零頁(yè)線程頁(yè)面緩沖算法舉例：（1）系統(tǒng)初始化完成后假設(shè)系統(tǒng)內(nèi)存有10個(gè)空閑塊，則相應(yīng)空閑內(nèi)存塊鏈表為：空閑頁(yè)面鏈表：已修改頁(yè)面鏈表：Null（2）創(chuàng)建P1進(jìn)程，分配4個(gè)塊，則分配到0,1,2,3四塊，此時(shí)空閑頁(yè)面鏈表變?yōu)椋?198765432987654頁(yè)面緩沖算法舉例：（3）P1裝入0,1,2,3四個(gè)頁(yè)面：（4）P1訪問(wèn)0頁(yè)、1頁(yè)、2頁(yè)，其中0頁(yè)修改，1頁(yè)、2頁(yè)不修改：0132013201320132M的值：100頁(yè)面緩沖算法舉例：（5）P1寫(xiě)第5頁(yè)，缺頁(yè)，按照FIFO，淘汰0頁(yè)，則系統(tǒng)處理方式為：已修改頁(yè)面鏈表：空閑頁(yè)面鏈表：進(jìn)程P1占據(jù)內(nèi)存情況：009876551324132M的值：1000頁(yè)面緩沖算法舉例：（6）P1讀第6頁(yè)，缺頁(yè)，按照