1、第六章第六章 存儲管理存儲管理l6.1 存儲管理功能存儲管理功能l6.2 內存資源管理內存資源管理l6.3 存儲管理方式存儲管理方式l6.4 外存空間管理外存空間管理l6.5 虛擬存儲系統虛擬存儲系統 16.4 外存資源管理外存資源管理l外存空間指磁盤等存儲型設備上的存儲區域外存空間指磁盤等存儲型設備上的存儲區域l邏輯上劃分為四個部分：輸入井、輸出井、文邏輯上劃分為四個部分：輸入井、輸出井、文件空間、交換空間件空間、交換空間l輸入井和輸出井用于實現作業的預輸入和作業的緩輸輸入井和輸出井用于實現作業的預輸入和作業的緩輸出出l文件空間用于保存文件文件空間用于保存文件l交換空間或對換空間用于實現虛擬

2、存儲的外存空間交換空間或對換空間用于實現虛擬存儲的外存空間, 在分級存儲體系中在分級存儲體系中, 可看成是內存的擴充可看成是內存的擴充Swap空間空間File空間空間輸入輸入井井輸出輸出井井26.4.1 外存空間劃分外存空間劃分 l存儲空間可看成是物理塊所構成的有序存儲空間可看成是物理塊所構成的有序序列序列l所有塊的長度相同所有塊的長度相同, 通常為通常為2i, 如如256字節、字節、512字節、字節、1024字節等字節等l這些塊由這些塊由0開始依次地編號開始依次地編號, 稱作稱作塊號塊號l塊是外存分配的基本單位塊是外存分配的基本單位, 也是也是I/O傳輸的基傳輸的基本單位本單位 36.4.2

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

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

5、個塊, 塊的編號可以不連續塊的編號可以不連續 l段式段式l每段占外存若干連續塊每段占外存若干連續塊l進程的多個段之間在外存中可不連續進程的多個段之間在外存中可不連續 6進程與外存對應關系進程與外存對應關系l段頁式段頁式l內存頁面長度與外存塊長度相同內存頁面長度與外存塊長度相同l內存一頁，外存一塊內存一頁，外存一塊l段內多個頁所對應的外存塊可不連續段內多個頁所對應的外存塊可不連續l一個進程的多個段可分散在外存不同區域中一個進程的多個段可分散在外存不同區域中76.5 虛擬存儲系統虛擬存儲系統l無虛擬存儲問題無虛擬存儲問題l不能運行比內存大的程序不能運行比內存大的程序l進程全部裝入內存，浪費空間（進

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

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

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

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

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

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

12、, 無論是否被修改無論是否被修改, 必需重新為其必需重新為其申請外存頁面申請外存頁面, 然后將該頁寫回外存然后將該頁寫回外存 l優點：節省外存優點：節省外存l缺點：速度慢缺點：速度慢-淘汰時必須寫回淘汰時必須寫回156.5.1.4 頁面調入時機頁面調入時機l有兩種方法有兩種方法: 請調和預調請調和預調l 請調請調(demand-paging)l當頁故障發生時進行調度當頁故障發生時進行調度l即當訪問某一頁面而該頁面不在內存時由動態調即當訪問某一頁面而該頁面不在內存時由動態調頁系統將其調入內存頁系統將其調入內存l預調預調(pre-paging)l 也稱先行調度：當頁故障發生前進行調度也稱先行調度：

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

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

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

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

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

18、時器中到對應的訪問時間記時器中l系統記錄了內存中所有頁面最后一次被訪問的時系統記錄了內存中所有頁面最后一次被訪問的時間間l淘汰時淘汰時, 選取訪問時間記時器中值最小者所對應的選取訪問時間記時器中值最小者所對應的頁面頁面24使用過最久的先淘汰使用過最久的先淘汰(Least Recently Used，LRU)l棧法棧法: l按照頁面最后一次訪問的時間次序將頁面號依次按照頁面最后一次訪問的時間次序將頁面號依次地排列到棧中地排列到棧中l當一個頁面被訪問時當一個頁面被訪問時, 其對應的頁面號由棧內取出其對應的頁面號由棧內取出送入棧頂送入棧頂l淘汰時淘汰時, 取棧底頁面號所對應的頁面取棧底頁面號所對應的

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

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

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

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

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

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

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

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

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

