1、2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院1第五章 存儲(chǔ)器管理5.1 虛擬存儲(chǔ)器的基本概念5.2 請(qǐng)求分頁存儲(chǔ)管理方式5.3 頁面置換算法5.4 “抖動(dòng)”與工作集5.5 請(qǐng)求分段存儲(chǔ)管理方式2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院25.1 虛擬存儲(chǔ)器的基本概念5.1.1 虛擬存儲(chǔ)器的引入（1） 常規(guī)存儲(chǔ)器管理方式的特征 一次性、駐留性（2）局部性原理：時(shí)間、空間局限性（3）虛擬存儲(chǔ)器的定義：具有請(qǐng)求調(diào)入和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)系統(tǒng)。2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院3虛擬存儲(chǔ)器的容量o 一個(gè)虛擬存儲(chǔ)器容量是由計(jì)算機(jī)的總線地址結(jié)構(gòu)確定的。如：若CPU的有

2、效地址長(zhǎng)度為32位，則程序可以尋址范圍是0 232 -1 ，即虛存容量為 4GB。o 以CPU時(shí)間和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)。2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院4例題1o 設(shè)主存容量為1MB，外存容量為400MB，計(jì)算機(jī)系統(tǒng)的地址寄存器有32位，那么虛擬存儲(chǔ)器的最大容量是（ ）o 1MBo 401MBo 1MB+232BA. 232BD2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院55.1.2 虛擬存儲(chǔ)器的特征 n離散性：在分配內(nèi)存時(shí)采用離散分配方式n多次性：一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行n對(duì)換性：允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)、換出。n虛擬性：能夠從邏輯

3、上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。 虛擬性以多次性和對(duì)換性為基礎(chǔ)；多次性和對(duì)換性又必須建立在離散分配的基礎(chǔ)上。2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院6例題2o 下列關(guān)于虛擬存儲(chǔ)器的敘述中，正確的是（ ）o 虛擬存儲(chǔ)只能基于連續(xù)分配技術(shù)o 虛擬存儲(chǔ)只能基于非連續(xù)分配技術(shù)o 虛擬存儲(chǔ)容量只受外存容量的限制o 虛擬存儲(chǔ)容量只受內(nèi)存容量的限制B2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院75.1.3 虛擬存儲(chǔ)器的實(shí)現(xiàn)方法 需要?jiǎng)討B(tài)重定位一、請(qǐng)求分頁系統(tǒng) 以頁為單位轉(zhuǎn)換 需硬件：（1）請(qǐng)求分頁的頁表機(jī)制（2）缺頁中斷（3）地址變換機(jī)構(gòu) 需實(shí)現(xiàn)請(qǐng)求分頁機(jī)制的軟件（置換軟件等）

4、二、請(qǐng)求分段系統(tǒng) 以段為單位轉(zhuǎn)換:（1）請(qǐng)求分段的段表結(jié)構(gòu)（2）缺段中斷（3）地址變換機(jī)構(gòu) 需實(shí)現(xiàn)請(qǐng)求分段機(jī)制的軟件（置換軟件等）2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院85.2 請(qǐng)求分頁存儲(chǔ)管理方式 2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院92. 缺頁中斷機(jī)構(gòu)TO B指令copy A A: B:頁面6543212022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院103. 地址變換機(jī)構(gòu) 缺頁中斷處理保留CPU現(xiàn)場(chǎng)從外存中找到缺頁內(nèi)存滿否？選擇一頁換出該頁被修改否？將該頁寫回外存OS命令CPU從外存讀缺頁啟動(dòng)I/O 硬件將一頁從外存換入內(nèi)存修改頁表否是是否頁表項(xiàng)在快表中？CPU檢索快表訪問頁表否

