教學(xué)課件PPT 存儲(chǔ)管理

《教學(xué)課件PPT 存儲(chǔ)管理》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《教學(xué)課件PPT 存儲(chǔ)管理（115頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1第第4 4章章 存儲(chǔ)管理存儲(chǔ)管理 重要內(nèi)容重要內(nèi)容0存儲(chǔ)器存儲(chǔ)器0連續(xù)存儲(chǔ)空間管理連續(xù)存儲(chǔ)空間管理0分頁(yè)存儲(chǔ)管理分頁(yè)存儲(chǔ)管理0分段存儲(chǔ)管理分段存儲(chǔ)管理0虛擬存儲(chǔ)管理虛擬存儲(chǔ)管理0Intel x86Intel x86分段和分頁(yè)存儲(chǔ)結(jié)構(gòu)分段和分頁(yè)存儲(chǔ)結(jié)構(gòu)0LinuxLinux虛擬存儲(chǔ)管理虛擬存儲(chǔ)管理0Windows 2003Windows 2003虛擬存儲(chǔ)管理（自學(xué)）虛擬存儲(chǔ)管理（自學(xué)）2存儲(chǔ)管理的功能存儲(chǔ)管理的功能 分配和去配分配和去配0請(qǐng)求和釋放主存空間請(qǐng)求和釋放主存空間 抽象和映射抽象和映射0抽象成一維數(shù)組或二維地址空間抽象成一維數(shù)組或二維地址空間0地址轉(zhuǎn)換地址轉(zhuǎn)換 隔離和共享隔離和共享0

2、隔離實(shí)現(xiàn)存儲(chǔ)保護(hù)功能隔離實(shí)現(xiàn)存儲(chǔ)保護(hù)功能0超越隔離機(jī)制，提高主存利用率超越隔離機(jī)制，提高主存利用率 存儲(chǔ)擴(kuò)充存儲(chǔ)擴(kuò)充0虛擬，允許進(jìn)程虛擬地址空間大于主存空間虛擬，允許進(jìn)程虛擬地址空間大于主存空間34.1 4.1 存儲(chǔ)器存儲(chǔ)器4.1.1 4.1.1 存儲(chǔ)器的層次存儲(chǔ)器的層次 4.1.2 4.1.2 地址轉(zhuǎn)換與存儲(chǔ)保護(hù)地址轉(zhuǎn)換與存儲(chǔ)保護(hù) 44.1.1 4.1.1 存儲(chǔ)器的層次存儲(chǔ)器的層次寄存器寄存器高速緩存高速緩存主存儲(chǔ)器主存儲(chǔ)器磁盤(pán)緩存磁盤(pán)緩存固定磁盤(pán)固定磁盤(pán)可移動(dòng)存儲(chǔ)介質(zhì)可移動(dòng)存儲(chǔ)介質(zhì)5 邏輯地址（虛地址）：邏輯地址（虛地址）：CPUCPU所生成的地址所生成的地址 物理地址（實(shí)地址）：內(nèi)存單元

3、所看到的地址物理地址（實(shí)地址）：內(nèi)存單元所看到的地址 邏輯地址空間：由程序所生成的所有邏輯地址的邏輯地址空間：由程序所生成的所有邏輯地址的集合集合 物理地址空間：由邏輯地址所對(duì)應(yīng)的所有物理地物理地址空間：由邏輯地址所對(duì)應(yīng)的所有物理地址的集合址的集合 地址轉(zhuǎn)換或重定位：把邏輯地址轉(zhuǎn)換為物理地址地址轉(zhuǎn)換或重定位：把邏輯地址轉(zhuǎn)換為物理地址4.1.2 4.1.2 地址轉(zhuǎn)換與存儲(chǔ)保護(hù)（地址轉(zhuǎn)換與存儲(chǔ)保護(hù)（1 1）6 靜態(tài)重定位靜態(tài)重定位0地址轉(zhuǎn)換工作在進(jìn)程執(zhí)行前一次完成；地址轉(zhuǎn)換工作在進(jìn)程執(zhí)行前一次完成；0無(wú)須硬件支持，易于實(shí)現(xiàn)，但不允許程序在執(zhí)行過(guò)程無(wú)須硬件支持，易于實(shí)現(xiàn)，但不允許程序在執(zhí)行過(guò)程中移動(dòng)

4、位置。中移動(dòng)位置。0早期單用戶(hù)單任務(wù)系統(tǒng)早期單用戶(hù)單任務(wù)系統(tǒng) 動(dòng)態(tài)重定位動(dòng)態(tài)重定位0地址轉(zhuǎn)換推遲到最后的可能時(shí)刻，即進(jìn)程執(zhí)行時(shí)才完地址轉(zhuǎn)換推遲到最后的可能時(shí)刻，即進(jìn)程執(zhí)行時(shí)才完成；成；0允許程序在主存中移動(dòng)、便于主存共享、主存利用率允許程序在主存中移動(dòng)、便于主存共享、主存利用率高。高。地址轉(zhuǎn)換與存儲(chǔ)保護(hù)地址轉(zhuǎn)換與存儲(chǔ)保護(hù)(2)(2)7存儲(chǔ)保護(hù)存儲(chǔ)保護(hù) 問(wèn)題：保護(hù)操作系統(tǒng)不受用戶(hù)進(jìn)程所影響，保護(hù)用戶(hù)進(jìn)程問(wèn)題：保護(hù)操作系統(tǒng)不受用戶(hù)進(jìn)程所影響，保護(hù)用戶(hù)進(jìn)程不受其他用戶(hù)進(jìn)程所影響不受其他用戶(hù)進(jìn)程所影響 方法方法1)1)存儲(chǔ)鍵保護(hù)存儲(chǔ)鍵保護(hù)v系統(tǒng)將主存劃分成大小相等的若干存儲(chǔ)塊，并給每個(gè)存系統(tǒng)將主存劃分

5、成大小相等的若干存儲(chǔ)塊，并給每個(gè)存儲(chǔ)塊都分配一個(gè)單獨(dú)的保護(hù)鍵（鎖）；在程序狀態(tài)字儲(chǔ)塊都分配一個(gè)單獨(dú)的保護(hù)鍵（鎖）；在程序狀態(tài)字PSWPSW中設(shè)置有保護(hù)鍵字段，對(duì)不同的作業(yè)賦予不同的代中設(shè)置有保護(hù)鍵字段，對(duì)不同的作業(yè)賦予不同的代碼（鑰匙）；鑰匙和鎖相配才允許訪(fǎng)問(wèn)碼（鑰匙）；鑰匙和鎖相配才允許訪(fǎng)問(wèn)2)2)界限寄存器（下頁(yè)圖）界限寄存器（下頁(yè)圖）v上、下界防護(hù)上、下界防護(hù)：硬件為分給用戶(hù)作業(yè)的連續(xù)的主存空間：硬件為分給用戶(hù)作業(yè)的連續(xù)的主存空間設(shè)置一對(duì)上、下界，分別指向該存儲(chǔ)空間的上、下界設(shè)置一對(duì)上、下界，分別指向該存儲(chǔ)空間的上、下界v基址、限長(zhǎng)防護(hù)基址、限長(zhǎng)防護(hù)：基址寄存器存放當(dāng)前正執(zhí)行者的程序：基

6、址寄存器存放當(dāng)前正執(zhí)行者的程序地址空間所占分區(qū)的始址，限長(zhǎng)寄存器存放該地址空間地址空間所占分區(qū)的始址，限長(zhǎng)寄存器存放該地址空間的長(zhǎng)度的長(zhǎng)度地址轉(zhuǎn)換與存儲(chǔ)保護(hù)地址轉(zhuǎn)換與存儲(chǔ)保護(hù)(3)(3)8下限寄存器下限寄存器20002000上限寄存器上限寄存器35003500基址寄存器基址寄存器20002000限長(zhǎng)寄存器限長(zhǎng)寄存器15001500進(jìn)程進(jìn)程idid下限下限+ +上限寄存器上限寄存器基址基址+ +限長(zhǎng)寄存器限長(zhǎng)寄存器1 11000+19991000+19991000+9991000+9992 22000+35002000+35002000+15002000+15003 34000+50004000

7、+50004000+10004000+1000內(nèi)存映像內(nèi)存映像進(jìn)程1進(jìn)程2進(jìn)程3100019992000350040005000正運(yùn)行的進(jìn)程是進(jìn)程正運(yùn)行的進(jìn)程是進(jìn)程2 294.2 4.2 連續(xù)存儲(chǔ)空間管理連續(xù)存儲(chǔ)空間管理4.2.1 4.2.1 固定分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理 4.2.2 4.2.2 可變分區(qū)存儲(chǔ)管理可變分區(qū)存儲(chǔ)管理 4.2.3 4.2.3 伙伴系統(tǒng)伙伴系統(tǒng)4.2.4 4.2.4 主存不足的存儲(chǔ)管理技術(shù)主存不足的存儲(chǔ)管理技術(shù)104.2.1 4.2.1 固定分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理 固定分區(qū)存儲(chǔ)管理的基本思想固定分區(qū)存儲(chǔ)管理的基本思想0主存空間被分成數(shù)目固定不變的分區(qū)，各分區(qū)

8、主存空間被分成數(shù)目固定不變的分區(qū)，各分區(qū)的大小不等，每個(gè)分區(qū)只裝入一個(gè)作業(yè)。的大小不等，每個(gè)分區(qū)只裝入一個(gè)作業(yè)。 固定分區(qū)存儲(chǔ)管理的數(shù)據(jù)結(jié)構(gòu)固定分區(qū)存儲(chǔ)管理的數(shù)據(jù)結(jié)構(gòu)0主存分配表：指出各分區(qū)的起始地址和長(zhǎng)度；主存分配表：指出各分區(qū)的起始地址和長(zhǎng)度；0占用標(biāo)志：指示此分區(qū)是否被使用。占用標(biāo)志：指示此分區(qū)是否被使用。 作業(yè)進(jìn)入固定分區(qū)排隊(duì)策略作業(yè)進(jìn)入固定分區(qū)排隊(duì)策略0每個(gè)分區(qū)有單獨(dú)的作業(yè)等待隊(duì)列；每個(gè)分區(qū)有單獨(dú)的作業(yè)等待隊(duì)列；0所有等待處理的作業(yè)排成一個(gè)等待隊(duì)列。所有等待處理的作業(yè)排成一個(gè)等待隊(duì)列。11固定分區(qū)的優(yōu)缺點(diǎn)固定分區(qū)的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)優(yōu)點(diǎn)0能夠解決單道程序運(yùn)行在并發(fā)環(huán)境下不能與能夠解決單道程

