操作系統(tǒng)教程：虛擬存儲(chǔ)管理

4.5虛擬存儲(chǔ)管理

4.5.1虛擬存儲(chǔ)管理的概念4.5.2請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理

4.5.3請(qǐng)求分段虛擬存儲(chǔ)管理4.5.4請(qǐng)求段頁(yè)式虛擬存儲(chǔ)管理4.5.1虛擬存儲(chǔ)管理的概念(1)為什么要引入虛擬存儲(chǔ)器?虛擬存儲(chǔ)器的基本思路?！安糠盅b入、部分對(duì)換”。虛擬存儲(chǔ)管理的概念(2)

虛擬存儲(chǔ)器的定義：在具有層次結(jié)構(gòu)存儲(chǔ)器的計(jì)算機(jī)系統(tǒng)中，采用自動(dòng)實(shí)現(xiàn)部分裝入和部分對(duì)換功能，為用戶(hù)提供一個(gè)比物理主存容量大得多的，可尋址的一種“主存儲(chǔ)器”。

虛擬存儲(chǔ)管理的概念(3)

虛擬存儲(chǔ)器是為擴(kuò)大主存而采用的一種設(shè)計(jì)技巧，它的容量與主存大小無(wú)直接關(guān)系，而受限于計(jì)算機(jī)的地址結(jié)構(gòu)及可用的輔助存儲(chǔ)器的容量。

虛擬存儲(chǔ)管理的概念(4)

虛擬存儲(chǔ)器的概念圖

虛擬地址空間處理器虛地址存儲(chǔ)管理部件實(shí)地址主存輔存物理地址空間虛擬存儲(chǔ)管理的概念(5)

作業(yè)信息不全部裝入主存，能否保證作業(yè)的正確運(yùn)行？回答是肯定的,1968年P(guān).Denning研究了程序執(zhí)行時(shí)的局部性原理。

虛擬存儲(chǔ)管理的概念(6)

程序的局部性原理：指程序在執(zhí)行過(guò)程中的一個(gè)較短時(shí)間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲(chǔ)區(qū)域中。又可細(xì)分時(shí)間局部性和空間局部性。虛擬存儲(chǔ)管理的概念(7)

第一，程序中只有少量分支和過(guò)程調(diào)用，大都是順序執(zhí)行的指令。第二，程序包含若干循環(huán)，是由相對(duì)較少的指令組成，在循環(huán)過(guò)程中，計(jì)算被限制在程序中很小的相鄰部分中。虛擬存儲(chǔ)管理的概念(8)

第三，很少出現(xiàn)連續(xù)的過(guò)程調(diào)用，相反，程序中過(guò)程調(diào)用的深度限制在小范圍內(nèi)，一段時(shí)間內(nèi)，指令引用被局限在很少幾個(gè)過(guò)程中。第四，對(duì)于連續(xù)訪問(wèn)數(shù)組之類(lèi)的數(shù)據(jù)結(jié)構(gòu)，往往是對(duì)存儲(chǔ)區(qū)域中相鄰位置的數(shù)據(jù)的操作。第五，程序中有些部分是彼此互斥的，不是每次運(yùn)行時(shí)都用到的，如出錯(cuò)處理程序。

虛擬存儲(chǔ)管理的概念(9)

實(shí)現(xiàn)虛擬存儲(chǔ)器必須解決好以下有關(guān)問(wèn)題：

?主存輔存統(tǒng)一管理問(wèn)題、

?邏輯地址到物理地址的轉(zhuǎn)換問(wèn)題、

?部分裝入和部分對(duì)換問(wèn)題。虛擬存儲(chǔ)管理的概念(10)

虛擬存儲(chǔ)管理主要采用以下技術(shù)實(shí)現(xiàn)：

?請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理

?請(qǐng)求分段虛擬存儲(chǔ)管理

?請(qǐng)求段頁(yè)式虛擬存儲(chǔ)管理4.5.2分頁(yè)式虛擬存儲(chǔ)系統(tǒng)

1

分頁(yè)式虛擬存儲(chǔ)系統(tǒng)的硬件支撐(1)

主存管理單元MMU完成邏輯地址到物理地址的轉(zhuǎn)換功能，它接受虛擬地址作為輸入，物理地址作為輸出，直接送到總線上，對(duì)內(nèi)存單元進(jìn)行尋址。分頁(yè)式虛擬存儲(chǔ)系統(tǒng)的硬件支撐(2)

CPUMMU內(nèi)存CPU把邏輯地址送至MMUMMU把物理地址送至內(nèi)存MMU的位置、功能和16個(gè)4KB頁(yè)面情況下MMU的內(nèi)部操作CPU送入的邏輯地址(8196)0010000000000100110000000000100MMU送出的物理地址(24580)00101100112110130001410015011160000700008101190000…頁(yè)號(hào)頁(yè)框號(hào)在主存否MMU主要功能(1)管理硬件頁(yè)表基址寄存器。(2)分解邏輯地址。(3)管理快表TLB。(4)訪問(wèn)頁(yè)表。(5)發(fā)出缺頁(yè)中斷或越界中斷，并將控制權(quán)交給內(nèi)核存儲(chǔ)管理處理。(6)設(shè)置和檢查頁(yè)表中各個(gè)特征位。2請(qǐng)求分頁(yè)虛擬存儲(chǔ)系統(tǒng)

