操作系統(tǒng)第4章存儲管理課件

第4章存儲管理重要內(nèi)容存儲器連續(xù)存儲空間管理分頁存儲管理分段存儲管理虛擬存儲管理Intelx86分段和分頁存儲結(jié)構(gòu)Linux虛擬存儲管理Windows2003虛擬存儲管理1第4章存儲管理重要內(nèi)容1存儲管理的功能分配和去配請求和釋放主存空間抽象和映射抽象成一維數(shù)組或二維地址空間地址轉(zhuǎn)換隔離和共享隔離實現(xiàn)存儲保護功能超越隔離機制，提高主存利用率存儲擴充虛擬，允許進程虛擬地址空間大于主存空間2存儲管理的功能分配和去配24.1存儲器4.1.1存儲器的層次4.1.2地址轉(zhuǎn)換與存儲保護34.1存儲器4.1.1存儲器的層次34.1.1存儲器的層次寄存器高速緩存主存儲器磁盤緩存固定磁盤可移動存儲介質(zhì)44.1.1存儲器的層次寄存器高速緩存主存儲器磁盤緩存固定磁4.1.2地址轉(zhuǎn)換與存儲保護(1)鏈接動態(tài)重定位靜態(tài)重定位…源程序模塊1源程序模塊2源程序模塊n…目標代碼1目標代碼2目標代碼n可重定位目標代碼(裝載代碼)(輔存)編譯裝入執(zhí)行程序名字空間邏輯地址空間物理地址空間可執(zhí)行二進代碼(主存)庫代碼可執(zhí)行二進代碼(主存)

程序的編譯、鏈接、裝入和執(zhí)行54.1.2地址轉(zhuǎn)換與存儲保護(1)鏈接動態(tài)重定位靜態(tài)重定位地址轉(zhuǎn)換與存儲保護(2)邏輯地址（虛地址）：CPU所生成的地址物理地址（實地址）：內(nèi)存單元所看到的地址邏輯地址空間：由程序所生成的所有邏輯地址的集合物理地址空間：由邏輯地址所對應(yīng)的所有物理地址的集合地址轉(zhuǎn)換或重定位：把邏輯地址轉(zhuǎn)換為物理地址6地址轉(zhuǎn)換與存儲保護(2)邏輯地址（虛地址）：CPU所生成的地靜態(tài)重定位地址轉(zhuǎn)換工作在進程執(zhí)行前一次完成；無須硬件支持，易于實現(xiàn)，但不允許程序在執(zhí)行過程中移動位置。早期單用戶單任務(wù)系統(tǒng)動態(tài)重定位地址轉(zhuǎn)換推遲到最后的可能時刻，即進程執(zhí)行時才完成；允許程序在主存中移動、便于主存共享、主存利用率高。地址轉(zhuǎn)換與存儲保護(3)7靜態(tài)重定位地址轉(zhuǎn)換與存儲保護(3)7例：使用重定位寄存器的動態(tài)重定位8例：使用重定位寄存器的動態(tài)重定位8存儲保護問題：保護操作系統(tǒng)不受用戶進程所影響，保護用戶進程不受其他用戶進程所影響方法存儲鍵保護系統(tǒng)將主存劃分成大小相等的若干存儲塊，并給每個存儲塊都分配一個單獨的保護鍵（鎖）；在程序狀態(tài)字PSW中設(shè)置有保護鍵字段，對不同的作業(yè)賦予不同的代碼（鑰匙）；鑰匙和鎖相配才允許訪問界限寄存器（下頁圖）上、下界防護：硬件為分給用戶作業(yè)的連續(xù)的主存空間設(shè)置一對上、下界，分別指向該存儲空間的上、下界基址、限長防護：基址寄存器存放當前正執(zhí)行者的程序地址空間所占分區(qū)的始址，限長寄存器存放該地址空間的長度地址轉(zhuǎn)換與存儲保護(4)9存儲保護地址轉(zhuǎn)換與存儲保護(4)9下限寄存器2000上限寄存器3500基址寄存器2000限長寄存器1500進程id下限+上限寄存器基址+限長寄存器11000+19991000+99922000+35002000+150034000+50004000+1000內(nèi)存映像……進程1進程2進程3……100019992000350040005000正運行的進程是進程210下限寄存器2000上限寄存器3500基址寄存器2000限長寄4.2連續(xù)存儲空間管理4.2.1固定分區(qū)存儲管理4.2.2可變分區(qū)存儲管理4.2.3伙伴系統(tǒng)4.2.4主存不足的存儲管理技術(shù)114.2連續(xù)存儲空間管理4.2.1固定分區(qū)存儲管理114.2.1固定分區(qū)存儲管理固定分區(qū)存儲管理的基本思想主存空間被分成數(shù)目固定不變的分區(qū)，各分區(qū)的大小不等，每個分區(qū)只裝入一個作業(yè)。固定分區(qū)存儲管理的數(shù)據(jù)結(jié)構(gòu)主存分配表：指出各分區(qū)的起始地址和長度；占用標志：指示此分區(qū)是否被使用。作業(yè)進入固定分區(qū)排隊策略每個分區(qū)有單獨的作業(yè)等待隊列；所有等待處理的作業(yè)排成一個等待隊列。124.2.1固定分區(qū)存儲管理固定分區(qū)存儲管理的基本思想12固定分區(qū)存儲管理的地址轉(zhuǎn)換和存儲保護

B下限寄存器邏輯地址CPU絕對地址操作系統(tǒng)區(qū)用戶分區(qū)1用戶分區(qū)2用戶分區(qū)3B+L2上限寄存器<B+L2越界中斷用戶分區(qū)4用戶分區(qū)5用戶分區(qū)613固定分區(qū)存儲管理的地址轉(zhuǎn)換和存儲保護B下限寄存器邏輯地址固定分區(qū)的優(yōu)缺點優(yōu)點能夠解決單道程序運行在并發(fā)環(huán)境下不能與CPU速度匹配的問題解決了單道程序運行時主存空間利用率低的問題實現(xiàn)簡單缺點大作業(yè)可能無法裝入主存空間利用率不高，會出現(xiàn)內(nèi)碎片擴充困難限制多道運行程序的個數(shù)14固定分區(qū)的優(yōu)缺點優(yōu)點144.2.2可變分區(qū)存儲管理可變分區(qū)存儲管理是按作業(yè)的實際大小來劃分分區(qū)，且分區(qū)個數(shù)也是隨機的,實現(xiàn)多個作業(yè)對主存的共享，進一步提高主存資源利用率。

154.2.2可變分區(qū)存儲管理可變分區(qū)存儲管理是按作業(yè)的實可變分區(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è)316可變分區(qū)方式主存分配示例操作系統(tǒng)作業(yè)1作業(yè)2空閑區(qū)4KB10可變分區(qū)存儲管理數(shù)據(jù)結(jié)構(gòu)可變分區(qū)主存分配表可由兩張表格組成，已分配區(qū)表未分配區(qū)表

17可變分區(qū)存儲管理數(shù)據(jù)結(jié)構(gòu)可變分區(qū)主存分配表可由兩張表格組可變分區(qū)回收算法AXAXBXBAXABB18可變分區(qū)回收算法AXAXBXBAXABB18鏈表空閑區(qū)管理方法空閑區(qū)開頭單元存放本空閑區(qū)長度及下個空閑區(qū)起始地址,把所有空閑區(qū)都鏈接起來,設(shè)置第一塊空閑區(qū)地址指針,讓它指向第一塊空閑區(qū)地址。申請空閑區(qū)：沿鏈查找并取一個長度能滿足要求的空閑區(qū)；歸還空閑區(qū)：把此空閑區(qū)鏈入空閑區(qū)鏈表的相應(yīng)位置。19鏈表空閑區(qū)管理方法空閑區(qū)開頭單元存放本空閑區(qū)長度及下個空閑區(qū)可變分區(qū)管理分配算法1）最先適應(yīng)分配算法空閑區(qū)通常按地址從小到大排列，分配第一個滿足長度要求的空閑區(qū)；優(yōu)點：分配從低地址開始，使高地址部分比較少用，以保持一個大空閑區(qū)，有利于大作業(yè)的裝入；缺點：分區(qū)利用不均衡，回收分區(qū)比較麻煩。

