教學課件PPT 存儲管理

1第第4 4章章 存儲管理存儲管理 重要內容重要內容0存儲器存儲器0連續(xù)存儲空間管理連續(xù)存儲空間管理0分頁存儲管理分頁存儲管理0分段存儲管理分段存儲管理0虛擬存儲管理虛擬存儲管理0Intel x86Intel x86分段和分頁存儲結構分段和分頁存儲結構0LinuxLinux虛擬存儲管理虛擬存儲管理0Windows 2003Windows 2003虛擬存儲管理（自學）虛擬存儲管理（自學）2存儲管理的功能存儲管理的功能 分配和去配分配和去配0請求和釋放主存空間請求和釋放主存空間 抽象和映射抽象和映射0抽象成一維數(shù)組或二維地址空間抽象成一維數(shù)組或二維地址空間0地址轉換地址轉換 隔離和共享隔離和共享0隔離實現(xiàn)存儲保護功能隔離實現(xiàn)存儲保護功能0超越隔離機制，提高主存利用率超越隔離機制，提高主存利用率 存儲擴充存儲擴充0虛擬，允許進程虛擬地址空間大于主存空間虛擬，允許進程虛擬地址空間大于主存空間34.1 4.1 存儲器存儲器4.1.1 4.1.1 存儲器的層次存儲器的層次 4.1.2 4.1.2 地址轉換與存儲保護地址轉換與存儲保護 44.1.1 4.1.1 存儲器的層次存儲器的層次寄存器寄存器高速緩存高速緩存主存儲器主存儲器磁盤緩存磁盤緩存固定磁盤固定磁盤可移動存儲介質可移動存儲介質5 邏輯地址（虛地址）：邏輯地址（虛地址）：CPUCPU所生成的地址所生成的地址 物理地址（實地址）：內存單元所看到的地址物理地址（實地址）：內存單元所看到的地址 邏輯地址空間：由程序所生成的所有邏輯地址的邏輯地址空間：由程序所生成的所有邏輯地址的集合集合 物理地址空間：由邏輯地址所對應的所有物理地物理地址空間：由邏輯地址所對應的所有物理地址的集合址的集合 地址轉換或重定位：把邏輯地址轉換為物理地址地址轉換或重定位：把邏輯地址轉換為物理地址4.1.2 4.1.2 地址轉換與存儲保護（地址轉換與存儲保護（1 1）6 靜態(tài)重定位靜態(tài)重定位0地址轉換工作在進程執(zhí)行前一次完成；地址轉換工作在進程執(zhí)行前一次完成；0無須硬件支持，易于實現(xiàn)，但不允許程序在執(zhí)行過程無須硬件支持，易于實現(xiàn)，但不允許程序在執(zhí)行過程中移動位置。中移動位置。0早期單用戶單任務系統(tǒng)早期單用戶單任務系統(tǒng) 動態(tài)重定位動態(tài)重定位0地址轉換推遲到最后的可能時刻，即進程執(zhí)行時才完地址轉換推遲到最后的可能時刻，即進程執(zhí)行時才完成；成；0允許程序在主存中移動、便于主存共享、主存利用率允許程序在主存中移動、便于主存共享、主存利用率高。高。地址轉換與存儲保護地址轉換與存儲保護(2)(2)7存儲保護存儲保護 問題：保護操作系統(tǒng)不受用戶進程所影響，保護用戶進程問題：保護操作系統(tǒng)不受用戶進程所影響，保護用戶進程不受其他用戶進程所影響不受其他用戶進程所影響 方法方法1)1)存儲鍵保護存儲鍵保護v系統(tǒng)將主存劃分成大小相等的若干存儲塊，并給每個存系統(tǒng)將主存劃分成大小相等的若干存儲塊，并給每個存儲塊都分配一個單獨的保護鍵（鎖）；在程序狀態(tài)字儲塊都分配一個單獨的保護鍵（鎖）；在程序狀態(tài)字PSWPSW中設置有保護鍵字段，對不同的作業(yè)賦予不同的代中設置有保護鍵字段，對不同的作業(yè)賦予不同的代碼（鑰匙）；鑰匙和鎖相配才允許訪問碼（鑰匙）；鑰匙和鎖相配才允許訪問2)2)界限寄存器（下頁圖）界限寄存器（下頁圖）v上、下界防護上、下界防護：硬件為分給用戶作業(yè)的連續(xù)的主存空間：硬件為分給用戶作業(yè)的連續(xù)的主存空間設置一對上、下界，分別指向該存儲空間的上、下界設置一對上、下界，分別指向該存儲空間的上、下界v基址、限長防護基址、限長防護：基址寄存器存放當前正執(zhí)行者的程序：基址寄存器存放當前正執(zhí)行者的程序地址空間所占分區(qū)的始址，限長寄存器存放該地址空間地址空間所占分區(qū)的始址，限長寄存器存放該地址空間的長度的長度地址轉換與存儲保護地址轉換與存儲保護(3)(3)8下限寄存器下限寄存器20002000上限寄存器上限寄存器35003500基址寄存器基址寄存器20002000限長寄存器限長寄存器15001500進程進程idid下限下限+ +上限寄存器上限寄存器基址基址+ +限長寄存器限長寄存器1 11000+19991000+19991000+9991000+9992 22000+35002000+35002000+15002000+15003 34000+50004000+50004000+10004000+1000內存映像內存映像進程1進程2進程3100019992000350040005000正運行的進程是進程正運行的進程是進程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 主存不足的存儲管理技術主存不足的存儲管理技術104.2.1 4.2.1 固定分區(qū)存儲管理固定分區(qū)存儲管理 固定分區(qū)存儲管理的基本思想固定分區(qū)存儲管理的基本思想0主存空間被分成數(shù)目固定不變的分區(qū)，各分區(qū)主存空間被分成數(shù)目固定不變的分區(qū)，各分區(qū)的大小不等，每個分區(qū)只裝入一個作業(yè)。的大小不等，每個分區(qū)只裝入一個作業(yè)。 固定分區(qū)存儲管理的數(shù)據(jù)結構固定分區(qū)存儲管理的數(shù)據(jù)結構0主存分配表：指出各分區(qū)的起始地址和長度；主存分配表：指出各分區(qū)的起始地址和長度；0占用標志：指示此分區(qū)是否被使用。占用標志：指示此分區(qū)是否被使用。 作業(yè)進入固定分區(qū)排隊策略作業(yè)進入固定分區(qū)排隊策略0每個分區(qū)有單獨的作業(yè)等待隊列；每個分區(qū)有單獨的作業(yè)等待隊列；0所有等待處理的作業(yè)排成一個等待隊列。所有等待處理的作業(yè)排成一個等待隊列。11固定分區(qū)的優(yōu)缺點固定分區(qū)的優(yōu)缺點 優(yōu)點優(yōu)點0能夠解決單道程序運行在并發(fā)環(huán)境下不能與能夠解決單道程序運行在并發(fā)環(huán)境下不能與CPUCPU速度匹速度匹配的問題配的問題0解決了單道程序運行時主存空間利用率低的問題解決了單道程序運行時主存空間利用率低的問題0實現(xiàn)簡單實現(xiàn)簡單 缺點缺點0大作業(yè)可能無法裝入大作業(yè)可能無法裝入0主存空間利用率不高，會出現(xiàn)內碎片主存空間利用率不高，會出現(xiàn)內碎片0擴充困難擴充困難0限制多道運行程序的個數(shù)限制多道運行程序的個數(shù)124.2.2 4.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理 可變分區(qū)存儲管理是按作業(yè)的實際大小來劃可變分區(qū)存儲管理是按作業(yè)的實際大小來劃分分區(qū)，且分區(qū)個數(shù)也是隨機的分分區(qū)，且分區(qū)個數(shù)也是隨機的, ,實現(xiàn)多個實現(xiàn)多個作業(yè)對主存的共享，進一步提高主存資源利作業(yè)對主存的共享，進一步提高主存資源利用率。用率。 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ù)結構可變分區(qū)存儲管理數(shù)據(jù)結構 可變分區(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ū)長度及下個空閑區(qū)開頭單元存放本空閑區(qū)長度及下個空閑區(qū)起始地址空閑區(qū)起始地址, ,把所有空閑區(qū)都鏈接起來把所有空閑區(qū)都鏈接起來, ,設置第一塊空閑區(qū)地址指針設置第一塊空閑區(qū)地址指針, ,讓它指向第讓它指向第一塊空閑區(qū)地址。一塊空閑區(qū)地址。 申請空閑區(qū)：沿鏈查找并取一個長度能滿申請空閑區(qū)：沿鏈查找并取一個長度能滿足要求的空閑區(qū)；足要求的空閑區(qū)； 歸還空閑區(qū)：把此空閑區(qū)鏈入空閑區(qū)鏈表歸還空閑區(qū)：把此空閑區(qū)鏈入空閑區(qū)鏈表的相應位置。的相應位置。17可變分區(qū)管理分配算法可變分區(qū)管理分配算法1 1）最先適應分配算法）最先適應分配算法空閑區(qū)通常按空閑區(qū)通常按地址地址從小到大排列，分配第從小到大排列，分配第一個滿足長度要求的空閑區(qū)；一個滿足長度要求的空閑區(qū)；優(yōu)點：分配從低地址開始，使高地址部分優(yōu)點：分配從低地址開始，使高地址部分比較少用，以保持一個大空閑區(qū)，有利于比較少用，以保持一個大空閑區(qū)，有利于大作業(yè)的裝入；大作業(yè)的裝入；缺點：分區(qū)利用不均衡，回收分區(qū)比較麻缺點：分區(qū)利用不均衡，回收分區(qū)比較麻煩。煩。 182 2）下次適應分配算法）下次適應分配算法1 1）的變種，每次分配時從未分配區(qū)的上次掃描）的變種，每次分配時從未分配區(qū)的上次掃描結束處順序查找。結束處順序查找?？梢越鉀Q可以解決1 1）的缺點。）的缺點。3) 3) 最優(yōu)適應分配算法最優(yōu)適應分配算法分配能滿足要求的最小區(qū)。分配能滿足要求的最小區(qū)?？梢詫⒖臻e區(qū)按照可以將空閑區(qū)按照大小大小從小到大排列，查找第一從小到大排列，查找第一個滿足要求的。個滿足要求的。優(yōu)點：主存利用率好。優(yōu)點：主存利用率好。缺點：分割剩下的空閑區(qū)比較小，難以利用；查缺點：分割剩下的空閑區(qū)比較小，難以利用；查找時間比較長。找時間比較長。194 4）最壞適應分配算法）最壞適應分配算法分配能滿足要求的最大區(qū)；分配能滿足要求的最大區(qū)；可以將空閑區(qū)按照可以將空閑區(qū)按照大小大小從大到小排列，查找第一從大到小排列，查找第一個滿足要求的。個滿足要求的。效率大致等同于最先適應法。效率大致等同于最先適應法。5) 5) 快速適應分配算法快速適應分配算法為經常用到的長度的空閑區(qū)設置單獨的鏈表。為經常用到的長度的空閑區(qū)設置單獨的鏈表。優(yōu)點：查找快速；優(yōu)點：查找快速；缺點：歸還時與相鄰空閑區(qū)的合并即復雜又費時缺點：歸還時與相鄰空閑區(qū)的合并即復雜又費時。 20下表為某系統(tǒng)中的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲管下表為某系統(tǒng)中的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲管理策略?，F(xiàn)有以下作業(yè)序列：理策略?，F(xiàn)有以下作業(yè)序列：96KB96KB，20KB20KB，200KB200KB，分別使，分別使用首次適應、最佳適用和最壞適用算法來處理這個作業(yè)序列用首次適應、最佳適用和最壞適用算法來處理這個作業(yè)序列，試問哪一種算法可以滿足該作業(yè)序列的請求，為什么？，試問哪一種算法可以滿足該作業(yè)序列的請求，為什么？分區(qū)號分區(qū)號大小大小起始地址起始地址1 132KB32KB100KB100KB2 210KB10KB150KB150KB3 35KB5KB200KB200KB4 4218KB218KB220KB220KB5 596KB96KB530KB530KB例題：例題：FF(N)FF(N)BF(Y)BF(Y)WF(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的空閑塊可以被分為兩個尺的空閑塊可以被分為兩個尺寸為寸為2 2i-1i-1的空閑塊，這兩個空閑塊稱為伙伴。的空閑塊，這兩個空閑塊稱為伙伴。 伙伴通過對大塊的物理主存劃分而獲得伙伴通過對大塊的物理主存劃分而獲得0假如從第假如從第0 0個頁面開始到第個頁面開始到第3 3個頁面結束的主存?zhèn)€頁面結束的主存0每次都對半劃分，那么第一次劃分獲得大小為每次都對半劃分，那么第一次劃分獲得大小為2 2頁的伙頁的伙伴，如伴，如0 0、1 1和和2 2、3 30進一步劃分，可以獲得大小為進一步劃分，可以獲得大小為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 1M 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 主存不足的存儲管理技術主存不足的存儲管理技術 操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)1 1空閑區(qū)空閑區(qū)作業(yè)作業(yè)2 2空閑區(qū)空閑區(qū)作業(yè)作業(yè)3 3空閑區(qū)空閑區(qū)操作系統(tǒng)操作系統(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.移動技術移動技術24有關移動問題討論有關移動問題討論 移動條件移動條件0在可變分區(qū)算法中，隨著進程不斷的裝入和撤銷，導致在可變分區(qū)算法中，隨著進程不斷的裝入和撤銷，導致主存中常常出現(xiàn)分散的小空閑區(qū)，稱為主存中常常出現(xiàn)分散的小空閑區(qū)，稱為碎片碎片。0當在未分配區(qū)中找不到足夠大的空閑區(qū)來裝入新進程時當在未分配區(qū)中找不到足夠大的空閑區(qū)來裝入新進程時，可采用移動技術，將分散的空閑區(qū)匯集成片。，可采用移動技術，將分散的空閑區(qū)匯集成片。 移動時機移動時機0進程撤銷之后釋放分區(qū)時，如果它不與空閑區(qū)鄰接，立進程撤銷之后釋放分區(qū)時，如果它不與空閑區(qū)鄰接，立即實施移動。即實施移動。0進程裝入分區(qū)時，如果它不與空閑區(qū)鄰接，立即實施引進程裝入分區(qū)時，如果它不與空閑區(qū)鄰接，立即實施引動。動。25 移動算法（假設進程移動算法（假設進程A A請求分配請求分配x KBx KB主存）主存）0步驟步驟1 1：查主存分配表，若有大于：查主存分配表，若有大于x KBx KB的空閑區(qū)，轉步的空閑區(qū)，轉步驟驟4 4；0步驟步驟2 2：若空閑區(qū)總和小于：若空閑區(qū)總和小于x KBx KB，則令進程，則令進程A A等待主存等待主存資源；資源；0步驟步驟3 3：移動主存的相關分區(qū)信息；修改主存分配表的：移動主存的相關分區(qū)信息；修改主存分配表的有關表項；修改被移動者的基礎寄存器等信息；有關表項；修改被移動者的基礎寄存器等信息；0步驟步驟4 4：分配：分配x KBx KB主存；修改主存分配表的有關項；設主存；修改主存分配表的有關項；設置進程置進程A A的基址寄存器；有申請者等待時予以釋放，算的基址寄存器；有申請者等待時予以釋放，算法結束。法結束。 開銷非常大，極少使用開銷非常大，極少使用262.2.對換技術對換技術 對換的作用對換的作用0通過將主存和磁盤的進程移出移入，解決主存通過將主存和磁盤的進程移出移入，解決主存容量不足的問題。容量不足的問題。 對換進程的選擇對換進程的選擇0選擇哪個進程換出；選擇哪個進程換出；0決定把進程的哪些信息移出去；決定把進程的哪些信息移出去；0需要確定對換時機。需要確定對換時機。 UNIXUNIX對換器對換器 WindowsWindows對換器對換器27在任何時候只在內存中保留所需的指令和數(shù)據(jù)在任何時候只在內存中保留所需的指令和數(shù)據(jù)由用戶實現(xiàn)，由用戶實現(xiàn)，讓不會同時調用的子模塊共同使用讓不會同時調用的子模塊共同使用同一內存區(qū)同一內存區(qū)F20KD22KE24KB12KC15KA30K常駐常駐A A（30KB30KB）覆蓋區(qū)覆蓋區(qū)0 0（15KB15KB）覆蓋區(qū)覆蓋區(qū)1 1（24KB24KB）A占用占用BC共用共用DEF共用共用3.3.覆蓋技術覆蓋技術28碎片碎片 外部碎片外部碎片：存在分區(qū)外，所有內存之和可以滿足：存在分區(qū)外，所有內存之和可以滿足請求，但不連續(xù)請求，但不連續(xù) 內部碎片內部碎片：存在分區(qū)內，但已不能滿足任何請求：存在分區(qū)內，但已不能滿足任何請求 解決外部碎片問題的方法解決外部碎片問題的方法0緊縮（緊縮（compactioncompaction）：移動內存內容，以便所有空閑）：移動內存內容，以便所有空閑空間合并成一整塊空間合并成一整塊0允許物理地址空間為非連續(xù)允許物理地址空間為非連續(xù)x 分頁分頁x 分段分段294.3 4.3 分頁式存儲管理分頁式存儲管理4.3.1 4.3.1 分頁式存儲管理的基本原理分頁式存儲管理的基本原理 4.3.2 4.3.2 快表快表4.3.3 4.3.3 分頁式存儲空間的分配和去配分頁式存儲空間的分配和去配4.3.4 4.3.4 分頁式存儲空間的頁面共享和保護分頁式存儲空間的頁面共享和保護4.3.5 4.3.5 多級頁表多級頁表4.3.6 4.3.6 反置頁表反置頁表304.3.1 4.3.1 分頁式存儲管理分頁式存儲管理l為什么要引進分頁技術為什么要引進分頁技術? ?l基本原理基本原理 頁面：進程邏輯地址空間分成大小相等的區(qū)；頁面：進程邏輯地址空間分成大小相等的區(qū)； 頁框（幀）：主存物理地址空間分成大小相等頁框（幀）：主存物理地址空間分成大小相等的區(qū)，其大小跟頁面大小相等；的區(qū)，其大小跟頁面大小相等； 邏輯地址形式：頁號頁內位移邏輯地址形式：頁號頁內位移 頁表和地址轉換（后面圖）頁表和地址轉換（后面圖） 基本原理基本原理(1)31基本原理基本原理(2)(2)l作業(yè)的頁面與分給的頁框如何建立聯(lián)系呢？作業(yè)的頁面與分給的頁框如何建立聯(lián)系呢？l邏輯地址邏輯地址( (頁面頁面) )如何變換成物理地址如何變換成物理地址( (頁框頁框) )呢？呢？l作業(yè)的物理地址空間由連續(xù)變成分散后，如作業(yè)的物理地址空間由連續(xù)變成分散后，如何保證程序正確執(zhí)行呢？何保證程序正確執(zhí)行呢？使用動態(tài)重定位技術，給每個頁面設立重定使用動態(tài)重定位技術，給每個頁面設立重定位寄存器，重定位寄存器的集合便稱位寄存器，重定位寄存器的集合便稱頁表頁表。頁表是操作系統(tǒng)為每個用戶作業(yè)建立的，用頁表是操作系統(tǒng)為每個用戶作業(yè)建立的，用來記錄程序頁面和主存對應頁框的對照表。來記錄程序頁面和主存對應頁框的對照表。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邏輯內存邏輯內存頁表頁表物理內存物理內存頁號頁號 幀號幀號幀號幀號物理內存和邏輯內存的分頁模型物理內存和邏輯內存的分頁模型33邏輯地址到物理地址的轉換邏輯地址到物理地址的轉換56120 1 2 3頁表頁表例：例：說明：頁大小為說明：頁大小為4B4B，頁表如圖所示，頁表如圖所示，將邏輯地址，將邏輯地址0 0、3 3、4 4、1313轉換為相轉換為相應物理地址應物理地址答案：答案：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練習：邏輯地址到物理地址的轉換練習：邏輯地址到物理地址的轉換 說明：頁大小為說明：頁大小為1024B1024B，頁表如圖所示，頁表如圖所示，將邏輯地址，將邏輯地址10111011、21482148、30003000、40004000、50125012轉換為相應物理地址轉換為相應物理地址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/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）：關聯(lián)的快速內存）：關聯(lián)的快速內存 TLBTLB與頁表一起工作與頁表一起工作0快表項包含頁號及對應的頁框號，當把頁號交給快表快表項包含頁號及對應的頁框號，當把頁號交給快表后，它通過并行匹配同時對所有快表項進行比較。后，它通過并行匹配同時對所有快表項進行比較。0如果找到，立即輸出頁框號，并形成物理地址；如果找到，立即輸出頁框號，并形成物理地址；0如果找不到，再查找主存中的頁表以形成物理地址，如果找不到，再查找主存中的頁表以形成物理地址，同時將頁號和頁框號登記到快表中；同時將頁號和頁框號登記到快表中；0當快表已滿且要登記新頁時，系統(tǒng)需要淘汰舊的快表當快表已滿且要登記新頁時，系統(tǒng)需要淘汰舊的快表項。項。36采用相聯(lián)存儲器的地址轉換采用相聯(lián)存儲器的地址轉換假定訪問主存時間為假定訪問主存時間為100100毫微秒，訪問相聯(lián)存儲器毫微秒，訪問相聯(lián)存儲器時間為時間為2020毫微秒，相聯(lián)存儲器為毫微秒，相聯(lián)存儲器為3232個單元時快表個單元時快表命中率可達命中率可達90%90%，按邏輯地址存取的平均時間為：，按邏輯地址存取的平均時間為：（1001002020）90%90%(100+100+20)(100+100+20)(1-90%)(1-90%)130130比兩次訪問主存的時間比兩次訪問主存的時間1001002 2200200下降了三成多下降了三成多。374.3.3 4.3.3 分頁式存儲空間的分配和去配分頁式存儲空間的分配和去配(1)(1) 位示圖法位示圖法0每位與一幀相對應，用每位與一幀相對應，用0/10/1表示對應塊為空閑表示對應塊為空閑/ /已占用，用另一專門字記錄當前空閑塊數(shù)。已占用，用另一專門字記錄當前空閑塊數(shù)。 鏈表方法鏈表方法0每個表項包含：每個表項包含：x進程占用區(qū)（進程占用區(qū)（P P）還是空閑區(qū)（）還是空閑區(qū)（H H）x起始地址起始地址x長度長度x指向下一表項的指針指向下一表項的指針38主存分配的位示圖和鏈表方法主存分配的位示圖和鏈表方法394.3.4 4.3.4 分頁存儲空間的頁面共享和保護分頁存儲空間的頁面共享和保護 數(shù)據(jù)共享數(shù)據(jù)共享0允許不同進程對共享的數(shù)據(jù)頁用不同的頁號，允許不同進程對共享的數(shù)據(jù)頁用不同的頁號，只要讓各自頁表中的有關表項指向共享的數(shù)據(jù)只要讓各自頁表中的有關表項指向共享的數(shù)據(jù)頁框；頁框； 程序共享程序共享0指令包含指向其它指令或數(shù)據(jù)的地址。指令包含指向其它指令或數(shù)據(jù)的地址。 標志位保護方法標志位保護方法0在頁表中增加標志位，指出此頁的信息只讀在頁表中增加標志位，指出此頁的信息只讀/ /讀寫讀寫/ /只可執(zhí)行只可執(zhí)行/ /不可訪問等。不可訪問等。 鍵保護方法鍵保護方法404.3.5 4.3.5 多級頁表多級頁表 多級頁表的概念多級頁表的概念 多級頁表的具體做法多級頁表的具體做法 邏輯地址結構邏輯地址結構 邏輯地址到物理地址轉換過程邏輯地址到物理地址轉換過程41多級頁表的概念多級頁表的概念 系統(tǒng)為每個進程建一張頁目錄表系統(tǒng)為每個進程建一張頁目錄表, ,它的每個表項它的每個表項對應一個頁表頁對應一個頁表頁, ,而頁表頁的每個表項給出了頁而頁表頁的每個表項給出了頁面和頁框的對應關系面和頁框的對應關系, ,頁目錄表是一級頁表頁目錄表是一級頁表, ,頁表頁表頁是二級頁表。頁是二級頁表。 邏輯地址結構有三部分組成：頁目錄、頁表頁和邏輯地址結構有三部分組成：頁目錄、頁表頁和位移。位移。 42多級頁表地址轉換過程多級頁表地址轉換過程 頁框號頁框號 頁內位移頁內位移 頁目錄位移頁目錄位移 頁表頁位移頁表頁位移 頁內位移頁內位移B BF F進程一級頁表進程一級頁表進程二級頁表進程二級頁表物理地址物理地址邏輯地址邏輯地址頁目錄表頁目錄表控制寄存器控制寄存器43解決頁表頁占用主存空間的問題解決頁表頁占用主存空間的問題 進程運行涉及頁面的頁表頁應放在主存進程運行涉及頁面的頁表頁應放在主存, ,其其他頁表頁使用時再調入他頁表頁使用時再調入, , 在頁目錄表中增加特征位在頁目錄表中增加特征位, ,指示對應的頁表指示對應的頁表頁是否已調入主存頁是否已調入主存, , 地址轉換機構根據(jù)邏輯地址中的地址轉換機構根據(jù)邏輯地址中的dir,dir,去查去查頁目錄表對應表項頁目錄表對應表項, ,如未調入如未調入, ,應產生一個應產生一個”缺頁表頁缺頁表頁”中斷信號，請求操作系統(tǒng)將中斷信號，請求操作系統(tǒng)將頁表頁調入主存。頁表頁調入主存。444.3.5 4.3.5 反置頁表反置頁表(1)(1) 頁框號頁框號 位移位移進程標識進程標識 頁號頁號 位移位移 進程標識進程標識 頁號頁號 特征位特征位 鏈指針鏈指針 序號序號反置頁表反置頁表物理地址物理地址邏輯地址邏輯地址哈希哈希函數(shù)函數(shù)哈希表哈希表反置頁表及其地址轉換反置頁表及其地址轉換45反置頁表反置頁表(2)(2) IPTIPT是為主存中的每一個物理塊建立一個頁是為主存中的每一個物理塊建立一個頁表并按照塊號排序表并按照塊號排序, , 該表每個表項包含正在訪問該頁框的進程該表每個表項包含正在訪問該頁框的進程標識、頁號及特征位、哈希鏈指針標識、頁號及特征位、哈希鏈指針, ,用來完用來完成邏輯地址到物理地址的轉換。成邏輯地址到物理地址的轉換。46反置頁表反置頁表(3)(3)反置頁表地址轉換過程如下反置頁表地址轉換過程如下: :邏輯地址給出進程標識和頁號邏輯地址給出進程標識和頁號, ,用它們去比較用它們去比較IPT,IPT,若整個反置頁表中未能找到匹配的頁表項若整個反置頁表中未能找到匹配的頁表項, ,說明該頁不在主存說明該頁不在主存, ,產生請頁中斷產生請頁中斷, ,請求操作系統(tǒng)請求操作系統(tǒng)調入調入; ;否則，該表項的序號便是頁框號否則，該表項的序號便是頁框號, ,塊號加上塊號加上位移位移, ,便形成物理地址。便形成物理地址。47 分頁技術分頁技術不會不會產生產生外部碎片外部碎片，但，但會會產生產生內內部碎片部碎片 分頁的重要特點是用戶觀點的內存和實際分頁的重要特點是用戶觀點的內存和實際的物理內存的分離的物理內存的分離 分頁可以共享共同代碼分頁可以共享共同代碼分頁內存管理方案小結分頁內存管理方案小結484.4 4.4 分段式存儲管理分段式存儲管理4.4.1 4.4.1 程序的分段結構程序的分段結構4.4.2 4.4.2 分段式存儲管理的基本原理分段式存儲管理的基本原理4.4.3 4.4.3 段的共享和保護段的共享和保護4.4.4 4.4.4 分段和分頁的比較分段和分頁的比較494.4.1 4.4.1 程序的分段結構程序的分段結構 分段存儲管理引入的主要原因分段存儲管理引入的主要原因0滿足用戶（程序員）編程和使用上的要求。滿足用戶（程序員）編程和使用上的要求。 模塊化程序設計的分段結構（下頁圖）模塊化程序設計的分段結構（下頁圖） 分頁存儲管理分頁存儲管理-一維地址結構一維地址結構 分段存儲管理分段存儲管理-二維地址結構二維地址結構50模塊化程序設計的分段結構模塊化程序設計的分段結構 子程序段子程序段X X數(shù)組段數(shù)組段A Acall Xcall X( (調用調用X X段的入口段的入口E)E)call Ycall Y( (調用調用Y Y段的入口段的入口F)F)load 1,Aload 1,A ( (調用數(shù)組段調用數(shù)組段AG)AG)主程序段主程序段E E：F F：子程序段子程序段Y YG G：工作區(qū)段工作區(qū)段514.4.2 4.4.2 分段式存儲管理的基本原理分段式存儲管理的基本原理(1)(1)l二維邏輯地址二維邏輯地址l段號：段內地址段號：段內地址l段表段表l段表指出主存中各分段的段號、段起始地址和段表指出主存中各分段的段號、段起始地址和段長度，起到基址段長度，起到基址/ /限長寄存器的作用。限長寄存器的作用。l段式存儲管理的地址轉換和存儲保護段式存儲管理的地址轉換和存儲保護 52分段式存儲管理的基本原理分段式存儲管理的基本原理(2)(2) 段控制寄存器段控制寄存器 段表始址段表始址 段表長度段表長度 段號段號s s 位移位移d d 段長段長 基址基址 物理地址物理地址越界越界? ? 段表段表53段表：將二維的邏輯地址映射為一維物理地址段表：將二維的邏輯地址映射為一維物理地址段基地址：包含該段在內存中的開始物理地址段基地址：包含該段在內存中的開始物理地址段界限：指定該段的長度段界限：指定該段的長度邏輯地址：段號邏輯地址：段號s s段內偏移段內偏移d d邏輯地址到物理地址的轉換邏輯地址到物理地址的轉換1)1) 段號與段表長度進行比較，若段號超過了段表長度段號與段表長度進行比較，若段號超過了段表長度，則越界（非法地址），否則轉，則越界（非法地址），否則轉2 2）2)2) 根據(jù)段表始址和段號計算出該段對應段表項的位置根據(jù)段表始址和段號計算出該段對應段表項的位置，從中讀出該段在內存的起始地址，檢查段內地址，從中讀出該段在內存的起始地址，檢查段內地址是否超過該段的段長，若超過則越界（非法地址）是否超過該段的段長，若超過則越界（非法地址），否則轉，否則轉3 3）3)3) 將該段的起始地址與段內位移相加，從而得到要訪將該段的起始地址與段內位移相加，從而得到要訪問的物理地址問的物理地址邏輯地址到物理地址轉換邏輯地址到物理地址轉換54邏輯地址到物理地址轉換例邏輯地址到物理地址轉換例說明：段表如表說明：段表如表1 1所示，將表所示，將表2 2所示邏輯地址轉換為相應所示邏輯地址轉換為相應物理地址物理地址答案：見表答案：見表3 3段號段號 內存起始內存起始地址地址段長段長0 02192196006001 12300230014142 290901001003 3132713275805804 4195219529696段段號號段內位段內位移移2 288884 4100100178178非法非法 表表1 表表2 表表390+881009655說明：段表如表說明：段表如表1 1所示，將表所示，將表2 2所示邏輯地址轉換為相應所示邏輯地址轉換為相應物理地址物理地址答案：見表答案：見表3 3邏輯地址到物理地址轉換練習邏輯地址到物理地址轉換練習段號段號段內位移段內位移0 04304301 110102 25005003 34004004 41121125 53232段號段號內存起始地址內存起始地址段長段長0 02102105005001 12350235020202 210010090903 3135013505905904 4193819389595 表表1 表表264064023602360非法非法17501750非法非法非法非法表表3210+4302350+10500901350+40011295段號段號5不存在不存在564.4.3 4.4.3 段的共享段的共享 多對基址多對基址/ /限長寄存器限長寄存器 段的共享，是通過不同作業(yè)段表中的項指段的共享，是通過不同作業(yè)段表中的項指向同一個段基址來實現(xiàn)。向同一個段基址來實現(xiàn)。 幾道作業(yè)共享的例行程序就可放在一個段幾道作業(yè)共享的例行程序就可放在一個段中，只要讓各道作業(yè)的共享部分有相同的中，只要讓各道作業(yè)的共享部分有相同的基址基址/ /限長值。限長值。 對共享段的信息必須進行保護。對共享段的信息必須進行保護。 574.4.4 4.4.4 分段和分頁的比較分段和分頁的比較(1)(1) 分段是信息的邏輯單位，由源程序的邏輯分段是信息的邏輯單位，由源程序的邏輯結構所決定，用戶可見，結構所決定，用戶可見， 段長可根據(jù)用戶需要來規(guī)定，段起始地址段長可根據(jù)用戶需要來規(guī)定，段起始地址可從任何主存地址開始?？蓮娜魏沃鞔娴刂烽_始。 分段方式中，源程序分段方式中，源程序( (段號，段內位移段號，段內位移) )經經連結裝配后地址仍保持二維結構。連結裝配后地址仍保持二維結構。58分段和分頁的比較分段和分頁的比較(2)(2) 分頁是信息的物理單位，與源程序的邏輯分頁是信息的物理單位，與源程序的邏輯結構無關，用戶不可見，結構無關，用戶不可見， 頁長由系統(tǒng)確定，頁面只能以頁大小的整頁長由系統(tǒng)確定，頁面只能以頁大小的整倍數(shù)地址開始。倍數(shù)地址開始。 分頁方式中，源程序分頁方式中，源程序( (頁號，頁內位移頁號，頁內位移) )經經連結裝配后地址變成了一維結構。連結裝配后地址變成了一維結構。594.5 4.5 虛擬存儲管理虛擬存儲管理4.5.1 4.5.1 虛擬存儲管理的概念虛擬存儲管理的概念4.5.2 4.5.2 請求分頁虛擬存儲管理請求分頁虛擬存儲管理4.5.3 4.5.3 請求分段虛擬存儲管理請求分段虛擬存儲管理4.5.4 4.5.4 請求段頁式虛擬存儲管理請求段頁式虛擬存儲管理604.5.1 4.5.1 虛擬存儲管理的概念虛擬存儲管理的概念 虛擬內存（虛擬內存（virtual memoryvirtual memory）：允許進程的執(zhí)行）：允許進程的執(zhí)行不必完全在內存中，程序可以比物理內存大。不必完全在內存中，程序可以比物理內存大。 在許多情況下不需要將整個程序放到內存中：在許多情況下不需要將整個程序放到內存中：0處理異常錯誤條件的代碼（幾乎不執(zhí)行）處理異常錯誤條件的代碼（幾乎不執(zhí)行）0數(shù)組、鏈表和表通常分配了比實際所需更多的內存數(shù)組、鏈表和表通常分配了比實際所需更多的內存0程序的某些選項或特點可能很少使用程序的某些選項或特點可能很少使用 能夠執(zhí)行只有部分在內存中的程序的好處能夠執(zhí)行只有部分在內存中的程序的好處0程序不再受現(xiàn)有的物理內存空間限制程序不再受現(xiàn)有的物理內存空間限制0更多程序可同時執(zhí)行，更多程序可同時執(zhí)行，CPUCPU利用率相應增加利用率相應增加0用戶程序會運行的更快用戶程序會運行的更快61虛擬存儲器虛擬存儲器 虛擬存儲器的定義：虛擬存儲器的定義：0在具有層次結構存儲器的計算機系統(tǒng)中在具有層次結構存儲器的計算機系統(tǒng)中，采用自動實現(xiàn)部分裝入和部分對換功，采用自動實現(xiàn)部分裝入和部分對換功能，為用戶提供一個比物理主存容量大能，為用戶提供一個比物理主存容量大得多的，可尋址的一種得多的，可尋址的一種“主存儲器主存儲器”。 62虛擬存儲器的概念圖虛擬存儲器的概念圖 邏輯地址空間邏輯地址空間處理器處理器虛地址虛地址存儲存儲管理管理部件部件實地址實地址主存主存輔存輔存物理地址空間物理地址空間63程序的局部性原理程序的局部性原理 指程序在執(zhí)行過程中的一個較短時間內，所指程序在執(zhí)行過程中的一個較短時間內，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲區(qū)域中。又可細分時間局部性和空定的存儲區(qū)域中。又可細分時間局部性和空間局部性。間局部性。時間局部性：最近訪問過的程序代碼和數(shù)據(jù)很時間局部性：最近訪問過的程序代碼和數(shù)據(jù)很快又被訪問。快又被訪問。空間局部性：某存儲單元被使用之后，其相鄰空間局部性：某存儲單元被使用之后，其相鄰的存儲單元也很快被使用。的存儲單元也很快被使用。64實現(xiàn)虛擬存儲器須解決的問題實現(xiàn)虛擬存儲器須解決的問題l 主存輔存統(tǒng)一管理問題主存輔存統(tǒng)一管理問題l 邏輯地址到物理地址的轉換問題邏輯地址到物理地址的轉換問題l 部分裝入和部分對換問題部分裝入和部分對換問題65虛擬存儲管理實現(xiàn)技術虛擬存儲管理實現(xiàn)技術l 請求分頁虛擬存儲管理請求分頁虛擬存儲管理l 請求分段虛擬存儲管理請求分段虛擬存儲管理l 請求段頁式虛擬存儲管理請求段頁式虛擬存儲管理664.5.2 4.5.2 請求分頁虛擬存儲系統(tǒng)請求分頁虛擬存儲系統(tǒng)1.1.請求分頁虛擬存儲系統(tǒng)的硬件支撐請求分頁虛擬存儲系統(tǒng)的硬件支撐(1)(1)主存管理單元主存管理單元MMUMMU完成邏輯地址到物理地址完成邏輯地址到物理地址的轉換功能，它接受虛擬地址作為輸入，的轉換功能，它接受虛擬地址作為輸入，物理地址作為輸出，直接送到總線上，對物理地址作為輸出，直接送到總線上，對主存單元進行尋址。主存單元進行尋址。 67MMUMMU主要功能主要功能(1)(1)管理硬件頁表基址寄存器。管理硬件頁表基址寄存器。(2)(2)分解邏輯地址。分解邏輯地址。(3)(3)管理快管理快表表TLBTLB。(4)(4)訪問頁表。訪問頁表。(5)(5)發(fā)出缺頁中斷或越界中斷，并將控制權交給內發(fā)出缺頁中斷或越界中斷，并將控制權交給內核存儲管理處理。核存儲管理處理。(6)(6)設置和檢查頁表中各個特征位。設置和檢查頁表中各個特征位。682.2.請求分頁虛擬存儲系統(tǒng)的基本原理請求分頁虛擬存儲系統(tǒng)的基本原理 分頁式虛存不把作業(yè)信息分頁式虛存不把作業(yè)信息( (程序和數(shù)據(jù)程序和數(shù)據(jù)) )全部裝入全部裝入主存，僅裝入立即使用的頁面，在執(zhí)行過程中訪主存，僅裝入立即使用的頁面，在執(zhí)行過程中訪問到不在主存的頁面時，產生缺頁中斷，再從磁問到不在主存的頁面時，產生缺頁中斷，再從磁盤動態(tài)地裝入盤動態(tài)地裝入 。 怎樣才能發(fā)現(xiàn)頁面不在主存中呢怎樣才能發(fā)現(xiàn)頁面不在主存中呢? ?怎樣處理這種怎樣處理這種情況呢情況呢? ?0采用的辦法是：擴充頁表的內容采用的辦法是：擴充頁表的內容, ,增加駐留標志位和頁增加駐留標志位和頁面輔存的地址等信息面輔存的地址等信息。69頁式虛擬存儲管理頁表擴展頁式虛擬存儲管理頁表擴展其它標志：其它標志： 訪問權限位訪問權限位 修改位（修改位（ModifiedModified） 引用位（引用位（RenferencedRenferenced）頁號頁號 駐留標志駐留標志 頁框號頁框號 輔存地址輔存地址 其它標志其它標志70請求分頁虛存地址轉換過程請求分頁虛存地址轉換過程查快表查快表有登記有登記無登記無登記查頁表查頁表登記入快表登記入快表發(fā)缺頁中斷發(fā)缺頁中斷在主存在主存在輔存在輔存形成絕對地址形成絕對地址繼續(xù)執(zhí)行指令繼續(xù)執(zhí)行指令重新執(zhí)行重新執(zhí)行被中斷指令被中斷指令恢復現(xiàn)場恢復現(xiàn)場調整頁表和調整頁表和主存分配表主存分配表裝入所需頁面裝入所需頁面主存有空閑塊主存有空閑塊保護現(xiàn)場保護現(xiàn)場有有選擇調出頁面選擇調出頁面該頁是否修改該頁是否修改未修改未修改已修改已修改把該頁寫回把該頁寫回輔存相應位置輔存相應位置操作系統(tǒng)操作系統(tǒng)硬件硬件邏輯地址邏輯地址無無71請求頁式虛擬存儲系統(tǒng)優(yōu)缺點請求頁式虛擬存儲系統(tǒng)優(yōu)缺點l優(yōu)點：作業(yè)的程序和數(shù)據(jù)可按頁分散存放優(yōu)點：作業(yè)的程序和數(shù)據(jù)可按頁分散存放在主存中，減少移動開銷，有效解決了碎在主存中，減少移動開銷，有效解決了碎片問題片問題; ;既有利于改進主存利用率，又有利既有利于改進主存利用率，又有利于多道程序運行。于多道程序運行。l缺點：要有硬件支持，要進行缺頁中斷處缺點：要有硬件支持，要進行缺頁中斷處理，機器成本增加，系統(tǒng)開銷加大。理，機器成本增加，系統(tǒng)開銷加大。723.3.頁面裝入策略和頁面清除策略頁面裝入策略和頁面清除策略l頁面裝入主存頁面裝入主存, ,有兩種策略：有兩種策略：l請頁式調度：僅調入所需頁面請頁式調度：僅調入所需頁面l預調式調度：使用前預先調入若干頁預調式調度：使用前預先調入若干頁l何時把一個修改過的頁面寫回輔存儲器，何時把一個修改過的頁面寫回輔存儲器，有兩種策略：有兩種策略：l請頁式清除：僅當一頁被選中進行替換且被請頁式清除：僅當一頁被選中進行替換且被修改過，才寫回磁盤。修改過，才寫回磁盤。l預清除：成批進行，所有預清除：成批進行，所有 被更改過的頁面，被更改過的頁面，在需要替換前把它們都寫回磁盤。在需要替換前把它們都寫回磁盤。734.4.頁面分配策略頁面分配策略 系統(tǒng)為進程分配主存系統(tǒng)為進程分配主存, ,需考慮因素需考慮因素: :分給進程的空間越小分給進程的空間越小, ,同一時間處于主存的進程同一時間處于主存的進程就越多，至少有一個進程處于就緒態(tài)的可能性就就越多，至少有一個進程處于就緒態(tài)的可能性就越大越大如果進程只有小部分在主存里如果進程只有小部分在主存里, ,即使局部性很好即使局部性很好, ,缺頁中斷率還會相當大缺頁中斷率還會相當大因程序的局部性原理，分給進程的主存超過一定因程序的局部性原理，分給進程的主存超過一定限度后，再增加主存空間限度后，再增加主存空間, ,不會明顯降低進程的不會明顯降低進程的缺頁中斷率缺頁中斷率。74頁面分配策略：固定分配頁面分配策略：固定分配 進程保持頁框數(shù)固定不變進程保持頁框數(shù)固定不變, ,稱固定分配稱固定分配; ; 進程創(chuàng)建時進程創(chuàng)建時, ,根據(jù)進程類型和程序員的要求根據(jù)進程類型和程序員的要求決定頁框數(shù)決定頁框數(shù), ,只要有一個缺頁中斷產生只要有一個缺頁中斷產生, ,進進程就會有一頁被替換。程就會有一頁被替換。75頁面分配策略：可變分配頁面分配策略：可變分配 進程分得的頁框數(shù)可變進程分得的頁框數(shù)可變, , 稱可變分配稱可變分配; ; 進程執(zhí)行的某階段缺頁率較高進程執(zhí)行的某階段缺頁率較高, ,說明目前說明目前局部性較差，系統(tǒng)可多分些頁框以降低缺局部性較差，系統(tǒng)可多分些頁框以降低缺頁率，反之說明進程目前的局部性較好頁率，反之說明進程目前的局部性較好, ,可減少分給進程的頁框數(shù)可減少分給進程的頁框數(shù)76頁面替換策略：局部替換和全局替換頁面替換策略：局部替換和全局替換 如果頁面替換算法的作用范圍是整個系統(tǒng)如果頁面替換算法的作用范圍是整個系統(tǒng)，稱全局頁面替換算法，稱全局頁面替換算法, ,它可以在運行進程它可以在運行進程間動態(tài)地分配頁框。間動態(tài)地分配頁框。 如果頁面替換算法的作用范圍局限于本進如果頁面替換算法的作用范圍局限于本進程，稱為局部頁面替換算法程，稱為局部頁面替換算法, ,它實際上需要它實際上需要為每個進程分配固定的頁框。為每個進程分配固定的頁框。 77固定分配和局部替換策略配合使用固定分配和局部替換策略配合使用(1)(1)l 進程分得的頁框數(shù)不變，發(fā)生缺頁中斷，進程分得的頁框數(shù)不變，發(fā)生缺頁中斷，只能從進程的頁面中選頁替換，保證進程只能從進程的頁面中選頁替換，保證進程的頁框總數(shù)不變。的頁框總數(shù)不變。l策略難點：應給每個進程分配多少頁框策略難點：應給每個進程分配多少頁框? ?給給少了少了, ,缺頁中斷率高缺頁中斷率高; ;給多了給多了, ,使主存中能同使主存中能同時執(zhí)行的進程數(shù)減少，進而造成處理器和時執(zhí)行的進程數(shù)減少，進而造成處理器和其它設備空閑。其它設備空閑。78固定分配和局部替換策略配合使用固定分配和局部替換策略配合使用(2)(2)采用固定分配算法，系統(tǒng)把頁框分配給進采用固定分配算法，系統(tǒng)把頁框分配給進程，采用：程，采用：平均分配平均分配按比例分配按比例分配優(yōu)先權分配優(yōu)先權分配79可變分配和全局替換策略配合使用可變分配和全局替換策略配合使用l先每個進程分配一定數(shù)目頁先每個進程分配一定數(shù)目頁框框,os,os保留若干空閑保留若干空閑頁框頁框, ,進程發(fā)生缺頁中斷時，從系統(tǒng)空閑頁框中進程發(fā)生缺頁中斷時，從系統(tǒng)空閑頁框中選一個給進程選一個給進程, ,這樣產生缺頁中斷進程的主存空這樣產生缺頁中斷進程的主存空間會逐漸增大間會逐漸增大, ,有助于減少系統(tǒng)的缺頁中斷次數(shù)有助于減少系統(tǒng)的缺頁中斷次數(shù)。l系統(tǒng)擁有的空閑頁框耗盡時系統(tǒng)擁有的空閑頁框耗盡時 ，會從主存中選擇，會從主存中選擇一頁淘汰，該頁可以是主存中任一進程的頁面，一頁淘汰，該頁可以是主存中任一進程的頁面，這樣又會使那個進程的頁框數(shù)減少，缺頁中斷率這樣又會使那個進程的頁框數(shù)減少，缺頁中斷率上升。上升。80可變分配和局部替換配合使用可變分配和局部替換配合使用其實現(xiàn)要點如下其實現(xiàn)要點如下: :(1)(1)新進程裝入主存時，根據(jù)應用類型、程序要求新進程裝入主存時，根據(jù)應用類型、程序要求，分配給一定數(shù)目頁框，分配給一定數(shù)目頁框, ,可用請頁式或預調式完可用請頁式或預調式完成這個分配。成這個分配。(2)(2)產生缺頁中斷時產生缺頁中斷時, ,從該進程駐留集中選一個頁面從該進程駐留集中選一個頁面替換。替換。(3)(3)不時重新評價進程的分配，增加或減少分配給不時重新評價進程的分配，增加或減少分配給進程的頁框以改善系統(tǒng)性能。進程的頁框以改善系統(tǒng)性能。815.5.缺頁中斷率缺頁中斷率l頁面替換頁面替換l當主存空間已滿又必須裝入新頁時，選擇主存當主存空間已滿又必須裝入新頁時，選擇主存中某頁淘汰。中某頁淘汰。l頁面淘汰算法頁面淘汰算法l選擇哪頁被淘汰的算法。選擇哪頁被淘汰的算法。l“抖動抖動”(Thrashing)(Thrashing)現(xiàn)象現(xiàn)象l剛被淘汰的頁面立即又要調用，調入不久又被剛被淘汰的頁面立即又要調用，調入不久又被淘汰，淘汰不久再被調入淘汰，淘汰不久再被調入如此反復，整個系如此反復，整個系統(tǒng)頻繁調頁，使得幾乎無時間進行計算任務。統(tǒng)頻繁調頁，使得幾乎無時間進行計算任務。82影響缺頁中斷率的因素影響缺頁中斷率的因素(1) 假定作業(yè)假定作業(yè)p p共計共計n n頁，系統(tǒng)分配給它的主存頁，系統(tǒng)分配給它的主存塊只有塊只有m m塊（塊（mnmn）。如果作業(yè)）。如果作業(yè)p p在運在運行中成功的訪問次數(shù)為行中成功的訪問次數(shù)為S S， 不成功的訪問不成功的訪問次數(shù)為次數(shù)為F F，則總的訪問次數(shù)為：，則總的訪問次數(shù)為：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) 先進先出頁面替換算法先進先出頁面替換算法FIFO FIFO 3) 3) 最近最少用頁面替換算法最近最少用頁面替換算法LRU LRU 4) 4) 第二次機會頁面替換算法第二次機會頁面替換算法SCR SCR 5) 5) 時鐘頁面替換算法時鐘頁面替換算法ClockClock注：所有算法例子中采用請頁時調度，即最注：所有算法例子中采用請頁時調度，即最初假設主存中沒有頁面。初假設主存中沒有頁面。 851)1)最佳替換算法最佳替換算法 調入一頁而必須淘汰一個舊頁時，所淘汰調入一頁而必須淘汰一個舊頁時，所淘汰的頁應該是以后不再訪問的頁或距現(xiàn)在最的頁應該是以后不再訪問的頁或距現(xiàn)在最長時間后再訪問的頁。長時間后再訪問的頁。 OPTOPT算法（算法（OptimalOptimal） ，可用來作為衡量各，可用來作為衡量各種具體算法的標準種具體算法的標準。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)先進先出頁面替換算法先進先出頁面替換算法 基于程序總是按線性順序來訪問物理空間基于程序總是按線性順序來訪問物理空間這一假設。這一假設。 算法總是淘汰最先調入主存的那一頁，或算法總是淘汰最先調入主存的那一頁，或者說在主存中駐留時間最長的那一頁（常者說在主存中駐留時間最長的那一頁（常駐的除外）。駐的除外）。 實現(xiàn)技術實現(xiàn)技術 (1)(1)設置具有設置具有m m個元素的頁號表，控制換頁個元素的頁號表，控制換頁 (2)(2)引入指針鏈成隊列引入指針鏈成隊列88FIFOFI