的基本原理(1)

分頁(yè)式虛擬存儲(chǔ)系統(tǒng)是將作業(yè)信息的副本存放在磁盤(pán)中，當(dāng)作業(yè)被調(diào)度投入運(yùn)行時(shí)，不把作業(yè)的程序和數(shù)據(jù)全部裝入主存，而僅裝入立即使用的頁(yè)面，在執(zhí)行過(guò)程中訪問(wèn)到不在主存的頁(yè)面時(shí)，產(chǎn)生缺頁(yè)中斷，再把它們動(dòng)態(tài)地裝入。

請(qǐng)求分頁(yè)虛擬存儲(chǔ)系統(tǒng)

的基本原理(2)

怎樣才能發(fā)現(xiàn)頁(yè)面不在內(nèi)存中呢?怎樣處理這種情況呢?采用的辦法是：擴(kuò)充頁(yè)表的內(nèi)容,增加駐留標(biāo)志位和頁(yè)面輔存的地址等信息。

頁(yè)式虛擬存儲(chǔ)管理頁(yè)表擴(kuò)展(1)

頁(yè)號(hào)駐留標(biāo)志

頁(yè)框號(hào)

輔存地址其它標(biāo)志

頁(yè)式虛擬存儲(chǔ)管理頁(yè)表擴(kuò)展(2)駐留標(biāo)志位(又稱(chēng)中斷位)修改位（Modified）引用位（Renferenced）訪問(wèn)位Linux的頁(yè)表項(xiàng)的主要內(nèi)容PRESENT位RWFOE位USER位WT位PCD位ACCESSED位DIRTY位4M位PFN請(qǐng)求分頁(yè)虛存地址轉(zhuǎn)換過(guò)程(1)

邏輯空間地址主存(用戶(hù)區(qū))CPU邏輯地址快表主存(系統(tǒng)區(qū))運(yùn)行進(jìn)程頁(yè)表輔存缺頁(yè)中斷處理①分解地址③⑤訪問(wèn)MMU②查快表③命中④不命中⑤頁(yè)表命中⑦發(fā)缺頁(yè)中斷⑧調(diào)頁(yè)⑨裝入、改表④查頁(yè)表運(yùn)行進(jìn)程頁(yè)表基址⑥裝入快表運(yùn)行進(jìn)程映象進(jìn)程切換時(shí)裝入物理地址頁(yè)框

頁(yè)內(nèi)地址頁(yè)號(hào)頁(yè)內(nèi)地址請(qǐng)求分頁(yè)虛存地址轉(zhuǎn)換過(guò)程(2)

查快表有登記無(wú)登記查頁(yè)表登記入快表發(fā)缺頁(yè)中斷在主存在輔存形成絕對(duì)地址繼續(xù)執(zhí)行指令重新執(zhí)行被中斷指令恢復(fù)現(xiàn)場(chǎng)調(diào)整頁(yè)表和主存分配表裝入所需頁(yè)面主存有空閑塊保護(hù)現(xiàn)場(chǎng)有選擇調(diào)出頁(yè)面該頁(yè)是否修改未修改已修改把該頁(yè)寫(xiě)回輔存相應(yīng)位置操作系統(tǒng)硬件邏輯地址無(wú)請(qǐng)求頁(yè)式存儲(chǔ)管理IBM/370系統(tǒng)的VS/1，VS/2和VM/370，Honeywell6180的MULTICSUNIVAC系列70/64的VMS請(qǐng)求頁(yè)式虛擬存儲(chǔ)系統(tǒng)優(yōu)缺點(diǎn)

?優(yōu)點(diǎn)：作業(yè)的程序和數(shù)據(jù)可按頁(yè)分散存放在內(nèi)存中，減少移動(dòng)開(kāi)銷(xiāo)，有效解決了碎片問(wèn)題;既有利于改進(jìn)主存利用率，又有利于多道程序運(yùn)行。

?缺點(diǎn)：要有硬件支持，要進(jìn)行缺頁(yè)中斷處理，機(jī)器成本增加，系統(tǒng)開(kāi)銷(xiāo)加大。3頁(yè)面裝入策略和清除策略(1)

頁(yè)面裝入主存,有兩種策略：

?請(qǐng)頁(yè)式調(diào)度

?預(yù)調(diào)式調(diào)度頁(yè)面裝入策略和清除策略(2)

請(qǐng)頁(yè)式調(diào)度需要訪問(wèn)程序和數(shù)據(jù)時(shí)，才把所在頁(yè)面裝入主存。根據(jù)局部性原理,一段時(shí)間后,缺頁(yè)中斷會(huì)下降到很低水平,程序進(jìn)入相對(duì)平穩(wěn)階段。缺點(diǎn)是處理缺頁(yè)中斷和調(diào)頁(yè)的系統(tǒng)開(kāi)銷(xiāo)較大，每次僅調(diào)一頁(yè),增加了磁盤(pán)I/O次數(shù)。頁(yè)面裝入策略和清除策略(3)