9、序運(yùn)行在并發(fā)環(huán)境下不能與CPUCPU速度匹速度匹配的問(wèn)題配的問(wèn)題0解決了單道程序運(yùn)行時(shí)主存空間利用率低的問(wèn)題解決了單道程序運(yùn)行時(shí)主存空間利用率低的問(wèn)題0實(shí)現(xiàn)簡(jiǎn)單實(shí)現(xiàn)簡(jiǎn)單 缺點(diǎn)缺點(diǎn)0大作業(yè)可能無(wú)法裝入大作業(yè)可能無(wú)法裝入0主存空間利用率不高，會(huì)出現(xiàn)內(nèi)碎片主存空間利用率不高，會(huì)出現(xiàn)內(nèi)碎片0擴(kuò)充困難擴(kuò)充困難0限制多道運(yùn)行程序的個(gè)數(shù)限制多道運(yùn)行程序的個(gè)數(shù)124.2.2 4.2.2 可變分區(qū)存儲(chǔ)管理可變分區(qū)存儲(chǔ)管理 可變分區(qū)存儲(chǔ)管理是按作業(yè)的實(shí)際大小來(lái)劃可變分區(qū)存儲(chǔ)管理是按作業(yè)的實(shí)際大小來(lái)劃分分區(qū)，且分區(qū)個(gè)數(shù)也是隨機(jī)的分分區(qū)，且分區(qū)個(gè)數(shù)也是隨機(jī)的, ,實(shí)現(xiàn)多個(gè)實(shí)現(xiàn)多個(gè)作業(yè)對(duì)主存的共享，進(jìn)一步提高主存資源利

10、作業(yè)對(duì)主存的共享，進(jìn)一步提高主存資源利用率。用率。 13可變分區(qū)方式主存分配示例可變分區(qū)方式主存分配示例操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)1 1空閑區(qū)空閑區(qū)作業(yè)作業(yè)2 2空閑區(qū)空閑區(qū)4KB4KB10KB10KB46KB46KB52KB52KB128KB128KB操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)1 1空閑區(qū)空閑區(qū)作業(yè)作業(yè)2 2空閑區(qū)空閑區(qū)4KB4KB10KB10KB40KB40KB46KB46KB52KB52KB128KB128KB作業(yè)作業(yè)3 3操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)1 1空閑區(qū)空閑區(qū)4KB4KB10KB10KB40KB40KB128KB128KB作業(yè)作業(yè)3 314可變分區(qū)存儲(chǔ)管理數(shù)據(jù)結(jié)構(gòu)可變分區(qū)存儲(chǔ)管理數(shù)據(jù)結(jié)

11、構(gòu) 可變分區(qū)主存分配表可由兩張表格組成，可變分區(qū)主存分配表可由兩張表格組成， 已分配區(qū)表已分配區(qū)表 未分配區(qū)表未分配區(qū)表15可變分區(qū)回收算法可變分區(qū)回收算法A AX XA AX XB BX XB BA AX XA AB BB B16鏈表空閑區(qū)管理方法鏈表空閑區(qū)管理方法 空閑區(qū)開(kāi)頭單元存放本空閑區(qū)長(zhǎng)度及下個(gè)空閑區(qū)開(kāi)頭單元存放本空閑區(qū)長(zhǎng)度及下個(gè)空閑區(qū)起始地址空閑區(qū)起始地址, ,把所有空閑區(qū)都鏈接起來(lái)把所有空閑區(qū)都鏈接起來(lái), ,設(shè)置第一塊空閑區(qū)地址指針設(shè)置第一塊空閑區(qū)地址指針, ,讓它指向第讓它指向第一塊空閑區(qū)地址。一塊空閑區(qū)地址。 申請(qǐng)空閑區(qū)：沿鏈查找并取一個(gè)長(zhǎng)度能滿(mǎn)申請(qǐng)空閑區(qū)：沿鏈查找并取一個(gè)長(zhǎng)

12、度能滿(mǎn)足要求的空閑區(qū)；足要求的空閑區(qū)； 歸還空閑區(qū)：把此空閑區(qū)鏈入空閑區(qū)鏈表歸還空閑區(qū)：把此空閑區(qū)鏈入空閑區(qū)鏈表的相應(yīng)位置。的相應(yīng)位置。17可變分區(qū)管理分配算法可變分區(qū)管理分配算法1 1）最先適應(yīng)分配算法）最先適應(yīng)分配算法空閑區(qū)通常按空閑區(qū)通常按地址地址從小到大排列，分配第從小到大排列，分配第一個(gè)滿(mǎn)足長(zhǎng)度要求的空閑區(qū)；一個(gè)滿(mǎn)足長(zhǎng)度要求的空閑區(qū)；優(yōu)點(diǎn)：分配從低地址開(kāi)始，使高地址部分優(yōu)點(diǎn)：分配從低地址開(kāi)始，使高地址部分比較少用，以保持一個(gè)大空閑區(qū)，有利于比較少用，以保持一個(gè)大空閑區(qū)，有利于大作業(yè)的裝入；大作業(yè)的裝入；缺點(diǎn)：分區(qū)利用不均衡，回收分區(qū)比較麻缺點(diǎn)：分區(qū)利用不均衡，回收分區(qū)比較麻煩。煩。

13、182 2）下次適應(yīng)分配算法）下次適應(yīng)分配算法1 1）的變種，每次分配時(shí)從未分配區(qū)的上次掃描）的變種，每次分配時(shí)從未分配區(qū)的上次掃描結(jié)束處順序查找。結(jié)束處順序查找?？梢越鉀Q可以解決1 1）的缺點(diǎn)。）的缺點(diǎn)。3) 3) 最優(yōu)適應(yīng)分配算法最優(yōu)適應(yīng)分配算法分配能滿(mǎn)足要求的最小區(qū)。分配能滿(mǎn)足要求的最小區(qū)?？梢詫⒖臻e區(qū)按照可以將空閑區(qū)按照大小大小從小到大排列，查找第一從小到大排列，查找第一個(gè)滿(mǎn)足要求的。個(gè)滿(mǎn)足要求的。優(yōu)點(diǎn)：主存利用率好。優(yōu)點(diǎn)：主存利用率好。缺點(diǎn)：分割剩下的空閑區(qū)比較小，難以利用；查缺點(diǎn)：分割剩下的空閑區(qū)比較小，難以利用；查找時(shí)間比較長(zhǎng)。找時(shí)間比較長(zhǎng)。194 4）最壞適應(yīng)分配算法）最壞適應(yīng)

14、分配算法分配能滿(mǎn)足要求的最大區(qū)；分配能滿(mǎn)足要求的最大區(qū)；可以將空閑區(qū)按照可以將空閑區(qū)按照大小大小從大到小排列，查找第一從大到小排列，查找第一個(gè)滿(mǎn)足要求的。個(gè)滿(mǎn)足要求的。效率大致等同于最先適應(yīng)法。效率大致等同于最先適應(yīng)法。5) 5) 快速適應(yīng)分配算法快速適應(yīng)分配算法為經(jīng)常用到的長(zhǎng)度的空閑區(qū)設(shè)置單獨(dú)的鏈表。為經(jīng)常用到的長(zhǎng)度的空閑區(qū)設(shè)置單獨(dú)的鏈表。優(yōu)點(diǎn)：查找快速；優(yōu)點(diǎn)：查找快速；缺點(diǎn)：歸還時(shí)與相鄰空閑區(qū)的合并即復(fù)雜又費(fèi)時(shí)缺點(diǎn)：歸還時(shí)與相鄰空閑區(qū)的合并即復(fù)雜又費(fèi)時(shí)。 20下表為某系統(tǒng)中的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲(chǔ)管下表為某系統(tǒng)中的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲(chǔ)管理策略?，F(xiàn)有以下作業(yè)序列：理

15、策略。現(xiàn)有以下作業(yè)序列：96KB96KB，20KB20KB，200KB200KB，分別使，分別使用首次適應(yīng)、最佳適用和最壞適用算法來(lái)處理這個(gè)作業(yè)序列用首次適應(yīng)、最佳適用和最壞適用算法來(lái)處理這個(gè)作業(yè)序列，試問(wèn)哪一種算法可以滿(mǎn)足該作業(yè)序列的請(qǐng)求，為什么？，試問(wèn)哪一種算法可以滿(mǎn)足該作業(yè)序列的請(qǐng)求，為什么？分區(qū)號(hào)分區(qū)號(hào)大小大小起始地址起始地址1 132KB32KB100KB100KB2 210KB10KB150KB150KB3 35KB5KB200KB200KB4 4218KB218KB220KB220KB5 596KB96KB530KB530KB例題：例題：FF(N)FF(N)BF(Y)BF(Y)W

16、F(N)WF(N)2/20/122/20/122/20/122/20/121/96/1221/96/122 3/200/183/200/181/96/1221/96/1222/20/1022/20/1021/96/01/96/0214.2.3 4.2.3 伙伴系統(tǒng)伙伴系統(tǒng)伙伴原理伙伴原理 伙伴系統(tǒng)是一種固定分區(qū)和可變分區(qū)折中的主存管理算伙伴系統(tǒng)是一種固定分區(qū)和可變分區(qū)折中的主存管理算法，基本原理：任何尺寸為法，基本原理：任何尺寸為2 2i i的空閑塊可以被分為兩個(gè)尺的空閑塊可以被分為兩個(gè)尺寸為寸為2 2i-1i-1的空閑塊，這兩個(gè)空閑塊稱(chēng)為伙伴。的空閑塊，這兩個(gè)空閑塊稱(chēng)為伙伴。 伙伴通過(guò)對(duì)大塊

17、的物理主存劃分而獲得伙伴通過(guò)對(duì)大塊的物理主存劃分而獲得0假如從第假如從第0 0個(gè)頁(yè)面開(kāi)始到第個(gè)頁(yè)面開(kāi)始到第3 3個(gè)頁(yè)面結(jié)束的主存?zhèn)€頁(yè)面結(jié)束的主存0每次都對(duì)半劃分，那么第一次劃分獲得大小為每次都對(duì)半劃分，那么第一次劃分獲得大小為2 2頁(yè)的伙頁(yè)的伙伴，如伴，如0 0、1 1和和2 2、3 30進(jìn)一步劃分，可以獲得大小為進(jìn)一步劃分，可以獲得大小為1 1頁(yè)的伙伴，例如頁(yè)的伙伴，例如0 0和和1 1，2 2和和3 30123012322伙伴系統(tǒng)原理伙伴系統(tǒng)原理128k 256k 384k 512k 640k 768k 896k 1M128k 256k 384k 512k 640k 768k 896k 1

18、M A A 128128 256256 512 512 A AB B6464 256256 512512 A AB B6464 C C 128128 512512 128128B B6464 C C 128128 512512 128128B BD D C C 128128 512512 1281286464D D C C 128128 512512 256256 C C 128128 512512 10241024234.2.4 4.2.4 主存不足的存儲(chǔ)管理技術(shù)主存不足的存儲(chǔ)管理技術(shù) 操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)1 1空閑區(qū)空閑區(qū)作業(yè)作業(yè)2 2空閑區(qū)空閑區(qū)作業(yè)作業(yè)3 3空閑區(qū)空閑區(qū)操作系統(tǒng)操作

