操作系統(tǒng)課件6_3

1、第六章第六章 存儲管理存儲管理l6.1 存儲管理功能存儲管理功能l6.2 內(nèi)存資源管理內(nèi)存資源管理l6.3 存儲管理方式存儲管理方式l6.4 外存空間管理外存空間管理l6.5 虛擬存儲系統(tǒng)虛擬存儲系統(tǒng) 16.4 外存資源管理外存資源管理l外存空間指磁盤等存儲型設(shè)備上的存儲區(qū)域外存空間指磁盤等存儲型設(shè)備上的存儲區(qū)域l邏輯上劃分為四個部分：輸入井、輸出井、文邏輯上劃分為四個部分：輸入井、輸出井、文件空間、交換空間件空間、交換空間l輸入井和輸出井用于實(shí)現(xiàn)作業(yè)的預(yù)輸入和作業(yè)的緩輸輸入井和輸出井用于實(shí)現(xiàn)作業(yè)的預(yù)輸入和作業(yè)的緩輸出出l文件空間用于保存文件文件空間用于保存文件l交換空間或?qū)Q空間用于實(shí)現(xiàn)虛擬

2、存儲的外存空間交換空間或?qū)Q空間用于實(shí)現(xiàn)虛擬存儲的外存空間, 在分級存儲體系中在分級存儲體系中, 可看成是內(nèi)存的擴(kuò)充可看成是內(nèi)存的擴(kuò)充Swap空間空間File空間空間輸入輸入井井輸出輸出井井26.4.1 外存空間劃分外存空間劃分 l存儲空間可看成是物理塊所構(gòu)成的有序存儲空間可看成是物理塊所構(gòu)成的有序序列序列l(wèi)所有塊的長度相同所有塊的長度相同, 通常為通常為2i, 如如256字節(jié)、字節(jié)、512字節(jié)、字節(jié)、1024字節(jié)等字節(jié)等l這些塊由這些塊由0開始依次地編號開始依次地編號, 稱作稱作塊號塊號l塊是外存分配的基本單位塊是外存分配的基本單位, 也是也是I/O傳輸?shù)幕鶄鬏數(shù)幕締挝槐締挝?36.4.2

3、 外存空間分配外存空間分配l外存的分配可采用與內(nèi)存相仿的方法外存的分配可采用與內(nèi)存相仿的方法l唯一差別在于內(nèi)存分配的基本單位是單元唯一差別在于內(nèi)存分配的基本單位是單元, 外外存分配的基本單位是塊存分配的基本單位是塊l如果需求不足一個完整的塊如果需求不足一個完整的塊, 則可能形成塊內(nèi)則可能形成塊內(nèi)“零頭零頭”。l外存空間分配采用如下三種方法之一外存空間分配采用如下三種方法之一: l空閑塊鏈空閑塊鏈(慢慢)l空閑塊表空閑塊表(UNIX)l字位映像圖字位映像圖46.4.2 外存空間分配外存空間分配l空閑塊鏈空閑塊鏈(與空閑頁鏈相似，速度慢與空閑頁鏈相似，速度慢)：所：所有空閑塊連成一個鏈有空閑塊連成

4、一個鏈l空閑塊表空閑塊表Unix(與空閑頁表相似與空閑頁表相似)：相連的：相連的空閑塊記錄在同一欄目中空閑塊記錄在同一欄目中l(wèi)字位映象圖：用一位代表一塊的狀態(tài)，這字位映象圖：用一位代表一塊的狀態(tài)，這些與內(nèi)存空間管理相仿些與內(nèi)存空間管理相仿5進(jìn)程與外存對應(yīng)關(guān)系進(jìn)程與外存對應(yīng)關(guān)系l界地址存儲管理外存空間分配界地址存儲管理外存空間分配 l每進(jìn)程占一組外存連續(xù)塊每進(jìn)程占一組外存連續(xù)塊l每進(jìn)程占二組外存連續(xù)塊（雙對界）每進(jìn)程占二組外存連續(xù)塊（雙對界）l頁式頁式l內(nèi)存頁面的長度與外存塊的長度相同內(nèi)存頁面的長度與外存塊的長度相同l內(nèi)存一頁，外存一塊內(nèi)存一頁，外存一塊l進(jìn)程在外存占有若干個塊進(jìn)程在外存占有若干

5、個塊, 塊的編號可以不連續(xù)塊的編號可以不連續(xù) l段式段式l每段占外存若干連續(xù)塊每段占外存若干連續(xù)塊l進(jìn)程的多個段之間在外存中可不連續(xù)進(jìn)程的多個段之間在外存中可不連續(xù) 6進(jìn)程與外存對應(yīng)關(guān)系進(jìn)程與外存對應(yīng)關(guān)系l段頁式段頁式l內(nèi)存頁面長度與外存塊長度相同內(nèi)存頁面長度與外存塊長度相同l內(nèi)存一頁，外存一塊內(nèi)存一頁，外存一塊l段內(nèi)多個頁所對應(yīng)的外存塊可不連續(xù)段內(nèi)多個頁所對應(yīng)的外存塊可不連續(xù)l一個進(jìn)程的多個段可分散在外存不同區(qū)域中一個進(jìn)程的多個段可分散在外存不同區(qū)域中76.5 虛擬存儲系統(tǒng)虛擬存儲系統(tǒng)l無虛擬存儲問題無虛擬存儲問題l不能運(yùn)行比內(nèi)存大的程序不能運(yùn)行比內(nèi)存大的程序l進(jìn)程全部裝入內(nèi)存，浪費(fèi)空間（進(jìn)

6、程活動具有局部進(jìn)程全部裝入內(nèi)存，浪費(fèi)空間（進(jìn)程活動具有局部性性)。l虛擬存儲虛擬存儲l一種借助于外存空間一種借助于外存空間, 允許一個進(jìn)程在其運(yùn)行過程允許一個進(jìn)程在其運(yùn)行過程中部分地裝入內(nèi)存的技術(shù)中部分地裝入內(nèi)存的技術(shù)l將內(nèi)存與外存有機(jī)結(jié)合將內(nèi)存與外存有機(jī)結(jié)合, 得到一個容量相當(dāng)于外存得到一個容量相當(dāng)于外存, 速度接近于內(nèi)存的存儲體系速度接近于內(nèi)存的存儲體系 l進(jìn)程部分裝入內(nèi)存，部分（或全部）裝入外存，運(yùn)進(jìn)程部分裝入內(nèi)存，部分（或全部）裝入外存，運(yùn)行時訪問在外存部分動態(tài)調(diào)入，內(nèi)存不夠淘汰。行時訪問在外存部分動態(tài)調(diào)入，內(nèi)存不夠淘汰。86.5 虛擬存儲系統(tǒng)虛擬存儲系統(tǒng)l6.5.1 虛擬頁式存儲系統(tǒng)

7、虛擬頁式存儲系統(tǒng) l6.5.2 虛擬段式存儲系統(tǒng)虛擬段式存儲系統(tǒng) l6.5.3 虛擬段頁式存儲系統(tǒng)虛擬段頁式存儲系統(tǒng) 96.5.1 虛擬頁式存儲系統(tǒng)虛擬頁式存儲系統(tǒng)l基本原理基本原理l進(jìn)程運(yùn)行前：進(jìn)程運(yùn)行前：l全部裝入外存，部分裝入內(nèi)存。全部裝入外存，部分裝入內(nèi)存。l進(jìn)程運(yùn)行時：進(jìn)程運(yùn)行時：l訪問頁不在內(nèi)存，發(fā)生訪問頁不在內(nèi)存，發(fā)生缺頁中斷缺頁中斷，中斷處理程序：，中斷處理程序：l找到訪問頁在外存的地址；找到訪問頁在外存的地址；l在內(nèi)存找一空閑頁面；在內(nèi)存找一空閑頁面；l如沒有，按淘汰算法淘汰一個；如沒有，按淘汰算法淘汰一個；l如需要，將淘汰頁面寫回外存，修改頁表和總頁表；如需要，將淘汰頁面寫