20可變分區(qū)管理分配算法1）最先適應(yīng)分配算法202）下次適應(yīng)分配算法1）的變種，每次分配時從未分配區(qū)的上次掃描結(jié)束處順序查找?？梢越鉀Q1）的缺點。3)最優(yōu)適應(yīng)分配算法分配能滿足要求的最小區(qū)?？梢詫⒖臻e區(qū)按照大小從小到大排列，查找第一個滿足要求的。優(yōu)點：主存利用率好。缺點：分割剩下的空閑區(qū)比較小，難以利用；查找時間比較長。212）下次適應(yīng)分配算法214）最壞適應(yīng)分配算法分配能滿足要求的最大區(qū)；可以將空閑區(qū)按照大小從大到小排列，查找第一個滿足要求的。效率大致等同于最先適應(yīng)法。5)快速適應(yīng)分配算法為經(jīng)常用到的長度的空閑區(qū)設(shè)置單獨的鏈表。優(yōu)點：查找快速；缺點：歸還時與相鄰空閑區(qū)的合并即復(fù)雜又費時。224）最壞適應(yīng)分配算法22下表為某系統(tǒng)中的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲管理策略?，F(xiàn)有以下作業(yè)序列：96KB，20KB，200KB，分別使用首次適應(yīng)、最佳適用和最壞適用算法來處理這個作業(yè)序列，試問哪一種算法可以滿足該作業(yè)序列的請求，為什么？分區(qū)號大小起始地址132KB100KB210KB150KB35KB200KB4218KB220KB596KB530KB例題：FF(N)BF(Y)WF(N)2/20/122/20/121/96/1223/200/181/96/1222/20/1021/96/023下表為某系統(tǒng)中的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲管理策略?？勺兎謪^(qū)地址轉(zhuǎn)換與存儲保護

基址基址寄存器邏輯地址CPU絕對地址操作系統(tǒng)區(qū)空閑分區(qū)1用戶作業(yè)1空閑分區(qū)2限長限長寄存器<限長越界中斷24可變分區(qū)地址轉(zhuǎn)換與存儲保護基址基址寄存器邏輯地址CPU絕多對基址/限長寄存器

進程B虛CPU進程A虛CPU物理主存進程A私有空間進程B私有空間共享區(qū)重定位寄存器1限長寄存器1重定位寄存器2限長寄存器2重定位寄存器1限長寄存器1重定位寄存器2限長寄存器2

多對重定位寄存器支持主存共享25多對基址/限長寄存器進程B虛CPU進程A虛CPU物理主存4.2.3伙伴系統(tǒng)伙伴原理伙伴系統(tǒng)是一種固定分區(qū)和可變分區(qū)折中的主存管理算法，基本原理：任何尺寸為2i的空閑塊可以被分為兩個尺寸為2i-1的空閑塊，這兩個空閑塊稱為伙伴?；锇橥ㄟ^對大塊的物理主存劃分而獲得假如從第0個頁面開始到第3個頁面結(jié)束的主存每次都對半劃分，那么第一次劃分獲得大小為2頁的伙伴，如0、1和2、3進一步劃分，可以獲得大小為1頁的伙伴，例如0和1，2和301230123264.2.3伙伴系統(tǒng)伙伴原理0123012326伙伴系統(tǒng)原理128k256k384k512k640k768k896k1MA128256512AB64256512AB64C128512128B64C128512128BDC12851212864DC128512256C128512102427伙伴系統(tǒng)原理128k256k384k52.Linux伙伴系統(tǒng)1)以page結(jié)構(gòu)為數(shù)組元素的mem_map[]數(shù)組2)以free_area_struct結(jié)構(gòu)為數(shù)組元素的free_area數(shù)組3)位圖數(shù)組(bitmap)282.Linux伙伴系統(tǒng)1)以page結(jié)構(gòu)為數(shù)組元素的mem3.Linux基于伙伴的slab分配器(1)為什么要使用slab分配器?緩沖機制，能夠提高效率slab的結(jié)構(gòu)見下頁圖slab的操作kmem-cache-create()kmem-cache-aloc()與kmem-cache-free()kmem-cache-grow()與kmem-cache-reap()kmalloc()kfree()kmem-getpages()與kmem-frepages()293.Linux基于伙伴的slab分配器(1)為什么要使用slLinux基于伙伴的slab分配器(2)slab分配器組成cacheslabslabslabslabslabslabslabcachecacheslabslab滿slab半滿slab空slab存pcb存inode存vma30Linux基于伙伴的slab分配器(2)slab分配器組成c4.2.4主存不足的存儲管理技術(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è)41.移動技術(shù)314.2.4主存不足的存儲管理技術(shù)操作系統(tǒng)作業(yè)1空閑區(qū)作業(yè)有關(guān)移動問題討論移動條件在可變分區(qū)算法中，隨著進程不斷的裝入和撤銷，導(dǎo)致主存中常常出現(xiàn)分散的小空閑區(qū)，稱為碎片。當在未分配區(qū)中找不到足夠大的空閑區(qū)來裝入新進程時，可采用移動技術(shù)，將分散的空閑空閑區(qū)匯集成片。移動時機進程撤銷之后釋放分區(qū)時，如果它不與空閑區(qū)鄰接，立即實施移動。進程裝入分區(qū)時，如果它不與空閑區(qū)鄰接，立即實施引動。32有關(guān)移動問題討論移動條件32移動算法（假設(shè)進程A請求分配xKB主存）步驟1：查主存分配表，若有大于xKB的空閑區(qū)，轉(zhuǎn)步驟4；步驟2：若空閑區(qū)總和小于xKB，則令進程A等待主存資源；步驟3：移動主存的相關(guān)分區(qū)信息；修改主存分配表的有關(guān)表項；修改被移動者的基礎(chǔ)寄存器等信息；步驟4：分配xKB主存；修改主存分配表的有關(guān)項；設(shè)置進程A的基址寄存器；有申請者等待時予以釋放，算法結(jié)束。開銷非常大，極少使用33移動算法（假設(shè)進程A請求分配xKB主存）332.對換技術(shù)對換的作用通過將主存和磁盤的進程移出移入，解決主存容量不足的問題。對換進程的選擇選擇哪個進程換出；決定把進程的哪些信息移出去；需要確定對換時機。UNIX對換器Windows對換器342.對換技術(shù)對換的作用34在任何時候只在內(nèi)存中保留所需的指令和數(shù)據(jù)由用戶實現(xiàn)，讓不會同時調(diào)用的子模塊共同使用同一內(nèi)存區(qū)F

20KD

22KE

24KB

12KC

15KA

30K常駐A（30KB）覆蓋區(qū)0（15KB）覆蓋區(qū)1（24KB）A占用BC共用DEF共用3.覆蓋技術(shù)35在任何時候只在內(nèi)存中保留所需的指令和數(shù)據(jù)F

20KD

