1、6.4 外存管理技術(shù)外存邏輯劃分 輸入井, 輸出井: 作業(yè)預輸入/作業(yè)緩輸出; 虛擬設備。 文件空間: 用于保存文件 ; 文件系統(tǒng)。 交換空間: 也叫對換空間。 實現(xiàn)虛擬存儲的外存空間 ; 內(nèi)存的擴充。 靜態(tài)等長, 2i , 稱為一塊 (block) ; 塊由0開始依次編號, 稱為塊號; 塊是外存分配的基本單位 ; 也是I/O傳輸?shù)幕締挝弧?.4.1 外存空間劃分6.4.2 外存空間分配 空閑塊鏈(慢) ; 空閑塊表(UNIX) ; 位示圖(字位映像圖): 每位代表塊狀態(tài)。 6.4.2 外存空間分配(Cont.)界地址: 塊首址, 塊個數(shù) 每個進程占一組連續(xù)外存塊 ; 每個進程占二組外存連續(xù)

2、塊 (雙對界)。頁 式: 內(nèi)存一頁, 外存一塊。段 式: 每段占若干連續(xù)外存塊。段頁式: 內(nèi)存一頁, 外存一塊。進程與外存對應關(guān)系為實現(xiàn)外存管理，采用與內(nèi)存同樣的數(shù)據(jù)結(jié)構(gòu)，并且這些數(shù)據(jù)結(jié)構(gòu)在內(nèi)存的系統(tǒng)區(qū)定義。6.5 虛擬存儲系統(tǒng)無虛擬問題 不能運行比內(nèi)存大的程序 ; 進程全部裝入內(nèi)存, 浪費空間 進程活動具有局部性: 時間局部性和空間局部性。虛擬存儲 進程部分裝入內(nèi)存, 部分 (或全部) 裝入外存; 運行時訪問在外存部分動態(tài)調(diào)入, 內(nèi)存不夠淘汰。6.5.1 虛擬頁式存儲管理1. 基本原理 進程運行前 全部 ( 或部分 ) 裝入外存，部分裝入內(nèi)存。 進程運行時: 訪問頁面不在內(nèi)存, 則產(chǎn)生缺頁中

3、斷, 進程進入等待狀態(tài), 系統(tǒng)頁面動態(tài)調(diào)度: 找到被訪問頁面在外存的地址; 在內(nèi)存找一空閑頁框 ; 如沒有, 按淘汰算法選擇一個頁面 p ; (當頁面P被修改時)將頁面 p寫回外存, 修改頁表和總頁表 ; 讀入所需頁面, 修改頁表及頁框分配表 ; 重新啟動進程(進程切換), 執(zhí)行被中斷的指令。6.5.1 虛擬頁式存儲管理(Cont.)虛擬頁式存儲管理地址映射指令給出邏輯地址(p,d)由p查快表得到 f查到 f、d合并得到物理地址0pl-1越界中斷由b、p查找頁表該頁在內(nèi)存缺頁中斷保存現(xiàn)場有空閑頁框選一頁面淘汰該頁面修改過寫回外存讀入所需頁面更新頁表和快表恢復現(xiàn)場FFFTTT( f,d) 快表如

4、快表滿，則淘汰一表項硬件完成軟件完成結(jié) 束T6.5.1 虛擬頁式存儲管理(Cont.)對頁表的改進:邏輯頁號頁框號外存塊號訪問權(quán)限內(nèi)外標志修改標志 pfbr,w,e1,01,0對快表的改進:邏輯頁號頁框號訪問權(quán)限修改標志 pfr,w,e1,0 6.5.1 虛擬頁式存儲管理(Cont.)2. 內(nèi)存頁框分配策略(靜態(tài)策略) 平均分配 如內(nèi)存128頁框, 進程25個, 每個進程5個頁框。 按進程長度比例分配 系統(tǒng)有n個進程, pi 共 si 個頁面(i=1,n), 內(nèi)存共m個頁框, 則進程 pi 分配的頁框數(shù)為: ai = (si/(sj ) m 按進程優(yōu)先級比例分配 高優(yōu)先級進程多分頁架, 公式中

5、 si 改為優(yōu)先級。 按進程長度和優(yōu)先級別比例分配: 公式中 si 改為 “ si + 優(yōu)先級 ” 。j=1n靜態(tài)策略沒有反映: 程序結(jié)構(gòu) ; 程序在不同時刻的行為特性。3. 外存塊的分配策略 靜態(tài)分配: 外存始終保存進程的全部頁面。 某頁面調(diào)入內(nèi)存時, 外存頁面也不釋放; 優(yōu)點: 速度快淘汰時不必寫回(未修改情況) ; 缺點: 外存浪費; 動態(tài)分配: 外存僅保存進程不在內(nèi)存的頁面。 某頁面調(diào)入內(nèi)存時, 釋放外存頁面; 優(yōu)點: 節(jié)省外存; 缺點: 速度慢淘汰時必須寫回。6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)4. 頁面調(diào)入時機 請 調(diào)(demand paging) upon page fau