5、頁在內(nèi)存？修改訪問位和修改位形成物理地址地址變換結(jié)束否頁號(hào)頁表長(zhǎng)度?開始程序請(qǐng)求訪問一頁產(chǎn)生缺頁中斷請(qǐng)求調(diào)頁修改快表是越界中斷是是2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院11在為進(jìn)程分配物理塊時(shí)，要解決下列的三個(gè)問題：（1 1） 保證進(jìn)程可正常運(yùn)行所需要的最少物理塊數(shù) 最小物理塊數(shù)的確定（2 2） 每個(gè)進(jìn)程的物理塊數(shù)，是固定值還是可變值 物理塊的分配策略（3 3） 不同進(jìn)程所分配的物理塊數(shù)，是采用平均分配算法還是根據(jù)進(jìn)程的大小按照比例予以分配。 物理塊的分配算法2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院12如： mov A, B允許間接尋址：則至少要求3個(gè)物理塊。mov A,B1000X

6、XXX若是單地址指令，且采用直接尋址方式，則所需最少物理塊數(shù)為2。2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院132. 物理塊的分配策略 2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院141）固定分配局部置換思路：分配固定數(shù)目的內(nèi)存空間（物理塊），在整個(gè)運(yùn)行期間都不改變策略：如果缺頁，則先從該進(jìn)程在內(nèi)存的頁面中選中一頁，進(jìn)行換出操作，然后再調(diào)入一頁。特點(diǎn)：為每個(gè)進(jìn)程分配多少物理塊是合適的值難以確定。（少：置換率高 多：資源浪費(fèi)）。2. 物理塊的分配策略 2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院152 2）可變分配全局置換思路：每個(gè)進(jìn)程預(yù)先分配一定數(shù)目的物理塊，同時(shí)OSOS也保持一個(gè)空閑物理塊

7、隊(duì)列。策略：當(dāng)缺頁時(shí)，首先將對(duì)OSOS所占有的空閑塊進(jìn)行分配，從而增加了各進(jìn)程的物理塊數(shù)。當(dāng)OSOS的空閑塊全部用完，將引起換出操作,OS,OS從內(nèi)存中選擇一頁，可能是系統(tǒng)中任一進(jìn)程的頁。是一種最易實(shí)現(xiàn)的策略2. 物理塊的分配策略 2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院163 3）可變分配局部置換思路：先為每個(gè)進(jìn)程預(yù)先分配一定數(shù)目的物理塊，系統(tǒng)根據(jù)缺頁率動(dòng)態(tài)調(diào)整各進(jìn)程占有的物理塊數(shù)目，使其保持在一個(gè)比較低的缺頁率狀態(tài)下。策略：如果缺頁，則先從該進(jìn)程在內(nèi)存的頁面中選中一頁，進(jìn)行換出操作特點(diǎn)：使大部分進(jìn)程可以達(dá)到比較近似的性能2. 物理塊的分配策略 2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)

8、院173. 物理塊分配算法 將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。缺點(diǎn)：未考慮各進(jìn)程本身的大小。2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院18niiSS1mSSbii3. 物理塊分配算法2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院19 在實(shí)際應(yīng)用中，為了照顧重要的、急迫的作業(yè)盡快完成，應(yīng)為它分配較多的內(nèi)存空間。方法：一部分按比例分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。3. 物理塊分配算法2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院205.2.3 調(diào)頁策略 （1）預(yù)調(diào)(prepaging)提前取頁：預(yù)先裝入主存一頁或幾頁。（根據(jù)程序順序行為

9、空間局部性，主要用于進(jìn)程的首次調(diào)入時(shí)） （2）請(qǐng)調(diào)(demand paging)請(qǐng)求取頁：當(dāng)用到某頁而不在主存時(shí)即發(fā)生缺頁中斷時(shí)調(diào)入。（每次僅調(diào)入一頁，較費(fèi)系統(tǒng)開銷）2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院21 外存有兩個(gè)部分：文件區(qū)和對(duì)換區(qū)。對(duì)換區(qū)I/O操作速度比文件區(qū)相對(duì)快一些，因此一般應(yīng)當(dāng)盡量使用對(duì)換區(qū)來調(diào)入頁面。對(duì)于不同情況，采用不同的策略：存儲(chǔ)內(nèi)容駐留時(shí)間主要目標(biāo)分配方式文件區(qū)文件較長(zhǎng)久提高文件存儲(chǔ)空間的利用率離散對(duì)換區(qū)從內(nèi)存換出的進(jìn)程短暫提高進(jìn)程換入和換出的速度連續(xù)2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院221) 缺頁中斷 2) 保留CPU現(xiàn)場(chǎng)環(huán)境，轉(zhuǎn)入缺頁中斷處理程序 3

