存儲管理_17667

1、存儲管理存儲管理n存儲體系存儲體系n存儲管理的任務(wù)存儲管理的任務(wù)n分區(qū)存儲管理分區(qū)存儲管理n頁式存儲管理頁式存儲管理n交換技術(shù)與覆蓋技術(shù)交換技術(shù)與覆蓋技術(shù)n虛擬存儲虛擬存儲一、存儲體系一、存儲體系存儲系統(tǒng)設(shè)計三個問題：存儲系統(tǒng)設(shè)計三個問題： 容量、速度和成本容量、速度和成本n容量：需求無止境容量：需求無止境n速度：能匹配處理器的速度速度：能匹配處理器的速度n成本問題：成本和其它部件相比應(yīng)在合成本問題：成本和其它部件相比應(yīng)在合適范圍之內(nèi)適范圍之內(nèi)層次化的存儲體系結(jié)構(gòu)層次化的存儲體系結(jié)構(gòu)存儲體系存儲體系操作系統(tǒng)協(xié)調(diào)各存儲器的使用操作系統(tǒng)協(xié)調(diào)各存儲器的使用 重要性：直接存取要求內(nèi)存速度盡量快到重要性

2、：直接存取要求內(nèi)存速度盡量快到與與CPU取指速度相匹配，大到能裝下當取指速度相匹配，大到能裝下當前運行的程序與數(shù)據(jù)，否則前運行的程序與數(shù)據(jù)，否則CPU執(zhí)行速執(zhí)行速度就會受到內(nèi)存速度和容量的影響而得度就會受到內(nèi)存速度和容量的影響而得不到充分發(fā)揮不到充分發(fā)揮內(nèi)存內(nèi)存 由存儲單元（字節(jié)或字）組成的一維連續(xù)由存儲單元（字節(jié)或字）組成的一維連續(xù)的地址空間，簡稱內(nèi)存空間。用來存放當?shù)牡刂房臻g，簡稱內(nèi)存空間。用來存放當前正在運行程序的代碼及數(shù)據(jù)，是程序中前正在運行程序的代碼及數(shù)據(jù)，是程序中指令本身地址所指的、亦即程序計數(shù)器所指令本身地址所指的、亦即程序計數(shù)器所指的存儲器指的存儲器分為：分為：n系統(tǒng)區(qū)：用于存

3、放操作系統(tǒng)系統(tǒng)區(qū)：用于存放操作系統(tǒng)n用戶區(qū)：用于裝入并存放用戶程序和數(shù)據(jù)用戶區(qū)：用于裝入并存放用戶程序和數(shù)據(jù) 二、存儲管理的任務(wù)二、存儲管理的任務(wù)（1）內(nèi)存空間的管理、分配與回收）內(nèi)存空間的管理、分配與回收n記錄內(nèi)存的使用情況記錄內(nèi)存的使用情況 設(shè)置相應(yīng)的內(nèi)存分配表設(shè)置相應(yīng)的內(nèi)存分配表 （內(nèi)存分配回收的依據(jù)）（內(nèi)存分配回收的依據(jù)）n 內(nèi)存空間劃分問題？內(nèi)存空間劃分問題？ 靜態(tài)或動態(tài)，等長或不等長靜態(tài)或動態(tài)，等長或不等長存儲管理的任務(wù)（續(xù)存儲管理的任務(wù)（續(xù)1）n內(nèi)存分配表內(nèi)存分配表n位示圖：位示圖：用一位（用一位（bitbit）表示一個空閑頁面（表示一個空閑頁面（0 0：空閑，空閑，1 1：占用

4、）：占用）n空閑頁面表：包括首頁面號和頁面?zhèn)€數(shù)，連續(xù)空閑頁面表：包括首頁面號和頁面?zhèn)€數(shù)，連續(xù)若干的頁面作為一組登記在表中若干的頁面作為一組登記在表中n空閑塊表：空閑塊首址和空閑塊長度，沒有記空閑塊表：空閑塊首址和空閑塊長度，沒有記錄的區(qū)域即為進程所占用錄的區(qū)域即為進程所占用n空閑塊鏈表：將所有的空閑塊鏈成一個鏈表空閑塊鏈表：將所有的空閑塊鏈成一個鏈表0.110.第第0頁第頁第1頁頁 第第i頁頁 第第n-1頁頁存儲管理的任務(wù)（續(xù)存儲管理的任務(wù)（續(xù)2）n確定分配算法確定分配算法 連續(xù)性連續(xù)性 離散性離散性 駐留性駐留性 交換性交換性 一次性一次性 多次性多次性n實施內(nèi)存分配實施內(nèi)存分配n內(nèi)存回收內(nèi)

5、存回收n內(nèi)存分配：靜態(tài)方式內(nèi)存分配：靜態(tài)方式 與與 動態(tài)方式動態(tài)方式存儲管理的任務(wù)（續(xù)存儲管理的任務(wù)（續(xù)3）（2）存儲共享）存儲共享 兩個或多個進程兩個或多個進程共用內(nèi)存中相同區(qū)域共用內(nèi)存中相同區(qū)域 目的：目的： 節(jié)省內(nèi)存空間，提高內(nèi)存利用率節(jié)省內(nèi)存空間，提高內(nèi)存利用率 實現(xiàn)進程通信（數(shù)據(jù)共享）實現(xiàn)進程通信（數(shù)據(jù)共享） 共享內(nèi)容：共享內(nèi)容： 代碼共享，要求代碼為純代碼代碼共享，要求代碼為純代碼 數(shù)據(jù)共享數(shù)據(jù)共享存儲管理的任務(wù)（續(xù)存儲管理的任務(wù)（續(xù)4）（3）存儲保護）存儲保護 為多個程序共享內(nèi)存提供保障，使在內(nèi)存中為多個程序共享內(nèi)存提供保障，使在內(nèi)存中的各道程序，的各道程序，只能訪問它自己的區(qū)域