19、系統(tǒng)作業(yè)作業(yè)1 1作業(yè)作業(yè)2 2作業(yè)作業(yè)3 3空閑區(qū)空閑區(qū)操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)1 1作業(yè)作業(yè)2 2作業(yè)作業(yè)3 3空閑區(qū)空閑區(qū)作業(yè)作業(yè)4 41.1.移動(dòng)技術(shù)移動(dòng)技術(shù)24有關(guān)移動(dòng)問(wèn)題討論有關(guān)移動(dòng)問(wèn)題討論 移動(dòng)條件移動(dòng)條件0在可變分區(qū)算法中，隨著進(jìn)程不斷的裝入和撤銷(xiāo)，導(dǎo)致在可變分區(qū)算法中，隨著進(jìn)程不斷的裝入和撤銷(xiāo)，導(dǎo)致主存中常常出現(xiàn)分散的小空閑區(qū)，稱(chēng)為主存中常常出現(xiàn)分散的小空閑區(qū)，稱(chēng)為碎片碎片。0當(dāng)在未分配區(qū)中找不到足夠大的空閑區(qū)來(lái)裝入新進(jìn)程時(shí)當(dāng)在未分配區(qū)中找不到足夠大的空閑區(qū)來(lái)裝入新進(jìn)程時(shí)，可采用移動(dòng)技術(shù)，將分散的空閑區(qū)匯集成片。，可采用移動(dòng)技術(shù)，將分散的空閑區(qū)匯集成片。 移動(dòng)時(shí)機(jī)移動(dòng)時(shí)機(jī)0進(jìn)

20、程撤銷(xiāo)之后釋放分區(qū)時(shí)，如果它不與空閑區(qū)鄰接，立進(jìn)程撤銷(xiāo)之后釋放分區(qū)時(shí)，如果它不與空閑區(qū)鄰接，立即實(shí)施移動(dòng)。即實(shí)施移動(dòng)。0進(jìn)程裝入分區(qū)時(shí)，如果它不與空閑區(qū)鄰接，立即實(shí)施引進(jìn)程裝入分區(qū)時(shí)，如果它不與空閑區(qū)鄰接，立即實(shí)施引動(dòng)。動(dòng)。25 移動(dòng)算法（假設(shè)進(jìn)程移動(dòng)算法（假設(shè)進(jìn)程A A請(qǐng)求分配請(qǐng)求分配x KBx KB主存）主存）0步驟步驟1 1：查主存分配表，若有大于：查主存分配表，若有大于x KBx KB的空閑區(qū)，轉(zhuǎn)步的空閑區(qū)，轉(zhuǎn)步驟驟4 4；0步驟步驟2 2：若空閑區(qū)總和小于：若空閑區(qū)總和小于x KBx KB，則令進(jìn)程，則令進(jìn)程A A等待主存等待主存資源；資源；0步驟步驟3 3：移動(dòng)主存的相關(guān)分區(qū)信息；

21、修改主存分配表的：移動(dòng)主存的相關(guān)分區(qū)信息；修改主存分配表的有關(guān)表項(xiàng)；修改被移動(dòng)者的基礎(chǔ)寄存器等信息；有關(guān)表項(xiàng)；修改被移動(dòng)者的基礎(chǔ)寄存器等信息；0步驟步驟4 4：分配：分配x KBx KB主存；修改主存分配表的有關(guān)項(xiàng)；設(shè)主存；修改主存分配表的有關(guān)項(xiàng)；設(shè)置進(jìn)程置進(jìn)程A A的基址寄存器；有申請(qǐng)者等待時(shí)予以釋放，算的基址寄存器；有申請(qǐng)者等待時(shí)予以釋放，算法結(jié)束。法結(jié)束。 開(kāi)銷(xiāo)非常大，極少使用開(kāi)銷(xiāo)非常大，極少使用262.2.對(duì)換技術(shù)對(duì)換技術(shù) 對(duì)換的作用對(duì)換的作用0通過(guò)將主存和磁盤(pán)的進(jìn)程移出移入，解決主存通過(guò)將主存和磁盤(pán)的進(jìn)程移出移入，解決主存容量不足的問(wèn)題。容量不足的問(wèn)題。 對(duì)換進(jìn)程的選擇對(duì)換進(jìn)程的選擇

22、0選擇哪個(gè)進(jìn)程換出；選擇哪個(gè)進(jìn)程換出；0決定把進(jìn)程的哪些信息移出去；決定把進(jìn)程的哪些信息移出去；0需要確定對(duì)換時(shí)機(jī)。需要確定對(duì)換時(shí)機(jī)。 UNIXUNIX對(duì)換器對(duì)換器 WindowsWindows對(duì)換器對(duì)換器27在任何時(shí)候只在內(nèi)存中保留所需的指令和數(shù)據(jù)在任何時(shí)候只在內(nèi)存中保留所需的指令和數(shù)據(jù)由用戶(hù)實(shí)現(xiàn)，由用戶(hù)實(shí)現(xiàn)，讓不會(huì)同時(shí)調(diào)用的子模塊共同使用讓不會(huì)同時(shí)調(diào)用的子模塊共同使用同一內(nèi)存區(qū)同一內(nèi)存區(qū)F20KD22KE24KB12KC15KA30K常駐常駐A A（30KB30KB）覆蓋區(qū)覆蓋區(qū)0 0（15KB15KB）覆蓋區(qū)覆蓋區(qū)1 1（24KB24KB）A占用占用BC共用共用DEF共用共用3.3.覆蓋

23、技術(shù)覆蓋技術(shù)28碎片碎片 外部碎片外部碎片：存在分區(qū)外，所有內(nèi)存之和可以滿(mǎn)足：存在分區(qū)外，所有內(nèi)存之和可以滿(mǎn)足請(qǐng)求，但不連續(xù)請(qǐng)求，但不連續(xù) 內(nèi)部碎片內(nèi)部碎片：存在分區(qū)內(nèi)，但已不能滿(mǎn)足任何請(qǐng)求：存在分區(qū)內(nèi)，但已不能滿(mǎn)足任何請(qǐng)求 解決外部碎片問(wèn)題的方法解決外部碎片問(wèn)題的方法0緊縮（緊縮（compactioncompaction）：移動(dòng)內(nèi)存內(nèi)容，以便所有空閑）：移動(dòng)內(nèi)存內(nèi)容，以便所有空閑空間合并成一整塊空間合并成一整塊0允許物理地址空間為非連續(xù)允許物理地址空間為非連續(xù)x 分頁(yè)分頁(yè)x 分段分段294.3 4.3 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理4.3.1 4.3.1 分頁(yè)式存儲(chǔ)管理的基本原理分頁(yè)式存儲(chǔ)管理

24、的基本原理 4.3.2 4.3.2 快表快表4.3.3 4.3.3 分頁(yè)式存儲(chǔ)空間的分配和去配分頁(yè)式存儲(chǔ)空間的分配和去配4.3.4 4.3.4 分頁(yè)式存儲(chǔ)空間的頁(yè)面共享和保護(hù)分頁(yè)式存儲(chǔ)空間的頁(yè)面共享和保護(hù)4.3.5 4.3.5 多級(jí)頁(yè)表多級(jí)頁(yè)表4.3.6 4.3.6 反置頁(yè)表反置頁(yè)表304.3.1 4.3.1 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理l為什么要引進(jìn)分頁(yè)技術(shù)為什么要引進(jìn)分頁(yè)技術(shù)? ?l基本原理基本原理 頁(yè)面：進(jìn)程邏輯地址空間分成大小相等的區(qū)；頁(yè)面：進(jìn)程邏輯地址空間分成大小相等的區(qū)； 頁(yè)框（幀）：主存物理地址空間分成大小相等頁(yè)框（幀）：主存物理地址空間分成大小相等的區(qū)，其大小跟頁(yè)面大小相等；的

25、區(qū)，其大小跟頁(yè)面大小相等； 邏輯地址形式：頁(yè)號(hào)頁(yè)內(nèi)位移邏輯地址形式：頁(yè)號(hào)頁(yè)內(nèi)位移 頁(yè)表和地址轉(zhuǎn)換（后面圖）頁(yè)表和地址轉(zhuǎn)換（后面圖） 基本原理基本原理(1)31基本原理基本原理(2)(2)l作業(yè)的頁(yè)面與分給的頁(yè)框如何建立聯(lián)系呢？作業(yè)的頁(yè)面與分給的頁(yè)框如何建立聯(lián)系呢？l邏輯地址邏輯地址( (頁(yè)面頁(yè)面) )如何變換成物理地址如何變換成物理地址( (頁(yè)框頁(yè)框) )呢？呢？l作業(yè)的物理地址空間由連續(xù)變成分散后，如作業(yè)的物理地址空間由連續(xù)變成分散后，如何保證程序正確執(zhí)行呢？何保證程序正確執(zhí)行呢？使用動(dòng)態(tài)重定位技術(shù)，給每個(gè)頁(yè)面設(shè)立重定使用動(dòng)態(tài)重定位技術(shù)，給每個(gè)頁(yè)面設(shè)立重定位寄存器，重定位寄存器的集合便稱(chēng)位寄

26、存器，重定位寄存器的集合便稱(chēng)頁(yè)表頁(yè)表。頁(yè)表是操作系統(tǒng)為每個(gè)用戶(hù)作業(yè)建立的，用頁(yè)表是操作系統(tǒng)為每個(gè)用戶(hù)作業(yè)建立的，用來(lái)記錄程序頁(yè)面和主存對(duì)應(yīng)頁(yè)框的對(duì)照表。來(lái)記錄程序頁(yè)面和主存對(duì)應(yīng)頁(yè)框的對(duì)照表。32頁(yè)頁(yè)0 0頁(yè)頁(yè)1 1頁(yè)頁(yè)2 2頁(yè)頁(yè)3 31 14 43 37 70 1 2 3頁(yè)頁(yè)0 0頁(yè)頁(yè)2 2頁(yè)頁(yè)1 1頁(yè)頁(yè)3 30 1 2 3 4 5 6 7邏輯內(nèi)存邏輯內(nèi)存頁(yè)表頁(yè)表物理內(nèi)存物理內(nèi)存頁(yè)號(hào)頁(yè)號(hào) 幀號(hào)幀號(hào)幀號(hào)幀號(hào)物理內(nèi)存和邏輯內(nèi)存的分頁(yè)模型物理內(nèi)存和邏輯內(nèi)存的分頁(yè)模型33邏輯地址到物理地址的轉(zhuǎn)換邏輯地址到物理地址的轉(zhuǎn)換56120 1 2 3頁(yè)表頁(yè)表例：例：說(shuō)明：頁(yè)大小為說(shuō)明：頁(yè)大小為4B4B，頁(yè)表如圖