10、) 缺頁中斷處理：查找頁表，得到對(duì)應(yīng)的外存物理塊號(hào)。如果內(nèi)存有空閑，則啟動(dòng)磁盤操作，將所缺的頁面讀入，并修改頁表。否則，到4)。 4) 若內(nèi)存沒有空閑，則執(zhí)行置換算法，選出要換出的頁面，如果該頁修改過，應(yīng)將其寫入磁盤，然后將所缺頁調(diào)入內(nèi)存，修改相應(yīng)表項(xiàng)，將其存在位置為1，并放入快表。 5) 利用修改后的頁表，形成物理地址，訪問內(nèi)存數(shù)據(jù)。2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院23假設(shè)一個(gè)進(jìn)程的邏輯空間為n頁，系統(tǒng)為其分配的內(nèi)存物理塊數(shù)為m（mn）。pS訪問頁面成功的次數(shù)（即所訪問頁面在內(nèi)存中）pF訪問頁面失敗的次數(shù)（即所訪問頁面不在內(nèi)存中， 需要從外存調(diào)入）pA=S+F進(jìn)程總的頁面訪問次數(shù)

11、 則：缺頁率 f=F/A2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院24假設(shè)被置換的頁面被修改的概率是，pta 缺頁中斷處理時(shí)間，ptb 被置換頁面沒有被修改的缺頁中斷時(shí)間那么，缺頁中斷處理時(shí)間的計(jì)算公式為： t= ta+（1-） tb2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院255.3 頁面置換算法(Page-Replacement Algorithms) 5.3.1 最佳置換(OPT)和先進(jìn)先出(FIFO)置換算法5.3.2 最近最久未使用(LRU)置換算法5.3.3 Clock置換算法 5.3.4 其它置換算法2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院265.3.1最佳置換算法和先進(jìn)

12、先出置換算法1. 最佳(Optimal)置換算法2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院271. 最佳(Optimal)置換算法2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院282. 先進(jìn)先出(FIFO)頁面置換算法 算法：淘汰最先進(jìn)入主存的頁2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院29 （2）實(shí)現(xiàn)：已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一隊(duì)列 （3）依據(jù): 先進(jìn)入的可能已經(jīng)使用完畢。 理論上來說，如果分配的塊數(shù)增加的話，缺頁率 是會(huì)減少，但是FIFO算法對(duì)于一些特殊的頁面訪問序列會(huì)有隨著分配的塊數(shù)增加，缺頁率也增加的異常現(xiàn)象。 （4） 隨著物理塊數(shù)的增多缺頁率增大！(舉例) （5）性能差、

13、有異常現(xiàn)象（Belady現(xiàn)象）2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院30先進(jìn)先出頁面置換算法（FIFO）（例） 有一虛擬存儲(chǔ)系統(tǒng)，采用FIFO的頁面淘汰算法。在內(nèi)存中為每個(gè)進(jìn)程分配3個(gè)物理塊。進(jìn)程有5頁，執(zhí)行時(shí)訪問頁面的順序?yàn)?，1，2，3，0，1，4，0， 1，2，3，4，（1）該進(jìn)程運(yùn)行時(shí)總共出現(xiàn)了幾次缺頁（2）若為每個(gè)進(jìn)程在內(nèi)存中分配4個(gè)物理塊，又將產(chǎn)生幾次缺頁。（3）如何解釋所出現(xiàn)的現(xiàn)象。2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院31物理塊m=3訪問序列：0，1，2，3，0，1，4，0， 1，2，3，42022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院32物理塊m=4訪問序列：0，1

14、， 2， 3， 0，1，4，0， 1，2，3，42022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院33FIFO算法與Belady現(xiàn)象o Belady現(xiàn)象： 采用FIFO算法時(shí)，若對(duì)一個(gè)進(jìn)程未分配它所要求的全部頁面，有時(shí)就會(huì)出現(xiàn)分配的物理塊數(shù)增多，缺頁率反而提高的異常現(xiàn)象。o Belady現(xiàn)象的描述： 一個(gè)進(jìn)程P要訪問 M個(gè)頁， OS分配 N個(gè)內(nèi)存頁面給進(jìn)程 P；對(duì)一個(gè)訪問序列S ，發(fā)生缺頁次數(shù)為 PE(S, N)。當(dāng)N增大時(shí)， PE(S, N) 時(shí)而增大，時(shí)而減小。o Belady現(xiàn)象的原因： FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動(dòng)態(tài)特征是矛盾的，即被置換的頁面并不是進(jìn)程不會(huì)訪問的。2022-3-