預(yù)調(diào)式調(diào)度系統(tǒng)預(yù)測(cè)進(jìn)程將要使用的頁(yè)面,使用前預(yù)先調(diào)入主存,每次調(diào)入若干頁(yè)面,而不是僅調(diào)一頁(yè)。一次調(diào)入多頁(yè)能減少磁盤(pán)I/O啟動(dòng)次數(shù),節(jié)省尋道和搜索時(shí)間。如果調(diào)入的一批頁(yè)面中多數(shù)未被使用,則效率就很低了，可見(jiàn)預(yù)調(diào)頁(yè)要建立在預(yù)測(cè)的基礎(chǔ)上。頁(yè)面裝入策略和清除策略(4)

清除策略(1)考慮何時(shí)把一個(gè)修改過(guò)的頁(yè)面寫(xiě)回輔存儲(chǔ)器:請(qǐng)頁(yè)式清除和預(yù)清除。請(qǐng)頁(yè)式清除是僅當(dāng)一頁(yè)選中被替換,且之前它又被修改過(guò),才把這個(gè)頁(yè)面寫(xiě)回輔存。

頁(yè)面裝入策略和清除策略(5)

清除策略(2)預(yù)清除，寫(xiě)出頁(yè)仍在內(nèi)存中,直到頁(yè)替換算法選中一頁(yè)從內(nèi)存中移出,成批地把頁(yè)面寫(xiě)出，但如若剛寫(xiě)出了很多頁(yè)面，在被替換前，其中大部分又被更改，預(yù)清除就毫無(wú)意義。請(qǐng)頁(yè)式清除，寫(xiě)出一頁(yè)是在讀進(jìn)新頁(yè)前進(jìn)行的，要成雙操作,引起進(jìn)程等待兩次I/O操作，會(huì)降低CPU使用效率。頁(yè)面裝入策略和清除策略(6)

頁(yè)緩沖策略策略如下:僅清除淘汰的頁(yè)面，并使清除操作和替換操作不必成雙進(jìn)行。在頁(yè)緩沖中，淘汰了的頁(yè)面進(jìn)入兩個(gè)隊(duì)列：修改頁(yè)面和非修改頁(yè)面隊(duì)列。修改頁(yè)面隊(duì)列中的頁(yè)的不時(shí)地成批寫(xiě)出并加入到非修改頁(yè)面隊(duì)列;非修改頁(yè)面隊(duì)列中的頁(yè)面，當(dāng)它被再次引用時(shí)回收，或者淘汰掉以作替換。4頁(yè)面分配策略：考慮因素

系統(tǒng)為進(jìn)程分配主存,需考慮因素:①分給進(jìn)程的空間越小,同一時(shí)間處于內(nèi)存的進(jìn)程就越多，至少有一個(gè)進(jìn)程處于就緒態(tài)的可能性就越大②如果進(jìn)程只有小部分在主存里,即使局部性很好,缺頁(yè)中斷率還會(huì)相當(dāng)③因程序的局部性原理，分給進(jìn)程的內(nèi)存超過(guò)一定限度后，再增加內(nèi)存空間,不會(huì)明顯降低進(jìn)程的缺頁(yè)中斷率。頁(yè)面分配策略：固定分配

進(jìn)程保持頁(yè)框數(shù)固定不變,稱(chēng)固定分配;進(jìn)程創(chuàng)建時(shí),根據(jù)進(jìn)程類(lèi)型和程序員的要求決定頁(yè)框數(shù),只要有一個(gè)缺頁(yè)中斷產(chǎn)生,進(jìn)程就會(huì)有一頁(yè)被替換。頁(yè)面分配策略：可變分配

進(jìn)程分得的頁(yè)框數(shù)可變,稱(chēng)可變分配;進(jìn)程執(zhí)行的某階段缺頁(yè)率較高,說(shuō)明目前局部性較差，系統(tǒng)可多分些頁(yè)框以降低缺頁(yè)率，反之說(shuō)明進(jìn)程目前的局部性較好,可減少分給進(jìn)程的頁(yè)框數(shù)頁(yè)面分配策略：分析

固定分配缺少靈活性，而可變分配的性能會(huì)更好些,被許多操作系統(tǒng)采用。采用可變分配策略的困難在于操作系統(tǒng)要經(jīng)常監(jiān)視活動(dòng)進(jìn)程的行為和進(jìn)程缺頁(yè)中斷率的情況,會(huì)增加系統(tǒng)的開(kāi)銷(xiāo)。

頁(yè)面替換策略：局部替換和全局替換如果頁(yè)面替換算法的作用范圍是整個(gè)系統(tǒng)，稱(chēng)全局頁(yè)面替換算法,它可以在運(yùn)行進(jìn)程間動(dòng)態(tài)地分配頁(yè)框。如果頁(yè)面替換算法的作用范圍局限于本進(jìn)程，稱(chēng)為局部頁(yè)面替換算法,它實(shí)際上需要為每個(gè)進(jìn)程分配固定的頁(yè)框。 固定分配和局部替換策略配合使用(1)

?進(jìn)程分得的頁(yè)框數(shù)不變，發(fā)生缺頁(yè)中斷，只能從進(jìn)程的頁(yè)面中選頁(yè)替換，保證進(jìn)程的頁(yè)框總數(shù)不變。