6、只能訪問它自己的區(qū)域，避免，避免各道程序間相互干擾，特別是當一道程序發(fā)各道程序間相互干擾，特別是當一道程序發(fā)生錯誤時，不致于影響其他程序的運行生錯誤時，不致于影響其他程序的運行 通常由硬件完成保護功能，由軟件輔助實現(xiàn)通常由硬件完成保護功能，由軟件輔助實現(xiàn)存儲管理的任務(wù)（續(xù)存儲管理的任務(wù)（續(xù)5）保護過程保護過程-防止地址越界防止地址越界 每個進程都有自己獨立的進程空間，如果一個進程每個進程都有自己獨立的進程空間，如果一個進程在運行時所產(chǎn)生的地址在其地址空間之外，則發(fā)生在運行時所產(chǎn)生的地址在其地址空間之外，則發(fā)生地址越界。即當程序要訪問某個內(nèi)存單元時，由硬地址越界。即當程序要訪問某個內(nèi)存單元時，由

7、硬件檢查是否允許，如果允許則執(zhí)行，否則產(chǎn)生地址件檢查是否允許，如果允許則執(zhí)行，否則產(chǎn)生地址越界中斷，由操作系統(tǒng)進行相應(yīng)處理越界中斷，由操作系統(tǒng)進行相應(yīng)處理一般由硬件提供一對寄存器：一般由硬件提供一對寄存器： 基址寄存器：存放起始地址基址寄存器：存放起始地址 限長寄存器：存放長度限長寄存器：存放長度 （或（或 上界寄存器上界寄存器/下界寄存器）下界寄存器）存儲管理的任務(wù)（續(xù)存儲管理的任務(wù)（續(xù)6）保護過程保護過程-防止操作越權(quán)防止操作越權(quán) 對于允許多個進程共享的存儲區(qū)域，每個進程都有對于允許多個進程共享的存儲區(qū)域，每個進程都有自己的訪問權(quán)限。如果一個進程對共享區(qū)域的訪問自己的訪問權(quán)限。如果一個進程

8、對共享區(qū)域的訪問違反了權(quán)限規(guī)定，則發(fā)生操作越權(quán)違反了權(quán)限規(guī)定，則發(fā)生操作越權(quán) 即讀寫保護即讀寫保護 存儲管理的任務(wù)（續(xù)存儲管理的任務(wù)（續(xù)7）（4）內(nèi)存擴充）內(nèi)存擴充 通過通過虛擬存儲技術(shù)虛擬存儲技術(shù)實現(xiàn)實現(xiàn) 用戶在編制程序時，不應(yīng)該受內(nèi)存容量限用戶在編制程序時，不應(yīng)該受內(nèi)存容量限制，所以要采用一定技術(shù)來制，所以要采用一定技術(shù)來“擴充擴充”內(nèi)存的內(nèi)存的容量，使用戶得到比實際內(nèi)存容量大的多的容量，使用戶得到比實際內(nèi)存容量大的多的內(nèi)存空間內(nèi)存空間 具體實現(xiàn)是在硬件支持下，軟硬件相互協(xié)具體實現(xiàn)是在硬件支持下，軟硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來統(tǒng)一使用作，將內(nèi)存和外存結(jié)合起來統(tǒng)一使用存儲管理的任務(wù)（續(xù)

9、存儲管理的任務(wù)（續(xù)8）（5）地址轉(zhuǎn)換）地址轉(zhuǎn)換 又稱地址重定位、地址映射又稱地址重定位、地址映射 n邏輯地址（相對地址，虛地址）邏輯地址（相對地址，虛地址）n物理地址（絕對地址，實地址）物理地址（絕對地址，實地址）n地址映射地址映射存儲管理的任務(wù)（續(xù)存儲管理的任務(wù)（續(xù)9）n邏輯地址（相對地址，虛地址）邏輯地址（相對地址，虛地址） 用戶的程序經(jīng)過匯編或編譯后形成目標代碼，用戶的程序經(jīng)過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的形式，其首地目標代碼通常采用相對地址的形式，其首地址為址為0，其余指令中的地址都相對于首地址，其余指令中的地址都相對于首地址而編址而編址 不能用邏輯地址在內(nèi)存中讀

10、取信息不能用邏輯地址在內(nèi)存中讀取信息n物理地址（絕對地址，實地址）物理地址（絕對地址，實地址） 內(nèi)存中存儲單元的地址，可直接尋址內(nèi)存中存儲單元的地址，可直接尋址存儲管理的任務(wù)（續(xù)存儲管理的任務(wù)（續(xù)10）n地址轉(zhuǎn)換地址轉(zhuǎn)換 為了保證為了保證CPU執(zhí)行指令時可正確訪問存儲單執(zhí)行指令時可正確訪問存儲單元，需將用戶程序中的邏輯地址轉(zhuǎn)換為運行元，需將用戶程序中的邏輯地址轉(zhuǎn)換為運行時由機器直接尋址的物理地址，這一過程稱時由機器直接尋址的物理地址，這一過程稱為地址映射為地址映射原因原因: 當程序裝入內(nèi)存時當程序裝入內(nèi)存時, 操作系統(tǒng)要為該程序分配操作系統(tǒng)要為該程序分配一個合適的內(nèi)存空間，由于程序的邏輯地址與