22K碎片外部碎片：存在分區(qū)外，所有內(nèi)存之和可以滿足請求，但不連續(xù)內(nèi)部碎片：存在分區(qū)內(nèi)，但已不能滿足任何請求解決外部碎片問題的方法緊縮（compaction）：移動內(nèi)存內(nèi)容，以便所有空閑空間合并成一整塊允許物理地址空間為非連續(xù)分頁分段36碎片外部碎片：存在分區(qū)外，所有內(nèi)存之和可以滿足請求，但不連續(xù)4.3分頁式存儲管理4.3.1分頁式存儲管理的基本原理4.3.2快表4.3.3分頁式存儲空間的分配和去配4.3.4分頁式存儲空間的頁面共享和保護4.3.5多級頁表4.3.6反置頁表374.3分頁式存儲管理4.3.1分頁式存儲管理的基本原理4.3.1分頁式存儲管理為什么要引進分頁技術(shù)?基本原理頁面：進程邏輯地址空間分成大小相等的區(qū)；頁框（幀）：主存物理地址空間分成大小相等的區(qū)，其大小跟頁面大小相等；邏輯地址形式：頁號＋頁內(nèi)位移頁表和地址轉(zhuǎn)換（后面圖）基本原理(1)384.3.1分頁式存儲管理為什么要引進分頁技術(shù)?基本原理(1基本原理(2)作業(yè)的頁面與分給的頁框如何建立聯(lián)系呢？邏輯地址(頁面)如何變換成物理地址(頁框)呢？作業(yè)的物理地址空間由連續(xù)變成分散后，如何保證程序正確執(zhí)行呢？使用動態(tài)重定位技術(shù)，給每個頁面設(shè)立重定位寄存器，重定位寄存器的集合便稱頁表。頁表是操作系統(tǒng)為每個用戶作業(yè)建立的，用來記錄程序頁面和主存對應(yīng)頁框的對照表。39基本原理(2)作業(yè)的頁面與分給的頁框如何建立聯(lián)系呢？使用動態(tài)頁0頁1頁2頁314370123頁0頁2頁1頁301234567邏輯內(nèi)存頁表物理內(nèi)存頁號

幀號幀號物理內(nèi)存和邏輯內(nèi)存的分頁模型40頁0頁1頁2頁314370123頁0頁2頁邏輯地址到物理地址的轉(zhuǎn)換56120123頁表例：說明：頁大小為4B，頁表如圖所示，將邏輯地址0、3、4、13轉(zhuǎn)換為相應(yīng)物理地址答案：20、23、24、90/4=0…05×4+0=203/4=0…35×4+3=234/4=1…06×4+0=2413/4=3…12×4+1=941邏輯地址到物理地址的轉(zhuǎn)換56120123頁練習(xí)：邏輯地址到物理地址的轉(zhuǎn)換說明：頁大小為1024B，頁表如圖所示，將邏輯地址1011、2148、3000、4000、5012轉(zhuǎn)換為相應(yīng)物理地址23160123頁表答案：3059、1124、1976、7072、邏輯地址非法1011/1024=0…10112×1024+1011=30592148/1024=2…1001×1024+100=11243000/1024=2…9521×1024+952=19764000/1024=3…9286×1024+928=70725012/1024=4…916頁號4不存在42練習(xí)：邏輯地址到物理地址的轉(zhuǎn)換說明：頁大小為1024B，頁表4.3.2快表相聯(lián)存儲器（翻譯后備緩沖（translationlook-asidebuffer，TLB））：關(guān)聯(lián)的快速內(nèi)存TLB與頁表一起工作（了解工作過程）434.3.2快表相聯(lián)存儲器（翻譯后備緩沖（translati采用相聯(lián)存儲器的地址轉(zhuǎn)換假定訪問主存時間為100毫微秒，訪問相聯(lián)存儲器時間為20毫微秒，相聯(lián)存儲器為32個單元時快表命中率可達90%，按邏輯地址存取的平均時間為：（100＋20）×90%＋(100+100+20)×(1-90%)＝130比兩次訪問主存的時間100×2+20＝200下降了三成多。44采用相聯(lián)存儲器的地址轉(zhuǎn)換假定訪問主存時間為100毫微秒，訪問4.3.3分頁式存儲空間的分配和去配(1)位示圖法每位與一幀相對應(yīng)，用0/1表示對應(yīng)塊為空閑/已占用，用另一專門字記錄當前空閑塊數(shù)。鏈表方法每個表項包含：進程占用區(qū)（P）還是空閑區(qū)（H）起始地址長度指向下一表項的指針454.3.3分頁式存儲空間的分配和去配(1)位示圖法45主存分配的位示圖和鏈表方法46主存分配的位示圖和鏈表方法464.3.4分頁存儲空間的頁面共享和保護(1)數(shù)據(jù)共享允許不同進程對共享的數(shù)據(jù)頁用不同的頁號，只要讓各自頁表中的有關(guān)表項指向共享的數(shù)據(jù)頁框；程序共享指令包含指向其它指令或數(shù)據(jù)的地址。標志位保護方法在頁表中增加標志位，指出此頁的信息只讀/讀寫/只可執(zhí)行/不可訪問等。鍵保護方法474.3.4分頁存儲空間的頁面共享和保護(1)數(shù)據(jù)共享47分頁存儲空間的頁面共享和保護(2)共享庫包含共享函數(shù)的目標代碼塊動態(tài)鏈接器負責(zé)動態(tài)鏈接。動態(tài)鏈接：共享庫運行時可加載到任意的主存區(qū)域，并在主存中和一個程序鏈接起來。編譯和動態(tài)鏈接共享庫的過程48分頁存儲空間的頁面共享和保護(2)共享庫48分頁存儲空間的頁面共享和保護(3)

Windows動態(tài)鏈接編譯后的目標文件引入庫(DLL函數(shù)的定位信息)鏈接器可執(zhí)行程序

主存重要定位信息動態(tài)鏈接庫調(diào)用DLL中的函數(shù)49分頁存儲空間的頁面共享和保護(3)Windows動態(tài)鏈接編4.3.5多級頁表多級頁表的概念多級頁表的具體做法邏輯地址結(jié)構(gòu)邏輯地址到物理地址轉(zhuǎn)換過程504.3.5多級頁表多級頁表的概念50多級頁表的概念系統(tǒng)為每個進程建一張頁目錄表,它的每個表項對應(yīng)一個頁表頁,而頁表頁的每個表項給出了頁面和頁框的對應(yīng)關(guān)系,頁目錄表是一級頁表,頁表頁是二級頁表。邏輯地址結(jié)構(gòu)有三部分組成：頁目錄、頁表頁和位移。51多級頁表的概念系統(tǒng)為每個進程建一張頁目錄表,它的每個表項對應(yīng)多級頁表地址轉(zhuǎn)換過程頁框號頁內(nèi)位移頁目錄位移頁表頁位移頁內(nèi)位移BF進程一級頁表進程二級頁表物理地址邏輯地址頁目錄表控制寄存器52多級頁表地址轉(zhuǎn)換過程頁框號頁內(nèi)位移頁目錄位移頁解決頁表頁占用主存空間的問題進程運行涉及頁面的頁表頁應(yīng)放在主存,其他頁表頁使用時再調(diào)入,在頁目錄表中增加特征位,指示對應(yīng)的頁表頁是否已調(diào)入主存,地址轉(zhuǎn)換機構(gòu)根據(jù)邏輯地址中的dir,去查頁目錄表對應(yīng)表項,如未調(diào)入,應(yīng)產(chǎn)生一個”缺頁表頁”中斷信號，請求操作系統(tǒng)將頁表頁調(diào)入主存。53解決頁表頁占用主存空間的問題進程運行涉及頁面的頁表頁應(yīng)放在主SUNSPARC計算機三級分頁結(jié)構(gòu)上下文號索引1(8)索引2(6)索引3(6)偏移(12)上下文表第一級第二級第三級4K頁面04095頁表54SUNSPARC計算機三級分頁結(jié)構(gòu)上下文號索引1(8)多級頁表結(jié)構(gòu)的本質(zhì)多級不連續(xù)導(dǎo)致多級索引。以二級頁表為例，用戶程序的頁面不連續(xù)存放，要有頁面地址索引，該索引是進程頁表；進程頁表又是不連續(xù)存放的多個頁表頁，故頁表頁也要頁表頁地址索引，該索引就是頁目錄。頁目錄項是頁表頁的索引，而頁表頁項是進程程序的頁面索引。55多級頁表結(jié)構(gòu)的本質(zhì)多級不連續(xù)導(dǎo)致多級索引。554.3.5反置頁表(1)

頁框號位移進程標識頁號位移進程標識頁號特征位鏈指針序號反置頁表物理地址邏輯地址··哈希函數(shù)哈希表反置頁表及其地址轉(zhuǎn)換564.3.5反置頁表(1)頁框號位移進程標識反置頁表(2)IPT是為主存中的每一個物理塊建立一個頁表并按照塊號排序,該表每個表項包含正在訪問該頁框的進程標識、頁號及特征位,用來完成主存頁框到訪問進程的頁號、即物理地址到邏輯地址的轉(zhuǎn)換。57反置頁表(2)IPT是為主存中的每一個物理塊建立一個頁表并按反置頁表(3)反置頁表地址轉(zhuǎn)換過程如下:邏輯地址給出進程標識和頁號,用它們?nèi)ケ容^IPT,若整個反置頁表中未能找到匹配的頁表項,說明該頁不在主存,產(chǎn)生請頁中斷,請求操作系統(tǒng)調(diào)入;否則，該表項的序號便是頁框號,塊號加上位移,便形成物理地址。58反置頁表(3)反置頁表地址轉(zhuǎn)換過程如下:58分頁技術(shù)不會產(chǎn)生外部碎片，但會產(chǎn)生內(nèi)部碎片分頁的重要特點是用戶觀點的內(nèi)存和實際的物理內(nèi)存的分離分頁可以共享共同代碼分頁內(nèi)存管理方案小結(jié)59分頁技術(shù)不會產(chǎn)生外部碎片，但會產(chǎn)生內(nèi)部碎片分頁內(nèi)存管理方案小4.4分段式存儲管理4.4.1程序的分段結(jié)構(gòu)4.4.2分段式存儲管理的基本原理4.4.3段的共享和保護4.4.4分段和分頁的比較604.4分段式存儲管理4.4.1程序的分段結(jié)構(gòu)604.4.1程序的分段結(jié)構(gòu)分段存儲管理引入的主要原因滿足用戶（程序員）編程和使用上的要求。模塊化程序設(shè)計的分段結(jié)構(gòu)（下頁圖）分頁存儲管理一維地址結(jié)構(gòu)分段存儲管理二維地址結(jié)構(gòu)614.4.1程序的分段結(jié)構(gòu)分段存儲管理引入的主要原因61模塊化程序設(shè)計的分段結(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ū)段62模塊化程序設(shè)計的分段結(jié)構(gòu)子程序段X數(shù)組段A┇主程序段子程序4.4.2分段式存儲管理的基本原理(1)兩維邏輯地址段號：段內(nèi)地址段表段表指出主存中各分段的段號、段起始地址和段長度，起到基址/限長寄存器的作用。段式存儲管理的地址轉(zhuǎn)換和存儲保護634.4.2分段式存儲管理的基本原理(1)兩維邏輯地址63分段式存儲管理的基本原理(2)