8、回外存，修改頁表和總頁表；l讀入所需頁面（切換進(jìn)程）；讀入所需頁面（切換進(jìn)程）；l啟動進(jìn)程，重新執(zhí)行被中斷的指令。啟動進(jìn)程，重新執(zhí)行被中斷的指令。106.5.1.1 基本原理基本原理l頁面調(diào)度需要執(zhí)行通道傳輸操作頁面調(diào)度需要執(zhí)行通道傳輸操作, 時間較長時間較長l被中斷進(jìn)程進(jìn)入等待狀態(tài)被中斷進(jìn)程進(jìn)入等待狀態(tài), 處理機(jī)轉(zhuǎn)去運(yùn)行其它處理機(jī)轉(zhuǎn)去運(yùn)行其它進(jìn)程進(jìn)程l待待I/O傳輸完成后硬件發(fā)出中斷信號，將缺頁進(jìn)傳輸完成后硬件發(fā)出中斷信號，將缺頁進(jìn)程喚醒程喚醒l為實(shí)現(xiàn)虛擬頁式存儲管理為實(shí)現(xiàn)虛擬頁式存儲管理, 頁表中需要增加如下頁表中需要增加如下欄目：欄目：l外存頁號外存頁號l內(nèi)外標(biāo)志內(nèi)外標(biāo)志l修改標(biāo)志等修改

9、標(biāo)志等 11對頁表的改進(jìn)：對頁表的改進(jìn)：對快表的改進(jìn)：對快表的改進(jìn)：邏輯頁號邏輯頁號 p . . . . . 頁架號頁架號 外存頁號外存頁號 內(nèi)外標(biāo)識內(nèi)外標(biāo)識 訪問權(quán)限訪問權(quán)限 修改標(biāo)志修改標(biāo)志 f p (0,1) r,w,e (0,1) . . . . . . . 邏輯頁號邏輯頁號 頁架號頁架號 訪問權(quán)限訪問權(quán)限 修改標(biāo)志修改標(biāo)志 p f r,w,e (0,1) . . . 126.5.1.2 內(nèi)存頁面分配策略內(nèi)存頁面分配策略 l平均分配平均分配l如內(nèi)存如內(nèi)存128頁，進(jìn)程頁，進(jìn)程25個，每個進(jìn)程個，每個進(jìn)程5個頁面?zhèn)€頁面l按進(jìn)程長度比例分配按進(jìn)程長度比例分配l按程序大小比例確定分配內(nèi)存物理

10、頁面?zhèn)€數(shù)按程序大小比例確定分配內(nèi)存物理頁面?zhèn)€數(shù)l設(shè)設(shè)si為進(jìn)程為進(jìn)程pi邏輯空間頁面數(shù)邏輯空間頁面數(shù), 定義定義: Ssil設(shè)設(shè)m為物理頁面總數(shù)為物理頁面總數(shù), 分配給進(jìn)程分配給進(jìn)程pi的內(nèi)存物的內(nèi)存物理頁面數(shù)理頁面數(shù) aisi /(Sm)l需對需對ai進(jìn)行調(diào)整使之不低于程序運(yùn)行所需的進(jìn)行調(diào)整使之不低于程序運(yùn)行所需的最少物理頁面數(shù)并且不高于最少物理頁面數(shù)并且不高于m136.5.1.2 內(nèi)存頁面分配策略內(nèi)存頁面分配策略l按進(jìn)程優(yōu)先級比例分配按進(jìn)程優(yōu)先級比例分配l為加速高優(yōu)先級進(jìn)程的執(zhí)行速度為加速高優(yōu)先級進(jìn)程的執(zhí)行速度, 可為其分配可為其分配較多的內(nèi)存頁面較多的內(nèi)存頁面l按進(jìn)程長度和優(yōu)先級別比例分

11、配按進(jìn)程長度和優(yōu)先級別比例分配l這是方法這是方法2和方法和方法3的結(jié)合的結(jié)合l方法方法2中的中的si為進(jìn)程為進(jìn)程pi邏輯頁面數(shù)與優(yōu)先級之邏輯頁面數(shù)與優(yōu)先級之和和 146.5.1.3 外存塊的分配策略外存塊的分配策略 l靜態(tài)分配靜態(tài)分配l 外存保持進(jìn)程的全部頁面外存保持進(jìn)程的全部頁面l 優(yōu)點(diǎn)：速度快優(yōu)點(diǎn)：速度快-淘汰時不必寫回淘汰時不必寫回(未修改情況未修改情況)l 缺點(diǎn)：外存浪費(fèi)缺點(diǎn)：外存浪費(fèi)l動態(tài)分配動態(tài)分配l外存僅保持進(jìn)程不在內(nèi)存的頁面外存僅保持進(jìn)程不在內(nèi)存的頁面l某一外存頁面被調(diào)入內(nèi)存時某一外存頁面被調(diào)入內(nèi)存時, 釋放所占用的外存頁面釋放所占用的外存頁面l當(dāng)該頁面被淘汰時當(dāng)該頁面被淘汰時

12、, 無論是否被修改無論是否被修改, 必需重新為其必需重新為其申請外存頁面申請外存頁面, 然后將該頁寫回外存然后將該頁寫回外存 l優(yōu)點(diǎn)：節(jié)省外存優(yōu)點(diǎn)：節(jié)省外存l缺點(diǎn)：速度慢缺點(diǎn)：速度慢-淘汰時必須寫回淘汰時必須寫回156.5.1.4 頁面調(diào)入時機(jī)頁面調(diào)入時機(jī)l有兩種方法有兩種方法: 請調(diào)和預(yù)調(diào)請調(diào)和預(yù)調(diào)l 請調(diào)請調(diào)(demand-paging)l當(dāng)頁故障發(fā)生時進(jìn)行調(diào)度當(dāng)頁故障發(fā)生時進(jìn)行調(diào)度l即當(dāng)訪問某一頁面而該頁面不在內(nèi)存時由動態(tài)調(diào)即當(dāng)訪問某一頁面而該頁面不在內(nèi)存時由動態(tài)調(diào)頁系統(tǒng)將其調(diào)入內(nèi)存頁系統(tǒng)將其調(diào)入內(nèi)存l預(yù)調(diào)預(yù)調(diào)(pre-paging)l 也稱先行調(diào)度：當(dāng)頁故障發(fā)生前進(jìn)行調(diào)度也稱先行調(diào)度：