11、分配一個合適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致到內(nèi)存物理地址不一致, 而而CPU執(zhí)行指令時，是按執(zhí)行指令時，是按物理地址進行的，所以要進行地址轉(zhuǎn)換物理地址進行的，所以要進行地址轉(zhuǎn)換03456.LOAD A 200.0100200300.LOAD A 2003456邏輯地址空間邏輯地址空間110012001300物理地址空間物理地址空間200VR+1000BR存儲管理的任務(wù)（續(xù)存儲管理的任務(wù)（續(xù)11）存儲管理的任務(wù)（續(xù)存儲管理的任務(wù)（續(xù)12）n靜態(tài)地址轉(zhuǎn)換靜態(tài)地址轉(zhuǎn)換 當用戶程序被裝入內(nèi)存時，一次性實現(xiàn)邏輯地址到當用戶程序被裝入內(nèi)存時，一次性實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以

12、后不再轉(zhuǎn)換物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換 一般在裝入內(nèi)存時由軟件完成一般在裝入內(nèi)存時由軟件完成n動態(tài)地址轉(zhuǎn)換動態(tài)地址轉(zhuǎn)換 在程序運行過程中要訪問數(shù)據(jù)時再進行地址變換在程序運行過程中要訪問數(shù)據(jù)時再進行地址變換（即在逐條指令執(zhí)行時完成地址映射。一般為了提（即在逐條指令執(zhí)行時完成地址映射。一般為了提高效率，此工作由硬件地址映射機制來完成。硬件高效率，此工作由硬件地址映射機制來完成。硬件支持，軟硬件結(jié)合完成）支持，軟硬件結(jié)合完成） 硬件上需要一對寄存器的支持硬件上需要一對寄存器的支持三、分區(qū)存儲管理方案三、分區(qū)存儲管理方案 系統(tǒng)把內(nèi)存用戶區(qū)劃分為若干分區(qū)，分系統(tǒng)把內(nèi)存用戶區(qū)劃分為若干分區(qū)，分區(qū)大小可以相

13、等，也可以不等。一個進區(qū)大小可以相等，也可以不等。一個進程占據(jù)一個分區(qū)程占據(jù)一個分區(qū)n固定分區(qū)固定分區(qū)n可變分區(qū)可變分區(qū)1. 固定分區(qū)固定分區(qū) 預(yù)先把可分配的內(nèi)存空間分割成若干個連預(yù)先把可分配的內(nèi)存空間分割成若干個連續(xù)區(qū)域，每一區(qū)域稱為分區(qū)續(xù)區(qū)域，每一區(qū)域稱為分區(qū) 每個分區(qū)的大小可以相同也可以不同，分每個分區(qū)的大小可以相同也可以不同，分區(qū)大小固定不變，每個分區(qū)裝一個且只區(qū)大小固定不變，每個分區(qū)裝一個且只能裝一個作業(yè)能裝一個作業(yè) 存儲分配：如果有一個空閑區(qū)，則分配給存儲分配：如果有一個空閑區(qū)，則分配給進程進程分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)多個等待隊列多個等待隊列單個等待

14、隊列單個等待隊列分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)固定分區(qū)（續(xù)）固定分區(qū)（續(xù)）內(nèi)存管理：設(shè)置內(nèi)存分配表內(nèi)存管理：設(shè)置內(nèi)存分配表內(nèi)存分配：內(nèi)存分配：內(nèi)存回收：內(nèi)存回收：缺點：內(nèi)存利用率不高缺點：內(nèi)存利用率不高分區(qū)號分區(qū)號 起始地址起始地址長度長度狀態(tài)狀態(tài)進程名進程名2. 可變分區(qū)存儲管理方案可變分區(qū)存儲管理方案n基本思想基本思想內(nèi)存不是預(yù)先劃分好的內(nèi)存不是預(yù)先劃分好的作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配使用情況來決定是否分配若有足夠的空間，則按需要分割一部分分區(qū)若有足夠的空間，則按需要分割一部分分區(qū)給該進程；否則

15、令其等待內(nèi)存空間給該進程；否則令其等待內(nèi)存空間可變分區(qū)存儲管理方案（續(xù)可變分區(qū)存儲管理方案（續(xù)1）n內(nèi)存管理內(nèi)存管理空閑塊表空閑塊表記錄了空閑區(qū)起始地址和記錄了空閑區(qū)起始地址和長度長度已分配區(qū)表已分配區(qū)表n內(nèi)存分配內(nèi)存分配 動態(tài)分配動態(tài)分配 三種分配算法：三種分配算法：首先適配、最佳適配、首先適配、最佳適配、最差適配最差適配0K15K38K48K68K80K110K120K空閑區(qū)表空閑區(qū)表已分配區(qū)表已分配區(qū)表始址始址長度長度標志標志15K23K未分配未分配48K20K未分配未分配80K30K未分配未分配空空空空始址始址長度長度標志標志0K15KJ138K10KJ268K12KJ3110K10K

16、J4空空空空0K15K38K48K68K80K110K120K空閑區(qū)表空閑區(qū)表已分配區(qū)表已分配區(qū)表始址始址長度長度標志標志15K23K未分配未分配48K20K未分配未分配98K12K未分配未分配空空空空始址始址長度長度標志標志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K可變分區(qū)存儲管理方案（續(xù)可變分區(qū)存儲管理方案（續(xù)2）n內(nèi)存回收內(nèi)存回收 當某一塊歸還后，前后空間合并，修改當某一塊歸還后，前后空間合并，修改內(nèi)存空閑塊表內(nèi)存空閑塊表 考慮：上鄰、下鄰、上下相鄰、上下不相鄰考慮：上鄰、下鄰、上下相鄰、上下不相鄰n“碎片碎片”問題問題 經(jīng)

17、過一段時間的分配回收后，內(nèi)存中存經(jīng)過一段時間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個都很在很多很小的空閑塊。它們每一個都很小，不足以滿足分配要求；但其總和滿小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片足分配要求。這些空閑塊被稱為碎片 造成存儲資源的浪費造成存儲資源的浪費可變分區(qū)存儲管理方案（續(xù)可變分區(qū)存儲管理方案（續(xù)3）n“碎片碎片”問題解決問題解決 緊湊技術(shù)：通過在內(nèi)存移動程序，將所緊湊技術(shù)：通過在內(nèi)存移動程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域有小的空閑區(qū)域合并為大的空閑區(qū)域 （又稱：緊縮技術(shù)，緊致技術(shù)，浮動技（又稱：緊縮技術(shù)，緊致技術(shù)，浮動技術(shù)，搬家技