?策略難點(diǎn)：應(yīng)給每個(gè)進(jìn)程分配多少頁(yè)框?給少了,缺頁(yè)中斷率高;給多了,使內(nèi)存中能同時(shí)執(zhí)行的進(jìn)程數(shù)減少，進(jìn)而造成處理器和其它設(shè)備空閑。固定分配和局部替換策略配合使用(2)

采用固定分配算法，系統(tǒng)把頁(yè)框分配給進(jìn)程，采用：①平均分配，②按比例分配,③優(yōu)先權(quán)分配,?？勺兎峙浜腿痔鎿Q策略配合使用

?先每個(gè)進(jìn)程分配一定數(shù)目頁(yè)框,os保留若干空閑頁(yè)框,進(jìn)程發(fā)生缺頁(yè)中斷時(shí)，從系統(tǒng)空閑頁(yè)框中選一個(gè)給進(jìn)程,這樣產(chǎn)生缺頁(yè)中斷進(jìn)程的內(nèi)存空間會(huì)逐漸增大,有助于減少系統(tǒng)的缺頁(yè)中斷次數(shù)。

?系統(tǒng)擁有的空閑頁(yè)框耗盡時(shí)，會(huì)從內(nèi)存中選擇一頁(yè)淘汰，該頁(yè)可以是內(nèi)存中任一進(jìn)程的頁(yè)面，這樣又會(huì)使那個(gè)進(jìn)程的頁(yè)框數(shù)減少，缺頁(yè)中斷率上升?？勺兎峙浜途植刻鎿Q配合使用

其實(shí)現(xiàn)要點(diǎn)如下:(1)新進(jìn)程裝入主存時(shí)，根據(jù)應(yīng)用類(lèi)型、程序要求，分配給一定數(shù)目頁(yè)框,可用請(qǐng)頁(yè)式或預(yù)調(diào)式完成這個(gè)分配。(2)產(chǎn)生缺頁(yè)中斷時(shí),從該進(jìn)程駐留集中選一個(gè)頁(yè)面替換。(3)不時(shí)重新評(píng)價(jià)進(jìn)程的分配，增加或減少分配給進(jìn)程的頁(yè)框以改善系統(tǒng)性能。5頁(yè)面替換策略

?頁(yè)面替換

?頁(yè)面淘汰算法

?“抖動(dòng)”(Thrashing)現(xiàn)象

影響缺頁(yè)中斷率的因素(1)

假定作業(yè)p共計(jì)n頁(yè)，系統(tǒng)分配給它的主存塊只有m塊（１≤m≤n）。如果作業(yè)p在運(yùn)行中成功的訪問(wèn)次數(shù)為s，不成功的訪問(wèn)次數(shù)為F，則總的訪問(wèn)次數(shù)Ａ為：A=S+F

又定義：f=F/A影響缺頁(yè)中斷率的因素(2)

稱(chēng)f為缺頁(yè)中斷率。影響缺頁(yè)中斷率f的因素有：

(1)主存頁(yè)框數(shù)。

(2)頁(yè)面大小。

(3)頁(yè)面替換算法。

(4)程序特性。影響缺頁(yè)中斷率的因素(3)

程序要將128×128的數(shù)組置“0”。分給的主存只一塊，頁(yè)面尺寸為每頁(yè)128個(gè)字，數(shù)組中的元素每行存放在一頁(yè)中。若程序如下：VarA:array[1..128]ofarray[1..128]ofinteger;forj:=1to128

fori:=1to128doA[i][j]:=0影響缺頁(yè)中斷率的因素(4)

每執(zhí)行一次Ａ[i][j]:＝０要產(chǎn)生一次缺頁(yè)中斷，總共要產(chǎn)生（128×128－1）次缺頁(yè)中斷。影響缺頁(yè)中斷率的因素(5)

如果重新編制程序如下：VarA:array[1..128]ofarray[1..128]ofinteger;fori:=1to128doforj:=1to128doA[i][j]:=0

總共產(chǎn)生（128－1）次缺頁(yè)中斷。一個(gè)理論算法(最佳替換算法)調(diào)入一頁(yè)而必須淘汰一個(gè)舊頁(yè)時(shí)，所淘汰的頁(yè)應(yīng)該是以后不再訪問(wèn)的頁(yè)或距現(xiàn)在最長(zhǎng)時(shí)間后再訪問(wèn)的頁(yè)。Belady算法（Optimal），可用來(lái)作為衡量各種具體算法的標(biāo)準(zhǔn)。1）隨機(jī)頁(yè)面替換算法要淘汰的頁(yè)面是由一個(gè)隨機(jī)數(shù)產(chǎn)生程序所產(chǎn)生的隨機(jī)數(shù)來(lái)確定,選擇一個(gè)不常使用的頁(yè)面會(huì)使系統(tǒng)性能較好,但這種調(diào)度算法做不到這一點(diǎn),雖很簡(jiǎn)單但效率卻低。2)先進(jìn)先出頁(yè)面替換算法（FIFO)基于程序總是按線性順序來(lái)訪問(wèn)物理空間這一假設(shè)。算法總是淘汰最先調(diào)入主存的那一頁(yè)，或者說(shuō)在主存中駐留時(shí)間最長(zhǎng)的那一頁(yè)（常駐的除外）。FIFO實(shí)現(xiàn)技術(shù)系統(tǒng)中設(shè)置一張具有m個(gè)元素的頁(yè)號(hào)表，它是Ｍ個(gè)數(shù)：P[0],P[1],…,P[m-1]

