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

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

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

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

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

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

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

6、址寄存器存放當(dāng)前正執(zhí)行者的程序地址空間所占分區(qū)的始址，限長寄存器存放該地址空間地址空間所占分區(qū)的始址，限長寄存器存放該地址空間的長度的長度地址轉(zhuǎn)換與存儲保護(hù)地址轉(zhuǎn)換與存儲保護(hù)(3)(3)8下限寄存器下限寄存器20002000上限寄存器上限寄存器35003500基址寄存器基址寄存器20002000限長寄存器限長寄存器15001500進(jìn)程進(jìn)程idid下限下限+ +上限寄存器上限寄存器基址基址+ +限長寄存器限長寄存器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ù)存儲空間管理連續(xù)存儲空間管理4.2.1 4.2.1 固定分區(qū)存儲管理固定分區(qū)存儲管理 4.2.2 4.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理 4.2.3 4.2.3 伙伴系統(tǒng)伙伴系統(tǒng)4.2.4 4.2.4 主存不足的存儲管理技術(shù)主存不足的存儲管理技術(shù)104.2.1 4.2.1 固定分區(qū)存儲管理固定分區(qū)存儲管理 固定分區(qū)存儲管理的基本思想固定分區(qū)存儲管理的基本思想0主存空間被分成數(shù)目固定不變的分區(qū)，各分區(qū)

8、主存空間被分成數(shù)目固定不變的分區(qū)，各分區(qū)的大小不等，每個(gè)分區(qū)只裝入一個(gè)作業(yè)。的大小不等，每個(gè)分區(qū)只裝入一個(gè)作業(yè)。 固定分區(qū)存儲管理的數(shù)據(jù)結(jié)構(gòu)固定分區(qū)存儲管理的數(shù)據(jù)結(jié)構(gòu)0主存分配表：指出各分區(qū)的起始地址和長度；主存分配表：指出各分區(qū)的起始地址和長度；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速度匹速度匹配的問題配的問題0解決了單道程序運(yùn)行時(shí)主存空間利用率低的問題解決了單道程序運(yùn)行時(shí)主存空間利用率低的問題0實(shí)現(xiàn)簡單實(shí)現(xiàn)簡單 缺點(diǎn)缺點(diǎn)0大作業(yè)可能無法裝入大作業(yè)可能無法裝入0主存空間利用率不高，會出現(xiàn)內(nèi)碎片主存空間利用率不高，會出現(xiàn)內(nèi)碎片0擴(kuò)充困難擴(kuò)充困難0限制多道運(yùn)行程序的個(gè)數(shù)限制多道運(yùn)行程序的個(gè)數(shù)124.2.2 4.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理 可變分區(qū)存儲管理是按作業(yè)的實(shí)際大小來劃可變分區(qū)存儲管理是按作業(yè)的實(shí)際大小來劃分分區(qū)，且分區(qū)個(gè)數(shù)也是隨機(jī)的分分區(qū)，且分區(qū)個(gè)數(shù)也是隨機(jī)的, ,實(shí)現(xiàn)多個(gè)實(shí)現(xiàn)多個(gè)作業(yè)對主存的共享，進(jìn)一步提高主存資源利

10、作業(yè)對主存的共享，進(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ū)存儲管理數(shù)據(jù)結(jié)構(gòu)可變分區(qū)存儲管理數(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ū)開頭單元存放本空閑區(qū)長度及下個(gè)空閑區(qū)開頭單元存放本空閑區(qū)長度及下個(gè)空閑區(qū)起始地址空閑區(qū)起始地址, ,把所有空閑區(qū)都鏈接起來把所有空閑區(qū)都鏈接起來, ,設(shè)置第一塊空閑區(qū)地址指針設(shè)置第一塊空閑區(qū)地址指針, ,讓它指向第讓它指向第一塊空閑區(qū)地址。一塊空閑區(qū)地址。 申請空閑區(qū)：沿鏈查找并取一個(gè)長度能滿申請空閑區(qū)：沿鏈查找并取一個(gè)長