18、術(shù)）術(shù)，搬家技術(shù)） 問題：開銷問題：開銷 大大 移動時機移動時機 ？可變分區(qū)存儲管理方案（續(xù)可變分區(qū)存儲管理方案（續(xù)4）n分區(qū)的保護：設(shè)置界地址寄存器分區(qū)的保護：設(shè)置界地址寄存器 保護鍵保護鍵n優(yōu)點：便于動態(tài)申請內(nèi)存優(yōu)點：便于動態(tài)申請內(nèi)存 便于共享內(nèi)存便于共享內(nèi)存 便于動態(tài)鏈接便于動態(tài)鏈接n缺點：缺點：碎片問題碎片問題(外碎片外碎片)，內(nèi)存利用率不高，內(nèi)存利用率不高 受實際內(nèi)存容量限制受實際內(nèi)存容量限制四、頁式存儲管理方案四、頁式存儲管理方案1. 基本思想（工作原理）基本思想（工作原理）n用戶程序劃分用戶程序劃分 把用戶程序按邏輯頁劃分成大小相等的把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁

19、。從部分，稱為頁。從0開始編制頁號，頁內(nèi)開始編制頁號，頁內(nèi)地址是相對于地址是相對于0編址編址n邏輯地址邏輯地址頁號頁號 頁內(nèi)地址頁內(nèi)地址基本思想（續(xù)基本思想（續(xù)1）n邏輯地址邏輯地址 用戶程序的劃分是由系統(tǒng)自動完成的，對用戶用戶程序的劃分是由系統(tǒng)自動完成的，對用戶是透明的。一般，一頁的大小為是透明的。一般，一頁的大小為2的整數(shù)次冪，的整數(shù)次冪，因此，地址的高位部分為頁號，低位部分為頁因此，地址的高位部分為頁號，低位部分為頁內(nèi)地址內(nèi)地址0111231頁號頁號P頁內(nèi)位移量頁內(nèi)位移量W編號編號01048575相對地址相對地址04095基本思想（續(xù)基本思想（續(xù)2）n內(nèi)存空間內(nèi)存空間 按頁的大小劃分為大

20、小相等的區(qū)域，稱按頁的大小劃分為大小相等的區(qū)域，稱為內(nèi)存塊（物理頁面，頁框）為內(nèi)存塊（物理頁面，頁框）n內(nèi)存分配內(nèi)存分配 以頁為單位進行分配，并按作業(yè)的頁數(shù)以頁為單位進行分配，并按作業(yè)的頁數(shù)多少來分配。邏輯上相鄰的頁，物理上多少來分配。邏輯上相鄰的頁，物理上不一定相鄰不一定相鄰.01234560123456作業(yè)的作業(yè)的地址空間地址空間頁框頁框（物理塊）（物理塊）頁頁號號頁頁表表主存中頁框主存中頁框（物理塊）（物理塊）.2. 管理管理n頁表：系統(tǒng)為每個進程建立一個頁表，頁表：系統(tǒng)為每個進程建立一個頁表，頁表給出邏輯頁號和具體內(nèi)存塊號相應(yīng)頁表給出邏輯頁號和具體內(nèi)存塊號相應(yīng)的關(guān)系的關(guān)系 頁表放在內(nèi)存

21、，屬于進程的現(xiàn)場信息頁表放在內(nèi)存，屬于進程的現(xiàn)場信息n空塊管理空塊管理位示圖位示圖0310/10/10/10/10/1017空閑塊數(shù)空閑塊數(shù)空塊管理空塊管理位示圖位示圖管理（續(xù)管理（續(xù)1）管理（續(xù)管理（續(xù)2）n內(nèi)存的分配與回收內(nèi)存的分配與回收計算一個作業(yè)所需要的總塊數(shù)計算一個作業(yè)所需要的總塊數(shù)N查位示圖，看看是否還有查位示圖，看看是否還有N個空閑塊個空閑塊如果有足夠的空閑塊，則頁表長度設(shè)為如果有足夠的空閑塊，則頁表長度設(shè)為N，可填入可填入PCB中；申請頁表區(qū)，把頁表始中；申請頁表區(qū)，把頁表始址填入址填入PCB依次分配依次分配N個空閑塊，將塊號和頁號填入個空閑塊，將塊號和頁號填入頁表頁表修改位示

22、圖修改位示圖3. 硬件支持硬件支持n系統(tǒng)設(shè)置一對寄存器：系統(tǒng)設(shè)置一對寄存器： 頁表始址寄存器頁表始址寄存器 頁表長度寄存器頁表長度寄存器n相聯(lián)存儲器相聯(lián)存儲器快表快表 快表表項：快表表項： 頁號；內(nèi)存塊號；標識位；淘汰位頁號；內(nèi)存塊號；標識位；淘汰位硬件支持（續(xù)硬件支持（續(xù)1）相聯(lián)（聯(lián)想）存儲器（相聯(lián)（聯(lián)想）存儲器（associative memory） TLB（Translation lookaside buffers） 介于內(nèi)存與寄存器之間的存儲機制，它又介于內(nèi)存與寄存器之間的存儲機制，它又叫快表叫快表用途：保存正在運行進程的頁表的子集（部用途：保存正在運行進程的頁表的子集（部分表項）分表