15、5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院345.3.2 最近最久未使用(LRU)置換算法 2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院35 雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件，須有兩類硬件之一的支持：寄存器或棧。1）寄存器 為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，用來記錄某進(jìn)程在內(nèi)存中各頁的使用情況。移位寄存器表示為: R=Rn-1Rn-2Rn-3R2R1R0 當(dāng)進(jìn)程訪問某物理塊時(shí)，要將相應(yīng)寄存器的Rn-1位置成1。此時(shí)，定時(shí)信號(hào)將每隔一定時(shí)間將寄存器右移一位。2. LRU置換算法的硬件支持 R0R1R2R3R4R5R6R7 R實(shí)頁0001011110011110011010110101

16、01011000100001010101100110010100100012345678某進(jìn)程具有8個(gè)頁面時(shí)的LRU訪問情況R0R1R2R3R4R5R6R7 R實(shí)頁000000000000000000000000000000000000000000000000000000000001011112345678某進(jìn)程具有8個(gè)頁面時(shí)的LRU訪問情況R0R1R2R3R4R5R6R7 R實(shí)頁000000000000000000000000000000000000000000000000000101110000000012345678某進(jìn)程具有8個(gè)頁面時(shí)的LRU訪問情況R710011110R0R1R2R3

17、R4R5R6R7 R實(shí)頁000000000000000000000000000000000000000000010111100111100000000012345678某進(jìn)程具有8個(gè)頁面時(shí)的LRU訪問情況R701101011R0R1R2R3R4R5R6R7 R實(shí)頁000101111001111001101011010101011000100001010101100110010100100012345678某進(jìn)程具有8個(gè)頁面時(shí)的LRU訪問情況2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院36 利用一個(gè)特殊的棧來保存當(dāng)前使用的各個(gè)頁面的頁面號(hào)。把被訪問的頁面頁號(hào)移到棧頂，于是棧底則是最近最久未使用頁

18、面的頁面號(hào)。44設(shè)一進(jìn)程訪問頁面的頁面號(hào)序列為：設(shè)一進(jìn)程訪問頁面的頁面號(hào)序列為：4，7，0，7，1，0，1，2，1，2，6隨著進(jìn)程的訪問，棧中頁面號(hào)的變化情況：隨著進(jìn)程的訪問，棧中頁面號(hào)的變化情況：477470040774071147100470114701224702114701227012662）棧棧底棧底棧頂棧頂棧頂棧頂棧頂棧頂棧頂棧頂棧頂棧頂2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院37 選擇到當(dāng)前時(shí)間為止被訪問次數(shù)最少的頁面被置換； 每頁設(shè)置訪問計(jì)數(shù)器，每當(dāng)頁面被訪問時(shí)，該頁面的訪問計(jì)數(shù)器加1； 發(fā)生缺頁中斷時(shí)，淘汰計(jì)數(shù)值最小的頁面，并將所有計(jì)數(shù)清零；2022-3-5阜陽師范學(xué)院計(jì)

19、算機(jī)與信息學(xué)院385.3.3 Clock置換算法 v 每頁設(shè)置一位訪問位，內(nèi)存中的所有頁鏈接成一個(gè)循環(huán)隊(duì)列；v 循環(huán)檢查各頁面的使用情況，訪問位為“0”，選擇該頁淘汰；訪問位為“1”，復(fù)位訪問位為“0”，查詢指針前進(jìn)一步（給該頁第二次駐留內(nèi)存的機(jī)會(huì)，簡(jiǎn)稱“第二次機(jī)會(huì)”算法）。v 又稱為“最近未使用”置換算法（NRU）2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院392. 改進(jìn)型Clock置換算法 由訪問位A和修改位M可以組合成下面四種類型的頁面： 1類(A=0, M=0): 表示該頁最近既未被訪問，又未被修改， 是最佳淘汰頁。 2類(A=0, M=1)： 表示該頁最近未被訪問，但已被修改， 并不

