計(jì)算機(jī)組成原理

Chapter4

存儲(chǔ)管理南通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院主講教師

周建美Mail：zhou.jm@今天雖然主存價(jià)格已相當(dāng)便宜，但主存容量仍然是計(jì)算機(jī)四大硬件資源（CPU、主板、內(nèi)存、顯卡）中最關(guān)鍵而又最緊張的“瓶頸”資源。因此對(duì)主存的管理和有效使用仍然是今天操作系統(tǒng)十分重要的內(nèi)容。許多操作系統(tǒng)之間最明顯的區(qū)別特征之一往往是所使用的存儲(chǔ)管理方法不同。如OS/360-MFT采用固定分區(qū)存儲(chǔ)管理技術(shù)，OS/360-MTV是采用可變分區(qū)存儲(chǔ)管理技術(shù)，OS/2，WindowsNT,是采用虛擬存儲(chǔ)管理技術(shù)。主存儲(chǔ)器管理技術(shù)可分為兩大類(lèi)：實(shí)存儲(chǔ)器管理和虛擬存儲(chǔ)器管理。存儲(chǔ)管理的功能分配和去配：抽象和映射：隔離和共享：存儲(chǔ)擴(kuò)充：本章內(nèi)容存儲(chǔ)器連續(xù)存儲(chǔ)空間分頁(yè)式存儲(chǔ)管理分段式存儲(chǔ)管理虛擬存儲(chǔ)管理4.1主存儲(chǔ)器內(nèi)容：存儲(chǔ)器的層次 地址轉(zhuǎn)換與存儲(chǔ)保護(hù)

4.1.1存儲(chǔ)器的層次存儲(chǔ)器的層次(1)寄存器高速緩存主存儲(chǔ)器磁盤(pán)緩存固定磁盤(pán)可移動(dòng)存儲(chǔ)介質(zhì)存儲(chǔ)器的層次(2)

某臺(tái)計(jì)算機(jī)存儲(chǔ)器層次配置CPU中的寄存器100個(gè)字；高速緩存512KB，存取周期15ns；主存儲(chǔ)器128MB，存取周期60ns；磁盤(pán)容量20GB，存取周期毫秒級(jí)；后援存儲(chǔ)容量1TB，存取周期秒級(jí)。

4.1.2地址轉(zhuǎn)換與存儲(chǔ)保護(hù)鏈接動(dòng)態(tài)重定位靜態(tài)重定位…源程序模塊1源程序模塊2源程序模塊n…目標(biāo)代碼1目標(biāo)代碼2目標(biāo)代碼n可重定位目標(biāo)代碼(裝載代碼)(輔存)編譯裝入執(zhí)行程序名字空間邏輯地址空間物理地址空間可執(zhí)行二進(jìn)代碼(主存)庫(kù)代碼可執(zhí)行二進(jìn)代碼(主存)

程序的編譯、鏈接、裝入和執(zhí)行

地址轉(zhuǎn)換與存儲(chǔ)保護(hù)邏輯地址（相對(duì)地址）與物理地址（絕對(duì)地址）邏輯地址空間與物理地址空間地址轉(zhuǎn)換或重定位靜態(tài)重定位與動(dòng)態(tài)重定位存儲(chǔ)保護(hù)4.2連續(xù)存儲(chǔ)空間管理內(nèi)容：固定分區(qū)存儲(chǔ)管理 可變分區(qū)存儲(chǔ)管理 伙伴系統(tǒng)主存不足的存儲(chǔ)管理技術(shù)4.2.1固定分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理的基本思想：固定分區(qū)存儲(chǔ)管理的數(shù)據(jù)結(jié)構(gòu)：作業(yè)進(jìn)入固定分區(qū)排隊(duì)策略：一是每個(gè)分區(qū)排一個(gè)等待處理的隊(duì)列,等待處理作業(yè)大小不均,導(dǎo)致有的分區(qū)空閑而有的分區(qū)忙碌;二是所有等待處理的作業(yè)排成一個(gè)隊(duì)列,當(dāng)調(diào)度其中一個(gè)進(jìn)入分區(qū)運(yùn)行時(shí),選擇可容納它的最小可用分區(qū),以充分利用主存。固定分區(qū)存儲(chǔ)管理的地址轉(zhuǎn)換和存儲(chǔ)保護(hù)

B下限寄存器邏輯地址CPU絕對(duì)地址操作系統(tǒng)區(qū)用戶(hù)分區(qū)1用戶(hù)分區(qū)2用戶(hù)分區(qū)3B+L2上限寄存器<B+L2越界中斷用戶(hù)分區(qū)4用戶(hù)分區(qū)5用戶(hù)分區(qū)64.2.2可變分區(qū)存儲(chǔ)管理可變分區(qū)存儲(chǔ)管理