組成的數(shù)組，每個(gè)P[i](i=0,1,…m-1)存儲(chǔ)一個(gè)在主存中的頁(yè)面的頁(yè)號(hào)。用指針k指示當(dāng)前調(diào)入新頁(yè)時(shí)應(yīng)淘汰的那一頁(yè)在頁(yè)號(hào)表中的位置。每當(dāng)調(diào)入一個(gè)新頁(yè)后，執(zhí)行P[k]:=新頁(yè)的頁(yè)號(hào);k:=（k+1）modm;FIFO另一個(gè)實(shí)現(xiàn)算法引入指針鏈成隊(duì)列，只要把進(jìn)入主存的頁(yè)面按時(shí)間的先后次序鏈接,新進(jìn)入的頁(yè)面從隊(duì)尾入隊(duì),淘汰總是從隊(duì)列頭進(jìn)行。3）最近最少用頁(yè)面替換算法LRU

算法淘汰的頁(yè)面是在最近一段時(shí)間里較久未被訪問(wèn)的那頁(yè)。根據(jù)程序局部性原理，那些剛被使用過(guò)的頁(yè)面，可能馬上還要被使用，而在較長(zhǎng)時(shí)間里未被使用的頁(yè)面，可能不會(huì)馬上使用到。LRU算法實(shí)現(xiàn)：頁(yè)面淘汰隊(duì)列(1)隊(duì)列中存放當(dāng)前在主存中的頁(yè)號(hào)，每當(dāng)訪問(wèn)一頁(yè)時(shí)就調(diào)整一次，使隊(duì)列尾總指向最近訪問(wèn)的頁(yè)，隊(duì)列頭就是最近最少用的頁(yè)。發(fā)生缺頁(yè)中斷時(shí)總淘汰隊(duì)列頭所指示的頁(yè)；執(zhí)行一次頁(yè)面訪問(wèn)后，需要從隊(duì)列中把該頁(yè)調(diào)整到隊(duì)列尾。LRU算法實(shí)現(xiàn)：頁(yè)面淘汰隊(duì)列(2)例：給某作業(yè)分配了三塊主存，該作業(yè)依次訪問(wèn)的頁(yè)號(hào)為：4，3，0，4，1，1，2，3，2。當(dāng)訪問(wèn)這些頁(yè)時(shí)，頁(yè)面淘汰序列變化情況如下LRU算法實(shí)現(xiàn)：頁(yè)面淘汰隊(duì)列(3)

訪問(wèn)頁(yè)號(hào)頁(yè)面淘汰序列被淘汰頁(yè)面

443430430430410413104124120312342132LRU算法實(shí)現(xiàn)：標(biāo)志位法每頁(yè)設(shè)置一個(gè)引用標(biāo)志位R，訪問(wèn)某頁(yè)時(shí)，由硬件將頁(yè)標(biāo)志位R置1，隔一定時(shí)間t將所有頁(yè)的標(biāo)志R均清0。發(fā)生缺頁(yè)中斷時(shí)，從標(biāo)志位R為0的頁(yè)中挑選一頁(yè)淘汰。挑選到要淘汰的頁(yè)后，也將所有頁(yè)的標(biāo)志位R清0。LRU算法實(shí)現(xiàn)：多位寄存器法(1)為每個(gè)頁(yè)設(shè)置一個(gè)多位寄存器，當(dāng)頁(yè)面被訪問(wèn)時(shí)，對(duì)應(yīng)的寄存器的最左邊位置1；每隔時(shí)間t，將r寄存器右移一位；發(fā)生缺頁(yè)中斷時(shí)，找最小數(shù)值的r寄存器對(duì)應(yīng)的頁(yè)面淘汰。LRU算法實(shí)現(xiàn)：多位寄存器法(2)例如，r寄存器共有四位，頁(yè)面P0、P1、P2在T1、T2、T3時(shí)刻的r寄存器內(nèi)容如下：

頁(yè)面時(shí)刻

T1T2T3P0

1000

0100 1010P1

10001100

0110P2

00001000

0100

LRU算法實(shí)現(xiàn)：多位計(jì)數(shù)器法每個(gè)頁(yè)面設(shè)置一個(gè)多位計(jì)數(shù)器，又叫最不常用頁(yè)面替換算法LFU。每當(dāng)訪問(wèn)一頁(yè)時(shí)，就使它對(duì)應(yīng)的計(jì)數(shù)器加１。當(dāng)發(fā)生缺頁(yè)中斷時(shí)，可選擇計(jì)數(shù)值最小的對(duì)應(yīng)頁(yè)面淘汰，并將所有計(jì)數(shù)器全部清０。