6、lt, 發(fā)生缺頁中斷時調(diào)入。 優(yōu) 點: 不會發(fā)生無意義的頁面調(diào)度; 缺 點: 缺頁中斷時進程等待, 影響進程推進。 預 調(diào)(prepaging) before page fault, 也叫先行調(diào)度。 將要訪問時調(diào)入(根據(jù)程序順序行為, 不一定準) ; 預調(diào)必須輔以請調(diào)。 優(yōu) 點: 降低缺頁故障率; 缺 點: 實現(xiàn)開銷大。6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)5. 置換算法(replacement algorithm) 也叫淘汰算法(removing algorithm) 作 用: 頁淘汰、段淘汰、快表淘汰。 目 的: lowest fault rate. 分 類: 局部置換和全局置換。 局

7、部置換: 在缺頁進程的頁框集中選擇淘汰頁面。 全局置換: 在內(nèi)存所有頁框集中選擇淘汰頁面。6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)6.5.1 虛擬頁式存儲系統(tǒng)(Cont.) 最佳淘汰算法(OPT-optimal) 淘汰將來最長時間以后才用到的頁面。 效率最高，not feasible。 例 OPT淘汰算法: 設進程 P 分配 3 個內(nèi)存頁框。頁面訪問序列50120304230321201501頁框 f155522222222222222555頁框 f20000004440000000000頁框 f3111333333331111111淘汰頁面510432缺頁故障缺頁故障 9 次6.5.1 虛

8、擬頁式存儲系統(tǒng)(Cont.) 先進先出(FIFO): 淘汰最先調(diào)入的頁面。 依據(jù): 先進入的可能已經(jīng)使用完畢; (如: 初始化段) 實現(xiàn): 記錄裝入時間；隊列。 negative case: 有些代碼和數(shù)據(jù)可能整個程序運行中用到。例 FIFO淘汰算法: 設進程 P 分配 3 個內(nèi)存頁框。頁面訪問序列50120304230321201501頁框 f155522224440000000555頁框 f20000333222221111100頁框 f3111100033333222221淘汰頁面501230423012缺頁故障缺頁故障 15 次6.5.1 虛擬頁式存儲系統(tǒng)(Cont.) Belady異

9、常: 采用FIFO淘汰算法時, 如果某進程未分配它所需要的全部頁框, 有時會出現(xiàn)分配的頁框數(shù)增多 但缺頁率反而提高的異?，F(xiàn)象。 Belady異常描述: 進程 P 要訪問 M 個頁面, OS分配 N (NM)個內(nèi)存頁框給進程 P ; 對一個訪問序列 S, 發(fā)生缺頁次數(shù)為PE (S, N)。 當 N 增大時, PE (S, N) 時而增大時而減小。例子Belady異常 設進程 P 頁面訪問序列為: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 56.5.1 虛擬頁式存儲系統(tǒng)(Cont.)分配頁框數(shù)頁面訪問序列1234125123453頁框 f1111444555555頁框 f2

10、22211111333頁框 f33332222244淘汰頁面123412缺頁故障9分配頁框數(shù)頁面訪問序列1234125123454頁框 f1111111555544頁框 f222222211115頁框 f33333332222頁框 f4444444333淘汰頁面123451缺頁故障106.5.1 虛擬頁式存儲系統(tǒng)(Cont.) 最近最少使用的先淘汰(Least-Recently-Used, LRU): 淘汰最后一次訪問時間距當前時間間隔最長的頁面。 實現(xiàn): 計時法: 對每個頁面增設訪問時間計時器。 當頁面被訪問時, 把絕對時間記錄到頁面計時器中; 淘汰時選頁面計時器中時間值最小的頁面淘汰。 棧

11、: 設置頁面訪問 “?！?非真正意義的LIFO棧)。 頁面 p 被訪問時, 刪除棧內(nèi)的 p , 再將 p 壓入棧; 淘汰時選棧底的頁面淘汰。OPT用于S的頁故障率=LRU用于R(S)的頁故障率。6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)例 LRU淘汰算法: 設進程 P 分配 3 個內(nèi)存頁架。頁面訪問序列50120304230321201501頁框 f155522224440001111111頁框 f20000000033333300000頁框 f3111333222222222555淘汰頁面512300032缺頁故障棧5 0120304230321201501缺頁故障 12 次LRU開銷大，需

12、硬件支持。完全由軟件實現(xiàn)，其速度至少降低90！6.5.1 虛擬頁式存儲系統(tǒng)(Cont.) 最近不用的先淘汰(Not-Used-Recently, NUR): 淘汰最近一段時間內(nèi)未用過的頁面。效率: 流行、低開銷、接近LRU效果。 實 現(xiàn): 每個頁面增設兩個硬件位:0 , 此頁未被訪問過 引用位 =1 , 此頁曾被訪問過0 , 此頁未被修改過 修改位 =1 , 此頁曾被修改過 位的修改: 頁面調(diào)入內(nèi)存時, 引用位、修改位均為0; 頁面執(zhí)行寫操作, 引用位、修改位均置為1; 頁面執(zhí)行讀操作, 引用位置為1; 每隔一段固定時間(最近), 將所有引用位都清0。6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)