27、所示，頁(yè)表如圖所示，將邏輯地址，將邏輯地址0 0、3 3、4 4、1313轉(zhuǎn)換為相轉(zhuǎn)換為相應(yīng)物理地址應(yīng)物理地址答案：答案：2020、2323、2424、9 90/4=00/4=00 50 54+0=204+0=203/4=03/4=03 53 54+3=234+3=234/4=14/4=10 60 64+0=244+0=2413/4=313/4=31 21 24+1=94+1=934練習(xí)：邏輯地址到物理地址的轉(zhuǎn)換練習(xí)：邏輯地址到物理地址的轉(zhuǎn)換 說(shuō)明：頁(yè)大小為說(shuō)明：頁(yè)大小為1024B1024B，頁(yè)表如圖所示，頁(yè)表如圖所示，將邏輯地址，將邏輯地址10111011、21482148、30003000

28、、40004000、50125012轉(zhuǎn)換為相應(yīng)物理地址轉(zhuǎn)換為相應(yīng)物理地址23160 1 2 3頁(yè)表頁(yè)表 答案：答案：30593059、11241124、19761976、70727072、邏、邏輯地址非法輯地址非法1011/1024=01011/1024=01011 21011 21024+1011=30591024+1011=30592148/1024=22148/1024=2100 1100 11024+100=11241024+100=11243000/1024=23000/1024=2952 1952 11024+952=19761024+952=19764000/1024=34000

29、/1024=3928 6928 61024+928=70721024+928=70725012/1024=45012/1024=4916 916 頁(yè)號(hào)頁(yè)號(hào)4 4不存在不存在354.3.2 4.3.2 快表快表 相聯(lián)存儲(chǔ)器（翻譯后備緩沖（相聯(lián)存儲(chǔ)器（翻譯后備緩沖（translation translation look-aside bufferlook-aside buffer，TLBTLB）：關(guān)聯(lián)的快速內(nèi)存）：關(guān)聯(lián)的快速內(nèi)存 TLBTLB與頁(yè)表一起工作與頁(yè)表一起工作0快表項(xiàng)包含頁(yè)號(hào)及對(duì)應(yīng)的頁(yè)框號(hào)，當(dāng)把頁(yè)號(hào)交給快表快表項(xiàng)包含頁(yè)號(hào)及對(duì)應(yīng)的頁(yè)框號(hào)，當(dāng)把頁(yè)號(hào)交給快表后，它通過(guò)并行匹配同時(shí)對(duì)所有快表項(xiàng)進(jìn)

30、行比較。后，它通過(guò)并行匹配同時(shí)對(duì)所有快表項(xiàng)進(jìn)行比較。0如果找到，立即輸出頁(yè)框號(hào)，并形成物理地址；如果找到，立即輸出頁(yè)框號(hào)，并形成物理地址；0如果找不到，再查找主存中的頁(yè)表以形成物理地址，如果找不到，再查找主存中的頁(yè)表以形成物理地址，同時(shí)將頁(yè)號(hào)和頁(yè)框號(hào)登記到快表中；同時(shí)將頁(yè)號(hào)和頁(yè)框號(hào)登記到快表中；0當(dāng)快表已滿(mǎn)且要登記新頁(yè)時(shí)，系統(tǒng)需要淘汰舊的快表當(dāng)快表已滿(mǎn)且要登記新頁(yè)時(shí)，系統(tǒng)需要淘汰舊的快表項(xiàng)。項(xiàng)。36采用相聯(lián)存儲(chǔ)器的地址轉(zhuǎn)換采用相聯(lián)存儲(chǔ)器的地址轉(zhuǎn)換假定訪(fǎng)問(wèn)主存時(shí)間為假定訪(fǎng)問(wèn)主存時(shí)間為100100毫微秒，訪(fǎng)問(wèn)相聯(lián)存儲(chǔ)器毫微秒，訪(fǎng)問(wèn)相聯(lián)存儲(chǔ)器時(shí)間為時(shí)間為2020毫微秒，相聯(lián)存儲(chǔ)器為毫微秒，相聯(lián)存儲(chǔ)器

31、為3232個(gè)單元時(shí)快表個(gè)單元時(shí)快表命中率可達(dá)命中率可達(dá)90%90%，按邏輯地址存取的平均時(shí)間為：，按邏輯地址存取的平均時(shí)間為：（1001002020）90%90%(100+100+20)(100+100+20)(1-90%)(1-90%)130130比兩次訪(fǎng)問(wèn)主存的時(shí)間比兩次訪(fǎng)問(wèn)主存的時(shí)間1001002 2200200下降了三成多下降了三成多。374.3.3 4.3.3 分頁(yè)式存儲(chǔ)空間的分配和去配分頁(yè)式存儲(chǔ)空間的分配和去配(1)(1) 位示圖法位示圖法0每位與一幀相對(duì)應(yīng)，用每位與一幀相對(duì)應(yīng)，用0/10/1表示對(duì)應(yīng)塊為空閑表示對(duì)應(yīng)塊為空閑/ /已占用，用另一專(zhuān)門(mén)字記錄當(dāng)前空閑塊數(shù)。已占用，用另一

32、專(zhuān)門(mén)字記錄當(dāng)前空閑塊數(shù)。 鏈表方法鏈表方法0每個(gè)表項(xiàng)包含：每個(gè)表項(xiàng)包含：x進(jìn)程占用區(qū)（進(jìn)程占用區(qū)（P P）還是空閑區(qū)（）還是空閑區(qū)（H H）x起始地址起始地址x長(zhǎng)度長(zhǎng)度x指向下一表項(xiàng)的指針指向下一表項(xiàng)的指針38主存分配的位示圖和鏈表方法主存分配的位示圖和鏈表方法394.3.4 4.3.4 分頁(yè)存儲(chǔ)空間的頁(yè)面共享和保護(hù)分頁(yè)存儲(chǔ)空間的頁(yè)面共享和保護(hù) 數(shù)據(jù)共享數(shù)據(jù)共享0允許不同進(jìn)程對(duì)共享的數(shù)據(jù)頁(yè)用不同的頁(yè)號(hào)，允許不同進(jìn)程對(duì)共享的數(shù)據(jù)頁(yè)用不同的頁(yè)號(hào)，只要讓各自頁(yè)表中的有關(guān)表項(xiàng)指向共享的數(shù)據(jù)只要讓各自頁(yè)表中的有關(guān)表項(xiàng)指向共享的數(shù)據(jù)頁(yè)框；頁(yè)框； 程序共享程序共享0指令包含指向其它指令或數(shù)據(jù)的地址。指令包含

33、指向其它指令或數(shù)據(jù)的地址。 標(biāo)志位保護(hù)方法標(biāo)志位保護(hù)方法0在頁(yè)表中增加標(biāo)志位，指出此頁(yè)的信息只讀在頁(yè)表中增加標(biāo)志位，指出此頁(yè)的信息只讀/ /讀寫(xiě)讀寫(xiě)/ /只可執(zhí)行只可執(zhí)行/ /不可訪(fǎng)問(wèn)等。不可訪(fǎng)問(wèn)等。 鍵保護(hù)方法鍵保護(hù)方法404.3.5 4.3.5 多級(jí)頁(yè)表多級(jí)頁(yè)表 多級(jí)頁(yè)表的概念多級(jí)頁(yè)表的概念 多級(jí)頁(yè)表的具體做法多級(jí)頁(yè)表的具體做法 邏輯地址結(jié)構(gòu)邏輯地址結(jié)構(gòu) 邏輯地址到物理地址轉(zhuǎn)換過(guò)程邏輯地址到物理地址轉(zhuǎn)換過(guò)程41多級(jí)頁(yè)表的概念多級(jí)頁(yè)表的概念 系統(tǒng)為每個(gè)進(jìn)程建一張頁(yè)目錄表系統(tǒng)為每個(gè)進(jìn)程建一張頁(yè)目錄表, ,它的每個(gè)表項(xiàng)它的每個(gè)表項(xiàng)對(duì)應(yīng)一個(gè)頁(yè)表頁(yè)對(duì)應(yīng)一個(gè)頁(yè)表頁(yè), ,而頁(yè)表頁(yè)的每個(gè)表項(xiàng)給出了頁(yè)而頁(yè)表

34、頁(yè)的每個(gè)表項(xiàng)給出了頁(yè)面和頁(yè)框的對(duì)應(yīng)關(guān)系面和頁(yè)框的對(duì)應(yīng)關(guān)系, ,頁(yè)目錄表是一級(jí)頁(yè)表頁(yè)目錄表是一級(jí)頁(yè)表, ,頁(yè)表頁(yè)表頁(yè)是二級(jí)頁(yè)表。頁(yè)是二級(jí)頁(yè)表。 邏輯地址結(jié)構(gòu)有三部分組成：頁(yè)目錄、頁(yè)表頁(yè)和邏輯地址結(jié)構(gòu)有三部分組成：頁(yè)目錄、頁(yè)表頁(yè)和位移。位移。 42多級(jí)頁(yè)表地址轉(zhuǎn)換過(guò)程多級(jí)頁(yè)表地址轉(zhuǎn)換過(guò)程 頁(yè)框號(hào)頁(yè)框號(hào) 頁(yè)內(nèi)位移頁(yè)內(nèi)位移 頁(yè)目錄位移頁(yè)目錄位移 頁(yè)表頁(yè)位移頁(yè)表頁(yè)位移 頁(yè)內(nèi)位移頁(yè)內(nèi)位移B BF F進(jìn)程一級(jí)頁(yè)表進(jìn)程一級(jí)頁(yè)表進(jìn)程二級(jí)頁(yè)表進(jìn)程二級(jí)頁(yè)表物理地址物理地址邏輯地址邏輯地址頁(yè)目錄表頁(yè)目錄表控制寄存器控制寄存器43解決頁(yè)表頁(yè)占用主存空間的問(wèn)題解決頁(yè)表頁(yè)占用主存空間的問(wèn)題 進(jìn)程運(yùn)行涉及頁(yè)面的頁(yè)表頁(yè)應(yīng)放在主