23、項）特點：按內(nèi)容并行查找特點：按內(nèi)容并行查找硬件支持（續(xù)硬件支持（續(xù)2）引入快表的目的：引入快表的目的： 為了提高地址映射速度為了提高地址映射速度快表淘汰問題？快表淘汰問題？p頁表頁表地址越界地址越界 l比較比較P=1pp. . .快表快表 b+頁號頁號p p 頁內(nèi)地址頁內(nèi)地址dPd物理地址物理地址頁表地址寄存器頁表地址寄存器頁表長度寄存器頁表長度寄存器邏輯地址邏輯地址地址映射機制地址映射機制五、覆蓋技術(shù)與交換技術(shù)五、覆蓋技術(shù)與交換技術(shù)1、為什么引入？、為什么引入？ 在多道環(huán)境下擴充內(nèi)存的方法，用以解在多道環(huán)境下擴充內(nèi)存的方法，用以解決在較小的存儲空間中運行較大程序時決在較小的存儲空間中運行較

24、大程序時遇到的矛盾遇到的矛盾n覆蓋技術(shù)主要用在早期的操作系統(tǒng)中覆蓋技術(shù)主要用在早期的操作系統(tǒng)中n交換技術(shù)被廣泛用于小型分時系統(tǒng)中，交換技術(shù)被廣泛用于小型分時系統(tǒng)中，交換技術(shù)的發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn)交換技術(shù)的發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn)為什么引入？（續(xù)）為什么引入？（續(xù)）n交換技術(shù)與覆蓋技術(shù)共同點：交換技術(shù)與覆蓋技術(shù)共同點： 進程的程序和數(shù)據(jù)主要放在外存，當前進程的程序和數(shù)據(jù)主要放在外存，當前需要執(zhí)行的部分放在內(nèi)存，內(nèi)外存之間需要執(zhí)行的部分放在內(nèi)存，內(nèi)外存之間進行信息交換進行信息交換n不同點：如何控制交換？不同點：如何控制交換？2、覆蓋技術(shù)、覆蓋技術(shù)n把程序劃分為若干個功能上相對獨立的程序段，把程

25、序劃分為若干個功能上相對獨立的程序段，按照其自身的邏輯結(jié)構(gòu)將那些不會同時執(zhí)行的按照其自身的邏輯結(jié)構(gòu)將那些不會同時執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域程序段共享同一塊內(nèi)存區(qū)域n程序段先保存在磁盤上，當有關(guān)程序段的前一程序段先保存在磁盤上，當有關(guān)程序段的前一部分執(zhí)行結(jié)束，把后續(xù)程序段調(diào)入內(nèi)存，覆蓋部分執(zhí)行結(jié)束，把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段（內(nèi)存前面的程序段（內(nèi)存“擴大擴大”了）了）n覆蓋：一個作業(yè)的若干程序段，或幾個作業(yè)的覆蓋：一個作業(yè)的若干程序段，或幾個作業(yè)的某些部分共享某一個存儲空間某些部分共享某一個存儲空間n一般要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)，一般要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)，

26、程序員要向系統(tǒng)指明覆蓋結(jié)構(gòu)，然后由由操作程序員要向系統(tǒng)指明覆蓋結(jié)構(gòu)，然后由由操作系統(tǒng)完成自動覆蓋系統(tǒng)完成自動覆蓋A8KE4KF10KC10KB8KD12K作業(yè)作業(yè)X的調(diào)用結(jié)構(gòu)的調(diào)用結(jié)構(gòu)作業(yè)作業(yè)X X的常駐區(qū)的常駐區(qū) A A（8K8K）覆蓋區(qū)覆蓋區(qū)0（10K）覆蓋區(qū)覆蓋區(qū)1（12K） BC C D E F覆蓋技術(shù)（續(xù)覆蓋技術(shù)（續(xù)1）缺點：缺點： 對用戶不透明，增加了用戶負擔對用戶不透明，增加了用戶負擔 例子：目前這一技術(shù)用于小型系統(tǒng)中的例子：目前這一技術(shù)用于小型系統(tǒng)中的系統(tǒng)程序的內(nèi)存管理上，系統(tǒng)程序的內(nèi)存管理上，MS-DOS的啟的啟動過程中，多次使用覆蓋技術(shù)；啟動之動過程中，多次使用覆蓋技術(shù)；啟

27、動之后，用戶程序區(qū)后，用戶程序區(qū)TPA的高端部分與的高端部分與COMMAND.COM暫駐模塊也是一種覆暫駐模塊也是一種覆蓋結(jié)構(gòu)蓋結(jié)構(gòu)覆蓋技術(shù)（續(xù)覆蓋技術(shù)（續(xù)2）3、交換技術(shù)、交換技術(shù)n為什么引入？為什么引入？ 當內(nèi)存空間緊張時，系統(tǒng)將內(nèi)存中某些當內(nèi)存空間緊張時，系統(tǒng)將內(nèi)存中某些進程暫時移到外存，把外存中某些進程進程暫時移到外存，把外存中某些進程換進內(nèi)存，占據(jù)前者所占用的區(qū)域，這換進內(nèi)存，占據(jù)前者所占用的區(qū)域，這種技術(shù)是進程在內(nèi)存與外存之間的動態(tài)種技術(shù)是進程在內(nèi)存與外存之間的動態(tài)調(diào)度調(diào)度 多用于分時系統(tǒng)中多用于分時系統(tǒng)中交換技術(shù)（續(xù)交換技術(shù)（續(xù)1）n交換技術(shù)實現(xiàn)中的幾個問題交換技術(shù)實現(xiàn)中的幾個問

