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

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

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

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

4、一個(gè)鏈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界地址存儲(chǔ)管理外存空間分配界地址存儲(chǔ)管理外存空間分配 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)程在外存占有若干個(gè)塊進(jìn)程在外存占有若干

5、個(gè)塊, 塊的編號(hào)可以不連續(xù)塊的編號(hào)可以不連續(xù) l段式段式l每段占外存若干連續(xù)塊每段占外存若干連續(xù)塊l進(jìn)程的多個(gè)段之間在外存中可不連續(xù)進(jìn)程的多個(gè)段之間在外存中可不連續(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)多個(gè)頁所對應(yīng)的外存塊可不連續(xù)段內(nèi)多個(gè)頁所對應(yīng)的外存塊可不連續(xù)l一個(gè)進(jìn)程的多個(gè)段可分散在外存不同區(qū)域中一個(gè)進(jìn)程的多個(gè)段可分散在外存不同區(qū)域中76.5 虛擬存儲(chǔ)系統(tǒng)虛擬存儲(chǔ)系統(tǒng)l無虛擬存儲(chǔ)問題無虛擬存儲(chǔ)問題l不能運(yùn)行比內(nèi)存大的程序不能運(yùn)行比內(nèi)存大的程序l進(jìn)程全部裝入內(nèi)存，浪費(fèi)空間（進(jìn)

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

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

8、回外存，修改頁表和總頁表；l讀入所需頁面（切換進(jìn)程）；讀入所需頁面（切換進(jìn)程）；l啟動(dòng)進(jìn)程，重新執(zhí)行被中斷的指令。啟動(dòng)進(jìn)程，重新執(zhí)行被中斷的指令。106.5.1.1 基本原理基本原理l頁面調(diào)度需要執(zhí)行通道傳輸操作頁面調(diào)度需要執(zhí)行通道傳輸操作, 時(shí)間較長時(shí)間較長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ā)出中斷信號(hào)，將缺頁進(jìn)傳輸完成后硬件發(fā)出中斷信號(hào)，將缺頁進(jìn)程喚醒程喚醒l為實(shí)現(xiàn)虛擬頁式存儲(chǔ)管理為實(shí)現(xiàn)虛擬頁式存儲(chǔ)管理, 頁表中需要增加如下頁表中需要增加如下欄目：欄目：l外存頁號(hào)外存頁號(hào)l內(nèi)外標(biāo)志內(nèi)外標(biāo)志l修改標(biāo)志等修改

9、標(biāo)志等 11對頁表的改進(jìn)：對頁表的改進(jìn)：對快表的改進(jìn)：對快表的改進(jìn)：邏輯頁號(hào)邏輯頁號(hào) p . . . . . 頁架號(hào)頁架號(hào) 外存頁號(hào)外存頁號(hào) 內(nèi)外標(biāo)識(shí)內(nèi)外標(biāo)識(shí) 訪問權(quán)限訪問權(quán)限 修改標(biāo)志修改標(biāo)志 f p (0,1) r,w,e (0,1) . . . . . . . 邏輯頁號(hào)邏輯頁號(hào) 頁架號(hào)頁架號(hào) 訪問權(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個(gè)，每個(gè)進(jìn)程個(gè)，每個(gè)進(jìn)程5個(gè)頁面?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í)比例分配按進(jìn)程優(yōu)先級(jí)比例分配l為加速高優(yōu)先級(jí)進(jìn)程的執(zhí)行速度為加速高優(yōu)先級(jí)進(jìn)程的執(zhí)行速度, 可為其分配可為其分配較多的內(nèi)存頁面較多的內(nèi)存頁面l按進(jìn)程長度和優(yōu)先級(jí)別比例分

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