可變分區(qū)(variablepartition)存儲(chǔ)管理是按作業(yè)的實(shí)際大小來(lái)劃分分區(qū)，且分區(qū)個(gè)數(shù)也是隨機(jī)的，劃分的時(shí)間、大小、位置都是動(dòng)態(tài)的，實(shí)現(xiàn)多個(gè)作業(yè)對(duì)內(nèi)存的共享，進(jìn)一步提高內(nèi)存資源利用率。

可變分區(qū)方式主存分配示例

操作系統(tǒng)作業(yè)1空閑區(qū)作業(yè)2空閑區(qū)4KB10KB46KB52KB128KB操作系統(tǒng)作業(yè)1空閑區(qū)作業(yè)2空閑區(qū)4KB10KB40KB46KB52KB128KB作業(yè)3操作系統(tǒng)作業(yè)1空閑區(qū)4KB10KB40KB128KB作業(yè)3可變分區(qū)存儲(chǔ)管理數(shù)據(jù)結(jié)構(gòu)可變分區(qū)主存分配表可由兩張表格組成：一張稱(chēng)“已分配區(qū)表”另一張是“未分配區(qū)表”可變分區(qū)的回收算法(1)當(dāng)一個(gè)進(jìn)程X撤離時(shí)，可分成四種情況：(1)其鄰近都有進(jìn)程（A和B），(2)一邊有進(jìn)程（A或B），(3)兩邊均為空閑區(qū)（黑色區(qū)域）。

可變分區(qū)的回收算法(2)

A

X

B

A

B

A

X

A

X

B

B

x

變?yōu)樽優(yōu)樽優(yōu)樽優(yōu)閄終止前X終止后鏈表空閑區(qū)管理方法每個(gè)內(nèi)存空閑區(qū)的開(kāi)頭單元存放本空閑區(qū)長(zhǎng)度及下一個(gè)空閑區(qū)起始地址,所有空閑區(qū)都鏈接起來(lái),系統(tǒng)設(shè)置第一塊空閑區(qū)地址指針,讓它指向第一塊空閑區(qū)地址。申請(qǐng)空閑區(qū);歸還空閑區(qū)?？勺兎謪^(qū)管理的分配算法1）最先適應(yīng)分配算法

2）下次適應(yīng)分配算法3)最優(yōu)適應(yīng)分配算法

4）最壞適應(yīng)分配算法5)快速適應(yīng)分配算法

查找和分配算法比較(1)從搜索空閑區(qū)速度及主存利用率來(lái)看,最先適用分配、下次適應(yīng)分配和最佳適應(yīng)算法比最壞適應(yīng)算法性能好。如果空閑區(qū)按從小到大排列,則最先適用分配算法等于最優(yōu)適應(yīng)分配算法。如果空閑區(qū)按從大到小排列,則最先適用分配算法等于最壞適應(yīng)分配算法。查找和分配算法比較(2)空閑區(qū)按從小到大排列時(shí),最先適用分配算法能盡可能使用低地址區(qū),從而高地址空間有較大的空閑區(qū)容納大的作業(yè)。下次適應(yīng)分配算法會(huì)使存儲(chǔ)器空間得到均衡使用。最優(yōu)適應(yīng)分配算法的主存利用率最好,但可能會(huì)導(dǎo)致空閑區(qū)分割下來(lái)的部分很小。查找和分配算法比較(3)處理某種作業(yè)序列時(shí),最壞適應(yīng)分配算法可能性能最佳,它選擇最大空閑區(qū),使得分配后剩余下來(lái)的空閑區(qū)不會(huì)太小,仍能用于再分配。最先適應(yīng)算法簡(jiǎn)單、快速，在實(shí)際的操作系統(tǒng)中用得較多；其次是最佳適應(yīng)算法和下次適應(yīng)算法?？勺兎謪^(qū)地址轉(zhuǎn)換與存儲(chǔ)保護(hù)