28、題 選擇原則選擇原則 即：將哪個進程換出即：將哪個進程換出/內(nèi)存？內(nèi)存？ 例子：分時系統(tǒng)，時間片輪轉(zhuǎn)法或基于優(yōu)先數(shù)的調(diào)度算例子：分時系統(tǒng)，時間片輪轉(zhuǎn)法或基于優(yōu)先數(shù)的調(diào)度算法，在選擇換出進程時，要確定換出的進程是要長時間法，在選擇換出進程時，要確定換出的進程是要長時間等待的等待的需要特殊考慮的是：任何等待需要特殊考慮的是：任何等待I/O的進程中存在的問題的進程中存在的問題解決：解決： 從不換出處于等待從不換出處于等待I/O狀態(tài)的進程狀態(tài)的進程 有些有些I/O進程因進程因DMA而不能換出內(nèi)存或換出前需要操作而不能換出內(nèi)存或換出前需要操作系統(tǒng)的特殊幫助系統(tǒng)的特殊幫助 交換技術(shù)（續(xù)交換技術(shù)（續(xù)2）交換

29、時機的確定交換時機的確定 何時需發(fā)生交換？何時需發(fā)生交換？ 例子：例子：只要不用就換出（很少再用）只要不用就換出（很少再用）只在內(nèi)存空間不夠或有不夠的危險時換出只在內(nèi)存空間不夠或有不夠的危險時換出交換時需要做哪些工作？交換時需要做哪些工作？ 需要一個盤交換區(qū)：必須足夠大以存放所有需要一個盤交換區(qū)：必須足夠大以存放所有用戶程序的所有內(nèi)存映像的拷貝；必須對這些用戶程序的所有內(nèi)存映像的拷貝；必須對這些內(nèi)存映像的直接存取內(nèi)存映像的直接存取交換技術(shù)（續(xù)交換技術(shù)（續(xù)3）換入回內(nèi)存時位置的確定換入回內(nèi)存時位置的確定 換出后再換入的內(nèi)存位置一定要在換出前的原換出后再換入的內(nèi)存位置一定要在換出前的原來位置上嗎？

30、來位置上嗎？ 受地址受地址“綁定綁定”技術(shù)的影響，即絕對地址產(chǎn)生技術(shù)的影響，即絕對地址產(chǎn)生時機的限制時機的限制 與覆蓋技術(shù)相比，交換技術(shù)不要求用戶給出程與覆蓋技術(shù)相比，交換技術(shù)不要求用戶給出程序段之間的邏輯覆蓋結(jié)構(gòu)；而且，交換發(fā)生在序段之間的邏輯覆蓋結(jié)構(gòu)；而且，交換發(fā)生在進程或作業(yè)之間，而覆蓋發(fā)生在同一進程或作進程或作業(yè)之間，而覆蓋發(fā)生在同一進程或作業(yè)內(nèi)。此外，覆蓋只能覆蓋那些與覆蓋段無關(guān)業(yè)內(nèi)。此外，覆蓋只能覆蓋那些與覆蓋段無關(guān)的程序段的程序段六、虛擬存儲六、虛擬存儲連續(xù)性連續(xù)性 ； 離散性離散性駐留性駐留性 ； 交換性交換性一次性；一次性； 多次性多次性 以以CPU時間和外存空間換取昂貴內(nèi)存

31、空時間和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)1、概述、概述n問題的提出問題的提出 程序大于內(nèi)存程序大于內(nèi)存 程序暫時不執(zhí)行或運行完是否還要占用內(nèi)存程序暫時不執(zhí)行或運行完是否還要占用內(nèi)存 基本思想是：程序、數(shù)據(jù)、堆棧的大小可以超基本思想是：程序、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存的大小，操作系統(tǒng)把程序當前使用的部過內(nèi)存的大小，操作系統(tǒng)把程序當前使用的部分保留在內(nèi)存，而把其它部分保存在磁盤上，分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需要時在內(nèi)存和磁盤之間動態(tài)交換并在需要時在內(nèi)存和磁盤之間動態(tài)交換 虛擬存儲技術(shù)支持多道程序設(shè)計系統(tǒng)虛擬存儲技術(shù)支持多道程

32、序設(shè)計系統(tǒng)CPUMMU內(nèi)存內(nèi)存磁盤磁盤控制器控制器總線總線虛擬地址虛擬地址物理地址物理地址MMU：內(nèi)存管理單元：內(nèi)存管理單元XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虛地址空間虛地址空間物理地址空間物理地址空間 虛頁虛頁頁框頁框151413121110 9 8 7 6 5 4 3

33、2 10000000000000000111100001011000000000000011110010001110100110101 00010000000000100110000000000100110在在/不在內(nèi)存不在內(nèi)存頁表頁表虛地址虛地址8196物理地址物理地址24580概述（續(xù)概述（續(xù)1）n程序局部性原理程序局部性原理 在一段時間內(nèi)一個程序的執(zhí)行往往呈現(xiàn)出高度在一段時間內(nèi)一個程序的執(zhí)行往往呈現(xiàn)出高度的局部性，表現(xiàn)在時間與空間兩方面的局部性，表現(xiàn)在時間與空間兩方面時間局部性時間局部性 一條指令被執(zhí)行了，則在不久的將來它可能再一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行被執(zhí)行空間局部

34、性空間局部性 若某一存儲單元被使用，則在一定時間內(nèi)，與若某一存儲單元被使用，則在一定時間內(nèi)，與該存儲單元相鄰的單元可能被使用該存儲單元相鄰的單元可能被使用n虛擬存儲技術(shù)虛擬存儲技術(shù)虛存：虛存：把內(nèi)存與外存有機的結(jié)合起來使用，從而把內(nèi)存與外存有機的結(jié)合起來使用，從而得到一個容量很大的得到一個容量很大的“內(nèi)存內(nèi)存”，這就是虛存，這就是虛存實現(xiàn)思想：實現(xiàn)思想：當進程運行時，先將一部分程序裝入當進程運行時，先將一部分程序裝入內(nèi)存，另一部分暫時留在外存，當要執(zhí)行的指內(nèi)存，另一部分暫時留在外存，當要執(zhí)行的指令不在內(nèi)存時，由系統(tǒng)自動完成將它們從外存令不在內(nèi)存時，由系統(tǒng)自動完成將它們從外存調(diào)入內(nèi)存工作調(diào)入內(nèi)存