13、 淘汰次序: 引用位=0、修改位=0, 直接淘汰; 引用位=0、修改位=1, 淘汰前寫回外存; 引用位=1、修改位=0, 直接淘汰; 引用位=1、修改位=1, 淘汰前寫回外存。頁面訪問序列5012102323040251頁框 f15555555333333355頁框 f2000000000000000頁框 f311111111144441頁框 f42222222222222淘汰頁面5134缺頁故障f1訪問標志1111000101110011f2訪問標志0111011100111111f3訪問標志0011111100010001f4訪問標志0001001111110111 最不經(jīng)常使用的先淘汰(

14、LFU): 淘汰使用次數(shù)最少的。 依據(jù): 活躍訪問頁面應有較大的訪問次數(shù). 不足: 前期使用多, 但以后不用, 難換出; 剛調(diào)入的頁面, 引用少, 被換出可能大。 實現(xiàn): 每個頁面設訪問次數(shù)計數(shù)器; 調(diào)入頁面, 其頁面計數(shù)器清0, 訪問增1 ; 淘汰選取計數(shù)器值最小的頁面。 最頻繁使用的先淘汰(MFU): 淘汰使用次數(shù)最多的。 依據(jù): 使用多的可能已經(jīng)用完了。 不足: 程序有些成分是在整個程序運行中都使用的。6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)6.5.1 虛擬頁式存儲系統(tǒng)(Cont.) 二次機會算法(second chance) 淘汰裝入最久且最近未被訪問的頁面。實 現(xiàn)：采用鏈式隊列數(shù)據(jù)

15、結(jié)構(gòu)。例: 某進程分配8個頁框，訪問頁面2時發(fā)生缺頁中斷。6/13/14/08/05/19/00/01/18/05/19/00/01/16/03/02/13/14/08/05/19/00/01/16/04/08/05/19/00/01/16/03/0 時鐘算法(clock algorithm)將頁面組織成環(huán)形，有一個指針指向當前位置。每次需要淘汰頁面時，從指針所指的頁面開始檢查:如果當前頁面訪問位為0，即從上次檢測到目前, 該頁沒有訪問過, 則將該頁淘汰;如果當前頁面的訪問位為1, 則將其清0, 順時針移動指針到下一個位置。重復上述步驟直至找到一個訪問位為0的頁面。6.5.1 虛擬頁式存儲系統(tǒng)

16、(Cont.) 時鐘算法與二次機會算法的淘汰效果基本相同； 采用的數(shù)據(jù)結(jié)構(gòu)不同： 二次機會使用的是鏈表，需要額外存儲空間，摘鏈入鏈速度很慢； 時鐘算法可直接利用頁表中的引用位，外加一個指針，速度快且節(jié)省空間。6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)頁6/r=1頁3/r=1頁4/r=0頁8/r=0頁10/r=1頁9/r=0頁0/r=0頁1/r=1框12框23框51框6框81框96框60框5訪問第18頁時鐘算法頁6/r=0頁3/r=1頁4/r=0頁8/r=0頁10/r=1頁9/r=0頁0/r=0頁1/r=1框12框23框51框6框81框96框60框5訪問第18頁6.5.1 虛擬頁式存儲系統(tǒng)(Co

17、nt.)時鐘算法6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)頁6/r=0頁3/r=0頁4/r=0頁8/r=0頁10/r=1頁9/r=0頁0/r=0頁1/r=1框12框23框51框6框81框96框60框5訪問第18頁時鐘算法6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)頁6/r=0頁3/r=0頁18/r=1頁8/r=0頁10/r=1頁9/r=0頁0/r=0頁1/r=1框12框23框51框6框81框96框60框5替換第4頁 改進的時鐘算法考慮修改標志mr=0, m=0：最佳淘汰頁面r=0, m=1：淘汰前回寫r=1, m=0：不淘汰r=1, m=1：不淘汰6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)6.5

18、.1 虛擬頁式存儲系統(tǒng)(Cont.) 改進的時鐘算法S1: 由指針當前位置開始掃描, 將第一個遇到的 r=0 且 m=0 的頁面作為淘汰頁面; 掃描過程中不改變引用位;S2: 若S1失敗, 再次從原位置開始掃描, 將第一個遇到的 r=0 且 m=1 的頁面作為淘汰頁面; 掃描過程中將掃描過的頁面的 r 位清0;S3: 若S2失敗, 指針再次回到原位置, goto S1。頁6/r=1 m=1頁3/r=1 m=1頁18/r=1 m=0頁8/r=1 m=0頁10/r=1 m=0頁9/r=0 m=1頁0/r=0 m=1頁1/r=1 m=0框12框23框51框6框81框96框60框5訪問第15頁6.5.

19、1 虛擬頁式存儲系統(tǒng)(Cont.)改進的時鐘算法頁6/r=1 m=1頁3/r=1 m=1頁18/r=1 m=0頁8/r=0 m=0頁10/r=1 m=0頁9/r=0 m=1頁0/r=0 m=1頁1/r=1 m=0框12框23框51框6框81框96框60框5訪問第15頁改進的時鐘算法6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)頁6/r=1 m=1頁3/r=1 m=1頁18/r=1 m=0頁8/r=0 m=0頁10/r=0 m=0頁9/r=0 m=1頁0/r=0 m=1頁1/r=1 m=0框12框23框51框6框81框96框60框5訪問第15頁改進的時鐘算法6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)