35、存進(jìn)程運(yùn)行涉及頁(yè)面的頁(yè)表頁(yè)應(yīng)放在主存, ,其其他頁(yè)表頁(yè)使用時(shí)再調(diào)入他頁(yè)表頁(yè)使用時(shí)再調(diào)入, , 在頁(yè)目錄表中增加特征位在頁(yè)目錄表中增加特征位, ,指示對(duì)應(yīng)的頁(yè)表指示對(duì)應(yīng)的頁(yè)表頁(yè)是否已調(diào)入主存頁(yè)是否已調(diào)入主存, , 地址轉(zhuǎn)換機(jī)構(gòu)根據(jù)邏輯地址中的地址轉(zhuǎn)換機(jī)構(gòu)根據(jù)邏輯地址中的dir,dir,去查去查頁(yè)目錄表對(duì)應(yīng)表項(xiàng)頁(yè)目錄表對(duì)應(yīng)表項(xiàng), ,如未調(diào)入如未調(diào)入, ,應(yīng)產(chǎn)生一個(gè)應(yīng)產(chǎn)生一個(gè)”缺頁(yè)表頁(yè)缺頁(yè)表頁(yè)”中斷信號(hào)，請(qǐng)求操作系統(tǒng)將中斷信號(hào)，請(qǐng)求操作系統(tǒng)將頁(yè)表頁(yè)調(diào)入主存。頁(yè)表頁(yè)調(diào)入主存。444.3.5 4.3.5 反置頁(yè)表反置頁(yè)表(1)(1) 頁(yè)框號(hào)頁(yè)框號(hào) 位移位移進(jìn)程標(biāo)識(shí)進(jìn)程標(biāo)識(shí) 頁(yè)號(hào)頁(yè)號(hào) 位移位移 進(jìn)程標(biāo)識(shí)進(jìn)

36、程標(biāo)識(shí) 頁(yè)號(hào)頁(yè)號(hào) 特征位特征位 鏈指針鏈指針 序號(hào)序號(hào)反置頁(yè)表反置頁(yè)表物理地址物理地址邏輯地址邏輯地址哈希哈希函數(shù)函數(shù)哈希表哈希表反置頁(yè)表及其地址轉(zhuǎn)換反置頁(yè)表及其地址轉(zhuǎn)換45反置頁(yè)表反置頁(yè)表(2)(2) IPTIPT是為主存中的每一個(gè)物理塊建立一個(gè)頁(yè)是為主存中的每一個(gè)物理塊建立一個(gè)頁(yè)表并按照塊號(hào)排序表并按照塊號(hào)排序, , 該表每個(gè)表項(xiàng)包含正在訪(fǎng)問(wèn)該頁(yè)框的進(jìn)程該表每個(gè)表項(xiàng)包含正在訪(fǎng)問(wèn)該頁(yè)框的進(jìn)程標(biāo)識(shí)、頁(yè)號(hào)及特征位、哈希鏈指針標(biāo)識(shí)、頁(yè)號(hào)及特征位、哈希鏈指針, ,用來(lái)完用來(lái)完成邏輯地址到物理地址的轉(zhuǎn)換。成邏輯地址到物理地址的轉(zhuǎn)換。46反置頁(yè)表反置頁(yè)表(3)(3)反置頁(yè)表地址轉(zhuǎn)換過(guò)程如下反置頁(yè)表地址轉(zhuǎn)

37、換過(guò)程如下: :邏輯地址給出進(jìn)程標(biāo)識(shí)和頁(yè)號(hào)邏輯地址給出進(jìn)程標(biāo)識(shí)和頁(yè)號(hào), ,用它們?nèi)ケ容^用它們?nèi)ケ容^IPT,IPT,若整個(gè)反置頁(yè)表中未能找到匹配的頁(yè)表項(xiàng)若整個(gè)反置頁(yè)表中未能找到匹配的頁(yè)表項(xiàng), ,說(shuō)明該頁(yè)不在主存說(shuō)明該頁(yè)不在主存, ,產(chǎn)生請(qǐng)頁(yè)中斷產(chǎn)生請(qǐng)頁(yè)中斷, ,請(qǐng)求操作系統(tǒng)請(qǐng)求操作系統(tǒng)調(diào)入調(diào)入; ;否則，該表項(xiàng)的序號(hào)便是頁(yè)框號(hào)否則，該表項(xiàng)的序號(hào)便是頁(yè)框號(hào), ,塊號(hào)加上塊號(hào)加上位移位移, ,便形成物理地址。便形成物理地址。47 分頁(yè)技術(shù)分頁(yè)技術(shù)不會(huì)不會(huì)產(chǎn)生產(chǎn)生外部碎片外部碎片，但，但會(huì)會(huì)產(chǎn)生產(chǎn)生內(nèi)內(nèi)部碎片部碎片 分頁(yè)的重要特點(diǎn)是用戶(hù)觀(guān)點(diǎn)的內(nèi)存和實(shí)際分頁(yè)的重要特點(diǎn)是用戶(hù)觀(guān)點(diǎn)的內(nèi)存和實(shí)際的物理內(nèi)存的分

38、離的物理內(nèi)存的分離 分頁(yè)可以共享共同代碼分頁(yè)可以共享共同代碼分頁(yè)內(nèi)存管理方案小結(jié)分頁(yè)內(nèi)存管理方案小結(jié)484.4 4.4 分段式存儲(chǔ)管理分段式存儲(chǔ)管理4.4.1 4.4.1 程序的分段結(jié)構(gòu)程序的分段結(jié)構(gòu)4.4.2 4.4.2 分段式存儲(chǔ)管理的基本原理分段式存儲(chǔ)管理的基本原理4.4.3 4.4.3 段的共享和保護(hù)段的共享和保護(hù)4.4.4 4.4.4 分段和分頁(yè)的比較分段和分頁(yè)的比較494.4.1 4.4.1 程序的分段結(jié)構(gòu)程序的分段結(jié)構(gòu) 分段存儲(chǔ)管理引入的主要原因分段存儲(chǔ)管理引入的主要原因0滿(mǎn)足用戶(hù)（程序員）編程和使用上的要求。滿(mǎn)足用戶(hù)（程序員）編程和使用上的要求。 模塊化程序設(shè)計(jì)的分段結(jié)構(gòu)（下頁(yè)

39、圖）模塊化程序設(shè)計(jì)的分段結(jié)構(gòu)（下頁(yè)圖） 分頁(yè)存儲(chǔ)管理分頁(yè)存儲(chǔ)管理-一維地址結(jié)構(gòu)一維地址結(jié)構(gòu) 分段存儲(chǔ)管理分段存儲(chǔ)管理-二維地址結(jié)構(gòu)二維地址結(jié)構(gòu)50模塊化程序設(shè)計(jì)的分段結(jié)構(gòu)模塊化程序設(shè)計(jì)的分段結(jié)構(gòu) 子程序段子程序段X X數(shù)組段數(shù)組段A Acall Xcall X( (調(diào)用調(diào)用X X段的入口段的入口E)E)call Ycall Y( (調(diào)用調(diào)用Y Y段的入口段的入口F)F)load 1,Aload 1,A ( (調(diào)用數(shù)組段調(diào)用數(shù)組段AG)AG)主程序段主程序段E E：F F：子程序段子程序段Y YG G：工作區(qū)段工作區(qū)段514.4.2 4.4.2 分段式存儲(chǔ)管理的基本原理分段式存儲(chǔ)管理的基本原理(

40、1)(1)l二維邏輯地址二維邏輯地址l段號(hào)：段內(nèi)地址段號(hào)：段內(nèi)地址l段表段表l段表指出主存中各分段的段號(hào)、段起始地址和段表指出主存中各分段的段號(hào)、段起始地址和段長(zhǎng)度，起到基址段長(zhǎng)度，起到基址/ /限長(zhǎng)寄存器的作用。限長(zhǎng)寄存器的作用。l段式存儲(chǔ)管理的地址轉(zhuǎn)換和存儲(chǔ)保護(hù)段式存儲(chǔ)管理的地址轉(zhuǎn)換和存儲(chǔ)保護(hù) 52分段式存儲(chǔ)管理的基本原理分段式存儲(chǔ)管理的基本原理(2)(2) 段控制寄存器段控制寄存器 段表始址段表始址 段表長(zhǎng)度段表長(zhǎng)度 段號(hào)段號(hào)s s 位移位移d d 段長(zhǎng)段長(zhǎng) 基址基址 物理地址物理地址越界越界? ? 段表段表53段表：將二維的邏輯地址映射為一維物理地址段表：將二維的邏輯地址映射為一維物理

41、地址段基地址：包含該段在內(nèi)存中的開(kāi)始物理地址段基地址：包含該段在內(nèi)存中的開(kāi)始物理地址段界限：指定該段的長(zhǎng)度段界限：指定該段的長(zhǎng)度邏輯地址：段號(hào)邏輯地址：段號(hào)s s段內(nèi)偏移段內(nèi)偏移d d邏輯地址到物理地址的轉(zhuǎn)換邏輯地址到物理地址的轉(zhuǎn)換1)1) 段號(hào)與段表長(zhǎng)度進(jìn)行比較，若段號(hào)超過(guò)了段表長(zhǎng)度段號(hào)與段表長(zhǎng)度進(jìn)行比較，若段號(hào)超過(guò)了段表長(zhǎng)度，則越界（非法地址），否則轉(zhuǎn)，則越界（非法地址），否則轉(zhuǎn)2 2）2)2) 根據(jù)段表始址和段號(hào)計(jì)算出該段對(duì)應(yīng)段表項(xiàng)的位置根據(jù)段表始址和段號(hào)計(jì)算出該段對(duì)應(yīng)段表項(xiàng)的位置，從中讀出該段在內(nèi)存的起始地址，檢查段內(nèi)地址，從中讀出該段在內(nèi)存的起始地址，檢查段內(nèi)地址是否超過(guò)該段的段長(zhǎng)，

42、若超過(guò)則越界（非法地址）是否超過(guò)該段的段長(zhǎng)，若超過(guò)則越界（非法地址），否則轉(zhuǎn)，否則轉(zhuǎn)3 3）3)3) 將該段的起始地址與段內(nèi)位移相加，從而得到要訪(fǎng)將該段的起始地址與段內(nèi)位移相加，從而得到要訪(fǎng)問(wèn)的物理地址問(wèn)的物理地址邏輯地址到物理地址轉(zhuǎn)換邏輯地址到物理地址轉(zhuǎn)換54邏輯地址到物理地址轉(zhuǎn)換例邏輯地址到物理地址轉(zhuǎn)換例說(shuō)明：段表如表說(shuō)明：段表如表1 1所示，將表所示，將表2 2所示邏輯地址轉(zhuǎn)換為相應(yīng)所示邏輯地址轉(zhuǎn)換為相應(yīng)物理地址物理地址答案：見(jiàn)表答案：見(jiàn)表3 3段號(hào)段號(hào) 內(nèi)存起始內(nèi)存起始地址地址段長(zhǎng)段長(zhǎng)0 02192196006001 12300230014142 290901001003 313271