LRU算法實(shí)現(xiàn)：多位計(jì)時(shí)器法為每個(gè)頁(yè)面設(shè)置一個(gè)多位計(jì)時(shí)器，每當(dāng)頁(yè)面被訪問(wèn)時(shí)，系統(tǒng)的絕對(duì)時(shí)間記入計(jì)時(shí)器。比較各頁(yè)面的計(jì)時(shí)器的值，選最小值的未使用的頁(yè)面淘汰，因?yàn)?，它是最“老”的未使用的?yè)面。4)第二次機(jī)會(huì)頁(yè)面替換算法(1)

改進(jìn)FIFO算法,把FIFO與頁(yè)表中的”引用位”結(jié)合起來(lái)使用：

?檢查FIFO中的隊(duì)首頁(yè)面(最早進(jìn)入主存的頁(yè)面),如果它的”引用位”是0,這個(gè)頁(yè)面既老又沒(méi)有用，選擇該頁(yè)面淘汰;

第二次機(jī)會(huì)頁(yè)面替換算法(2)

?如果”引用位”是1,說(shuō)明它進(jìn)入主存較早，但最近仍在使用。把它的”引用位”清0,并把這個(gè)頁(yè)面移到隊(duì)尾，把它看作是一個(gè)新調(diào)入的頁(yè)。

?算法含義：最先進(jìn)入主存的頁(yè)面，如果最近還在被使用的話,仍然有機(jī)會(huì)作為像一個(gè)新調(diào)入頁(yè)面一樣留在主存中。5）時(shí)鐘頁(yè)面替換算法(ClockPolicy)(1)

算法實(shí)現(xiàn)要點(diǎn)(1)：?

一個(gè)頁(yè)面首次裝入主存，其“引用位”置0。主存中的任何頁(yè)面被訪問(wèn)時(shí),”引用位”置1。淘汰頁(yè)面時(shí),從指針當(dāng)前指向的頁(yè)面開(kāi)始掃描循環(huán)隊(duì)列，把遷到的”引用位”是1的頁(yè)面的”引用位”清0,跳過(guò)這個(gè)頁(yè)面;把所遷到的”引用位”是0的頁(yè)面淘汰掉,指針推進(jìn)一步。時(shí)鐘頁(yè)面替換算法

(ClockPolicy)(2)

算法實(shí)現(xiàn)要點(diǎn)(2)：掃描循環(huán)隊(duì)列時(shí)，如果遷到的所有頁(yè)面的”引用位”為1，指針就會(huì)繞整個(gè)循環(huán)隊(duì)列一圈，把碰到的所有頁(yè)面的”引用位”清0;指針停在起始位置，并淘汰掉這一頁(yè),然后，指針推進(jìn)一步。時(shí)鐘頁(yè)面替換算法的一個(gè)例子

Page9use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page33Use=1Page222Use=0下一個(gè)幀指針n012345678一個(gè)頁(yè)替換前的緩沖區(qū)狀態(tài)Page9use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=1Page727Use=1Page13Use=0Page67Use=1Page33Use=1Page222Use=0n012345678下一頁(yè)替換后的緩沖區(qū)狀態(tài)第1頁(yè)框時(shí)鐘頁(yè)面替換改進(jìn)算法(1)把”引用位”和”修改位”結(jié)合起來(lái)使用，共組合成四種情況：(1)最近沒(méi)有被引用,沒(méi)有被修改(r=0,m=0)(2)最近被引用,沒(méi)有被修改(r=1,m=0)(3)最近沒(méi)有被引用,但被修改(r=0,m=1)(4)最近被引用過(guò),也被修改過(guò)(r=1,m=1)時(shí)鐘頁(yè)面替換改進(jìn)算法(2)

步1：選擇最佳淘汰頁(yè)面，從指針當(dāng)前位置開(kāi)始,掃描循環(huán)隊(duì)列。掃描過(guò)程中不改變”引用位”，把迂到的第一個(gè)r=0,m=0的頁(yè)面作為淘汰頁(yè)面。步2：如果步1失敗，再次從原位置開(kāi)始，查找r=0且m=1的頁(yè)面，把把迂到的第一個(gè)這樣的頁(yè)面作為淘汰頁(yè)面，而在掃描過(guò)程中把指針?biāo)鶔哌^(guò)的頁(yè)面的”引用位”r置0。時(shí)鐘頁(yè)面替換改進(jìn)算法(3)

步3：如果步2失敗，指針再次回到了起始位置，由于此時(shí)所有頁(yè)面的”引用位”r均己為0，再轉(zhuǎn)向步1操作，必要時(shí)再做步2操作，這次一定可以挑出一個(gè)可淘汰的頁(yè)面。UNIXSVR4雙指針clock算法引用位前指針和后指針兩個(gè)指針掃描頁(yè)表的速度兩個(gè)指針之間時(shí)間間隔的選擇

一個(gè)例子，計(jì)算缺頁(yè)中斷次數(shù)和被淘汰頁(yè)面(1)假設(shè)采用固定分配策略，進(jìn)程分得三個(gè)頁(yè)框,執(zhí)行中按下列次序引用5個(gè)獨(dú)立的頁(yè)面:232152453252。一個(gè)例子，計(jì)算缺頁(yè)中斷次數(shù)和被淘汰頁(yè)面(2)一個(gè)例子，計(jì)算缺頁(yè)中斷次數(shù)和被淘汰頁(yè)面(3)一個(gè)例子，計(jì)算缺頁(yè)中斷次數(shù)和被淘汰頁(yè)面(4)