20、頁6/r=1 m=1頁3/r=1 m=1頁18/r=1 m=0頁8/r=0 m=0頁10/r=0 m=0頁15/r=1 m=0頁0/r=0 m=1頁1/r=1 m=0框12框23框51框6框81框96框60框5改進的時鐘算法6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)6. 抖動/顛簸(thrashing) 頁面在內(nèi)存與外存之間頻繁換入換出。原因: 分給進程物理頁框過少; 淘汰算法不合理; 程序結(jié)構(gòu): 跳轉(zhuǎn)指令, 全局變量分散定義。處理: 增加分給進程物理頁框數(shù) ; 改進淘汰算法。 改進程序結(jié)構(gòu);思考題: 在某些虛擬頁式存儲管理系統(tǒng)中, 內(nèi)存中總保持 一個空閑的物理頁框, 這樣做有什么好處？6.5

21、.1 虛擬頁式存儲系統(tǒng)(Cont.)6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)7. 工作集模型(working set model)淘汰算法的效果與進程運行的頁面走向有關(guān); 進程訪問頁面的局部化程度愈高, 進程運行效率愈高。 時間局部化: 一旦某條指令或數(shù)據(jù)被訪問, 經(jīng)常很快又被訪問, 如程序中的循環(huán)體部分和循環(huán)控制變量。 空間局部化: 一旦某個位置被訪問到, 附近的位置也可能很快要用到, 如程序中的順序指令串、數(shù)組。 局部化反映在頁面走向上, 就是在任何一小段時間里, 進程運行只集中于訪問某幾頁。 6.5.1 虛擬頁式存儲系統(tǒng)(Cont.) 工作集(working set): 進程在一段時間

22、內(nèi)所訪問頁面(活動頁面)的集合。某進程從時刻 (t -) 到時刻 t 之間所訪問頁面的集合 WS (t ,) 稱作該進程的工作集。稱作窗口尺寸(windows size)。 可利用工作集動態(tài)調(diào)整(增加或減少)進程的頁框分配數(shù)。訪問頁面: 2 , 3 , 3 , 3 , 2 , 3 , 2 , 5 , 5 , 8 , 5Tt -tWS(t ,)=(2,3,5,8)Denning 認為: 為使程序有效運行, 工作集應能放入內(nèi)存。6.5.1 虛擬頁式存儲系統(tǒng)(Cont.) 工作集與時間有關(guān)：訪問頁面: 2, 3, 3, 3, 2, 3, 2, 5, 5, 8, 5, 5, 8, 5, 3, 9, 8

23、, 9, 5, 8, 7, 8Tt1 -t1t2WS(t1 ,)=(2,3,5,8)WS(t2 ,)=(5,8,3,9,7) 工作集與窗口尺寸有關(guān)：WS窗口尺寸程序大小06.5.1 虛擬頁式存儲系統(tǒng)(Cont.) 周期內(nèi)確定工作集大小的實現(xiàn) 頁表、快表增加頁面引用位； 每個 周期開始時，引用位都清 0； 每當訪問一個頁面，其引用位置 1； 當 周期結(jié)束時， 標記為1的頁面?zhèn)€數(shù)即為工作集的大小。 第n+1個周期工作集大小的估算公式： n+1=Wn+(1 - ) n 其中： Wn為第n個周期實際工作集大??； n為第n個周期工作集估算值； 通常取值為0.5。6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)

24、8. 頁故障率反饋模型: PFFB(Page Fault Feed Back) 頁故障率訪問內(nèi)存缺頁次數(shù)/訪問內(nèi)存總次數(shù) 思 想: 利用頁故障率反饋信息, 動態(tài)調(diào)整頁框的分配。 實 現(xiàn): 規(guī)定頁故障率上界、下界; 頁故障率高(達到某上界閾值): 內(nèi)存頁面少, 增加頁框。 頁故障率低(達到某下界閾值): 內(nèi)存頁面多, 減少頁框。9. 例子: 某虛擬頁式系統(tǒng)，進程空間和內(nèi)存空間都是64k， 頁長1K。某進程6個頁面，內(nèi)存分配4個頁框，采用 局部置換。280時刻頁表和Clock數(shù)據(jù)結(jié)構(gòu)如下：0頁2頁3頁5頁框5框12框8框3(順時針)邏輯頁號頁框號裝入時間訪問標志0511011-2121601382

25、3014-538016.5.1 虛擬頁式存儲系統(tǒng)(Cont.)280時刻：(1) 訪問13B7H，邏輯頁號是多少？(2) 采用FIFO置換算法， 物理頁框號是多少？物理地址是多少？(3) 采用CLOCK置換算法， 頁框號是多少？物理地址是多少？6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)解：（1）邏輯地址13B7H化為二進制數(shù)為 0001,0011,1011,0111 其中低10位為頁內(nèi)地址， 高6位為邏輯頁號，即邏輯頁號為4。 4號頁面不在內(nèi)存，發(fā)生缺頁中斷， （2）按 FIFO 置換算法，應置換第5頁，所得頁框號3， 形成物理地址：0000,11 11,1011,0111 劃成16進制為：0

26、FB7H （3）采用CLOCK置換算法，淘汰第0頁，得頁框5， 形成物理地址：0001,01 11,1011,0111 劃成16進制為17B7H。6.5.1 虛擬頁式存儲系統(tǒng)(Cont.)6.5.2 虛擬段式存儲系統(tǒng)1. 基本原理 進程運行前: 全部裝入外存, 部分(主程序)裝入內(nèi)存; 進程運行時: 訪問段不在內(nèi)存, 發(fā)生缺段中斷, 動態(tài)調(diào)入。 調(diào)入時如果內(nèi)存空間不足, 采用方法: 緊 湊: 空閑區(qū)合并; 淘 汰: 按淘汰算法將內(nèi)存中某段移至外存。6.5.2 虛擬段式存儲系統(tǒng)(Cont.)虛擬段式存儲管理地址映射指令確定邏輯地址(s,d)由s查快表得到b 和 l查到 b+d 得到物理地址0sl