段控制寄存器

段表始址段表長度

段號s位移d

段長基址物理地址越界?段表64分段式存儲管理的基本原理(2)段控制寄存器段表始址段表：將二維的邏輯地址映射為一維物理地址段基地址：包含該段在內(nèi)存中的開始物理地址段界限：指定該段的長度邏輯地址：段號s＋段內(nèi)偏移d邏輯地址到物理地址的轉(zhuǎn)換段號與段表長度進行比較，若段號超過了段表長度，則越界（非法地址），否則轉(zhuǎn)2）根據(jù)段表始址和段號計算出該段對應(yīng)段表項的位置，從中讀出該段在內(nèi)存的起始地址，檢查段內(nèi)地址是否超過該段的段長，若超過則越界（非法地址），否則轉(zhuǎn)3）將該段的起始地址與段內(nèi)位移相加，從而得到要訪問的物理地址邏輯地址到物理地址轉(zhuǎn)換65段表：將二維的邏輯地址映射為一維物理地址邏輯地址到物理地址轉(zhuǎn)邏輯地址到物理地址轉(zhuǎn)換例說明：段表如表1所示，將表2所示邏輯地址轉(zhuǎn)換為相應(yīng)物理地址答案：見表3段號內(nèi)存起始地址段長02196001230014290100313275804195296段號段內(nèi)位移2884100178非法

表1表2表390+88100>9666邏輯地址到物理地址轉(zhuǎn)換例說明：段表如表1所示，將表2所示邏輯說明：段表如表1所示，將表2所示邏輯地址轉(zhuǎn)換為相應(yīng)物理地址答案：見表3邏輯地址到物理地址轉(zhuǎn)換練習(xí)段號段內(nèi)位移0430110250034004112532段號內(nèi)存起始地址段長02105001235020210090313505904193895

表1表26402360非法1750非法非法表3210+4302350+10500>901350+400112>95段號5不存在67說明：段表如表1所示，將表2所示邏輯地址轉(zhuǎn)換為相應(yīng)物理地址邏4.4.3段的共享多對基址/限長寄存器段的共享，是通過不同作業(yè)段表中的項指向同一個段基址來實現(xiàn)。幾道作業(yè)共享的例行程序就可放在一個段中，只要讓各道作業(yè)的共享部分有相同的基址/限長值。對共享段的信息必須進行保護。

684.4.3段的共享多對基址/限長寄存器684.4.4分段和分頁的比較(1)

分段是信息的邏輯單位，由源程序的邏輯結(jié)構(gòu)所決定，用戶可見，段長可根據(jù)用戶需要來規(guī)定，段起始地址可從任何主存地址開始。分段方式中，源程序(段號，段內(nèi)位移)經(jīng)連結(jié)裝配后地址仍保持二維結(jié)構(gòu)。694.4.4分段和分頁的比較(1)分段是信息的邏輯單位，由分段和分頁的比較(2)

分頁是信息的物理單位，與源程序的邏輯結(jié)構(gòu)無關(guān)，用戶不可見，頁長由系統(tǒng)確定，頁面只能以頁大小的整倍數(shù)地址開始。分頁方式中，源程序(頁號，頁內(nèi)位移)經(jīng)連結(jié)裝配后地址變成了一維結(jié)構(gòu)。70分段和分頁的比較(2)分頁是信息的物理單位，與源程序的邏輯4.5虛擬存儲管理4.5.1虛擬存儲管理的概念4.5.2請求分頁虛擬存儲管理4.5.3請求分段虛擬存儲管理4.5.4請求段頁式虛擬存儲管理714.5虛擬存儲管理4.5.1虛擬存儲管理的概念714.5.1虛擬存儲管理的概念虛擬內(nèi)存（virtualmemory）：允許進程的執(zhí)行不必完全在內(nèi)存中，程序可以比物理內(nèi)存大。在許多情況下不需要將整個程序放到內(nèi)存中：處理異常錯誤條件的代碼（幾乎不執(zhí)行）數(shù)組、鏈表和表通常分配了比實際所需更多的內(nèi)存程序的某些選項或特點可能很少使用能夠執(zhí)行只有部分在內(nèi)存中的程序的好處程序不再受現(xiàn)有的物理內(nèi)存空間限制更多程序可同時執(zhí)行，CPU利用率相應(yīng)增加用戶程序會運行的更快724.5.1虛擬存儲管理的概念虛擬內(nèi)存（virtualme虛擬存儲器虛擬存儲器的定義：在具有層次結(jié)構(gòu)存儲器的計算機系統(tǒng)中，采用自動實現(xiàn)部分裝入和部分對換功能，為用戶提供一個比物理主存容量大得多的，可尋址的一種“主存儲器”。73虛擬存儲器虛擬存儲器的定義：73

虛擬存儲器的概念圖

邏輯地址空間處理器虛地址存儲管理部件實地址主存輔存物理地址空間74

虛擬存儲器的概念圖邏輯地址空間處程序的局部性原理指程序在執(zhí)行過程中的一個較短時間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲區(qū)域中。又可細分時間局部性和空間局部性。時間局部性：最近訪問過的程序代碼和數(shù)據(jù)很快又被訪問?？臻g局部性：某存儲單元被使用之后，其相鄰的存儲單元也很快被使用。75程序的局部性原理指程序在執(zhí)行過程中實現(xiàn)虛擬存儲器須解決的問題

主存輔存統(tǒng)一管理問題邏輯地址到物理地址的轉(zhuǎn)換問題

部分裝入和部分對換問題76實現(xiàn)虛擬存儲器須解決的問題主存輔存統(tǒng)一管理問題76虛擬存儲管理實現(xiàn)技術(shù)請求分頁虛擬存儲管理請求分段虛擬存儲管理請求段頁式虛擬存儲管理77虛擬存儲管理實現(xiàn)技術(shù)請求分頁虛擬存儲管理774.5.2請求分頁虛擬存儲系統(tǒng)1.請求分頁虛擬存儲系統(tǒng)的硬件支撐(1)主存管理單元MMU完成邏輯地址到物理地址的轉(zhuǎn)換功能，它接受虛擬地址作為輸入，物理地址作為輸出，直接送到總線上，對主存單元進行尋址。784.5.2請求分頁虛擬存儲系統(tǒng)1.請求分頁虛擬存儲系統(tǒng)的硬分頁式虛擬存儲系統(tǒng)的硬件支撐(2)