基址基址寄存器邏輯地址CPU絕對(duì)地址操作系統(tǒng)區(qū)空閑分區(qū)1用戶(hù)作業(yè)1空閑分區(qū)2限長(zhǎng)限長(zhǎng)寄存器<限長(zhǎng)越界中斷多對(duì)基址/限長(zhǎng)寄存器允許一個(gè)進(jìn)程占用兩個(gè)或多個(gè)分區(qū)。規(guī)定某對(duì)基址/限長(zhǎng)寄存器的區(qū)域是共享的，用來(lái)存放共享的程序和常數(shù)，對(duì)共享區(qū)域的信息只能讀出不能寫(xiě)入。進(jìn)程共享的例行程序就可放在限定的公用區(qū)域中,而讓進(jìn)程的共享部分具有相同的基址/限長(zhǎng)值。進(jìn)程B虛CPU進(jìn)程A虛CPU物理主存進(jìn)程A私有空間進(jìn)程B私有空間共享區(qū)重定位寄存器1限長(zhǎng)寄存器1重定位寄存器2限長(zhǎng)寄存器2重定位寄存器1限長(zhǎng)寄存器1重定位寄存器2限長(zhǎng)寄存器2

多對(duì)重定位寄存器支持主存共享4.2.3伙伴系統(tǒng)

兩個(gè)伙伴的大小必須相同，物理地址必須連續(xù)?；驹恚篜241伙伴通過(guò)對(duì)大塊的物理主存劃分而獲得假如從第0個(gè)頁(yè)面開(kāi)始到第3個(gè)頁(yè)面結(jié)束的主存每次都對(duì)半劃分，那么第一次劃分獲得大小為2頁(yè)的伙伴，如0、1和2、3進(jìn)一步劃分，可以獲得大小為1頁(yè)的伙伴，例如0和1，2和301230123伙伴原理伙伴系統(tǒng)原理下面通過(guò)一個(gè)例子說(shuō)明伙伴系統(tǒng)的工作過(guò)程。內(nèi)存管理模塊保持有一個(gè)空閑塊鏈表，空閑塊的大小可以為1，2，4，8，…，2n字節(jié)，其中n為計(jì)算機(jī)的有效地址位。例如，對(duì)于1M的內(nèi)存，空閑塊的大小可有20個(gè)不同的值，分別為2i個(gè)字節(jié)，其中1i20。初始時(shí)，整個(gè)存儲(chǔ)器是空閑的，鏈表只含有一個(gè)1M字節(jié)的空閑塊?；锇橄到y(tǒng)原理

128k256k384k512k640k768k896k1M

A

128

256512

AB64

256

512

AB64

C

128

512

128B64

C

128

512

128BD

C

128

512

12864D

C

128

512

256

C

128

512

1024伙伴系統(tǒng)原理優(yōu)點(diǎn)：當(dāng)一個(gè)大小為2k個(gè)字節(jié)的塊釋放時(shí)，存儲(chǔ)器管理模塊只需搜索大小為2k字節(jié)的塊，看其是否可以合并，而其它算法則必須搜索所有的空閑塊。因此，伙伴系統(tǒng)速度快。但存儲(chǔ)器利用角度來(lái)說(shuō)，伙伴系統(tǒng)性能很差，其原因是進(jìn)程的大小不一定是2的整數(shù)倍，由此會(huì)造成浪費(fèi)。例如，35K的進(jìn)程要分配64K的內(nèi)存給它，29K的內(nèi)存便浪費(fèi)掉了。這種存儲(chǔ)段內(nèi)的碎片稱(chēng)之為內(nèi)部碎片，而存儲(chǔ)段間的碎片稱(chēng)之為外部碎片。4.2.4主存不足的存儲(chǔ)管理技術(shù)

操作系統(tǒng)作業(yè)1空閑區(qū)作業(yè)2空閑區(qū)作業(yè)3空閑區(qū)操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)作業(yè)4移動(dòng)技術(shù)有關(guān)移動(dòng)問(wèn)題討論移動(dòng)條件移動(dòng)時(shí)機(jī)移動(dòng)算法對(duì)換技術(shù)對(duì)換的作用對(duì)換進(jìn)程的選擇UNIX對(duì)換器Windows對(duì)換器覆蓋技術(shù)覆蓋的作用覆蓋的實(shí)現(xiàn)技術(shù)覆蓋技術(shù)的不足

4.3分頁(yè)式存儲(chǔ)管理內(nèi)容：分頁(yè)式存儲(chǔ)管理的基本原理 快表 分頁(yè)式存儲(chǔ)空間的分配和去配 分頁(yè)式存儲(chǔ)空間的頁(yè)面共享和保護(hù) 多級(jí)頁(yè)表 反置頁(yè)表4.3.1