13、當(dāng)頁故障發(fā)生前進(jìn)行調(diào)度l即當(dāng)一個頁面即將被訪問之前由動態(tài)調(diào)頁系統(tǒng)將即當(dāng)一個頁面即將被訪問之前由動態(tài)調(diào)頁系統(tǒng)將其調(diào)入內(nèi)存其調(diào)入內(nèi)存l預(yù)調(diào)必須輔以請調(diào)預(yù)調(diào)必須輔以請調(diào)166.5.1.5 置換算法置換算法(Replacement Algorithm)l用于：頁淘汰、段淘汰、快表淘汰用于：頁淘汰、段淘汰、快表淘汰l當(dāng)要訪問頁面不在內(nèi)存時當(dāng)要訪問頁面不在內(nèi)存時, 需將其調(diào)入內(nèi)需將其調(diào)入內(nèi)存存l如果內(nèi)存中無空閑頁面如果內(nèi)存中無空閑頁面, 需將內(nèi)存中某一頁面需將內(nèi)存中某一頁面移至外存移至外存, 被移出的頁面稱作被移出的頁面稱作淘汰頁面淘汰頁面 l選擇被淘汰頁面的算法稱作選擇被淘汰頁面的算法稱作置換算法置換算

14、法l置換算法的設(shè)計(jì)即要考慮效果置換算法的設(shè)計(jì)即要考慮效果, 又要考慮開銷又要考慮開銷 l頁面置換有頁面置換有局部與全局局部與全局之分之分l局部置換：在當(dāng)前缺頁進(jìn)程的頁架集中選擇淘汰局部置換：在當(dāng)前缺頁進(jìn)程的頁架集中選擇淘汰頁面頁面l全局置換：在內(nèi)存所有頁架集中選擇淘汰頁面全局置換：在內(nèi)存所有頁架集中選擇淘汰頁面 17最佳淘汰算法最佳淘汰算法(Optimal，OPT) l淘汰以后不再需要的淘汰以后不再需要的, 或者在最長時間以或者在最長時間以后才會用到的頁面后才會用到的頁面 l缺點(diǎn)：缺點(diǎn)： 無法準(zhǔn)確預(yù)期頁面無法準(zhǔn)確預(yù)期頁面“將來將來”的訪問情的訪問情況。況。l優(yōu)點(diǎn)：效率最高優(yōu)點(diǎn)：效率最高l有如下

15、頁面訪問序列有如下頁面訪問序列 6,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1l內(nèi)存中為該進(jìn)程分配內(nèi)存中為該進(jìn)程分配3個物理頁架個物理頁架, 開始時開始時內(nèi)存頁架為空內(nèi)存頁架為空, 缺頁故障次數(shù)為缺頁故障次數(shù)為9 18最佳淘汰算法最佳淘汰算法(Optimal，OPT)19先進(jìn)先出淘汰算法先進(jìn)先出淘汰算法(First-In First-Out，F(xiàn)IFO) l淘汰最先進(jìn)入內(nèi)存的頁面淘汰最先進(jìn)入內(nèi)存的頁面l實(shí)現(xiàn)時實(shí)現(xiàn)時, 每個頁面有一個調(diào)入時間每個頁面有一個調(diào)入時間, 該時間可該時間可在內(nèi)存中用軟件記錄在內(nèi)存中用軟件記錄, 最好設(shè)在寄存器中并由最好設(shè)在寄存器中并由硬件

16、記錄硬件記錄l當(dāng)內(nèi)存空間緊張時當(dāng)內(nèi)存空間緊張時, 調(diào)入時間最早的頁面將被調(diào)入時間最早的頁面將被淘汰淘汰l該算法也可以這樣實(shí)現(xiàn)該算法也可以這樣實(shí)現(xiàn)l將所有頁面按照進(jìn)入內(nèi)存的次序排成一個隊(duì)將所有頁面按照進(jìn)入內(nèi)存的次序排成一個隊(duì)列列l(wèi)當(dāng)一個頁面由外存調(diào)入內(nèi)存時排入隊(duì)尾當(dāng)一個頁面由外存調(diào)入內(nèi)存時排入隊(duì)尾l當(dāng)需要淘汰時取隊(duì)頭的頁面當(dāng)需要淘汰時取隊(duì)頭的頁面20先進(jìn)先出淘汰算法先進(jìn)先出淘汰算法(First-In First-Out，F(xiàn)IFO)21先進(jìn)先出淘汰算法先進(jìn)先出淘汰算法(First-In First-Out，F(xiàn)IFO)l如：如：1，2，3，4，1，2，5，1，2，3，4，5l內(nèi)存內(nèi)存3個物理頁面：頁

17、故障率個物理頁面：頁故障率=9/12內(nèi)存內(nèi)存4個物理個物理頁面：頁面：頁故障率頁故障率=10/12 22使用過最久的先淘汰使用過最久的先淘汰(Least Recently Used，LRU) l淘汰最后一次訪問時間距當(dāng)前時間間隔最淘汰最后一次訪問時間距當(dāng)前時間間隔最長的頁面長的頁面 23使用過最久的先淘汰使用過最久的先淘汰(Least Recently Used，LRU)lLRU的兩個實(shí)現(xiàn)方法的兩個實(shí)現(xiàn)方法:l記時法記時法: l每一頁面增設(shè)一個每一頁面增設(shè)一個訪問時間記時器訪問時間記時器l當(dāng)一個頁面被訪問時當(dāng)一個頁面被訪問時, 當(dāng)時的絕對時鐘內(nèi)容被拷貝當(dāng)時的絕對時鐘內(nèi)容被拷貝到對應(yīng)的訪問時間記

18、時器中到對應(yīng)的訪問時間記時器中l(wèi)系統(tǒng)記錄了內(nèi)存中所有頁面最后一次被訪問的時系統(tǒng)記錄了內(nèi)存中所有頁面最后一次被訪問的時間間l淘汰時淘汰時, 選取訪問時間記時器中值最小者所對應(yīng)的選取訪問時間記時器中值最小者所對應(yīng)的頁面頁面24使用過最久的先淘汰使用過最久的先淘汰(Least Recently Used，LRU)l棧法棧法: l按照頁面最后一次訪問的時間次序?qū)㈨撁嫣栆来伟凑枕撁孀詈笠淮卧L問的時間次序?qū)㈨撁嫣栆来蔚嘏帕械綏Ｖ械嘏帕械綏Ｖ衛(wèi)當(dāng)一個頁面被訪問時當(dāng)一個頁面被訪問時, 其對應(yīng)的頁面號由棧內(nèi)取出其對應(yīng)的頁面號由棧內(nèi)取出送入棧頂送入棧頂l淘汰時淘汰時, 取棧底頁面號所對應(yīng)的頁面取棧底頁面號所對應(yīng)的

19、頁面l這里的這里的“棧?！辈皇峭ǔＫx的不是通常所定義的LIFO棧棧l使用雙向鏈來構(gòu)造，其鏈頭和鏈尾各需一個指針使用雙向鏈來構(gòu)造，其鏈頭和鏈尾各需一個指針25棧法棧法設(shè)有訪問序列：設(shè)有訪問序列： 4, 7, 0, 7, 1, 0, 1, 2, 1, 2, 7, 1, 2 07470417044740174107421074120742107472104172042170426使用過最久的先淘汰使用過最久的先淘汰(Least Recently Used，LRU)lLRU算法的實(shí)現(xiàn)開銷很大算法的實(shí)現(xiàn)開銷很大l必須有硬件的支持必須有硬件的支持l完全由軟件實(shí)現(xiàn)其速度至少會降低完全由軟件實(shí)現(xiàn)其速度至少