CPUMMU內(nèi)存CPU把邏輯地址送至MMUMMU把物理地址送至主存MMU的位置、功能和16個4KB頁面情況下MMU的內(nèi)部操作CPU送入的邏輯地址(8196)0010000000000100110000000000100MMU送出的物理地址00101100112110130001410015011160000700008101190000…頁號頁框號在主存否79分頁式虛擬存儲系統(tǒng)的硬件支撐(2)CPUMMU內(nèi)CPU把MMU主要功能(1)管理硬件頁表基址寄存器。(2)分解邏輯地址。(3)管理快表TLB。(4)訪問頁表。(5)發(fā)出缺頁中斷或越界中斷，并將控制權(quán)交給內(nèi)核存儲管理處理。(6)設(shè)置和檢查頁表中各個特征位。80MMU主要功能(1)管理硬件頁表基址寄存器。802.請求分頁虛擬存儲系統(tǒng)的基本原理分頁式虛存不把作業(yè)信息(程序和數(shù)據(jù))全部裝入主存，僅裝入立即使用的頁面，在執(zhí)行過程中訪問到不在主存的頁面時，產(chǎn)生缺頁中斷，再從磁盤動態(tài)地裝入。怎樣才能發(fā)現(xiàn)頁面不在主存中呢?怎樣處理這種情況呢?采用的辦法是：擴充頁表的內(nèi)容,增加駐留標志位和頁面輔存的地址等信息。812.請求分頁虛擬存儲系統(tǒng)的基本原理分頁式虛存不把作業(yè)信息(程頁式虛擬存儲管理頁表擴展其它標志：訪問權(quán)限位修改位（Modified）引用位（Renferenced）頁號駐留標志

頁框號

輔存地址其它標志

82頁式虛擬存儲管理頁表擴展其它標志：頁號駐留標志頁框號請求分頁虛存地址轉(zhuǎn)換過程(1)

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

頁內(nèi)地址頁號頁內(nèi)地址83請求分頁虛存地址轉(zhuǎn)換過程(1)邏輯空間地址主存(用戶區(qū)請求分頁虛存地址轉(zhuǎn)換過程(2)查快表有登記無登記查頁表登記入快表發(fā)缺頁中斷在主存在輔存形成絕對地址繼續(xù)執(zhí)行指令重新執(zhí)行被中斷指令恢復(fù)現(xiàn)場調(diào)整頁表和主存分配表裝入所需頁面主存有空閑塊保護現(xiàn)場有選擇調(diào)出頁面該頁是否修改未修改已修改把該頁寫回輔存相應(yīng)位置操作系統(tǒng)硬件邏輯地址無84請求分頁虛存地址轉(zhuǎn)換過程(2)查快表有登記無登記查頁表登記入請求頁式虛擬存儲系統(tǒng)優(yōu)缺點優(yōu)點：作業(yè)的程序和數(shù)據(jù)可按頁分散存放在主存中，減少移動開銷，有效解決了碎片問題;既有利于改進主存利用率，又有利于多道程序運行。缺點：要有硬件支持，要進行缺頁中斷處理，機器成本增加，系統(tǒng)開銷加大。85請求頁式虛擬存儲系統(tǒng)優(yōu)缺點優(yōu)點：作業(yè)的程序和數(shù)據(jù)可按頁分散存3.頁面裝入策略和頁面清除策略頁面裝入主存,有兩種策略：請頁式調(diào)度：僅調(diào)入所需頁面預(yù)調(diào)式調(diào)度：使用前預(yù)先調(diào)入若干頁何時把一個修改過的頁面寫回輔存儲器，有兩種策略：請頁式清除：僅當一頁被選中進行替換且被修改過，才寫回磁盤。預(yù)清除：成批進行，所有被更改過的頁面，在需要替換前把它們都寫回磁盤。863.頁面裝入策略和頁面清除策略頁面裝入主存,有兩種策略：864.頁面分配策略系統(tǒng)為進程分配主存,需考慮因素:①分給進程的空間越小,同一時間處于主存的進程就越多，至少有一個進程處于就緒態(tài)的可能性就越大②如果進程只有小部分在主存里,即使局部性很好,缺頁中斷率還會相當③因程序的局部性原理，分給進程的主存超過一定限度后，再增加主存空間,不會明顯降低進程的缺頁中斷率。874.頁面分配策略系統(tǒng)為進程分配主存,需考慮因素:87頁面分配策略：固定分配進程保持頁框數(shù)固定不變,稱固定分配;進程創(chuàng)建時,根據(jù)進程類型和程序員的要求決定頁框數(shù),只要有一個缺頁中斷產(chǎn)生,進程就會有一頁被替換。88頁面分配策略：固定分配進程保持頁框數(shù)固定不變,稱固定分配;8頁面分配策略：可變分配進程分得的頁框數(shù)可變,稱可變分配;進程執(zhí)行的某階段缺頁率較高,說明目前局部性較差，系統(tǒng)可多分些頁框以降低缺頁率，反之說明進程目前的局部性較好,可減少分給進程的頁框數(shù)89頁面分配策略：可變分配進程分得的頁框數(shù)可變,稱可變分配;8頁面替換策略：局部替換和全局替換如果頁面替換算法的作用范圍是整個系統(tǒng)，稱全局頁面替換算法,它可以在運行進程間動態(tài)地分配頁框。如果頁面替換算法的作用范圍局限于本進程，稱為局部頁面替換算法,它實際上需要為每個進程分配固定的頁框。 90頁面替換策略：局部替換和全局替換如果頁面替換算法的作用范圍是固定分配和局部替換策略配合使用(1)

進程分得的頁框數(shù)不變，發(fā)生缺頁中斷，只能從進程的頁面中選頁替換，保證進程的頁框總數(shù)不變。策略難點：應(yīng)給每個進程分配多少頁框?給少了,缺頁中斷率高;給多了,使主存中能同時執(zhí)行的進程數(shù)減少，進而造成處理器和其它設(shè)備空閑。91固定分配和局部替換策略配合使用(1)進程分得的頁框數(shù)不變，固定分配和局部替換策略配合使用(2)采用固定分配算法，系統(tǒng)把頁框分配給進程，采用：①平均分配②按比例分配③優(yōu)先權(quán)分配92固定分配和局部替換策略配合使用(2)采用固定分配算法，系統(tǒng)把可變分配和全局替換策略配合使用先每個進程分配一定數(shù)目頁框,os保留若干空閑頁框,進程發(fā)生缺頁中斷時，從系統(tǒng)空閑頁框中選一個給進程,這樣產(chǎn)生缺頁中斷進程的主存空間會逐漸增大,有助于減少系統(tǒng)的缺頁中斷次數(shù)。系統(tǒng)擁有的空閑頁框耗盡時，會從主存中選擇一頁淘汰，該頁可以是主存中任一進程的頁面，這樣又會使那個進程的頁框數(shù)減少，缺頁中斷率上升。93可變分配和全局替換策略配合使用先每個進程分配一定數(shù)目頁框,o可變分配和局部替換配合使用其實現(xiàn)要點如下:(1)新進程裝入主存時，根據(jù)應(yīng)用類型、程序要求，分配給一定數(shù)目頁框,可用請頁式或預(yù)調(diào)式完成這個分配。(2)產(chǎn)生缺頁中斷時,從該進程駐留集中選一個頁面替換。(3)不時重新評價進程的分配，增加或減少分配給進程的頁框以改善系統(tǒng)性能。94可變分配和局部替換配合使用其實現(xiàn)要點如下:945.缺頁中斷率頁面替換當主存空間已滿又必須裝入新頁時，選擇主存中某頁淘汰。頁面淘汰算法選擇哪頁被淘汰的算法。“抖動”(Thrashing)現(xiàn)象剛被淘汰的頁面立即又要調(diào)用，調(diào)入不久又被淘汰，淘汰不久再被調(diào)入…如此反復(fù)，整個系統(tǒng)頻繁調(diào)頁，使得幾乎無時間進行計算任務(wù)。955.缺頁中斷率頁面替換95影響缺頁中斷率的因素(1)

假定作業(yè)p共計n頁，系統(tǒng)分配給它的主存塊只有m塊（１≤m≤n）。如果作業(yè)p在運行中成功的訪問次數(shù)為S，不成功的訪問次數(shù)為F，則總的訪問次數(shù)Ａ為：A=S+F又定義：f=F/A稱f為缺頁中斷率。96影響缺頁中斷率的因素(1)假定作業(yè)p共計n頁，系統(tǒng)分配給它影響缺頁中斷率的因素(2)

影響缺頁中斷率f的因素有：(1)主存頁框數(shù)。(2)頁面大小。(3)頁面替換算法。(4)程序特性。97影響缺頁中斷率的因素(2)影響缺頁中斷率f的因素有：976.全局頁面替換策略1)最佳頁面替換算法OPT2)先進先出頁面替換算法FIFO3)最近最少用頁面替換算法LRU4)第二次機會頁面替換算法SCR5)時鐘頁面替換算法Clock注：所有算法例子中采用請頁時調(diào)度，即最初假設(shè)主存中沒有頁面。986.全局頁面替換策略1)最佳頁面替換算法OPT981)最佳替換算法調(diào)入一頁而必須淘汰一個舊頁時，所淘汰的頁應(yīng)該是以后不再訪問的頁或距現(xiàn)在最長時間后再訪問的頁。OPT算法（Optimal），可用來作為衡量各種具體算法的標準。991)最佳替換算法調(diào)入一頁而必須淘汰一個舊頁時，所淘汰的頁應(yīng)該OPT例（可用幀數(shù)量3）引用串如下：70120304230321201701107107R107102102102R102302302R302342342R342302R302102R102F107F07F7置換幀3幀2幀1引用串10710212303240302107缺頁率