分頁(yè)式存儲(chǔ)管理的基本原理分頁(yè)式存儲(chǔ)管理基本原理(1)?為什么要引進(jìn)分頁(yè)技術(shù)??基本原理(1)頁(yè)框(2)頁(yè)面(3)邏輯地址形式(4)頁(yè)表和地址轉(zhuǎn)換分頁(yè)式存儲(chǔ)管理基本原理(2)作業(yè)的頁(yè)面與分給的頁(yè)框如何建立聯(lián)系呢？邏輯地址(頁(yè)面)如何變換成物理地址(頁(yè)框)呢？作業(yè)的物理地址空間由連續(xù)變成分散后，如何保證程序正確執(zhí)行呢？分頁(yè)式存儲(chǔ)管理基本原理(3)

?動(dòng)態(tài)重定位技術(shù)，讓程序的指令執(zhí)行時(shí)動(dòng)態(tài)地進(jìn)行地址變換，給每個(gè)頁(yè)面設(shè)立重定位寄存器，重定位寄存器的集合便稱(chēng)頁(yè)表（pagetable）。

?頁(yè)表：操作系統(tǒng)為每個(gè)用戶(hù)作業(yè)建立的，用來(lái)記錄程序頁(yè)面和主存對(duì)應(yīng)頁(yè)框的對(duì)照表。

?頁(yè)表控制寄存器：當(dāng)前運(yùn)行作業(yè)的頁(yè)表起址和頁(yè)表長(zhǎng)。

?作業(yè)表：登記每個(gè)作業(yè)的頁(yè)表地址。分頁(yè)式存儲(chǔ)管理基本原理(4)

塊號(hào)1…。。。塊號(hào)2塊號(hào)第0頁(yè)…。。。第1頁(yè)頁(yè)號(hào)作業(yè)名BA頁(yè)表始址XXXXXX頁(yè)表長(zhǎng)度XXXX作業(yè)表頁(yè)表…。。。…。。?！?。。

頁(yè)表和作業(yè)表的一般格式頁(yè)式存儲(chǔ)管理的地址轉(zhuǎn)換和存儲(chǔ)保護(hù)

物理地址邏輯地址01··pb···頁(yè)表CPUpdbd主存分頁(yè)存儲(chǔ)管理的地址轉(zhuǎn)換頁(yè)表基址寄存器4.3.2快表相聯(lián)存儲(chǔ)器和快表相聯(lián)存儲(chǔ)器快表的格式采用相聯(lián)存儲(chǔ)器后地址轉(zhuǎn)換采用相聯(lián)存儲(chǔ)器的地址轉(zhuǎn)換假定訪問(wèn)主存時(shí)間為100毫微秒，訪問(wèn)相聯(lián)存儲(chǔ)器時(shí)間為20毫微秒，相聯(lián)存儲(chǔ)器為32個(gè)單元時(shí)快表命中率可達(dá)90%，按邏輯地址存取的平均時(shí)間為：（100＋20）×90%＋(100+100)×(1-90%)＝128毫微秒比兩次訪問(wèn)主存的時(shí)間200毫微秒下降近四成。4.3.3分頁(yè)式存儲(chǔ)空間

的分配和去配分頁(yè)式存儲(chǔ)空間的分配和去配位示圖法鏈表方法分配算法主存分配的位示圖和鏈表方法4.3.4分頁(yè)存儲(chǔ)空間的

頁(yè)面共享和保護(hù)分頁(yè)存儲(chǔ)管理能實(shí)現(xiàn)多作業(yè)共享程序和數(shù)據(jù)(1)數(shù)據(jù)共享程序共享分頁(yè)存儲(chǔ)管理能實(shí)現(xiàn)多作業(yè)共享程序和數(shù)據(jù)(2)共享信息的保護(hù)問(wèn)題標(biāo)志位保護(hù)方法鍵保護(hù)方法4.3.5多級(jí)頁(yè)表多級(jí)頁(yè)表多級(jí)頁(yè)表的概念多級(jí)頁(yè)表的具體做法邏輯地址結(jié)構(gòu)邏輯地址到物理地址轉(zhuǎn)換過(guò)程多級(jí)頁(yè)表的概念(1)

頁(yè)表存儲(chǔ)開(kāi)銷(xiāo)太大書(shū)P252多級(jí)頁(yè)表的概念(2)多級(jí)頁(yè)表概念：頁(yè)表和頁(yè)面一樣也進(jìn)行分頁(yè)，內(nèi)存僅存放當(dāng)前使用的頁(yè)表,暫時(shí)不用部分放在磁盤(pán)上,待用到時(shí)再行調(diào)進(jìn)。具體做法：把整個(gè)頁(yè)表進(jìn)行分頁(yè),分成一張張小頁(yè)表(稱(chēng)為頁(yè)表頁(yè)),小頁(yè)表的大小與頁(yè)框相同，為進(jìn)行索引查找,應(yīng)該為這些小頁(yè)表建一張頁(yè)目錄表,其表項(xiàng)指出小頁(yè)表所在頁(yè)框號(hào)及相關(guān)信息。