20、會降低10倍倍 27最近不用的先淘汰最近不用的先淘汰(Not Used Recently，NUR) l淘汰最近一段時間內(nèi)未用過的頁面淘汰最近一段時間內(nèi)未用過的頁面l根據(jù)程序一般的行為特性根據(jù)程序一般的行為特性l一個在最近一段時間內(nèi)未被用到的頁面在以一個在最近一段時間內(nèi)未被用到的頁面在以后也不大可能會被用到后也不大可能會被用到l它們可以被淘汰它們可以被淘汰l這是一種流行的、低開銷的、接近于這是一種流行的、低開銷的、接近于LRU效效果的淘汰算法果的淘汰算法 28最近不用的先淘汰最近不用的先淘汰(Not Used Recently，NUR)l實(shí)現(xiàn)時實(shí)現(xiàn)時, 為每一個頁面增加兩個硬件位為每一個頁面增加

21、兩個硬件位, 它它們是們是: 引用位引用位 0, 此頁未被訪問過此頁未被訪問過 1, 此頁曾被訪問過此頁曾被訪問過 修改位修改位 0, 此頁未被修改過此頁未被修改過 1, 此頁曾被修改過此頁曾被修改過29最近不用的先淘汰最近不用的先淘汰(Not Used Recently，NUR)l一個頁面由外存調(diào)入內(nèi)存時一個頁面由外存調(diào)入內(nèi)存時, 其引用位和修改位其引用位和修改位均為均為0l對某頁面執(zhí)行寫操作對某頁面執(zhí)行寫操作, 其修改位和引用位由硬件其修改位和引用位由硬件置為置為1l對某頁面執(zhí)行讀操作對某頁面執(zhí)行讀操作, 其引用位由硬件置為其引用位由硬件置為1l每隔固定時間將所有引用位都清每隔固定時間將所

22、有引用位都清0l要淘汰某一頁面時要淘汰某一頁面時, 按照下面次序選擇按照下面次序選擇:l(1) 引用位引用位0, 修改位修改位0: 直接淘汰直接淘汰;(2) 引用位引用位0, 修改位修改位1: 淘汰之前寫回外存淘汰之前寫回外存;(3) 引用位引用位1, 修改位修改位0: 直接淘汰直接淘汰;(4) 引用位引用位1, 修改位修改位1: 淘汰之前寫回外存淘汰之前寫回外存30最不經(jīng)常使用者先淘汰最不經(jīng)常使用者先淘汰(Least Frequently Used，LFU) l淘汰訪問次數(shù)最少的頁面淘汰訪問次數(shù)最少的頁面 l實(shí)現(xiàn)時實(shí)現(xiàn)時, 為每一個頁面設(shè)一個訪問次數(shù)計(jì)為每一個頁面設(shè)一個訪問次數(shù)計(jì)數(shù)器數(shù)器l當(dāng)

23、一個頁面由外存移到內(nèi)存時當(dāng)一個頁面由外存移到內(nèi)存時, 對應(yīng)計(jì)數(shù)器清對應(yīng)計(jì)數(shù)器清0l當(dāng)一個頁面被訪問時當(dāng)一個頁面被訪問時, 對應(yīng)計(jì)數(shù)器加對應(yīng)計(jì)數(shù)器加1l當(dāng)需要淘汰時當(dāng)需要淘汰時, 取計(jì)數(shù)值最小的頁面取計(jì)數(shù)值最小的頁面 31最不經(jīng)常使用者先淘汰最不經(jīng)常使用者先淘汰(Least Frequently Used，LFU)l算法的依據(jù)算法的依據(jù)l活動的頁面其計(jì)數(shù)值大活動的頁面其計(jì)數(shù)值大, 應(yīng)當(dāng)將其留在內(nèi)存應(yīng)當(dāng)將其留在內(nèi)存l不足不足l以前曾經(jīng)多次使用的頁面雖目前不用也會留在內(nèi)以前曾經(jīng)多次使用的頁面雖目前不用也會留在內(nèi)存存l剛剛移入內(nèi)存的頁面因其訪問計(jì)數(shù)值很小反而會剛剛移入內(nèi)存的頁面因其訪問計(jì)數(shù)值很小反而會

24、被淘汰被淘汰l一種彌補(bǔ)方法是定時將計(jì)數(shù)值右移一種彌補(bǔ)方法是定時將計(jì)數(shù)值右移, 形成按時間指形成按時間指數(shù)衰減的平均使用計(jì)數(shù)值數(shù)衰減的平均使用計(jì)數(shù)值32使用最頻繁者先淘汰使用最頻繁者先淘汰(Most Frequently Used，MFU) l淘汰使用次數(shù)最多的淘汰使用次數(shù)最多的l認(rèn)為計(jì)數(shù)值最小的頁面很可能剛剛調(diào)入內(nèi)認(rèn)為計(jì)數(shù)值最小的頁面很可能剛剛調(diào)入內(nèi)存存, 正待被使用，不應(yīng)淘汰。正待被使用，不應(yīng)淘汰。l依據(jù)：使用多的可能已經(jīng)用完了依據(jù)：使用多的可能已經(jīng)用完了lLFU和和MFU都有缺點(diǎn)都有缺點(diǎn), 而且實(shí)現(xiàn)開銷較大而且實(shí)現(xiàn)開銷較大 336.5.1.6 顛簸顛簸(Thrashing)l顛簸又譯抖動顛

25、簸又譯抖動, 指頁面在內(nèi)存與外存之間指頁面在內(nèi)存與外存之間頻繁地?fù)Q入換出頻繁地?fù)Q入換出l原因原因 l分給進(jìn)程物理頁架過少分給進(jìn)程物理頁架過少 l淘汰算法不合理淘汰算法不合理l程序結(jié)構(gòu)問題：濫用轉(zhuǎn)移指令、分散的全局程序結(jié)構(gòu)問題：濫用轉(zhuǎn)移指令、分散的全局變量都會破壞程序的局部性變量都會破壞程序的局部性, 從而增加頁故障從而增加頁故障率率, 甚至引起顛簸甚至引起顛簸 346.5.1.6 顛簸顛簸(Thrashing)l處理：處理：l增加分給進(jìn)程物理頁架數(shù)增加分給進(jìn)程物理頁架數(shù)l改進(jìn)淘汰算法：改進(jìn)淘汰算法：l首先可考慮首先可考慮LRU算法算法l如開銷過大或硬件支持不夠如開銷過大或硬件支持不夠, 可選擇

26、可選擇NUR算法算法, 通通常問題可以得到解決常問題可以得到解決 356.5.1.6 顛簸顛簸(Thrashing)l為描述顛簸為描述顛簸, 引入頁故障率的概念引入頁故障率的概念l設(shè)進(jìn)程訪問內(nèi)存成功的次數(shù)為設(shè)進(jìn)程訪問內(nèi)存成功的次數(shù)為S, 故障的次數(shù)為故障的次數(shù)為F,則總訪問次數(shù)則總訪問次數(shù)A： ASF， 頁故障率頁故障率f：fFAl系統(tǒng)用于調(diào)度頁面所需時間比進(jìn)程實(shí)際運(yùn)行所系統(tǒng)用于調(diào)度頁面所需時間比進(jìn)程實(shí)際運(yùn)行所占用的時間要多占用的時間要多l(xiāng)顛簸是由于頁故障率過高的結(jié)果顛簸是由于頁故障率過高的結(jié)果, 它將嚴(yán)重地影它將嚴(yán)重地影響系統(tǒng)的效率，甚至可能使系統(tǒng)全面崩潰響系統(tǒng)的效率，甚至可能使系統(tǒng)全面崩潰