12、度能滿足要求的空閑區(qū)；足要求的空閑區(qū)； 歸還空閑區(qū)：把此空閑區(qū)鏈入空閑區(qū)鏈表歸還空閑區(qū)：把此空閑區(qū)鏈入空閑區(qū)鏈表的相應(yīng)位置。的相應(yīng)位置。17可變分區(qū)管理分配算法可變分區(qū)管理分配算法1 1）最先適應(yīng)分配算法）最先適應(yīng)分配算法空閑區(qū)通常按空閑區(qū)通常按地址地址從小到大排列，分配第從小到大排列，分配第一個(gè)滿足長度要求的空閑區(qū)；一個(gè)滿足長度要求的空閑區(qū)；優(yōu)點(diǎn)：分配從低地址開始，使高地址部分優(yōu)點(diǎn)：分配從低地址開始，使高地址部分比較少用，以保持一個(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é)束處順序查找。可以解決可以解決1 1）的缺點(diǎn)。）的缺點(diǎn)。3) 3) 最優(yōu)適應(yīng)分配算法最優(yōu)適應(yīng)分配算法分配能滿足要求的最小區(qū)。分配能滿足要求的最小區(qū)?？梢詫⒖臻e區(qū)按照可以將空閑區(qū)按照大小大小從小到大排列，查找第一從小到大排列，查找第一個(gè)滿足要求的。個(gè)滿足要求的。優(yōu)點(diǎn)：主存利用率好。優(yōu)點(diǎn)：主存利用率好。缺點(diǎn)：分割剩下的空閑區(qū)比較小，難以利用；查缺點(diǎn)：分割剩下的空閑區(qū)比較小，難以利用；查找時(shí)間比較長。找時(shí)間比較長。194 4）最壞適應(yīng)分配算法）最壞適應(yīng)

14、分配算法分配能滿足要求的最大區(qū)；分配能滿足要求的最大區(qū)；可以將空閑區(qū)按照可以將空閑區(qū)按照大小大小從大到小排列，查找第一從大到小排列，查找第一個(gè)滿足要求的。個(gè)滿足要求的。效率大致等同于最先適應(yīng)法。效率大致等同于最先適應(yīng)法。5) 5) 快速適應(yīng)分配算法快速適應(yīng)分配算法為經(jīng)常用到的長度的空閑區(qū)設(shè)置單獨(dú)的鏈表。為經(jī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ū)存儲管下表為某系統(tǒng)中的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲管理策略?，F(xiàn)有以下作業(yè)序列：理

15、策略。現(xiàn)有以下作業(yè)序列：96KB96KB，20KB20KB，200KB200KB，分別使，分別使用首次適應(yīng)、最佳適用和最壞適用算法來處理這個(gè)作業(yè)序列用首次適應(yīng)、最佳適用和最壞適用算法來處理這個(gè)作業(yè)序列，試問哪一種算法可以滿足該作業(yè)序列的請求，為什么？，試問哪一種算法可以滿足該作業(yè)序列的請求，為什么？分區(qū)號分區(qū)號大小大小起始地址起始地址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è)空閑塊稱為伙伴。的空閑塊，這兩個(gè)空閑塊稱為伙伴。 伙伴通過對大塊