多級(jí)頁(yè)表的概念(3)系統(tǒng)為每個(gè)進(jìn)程建一張頁(yè)目錄表,它的每個(gè)表項(xiàng)對(duì)應(yīng)一個(gè)頁(yè)表頁(yè),而頁(yè)表頁(yè)的每個(gè)表項(xiàng)給出了頁(yè)面和頁(yè)框的對(duì)應(yīng)關(guān)系。頁(yè)目錄表是一級(jí)頁(yè)表,頁(yè)表頁(yè)是二級(jí)頁(yè)表。邏輯地址結(jié)構(gòu)有三部分組成：頁(yè)目錄、頁(yè)表頁(yè)和位移。多級(jí)頁(yè)表地址轉(zhuǎn)換過(guò)程(1)頁(yè)目錄表控制寄存器指出當(dāng)前運(yùn)行進(jìn)程的頁(yè)目錄表內(nèi)存所在地址,由頁(yè)目錄表起址加上“頁(yè)目錄位移(dir)”作索引,可找到某個(gè)頁(yè)表頁(yè)在內(nèi)存頁(yè)框的地址,以“頁(yè)表頁(yè)位移(page)”作索引,找到頁(yè)表頁(yè)的頁(yè)表項(xiàng),而該表項(xiàng)中包含了頁(yè)面對(duì)應(yīng)的頁(yè)框號(hào),頁(yè)框號(hào)和”頁(yè)內(nèi)位移(offset)”便可生成物理地址。多級(jí)頁(yè)表地址轉(zhuǎn)換過(guò)程(2)

B

offset

dirpageoffsetBF進(jìn)程一級(jí)頁(yè)表進(jìn)程二級(jí)頁(yè)表物理地址邏輯地址頁(yè)目錄表控制寄存器解決頁(yè)表頁(yè)占用內(nèi)存空間的問(wèn)題進(jìn)程運(yùn)行涉及頁(yè)面的頁(yè)表頁(yè)應(yīng)放在主存,其他頁(yè)表頁(yè)使用時(shí)再調(diào)入,在頁(yè)目錄表中增加特征位,指示對(duì)應(yīng)的頁(yè)表頁(yè)是否已調(diào)入內(nèi)存,地址轉(zhuǎn)換機(jī)構(gòu)根據(jù)邏輯地址中的dir,去查頁(yè)目錄表對(duì)應(yīng)表項(xiàng),如未調(diào)入,應(yīng)產(chǎn)生一個(gè)”缺頁(yè)表頁(yè)”中斷信號(hào)，請(qǐng)求操作系統(tǒng)將頁(yè)表頁(yè)調(diào)入主存。多級(jí)頁(yè)表結(jié)構(gòu)的本質(zhì)多級(jí)不連續(xù)導(dǎo)致多級(jí)索引。以二級(jí)頁(yè)表為例，用戶(hù)程序的頁(yè)面不連續(xù)存放，要有頁(yè)面地址索引，該索引是進(jìn)程頁(yè)表；進(jìn)程頁(yè)表又是不連續(xù)存放的多個(gè)頁(yè)表頁(yè)，故頁(yè)表頁(yè)也要頁(yè)表頁(yè)地址索引，該索引就是頁(yè)目錄。頁(yè)目錄項(xiàng)是頁(yè)表頁(yè)的索引，而頁(yè)表頁(yè)項(xiàng)是進(jìn)程程序的頁(yè)面索引。4.3.6反置頁(yè)表反置頁(yè)表(1)IPT是為內(nèi)存中的每一個(gè)物理塊建立一個(gè)頁(yè)表并按照塊號(hào)排序,該表每個(gè)表項(xiàng)包含正在訪問(wèn)該頁(yè)框的進(jìn)程標(biāo)識(shí)、頁(yè)號(hào)及特征位,用來(lái)完成主存頁(yè)框到訪問(wèn)進(jìn)程的頁(yè)號(hào)、即物理地址到邏輯地址的轉(zhuǎn)換。反置頁(yè)表(2)