27、366.5.1.6 顛簸顛簸(Thrashing)l思考題：思考題：l在某些虛擬頁式存儲管理系統(tǒng)中，內(nèi)存中總在某些虛擬頁式存儲管理系統(tǒng)中，內(nèi)存中總保持一個空閑的物理頁面，這樣做有什么好保持一個空閑的物理頁面，這樣做有什么好處？處？376.5.1.7 工作集模型工作集模型(working set model)l工作集模型由工作集模型由Denning提出提出l工作集工作集(working set)是進(jìn)程在一段時間之是進(jìn)程在一段時間之內(nèi)活躍地訪問頁面的集合內(nèi)活躍地訪問頁面的集合lDenning認(rèn)為認(rèn)為, 為使程序有效地運(yùn)行為使程序有效地運(yùn)行, 它的它的工作集頁面必須能夠放到內(nèi)存中工作集頁面必須能夠放

28、到內(nèi)存中386.5.1.7 工作集模型工作集模型(working set model)l準(zhǔn)確地說準(zhǔn)確地說, 一進(jìn)程從時刻一進(jìn)程從時刻(t-)到時刻到時刻t之間所訪之間所訪問頁面的集合問頁面的集合WS(t,)稱作該進(jìn)程的工作集稱作該進(jìn)程的工作集l如圖如圖 6-41 所示，所示，稱作窗口尺寸稱作窗口尺寸(windows size)396.5.1.7 工作集模型工作集模型(working set model)l工作集是隨時間而變化的工作集是隨時間而變化的l下圖所示的頁面訪問軌跡，下圖所示的頁面訪問軌跡，WS(t1,)5,7,1,6,2, WS(t2,)2,3,4WS(t1, )=5,7,1,6,22

29、 6 1 5 7 7 7 7 5 1 6 2 2 1 2 3 4 4 4 3 4 3 4 4 4 1 3 4 .WS(t2, )=2,3,4t1t2406.5.1.7 工作集模型工作集模型(working set model)l工作集大小與窗口尺寸工作集大小與窗口尺寸密切相關(guān)密切相關(guān), 程序大小程序大小 WS416.5.1.7 工作集模型工作集模型(working set model)l工作集模型的精確度與工作集模型的精確度與密切相關(guān)密切相關(guān)l過小過小, 程序活動頁面不能全部裝入內(nèi)存程序活動頁面不能全部裝入內(nèi)存, 頁故障率高頁故障率高l過大過大, 允許同時并發(fā)執(zhí)行進(jìn)程的個數(shù)降低允許同時并發(fā)執(zhí)行

30、進(jìn)程的個數(shù)降低lMadnick和和Donovan建議建議大約為大約為10,000次訪問內(nèi)存次訪問內(nèi)存l實(shí)現(xiàn)：頁表中增加訪問位：實(shí)現(xiàn)：頁表中增加訪問位： l開始時，全部清開始時，全部清0, 訪問：置訪問：置1,l結(jié)束時結(jié)束時(新新開始時開始時)訪問標(biāo)志為訪問標(biāo)志為1的，為該的，為該期間工作期間工作集，調(diào)整集，調(diào)整(增加或減少增加或減少)該進(jìn)程在內(nèi)存頁面數(shù)為該工作該進(jìn)程在內(nèi)存頁面數(shù)為該工作集大小。集大小。426.5.1.8 頁故障率反饋模型頁故障率反饋模型l工作集模型能夠非常成功地指導(dǎo)頁面的分工作集模型能夠非常成功地指導(dǎo)頁面的分配配, 從而防止發(fā)生顛簸從而防止發(fā)生顛簸l它的實(shí)現(xiàn)開銷較大它的實(shí)現(xiàn)開銷

31、較大, 使用存在困難。使用存在困難。l顛簸是由于頁故障率高而引起顛簸是由于頁故障率高而引起l系統(tǒng)利用頁故障率的反饋信息來動態(tài)地調(diào)系統(tǒng)利用頁故障率的反饋信息來動態(tài)地調(diào)整頁面的分配整頁面的分配, 這就是頁故障率反饋模型這就是頁故障率反饋模型的思想的思想436.5.1.8 頁故障率反饋模型頁故障率反饋模型PFFB(Page Fault Feed Back)頁故障率高頁故障率高(達(dá)到某上界閾值達(dá)到某上界閾值)：內(nèi)存頁面少，增加。：內(nèi)存頁面少，增加。頁故障率低頁故障率低(達(dá)到某下界閾值達(dá)到某下界閾值)：內(nèi)存頁面多，減少。：內(nèi)存頁面多，減少。446.5.2 虛擬段式存儲系統(tǒng)虛擬段式存儲系統(tǒng)l6.5.2.1

32、 基本原理基本原理 l6.5.2.2 段的動態(tài)連接段的動態(tài)連接456.5.2.1 基本原理基本原理l思想與虛擬頁式相似思想與虛擬頁式相似, 只是將頁變化為段只是將頁變化為段l進(jìn)程運(yùn)行前將主程序段裝入內(nèi)存進(jìn)程運(yùn)行前將主程序段裝入內(nèi)存, 其它段其它段裝入外存裝入外存l運(yùn)行時所需的段如不在內(nèi)存運(yùn)行時所需的段如不在內(nèi)存, 將其動態(tài)調(diào)將其動態(tài)調(diào)入入, 內(nèi)存沒有足夠空間采取兩種方法內(nèi)存沒有足夠空間采取兩種方法l緊湊：將內(nèi)存中所有空閑區(qū)合并緊湊：將內(nèi)存中所有空閑區(qū)合并l淘汰：將內(nèi)存中某段移出至外存淘汰：將內(nèi)存中某段移出至外存, 段的淘汰可段的淘汰可采用與頁式相似的算法采用與頁式相似的算法466.5.2.1

33、基本原理基本原理 修改過修改過TF缺段中斷缺段中斷在外存找到所缺段在外存找到所缺段內(nèi)存夠用內(nèi)存夠用選一段淘汰選一段淘汰寫回外存寫回外存修改段表修改段表F移入移入修改段表修改段表T476.5.2.1 基本原理基本原理l段表的改進(jìn)段表的改進(jìn) . . . .段號段號 s . 段長段長 內(nèi)存首址內(nèi)存首址 外存首址外存首址 權(quán)限權(quán)限 內(nèi)外標(biāo)識內(nèi)外標(biāo)識 修改標(biāo)志修改標(biāo)志 l b b” rwe (0,1) (0,1) . . . .48 . . . . 段號段號 段長段長 內(nèi)存首址內(nèi)存首址 訪問權(quán)限訪問權(quán)限 修改標(biāo)志修改標(biāo)志 s l b rwe (0,1) . . . .6.5.2.1 基本原理基本原理l快

34、表的改進(jìn)快表的改進(jìn)496.5.2.2 段的動態(tài)連接段的動態(tài)連接(dynamic linking)l動態(tài)連接動態(tài)連接 vs. 靜態(tài)連接靜態(tài)連接l靜態(tài)連接：運(yùn)行前連接，由靜態(tài)連接：運(yùn)行前連接，由link完成完成l動態(tài)連接：運(yùn)行時連接，由動態(tài)連接：運(yùn)行時連接，由OS完成完成l靜態(tài)連接的缺點(diǎn)靜態(tài)連接的缺點(diǎn)l連接時間長；連接時間長；l目標(biāo)代碼長；目標(biāo)代碼長；l連接段可能并不執(zhí)行連接段可能并不執(zhí)行(未用到未用到)50動態(tài)連接的實(shí)現(xiàn)動態(tài)連接的實(shí)現(xiàn) l在靜態(tài)連接中在靜態(tài)連接中, 程序共有多少個段是確定的程序共有多少個段是確定的, 連連接裝配程序?yàn)槊總€段分配一個段號接裝配程序?yàn)槊總€段分配一個段號, 即即段名到段