性能比較OPTF(1)F(2)F(4)LRU

F(3)F(1)F(2)F(4)CLOCKF(2)F(3)F(1)F(5)F(4)FIFOF(1)F(3)F(1)F(5)F(2)F(4)計(jì)算缺頁(yè)中斷實(shí)例(1)

假設(shè)固定分配,運(yùn)行FORTRAN程序,共有0.25×106次頁(yè)面引用，頁(yè)面大小為256個(gè)字。分給進(jìn)程的頁(yè)框數(shù)分別為6、8、10、12和14。FIFO所產(chǎn)生的缺頁(yè)中斷基本上是Opt的2倍,Clock則比較接近于LRU。計(jì)算缺頁(yè)中斷實(shí)例(2)

051015202535403006686101214

FIFO

CLOCK

LRU

OPT分配的頁(yè)數(shù)每千次訪問(wèn)的缺頁(yè)中斷數(shù)

6請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理的幾個(gè)設(shè)計(jì)問(wèn)題

(1)頁(yè)面大小

.從頁(yè)表大小考慮

.從主存利用率考慮

.從讀寫(xiě)一個(gè)頁(yè)面所需時(shí)間考慮

最佳頁(yè)面尺寸(1)

假定S表示用戶(hù)作業(yè)程序的字節(jié)數(shù)平均長(zhǎng)度，P表示以字節(jié)為單位的頁(yè)面長(zhǎng)度，且有S>>P，頁(yè)表項(xiàng)需要e個(gè)字節(jié)。作業(yè)的頁(yè)表長(zhǎng)度為S/P，占用了Se/P個(gè)字節(jié)的頁(yè)表空間，作業(yè)的最后一頁(yè)，浪費(fèi)的主存平均為P/2字節(jié)。對(duì)一個(gè)作業(yè)而言：

浪費(fèi)的存儲(chǔ)字=頁(yè)表使用的主存空間+內(nèi)部碎片=Se/P+P/2最佳頁(yè)面尺寸(2)

頁(yè)面較小時(shí)頁(yè)表占用空間多(因Se/P較大)，頁(yè)面較大時(shí)內(nèi)部碎片浪費(fèi)多(因P/2較大)。現(xiàn)對(duì)P求一階導(dǎo)數(shù)并令其為0，得到

-Se/P2+1/2=0

那么，可以得出最優(yōu)頁(yè)面尺寸

P=開(kāi)根號(hào)2Se

時(shí)，浪費(fèi)的存儲(chǔ)字節(jié)最少，稱(chēng)P為最佳頁(yè)面尺寸。對(duì)于S=128KB，每個(gè)頁(yè)表項(xiàng)e=8B時(shí)，最優(yōu)頁(yè)面尺寸是1448字節(jié)

著名操作系統(tǒng)選擇的頁(yè)面尺寸Atlas為512字(每字48位)、IBM370系列機(jī)為2048或4096字節(jié)、VAX為512字節(jié)、IBMas/400為512字節(jié)、Intel486和Motorola68040為4096字節(jié)。(2)工作集模型(1)

P.J.Denning認(rèn)為，應(yīng)該將處理機(jī)調(diào)度和主存管理結(jié)合起來(lái)進(jìn)行考慮，并在1968年提出了工作集模型。工作集模型(2)

?工作集--“在未來(lái)的時(shí)間間隔內(nèi)，一個(gè)進(jìn)程運(yùn)行時(shí)所需訪問(wèn)的頁(yè)面集”。工作集模型(3)

時(shí)間過(guò)渡工作集過(guò)渡工作集第2個(gè)工作集第1個(gè)工作集過(guò)渡工作集第3個(gè)工作集第4個(gè)工作集工作集頁(yè)面數(shù)工作集的演變過(guò)程(1)

工作集的演變過(guò)程(2)作業(yè)占用的主存塊數(shù)目小于工作集，運(yùn)行中會(huì)不斷出現(xiàn)缺頁(yè)中斷，為保證作業(yè)有效運(yùn)行，應(yīng)該根據(jù)工作集大小分給它主存塊，以保證工作集中所需要的頁(yè)面能夠進(jìn)入主存。為了避免系統(tǒng)發(fā)生抖動(dòng)，就應(yīng)該限制系統(tǒng)內(nèi)的作業(yè)數(shù)，使它們的工作集總尺寸不超過(guò)主存塊總數(shù)。工作集和工作集窗口(1)

用W(t,△)表示從時(shí)刻t-△到時(shí)刻t之間所訪問(wèn)的不同頁(yè)面的集合，t是進(jìn)程實(shí)際耗用的時(shí)間,可以通過(guò)執(zhí)行的指令周期來(lái)計(jì)算;△是時(shí)間窗口尺寸,通過(guò)窗口來(lái)觀察進(jìn)程的行為。W(t,△)就是作業(yè)在時(shí)刻t的工作集,表示在最近△個(gè)實(shí)際時(shí)間單位內(nèi)進(jìn)程所引用過(guò)的頁(yè)面的集合;工作集和工作集窗口(2)