頁(yè)框號(hào)位移進(jìn)程標(biāo)識(shí)頁(yè)號(hào)位移進(jìn)程標(biāo)識(shí)頁(yè)號(hào)特征位鏈指針序號(hào)反置頁(yè)表物理地址邏輯地址··哈希函數(shù)哈希表反置頁(yè)表及其地址轉(zhuǎn)換反置頁(yè)表(3)反置頁(yè)表地址轉(zhuǎn)換過(guò)程如下:邏輯地址給出進(jìn)程標(biāo)識(shí)和頁(yè)號(hào),用它們?nèi)ケ容^IPT,若整個(gè)反置頁(yè)表中未能找到匹配的頁(yè)表項(xiàng),說(shuō)明該頁(yè)不在主存,產(chǎn)生請(qǐng)頁(yè)中斷,請(qǐng)求操作系統(tǒng)調(diào)入;否則，該表項(xiàng)的序號(hào)便是頁(yè)框號(hào),塊號(hào)加上位移,便形成物理地址。4.4分段式存儲(chǔ)管理內(nèi)容：程序的分段結(jié)構(gòu) 分段式存儲(chǔ)管理的基本原理 段的共享和保護(hù) 分段和分頁(yè)的比較4.4.1程序的分段結(jié)構(gòu)程序的分段結(jié)構(gòu)分段存儲(chǔ)管理引入的主要原因模塊化程序設(shè)計(jì)的分段結(jié)構(gòu)分頁(yè)存儲(chǔ)管理——一維地址結(jié)構(gòu)分段存儲(chǔ)管理——二維地址結(jié)構(gòu)模塊化程序設(shè)計(jì)的分段結(jié)構(gòu)

子程序段X數(shù)組段A┇call[X]∣<E>(調(diào)用X段的入口E)┇call[Y]∣<F>(調(diào)用Y段的入口F)┇load1,[A]∣<G>(調(diào)用數(shù)組段A[G])┇主程序段E：┅┅┅┅┅┅F：┅┅┅┅┅┅子程序段YG：┅┅┅┅┅┅工作區(qū)段4.4.2分段式存儲(chǔ)管理的基本原理分段式存儲(chǔ)管理的基本原理(1)

?兩維邏輯地址段號(hào)：段內(nèi)地址

?作業(yè)表和段表

?段式存儲(chǔ)管理的地址轉(zhuǎn)換和存儲(chǔ)保護(hù)分段式存儲(chǔ)管理的基本原理(2)

XXX…XXX始址第0段第1段段號(hào)作業(yè)名BA段表始址XXXXXX表段長(zhǎng)度XXXX作業(yè)表段表………XXX…XXX長(zhǎng)度第2段分段式存儲(chǔ)管理的基本原理(3)

段控制寄存器

段表始址段表長(zhǎng)度

段號(hào)s位移d

段長(zhǎng)基址物理地址越界?段表4.4.3段的共享段的共享多對(duì)基址/限長(zhǎng)寄存器段的共享，是通過(guò)不同作業(yè)段表中的項(xiàng)指向同一個(gè)段基址來(lái)實(shí)現(xiàn)。幾道作業(yè)共享的例行程序就可放在一個(gè)段中，只要讓各道作業(yè)的共享部分有相同的基址/限長(zhǎng)值。對(duì)共享段的信息必須進(jìn)行保護(hù)。4.4.4分段和分頁(yè)的比較分段和分頁(yè)的比較(1)分段是信息的邏輯單位，由源程序的邏輯結(jié)構(gòu)所決定，用戶(hù)可見(jiàn)，段長(zhǎng)可根據(jù)用戶(hù)需要來(lái)規(guī)定，段起始地址可從任何主存地址開(kāi)始。分段方式中，源程序(段號(hào)，段內(nèi)位移)經(jīng)連結(jié)裝配后地址仍保持二維結(jié)構(gòu)。分段和分頁(yè)的比較(2)分頁(yè)是信息的物理單位，與源程序的邏輯結(jié)構(gòu)無(wú)關(guān)，用戶(hù)不可見(jiàn)，頁(yè)長(zhǎng)由系統(tǒng)確定，頁(yè)面只能以頁(yè)大小的整倍數(shù)地址開(kāi)始。分頁(yè)方式中，源程序(頁(yè)號(hào)，頁(yè)內(nèi)位移)經(jīng)連結(jié)裝配后地址變成了一維結(jié)構(gòu)。4.5虛擬存儲(chǔ)管理內(nèi)容：虛擬存儲(chǔ)管理的概念 請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理 請(qǐng)求分段虛擬存儲(chǔ)管理 請(qǐng)求段頁(yè)式虛擬存儲(chǔ)管理4.5.1虛擬存儲(chǔ)器的概念虛擬存儲(chǔ)管理的概念(1)為什么要引入虛擬存儲(chǔ)器?虛擬存儲(chǔ)器的基本思路。“部分裝入、部分對(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ǔ)器的概念圖邏輯地址空間處理器虛地址存儲(chǔ)管理部件實(shí)地址主存輔存物理地址空間虛擬存儲(chǔ)管理的概念(4)作業(yè)信息不全部裝入主存，能否保證作業(yè)的正確運(yùn)行？回答是肯定的,1968年P(guān).Denning研究了程序執(zhí)行時(shí)的局部性原理。程序的局部性原理程序在執(zhí)行過(guò)程中的一個(gè)較短時(shí)間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲(chǔ)區(qū)域中。又可細(xì)分時(shí)間局部性和空間局部性。程序的局部性原理（續(xù)）第一，程序中只有少量分支和過(guò)程調(diào)用，大都是順序執(zhí)行的指令。第二，程序包含若干循環(huán)，是由相對(duì)較少的指令組成，在循環(huán)過(guò)程中，計(jì)算被限制在程序中很小的相鄰部分中。程序的局部性原理（續(xù)）第三，很少出現(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ò)處理程序。實(shí)現(xiàn)虛擬存儲(chǔ)器必須解決的問(wèn)題

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

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