43、3275805804 4195219529696段段號(hào)號(hào)段內(nèi)位段內(nèi)位移移2 288884 4100100178178非法非法 表表1 表表2 表表390+881009655說(shuō)明：段表如表說(shuō)明：段表如表1 1所示，將表所示，將表2 2所示邏輯地址轉(zhuǎn)換為相應(yīng)所示邏輯地址轉(zhuǎn)換為相應(yīng)物理地址物理地址答案：見(jiàn)表答案：見(jiàn)表3 3邏輯地址到物理地址轉(zhuǎn)換練習(xí)邏輯地址到物理地址轉(zhuǎn)換練習(xí)段號(hào)段號(hào)段內(nèi)位移段內(nèi)位移0 04304301 110102 25005003 34004004 41121125 53232段號(hào)段號(hào)內(nèi)存起始地址內(nèi)存起始地址段長(zhǎng)段長(zhǎng)0 02102105005001 12350235020202 2

44、10010090903 3135013505905904 4193819389595 表表1 表表264064023602360非法非法17501750非法非法非法非法表表3210+4302350+10500901350+40011295段號(hào)段號(hào)5不存在不存在564.4.3 4.4.3 段的共享段的共享 多對(duì)基址多對(duì)基址/ /限長(zhǎng)寄存器限長(zhǎng)寄存器 段的共享，是通過(guò)不同作業(yè)段表中的項(xiàng)指段的共享，是通過(guò)不同作業(yè)段表中的項(xiàng)指向同一個(gè)段基址來(lái)實(shí)現(xiàn)。向同一個(gè)段基址來(lái)實(shí)現(xiàn)。 幾道作業(yè)共享的例行程序就可放在一個(gè)段幾道作業(yè)共享的例行程序就可放在一個(gè)段中，只要讓各道作業(yè)的共享部分有相同的中，只要讓各道作業(yè)的共享

45、部分有相同的基址基址/ /限長(zhǎng)值。限長(zhǎng)值。 對(duì)共享段的信息必須進(jìn)行保護(hù)。對(duì)共享段的信息必須進(jìn)行保護(hù)。 574.4.4 4.4.4 分段和分頁(yè)的比較分段和分頁(yè)的比較(1)(1) 分段是信息的邏輯單位，由源程序的邏輯分段是信息的邏輯單位，由源程序的邏輯結(jié)構(gòu)所決定，用戶(hù)可見(jiàn)，結(jié)構(gòu)所決定，用戶(hù)可見(jiàn)， 段長(zhǎng)可根據(jù)用戶(hù)需要來(lái)規(guī)定，段起始地址段長(zhǎng)可根據(jù)用戶(hù)需要來(lái)規(guī)定，段起始地址可從任何主存地址開(kāi)始?？蓮娜魏沃鞔娴刂烽_(kāi)始。 分段方式中，源程序分段方式中，源程序( (段號(hào)，段內(nèi)位移段號(hào)，段內(nèi)位移) )經(jīng)經(jīng)連結(jié)裝配后地址仍保持二維結(jié)構(gòu)。連結(jié)裝配后地址仍保持二維結(jié)構(gòu)。58分段和分頁(yè)的比較分段和分頁(yè)的比較(2)(2)

46、 分頁(yè)是信息的物理單位，與源程序的邏輯分頁(yè)是信息的物理單位，與源程序的邏輯結(jié)構(gòu)無(wú)關(guān)，用戶(hù)不可見(jiàn)，結(jié)構(gòu)無(wú)關(guān)，用戶(hù)不可見(jiàn)， 頁(yè)長(zhǎng)由系統(tǒng)確定，頁(yè)面只能以頁(yè)大小的整頁(yè)長(zhǎng)由系統(tǒng)確定，頁(yè)面只能以頁(yè)大小的整倍數(shù)地址開(kāi)始。倍數(shù)地址開(kāi)始。 分頁(yè)方式中，源程序分頁(yè)方式中，源程序( (頁(yè)號(hào)，頁(yè)內(nèi)位移頁(yè)號(hào)，頁(yè)內(nèi)位移) )經(jīng)經(jīng)連結(jié)裝配后地址變成了一維結(jié)構(gòu)。連結(jié)裝配后地址變成了一維結(jié)構(gòu)。594.5 4.5 虛擬存儲(chǔ)管理虛擬存儲(chǔ)管理4.5.1 4.5.1 虛擬存儲(chǔ)管理的概念虛擬存儲(chǔ)管理的概念4.5.2 4.5.2 請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理4.5.3 4.5.3 請(qǐng)求分段虛擬存儲(chǔ)管理請(qǐng)求分段虛擬存儲(chǔ)管理4.5

47、.4 4.5.4 請(qǐng)求段頁(yè)式虛擬存儲(chǔ)管理請(qǐng)求段頁(yè)式虛擬存儲(chǔ)管理604.5.1 4.5.1 虛擬存儲(chǔ)管理的概念虛擬存儲(chǔ)管理的概念 虛擬內(nèi)存（虛擬內(nèi)存（virtual memoryvirtual memory）：允許進(jìn)程的執(zhí)行）：允許進(jìn)程的執(zhí)行不必完全在內(nèi)存中，程序可以比物理內(nèi)存大。不必完全在內(nèi)存中，程序可以比物理內(nèi)存大。 在許多情況下不需要將整個(gè)程序放到內(nèi)存中：在許多情況下不需要將整個(gè)程序放到內(nèi)存中：0處理異常錯(cuò)誤條件的代碼（幾乎不執(zhí)行）處理異常錯(cuò)誤條件的代碼（幾乎不執(zhí)行）0數(shù)組、鏈表和表通常分配了比實(shí)際所需更多的內(nèi)存數(shù)組、鏈表和表通常分配了比實(shí)際所需更多的內(nèi)存0程序的某些選項(xiàng)或特點(diǎn)可能很少使用

48、程序的某些選項(xiàng)或特點(diǎn)可能很少使用 能夠執(zhí)行只有部分在內(nèi)存中的程序的好處能夠執(zhí)行只有部分在內(nèi)存中的程序的好處0程序不再受現(xiàn)有的物理內(nèi)存空間限制程序不再受現(xiàn)有的物理內(nèi)存空間限制0更多程序可同時(shí)執(zhí)行，更多程序可同時(shí)執(zhí)行，CPUCPU利用率相應(yīng)增加利用率相應(yīng)增加0用戶(hù)程序會(huì)運(yùn)行的更快用戶(hù)程序會(huì)運(yùn)行的更快61虛擬存儲(chǔ)器虛擬存儲(chǔ)器 虛擬存儲(chǔ)器的定義：虛擬存儲(chǔ)器的定義：0在具有層次結(jié)構(gòu)存儲(chǔ)器的計(jì)算機(jī)系統(tǒng)中在具有層次結(jié)構(gòu)存儲(chǔ)器的計(jì)算機(jī)系統(tǒng)中，采用自動(dòng)實(shí)現(xiàn)部分裝入和部分對(duì)換功，采用自動(dòng)實(shí)現(xiàn)部分裝入和部分對(duì)換功能，為用戶(hù)提供一個(gè)比物理主存容量大能，為用戶(hù)提供一個(gè)比物理主存容量大得多的，可尋址的一種得多的，可尋址的

49、一種“主存儲(chǔ)器主存儲(chǔ)器”。 62虛擬存儲(chǔ)器的概念圖虛擬存儲(chǔ)器的概念圖 邏輯地址空間邏輯地址空間處理器處理器虛地址虛地址存儲(chǔ)存儲(chǔ)管理管理部件部件實(shí)地址實(shí)地址主存主存輔存輔存物理地址空間物理地址空間63程序的局部性原理程序的局部性原理 指程序在執(zhí)行過(guò)程中的一個(gè)較短時(shí)間內(nèi)，所指程序在執(zhí)行過(guò)程中的一個(gè)較短時(shí)間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲(chǔ)區(qū)域中。又可細(xì)分時(shí)間局部性和空定的存儲(chǔ)區(qū)域中。又可細(xì)分時(shí)間局部性和空間局部性。間局部性。時(shí)間局部性：最近訪(fǎng)問(wèn)過(guò)的程序代碼和數(shù)據(jù)很時(shí)間局部性：最近訪(fǎng)問(wèn)過(guò)的程序代碼和數(shù)據(jù)很快又被訪(fǎng)問(wèn)?？煊直辉L(fǎng)問(wèn)?？臻g局部性：某存

50、儲(chǔ)單元被使用之后，其相鄰空間局部性：某存儲(chǔ)單元被使用之后，其相鄰的存儲(chǔ)單元也很快被使用。的存儲(chǔ)單元也很快被使用。64實(shí)現(xiàn)虛擬存儲(chǔ)器須解決的問(wèn)題實(shí)現(xiàn)虛擬存儲(chǔ)器須解決的問(wèn)題l 主存輔存統(tǒng)一管理問(wèn)題主存輔存統(tǒng)一管理問(wèn)題l 邏輯地址到物理地址的轉(zhuǎn)換問(wèn)題邏輯地址到物理地址的轉(zhuǎn)換問(wèn)題l 部分裝入和部分對(duì)換問(wèn)題部分裝入和部分對(duì)換問(wèn)題65虛擬存儲(chǔ)管理實(shí)現(xiàn)技術(shù)虛擬存儲(chǔ)管理實(shí)現(xiàn)技術(shù)l 請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理l 請(qǐng)求分段虛擬存儲(chǔ)管理請(qǐng)求分段虛擬存儲(chǔ)管理l 請(qǐng)求段頁(yè)式虛擬存儲(chǔ)管理請(qǐng)求段頁(yè)式虛擬存儲(chǔ)管理664.5.2 4.5.2 請(qǐng)求分頁(yè)虛擬存儲(chǔ)系統(tǒng)請(qǐng)求分頁(yè)虛擬存儲(chǔ)系統(tǒng)1.1.請(qǐng)求分頁(yè)虛擬存儲(chǔ)系統(tǒng)的硬

51、件支撐請(qǐng)求分頁(yè)虛擬存儲(chǔ)系統(tǒng)的硬件支撐(1)(1)主存管理單元主存管理單元MMUMMU完成邏輯地址到物理地址完成邏輯地址到物理地址的轉(zhuǎn)換功能，它接受虛擬地址作為輸入，的轉(zhuǎn)換功能，它接受虛擬地址作為輸入，物理地址作為輸出，直接送到總線(xiàn)上，對(duì)物理地址作為輸出，直接送到總線(xiàn)上，對(duì)主存單元進(jìn)行尋址。主存單元進(jìn)行尋址。 67MMUMMU主要功能主要功能(1)(1)管理硬件頁(yè)表基址寄存器。管理硬件頁(yè)表基址寄存器。(2)(2)分解邏輯地址。分解邏輯地址。(3)(3)管理快管理快表表TLBTLB。(4)(4)訪(fǎng)問(wèn)頁(yè)表。訪(fǎng)問(wèn)頁(yè)表。(5)(5)發(fā)出缺頁(yè)中斷或越界中斷，并將控制權(quán)交給內(nèi)發(fā)出缺頁(yè)中斷或越界中斷，并將控制