20、是很好的淘汰頁。 3類(A=1, M=0)： 最近已被訪問， 但未被修改，該頁有可能再被訪問。 4類(A=1, M=1): 最近已被訪問且被修改，該頁可能再被訪問。 2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院40執(zhí)行過程 訪問位A，修改位M共同表示一個(gè)頁面的狀態(tài) 四種狀態(tài)：00 01 10 11 三輪掃描：v第一輪：查找00頁面，未找到，下一步；v第二輪：查找01頁面，將所掃描過的頁面的A位復(fù)位為“0”，未找到，下一步；v第三輪：若第2步失敗，重復(fù)1和2（如果需要）。2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院41 系統(tǒng)為一個(gè)有6頁的進(jìn)程分配4個(gè)物理塊，其頁表如下所示，頁的大小為1K，請(qǐng)計(jì)算

21、邏輯地址為17C8H的物理地址。（表中：R(讀/ 訪問)、 M(修改) ）按FIFO算法為多少？按LRU算法為？按CLOCK算法為多少？例題32022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院42分析o CLOCK算法： 淘汰R=0,M=0的頁面0，對(duì)應(yīng)的塊號(hào)為7（111），o FIFO算法：n淘汰120時(shí)刻轉(zhuǎn)入的頁面2，對(duì)應(yīng)的塊號(hào)為2（10）o LRU算法：n淘汰260時(shí)刻引用的頁面1，對(duì)應(yīng)的塊號(hào)為4（100）1 17 7C C8 800010001011101111100110010001000邏輯地址為：17C8H頁號(hào)頁內(nèi)地址（10位）0001 010001 0111 1100 100011

22、1100 1000頁號(hào)頁內(nèi)地址（10位）0001 010001 0111 1100 100011 1100 10002022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院43例題4o設(shè)某計(jì)算機(jī)的邏輯地址空間和物理地址空間均為64KB，按字節(jié)編址。若某進(jìn)程最多需要6頁數(shù)據(jù)存儲(chǔ)空間，頁的大小為1KB，操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配4個(gè)物理塊。頁號(hào)物理塊號(hào)裝入時(shí)刻訪問位0713011423012220013916012022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院44當(dāng)該進(jìn)程執(zhí)行到時(shí)刻260時(shí)，要訪問邏輯地址為17CAH的數(shù)據(jù)，請(qǐng)回答下列問題：（1）該邏輯地址對(duì)應(yīng)的頁號(hào)是多少？（2）若采用先進(jìn)先出（

23、FIFO）置換算法，該邏輯地址對(duì)應(yīng)的物理地址是多少？要求給出計(jì)算過程。 （3）若采用時(shí)鐘（Clock）置換算法，該邏輯地址對(duì)應(yīng)的物理地址是多少？要求給出計(jì)算過程。（設(shè)搜索下一頁的指針沿順時(shí)針方向移動(dòng)，且當(dāng)前指向2號(hào)物理塊，如圖所示）2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院45解答o17CAH=（0001 0111 1100 1010）2 （1）頁大小為1K，所以頁內(nèi)偏移地址為10位，頁號(hào)為6位所以其對(duì)應(yīng)的頁號(hào)為5.（2）FIFO算法：被置換的頁面0所在的物理塊號(hào)為7，所以其對(duì)應(yīng)的物理地址為（0001 1111 1100 1010）2 =1FCAH（3） Clock算法：被置換的頁面2所在的

24、物理塊號(hào)為2，所以其對(duì)應(yīng)的物理地址為（0000 1011 1100 1010）2 =0BCAH 頁號(hào)（6位）頁內(nèi)地址（10位）0001 010001 0111 1100 101011 1100 10102022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院46練習(xí)o 頁式存儲(chǔ)管理，允許用戶編程空間為32個(gè)頁面（每頁1KB），主存為16KB，如有一用戶程序有10頁長(zhǎng)，且某時(shí)刻該用戶程序頁表如下表所示：o 若分別遇到有以下三個(gè)邏輯地址：0AC5H、1AC5H、3AC5H處的操作，試計(jì)算并說明存儲(chǔ)管理系統(tǒng)將如何處理。邏輯頁號(hào)物理塊號(hào)0817243102022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院47（1）影響頁