?部分裝入和部分對(duì)換問(wèn)題。虛擬存儲(chǔ)管理實(shí)現(xiàn)技術(shù)

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

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

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

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

CPUMMU內(nèi)存CPU把邏輯地址送至MMUMMU把物理地址送至主存

MMU的位置、功能和16個(gè)4KB頁(yè)面情況下MMU的內(nèi)部操作CPU送入的邏輯地址(8196)0010000000000100

110000000000100MMU送出的物理地址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è)特征位。請(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）請(qǐng)求分頁(yè)虛存地址轉(zhuǎn)換過(guò)程邏輯空間地址主存(用戶(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)地址查快表有登記無(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ǔ)系統(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)加大。頁(yè)面裝入策略和清除策略

頁(yè)面裝入策略決定何時(shí)把頁(yè)面裝入主存，有兩種策略：

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

?預(yù)調(diào)式調(diào)度頁(yè)面裝入策略—請(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è)面裝入策略—預(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è)面清除策略考慮何時(shí)把一個(gè)修改過(guò)的頁(yè)面寫(xiě)回輔存儲(chǔ)器：請(qǐng)頁(yè)式清除和預(yù)約式清除。請(qǐng)頁(yè)式清除：僅當(dāng)一頁(yè)選中被替換,且之前它又被修改過(guò)，才把這個(gè)頁(yè)面寫(xiě)回輔存。預(yù)約式清除：對(duì)所有更改過(guò)的頁(yè)面，在需要之前就把它們都寫(xiě)回輔存，可成批進(jìn)行。頁(yè)面清除策略的缺點(diǎn)預(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è)面清除策略—頁(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í)回收，或者淘汰掉以作替換。頁(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è)中斷率上升。

?難點(diǎn)：P.263可變分配和局部替換配合使用其實(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)性能。頁(yè)面替換策略（重點(diǎn)）

?頁(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

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

影響缺頁(yè)中斷率f的因素有：

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

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

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

(4)程序特性。全局頁(yè)面替換策略1)最佳頁(yè)面替換算法OPT2)先進(jìn)先出頁(yè)面替換算法FIFO3)最近最少用頁(yè)面替換算法LRU4)第二次機(jī)會(huì)頁(yè)面替換算法SCR5)時(shí)鐘頁(yè)面替換算法Clock

1）最佳替換算法(一個(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)。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)：多位計(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è)面淘汰;如果”引用位”是1,說(shuō)明它進(jìn)入主存較早，但最近仍在使用。把它的”引用位”清0,并把這個(gè)頁(yè)面移到隊(duì)尾，把它看作是一個(gè)新調(diào)入的頁(yè)。第二次機(jī)會(huì)頁(yè)面替換算法(2)算法含義：最先進(jìn)入主存的頁(yè)面，如果最近還在被使用的話,仍然有機(jī)會(huì)作為像一個(gè)新調(diào)入頁(yè)面一樣留在主存中。5)時(shí)鐘頁(yè)面替換算法