52、權(quán)交給內(nèi)核存儲(chǔ)管理處理。核存儲(chǔ)管理處理。(6)(6)設(shè)置和檢查頁(yè)表中各個(gè)特征位。設(shè)置和檢查頁(yè)表中各個(gè)特征位。682.2.請(qǐng)求分頁(yè)虛擬存儲(chǔ)系統(tǒng)的基本原理請(qǐng)求分頁(yè)虛擬存儲(chǔ)系統(tǒng)的基本原理 分頁(yè)式虛存不把作業(yè)信息分頁(yè)式虛存不把作業(yè)信息( (程序和數(shù)據(jù)程序和數(shù)據(jù)) )全部裝入全部裝入主存，僅裝入立即使用的頁(yè)面，在執(zhí)行過(guò)程中訪(fǎng)主存，僅裝入立即使用的頁(yè)面，在執(zhí)行過(guò)程中訪(fǎng)問(wèn)到不在主存的頁(yè)面時(shí)，產(chǎn)生缺頁(yè)中斷，再?gòu)拇艈?wèn)到不在主存的頁(yè)面時(shí)，產(chǎn)生缺頁(yè)中斷，再?gòu)拇疟P(pán)動(dòng)態(tài)地裝入盤(pán)動(dòng)態(tài)地裝入 。 怎樣才能發(fā)現(xiàn)頁(yè)面不在主存中呢怎樣才能發(fā)現(xiàn)頁(yè)面不在主存中呢? ?怎樣處理這種怎樣處理這種情況呢情況呢? ?0采用的辦法是：擴(kuò)充頁(yè)表

53、的內(nèi)容采用的辦法是：擴(kuò)充頁(yè)表的內(nèi)容, ,增加駐留標(biāo)志位和頁(yè)增加駐留標(biāo)志位和頁(yè)面輔存的地址等信息面輔存的地址等信息。69頁(yè)式虛擬存儲(chǔ)管理頁(yè)表擴(kuò)展頁(yè)式虛擬存儲(chǔ)管理頁(yè)表擴(kuò)展其它標(biāo)志：其它標(biāo)志： 訪(fǎng)問(wèn)權(quán)限位訪(fǎng)問(wèn)權(quán)限位 修改位（修改位（ModifiedModified） 引用位（引用位（RenferencedRenferenced）頁(yè)號(hào)頁(yè)號(hào) 駐留標(biāo)志駐留標(biāo)志 頁(yè)框號(hào)頁(yè)框號(hào) 輔存地址輔存地址 其它標(biāo)志其它標(biāo)志70請(qǐng)求分頁(yè)虛存地址轉(zhuǎn)換過(guò)程請(qǐng)求分頁(yè)虛存地址轉(zhuǎn)換過(guò)程查快表查快表有登記有登記無(wú)登記無(wú)登記查頁(yè)表查頁(yè)表登記入快表登記入快表發(fā)缺頁(yè)中斷發(fā)缺頁(yè)中斷在主存在主存在輔存在輔存形成絕對(duì)地址形成絕對(duì)地址繼續(xù)執(zhí)行指令

54、繼續(xù)執(zhí)行指令重新執(zhí)行重新執(zhí)行被中斷指令被中斷指令恢復(fù)現(xiàn)場(chǎng)恢復(fù)現(xiàn)場(chǎng)調(diào)整頁(yè)表和調(diào)整頁(yè)表和主存分配表主存分配表裝入所需頁(yè)面裝入所需頁(yè)面主存有空閑塊主存有空閑塊保護(hù)現(xiàn)場(chǎng)保護(hù)現(xiàn)場(chǎng)有有選擇調(diào)出頁(yè)面選擇調(diào)出頁(yè)面該頁(yè)是否修改該頁(yè)是否修改未修改未修改已修改已修改把該頁(yè)寫(xiě)回把該頁(yè)寫(xiě)回輔存相應(yīng)位置輔存相應(yīng)位置操作系統(tǒng)操作系統(tǒng)硬件硬件邏輯地址邏輯地址無(wú)無(wú)71請(qǐng)求頁(yè)式虛擬存儲(chǔ)系統(tǒng)優(yōu)缺點(diǎn)請(qǐng)求頁(yè)式虛擬存儲(chǔ)系統(tǒng)優(yōu)缺點(diǎn)l優(yōu)點(diǎn)：作業(yè)的程序和數(shù)據(jù)可按頁(yè)分散存放優(yōu)點(diǎn)：作業(yè)的程序和數(shù)據(jù)可按頁(yè)分散存放在主存中，減少移動(dòng)開(kāi)銷(xiāo)，有效解決了碎在主存中，減少移動(dòng)開(kāi)銷(xiāo)，有效解決了碎片問(wèn)題片問(wèn)題; ;既有利于改進(jìn)主存利用率，又有利既有利于改進(jìn)主存利

55、用率，又有利于多道程序運(yùn)行。于多道程序運(yùn)行。l缺點(diǎn)：要有硬件支持，要進(jìn)行缺頁(yè)中斷處缺點(diǎn)：要有硬件支持，要進(jìn)行缺頁(yè)中斷處理，機(jī)器成本增加，系統(tǒng)開(kāi)銷(xiāo)加大。理，機(jī)器成本增加，系統(tǒng)開(kāi)銷(xiāo)加大。723.3.頁(yè)面裝入策略和頁(yè)面清除策略頁(yè)面裝入策略和頁(yè)面清除策略l頁(yè)面裝入主存頁(yè)面裝入主存, ,有兩種策略：有兩種策略：l請(qǐng)頁(yè)式調(diào)度：僅調(diào)入所需頁(yè)面請(qǐng)頁(yè)式調(diào)度：僅調(diào)入所需頁(yè)面l預(yù)調(diào)式調(diào)度：使用前預(yù)先調(diào)入若干頁(yè)預(yù)調(diào)式調(diào)度：使用前預(yù)先調(diào)入若干頁(yè)l何時(shí)把一個(gè)修改過(guò)的頁(yè)面寫(xiě)回輔存儲(chǔ)器，何時(shí)把一個(gè)修改過(guò)的頁(yè)面寫(xiě)回輔存儲(chǔ)器，有兩種策略：有兩種策略：l請(qǐng)頁(yè)式清除：僅當(dāng)一頁(yè)被選中進(jìn)行替換且被請(qǐng)頁(yè)式清除：僅當(dāng)一頁(yè)被選中進(jìn)行替換且被修

56、改過(guò)，才寫(xiě)回磁盤(pán)。修改過(guò)，才寫(xiě)回磁盤(pán)。l預(yù)清除：成批進(jìn)行，所有預(yù)清除：成批進(jìn)行，所有 被更改過(guò)的頁(yè)面，被更改過(guò)的頁(yè)面，在需要替換前把它們都寫(xiě)回磁盤(pán)。在需要替換前把它們都寫(xiě)回磁盤(pán)。734.4.頁(yè)面分配策略頁(yè)面分配策略 系統(tǒng)為進(jìn)程分配主存系統(tǒng)為進(jìn)程分配主存, ,需考慮因素需考慮因素: :分給進(jìn)程的空間越小分給進(jìn)程的空間越小, ,同一時(shí)間處于主存的進(jìn)程同一時(shí)間處于主存的進(jìn)程就越多，至少有一個(gè)進(jìn)程處于就緒態(tài)的可能性就就越多，至少有一個(gè)進(jìn)程處于就緒態(tài)的可能性就越大越大如果進(jìn)程只有小部分在主存里如果進(jìn)程只有小部分在主存里, ,即使局部性很好即使局部性很好, ,缺頁(yè)中斷率還會(huì)相當(dāng)大缺頁(yè)中斷率還會(huì)相當(dāng)大因程序

57、的局部性原理，分給進(jìn)程的主存超過(guò)一定因程序的局部性原理，分給進(jìn)程的主存超過(guò)一定限度后，再增加主存空間限度后，再增加主存空間, ,不會(huì)明顯降低進(jìn)程的不會(huì)明顯降低進(jìn)程的缺頁(yè)中斷率缺頁(yè)中斷率。74頁(yè)面分配策略：固定分配頁(yè)面分配策略：固定分配 進(jìn)程保持頁(yè)框數(shù)固定不變進(jìn)程保持頁(yè)框數(shù)固定不變, ,稱(chēng)固定分配稱(chēng)固定分配; ; 進(jìn)程創(chuàng)建時(shí)進(jìn)程創(chuàng)建時(shí), ,根據(jù)進(jìn)程類(lèi)型和程序員的要求根據(jù)進(jìn)程類(lèi)型和程序員的要求決定頁(yè)框數(shù)決定頁(yè)框數(shù), ,只要有一個(gè)缺頁(yè)中斷產(chǎn)生只要有一個(gè)缺頁(yè)中斷產(chǎn)生, ,進(jìn)進(jìn)程就會(huì)有一頁(yè)被替換。程就會(huì)有一頁(yè)被替換。75頁(yè)面分配策略：可變分配頁(yè)面分配策略：可變分配 進(jìn)程分得的頁(yè)框數(shù)可變進(jìn)程分得的頁(yè)框數(shù)可

58、變, , 稱(chēng)可變分配稱(chēng)可變分配; ; 進(jìn)程執(zhí)行的某階段缺頁(yè)率較高進(jìn)程執(zhí)行的某階段缺頁(yè)率較高, ,說(shuō)明目前說(shuō)明目前局部性較差，系統(tǒng)可多分些頁(yè)框以降低缺局部性較差，系統(tǒng)可多分些頁(yè)框以降低缺頁(yè)率，反之說(shuō)明進(jìn)程目前的局部性較好頁(yè)率，反之說(shuō)明進(jìn)程目前的局部性較好, ,可減少分給進(jìn)程的頁(yè)框數(shù)可減少分給進(jìn)程的頁(yè)框數(shù)76頁(yè)面替換策略：局部替換和全局替換頁(yè)面替換策略：局部替換和全局替換 如果頁(yè)面替換算法的作用范圍是整個(gè)系統(tǒng)如果頁(yè)面替換算法的作用范圍是整個(gè)系統(tǒng)，稱(chēng)全局頁(yè)面替換算法，稱(chēng)全局頁(yè)面替換算法, ,它可以在運(yùn)行進(jìn)程它可以在運(yùn)行進(jìn)程間動(dòng)態(tài)地分配頁(yè)框。間動(dòng)態(tài)地分配頁(yè)框。 如果頁(yè)面替換算法的作用范圍局限于本進(jìn)如果