25、面換進(jìn)換出效率的若干因素q 頁面置換算法q 寫回磁盤的頻率q 讀入內(nèi)存的頻率5.3.4 頁面緩沖算法(PBA)2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院48（2）頁面緩沖算法(PBA)q被置換頁面的選擇和處理：用FIFO算法選擇被置換頁 如果頁面未被修改，就將其歸入到空閑頁面鏈表的末尾 否則將其歸入到已修改頁面鏈表。 此時(shí)頁面在內(nèi)存中并不做物理上的移動(dòng)，只是將頁表中的表項(xiàng)移到上述兩鏈表之一5.3.4 頁面緩沖算法(PBA)2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院49q需要調(diào)入新的頁面時(shí)，將新頁面內(nèi)容讀入到空閑頁面鏈表的第一項(xiàng)所指的頁面。q空閑頁面和已修改頁面，仍停留在內(nèi)存中一段時(shí)間，如果

26、這些頁面被再次訪問，只需較小開銷，而被訪問的頁面可以返還作為進(jìn)程的內(nèi)存頁。q當(dāng)已修改頁面達(dá)到一定數(shù)目后，再將它們一起調(diào)出到外存，然后將它們歸入空閑頁面鏈表，這樣能大大減少I/O操作的次數(shù)。頁面緩沖算法(PBA)2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院50補(bǔ)充作業(yè) 在一個(gè)請(qǐng)求頁式存儲(chǔ)管理系統(tǒng)中，進(jìn)程P共有5頁。訪問串為3、2、1、0、3、2、4、3、2、1、0、4時(shí)，試采用FIFO、LRU置換算法，計(jì)算當(dāng)分配給該進(jìn)程的物理塊分別為3、4時(shí)，訪問過程中發(fā)生的缺頁次數(shù)和缺頁率，比較所得的結(jié)果，淺析原因。2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院515.4 “抖動(dòng)”與工作集（駐留集）o 產(chǎn)生抖動(dòng)

27、的原因n 同時(shí)在系統(tǒng)中運(yùn)行的進(jìn)程太多，分配給每一個(gè)進(jìn)程的物理塊太少n 不能滿足進(jìn)程正常運(yùn)行的基本要求n 頻繁地出現(xiàn)缺頁，必須請(qǐng)求系統(tǒng)將所缺之頁調(diào)入內(nèi)存2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院525.4 “抖動(dòng)”與工作集（駐留集）o 進(jìn)程在運(yùn)行時(shí)對(duì)頁面的訪問是不均勻的，即往往在某段時(shí)間內(nèi)的訪問僅局限于較少的若干個(gè)頁面；而在另一段時(shí)間內(nèi)，則又可能僅局限于對(duì)另一些較少的頁面進(jìn)行訪問。o 這些頁面被稱為活動(dòng)頁面o 如果能夠預(yù)知進(jìn)程在某段時(shí)間間隔內(nèi)要訪問哪些頁面，并能將這些頁面提前調(diào)入內(nèi)存，將會(huì)大大地降低缺頁率，從而減少置換工作，提高CPU的利用率。o 所謂駐留集，是指在某段時(shí)間間隔內(nèi)，進(jìn)程要訪問的

28、頁面集合。具體地說，把某進(jìn)程在時(shí)間t的駐留集記作w（t，），變量稱為駐留集的“窗口大小” 2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院535.4 “抖動(dòng)”與工作集（駐留集）o 抖動(dòng)的預(yù)防方法n 采取局部置換策略n 把工作集算法融入到處理機(jī)調(diào)度中n 利用L=S準(zhǔn)則調(diào)節(jié)缺頁率n 選擇暫停的進(jìn)程2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院54例題5 請(qǐng)求分頁管理系統(tǒng)中，假設(shè)某進(jìn)程的頁表內(nèi)容如下表所示。 頁號(hào)頁框號(hào)有效位（存在位）0 0101H101H1 11 1-0 02 2254H254H1 1 頁面大小為4KB，一次內(nèi)存的訪問時(shí)間是100ns，一次快表（TLB）的訪問時(shí)間是10ns，處理一次缺頁