∣W(t,△)∣表示工作集中的頁(yè)面數(shù)目,稱(chēng)工作集尺寸。如果系統(tǒng)能隨∣W(t,△)∣的大小來(lái)分配主存塊，就既能有效利用主存，又可使缺頁(yè)中斷盡量少地發(fā)生,或者說(shuō)程序要有效運(yùn)行，其工作集必須在主存中。

工作集和工作集窗口(3)

工作集W是t的函數(shù)，隨時(shí)間不同，工作集也不同。其一是不同時(shí)間的工作集包含的頁(yè)面數(shù)可能不同；其二是不同時(shí)間的工作集包含的頁(yè)面可能不同。工作集W又是工作集窗口尺寸△的函數(shù)，而且工作集尺寸∣W（t，△）∣是工作集窗口尺寸△的非遞減函數(shù)。

24151823241718241817171524172418241524181523182423172418172418182417181715172415172424171824241524181524231815242318172423181724****151718241517**18241724152418152423181524*17242318*****15171824****24152418152423181524*1724231815**********5234窗口大小頁(yè)面訪問(wèn)序列工作集和工作集窗口(4)正確選擇工作集窗口尺寸如果△過(guò)大，甚至把作業(yè)地址空間全包括在內(nèi)，就成了實(shí)存管理;如果△過(guò)小，則會(huì)引起頻繁缺頁(yè),降低了系統(tǒng)的效率。通過(guò)工作集概念來(lái)指導(dǎo)確定駐留集的大小(1)監(jiān)視每個(gè)進(jìn)程的工作集。

(2)定期地從一個(gè)進(jìn)程駐留集中刪去那些不在工作集中的頁(yè)。

(3)僅當(dāng)一個(gè)進(jìn)程的工作集在主存即駐留集包含了它的工作集時(shí)，進(jìn)程才能執(zhí)行。

頁(yè)面故障率是分配頁(yè)框數(shù)的函數(shù)

頁(yè)面故障率（PageFaultFrequency）包括LRU在內(nèi)的一大類(lèi)頁(yè)面替換算法的故障率隨著分配的頁(yè)框數(shù)的增加而減少PFF試圖把頁(yè)面故障率保持在一個(gè)可接受的范圍內(nèi)。(3)頁(yè)面交換區(qū)替換算法要挑選頁(yè)面淘汰出主存，但被淘汰出去的頁(yè)面可能很快使用，又要被重新裝入主存。操作系統(tǒng)必須保存被淘汰的頁(yè)面,例如UNIX使用交換區(qū)臨時(shí)保存頁(yè)面，系統(tǒng)初始化時(shí),保留一定盤(pán)空間作交換區(qū)。(4)鎖定主存頁(yè)

如果采用全局替換策略，鎖住正在做I/O操作的內(nèi)存頁(yè)面，保證它不被移出，可以在頁(yè)表項(xiàng)中增加鎖定位來(lái)做到這一點(diǎn)。另一種解決方法是在核心內(nèi)的緩沖區(qū)完成I/O，然后，把數(shù)據(jù)復(fù)制到用戶(hù)的頁(yè)面。(5)寫(xiě)時(shí)復(fù)制(1)寫(xiě)時(shí)復(fù)制(copy-on-write)是存儲(chǔ)管理節(jié)省物理內(nèi)存(頁(yè)框)的一種頁(yè)面級(jí)優(yōu)化技術(shù),已被UNIX和Windows等采用，能減少主存頁(yè)面內(nèi)容的復(fù)制操作,減少相同內(nèi)容頁(yè)面在主存的副本數(shù)目。(5)寫(xiě)時(shí)復(fù)制(2)

原始數(shù)據(jù)原始數(shù)據(jù)原始數(shù)據(jù)進(jìn)程地址空間物理地址空間原始數(shù)據(jù)原始數(shù)據(jù)原始數(shù)據(jù)進(jìn)程地址空間物理地址空間原始數(shù)據(jù)原始數(shù)據(jù)原始數(shù)據(jù)進(jìn)程地址空間原始數(shù)據(jù)原始數(shù)據(jù)原始數(shù)據(jù)進(jìn)程地址空間頁(yè)面2副本頁(yè)面1頁(yè)面2頁(yè)面3頁(yè)面1頁(yè)面2頁(yè)面34.5.3請(qǐng)求分段虛擬存儲(chǔ)系統(tǒng)

分段式虛擬存儲(chǔ)系統(tǒng)把作業(yè)的所有分段的副本都存放在輔助存儲(chǔ)器中，當(dāng)作業(yè)被調(diào)度投入運(yùn)行時(shí)，首先把當(dāng)前需要的一段或幾段裝入主存，在執(zhí)行過(guò)程中訪問(wèn)到不在主存的段時(shí)再把它們裝入。段式虛擬存儲(chǔ)管理的段表擴(kuò)展(1)

段號(hào)擴(kuò)充位主存始址特征存取權(quán)限輔存始址標(biāo)志限長(zhǎng)

段式虛擬存儲(chǔ)管理的段表擴(kuò)展(2)

特征位:00(不在內(nèi)存)；01(在內(nèi)存)；11(共享段)；存取權(quán)限:0