59、頁(yè)面替換算法的作用范圍局限于本進(jìn)程，稱(chēng)為局部頁(yè)面替換算法程，稱(chēng)為局部頁(yè)面替換算法, ,它實(shí)際上需要它實(shí)際上需要為每個(gè)進(jìn)程分配固定的頁(yè)框。為每個(gè)進(jìn)程分配固定的頁(yè)框。 77固定分配和局部替換策略配合使用固定分配和局部替換策略配合使用(1)(1)l 進(jìn)程分得的頁(yè)框數(shù)不變，發(fā)生缺頁(yè)中斷，進(jìn)程分得的頁(yè)框數(shù)不變，發(fā)生缺頁(yè)中斷，只能從進(jìn)程的頁(yè)面中選頁(yè)替換，保證進(jìn)程只能從進(jìn)程的頁(yè)面中選頁(yè)替換，保證進(jìn)程的頁(yè)框總數(shù)不變。的頁(yè)框總數(shù)不變。l策略難點(diǎn)：應(yīng)給每個(gè)進(jìn)程分配多少頁(yè)框策略難點(diǎn)：應(yīng)給每個(gè)進(jìn)程分配多少頁(yè)框? ?給給少了少了, ,缺頁(yè)中斷率高缺頁(yè)中斷率高; ;給多了給多了, ,使主存中能同使主存中能同時(shí)執(zhí)行的進(jìn)程數(shù)

60、減少，進(jìn)而造成處理器和時(shí)執(zhí)行的進(jìn)程數(shù)減少，進(jìn)而造成處理器和其它設(shè)備空閑。其它設(shè)備空閑。78固定分配和局部替換策略配合使用固定分配和局部替換策略配合使用(2)(2)采用固定分配算法，系統(tǒng)把頁(yè)框分配給進(jìn)采用固定分配算法，系統(tǒng)把頁(yè)框分配給進(jìn)程，采用：程，采用：平均分配平均分配按比例分配按比例分配優(yōu)先權(quán)分配優(yōu)先權(quán)分配79可變分配和全局替換策略配合使用可變分配和全局替換策略配合使用l先每個(gè)進(jìn)程分配一定數(shù)目頁(yè)先每個(gè)進(jìn)程分配一定數(shù)目頁(yè)框框,os,os保留若干空閑保留若干空閑頁(yè)框頁(yè)框, ,進(jìn)程發(fā)生缺頁(yè)中斷時(shí)，從系統(tǒng)空閑頁(yè)框中進(jìn)程發(fā)生缺頁(yè)中斷時(shí)，從系統(tǒng)空閑頁(yè)框中選一個(gè)給進(jìn)程選一個(gè)給進(jìn)程, ,這樣產(chǎn)生缺頁(yè)中斷進(jìn)程

61、的主存空這樣產(chǎn)生缺頁(yè)中斷進(jìn)程的主存空間會(huì)逐漸增大間會(huì)逐漸增大, ,有助于減少系統(tǒng)的缺頁(yè)中斷次數(shù)有助于減少系統(tǒng)的缺頁(yè)中斷次數(shù)。l系統(tǒng)擁有的空閑頁(yè)框耗盡時(shí)系統(tǒng)擁有的空閑頁(yè)框耗盡時(shí) ，會(huì)從主存中選擇，會(huì)從主存中選擇一頁(yè)淘汰，該頁(yè)可以是主存中任一進(jìn)程的頁(yè)面，一頁(yè)淘汰，該頁(yè)可以是主存中任一進(jìn)程的頁(yè)面，這樣又會(huì)使那個(gè)進(jìn)程的頁(yè)框數(shù)減少，缺頁(yè)中斷率這樣又會(huì)使那個(gè)進(jìn)程的頁(yè)框數(shù)減少，缺頁(yè)中斷率上升。上升。80可變分配和局部替換配合使用可變分配和局部替換配合使用其實(shí)現(xiàn)要點(diǎn)如下其實(shí)現(xiàn)要點(diǎn)如下: :(1)(1)新進(jìn)程裝入主存時(shí)，根據(jù)應(yīng)用類(lèi)型、程序要求新進(jìn)程裝入主存時(shí)，根據(jù)應(yīng)用類(lèi)型、程序要求，分配給一定數(shù)目頁(yè)框，分配給一

62、定數(shù)目頁(yè)框, ,可用請(qǐng)頁(yè)式或預(yù)調(diào)式完可用請(qǐng)頁(yè)式或預(yù)調(diào)式完成這個(gè)分配。成這個(gè)分配。(2)(2)產(chǎn)生缺頁(yè)中斷時(shí)產(chǎn)生缺頁(yè)中斷時(shí), ,從該進(jìn)程駐留集中選一個(gè)頁(yè)面從該進(jìn)程駐留集中選一個(gè)頁(yè)面替換。替換。(3)(3)不時(shí)重新評(píng)價(jià)進(jìn)程的分配，增加或減少分配給不時(shí)重新評(píng)價(jià)進(jìn)程的分配，增加或減少分配給進(jìn)程的頁(yè)框以改善系統(tǒng)性能。進(jìn)程的頁(yè)框以改善系統(tǒng)性能。815.5.缺頁(yè)中斷率缺頁(yè)中斷率l頁(yè)面替換頁(yè)面替換l當(dāng)主存空間已滿(mǎn)又必須裝入新頁(yè)時(shí)，選擇主存當(dāng)主存空間已滿(mǎn)又必須裝入新頁(yè)時(shí)，選擇主存中某頁(yè)淘汰。中某頁(yè)淘汰。l頁(yè)面淘汰算法頁(yè)面淘汰算法l選擇哪頁(yè)被淘汰的算法。選擇哪頁(yè)被淘汰的算法。l“抖動(dòng)抖動(dòng)”(Thrashing)(

63、Thrashing)現(xiàn)象現(xiàn)象l剛被淘汰的頁(yè)面立即又要調(diào)用，調(diào)入不久又被剛被淘汰的頁(yè)面立即又要調(diào)用，調(diào)入不久又被淘汰，淘汰不久再被調(diào)入淘汰，淘汰不久再被調(diào)入如此反復(fù)，整個(gè)系如此反復(fù)，整個(gè)系統(tǒng)頻繁調(diào)頁(yè)，使得幾乎無(wú)時(shí)間進(jìn)行計(jì)算任務(wù)。統(tǒng)頻繁調(diào)頁(yè)，使得幾乎無(wú)時(shí)間進(jìn)行計(jì)算任務(wù)。82影響缺頁(yè)中斷率的因素影響缺頁(yè)中斷率的因素(1) 假定作業(yè)假定作業(yè)p p共計(jì)共計(jì)n n頁(yè)，系統(tǒng)分配給它的主存頁(yè)，系統(tǒng)分配給它的主存塊只有塊只有m m塊（塊（mnmn）。如果作業(yè)）。如果作業(yè)p p在運(yùn)在運(yùn)行中成功的訪(fǎng)問(wèn)次數(shù)為行中成功的訪(fǎng)問(wèn)次數(shù)為S S， 不成功的訪(fǎng)問(wèn)不成功的訪(fǎng)問(wèn)次數(shù)為次數(shù)為F F，則總的訪(fǎng)問(wèn)次數(shù)為：，則總的訪(fǎng)問(wèn)次數(shù)為

64、：A = S + FA = S + F 又定義：又定義：f = F / Af = F / A 稱(chēng)稱(chēng)f f為缺頁(yè)中斷率。為缺頁(yè)中斷率。83影響缺頁(yè)中斷率的因素影響缺頁(yè)中斷率的因素(2) 影響缺頁(yè)中斷率影響缺頁(yè)中斷率f f的因素有：的因素有：(1)(1)主存頁(yè)框數(shù)。主存頁(yè)框數(shù)。(2)(2)頁(yè)面大小。頁(yè)面大小。(3)(3)頁(yè)面替換算法。頁(yè)面替換算法。(4)(4)程序特性。程序特性。846.6.全局頁(yè)面替換策略全局頁(yè)面替換策略1) 1) 最佳頁(yè)面替換算法最佳頁(yè)面替換算法OPT OPT 2) 2) 先進(jìn)先出頁(yè)面替換算法先進(jìn)先出頁(yè)面替換算法FIFO FIFO 3) 3) 最近最少用頁(yè)面替換算法最近最少用頁(yè)

65、面替換算法LRU LRU 4) 4) 第二次機(jī)會(huì)頁(yè)面替換算法第二次機(jī)會(huì)頁(yè)面替換算法SCR SCR 5) 5) 時(shí)鐘頁(yè)面替換算法時(shí)鐘頁(yè)面替換算法ClockClock注：所有算法例子中采用請(qǐng)頁(yè)時(shí)調(diào)度，即最注：所有算法例子中采用請(qǐng)頁(yè)時(shí)調(diào)度，即最初假設(shè)主存中沒(méi)有頁(yè)面。初假設(shè)主存中沒(méi)有頁(yè)面。 851)1)最佳替換算法最佳替換算法 調(diào)入一頁(yè)而必須淘汰一個(gè)舊頁(yè)時(shí)，所淘汰調(diào)入一頁(yè)而必須淘汰一個(gè)舊頁(yè)時(shí)，所淘汰的頁(yè)應(yīng)該是以后不再訪(fǎng)問(wèn)的頁(yè)或距現(xiàn)在最的頁(yè)應(yīng)該是以后不再訪(fǎng)問(wèn)的頁(yè)或距現(xiàn)在最長(zhǎng)時(shí)間后再訪(fǎng)問(wèn)的頁(yè)。長(zhǎng)時(shí)間后再訪(fǎng)問(wèn)的頁(yè)。 OPTOPT算法（算法（OptimalOptimal） ，可用來(lái)作為衡量各，可用來(lái)作為衡量各

66、種具體算法的標(biāo)準(zhǔn)種具體算法的標(biāo)準(zhǔn)。86OPTOPT例例 （可用幀數(shù)量（可用幀數(shù)量3 3）引用串如下：）引用串如下：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 11 7 0 1107107R107102102102R102302302R302342342R342302R302102R102F107F07F7置換幀3幀2幀1引用串10710212303240302107缺頁(yè)率缺頁(yè)率 p=9/20=45%p=9/20=45%872)2)先進(jìn)先出頁(yè)面替換算法先進(jìn)先出頁(yè)面替換算法 基于程序總是按線(xiàn)性順序來(lái)訪(fǎng)問(wèn)物理空間基于程序總是按線(xiàn)性順序來(lái)訪(fǎng)問(wèn)物理空間這一假設(shè)。這一假設(shè)。 算法總是淘汰最先調(diào)入主存的那一頁(yè)，或算法總是淘汰最先調(diào)入主存的那一頁(yè)，或者說(shuō)在主存中駐留時(shí)間最長(zhǎng)的那一頁(yè)（常者說(shuō)在主存中駐留時(shí)間最長(zhǎng)的那一頁(yè)（常駐的除外）。駐的除外）。 實(shí)現(xiàn)技術(shù)實(shí)現(xiàn)技術(shù) (1)(1)設(shè)置具有設(shè)置具有m m個(gè)元素的頁(yè)號(hào)表，控制換頁(yè)個(gè)元素的頁(yè)號(hào)表，控制換頁(yè) (2)(2)引入指針鏈成隊(duì)列引入指針鏈成隊(duì)列88FIFOFI