17、的物理主存劃分而獲得伙伴通過對大塊的物理主存劃分而獲得0假如從第假如從第0 0個(gè)頁面開始到第個(gè)頁面開始到第3 3個(gè)頁面結(jié)束的主存?zhèn)€頁面結(jié)束的主存0每次都對半劃分，那么第一次劃分獲得大小為每次都對半劃分，那么第一次劃分獲得大小為2 2頁的伙頁的伙伴，如伴，如0 0、1 1和和2 2、3 30進(jìn)一步劃分，可以獲得大小為進(jìn)一步劃分，可以獲得大小為1 1頁的伙伴，例如頁的伙伴，例如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 主存不足的存儲管理技術(shù)主存不足的存儲管理技術(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.移動技術(shù)移動技術(shù)24有關(guān)移動問題討論有關(guān)移動問題討論 移動條件移動條件0在可變分區(qū)算法中，隨著進(jìn)程不斷的裝入和撤銷，導(dǎo)致在可變分區(qū)算法中，隨著進(jìn)程不斷的裝入和撤銷，導(dǎo)致主存中常常出現(xiàn)分散的小空閑區(qū)，稱為主存中常常出現(xiàn)分散的小空閑區(qū)，稱為碎片碎片。0當(dāng)在未分配區(qū)中找不到足夠大的空閑區(qū)來裝入新進(jìn)程時(shí)當(dāng)在未分配區(qū)中找不到足夠大的空閑區(qū)來裝入新進(jìn)程時(shí)，可采用移動技術(shù)，將分散的空閑區(qū)匯集成片。，可采用移動技術(shù)，將分散的空閑區(qū)匯集成片。 移動時(shí)機(jī)移動時(shí)機(jī)0進(jìn)

20、程撤銷之后釋放分區(qū)時(shí)，如果它不與空閑區(qū)鄰接，立進(jìn)程撤銷之后釋放分區(qū)時(shí)，如果它不與空閑區(qū)鄰接，立即實(shí)施移動。即實(shí)施移動。0進(jìn)程裝入分區(qū)時(shí)，如果它不與空閑區(qū)鄰接，立即實(shí)施引進(jìn)程裝入分區(qū)時(shí)，如果它不與空閑區(qū)鄰接，立即實(shí)施引動。動。25 移動算法（假設(shè)進(jìn)程移動算法（假設(shè)進(jìn)程A A請求分配請求分配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：移動主存的相關(guān)分區(qū)信息；

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

22、0選擇哪個(gè)進(jìn)程換出；選擇哪個(gè)進(jìn)程換出；0決定把進(jìn)程的哪些信息移出去；決定把進(jìn)程的哪些信息移出去；0需要確定對換時(shí)機(jī)。需要確定對換時(shí)機(jī)。 UNIXUNIX對換器對換器 WindowsWindows對換器對換器27在任何時(shí)候只在內(nèi)存中保留所需的指令和數(shù)據(jù)在任何時(shí)候只在內(nèi)存中保留所需的指令和數(shù)據(jù)由用戶實(shí)現(xiàn)，由用戶實(shí)現(xiàn)，讓不會同時(shí)調(diào)用的子模塊共同使用讓不會同時(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)存之和可以滿足：存在分區(qū)外，所有內(nèi)存之和可以滿足請求，但不連續(xù)請求，但不連續(xù) 內(nèi)部碎片內(nèi)部碎片：存在分區(qū)內(nèi)，但已不能滿足任何請求：存在分區(qū)內(nèi)，但已不能滿足任何請求 解決外部碎片問題的方法解決外部碎片問題的方法0緊縮（緊縮（compactioncompaction）：移動內(nèi)存內(nèi)容，以便所有空閑）：移動內(nèi)存內(nèi)容，以便所有空閑空間合并成一整塊空間合并成一整塊0允許物理地址空間為非連續(xù)允許物理地址空間為非連續(xù)x 分頁分頁x 分段分段294.3 4.3 分頁式存儲管理分頁式存儲管理4.3.1 4.3.1 分頁式存儲管理的基本原理分頁式存儲管理

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

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

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

27、所示，頁表如圖所示，將邏輯地址，將邏輯地址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)換 說明：頁大小為說明：頁大小為1024B1024B，頁表如圖所示，頁表如圖所示，將邏輯地址，將邏輯地址10111011、21482148、30003000

28、、40004000、50125012轉(zhuǎn)換為相應(yīng)物理地址轉(zhuǎn)換為相應(yīng)物理地址23160 1 2 3頁表頁表 答案：答案：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 頁號頁號4 4不存在不存在354.3.2 4.3.2 快表快表 相聯(lián)存儲器（翻譯后備緩沖（相聯(lián)存儲器（翻譯后備緩沖（translation translation look-aside bufferlook-aside buffer，TLBTLB）：關(guān)聯(lián)的快速內(nèi)存）：關(guān)聯(lián)的快速內(nèi)存 TLBTLB與頁表一起工作與頁表一起工作0快表項(xiàng)包含頁號及對應(yīng)的頁框號，當(dāng)把頁號交給快表快表項(xiàng)包含頁號及對應(yīng)的頁框號，當(dāng)把頁號交給快表后，它通過并行匹配同時(shí)對所有快表項(xiàng)進(jìn)

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

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比兩次訪問主存的時(shí)間比兩次訪問主存的時(shí)間1001002 2200200下降了三成多下降了三成多。374.3.3 4.3.3 分頁式存儲空間的分配和去配分頁式存儲空間的分配和去配(1)(1) 位示圖法位示圖法0每位與一幀相對應(yīng)，用每位與一幀相對應(yīng)，用0/10/1表示對應(yīng)塊為空閑表示對應(yīng)塊為空閑/ /已占用，用另一專門字記錄當(dāng)前空閑塊數(shù)。已占用，用另一