35、工作目的：目的： 提高內(nèi)存利用率提高內(nèi)存利用率概述（續(xù)概述（續(xù)2）2、虛擬頁式存儲管理、虛擬頁式存儲管理（1）基本思想）基本思想 在進程開始運行之前，不是裝入全部頁在進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根面，而是裝入一個或零個頁面，之后根據(jù)進程運行的需要，動態(tài)裝入其它頁面；據(jù)進程運行的需要，動態(tài)裝入其它頁面；當內(nèi)存空間已滿，而又需要裝入新的頁當內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面以便裝入新的頁面（2）頁表表項設(shè)計）頁表表項設(shè)計n頁號、駐留位、內(nèi)存塊號、保護位、訪問頁號、駐留位、內(nèi)存塊號、

36、保護位、訪問位、修改位位、修改位n駐留位（中斷位）：表示該頁是在內(nèi)存還是在外存駐留位（中斷位）：表示該頁是在內(nèi)存還是在外存n訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定）決定）n修改位：查看此頁是否在內(nèi)存中被修改過修改位：查看此頁是否在內(nèi)存中被修改過n保護位：讀保護位：讀/寫寫/執(zhí)行執(zhí)行n禁止緩存位：采用內(nèi)存映射禁止緩存位：采用內(nèi)存映射I/O的機器中需要的機器中需要頁號頁號中斷位中斷位 內(nèi)存塊號內(nèi)存塊號 保護位保護位訪問位訪問位 修改位修改位禁止緩存位禁止緩存位（3）缺頁中斷（）缺頁中斷（Page Fault）處理）處理n在地址映射過程中，在

37、頁表中發(fā)現(xiàn)所要訪在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，處理程序，根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存，使作業(yè)繼續(xù)運行下去將該頁調(diào)入內(nèi)存，使作業(yè)繼續(xù)運行下去n如果內(nèi)存中有空閑塊，則分配一頁，將新如果內(nèi)存中有空閑塊，則分配一頁，將新調(diào)入頁裝入內(nèi)存，并修改頁表中相應(yīng)頁表調(diào)入頁裝入內(nèi)存，并修改頁表中相應(yīng)頁表項目的駐留位及相應(yīng)的內(nèi)存塊號項目的駐留位及相應(yīng)的內(nèi)存塊號n若此時內(nèi)存中沒有空閑塊，則要淘汰某頁，若此時內(nèi)存中沒有空閑塊

38、，則要淘汰某頁，若該頁在內(nèi)存期間被修改過，則要將其寫若該頁在內(nèi)存期間被修改過，則要將其寫回外存回外存（4）頁面淘汰算法）頁面淘汰算法n理想淘汰算法理想淘汰算法最佳頁面算法（最佳頁面算法（OPT） 淘汰以后不再需要的或最遠的將來才會淘汰以后不再需要的或最遠的將來才會用到的頁面用到的頁面實現(xiàn)？實現(xiàn)？作用？作用？頁面淘汰算法（續(xù)頁面淘汰算法（續(xù)1）n最近未使用頁面淘汰算法最近未使用頁面淘汰算法（NRUNot Recently Used） 選擇在最近一段時間內(nèi)未使用過的一頁并淘汰選擇在最近一段時間內(nèi)未使用過的一頁并淘汰之之實現(xiàn)：設(shè)置兩位實現(xiàn)：設(shè)置兩位 訪問位（訪問位（R），）， 修改位（修改位（M）

39、啟動一個進程時，啟動一個進程時，R、M置置0 R被定期清零被定期清零發(fā)生缺頁中斷時，操作系統(tǒng)檢查發(fā)生缺頁中斷時，操作系統(tǒng)檢查R R，M M： 第第0 0類：無訪問，無修改類：無訪問，無修改 第第1 1類：無訪問，有修改類：無訪問，有修改 第第2 2類：有訪問，無修改類：有訪問，無修改 第第3 3類：有訪問，有修改類：有訪問，有修改 操作系統(tǒng)隨機從編號最小的非空類中選擇一頁操作系統(tǒng)隨機從編號最小的非空類中選擇一頁淘汰淘汰頁面淘汰算法（續(xù)頁面淘汰算法（續(xù)2）頁面淘汰算法（續(xù)頁面淘汰算法（續(xù)3）n先進先出頁面淘汰算法（先進先出頁面淘汰算法（FIFO） 選擇在內(nèi)存中駐留時間最長的頁并淘汰之選擇在內(nèi)存中

40、駐留時間最長的頁并淘汰之 對照：超市撤換商品對照：超市撤換商品n第二次機會淘汰算法第二次機會淘汰算法 (SCR-Second Chance ) 按照先進先出算法選擇某一頁面，檢查其按照先進先出算法選擇某一頁面，檢查其訪問位，如果為訪問位，如果為0，則淘汰該頁，如果為，則淘汰該頁，如果為1，則給第二次機會，并將訪問位置則給第二次機會，并將訪問位置0 實現(xiàn)：時鐘（實現(xiàn)：時鐘（Clock）算法）算法頁面淘汰算法（續(xù)頁面淘汰算法（續(xù)4）n最近最久未使用頁面淘汰算法最近最久未使用頁面淘汰算法（LRULeast Recently Used） 選擇最后一次訪問時間距離當前時間最選擇最后一次訪問時間距離當前時