12、, 無論是否被修改無論是否被修改, 必需重新為其必需重新為其申請外存頁面申請外存頁面, 然后將該頁寫回外存然后將該頁寫回外存 l優(yōu)點(diǎn)：節(jié)省外存優(yōu)點(diǎn)：節(jié)省外存l缺點(diǎn)：速度慢缺點(diǎn)：速度慢-淘汰時(shí)必須寫回淘汰時(shí)必須寫回156.5.1.4 頁面調(diào)入時(shí)機(jī)頁面調(diào)入時(shí)機(jī)l有兩種方法有兩種方法: 請調(diào)和預(yù)調(diào)請調(diào)和預(yù)調(diào)l 請調(diào)請調(diào)(demand-paging)l當(dāng)頁故障發(fā)生時(shí)進(jìn)行調(diào)度當(dāng)頁故障發(fā)生時(shí)進(jìn)行調(diào)度l即當(dāng)訪問某一頁面而該頁面不在內(nèi)存時(shí)由動(dòng)態(tài)調(diào)即當(dāng)訪問某一頁面而該頁面不在內(nèi)存時(shí)由動(dòng)態(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)一個(gè)頁面即將被訪問之前由動(dòng)態(tài)調(diào)頁系統(tǒng)將即當(dāng)一個(gè)頁面即將被訪問之前由動(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)存時(shí)當(dāng)要訪問頁面不在內(nèi)存時(shí), 需將其調(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淘汰以后不再需要的淘汰以后不再需要的, 或者在最長時(shí)間以或者在最長時(shí)間以后才會(huì)用到的頁面后才會(huì)用到的頁面 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個(gè)物理頁架個(gè)物理頁架, 開始時(shí)開始時(shí)內(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í)實(shí)現(xiàn)時(shí), 每個(gè)頁面有一個(gè)調(diào)入時(shí)間每個(gè)頁面有一個(gè)調(diào)入時(shí)間, 該時(shí)間可該時(shí)間可在內(nèi)存中用軟件記錄在內(nèi)存中用軟件記錄, 最好設(shè)在寄存器中并由最好設(shè)在寄存器中并由硬件

16、記錄硬件記錄l當(dāng)內(nèi)存空間緊張時(shí)當(dāng)內(nèi)存空間緊張時(shí), 調(diào)入時(shí)間最早的頁面將被調(diào)入時(shí)間最早的頁面將被淘汰淘汰l該算法也可以這樣實(shí)現(xiàn)該算法也可以這樣實(shí)現(xiàn)l將所有頁面按照進(jìn)入內(nèi)存的次序排成一個(gè)隊(duì)將所有頁面按照進(jìn)入內(nèi)存的次序排成一個(gè)隊(duì)列列l(wèi)當(dāng)一個(gè)頁面由外存調(diào)入內(nèi)存時(shí)排入隊(duì)尾當(dāng)一個(gè)頁面由外存調(diào)入內(nèi)存時(shí)排入隊(duì)尾l當(dāng)需要淘汰時(shí)取隊(duì)頭的頁面當(dāng)需要淘汰時(shí)取隊(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個(gè)物理頁面：頁

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

18、時(shí)器中到對應(yīng)的訪問時(shí)間記時(shí)器中l(wèi)系統(tǒng)記錄了內(nèi)存中所有頁面最后一次被訪問的時(shí)系統(tǒng)記錄了內(nèi)存中所有頁面最后一次被訪問的時(shí)間間l淘汰時(shí)淘汰時(shí), 選取訪問時(shí)間記時(shí)器中值最小者所對應(yīng)的選取訪問時(shí)間記時(shí)器中值最小者所對應(yīng)的頁面頁面24使用過最久的先淘汰使用過最久的先淘汰(Least Recently Used，LRU)l棧法棧法: l按照頁面最后一次訪問的時(shí)間次序?qū)㈨撁嫣?hào)依次按照頁面最后一次訪問的時(shí)間次序?qū)㈨撁嫣?hào)依次地排列到棧中地排列到棧中l(wèi)當(dāng)一個(gè)頁面被訪問時(shí)當(dāng)一個(gè)頁面被訪問時(shí), 其對應(yīng)的頁面號(hào)由棧內(nèi)取出其對應(yīng)的頁面號(hào)由棧內(nèi)取出送入棧頂送入棧頂l淘汰時(shí)淘汰時(shí), 取棧底頁面號(hào)所對應(yīng)的頁面取棧底頁面號(hào)所對應(yīng)的

19、頁面l這里的這里的“棧棧”不是通常所定義的不是通常所定義的LIFO棧棧l使用雙向鏈來構(gòu)造，其鏈頭和鏈尾各需一個(gè)指針使用雙向鏈來構(gòu)造，其鏈頭和鏈尾各需一個(gè)指針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)其速度至少會(huì)降低完全由軟件實(shí)現(xiàn)其速度至少

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

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

22、有引用位都清0l要淘汰某一頁面時(shí)要淘汰某一頁面時(shí), 按照下面次序選擇按照下面次序選擇: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í)實(shí)現(xiàn)時(shí), 為每一個(gè)頁面設(shè)一個(gè)訪問次數(shù)計(jì)為每一個(gè)頁面設(shè)一個(gè)訪問次數(shù)計(jì)數(shù)器數(shù)器l當(dāng)

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