29、的平均時(shí)間為108ns（已含更新TLB和頁表的時(shí)間），進(jìn)程的駐留集大小固定為2，采用最近最少使用置換算法（LRU）和局部淘汰策略。2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院55假設(shè) TLB初始為空； 地址轉(zhuǎn)換時(shí)先訪問TLB，若TLB未命中，再訪問頁表（忽略訪問頁表之后的TLB更新時(shí)間）； 有效位為0表示頁面不在內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷處理后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H，請(qǐng)問： （1） 依次訪問上述三個(gè)虛地址，各需多少時(shí)間？給出計(jì)算過程。 （2） 基于上述訪問序列，虛地址1565H的 物理地址是多少？請(qǐng)說明理由。 2022-3-

30、5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院56分析 （1）頁面大小為4KB= 212 ，可得三個(gè)虛地址的頁號(hào)P如下： 2362H：P=2，訪問快表10ns，因初始為空，訪問頁表100ns得到頁框號(hào)，合成物理地址后訪問主存100ns，共計(jì)10ns+100ns+100ns=210ns。 1565H：P=1，訪問快表10ns，落空，訪問頁表100ns落空，進(jìn)行缺頁中斷處理108ns，合成物理地址后訪問主存100ns，共計(jì)10ns+100ns+108ns+100ns=318ns。 25A5H：P=2，訪問快表，因第一次訪問已將該頁號(hào)放入快表，因此花費(fèi)10ns便可合成物理地址，訪問主存100ns，共計(jì)10ns+10

31、0ns=110ns。 2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院57例題6某請(qǐng)求分頁系統(tǒng)的頁面置換策略如下： 從0時(shí)刻開始掃描，每隔5個(gè)時(shí)間單位掃描一輪駐留集（掃描時(shí)間忽略不計(jì)）且在本輪沒有被訪問過的頁框被系統(tǒng)回收，并放入到空閑頁框鏈尾，其中內(nèi)容在下一次分配之前不清空。當(dāng)發(fā)生缺頁時(shí)，如果該頁曾被使用過且還在空閑頁鏈表中，則重新放回進(jìn)程的駐留集中；否則，從空閑頁框鏈表頭部取出一個(gè)頁框。 2022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院58 忽略其它進(jìn)程的影響和系統(tǒng)開銷，初始時(shí)進(jìn)程駐留集為空。目前系統(tǒng)空閑頁的頁框號(hào)依次為32、15、21、41 進(jìn)程P依次訪問的為、 、 、 、 、 、 （1）當(dāng)虛擬頁

32、為時(shí)，對(duì)應(yīng)的頁框號(hào)是什么？分析： 初始駐留集為空，l 1頁對(duì)應(yīng)的頁框?yàn)榭臻e鏈表中的第一個(gè)空閑頁框32l 3頁對(duì)應(yīng)的頁框?yàn)榭臻e鏈表中的第一個(gè)空閑頁框15l 0頁對(duì)應(yīng)的頁框?yàn)榭臻e鏈表中的第三個(gè)空閑頁框212022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院59 忽略其它進(jìn)程的影響和系統(tǒng)開銷，初始時(shí)進(jìn)程駐留集為空。目前系統(tǒng)空閑頁的頁框號(hào)依次為32、15、21、41 進(jìn)程P依次訪問的為、 、 、 、 、 、 。（2）當(dāng)虛擬頁為時(shí)，對(duì)應(yīng)的頁框號(hào)是什么？分析：l 在第二輪掃描中只對(duì)0頁進(jìn)行掃描，而1和3頁對(duì)應(yīng)的頁框插入到空閑頁框鏈尾l 發(fā)生在第三輪掃描中，此刻該頁又被重新訪問，因此應(yīng)被重新放回駐留集中，其頁框?yàn)?22022-3-5阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院60 忽略其它進(jìn)程的影響和系統(tǒng)開銷，初始時(shí)進(jìn)程駐留集為空。目前系統(tǒng)空閑頁的頁框號(hào)依次為32、15、21、41 進(jìn)程P依