41、間最長的一頁并淘汰之長的一頁并淘汰之 即淘汰沒有使用的時間最長的頁即淘汰沒有使用的時間最長的頁 實現(xiàn)代價很高實現(xiàn)代價很高 時間戳或硬件方法時間戳或硬件方法頁面淘汰算法（續(xù)頁面淘汰算法（續(xù)5）LRU的軟件解決方案：的軟件解決方案：n最不經(jīng)常使用（最不經(jīng)常使用（NFU-Not Frequently Used） 選擇訪問次數(shù)最少的頁面淘汰之選擇訪問次數(shù)最少的頁面淘汰之 實現(xiàn)：軟件計數(shù)器，一頁一個，初值為實現(xiàn)：軟件計數(shù)器，一頁一個，初值為0。每。每次時鐘中斷時，計數(shù)器加次時鐘中斷時，計數(shù)器加R。發(fā)生缺頁中斷時，。發(fā)生缺頁中斷時，選擇計數(shù)器值最小的一頁淘汰選擇計數(shù)器值最小的一頁淘汰改進（模擬改進（模擬L

42、RU）：計數(shù)器在加）：計數(shù)器在加R前先右移一位前先右移一位 R位加到計數(shù)器的最左端位加到計數(shù)器的最左端稱為稱為老化算法老化算法 某程序在內(nèi)存中分配三個頁面，初始為某程序在內(nèi)存中分配三個頁面，初始為空，頁面走向為空，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5，計算缺頁次數(shù)，計算缺頁次數(shù)頁面淘汰算法（續(xù)頁面淘汰算法（續(xù)6）FIFO 4 3 2 1 4 3 5 4 3 2 1 5頁頁1 4 3 2 1 4 3 5 5 5 2 1 1頁頁2 4 3 2 1 4 3 3 3 5 2 2頁頁3 4 3 2 1 4 4 4 3 5 5 x x x x x x x x x 共缺頁中斷共缺頁中斷9

43、次次頁面淘汰算法（續(xù)頁面淘汰算法（續(xù)7） LRU 4 3 2 1 4 3 5 4 3 2 1 5頁頁1 4 3 2 1 4 3 5 4 3 2 1 5頁頁2 4 3 2 1 4 3 5 4 3 2 1頁頁3 4 3 2 1 4 3 5 4 3 2 x x x x x x x x x x共缺頁中斷共缺頁中斷10次次頁面淘汰算法（續(xù)頁面淘汰算法（續(xù)8） OPT 4 3 2 1 4 3 5 4 3 2 1 5頁頁1 4 3 2 1 1 1 5 5 5 2 1 1頁頁2 4 3 3 3 3 3 3 3 5 5 5頁頁3 4 4 4 4 4 4 4 4 4 4 x x x x x x x 共缺頁中斷共缺

44、頁中斷7次次頁面淘汰算法（續(xù)頁面淘汰算法（續(xù)9） 例例2：某程序在內(nèi)存中分配：某程序在內(nèi)存中分配m頁初始為空，頁初始為空，頁面走向為頁面走向為1，2，3，4，1，2，5，1，2，3，4，5。當。當m=3，m=4時缺頁中斷分別時缺頁中斷分別為多少？用為多少？用FIFO算法計算缺頁次數(shù)算法計算缺頁次數(shù)頁面淘汰算法（續(xù)頁面淘汰算法（續(xù)10）m=3時，缺頁中斷時，缺頁中斷9次次m=4時，缺頁中斷時，缺頁中斷10次次注：注：FIFO頁面淘汰算法會產(chǎn)生異?，F(xiàn)頁面淘汰算法會產(chǎn)生異?，F(xiàn)象（象（Belady現(xiàn)象），即：當分配給現(xiàn)象），即：當分配給進程的物理頁面數(shù)增加時，缺頁次進程的物理頁面數(shù)增加時，缺頁次數(shù)反而

45、增加數(shù)反而增加頁面淘汰算法（續(xù)頁面淘汰算法（續(xù)11）(1) 分配給進程的物理頁面數(shù)分配給進程的物理頁面數(shù)(2) 頁面本身的大小頁面本身的大小(3) 程序的編制方法程序的編制方法(4) 頁面淘汰算法頁面淘汰算法（5）影響缺頁次數(shù)的因素）影響缺頁次數(shù)的因素例子例子3：內(nèi)存分配一頁，初始時第一頁在內(nèi)存；頁：內(nèi)存分配一頁，初始時第一頁在內(nèi)存；頁面大小為面大小為128個整數(shù)；矩陣個整數(shù)；矩陣A128X128按行存放按行存放程序編制方法程序編制方法1： For j:=1 to 128 For i:=1 to 128 Ai,j:=0;程序編制方法程序編制方法2： For i:=1 to 128 For j:

46、=1 to 128 Ai,j:=0;影響缺頁次數(shù)的因素（續(xù)影響缺頁次數(shù)的因素（續(xù)1）（1）顛簸（抖動）顛簸（抖動） 在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面所需時間比進程實際運行以至于調(diào)度頁面所需時間比進程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚的時間還多，此時系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動動原因：原因：頁面淘汰算法不合理頁面淘汰算法不合理分配給進程的物理頁面數(shù)太少分配給進程的物理頁面數(shù)太少3、性能問題、性能問題 基本思想：根據(jù)程序的局部性原理，一基本思想：根據(jù)程序的局部性原理，一般情況下，進程在一段時間內(nèi)總是集中般情況下，進程在一段時間內(nèi)總是集中訪問一些頁面，這些頁面稱為活躍頁面，訪問一些頁面，這些頁面稱為活躍頁面，如果分配給一個進程的物理頁面數(shù)太少如果分配給一個進程的物理頁面數(shù)太少了，使該進程所需的活躍頁面不能全部了，使該進程所需的活躍頁面不能全部裝入內(nèi)存，則進程在運行過程中將頻繁裝入內(nèi)存，則進程在運行過程中將頻繁發(fā)生中斷發(fā)生中斷