27、-1越界中斷由b、s查找段表該段在內(nèi)存缺段中斷保存現(xiàn)場內(nèi)存可滿足選一段淘汰該段修改過寫回外存讀入該段修改段表和快表恢復現(xiàn)場FFFTTT( s, b,l) 快表如快表滿，則淘汰一表項硬件完成軟件完成結(jié) 束T0dl-1T越界中斷F0dl-1越界中斷F b+d 得到物理地址找到該段在外存的位置緊湊夠緊湊T修改段表6.5.2 虛擬段式存儲系統(tǒng)(Cont.) 段表的改進:段號段長內(nèi)存首址外存首址訪問權(quán)限內(nèi)外標識修改標志Slbbrwe0,10,1 快表的改進:段號段長內(nèi)存首址訪問權(quán)限修改標志Slbrwe0,16.5.2 虛擬段式存儲系統(tǒng)(Cont.)2. 段的動態(tài)連接(dynamic linking) 動

28、態(tài)連接的提出 靜態(tài)連接: 運行前連接, 由link完成; 動態(tài)連接: 運行需要時連接, 由OS完成。 靜態(tài)連接的缺點: 連接時間長 ; 目標代碼長 ; 連接段可能并不執(zhí)行(未用到)。6.5.2 虛擬段式存儲系統(tǒng)(Cont.) 動態(tài)連接的實現(xiàn) (Multics為例)靜態(tài)連接: 程序段個數(shù)固定, 段名、段號轉(zhuǎn)換直接由 連接裝配程序完成。動態(tài)連接: 程序段個數(shù)不確定, 段名、段號轉(zhuǎn)換由 操作系統(tǒng)完成。實現(xiàn)所需表:段名段號s_names_numb符號名段內(nèi)偏移S1A1SkAk符號表目標代碼或數(shù)據(jù)(每進程一個)(每段一個)段結(jié)構(gòu)段名/段號對照表符號表6.5.2 虛擬段式存儲系統(tǒng)(Cont.) 動態(tài)連接的

29、實現(xiàn)步驟 編譯(匯編)時: 遇到訪問外段指令, 采用間接尋址, 指向一個間接字:LD符號地址：“X|”邏輯地址(段號,段內(nèi)偏移)1: 未連接, 段號未定0: 已連接, 段號已定L也叫障礙指示位！遇到間接指令, 且 L = 1, 發(fā)生連接中斷, 處理程序: 由 D 取出符號地址”X|” ; 由段名 ”X” 查找, 如查到表項(X, Sx), 則已分配段號:取出段號 Sx , 并用 Sx 查段表, 找到該段;由符號地址查段名X的得段內(nèi)地址Ax;邏輯地址 (Sx, Ax) D, 0 L ;轉(zhuǎn)段式。 否則未分配段號: X段未連接過。將X段讀入內(nèi)存, 分配段號;填寫, 填寫, 轉(zhuǎn)。6.5.2 虛擬段式存

30、儲系統(tǒng)(Cont.) 執(zhí)行時:6.5.2 虛擬段式存儲系統(tǒng)(Cont.)例子: 設有兩個段W, X。 匯編前:W段.Load 1, X|Load 2, X|.X段12345678.Y:Z:6.5.2 虛擬段式存儲系統(tǒng)(Cont.) 匯編后: W段已連接并在內(nèi)存, 段號為2 ; X段未連接。段號段首址0123段表Load *1, 2|100Load *2, 2|150100:1 2 200150:1 2 250200:“7X|”250:“7X|”W段(段號=2)段名段號MAIN0A1W2段名/段號對照表30040030012344005678X段100, 150為間接字; 淺藍色為符號表。6.5

31、.2 虛擬段式存儲系統(tǒng)(Cont.)第一次連接: 執(zhí)行指令 Load *1, 2|100; 將X段連接到內(nèi)存.段號段首址0123段表Load *1, 2|100Load *2, 2|150100:0 3 300150:1 2 250200:“7X|”250:“7X|”W段(段號=2)段名段號MAIN0A1W2X3段名/段號對照表30040030012344005678X段(段號=3)6.5.2 虛擬段式存儲系統(tǒng)(Cont.) 第二次連接: 執(zhí)行指令Load *2, 2|150。段號段首址0123段表Load *1, 2|100;Load *2, 2|150;100:0 3 300150:0 3

32、 400200:“7X|”250:“7X|”W段(段號=2)段名段號MAIN0A1W2X3段名/段號對照表30040030012344005678X段(段號=3) 動態(tài)連接的問題 動態(tài)連接與共享的矛盾 多道程序環(huán)境下要求代碼段共享中不能被修改; 動態(tài)連接: 修改間接字(代碼); 段的共享: 要求純代碼(pure code)。 解決方法: 共享代碼分為”純段”和”雜段” 純段共享; 雜段私用: 間接字等可修改內(nèi)容放在雜段中。6.5.2 虛擬段式存儲系統(tǒng)(Cont.)6.5.3 虛擬段頁式存儲系統(tǒng)虛擬頁式: 存儲空間靜態(tài)劃分等長區(qū)域; 無碎片; 進程空間不能動態(tài)擴充, 不能動態(tài)連接; 共享不方便。