24、被淘汰被淘汰l一種彌補(bǔ)方法是定時(shí)將計(jì)數(shù)值右移一種彌補(bǔ)方法是定時(shí)將計(jì)數(shù)值右移, 形成按時(shí)間指形成按時(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顛簸又譯抖動(dòng)顛

25、簸又譯抖動(dòng), 指頁面在內(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)移指令、分散的全局變量都會(huì)破壞程序的局部性變量都會(huì)破壞程序的局部性, 從而增加頁故障從而增加頁故障率率, 甚至引起顛簸甚至引起顛簸 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)度頁面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行所系統(tǒng)用于調(diào)度頁面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行所占用的時(shí)間要多占用的時(shí)間要多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在某些虛擬頁式存儲(chǔ)管理系統(tǒng)中，內(nèi)存中總在某些虛擬頁式存儲(chǔ)管理系統(tǒng)中，內(nèi)存中總保持一個(gè)空閑的物理頁面，這樣做有什么好保持一個(gè)空閑的物理頁面，這樣做有什么好處？處？376.5.1.7 工作集模型工作集模型(working set model)l工作集模型由工作集模型由Denning提出提出l工作集工作集(working set)是進(jìn)程在一段時(shí)間之是進(jìn)程在一段時(shí)間之內(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)程從時(shí)刻一進(jìn)程從時(shí)刻(t-)到時(shí)刻到時(shí)刻t之間所訪之間所訪問頁面的集合問頁面的集合WS(t,)稱作該進(jìn)程的工作集稱作該進(jìn)程的工作集l如圖如圖 6-41 所示，所示，稱作窗口尺寸稱作窗口尺寸(windows size)396.5.1.7 工作集模型工作集模型(working set model)l工作集是隨時(shí)間而變化的工作集是隨時(shí)間而變化的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過小過小, 程序活動(dòng)頁面不能全部裝入內(nèi)存程序活動(dòng)頁面不能全部裝入內(nèi)存, 頁故障率高頁故障率高l過大過大, 允許同時(shí)并發(fā)執(zhí)行進(jìn)程的個(gè)數(shù)降低允許同時(shí)并發(fā)執(zhí)行

30、進(jìn)程的個(gè)數(shù)降低lMadnick和和Donovan建議建議大約為大約為10,000次訪問內(nèi)存次訪問內(nèi)存l實(shí)現(xiàn)：頁表中增加訪問位：實(shí)現(xiàn)：頁表中增加訪問位： l開始時(shí)，全部清開始時(shí)，全部清0, 訪問：置訪問：置1,l結(jié)束時(shí)結(jié)束時(shí)(新新開始時(shí)開始時(shí))訪問標(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)利用頁故障率的反饋信息來動(dòng)態(tài)地調(diào)系統(tǒng)利用頁故障率的反饋信息來動(dò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 虛擬段式存儲(chǔ)系統(tǒng)虛擬段式存儲(chǔ)系統(tǒng)l6.5.2.1

32、 基本原理基本原理 l6.5.2.2 段的動(dòng)態(tài)連接段的動(dòng)態(tài)連接456.5.2.1 基本原理基本原理l思想與虛擬頁式相似思想與虛擬頁式相似, 只是將頁變化為段只是將頁變化為段l進(jìn)程運(yùn)行前將主程序段裝入內(nèi)存進(jìn)程運(yùn)行前將主程序段裝入內(nèi)存, 其它段其它段裝入外存裝入外存l運(yùn)行時(shí)所需的段如不在內(nèi)存運(yùn)行時(shí)所需的段如不在內(nèi)存, 將其動(dòng)態(tài)調(diào)將其動(dòng)態(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) . . . .段號(hào)段號(hào) s . 段長段長 內(nèi)存首址內(nèi)存首址 外存首址外存首址 權(quán)限權(quán)限 內(nèi)外標(biāo)識(shí)內(nèi)外標(biāo)識(shí) 修改標(biāo)志修改標(biāo)志 l b b” rwe (0,1) (0,1) . . . .48 . . . . 段號(hào)段號(hào) 段長段長 內(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 段的動(dòng)態(tài)連接段的動(dòng)態(tài)連接(dynamic linking)l動(dòng)態(tài)連接動(dòng)態(tài)連接 vs. 靜態(tài)連接靜態(tài)連接l靜態(tài)連接：運(yùn)行前連接，由靜態(tài)連接：運(yùn)行前連接，由link完成完成l動(dòng)態(tài)連接：運(yùn)行時(shí)連接，由動(dòng)態(tài)連接：運(yùn)行時(shí)連接，由OS完成完成l靜態(tài)連接的缺點(diǎn)靜態(tài)連接的缺點(diǎn)l連接時(shí)間長；連接時(shí)間長；l目標(biāo)代碼長；目標(biāo)代碼長；l連接段可能并不執(zhí)行連接段可能并不執(zhí)行(未用到未用到)50動(dòng)態(tài)連接的實(shí)現(xiàn)動(dòng)態(tài)連接的實(shí)現(xiàn) l在靜態(tài)連接中在靜態(tài)連接中, 程序共有多少個(gè)段是確定的程序共有多少個(gè)段是確定的, 連連接裝配程序?yàn)槊總€(gè)段分配一個(gè)段號(hào)接裝配程序?yàn)槊總€(gè)段分配一個(gè)段號(hào), 即即段名到段

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

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

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

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

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

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

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

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

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

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

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

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

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