35、段名到段號的轉(zhuǎn)換由連接裝配程序完成號的轉(zhuǎn)換由連接裝配程序完成l在動態(tài)連接中在動態(tài)連接中, 一個程序共有多少個段是不定的一個程序共有多少個段是不定的, 段名到段號的轉(zhuǎn)換由操作系統(tǒng)來完成段名到段號的轉(zhuǎn)換由操作系統(tǒng)來完成l由于同一個段只分配一個段號由于同一個段只分配一個段號, 操作系統(tǒng)需為每操作系統(tǒng)需為每一個進(jìn)程保持一個用于記錄當(dāng)前已連接段的表一個進(jìn)程保持一個用于記錄當(dāng)前已連接段的表目目l該表稱作該表稱作段名段名段號對照表段號對照表, 其形式如圖其形式如圖 644 所示所示51動態(tài)連接的實(shí)現(xiàn)動態(tài)連接的實(shí)現(xiàn)段名段名-段號對照表：每進(jìn)程一個段號對照表：每進(jìn)程一個段名段名 段號段號sname snum .

36、 .52動態(tài)連接的實(shí)現(xiàn)動態(tài)連接的實(shí)現(xiàn)l將一個外段中的符號名轉(zhuǎn)換為對應(yīng)的段內(nèi)地址將一個外段中的符號名轉(zhuǎn)換為對應(yīng)的段內(nèi)地址, 每個段在編譯每個段在編譯(匯編匯編)時時, 需生成一個符號表需生成一個符號表, 放在放在一個段的前面一個段的前面, 作為段的一個組成部分作為段的一個組成部分l符號表如圖所示符號表如圖所示符號名符號名 段內(nèi)位移段內(nèi)位移 func 150 . .53動態(tài)連接的實(shí)現(xiàn)動態(tài)連接的實(shí)現(xiàn)l一個段由符號表和目標(biāo)程序一個段由符號表和目標(biāo)程序(或者數(shù)據(jù)或者數(shù)據(jù))兩兩部分構(gòu)成部分構(gòu)成, 如圖所示如圖所示段形式：段形式：符號表符號表目標(biāo)代碼目標(biāo)代碼或者數(shù)據(jù)或者數(shù)據(jù)54動態(tài)連接需要經(jīng)過的步驟動態(tài)連接

37、需要經(jīng)過的步驟:l編譯編譯(匯編匯編)時：遇到訪問外段指令時：遇到訪問外段指令, 采用間采用間接尋址接尋址, 即指向一個間接字，間接字的形即指向一個間接字，間接字的形式如圖所示式如圖所示 LD1: 未連接未連接0: 已連接已連接符號地址：符號地址：“X|”邏輯地址：邏輯地址：(段號段號,段內(nèi)地址段內(nèi)地址)55編譯編譯(匯編匯編)時時lL=1, 表示尚未連接表示尚未連接, D為符號地址為符號地址l“X|” 表示表示X段段單元單元lL=0, 表示連接完畢表示連接完畢, D為邏輯地址為邏輯地址, 由段號與段內(nèi)地址構(gòu)由段號與段內(nèi)地址構(gòu)成成l初始時初始時, L均為均為1lL為為1, 表示需要進(jìn)行動態(tài)連接

38、表示需要進(jìn)行動態(tài)連接, 否則為一般的間接指令否則為一般的間接指令LD1: 未連接未連接0: 已連接已連接符號地址：符號地址：“X|”邏輯地址：邏輯地址：(段號段號,段內(nèi)地址段內(nèi)地址)56執(zhí)行時執(zhí)行時l遇到間址指令且遇到間址指令且L=1時時, 硬件產(chǎn)生連接中硬件產(chǎn)生連接中斷斷, 由連接中斷處理程序進(jìn)行動態(tài)連接由連接中斷處理程序進(jìn)行動態(tài)連接, 具具體做法如下體做法如下:la)由由D處取出符號地址中段名部分處取出符號地址中段名部分;lb)由段名查段名由段名查段名段號對照表看該段是否已分段號對照表看該段是否已分配段號配段號, 有兩種情形有兩種情形:57執(zhí)行時執(zhí)行時lc)該段已分配段號該段已分配段號,

39、該段以前曾連接過該段以前曾連接過l將該段號由段名將該段號由段名段號對照表中取出段號對照表中取出l由段號查段表找到該段由段號查段表找到該段l由單元名查該段的符號表從中取出段內(nèi)地址由單元名查該段的符號表從中取出段內(nèi)地址l將段號和段內(nèi)地址送入將段號和段內(nèi)地址送入D, 0送送L; ld)該段未分配段號該段未分配段號, 說明該段以前未連接過說明該段以前未連接過l將該段由文件系統(tǒng)中調(diào)入內(nèi)存將該段由文件系統(tǒng)中調(diào)入內(nèi)存, 分配一個段號分配一個段號l填寫段名填寫段名段號對照表段號對照表l轉(zhuǎn)轉(zhuǎn)(b)58實(shí)例實(shí)例1 匯編前：匯編前：設(shè)有兩個段設(shè)有兩個段, 段名分別為段名分別為W和和X指令指令LOAD 1, X|表示

40、：表示：將將X段段單元中的內(nèi)容取來送入單元中的內(nèi)容取來送入1號寄存器號寄存器這是一條訪問外段的指令這是一條訪問外段的指令 59實(shí)例實(shí)例1 l匯編后：假設(shè)匯編后：假設(shè)W段已連接并在內(nèi)存段已連接并在內(nèi)存, 段號段號為為 2; X段尚未連接段尚未連接, 保存在文件系統(tǒng)中保存在文件系統(tǒng)中, 進(jìn)程空間各段進(jìn)程空間各段, 以及各表目如圖以及各表目如圖 6-49所示所示l符號地址是一個字符串符號地址是一個字符串, 可能很長可能很長, D處存處存放不下放不下, 所以所以D處實(shí)際存了一個指向該符號處實(shí)際存了一個指向該符號串的首地址串的首地址l7X| 中的數(shù)字中的數(shù)字7是符號串是符號串X|的長度的長度 6061匯

41、編后連接后匯編后連接后 lW段段: 已連接已連接在內(nèi)存在內(nèi)存 X段段: 已連接已連接在內(nèi)存在內(nèi)存l進(jìn)程空間各段進(jìn)程空間各段, 以及各表形式如圖以及各表形式如圖 650 所示所示6263實(shí)例實(shí)例2: .Load 1, X|Load 2, X|.W段X段12345678.Y:Z:64匯編后，連接前：匯編后，連接前：100:Load *1, 2|100;Load *2, 2|150;“7X|”.“7X|”1 2 2001 2 250150:200:250:W段（段號段（段號=2)X段段 300 40012345678300400段表段表 段首址段首址 .段號 0 1 2 3 .段名段名 段號段號Ma

42、in 0A 1W 2段名段名-段號對照表段號對照表65第一次連接后：第一次連接后：100:Load *1, 2|100;Load *2, 2|150;“7X|”.“7X|”0 3 3001 2 250150:200:250:W段（段號段（段號=2)X段段 300 40012345678300400段表段表 段首址段首址 .段號 0 1 2 3 .段名段名 段號段號Main 0A 1W 2段名段名-段號對照表段號對照表X 366100:Load *1, 2|100;Load *2, 2|150;“7X|”.“7X|”0 3 3000 3 400150:200:250:W段（段號段（段號=2)X段