33、虛擬段式: 存儲空間動態(tài)劃分不等長區(qū)域(程序單位); 有碎片; 段的動態(tài)連接; 便于存儲共享和保護; 段長度可動態(tài)變化。6.5.3 虛擬段頁式存儲系統(tǒng)(Cont.)1. 基本原理 所需表目 段表: 每個進程一個。段號頁表長度頁表首址訪問權(quán)限擴充標志共享段表入口slbael 頁表: 每個段一個。邏輯頁號頁框號外存塊號內(nèi)外標志修改標志pfbim 共享段表: 整個系統(tǒng)一個, 記錄所有共享段。段名頁表長度頁表首址擴充標志共享計數(shù)namelbec 段名/段號對照表: 每個進程一個。 總頁表：內(nèi)、外存各一個。6.5.3 虛擬段頁式存儲系統(tǒng)(Cont.) 各表之間聯(lián)系段號SiSjP1段表段號SkSrP2段表

34、共享段表頁表(私用)頁表(共享)15161718192021存儲空間6.5.3 虛擬段頁式存儲系統(tǒng)(Cont.) 所需寄存器 段表首址寄存器b: 保存正運行進程段表首址; 段表長度寄存器l: 保存正運行進程段表長度; 快表段號邏輯頁號頁框號訪問權(quán)限修改標志spfam 地址映射: : (s, p, d) (f, d) 邏輯地址(s, p, d) 物理地址(f, d)6.5.3 虛擬段頁式存儲系統(tǒng)(Cont.)虛擬段頁式地址轉(zhuǎn)換l : 段表長度b : 段表首地址l : 頁表長度b : 頁表首地址邏輯地址(s, p, d)由(s,p)查快表找頁框號f找到f?F0sl-1T訪問權(quán)限合法?T形成物理地址

35、(f,d)F越權(quán)中斷間接指令?T有障礙位?F繼續(xù)執(zhí)行T連接中斷F該頁在內(nèi)存?F缺頁中斷T(s,p,f)快表地址轉(zhuǎn)換結(jié)束T0pl-1T由s和b查段表得頁表F邏輯地址(s,p,d)物理地址(f,d)F越界中斷由b和p查頁表得f6.5.3 虛擬段頁式存儲系統(tǒng)(Cont.) 連接中斷: 由段名查本進程的段名/段號對照表及共享段表, 可能的三種情形: 所有進程都未連接過(共享段表, 段名/段號對照表均無) 查文件目錄找到該段, 為該段建立頁表, 將該段由文件全 部讀入swap空間, 部分讀入內(nèi)存, 填寫頁表; 為該段分配段號, 填寫段名/段號對照表; 如該段可共享, 填寫共享段表, 共享記數(shù)置1; 填寫

36、段表; 根據(jù)段號及段內(nèi)地址形成無障礙指示位的一般間接地址。2. 中斷處理 其它進程連接過但本進程未連接過 (共享段表有, 段名-段號對照表無) 為該段分配段號; 填寫段名/段號對照表, 填寫段表(指向共享段表), 共享段表中共享記數(shù)加1; 根據(jù)段號及段內(nèi)地址形成無障礙指示位的一般間接地址。 本進程已連接過(共享段表無, 段名/段號對照表有) 根據(jù)段號及段內(nèi)地址形成無障礙指示位的一般間接地址。 段內(nèi)地址由兩部分構(gòu)成, 即邏輯頁號和頁內(nèi)地址。6.5.3 虛擬段頁式存儲系統(tǒng)(Cont.) 缺頁中斷: 調(diào)入所需頁面, 更新頁表和總頁表。 越界中斷: 段號越界: 訪問不存在的段，地址錯誤處理。 頁號越界

37、: 如可擴展, 擴展該段(增加頁), 修改頁表和段表(頁表長度); 如不可擴展, 錯誤處理。 越權(quán)中斷: 違反段的訪問權(quán)限，錯誤處理。6.5.3 虛擬段頁式存儲系統(tǒng)(Cont.)各種虛擬存儲管理系統(tǒng)特性比較地址空間存儲分配存儲碎片存儲共享存儲保護動態(tài)擴充動態(tài)連接虛擬頁式一維簡單無不便不便不可不可虛擬段式二維復雜有方便方便可以可以虛擬段頁式二維簡單無方便方便可以可以特性管理方式6.5.3 虛擬段頁式存儲系統(tǒng)(Cont.)6.6 系統(tǒng)舉例6.6.1 Linux 存儲管理6.6.2 Windows Vista 存儲管理6.6.1 Linux 存儲管理 Physical memory manageme

38、nt 頁框: 靜態(tài)等長, 4KB; 塊組: 連續(xù)的 2 i ( i = 0, 1, 2, , 9 )個頁框構(gòu)成一個塊組; 共10個塊組, 長度為2 i 的塊組叫作塊組 i ; 空閑區(qū)表: free_areai表示頁框數(shù)為2 i的塊組, 其結(jié)構(gòu)為: 分配/釋放: Buddy heap algorithm 以2 i 個頁框(塊祖)為分配/釋放單位( 2 i-1fn2 i ), fn為要申請的頁框數(shù);空閑塊組指針塊組位圖指針1. 伙伴堆存儲分配算法6.6.1 Linux 存儲管理(Cont.) 塊組位圖: 對于塊組2 i 按前后順序兩兩結(jié)合成一對Buddy, 如: 2 1塊組的0、1頁框和2、3頁框