28、到內存中386.5.1.7 工作集模型工作集模型(working set model)l準確地說準確地說, 一進程從時刻一進程從時刻(t-)到時刻到時刻t之間所訪之間所訪問頁面的集合問頁面的集合WS(t,)稱作該進程的工作集稱作該進程的工作集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工作集大小與窗口尺寸工作集大小與窗口尺寸密切相關密切相關, 程序大小程序大小 WS416.5.1.7 工作集模型工作集模型(working set model)l工作集模型的精確度與工作集模型的精確度與密切相關密切相關l過小過小, 程序活動頁面不能全部裝入內存程序活動頁面不能全部裝入內存, 頁故障率高頁故障率高l過大過大, 允許同時并發執行進程的個數降低允許同時并發執行

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

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

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

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

34、表的改進快表的改進496.5.2.2 段的動態連接段的動態連接(dynamic linking)l動態連接動態連接 vs. 靜態連接靜態連接l靜態連接：運行前連接，由靜態連接：運行前連接，由link完成完成l動態連接：運行時連接，由動態連接：運行時連接，由OS完成完成l靜態連接的缺點靜態連接的缺點l連接時間長；連接時間長；l目標代碼長；目標代碼長；l連接段可能并不執行連接段可能并不執行(未用到未用到)50動態連接的實現動態連接的實現 l在靜態連接中在靜態連接中, 程序共有多少個段是確定的程序共有多少個段是確定的, 連連接裝配程序為每個段分配一個段號接裝配程序為每個段分配一個段號, 即即段名到段

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

36、 .52動態連接的實現動態連接的實現l將一個外段中的符號名轉換為對應的段內地址將一個外段中的符號名轉換為對應的段內地址, 每個段在編譯每個段在編譯(匯編匯編)時時, 需生成一個符號表需生成一個符號表, 放在放在一個段的前面一個段的前面, 作為段的一個組成部分作為段的一個組成部分l符號表如圖所示符號表如圖所示符號名符號名 段內位移段內位移 func 150 . .53動態連接的實現動態連接的實現l一個段由符號表和目標程序一個段由符號表和目標程序(或者數據或者數據)兩兩部分構成部分構成, 如圖所示如圖所示段形式：段形式：符號表符號表目標代碼目標代碼或者數據或者數據54動態連接需要經過的步驟動態連接

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

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

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

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

41、編后連接后匯編后連接后 lW段段: 已連接已連接在內存在內存 X段段: 已連接已連接在內存在內存l進程空間各段進程空間各段, 以及各表形式如圖以及各表形式如圖 650 所示所示6263實例實例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動態連接問題動態連接問題l動態連接與共享的矛盾動態連接與共享的矛盾l動態連接：修改連接字（代碼）動態連接：修改連接字（代碼）l段的共享：要求純代碼（段的共享：要求純代碼（pure code)l解決方法解決方法l共享代碼分為共享代碼分為“純段純段”和和“雜段雜段”l純段共享，純段共享，l雜段私用。雜段私用。686.5.3 虛擬段頁式存儲系統虛擬段頁式存儲系統l虛擬頁式：將存儲空間靜態地劃分為長度虛擬頁式：將

44、存儲空間靜態地劃分為長度相同的區域相同的區域, l優點：簡化存儲分配優點：簡化存儲分配, 消除消除“碎片碎片”問題問題. l缺點：只提供一維地址缺點：只提供一維地址, 進程空間不能動態擴進程空間不能動態擴充充, 無法實現程序段的動態連接無法實現程序段的動態連接. l頁式存儲管理也能實現存儲的共享和保護頁式存儲管理也能實現存儲的共享和保護l由于以頁為基本單位由于以頁為基本單位, 頁面長度與程序基本單頁面長度與程序基本單位長度不等位長度不等, 實現起來比較麻煩實現起來比較麻煩696.5.3 虛擬段頁式存儲系統虛擬段頁式存儲系統l虛擬段式：將存儲空間動態地劃分為長度虛擬段式：將存儲空間動態地劃分為長

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

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

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

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

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

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

51、享段表)，共享，共享記數加記數加1, 形成邏輯地址。形成邏輯地址。l本進程已連接過本進程已連接過(共享段表無共享段表無, 段名段名-段號對照表有段號對照表有),形成邏輯地形成邏輯地址。址。806.5.3.2 中斷處理中斷處理l缺頁中斷缺頁中斷l調入所需頁面，更新頁表和總頁表。調入所需頁面，更新頁表和總頁表。l越界中斷越界中斷l段號越界：錯誤處理。段號越界：錯誤處理。l頁號越界：如可擴展，擴展該段頁號越界：如可擴展，擴展該段(增加頁增加頁)，修，修改頁表和段表改頁表和段表(頁表長頁表長); 如不可擴展，錯誤處如不可擴展，錯誤處理。理。l越權中斷越權中斷l違反段的訪問權限違反段的訪問權限, 程序將

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

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

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

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

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