49、,p,d)l物理地址的形式為物理地址的形式為: (頁架號(hào)頁架號(hào),頁內(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)程的段名段號(hào)對照表及共享段號(hào)對照表及共享段表

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

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

52、被中止程序?qū)⒈恢兄?81三種虛擬存儲(chǔ)系統(tǒng)的優(yōu)點(diǎn)和缺點(diǎn)三種虛擬存儲(chǔ)系統(tǒng)的優(yōu)點(diǎn)和缺點(diǎn) 826.6 系統(tǒng)舉例系統(tǒng)舉例lLinux存儲(chǔ)管理存儲(chǔ)管理lWindows2000/XP存儲(chǔ)管理存儲(chǔ)管理83Linux存儲(chǔ)管理存儲(chǔ)管理l頁式存儲(chǔ)管理不要求一個(gè)進(jìn)程的頁面在物頁式存儲(chǔ)管理不要求一個(gè)進(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存儲(chǔ)管理存儲(chǔ)管理l伙伴堆伙伴堆(buddy heap)內(nèi)存分配算法內(nèi)存分配算法l將所有空閑頁面分為將所有空閑頁面分為10個(gè)塊組，塊組編號(hào)為個(gè)塊組，塊組編號(hào)為i (i=09)l塊組塊組i中記載長度為中記載長度為2i個(gè)頁面連續(xù)區(qū)域個(gè)頁面連續(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釋放是上述操作的逆過程，兩個(gè)塊為伙伴的條件釋放是上述操作的逆過程，兩個(gè)塊為伙伴的條件是是:l兩個(gè)塊的大小相同，如兩個(gè)塊的大小相同，如b個(gè)頁面；個(gè)頁面；l兩個(gè)塊的物理地址連續(xù)；兩個(gè)塊的物理地址連續(xù)；l位于后面塊的最后頁面編號(hào)必須是位于后面塊的

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

56、算法記載可用存儲(chǔ)區(qū)）算法記載可用存儲(chǔ)區(qū)） Each allocatable memory region is paired with an adjacent partner.（每個(gè)可用存儲(chǔ)區(qū)有一個(gè)伙伴）（每個(gè)可用存儲(chǔ)區(qū)有一個(gè)伙伴）Whenever two allocated partner regions are both freed up they are combined to form a larger region.（兩個(gè)相鄰的伙伴被釋放時(shí)，（兩個(gè)相鄰的伙伴被釋放時(shí)，合并為一個(gè)大空閑區(qū)）合并為一個(gè)大空閑區(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ū)域不能滿足時(shí)，分割大區(qū)域）不能滿足時(shí)，分割大區(qū)域）Linux存儲(chǔ)管理存儲(chǔ)管理l虛擬存儲(chǔ)管理虛擬存儲(chǔ)管理 l頁表分為三級(jí)頁表分為三級(jí)l無預(yù)調(diào)頁功能無預(yù)調(diào)頁功能l未采用工作集模型未采用工作集模型l系統(tǒng)守護(hù)進(jìn)程系統(tǒng)守護(hù)進(jìn)程kswapd每秒運(yùn)行一次，動(dòng)態(tài)調(diào)每秒運(yùn)行一次，動(dòng)態(tài)調(diào)整頁面分配，保持內(nèi)存有一定數(shù)量的空閑頁整頁面分配，保持內(nèi)存有一定數(shù)量的空閑頁面面lBdflush進(jìn)程周期性醒來并刷新進(jìn)程周期性醒來并刷新“臟頁臟頁” 906.6.2 Windows2000/XP存儲(chǔ)管理存儲(chǔ)管理 lWin32提供一組與存儲(chǔ)管理相關(guān)的調(diào)用，提供一組與存儲(chǔ)管理相關(guān)的調(diào)用，核心中有核心中有6個(gè)專門負(fù)責(zé)存儲(chǔ)管理的線程個(gè)專門負(fù)責(zé)存儲(chǔ)管理的線程l6.6.2.1 進(jìn)程地址空間進(jìn)程地址空間l6.6.2.2 存儲(chǔ)管理方式存儲(chǔ)管理方