39、是一對Buddy; 塊組位圖的 1 位表示對應的一對Buddy頁框塊組的使用情況; 對于一對buddy: 若一個空閑, 另一個全部或部分占用, 則位圖相應位置1; 當兩個都空閑, 或都被全部或部分占用, 則位圖相應位置0。 伙伴條件: 兩個塊大小相同, 即具有相同的頁框數(shù)b;兩個塊的物理地址相連;位于后面塊組的最后頁框編號+1必須是2b的整數(shù)倍。位圖主要用于釋放時，位圖“異或”判斷是否合并塊組6.6.1 Linux 存儲管理(Cont.) 空閑區(qū)鏈表 組織結(jié)構(gòu): 假設6個塊組空閑塊組指針塊組位圖指針塊組號543210物理內(nèi)存頁框號15141312111098765432100100001111

40、0102104page1page12page3page4page14page8mapfree_areai6.6.1 Linux 存儲管理(Cont.) Buddy heap algorithm分配: 申請 fn個頁框從小到大，找到第一個滿足 fn 2 j 的空閑塊組 j ; 在塊組 j 的第一個空閑塊分配 2 i個頁框( 2 i-1fn2 i );調(diào)整塊組 j 的空閑塊鏈表;若 2 j 2 i, 則把2 j - 2 i 個空閑頁框加入到相應塊組空閑鏈中; (若2 j - 2 i不是2的整數(shù)次冪, 則將其拆分成不同的整數(shù)次冪。)修改位圖。 釋放: 釋放 2 i個頁框釋放的2 i個頁框與相鄰的空閑

41、區(qū)按伙伴關(guān)系合并, 即兩個相鄰的伙伴合并為一個大的空閑區(qū);把得到的空閑區(qū)加入到不同塊組的空閑鏈中;修改位圖。6.6.1 Linux 存儲管理(Cont.) 分配例: 申請頁框數(shù)fn=3空閑塊組指針塊組位圖指針塊組號543210物理內(nèi)存頁框號151413121110987654321001000011110102104page1page12page3page4page14page8map 21fn22 在塊組2 的空閑塊 中分配22個頁框。6.6.1 Linux 存儲管理(Cont.)塊組2分配4個頁框(8,9,10,11)后,空閑鏈及位圖變化情況如圖?？臻e塊組指針塊組位圖指針塊組號543210

42、物理內(nèi)存頁架號151413121110987654321001000011110102004page1page3page4page14mappage12page86.6.1 Linux 存儲管理(Cont.) 釋放例: 釋放頁框13空閑塊組指針塊組位圖指針塊組號543210物理內(nèi)存頁架號151413121110987654321000000011100102104page1page3page4mappage12釋放13后:12,13是伙伴, 14,15是伙伴, 這兩個伙伴構(gòu)成頁框數(shù)為4的空閑區(qū),將該空閑區(qū)加到塊組2。6.6.1 Linux 存儲管理(Cont.) Buddy heap algo

43、rithm: 問題: internal fragmentation. 例如: 申請17個頁架, 由于2 4172 5 , 按Buddy heap algorithm, 要在塊組5的空閑區(qū)分配32個頁框, 造成15個頁框的浪費, 即internal fragmentation. 解決辦法: second memory allocator 當實際申請頁框數(shù)fn2 i時, 將2 i- fn按2的整數(shù)次冪切分(carves slabs), 由second memory allocator單獨管理 。 third memory allocator 進程物理空間不要求連續(xù)時, 內(nèi)存分配由third mem

44、ory allocator完成。6.6.1 Linux 存儲管理(Cont.) 2. 虛擬存儲管理：請求式虛擬頁式存儲管理方法。 Three level page table: page directory; page middle directory; page table。 虛擬地址: Demand paging: no pre-paging, no working set. Page replacement: two daemons page daemon: kswapd runs once a second , keep enough free pages in memory. flu

45、sh daemon: bdflush wakes up periodically, ”dirty page out”. 頁目錄頁中間目錄頁表頁內(nèi)偏移6.6.2 Windows Vista 存儲管理 虛擬存儲管理器(Virtual Memory Manager, VMM) 負責存儲管理; Win32提供一組與存儲管理相關(guān)的調(diào)用; 核心中有6個專門負責存儲管理的線程。 1. 進程地址空間 虛擬地址空間32位地址碼，尋址范圍4GB； 用戶空間: 低地址端2GB； 系統(tǒng)空間: 高地址端2GB。6.6.2 Windows Vista 存儲管理(Cont.)Windows Vista虛擬存儲空間地址映像F