(ClockPolicy)(1)算法實(shí)現(xiàn)要點(diǎn)(1)：一個(gè)頁(yè)面首次裝入主存，其“引用位”置1。主存中的任何頁(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è)面。例子：計(jì)算缺頁(yè)中斷次數(shù)和被淘汰頁(yè)面(1)假設(shè)采用固定分配策略，進(jìn)程分得三個(gè)頁(yè)框,執(zhí)行中按下列次序引用5個(gè)獨(dú)立的頁(yè)面:232152453252。例子：計(jì)算缺頁(yè)中斷次數(shù)和被淘汰頁(yè)面(2)232152453252tailhead232152453252例子：計(jì)算缺頁(yè)中斷次數(shù)和被淘汰頁(yè)面(3)

C

O

K

F(2)

F

F

F(2)

F(3)

F(1)

F(5)

F(2)

F(4)

2

2

2

2

3

1

5

5

2

2

4

3

3

3

3

1

5

2

2

4

4

3

5

I

O

1

5

2

4

4

3

3

5

2

F(3)

F(1)

F(5)

F(4)

2*

2*

2*

2*

5*

5*

5*

5*

3*

3*

3*

3*

→

3*

3*

3*

3

2*

2*

2*

2

2*

2

2*

L

→

C

→

→

1*

→

1

→

1

→

4*

→

4*

→

4

→

4

→

5*

→

5*

232152453252232152453252例子：計(jì)算缺頁(yè)中斷次數(shù)和被淘汰頁(yè)面(4)

性能比較

OPTF(1)F(2)F(4)+3次LRUF(3)F(1)F(2)F(4)+3次CLOCKF(2)F(3)F(1)F(5)F(4)+3次FIFOF(1)F(3)F(1)F(5)F(2)F(4)+3次局部頁(yè)面替換算法1)局部最佳頁(yè)面替換算法

2)工作集模型和工作集置換算法3)模擬工作集替換算法4)缺頁(yè)頻率替換算法1)局部最佳頁(yè)面替換算法實(shí)現(xiàn)思想：進(jìn)程在時(shí)刻t訪問(wèn)某頁(yè)面，如果該頁(yè)面不在主存中，導(dǎo)致一次缺頁(yè)，把該頁(yè)面裝入一個(gè)空閑頁(yè)框。不論發(fā)生缺頁(yè)與否，算法在每一步要考慮引用串，如果該頁(yè)面在時(shí)間間隔(t,t+τ)內(nèi)未被再次引用，那么就移出頁(yè)面；否則，該頁(yè)被保留在進(jìn)程的駐留集中，直到再次被引用。

示例：P271圖4.232)工作集模型和工作集置換算法

進(jìn)程工作集指“在某一段時(shí)間間隔內(nèi)進(jìn)程運(yùn)行所需訪問(wèn)的頁(yè)面集合”。實(shí)現(xiàn)思想：工作集模型用來(lái)對(duì)局部最佳頁(yè)面替換算法進(jìn)行模擬實(shí)現(xiàn)，不向前查看頁(yè)面引用串，而是基于程序局部性原理向后看，在任何給定時(shí)刻，一個(gè)進(jìn)程不久的將來(lái)所需主存頁(yè)框數(shù)，可通過(guò)考查其過(guò)去最近的時(shí)間內(nèi)的主存需求做出估計(jì)。示例：P272圖4.243)模擬工作集替換算法老化(Aging)算法例如，時(shí)間間隔T定為1000次存儲(chǔ)器引用，頁(yè)面P在時(shí)刻t+0時(shí)寄存器為“1000”，在時(shí)刻t+1000時(shí)寄存器為“0100”，在時(shí)刻t+2000時(shí)寄存器為“0010”，在時(shí)刻t+3000時(shí)寄存器為“0001”，在時(shí)刻t+4000時(shí)寄存器為“0000”，此時(shí)，頁(yè)面p被移出工作集，時(shí)間戳算法若t_off>t_max，把頁(yè)面從工作集中移出

4)缺頁(yè)頻率替換算法缺頁(yè)頻率替換算法根據(jù)連續(xù)的缺頁(yè)之間的時(shí)間間隔來(lái)對(duì)缺頁(yè)頻率進(jìn)行測(cè)量，每次缺頁(yè)時(shí)，利用測(cè)量時(shí)間調(diào)整進(jìn)程工作集尺寸。規(guī)則：如果本次缺頁(yè)與前次缺頁(yè)之間的時(shí)間超過(guò)臨界值τ，那么，所有在這個(gè)時(shí)間間隔內(nèi)沒(méi)有引用的頁(yè)面都被移出工作集。示例：P273圖4.25請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理的幾個(gè)設(shè)計(jì)問(wèn)題1)頁(yè)面大小

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

.從主存利用率考慮

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

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

2)頁(yè)面交