p=9/20=45%100OPT例（可用幀數(shù)量3）引用串如下：107107R107102)先進先出頁面替換算法基于程序總是按線性順序來訪問物理空間這一假設(shè)。算法總是淘汰最先調(diào)入主存的那一頁，或者說在主存中駐留時間最長的那一頁（常駐的除外）。實現(xiàn)技術(shù)(1)設(shè)置具有m個元素的頁號表，控制換頁(2)引入指針鏈成隊列1012)先進先出頁面替換算法基于程序總是按線性順序來訪問物理空間FIFO例容易理解和實現(xiàn)，性能并不總是很好例（可用幀數(shù)量3）引用串如下：70120304230321201701R107R207R217210210R210R310320320R320R324R024R034R032R132102R102F107F07F7置換幀3幀2幀110710212303240302107引用串缺頁率

p=15/20=75%102FIFO例容易理解和實現(xiàn)，性能并不總是很好R107R207R

Belady異常：頁錯誤率隨著所分配的幀數(shù)增加而增加的現(xiàn)象，例：123412512345幀1111444555555幀222211111333幀33332222244缺頁:FFFRRRRRR123412512345幀1111111555544幀222222211115幀33333332222幀4444444333缺頁:FFFFRRRRRR可用幀數(shù)3，9次缺頁可用幀數(shù)4，10次缺頁103Belady異常：頁錯誤率隨著所分配的幀數(shù)增加而增加的現(xiàn)3)最近最少用頁面替換算法算法淘汰的頁面是在最近一段時間里較久未被訪問的那頁。根據(jù)程序局部性原理，那些剛被使用過的頁面，可能馬上還要被使用，而在較長時間里未被使用的頁面，可能不會馬上使用到。1043)最近最少用頁面替換算法算法淘汰的頁面是在最近一段時間里較LRU例思想：置換過去最長時間沒有使用的頁例（可用幀數(shù)量3）引用串如下：70120304230321201701701701R701201R201231R231230230R230R234R204R304302R302102R102F107F07F7缺頁率

p=12/20=60%置換幀3幀2幀1引用串10710212303240302107105LRU例思想：置換過去最長時間沒有使用的頁701701R70LRU算法實現(xiàn)：頁面淘汰隊列隊列中存放當前在主存中的頁號，每當訪問一頁時就調(diào)整一次，使隊列尾總指向最近訪問的頁，隊列頭就是最近最少用的頁。發(fā)生缺頁中斷時總淘汰隊列頭所指示的頁；執(zhí)行一次頁面訪問后，需要從隊列中把該頁調(diào)整到隊列尾。106LRU算法實現(xiàn)：頁面淘汰隊列隊列中存放當前在主存中的頁號，每LRU算法實現(xiàn)：標志位法每頁設(shè)置一個引用標志位R，訪問某頁時，由硬件將頁標志位R置1，隔一定時間t將所有頁的標志R均清0。發(fā)生缺頁中斷時，從標志位R為0的頁中挑選一頁淘汰。挑選到要淘汰的頁后，也將所有頁的標志位R清0。107LRU算法實現(xiàn)：標志位法每頁設(shè)置一個引用標志位R，訪問某頁時LRU算法實現(xiàn)：多位計數(shù)器法每個頁面設(shè)置一個多位計數(shù)器，又叫最不常用頁面替換算法LFU。每當訪問一頁時，就使它對應(yīng)的計數(shù)器加１。當發(fā)生缺頁中斷時，可選擇計數(shù)值最小的對應(yīng)頁面淘汰，并將所有計數(shù)器全部清０。108LRU算法實現(xiàn)：多位計數(shù)器法每個頁面設(shè)置一個多位計數(shù)器，又叫LRU算法實現(xiàn)：多位計時器法為每個頁面設(shè)置一個多位計時器，每當頁面被訪問時，系統(tǒng)的絕對時間記入計時器。比較各頁面的計時器的值，選最小值的未使用的頁面淘汰，因為，它是最“老”的未使用的頁面。109LRU算法實現(xiàn)：多位計時器法為每個頁面設(shè)置一個多位計時器，每4)第二次機會頁面替換算法改進FIFO算法,把FIFO與頁表中的”引用位”結(jié)合起來使用；檢查FIFO中的隊首頁面(最早進入主存的頁面),如果它的”引用位”是0,這個頁面既老又沒有用，選擇該頁面淘汰;如果”引用位”是1,說明它進入主存較早，但最近仍在使用。把它的”引用位”清0,并把這個頁面移到隊尾，把它看作是一個新調(diào)入的頁。算法含義：最先進入主存的頁面，如果最近還在被使用的話,仍然有機會作為像一個新調(diào)入頁面一樣留在主存中。1104)第二次機會頁面替換算法改進FIFO算法,把FIFO與頁表5）時鐘頁面替換算法算法實現(xiàn)要點：一個頁面首次裝入主存，其“引用位”置0。主存中的任何頁面被訪問時,“引用位”置1。淘汰頁面時,從指針當前指向的頁面開始掃描循環(huán)隊列，把遷到的“引用位”是1的頁面的“引用位”清0,跳過這個頁面;把所遷到的“引用位”是0的頁面淘汰掉,指針推進一步。掃描循環(huán)隊列時，如果遷到的所有頁面的“引用位”為1，指針就會繞整個循環(huán)隊列一圈，把碰到的所有頁面的“引用位”清0;指針停在起始位置，并淘汰掉這一頁,然后，指針推進一步。1115）時鐘頁面替換算法算法實現(xiàn)要點：111時鐘頁面替換改進算法(1)把”引用位”和”修改位”結(jié)合起來使用，共組合成四種情況：(1)最近沒有被引用,沒有被修改(r=0,m=0)(2)最近被引用,沒有被修改(r=1,m=0)(3)最近沒有被引用,但被修改(r=0,m=1)(4)最近被引用過,也被修改過(r=1,m=1)112時鐘頁面替換改進算法(1)把”引用位”和”修改位”結(jié)合起來使時鐘頁面替換改進算法(2)步1：選擇最佳淘汰頁面，從指針當前位置開始,掃描循環(huán)隊列。掃描過程中不改變”引用位”，把迂到的第一個r=0,m=0的頁面作為淘汰頁面。步2：如果步1失敗，再次從原位置開始，查找r=0且m=1的頁面，把把迂到的第一個這樣的頁面作為淘汰頁面，而在掃描過程中把指針所掃過的頁面的”引用位”r置0。步3：如果步2失敗，指針再次回到了起始位置，由于此時所有頁面的”引用位”r均己為0，再轉(zhuǎn)向步1操作，必要時再做步2操作，這次一定可以挑出一個可淘汰的頁面。113時鐘頁面替換改進算法(2)步1：選擇最佳淘汰頁面，從指針當前頁置換算法練習(xí)已知頁面走向為1、2、1、3、1、2、4、2、1、3、4，且開始執(zhí)行時內(nèi)存中沒有頁面。若只給該作業(yè)分配2個物理塊。當采用FIFO、OPT、LRU頁置換算法時缺頁率為多少？假定現(xiàn)有一種置換算法，該算法淘汰頁面的策略為當需要淘汰頁面時，就把剛使用過的頁面作為淘汰對象，試問就相同的頁面走向，其缺頁率又為多少？假如分配3個物理塊呢？114頁置換算法練習(xí)已知頁面走向為1、2、1、3、1、2、4、2、11332211422114433111144423221311114114232223311311134222422212131242134FIFO9/11=81.8%OPT7/11=63.6%LRU8/11=72.7%NEW8/11=72.7%2個物理塊115113322114221144331111444232213111442221333111132222344111111222243433111111224223334121312421343個物理塊FIFO5/11=45.5%OPT5/11=45.5%LRU6/11=54.5%NEW6/11=54.5%1161114422213331111322223441111117.局部頁面替換算法1)局部最佳頁面替換算法2)工作集模型和工作集置換算法3)模擬工作集替換算法4)缺頁頻率替換算法1177.局部頁面替換算法1)局部最佳頁面替換算法1171)局部最佳頁面替換算法實現(xiàn)思想：進程在時刻t訪問某頁面，如果該頁面不在主存中，導(dǎo)致一次缺頁，把該頁面裝入一個空閑頁框。不論發(fā)生缺頁與否，算法在每一步要考慮引用串，如果該頁面在時間間隔(t,t+τ)內(nèi)未被再次引用，那么就移出頁面；否則，該頁被保留在進程的駐留集中，直到再次被引用。1181)局部最佳頁面替換算法實現(xiàn)思想：118局部最佳頁面替換算法例時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1---------√-P2----√------P3-√√√√√√√---P4√√√√------√P5------√√√--IntP3P2P5P1P4OuttP4P2P3P5P1119局部最佳頁面替換算法例時刻t012345678910引用串P2)工作集模型和工作集置換算法