43、段 300 40012345678300400段表段表 段首址 .段號 0 1 2 3 .段名 段號Main 0A 1W 2段名段名-段號對照表段號對照表X 3第二次連接后：第二次連接后：67動態(tài)連接問題動態(tài)連接問題l動態(tài)連接與共享的矛盾動態(tài)連接與共享的矛盾l動態(tài)連接：修改連接字（代碼）動態(tài)連接：修改連接字（代碼）l段的共享：要求純代碼（段的共享：要求純代碼（pure code)l解決方法解決方法l共享代碼分為共享代碼分為“純段純段”和和“雜段雜段”l純段共享，純段共享，l雜段私用。雜段私用。686.5.3 虛擬段頁式存儲系統(tǒng)虛擬段頁式存儲系統(tǒng)l虛擬頁式：將存儲空間靜態(tài)地劃分為長度虛擬頁式：將

44、存儲空間靜態(tài)地劃分為長度相同的區(qū)域相同的區(qū)域, l優(yōu)點(diǎn)：簡化存儲分配優(yōu)點(diǎn)：簡化存儲分配, 消除消除“碎片碎片”問題問題. l缺點(diǎn)：只提供一維地址缺點(diǎn)：只提供一維地址, 進(jìn)程空間不能動態(tài)擴(kuò)進(jìn)程空間不能動態(tài)擴(kuò)充充, 無法實(shí)現(xiàn)程序段的動態(tài)連接無法實(shí)現(xiàn)程序段的動態(tài)連接. l頁式存儲管理也能實(shí)現(xiàn)存儲的共享和保護(hù)頁式存儲管理也能實(shí)現(xiàn)存儲的共享和保護(hù)l由于以頁為基本單位由于以頁為基本單位, 頁面長度與程序基本單頁面長度與程序基本單位長度不等位長度不等, 實(shí)現(xiàn)起來比較麻煩實(shí)現(xiàn)起來比較麻煩696.5.3 虛擬段頁式存儲系統(tǒng)虛擬段頁式存儲系統(tǒng)l虛擬段式：將存儲空間動態(tài)地劃分為長度虛擬段式：將存儲空間動態(tài)地劃分為長

45、度不同的區(qū)域不同的區(qū)域, 一個區(qū)域恰好對應(yīng)一個程序一個區(qū)域恰好對應(yīng)一個程序單位。單位。l優(yōu)點(diǎn)：提供二維地址優(yōu)點(diǎn)：提供二維地址, 方便存儲共享和存儲保方便存儲共享和存儲保護(hù)，可實(shí)現(xiàn)段長度的動態(tài)變化護(hù)，可實(shí)現(xiàn)段長度的動態(tài)變化, 以及段間動態(tài)以及段間動態(tài)連接連接. l 缺點(diǎn)：存儲空間的分配和去配比較復(fù)雜缺點(diǎn)：存儲空間的分配和去配比較復(fù)雜, 可可能形成能形成“碎片碎片”706.5.3 虛擬段頁式存儲系統(tǒng)虛擬段頁式存儲系統(tǒng)l虛擬段頁式考慮：虛擬段頁式考慮：l段的動態(tài)連接段的動態(tài)連接l段的共享段的共享l段長度的動態(tài)變化段長度的動態(tài)變化l6.5.3.1 基本原理基本原理l6.5.3.2 中斷處理中斷處理71

46、6.5.3.1 基本原理基本原理l所需表目所需表目l總頁表：即位示圖，內(nèi)存和外存各一個總頁表：即位示圖，內(nèi)存和外存各一個, 其形其形式與非虛擬存儲管理相同式與非虛擬存儲管理相同. l段表段表: 每個進(jìn)程一個每個進(jìn)程一個, 該表長度動態(tài)變化該表長度動態(tài)變化, 每連每連接一個新的段時接一個新的段時, 增加一個新的項(xiàng)目增加一個新的項(xiàng)目頁表長度頁表長度 頁表首址頁表首址 訪問權(quán)限訪問權(quán)限 擴(kuò)展標(biāo)志擴(kuò)展標(biāo)志 共享段入口共享段入口 段號段號72所需表目所需表目l頁表頁表: 每個段一個每個段一個, 進(jìn)程開始運(yùn)行時只為主進(jìn)程開始運(yùn)行時只為主程序段建立一個程序段建立一個, 其它段的頁表在段連接其它段的頁表在段連

47、接時建立時建立l共享段表共享段表: 整個系統(tǒng)一個整個系統(tǒng)一個, 記錄所有共享段記錄所有共享段邏輯頁號邏輯頁號內(nèi)存頁號內(nèi)存頁號 外存頁號外存頁號 內(nèi)外標(biāo)志內(nèi)外標(biāo)志 修改標(biāo)志修改標(biāo)志 .段名段名 頁表長度頁表長度 頁表首址頁表首址 擴(kuò)充標(biāo)志擴(kuò)充標(biāo)志 共享計(jì)數(shù)共享計(jì)數(shù) 73所需表目所需表目l段名段名段號對照表：每個進(jìn)程一個段號對照表：每個進(jìn)程一個74私用段私用段共享段共享段共享段表共享段表P1段表段表：P2段表：段表：各表之間聯(lián)系各表之間聯(lián)系 75共享段表共享段表P1段表：P2段表： 15 16 17 18 19 20 21 22 23 24 25 . .頁表頁表頁表頁表存儲空間：存儲空間：sisj

48、sk76所需寄存器所需寄存器 l段表首址寄存器段表首址寄存器 b：整個系統(tǒng)一個：整個系統(tǒng)一個, 保存保存正在運(yùn)行進(jìn)程段表首址正在運(yùn)行進(jìn)程段表首址l段表長度寄存器段表長度寄存器 l：整個系統(tǒng)一個：整個系統(tǒng)一個, 保存正保存正在運(yùn)行進(jìn)程段表長度在運(yùn)行進(jìn)程段表長度l在進(jìn)程運(yùn)行過程中可能動態(tài)變化在進(jìn)程運(yùn)行過程中可能動態(tài)變化l每連接一個新的段時其值加每連接一個新的段時其值加1l快表快表：每個進(jìn)程一個：每個進(jìn)程一個段號段號 邏輯頁號邏輯頁號 物理頁號物理頁號 訪問權(quán)限訪問權(quán)限 修改標(biāo)志修改標(biāo)志 77地址映射地址映射 l邏輯地址的形式為邏輯地址的形式為: (段號段號,邏輯頁號邏輯頁號,頁內(nèi)地址頁內(nèi)地址)(s

49、,p,d)l物理地址的形式為物理地址的形式為: (頁架號頁架號,頁內(nèi)地址頁內(nèi)地址)(f,d)78由由(s,p)查快表得查快表得f查到查到訪問合法訪問合法形成物理地址形成物理地址(f,d)是間址是間址有障礙位有障礙位繼續(xù)繼續(xù)0 s l-10 p l-1由由(s,b)查段表得查段表得b,l越界中斷越界中斷越界中斷越界中斷由由b和和p查頁表得查頁表得f該頁在內(nèi)存該頁在內(nèi)存缺頁中斷缺頁中斷(s,p,f)快表快表越權(quán)中斷越權(quán)中斷TFTF連接中斷連接中斷TFTFTFTFT796.5.3.2 中斷處理中斷處理 l連接中斷：由段名查本進(jìn)程的段名連接中斷：由段名查本進(jìn)程的段名段號對照表及共享段號對照表及共享段表