32、專門字記錄當(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長度長度x指向下一表項(xiàng)的指針指向下一表項(xiàng)的指針38主存分配的位示圖和鏈表方法主存分配的位示圖和鏈表方法394.3.4 4.3.4 分頁存儲空間的頁面共享和保護(hù)分頁存儲空間的頁面共享和保護(hù) 數(shù)據(jù)共享數(shù)據(jù)共享0允許不同進(jìn)程對共享的數(shù)據(jù)頁用不同的頁號，允許不同進(jìn)程對共享的數(shù)據(jù)頁用不同的頁號，只要讓各自頁表中的有關(guān)表項(xiàng)指向共享的數(shù)據(jù)只要讓各自頁表中的有關(guān)表項(xiàng)指向共享的數(shù)據(jù)頁框；頁框； 程序共享程序共享0指令包含指向其它指令或數(shù)據(jù)的地址。指令包含

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

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

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

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

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

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

39、圖）模塊化程序設(shè)計(jì)的分段結(jié)構(gòu)（下頁圖） 分頁存儲管理分頁存儲管理-一維地址結(jié)構(gòu)一維地址結(jié)構(gòu) 分段存儲管理分段存儲管理-二維地址結(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 分段式存儲管理的基本原理分段式存儲管理的基本原理(

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

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

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

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

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

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

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

47、.4 4.5.4 請求段頁式虛擬存儲管理請求段頁式虛擬存儲管理604.5.1 4.5.1 虛擬存儲管理的概念虛擬存儲管理的概念 虛擬內(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處理異常錯誤條件的代碼（幾乎不執(zhí)行）處理異常錯誤條件的代碼（幾乎不執(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用戶程序會運(yùn)行的更快用戶程序會運(yùn)行的更快61虛擬存儲器虛擬存儲器 虛擬存儲器的定義：虛擬存儲器的定義：0在具有層次結(jié)構(gòu)存儲器的計(jì)算機(jī)系統(tǒng)中在具有層次結(jié)構(gòu)存儲器的計(jì)算機(jī)系統(tǒng)中，采用自動實(shí)現(xiàn)部分裝入和部分對換功，采用自動實(shí)現(xiàn)部分裝入和部分對換功能，為用戶提供一個(gè)比物理主存容量大能，為用戶提供一個(gè)比物理主存容量大得多的，可尋址的一種得多的，可尋址的

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

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

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

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

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

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

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

56、改過，才寫回磁盤。修改過，才寫回磁盤。l預(yù)清除：成批進(jìn)行，所有預(yù)清除：成批進(jìn)行，所有 被更改過的頁面，被更改過的頁面，在需要替換前把它們都寫回磁盤。在需要替換前把它們都寫回磁盤。734.4.頁面分配策略頁面分配策略 系統(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)程只有小部分在主存里, ,即使局部性很好即使局部性很好, ,缺頁中斷率還會相當(dāng)大缺頁中斷率還會相當(dāng)大因程序

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

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

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

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

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

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

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

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

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

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缺頁率缺頁率 p=9/20=45%p=9/20=45%872)2)先進(jìn)先出頁面替換算法先進(jìn)先出頁面替換算法 基于程序總是按線性順序來訪問物理空間基于程序總是按線性順序來訪問物理空間這一假設(shè)。這一假設(shè)。 算法總是淘汰最先調(diào)入主存的那一頁，或算法總是淘汰最先調(diào)入主存的那一頁，或者說在主存中駐留時(shí)間最長的那一頁（常者說在主存中駐留時(shí)間最長的那一頁（常駐的除外）。駐的除外）。 實(shí)現(xiàn)技術(shù)實(shí)現(xiàn)技術(shù) (1)(1)設(shè)置具有設(shè)置具有m m個(gè)元素的頁號表，控制換頁個(gè)元素的頁號表，控制換頁 (2)(2)引入指針鏈成隊(duì)列引入指針鏈成隊(duì)列88FIFOFI