進程工作集指“在某一段時間間隔內(nèi)進程運行所需訪問的頁面集合”。實現(xiàn)思想：工作集模型用來對局部最佳頁面替換算法進行模擬實現(xiàn)，不向前查看頁面引用串，而是基于程序局部性原理向后看，在任何給定時刻，一個進程不久的將來所需主存頁框數(shù)，可通過考查其過去最近的時間內(nèi)的主存需求做出估計。1202)工作集模型和工作集置換算法進程工作集指“在某一段時間間工作集替換示例時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1√√√√-----√√P2----√√√√---P3-√√√√√√√√√√P4√√√√√√√---√P5√√----√√√√√IntP3P2P5P1P4OuttP5P1P4P2121工作集替換示例時刻t012345678910引用串P4P3P3)模擬工作集替換算法老化(Aging)算法例如，時間間隔T定為1000次存儲器引用，頁面P在時刻t+0時寄存器為“1000”，在時刻t+1000時寄存器為“0100”，在時刻t+2000時寄存器為“0010”，在時刻t+3000時寄存器為“0001”，在時刻t+4000時寄存器為“0000”，此時，頁面p被移出工作集，時間戳算法若t_off>t_max，把頁面從工作集中移出1223)模擬工作集替換算法老化(Aging)算法1224)缺頁頻率替換算法缺頁頻率替換算法根據(jù)連續(xù)的缺頁之間的時間間隔來對缺頁頻率進行測量，每次缺頁時，利用測量時間調(diào)整進程工作集尺寸。規(guī)則：如果本次缺頁與前次缺頁之間的時間超過臨界值τ，那么，所有在這個時間間隔內(nèi)沒有引用的頁面都被移出工作集。1234)缺頁頻率替換算法缺頁頻率替換算法根據(jù)連續(xù)的缺頁之間的時間PFF替換示例時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1√√√√-----√√P2----√√√√√--P3-√√√√√√√√√√P4√√√√√√√√√-√P5√√√√--√√√√√IntP3P2P5P1P4OuttP1P5P2P4124PFF替換示例時刻t012345678910引用串P4P3P8.請求分頁虛擬存儲管理的幾個設(shè)計問題1)頁面大小考慮頁表大?。箜搩?nèi)存利用－小頁（減少碎片）頁讀寫所需時間－大頁精度－小頁降低頁錯誤數(shù)量－大頁分析：沒有最佳答案，趨向于大頁

1258.請求分頁虛擬存儲管理的幾個設(shè)計問題1)頁面大小1252)頁面交換區(qū)替換算法要挑選頁面淘汰出主存，但被淘汰出去的頁面可能很快使用，又要被重新裝入主存。操作系統(tǒng)必須保存被淘汰的頁面,例如UNIX/Linux使用交換區(qū)臨時保存頁面，系統(tǒng)初始化時,保留一定盤空間作交換區(qū)。1262)頁面交換區(qū)替換算法要挑選頁面淘汰出主存，但被淘汰出去的頁3)寫時復(fù)制(1)寫時復(fù)制(copy-on-write)是存儲管理節(jié)省物理主存(頁框)的一種頁面級優(yōu)化技術(shù),已被UNIX和Windows等采用，能減少主存頁面內(nèi)容的復(fù)制操作,減少相同內(nèi)容頁面在主存的副本數(shù)目。1273)寫時復(fù)制(1)寫時復(fù)制(copy-on-write)是存寫時復(fù)制(2)

原始數(shù)據(jù)原始數(shù)據(jù)原始數(shù)據(jù)進程地址空間物理地址空間原始數(shù)據(jù)原始數(shù)據(jù)原始數(shù)據(jù)進程地址空間物理地址空間原始數(shù)據(jù)原始數(shù)據(jù)原始數(shù)據(jù)進程地址空間原始數(shù)據(jù)原始數(shù)據(jù)原始數(shù)據(jù)進程地址空間頁面2副本頁面1頁面2頁面3頁面1頁面2頁面3128寫時復(fù)制(2)原始數(shù)據(jù)進程地址空間物理地址空間原始數(shù)據(jù)進程4.5.3請求分段虛擬存儲系統(tǒng)分段式虛擬存儲系統(tǒng)把作業(yè)的所有分段的副本都存放在輔助存儲器中，當作業(yè)被調(diào)度投入運行時，首先把當前需要的一段或幾段裝入主存，在執(zhí)行過程中訪問到不在主存的段時再把它們裝入。1294.5.3請求分段虛擬存儲系統(tǒng)分段式虛擬存儲系統(tǒng)把作業(yè)的所段式虛擬存儲管理的段表擴展段表中增加供管理使用的一些表項：特征位00(不在主存)01(在主存)11(共享段)；存取權(quán)限00(可執(zhí)行)01(可讀)11(可寫)130段式虛擬存儲管理的段表擴展段表中增加供管理使用的一些表項：段表中增加供管理使用的一些表項：擴充位0(固定長)1(可擴充)；標志位00(未修改)01(已修改)11(不可移動)；131段表中增加供管理使用的一些表項：131

S段在主存否是B<S段長度發(fā)越界中斷是否形成絕對地址繼續(xù)執(zhí)行指令操作系統(tǒng)硬件符合存取權(quán)限發(fā)保護中斷是否發(fā)缺段中斷移動或調(diào)出分段S段末端相鄰空閑區(qū)長度滿足要求地址錯S段可擴充是裝入S段重新啟動指令調(diào)整S段段表及主存分配表否非法存取否主存中有滿足S段長度的連續(xù)空閑區(qū)是否是移動或調(diào)出分段請求分段虛存管理的地址轉(zhuǎn)換132S段在主存否是B<S段長度發(fā)越界中斷是否形成絕對地址繼續(xù)請求分段虛擬存儲管理實現(xiàn)分段的共享和保護段共享表段的共享段的保護133請求分段虛擬存儲管理實現(xiàn)分段的共享和保護段共享表1334.5.4請求段頁式虛擬存儲管理段式存儲是基于用戶程序結(jié)構(gòu)的存儲管理技術(shù)，有利于模塊化程序設(shè)計，便于段的擴充、動態(tài)鏈接、共享和保護,但會生成段內(nèi)碎片浪費存儲空間頁式存儲是基于系統(tǒng)存儲器結(jié)構(gòu)的存儲管理技術(shù),存儲利用率高,便于系統(tǒng)管理，但不易實現(xiàn)存儲共享、保護和動態(tài)擴充把兩者結(jié)合起來就是段頁式存儲管理1344.5.4請求段頁式虛擬存儲管理段式存儲是基于用戶程序結(jié)構(gòu)虛地址以程序的邏輯結(jié)構(gòu)劃分成段(段頁式存儲管理的段式特征)實地址劃分成位置固定、大小相等的頁框(段頁式存儲管理的頁式特征)將每一段的線性地址空間劃分成與頁框大小相等的頁面，于是形成了段頁式存儲管理的特征。邏輯地址形式為：請求段頁式存儲管理的基本原理段號(s)段內(nèi)頁號(p)頁內(nèi)位移(d)135虛地址以程序的邏輯結(jié)構(gòu)劃分成段(段頁式存儲管理的段式特征)請請求段頁式存儲管理的數(shù)據(jù)結(jié)構(gòu)