50、段表, 分三種情形分三種情形:l所有進(jìn)程都未連接過（共享段表、段名所有進(jìn)程都未連接過（共享段表、段名-段號對照表均無）段號對照表均無） 建立頁表，由文件全部讀入外存建立頁表，由文件全部讀入外存swap，部分頁讀入內(nèi)存，分配，部分頁讀入內(nèi)存，分配段號，填段名段號，填段名-段號對照表，如是共享段填共享段表，填段段號對照表，如是共享段填共享段表，填段表表 ，形成邏輯地址。，形成邏輯地址。l其它進(jìn)程連接過但本進(jìn)程未連接過其它進(jìn)程連接過但本進(jìn)程未連接過(共享段表有共享段表有, 段名段名-段號對照段號對照表無表無) 分配段號，填段名分配段號，填段名-段號對照表，填段表段號對照表，填段表(指向共享段表指向共

51、享段表)，共享，共享記數(shù)加記數(shù)加1, 形成邏輯地址。形成邏輯地址。l本進(jìn)程已連接過本進(jìn)程已連接過(共享段表無共享段表無, 段名段名-段號對照表有段號對照表有),形成邏輯地形成邏輯地址。址。806.5.3.2 中斷處理中斷處理l缺頁中斷缺頁中斷l(xiāng)調(diào)入所需頁面，更新頁表和總頁表。調(diào)入所需頁面，更新頁表和總頁表。l越界中斷越界中斷l(xiāng)段號越界：錯誤處理。段號越界：錯誤處理。l頁號越界：如可擴(kuò)展，擴(kuò)展該段頁號越界：如可擴(kuò)展，擴(kuò)展該段(增加頁增加頁)，修，修改頁表和段表改頁表和段表(頁表長頁表長); 如不可擴(kuò)展，錯誤處如不可擴(kuò)展，錯誤處理。理。l越權(quán)中斷越權(quán)中斷l(xiāng)違反段的訪問權(quán)限違反段的訪問權(quán)限, 程序?qū)?/p>

52、被中止程序?qū)⒈恢兄?81三種虛擬存儲系統(tǒng)的優(yōu)點(diǎn)和缺點(diǎn)三種虛擬存儲系統(tǒng)的優(yōu)點(diǎn)和缺點(diǎn) 826.6 系統(tǒng)舉例系統(tǒng)舉例lLinux存儲管理存儲管理lWindows2000/XP存儲管理存儲管理83Linux存儲管理存儲管理l頁式存儲管理不要求一個進(jìn)程的頁面在物頁式存儲管理不要求一個進(jìn)程的頁面在物理上連續(xù)理上連續(xù)lDMA傳輸在沒有地址映射條件下進(jìn)行，跨傳輸在沒有地址映射條件下進(jìn)行，跨頁的頁的DMA傳輸要求頁面物理上連續(xù)傳輸要求頁面物理上連續(xù)l連續(xù)物理頁面分配的問題是可能產(chǎn)生外碎連續(xù)物理頁面分配的問題是可能產(chǎn)生外碎片片(external fragmentation)l伙伴算法是針對外碎片問題而提出的一種伙

53、伴算法是針對外碎片問題而提出的一種穩(wěn)定、高效的分配策略穩(wěn)定、高效的分配策略 84Linux存儲管理存儲管理l伙伴堆伙伴堆(buddy heap)內(nèi)存分配算法內(nèi)存分配算法l將所有空閑頁面分為將所有空閑頁面分為10個塊組，塊組編號為個塊組，塊組編號為i (i=09)l塊組塊組i中記載長度為中記載長度為2i個頁面連續(xù)區(qū)域個頁面連續(xù)區(qū)域l第第1組中塊的大小均為組中塊的大小均為20(1頁頁)，第，第2組中塊的大小組中塊的大小均為均為21(2頁頁),第第10組中塊的大小均為組中塊的大小均為29(512頁頁). l同組中所有塊以鏈表形式組織同組中所有塊以鏈表形式組織85l申請長度為申請長度為128，在第，在

54、第8組中取一塊。組中取一塊。l若第若第8組已空，在第組已空，在第9組取一塊，分配其中的組取一塊，分配其中的128頁，并頁，并將剩余的將剩余的128頁記入第頁記入第8組。組。l若第若第9組也空，在第組也空，在第10組取一塊，進(jìn)行兩次分割，分配組取一塊，進(jìn)行兩次分割，分配128頁，剩余的頁，剩余的128頁和頁和256頁分別記入第頁分別記入第8組和第組和第9組組l釋放是上述操作的逆過程，兩個塊為伙伴的條件釋放是上述操作的逆過程，兩個塊為伙伴的條件是是:l兩個塊的大小相同，如兩個塊的大小相同，如b個頁面；個頁面；l兩個塊的物理地址連續(xù)；兩個塊的物理地址連續(xù)；l位于后面塊的最后頁面編號必須是位于后面塊的

55、最后頁面編號必須是2b的整數(shù)倍的整數(shù)倍8610(29)9(28) 8(27)4(23)3(22)2(21)1(20)Linux存儲管理存儲管理87buddy heap)內(nèi)存分配算法內(nèi)存分配算法Managing Physical MemorylAllocate ranges of physically-contiguous pages on request.（為進(jìn)程分配連續(xù)存儲區(qū)）（為進(jìn)程分配連續(xù)存儲區(qū)）lThe allocator uses a buddy-heap algorithm to keep track of available physical pages. (Buddy heap

56、算法記載可用存儲區(qū)）算法記載可用存儲區(qū)） Each allocatable memory region is paired with an adjacent partner.（每個可用存儲區(qū)有一個伙伴）（每個可用存儲區(qū)有一個伙伴）Whenever two allocated partner regions are both freed up they are combined to form a larger region.（兩個相鄰的伙伴被釋放時，（兩個相鄰的伙伴被釋放時，合并為一個大空閑區(qū)）合并為一個大空閑區(qū)） If a memory request cannot be satisfied

57、 by allocating an existing small free region, then a larger free region will be subdivided into two partners to satisfy the request.（小區(qū)域（小區(qū)域不能滿足時，分割大區(qū)域）不能滿足時，分割大區(qū)域）Linux存儲管理存儲管理l虛擬存儲管理虛擬存儲管理 l頁表分為三級頁表分為三級l無預(yù)調(diào)頁功能無預(yù)調(diào)頁功能l未采用工作集模型未采用工作集模型l系統(tǒng)守護(hù)進(jìn)程系統(tǒng)守護(hù)進(jìn)程kswapd每秒運(yùn)行一次，動態(tài)調(diào)每秒運(yùn)行一次，動態(tài)調(diào)整頁面分配，保持內(nèi)存有一定數(shù)量的空閑頁整頁面分配，保持內(nèi)存有一定數(shù)量的空閑頁面面lBdflush進(jìn)程周期性醒來并刷新進(jìn)程周期性醒來并刷新“臟頁臟頁” 906.6.2 Windows2000/XP存儲管理存儲管理 lWin32提供一組與存儲管理相關(guān)的調(diào)用，提供一組與存儲管理相關(guān)的調(diào)用，核心中有核心中有6個專門負(fù)責(zé)存儲管理的線程個專門負(fù)責(zé)存儲管理的線程l6.6.2.1 進(jìn)程地址空間進(jìn)程地址空間l6.6.2.2 存儲管理方式存儲管理方