46、FFFFFFFH系統(tǒng)空間(2GB)非交換區(qū)頁交換區(qū)直接映射區(qū)80000000H操作系統(tǒng)駐留代碼7FFFFFFFH用戶代碼和數(shù)據(jù)(2GB)頁交換區(qū)00000000H6.6.2 Windows Vista 存儲管理(Cont.) 2. 存儲管理方式: 虛擬頁式 頁面尺寸: 4KB64KB; 可交換頁面: 用戶空間2GB以頁為單位均可交換; 系統(tǒng)空間部分頁面(動態(tài)鏈接庫)可交換。 頁表結(jié)構(gòu)：二級頁表 頁目錄(Page Directory: PD) 每個進程一個, 最多210個表項, 每個表項存放指向一個頁表入口; 頁表(Page Table) 頁表最多210個表項, 每個表項存該頁號分配的頁框號或原

47、型頁表表項。 32位虛擬地址6.6.2 Windows Vista 存儲管理(Cont.)31 2221 1211 0PDEPTEd頁目錄入口頁表入口頁內(nèi)偏移 地址映射PDEPTEdCR3+頁目錄+頁表f+4KB6.6.2 Windows Vista 存儲管理(Cont.) 3. 存儲共享及保護 原型頁表(Prototype Page Table): 對于共享頁, 頁表表項不 指向物理頁框, 而是指向原型頁表, 原型頁表的表項指向?qū)嶋H物理頁框號。 頁為保護單位，只讀、讀寫、執(zhí)行、不可操作、寫時復制。P頁目錄05115121023P頁表f01f02系統(tǒng)頁表原型頁表共享頁各表之間的關(guān)系6.6.2

48、Windows Vista 存儲管理(Cont.)4. 內(nèi)存優(yōu)先級內(nèi)存優(yōu)先級空閑頁框指針01234567待機列表standbylist6.6.2 Windows Vista 存儲管理(Cont.)進程虛擬頁面狀態(tài) 閑置(free)狀態(tài): 未分配內(nèi)存的頁面。 對閑置狀態(tài)頁面的訪問, 將導致缺頁中斷; 預定(reserved)狀態(tài)： 已分配內(nèi)存, 但不可立即使用; 只有顯示地解除預訂狀態(tài)才可使用, 通常用來存儲區(qū)的預留; 確認(committed)狀態(tài): 已分配內(nèi)存并且可訪問的頁面。5. 頁面調(diào)度習題講解：P143 20. 設自行車生產(chǎn)線上有一只箱子, 其中有N個位置(N3), 每個位置可以存放一

49、個車架或一個車輪; 又設有3個工人, 其活動分別為:工人1 活動:do 加工一個車架; 車架放入箱中; while (1)工人2 活動:do 加工一個車輪; 車輪放入箱中; while (1)工人3 活動:do 箱中取一個車架; 箱中取兩個車輪; 組裝為一臺車; while (1)試分別用信號燈與p/v操作、管程、會合實現(xiàn)3個工人的合作，要求解中不含死鎖。3個工人合作信號燈與p/v操作的實現(xiàn)分析: 工人1 放到箱子中的車架數(shù)最大為k-2, 即至少留出兩個車輪的位置; 工人2 放到箱子中的車輪數(shù)最大為k-1, 即至少留出一個車架的位置; 工人1 和工人2 從箱子兩端分別放車架和車輪, 兩者的存放

50、指針向箱子中間位置移動; 工人3 取車架和車輪分別從工人1 和工人2 的存放位置 向箱子兩邊位置移動; 由于工人1、工人2存放的部件不同, 所以其存放位置不能循環(huán)、交叉。3個工人合作信號燈與p/v操作的實現(xiàn)(Cont.)變量定義:Var B : array 0 . k-1 of object ;i : 0 . k-1; /工人1 放車架指針, 初值 0 ;j : 0 . k-1; /工人2 放車輪指針, 初值 k-1 ;S1: semaphore; /箱子剩余位置總數(shù), 初值 k;S2: semaphore; /箱中車架個數(shù), 初值0;S3: semaphore; /箱中車輪個數(shù), 初值0;S

51、4: semaphore; /箱中可放車架的位置數(shù), 初值k-2;S5: semaphore; /箱中可放車輪的位置數(shù), 初值k-1;mutex : semaphore; /共享區(qū)互斥, 初值1;W1:loop Produce a frame; P(S4); P(S1); P(mutex); Bi:=frame; i:=i+1; V(mutex); V(S2);end;W2:loop Produce a wheel ; P(S5); P(S1); P(mutex); Bj:=wheel; j:=j-1; V(mutex); V(S3);end;W3:loop P(S2); P(mutex);

52、i:=i-1; f:=Bi; V(mutex); V(S4); V(S1); P(S3); P(S3); P(mutex); j:=j+1; c1:=Bj; j:=j+1; c2:=Bj; V(mutex); V(S5); V(S5); V(S1); V(S1); make a bikeend;3個工人合作信號燈與p/v操作的實現(xiàn)(Cont.)3個工人合作管程的實現(xiàn)type bike = MONITOR;var B: array 0 . k-1 of object ; i , j : integer ; count , f_count , w_count : integer ; count_q

53、 , f_count_q, w_count_q : condition; f_num_q , w_num_q : condition ;define putin_f , putin_w , getout_f , getout_w ;procedure putin_w (item : object ) ;begin if w_count = k-1 then wait (w_count_q) ; if count = k then wait ( count_q ) ; B j := item ; j - ; count+; w_count+ ; signal (w_num_q) ;end;3個工人合作管程的實現(xiàn)(Cont.)procedure putin_f (item : object ) ;begin if f_count = k-2 then wait (f_count_q) ; if count = k then w