段頁式存儲管理的數(shù)據(jù)結(jié)構(gòu)包括：作業(yè)表：登記進入系統(tǒng)中的所有作業(yè)及該作業(yè)段表的起始地址，段表：至少包含這個段是否在主存，以及該段頁表的起始地址,頁表：包含該頁是否在主存(中斷位)、對應(yīng)主存塊號。136請求段頁式存儲管理的數(shù)據(jù)結(jié)構(gòu)段頁式存儲管理的數(shù)據(jù)結(jié)構(gòu)包括請求段頁式存儲管理的動態(tài)地址轉(zhuǎn)換(1)從邏輯地址出發(fā)，先以段號s和頁號p作索引去查快表,如果找到,那么立即獲得頁p的頁框號p’,并與位移d一起拼裝得到訪問主存的實地址,從而完成了地址轉(zhuǎn)換。若查快表失敗,就要通過段表和頁表作地址轉(zhuǎn)換了，用段號s作索引,找到相應(yīng)表目,由此得到s段的頁表起址s’,再以p作索引得到s段p頁對應(yīng)的表目,得到頁框號p’;這時一方面把s段p頁和頁框號p’置換進快表，另一方面用p’和d生成主存實地址,從而完成地址轉(zhuǎn)換。137請求段頁式存儲管理的動態(tài)地址轉(zhuǎn)換(1)從邏輯地址出發(fā)，先以段請求段頁式存儲管理的動態(tài)地址轉(zhuǎn)換(2)如查段表時，發(fā)現(xiàn)s段不在主存，產(chǎn)生“缺段中斷”，引起系統(tǒng)查找s段在輔存的位置，將該段頁表調(diào)入主存；如查頁表時，發(fā)現(xiàn)s段的p頁不在主存，產(chǎn)生“缺頁中斷”，引起系統(tǒng)查找s段p頁在輔存的位置，并將該頁調(diào)入主存，當主存已無空閑頁框時，就會導(dǎo)致淘汰頁面。138請求段頁式存儲管理的動態(tài)地址轉(zhuǎn)換(2)如查段表時，發(fā)現(xiàn)s段不

段表控制寄存器段表始址段表長度段號s頁號p位移d段超長?頁框號位移段表頁表請求段頁式存儲管理的動態(tài)地址轉(zhuǎn)換(3)139段表控制寄存器段表始址段表長度段號s頁號p4.6Intelx86分段和分頁存儲結(jié)構(gòu)Intelx86系列CPU提供三種工作模式：實地址模式、保護模式和虛擬8086模式Intelx86上虛擬存儲管理核心表：LDT和GDT段寄存器和虛擬地址(b)段寄器高13位為段選擇符(a)虛擬地址段選擇符偏移量4732310indexTRPL152100=GDT/1=LDT特權(quán)級Intelx86虛擬地址和段選擇符1404.6Intelx86分段和分頁存儲結(jié)構(gòu)Intelx8虛擬地址空間大小虛擬地址空間共包含16K個存儲器分段，其中GDT映射一半（8192個）全局虛擬地址空間，由LDT映射另一半（8192個）局部虛擬地址空間，發(fā)生進程切換時，LDT更新為待執(zhí)行進程的LDT，而GDT保持不變。由于每段偏移量32位、即=4GB，整個虛存地址空間=16K×4GB=64TB。141虛擬地址空間大小虛擬地址空間共包含16K個存儲器分段，其中G4.7Linux虛擬存儲管理4.7.1Linux虛擬存儲管理概述在Linux中，進程可訪問4GB虛擬地址空間，其中，從0到3GB被用戶進程獨占并可直接進行訪問；從3GB到4GB是內(nèi)核空間，由所有核心態(tài)進程共享，存放系統(tǒng)代碼和數(shù)據(jù)。進程有一個頁目錄，大小為一個頁，頁目錄的起始地址存放在進程mm_struct結(jié)構(gòu)中，工作時被裝入寄存器CR3。頁目錄項為4字節(jié)，共有1024項，用來保存頁表的起始地址。每張頁表也用一個頁面存儲，每項為4字節(jié)，共有1024項，用來保存頁框基地址。1424.7Linux虛擬存儲管理4.7.1Linux虛擬存儲頁表項的格式

0位為頁面在/不在主存；1位若置位，頁面可讀可寫，否則只讀；2位為選擇用戶級訪問許可/內(nèi)核級訪問許可；3位為若置位表示頁面cache采用“直寫”，否則回寫緩存；4位為若置位，禁用高速緩存；5位為置位表示該頁面最近曾被訪問過；6位為被置位，表示頁面在上次該位被清除之后頁面內(nèi)容被改變過；7位為頁面大小；8位為全局頁面；12至31位是頁框基地址。頁框基址……pDACDWTU/SR/WP3112876543210143頁表項的格式0位為頁面在/不在主存；1位若置位，頁面可讀可4.7.2存儲管理數(shù)據(jù)結(jié)構(gòu)1.物理主存數(shù)據(jù)結(jié)構(gòu)物理主存分三個層次管理：1)存儲節(jié)點2)管理區(qū)3)頁框1444.7.2存儲管理數(shù)據(jù)結(jié)構(gòu)1.物理主存數(shù)據(jù)結(jié)構(gòu)1441)頁框管理物理主存劃分成頁框，其長度與頁面相等，系統(tǒng)中所有頁框都由mem_map表描述，它在初始化時通過free_area_init()函數(shù)創(chuàng)建。mem_map本身是由mem_map_t組成的數(shù)組，每個mem_map_t描述一個頁框，整個數(shù)組就代表系統(tǒng)中的全部頁框，數(shù)組下標就是物理頁框的序號，用于對頁框進行管理。1451)頁框管理物理主存劃分成頁框，其長度與頁面相等，系統(tǒng)中所2)管理區(qū)管理主存被劃分成三個區(qū)：ZONE_DMA區(qū)，專供DMA使用；ZONE_NORMAL區(qū)，被常規(guī)使用；ZONE_HIGHMEM區(qū)，內(nèi)核不能直接映射區(qū)。設(shè)置ZONE_DMA是保證磁盤I/O所需的連續(xù)物理頁框，ZONE_NORMAL里的頁框用作通常的主存分配。1462)管理區(qū)管理主存被劃分成三個區(qū)：146管理區(qū)數(shù)據(jù)結(jié)構(gòu)zone_struct含有一組空閑區(qū)隊列，typedefstructfree_area_struct｛/*空閑區(qū)隊列頭部結(jié)構(gòu)*/structlist_headfree_list；/*指向空閑區(qū)隊列*/unsignedint*map；/*指向bitmap表*/}free_area_t；147管理區(qū)數(shù)據(jù)結(jié)構(gòu)zone_struct含有一組空閑區(qū)隊列，14存儲節(jié)點管理數(shù)據(jù)結(jié)構(gòu)typedefstructpglist_data{/*存儲節(jié)點的結(jié)構(gòu)*/zone_tnode_zones［MAX_NR_ZONES］;/*該節(jié)點的管理區(qū)數(shù)組*/zonelist_tnode_zonelists［NR_GFPINDEX］；structpage*node_mem__map;/*存儲節(jié)點的主存映射表*/intnr_zones;/*存儲節(jié)點的管理區(qū)數(shù)目*/unsignedlong*valid_addr_bitmap;/*位圖表示的有效地址*/structbootmem_data*bdata;/*存放位圖的數(shù)據(jù)結(jié)構(gòu)*/unsignedlongnode_start_paddr;/*存儲節(jié)點起始物理地址*/unsignedlongnode_start_mapnr;/*在mem_map中的下標*/unsignedlongnode_size;/*存儲節(jié)點物理主存大小*/intnode_id;/*存儲節(jié)點標識符*/structpglist_data*node_next;/*下一存儲節(jié)點指針*/}pg_data_t;148存儲節(jié)點管理數(shù)據(jù)結(jié)構(gòu)typedefstructpgli2.虛擬主存管理1)虛存區(qū)vm_area_struct內(nèi)核將進程的每個虛存區(qū)作為一個單獨的主存對象管理，每個虛存區(qū)都擁有一致的屬性，比如訪問權(quán)限等，采用虛存區(qū)vma(virtualmemoryarea)來描述進程的虛擬主存的一個區(qū)域，而vma鏈表用來表示該進程實際用到的虛擬地址空間。1492.虛擬主存管理1)虛存區(qū)vm_area_struct2)主存描述符mm_struct進程有一個mm_struct結(jié)構(gòu)，在進程的task_struct結(jié)構(gòu)中有指針mm指向該進程的mm_struct結(jié)構(gòu)，mm_struct結(jié)構(gòu)是進程整個虛擬地址空間的抽象。結(jié)構(gòu)中的前三個虛存區(qū)指針：mmap用來建立一個虛存區(qū)間結(jié)構(gòu)的鏈接隊列；mmap_avl用來建立一個虛存區(qū)結(jié)構(gòu)的AVL樹；mmap_cache用來指向最近一次用到的那個虛存區(qū)結(jié)構(gòu)，因為程序具有的局部性，很可能這就是下次要用到的區(qū)間，以便提高效率。指針pgd指向該進程的頁表目錄，當進程被調(diào)度時，該指針被轉(zhuǎn)換成物理地址，寫入控制寄存器CR3。1502)主存描述符mm_struct進程有一個mm_struct進程虛存管理數(shù)據(jù)結(jié)構(gòu)進程任務(wù)結(jié)構(gòu)task_struct*mm虛存區(qū)結(jié)構(gòu)vm_area_struct*vm_mmv