操作系統(tǒng)第六章存儲管理2ppt課件

1、6.4 外存資源管理外存資源管理n外存空間劃分外存空間劃分n靜態(tài)等長，靜態(tài)等長，2i, 稱為一塊稱為一塊(block)，塊是，塊是外存分配的根本單位，也是外存分配的根本單位，也是IO傳輸?shù)母鶄鬏數(shù)母締挝弧１締挝?。n外存空間分配外存空間分配n空閑塊鏈空閑塊鏈(慢慢)n空閑塊表空閑塊表(UNIX)n字位映像圖字位映像圖Swap空間空間File空間空間輸入輸入井井輸出輸出井井進(jìn)程與外存對應(yīng)關(guān)系進(jìn)程與外存對應(yīng)關(guān)系n界地址界地址n每進(jìn)程占一組外存延續(xù)塊；每進(jìn)程占一組外存延續(xù)塊；n每進(jìn)程占二組外存延續(xù)塊雙對界。每進(jìn)程占二組外存延續(xù)塊雙對界。n頁式頁式n內(nèi)存一頁，外存一塊。內(nèi)存一頁，外存一塊。n段式段式n

2、每段占外存假設(shè)干延續(xù)塊。每段占外存假設(shè)干延續(xù)塊。n段頁式段頁式n內(nèi)存一頁，外存一塊。內(nèi)存一頁，外存一塊。6.5 虛擬存儲系統(tǒng)虛擬存儲系統(tǒng)無虛擬問題無虛擬問題不能運(yùn)轉(zhuǎn)比內(nèi)存大的程序；不能運(yùn)轉(zhuǎn)比內(nèi)存大的程序；進(jìn)程全部裝入內(nèi)存，浪費(fèi)空間進(jìn)程活動具有部進(jìn)程全部裝入內(nèi)存，浪費(fèi)空間進(jìn)程活動具有部分性分性)。單控制流的進(jìn)程需求較少部分在內(nèi)存；單控制流的進(jìn)程需求較少部分在內(nèi)存；多控制流的進(jìn)程需求較多部分在內(nèi)存。多控制流的進(jìn)程需求較多部分在內(nèi)存。虛擬存儲虛擬存儲進(jìn)程部分裝入內(nèi)存，部分或全部裝入外存，進(jìn)程部分裝入內(nèi)存，部分或全部裝入外存，運(yùn)轉(zhuǎn)時訪問在外存部分動態(tài)調(diào)入，內(nèi)存不夠淘運(yùn)轉(zhuǎn)時訪問在外存部分動態(tài)調(diào)入，內(nèi)存不

3、夠淘汰。汰。6.5.1 虛擬頁式存儲系統(tǒng)虛擬頁式存儲系統(tǒng)n根本原理根本原理n進(jìn)程運(yùn)轉(zhuǎn)前：進(jìn)程運(yùn)轉(zhuǎn)前：n全部裝入外存，部分裝入內(nèi)存。全部裝入外存，部分裝入內(nèi)存。n進(jìn)程運(yùn)轉(zhuǎn)時：進(jìn)程運(yùn)轉(zhuǎn)時：n訪問頁不在內(nèi)存，發(fā)生缺頁中斷，中斷處訪問頁不在內(nèi)存，發(fā)生缺頁中斷，中斷處置程序：置程序：n找到訪問頁在外存的地址；找到訪問頁在外存的地址；n在內(nèi)存找一空閑頁面；在內(nèi)存找一空閑頁面；n如沒有，按淘汰算法淘汰一個；如沒有，按淘汰算法淘汰一個；n如需求，將淘汰頁面寫回外存，修正頁表如需求，將淘汰頁面寫回外存，修正頁表和總頁表；和總頁表；n讀入所需頁面切換進(jìn)程；讀入所需頁面切換進(jìn)程；n重新啟動中斷指令。重新啟動中斷指令

4、。6.5.1 虛擬頁式存儲管理虛擬頁式存儲管理(Cont.)虛擬頁式存儲管理地址映射虛擬頁式存儲管理地址映射指令給出邏輯地址指令給出邏輯地址(p,d)由由p查快表得到查快表得到 f查查到到 f、d合并得物理地址合并得物理地址0pl-1越界中斷越界中斷由由b、p查找頁表得查找頁表得f該頁在該頁在內(nèi)存內(nèi)存缺頁中斷缺頁中斷保管現(xiàn)場保管現(xiàn)場有空閑有空閑頁框頁框選一頁面淘汰選一頁面淘汰該頁面修該頁面修正正正正寫回外存寫回外存讀入所需頁面讀入所需頁面更新頁表和快表更新頁表和快表恢復(fù)現(xiàn)場恢復(fù)現(xiàn)場FFFTTT( f,d) 快表快表如快表滿，淘如快表滿，淘汰一表項汰一表項硬硬件件完完成成軟軟件件完完成成T f、

5、d合并得合并得物理地址物理地址對頁表的改良：對頁表的改良：對快表的改良：對快表的改良：邏輯頁號邏輯頁號 p . . . . . 頁框號頁框號 外存塊號外存塊號 內(nèi)外標(biāo)識內(nèi)外標(biāo)識 訪問權(quán)限訪問權(quán)限 修正標(biāo)志修正標(biāo)志 f b (0,1) r,w,e (0,1) . . . . . . . 邏輯頁號邏輯頁號 頁框號頁框號 訪問權(quán)限訪問權(quán)限 修正標(biāo)志修正標(biāo)志 p f r,w,e (0,1) . . . 6.5.1.2 內(nèi)存頁框分配戰(zhàn)略靜態(tài)戰(zhàn)略內(nèi)存頁框分配戰(zhàn)略靜態(tài)戰(zhàn)略 1. 平均分配平均分配 如內(nèi)存如內(nèi)存128頁，進(jìn)程頁，進(jìn)程25個，每個進(jìn)程個，每個進(jìn)程5個頁架個頁架 2. 按進(jìn)程長度比例分配按進(jìn)程長度

6、比例分配 pi共共si個頁面；個頁面；S=si；內(nèi)存共；內(nèi)存共m個頁架個頁架 ai=(si/S)m 3. 按進(jìn)程優(yōu)先級比例分配按進(jìn)程優(yōu)先級比例分配 4. 按進(jìn)程長度和優(yōu)先級別比例分配按進(jìn)程長度和優(yōu)先級別比例分配 靜態(tài)戰(zhàn)略沒有反映：靜態(tài)戰(zhàn)略沒有反映：(1)程序構(gòu)造；程序構(gòu)造；(2)程序在不同時辰的行為特性。程序在不同時辰的行為特性。6.5.1.3 外存塊的分配戰(zhàn)略外存塊的分配戰(zhàn)略 1. 靜態(tài)分配靜態(tài)分配 外存堅持進(jìn)程的全部頁面：外存堅持進(jìn)程的全部頁面： 優(yōu)點：速度快優(yōu)點：速度快-淘汰時不用寫回淘汰時不用寫回(未修正情況未修正情況) 缺陷：外存浪費(fèi)缺陷：外存浪費(fèi) 2. 動態(tài)分配動態(tài)分配 外存僅堅持

7、進(jìn)程不在內(nèi)存的頁面：外存僅堅持進(jìn)程不在內(nèi)存的頁面： 優(yōu)點：節(jié)省外存優(yōu)點：節(jié)省外存 缺陷：速度慢缺陷：速度慢-淘汰時必需寫回淘汰時必需寫回6.5.1.4 頁面調(diào)入時機(jī)頁面調(diào)入時機(jī) 1. 請調(diào)請調(diào)(demand paging) upon page fault, 發(fā)生缺頁中斷時調(diào)入。發(fā)生缺頁中斷時調(diào)入。 2. 預(yù)調(diào)預(yù)調(diào)(prepaging) before page fault, 將要訪問時調(diào)入將要訪問時調(diào)入(根據(jù)程序順序行為，根據(jù)程序順序行為， 不一定準(zhǔn)不一定準(zhǔn) 預(yù)調(diào)必需輔以請調(diào)。預(yù)調(diào)必需輔以請調(diào)。 用于：頁淘汰、段淘汰、快表淘汰。用于：頁淘汰、段淘汰、快表淘汰。 Objective: lowest

8、 page-fault rate. 1. 最正確淘汰算法最正確淘汰算法(OPT-optimal) 淘汰未來最長時間以后才用到的。淘汰未來最長時間以后才用到的。 效率最高，效率最高，not feasible。 6 6 0 0 1 1 2 2 0 0 3 3 0 0 4 4 2 2 3 3 0 0 3 3 2 2 1 1 2 2 0 0 1 1 6 6 0 0 1 16 6 6 6 6 6 2 22 22 22 22 26 60 0 0 0 0 00 04 40 00 00 01 1 1 13 33 33 31 11 1 6.5.1.5 置換算法置換算法(replacement algorithm

9、)2. 先進(jìn)先出先進(jìn)先出(FIFO) 淘汰最先調(diào)入的。淘汰最先調(diào)入的。 根據(jù)根據(jù): 先進(jìn)入的能夠曾經(jīng)運(yùn)用終了。先進(jìn)入的能夠曾經(jīng)運(yùn)用終了。 實現(xiàn)：隊列實現(xiàn)：隊列 negative case: 有些代碼和數(shù)據(jù)能夠整個程序運(yùn)轉(zhuǎn)中用有些代碼和數(shù)據(jù)能夠整個程序運(yùn)轉(zhuǎn)中用到。到。 Belady異常異常: 例子：例子：1，2，3，4，1，2，5，1，2，3，4，5 內(nèi)存內(nèi)存3個物理頁面：頁缺點率個物理頁面：頁缺點率=9/12 內(nèi)存內(nèi)存4個物理頁面：頁缺點率個物理頁面：頁缺點率=10/12 FIFO淘汰算法淘汰算法(belady異常異常)12 3 4 1 2 5 1 2 3 4511 1 4 4 4 55 52

10、 2 2 1 1 13 33 3 3 2 22 41 2 3 4 1 2 5 1 2 3 4 51 1 1 15 5 5 5 4 42 2 22 1 1 1 1 53 33 3 2 2 2 244 4 4 3 3 3頁缺點率頁缺點率=10/12頁缺點率頁缺點率=9/12訪問序列訪問序列:訪問序列訪問序列:內(nèi)存頁面內(nèi)存頁面:內(nèi)存頁面內(nèi)存頁面:3. 運(yùn)用過最久的先淘汰運(yùn)用過最久的先淘汰LRU 淘汰最近一次訪問距當(dāng)前時間最長的。淘汰最近一次訪問距當(dāng)前時間最長的。 Replace page that hasnt been used for the longest period of time. 實現(xiàn)：

11、實現(xiàn)：stack 當(dāng)一頁面被訪問時當(dāng)一頁面被訪問時, 從棧中取出壓到棧頂從棧中取出壓到棧頂, 棧底是棧底是: LRU page. 例子：例子：reference string: 4, 7, 0, 7, 1, 0, 1, 2, 1, 2, 7, 1, 2 2107472104Stack before aStack before b a bnLRU算法6 6 0 0 1 1 2 2 0 0 3 3 0 0 4 4 2 2 3 3 0 0 3 3 2 2 1 1 2 2 0 0 1 1 6 6 0 0 1 16 6 6 6 6 6 2 22 24 4 4 4 4 4 0 01 11 11 10 0

12、0 0 0 00 00 0 0 0 3 3 3 33 30 00 01 1 1 13 33 3 2 2 2 2 2 22 22 26 6 4. 最近不用的先淘汰最近不用的先淘汰(not used recently) 淘汰最近一段時間未用到的。淘汰最近一段時間未用到的。 實現(xiàn)：每頁添加一個訪問標(biāo)志，實現(xiàn)：每頁添加一個訪問標(biāo)志， 訪問置訪問置1，定時清，定時清0， 淘汰時取標(biāo)志為淘汰時取標(biāo)志為0的。的。 LRU算法的近似：算法的近似： Reference string: 2, 3, 5, 6, 4, 2, 5, 6, 7, 5, 6, 8, 標(biāo)志清標(biāo)志清0選擇淘汰選擇淘汰LRU：3NUR：2，3，

13、4恣意恣意5. 最不經(jīng)常運(yùn)用的先淘汰最不經(jīng)常運(yùn)用的先淘汰(LFU) 淘汰運(yùn)用次數(shù)最少的。淘汰運(yùn)用次數(shù)最少的。 根據(jù)根據(jù): 活潑訪問頁面應(yīng)有較大的訪問次數(shù)活潑訪問頁面應(yīng)有較大的訪問次數(shù). Suffer: (1) 前期運(yùn)用多，但以后不用，難換出；前期運(yùn)用多，但以后不用，難換出； (2) 剛調(diào)入的頁面，援用少，被換出能夠大。剛調(diào)入的頁面，援用少，被換出能夠大。 實現(xiàn)：記數(shù)器，調(diào)入清實現(xiàn)：記數(shù)器，調(diào)入清0，訪問增，訪問增1，淘汰選取最小者。，淘汰選取最小者。6. 最經(jīng)常運(yùn)用的先淘汰最經(jīng)常運(yùn)用的先淘汰(MFU) 淘汰運(yùn)用次數(shù)最多的。淘汰運(yùn)用次數(shù)最多的。 根據(jù)根據(jù): 運(yùn)用多的能夠曾經(jīng)用完了。運(yùn)用多的能夠曾

14、經(jīng)用完了。 Suffer: 程序有些成分是在整個程序運(yùn)轉(zhuǎn)中都運(yùn)用的。程序有些成分是在整個程序運(yùn)轉(zhuǎn)中都運(yùn)用的。7. 二次時機(jī)二次時機(jī)(second chance)n淘汰裝入最久且最近未被訪問的頁面。淘汰裝入最久且最近未被訪問的頁面。n實現(xiàn)時：采用拉鏈數(shù)據(jù)構(gòu)造。實現(xiàn)時：采用拉鏈數(shù)據(jù)構(gòu)造。6/13/14/08/05/19/00/01/13/14/08/05/19/00/01/16/04/08/05/19/00/01/16/03/08/05/19/00/01/16/03/02/18. 時鐘算法時鐘算法(clock algorithm)n將頁面組織成環(huán)形，有一個指針指向當(dāng)前位置。每次將頁面組織成環(huán)形，有

15、一個指針指向當(dāng)前位置。每次需求淘汰頁面時，從指針?biāo)傅捻撁骈_場檢查。假設(shè)需求淘汰頁面時，從指針?biāo)傅捻撁骈_場檢查。假設(shè)當(dāng)前頁面的訪問位為當(dāng)前頁面的訪問位為0，即從上次檢測到目前，該頁沒，即從上次檢測到目前，該頁沒有訪問過，那么將該頁交換。假設(shè)當(dāng)前頁面的訪問位有訪問過，那么將該頁交換。假設(shè)當(dāng)前頁面的訪問位為為1，那么將其清，那么將其清0，并順時針挪動指針到下一個位置。，并順時針挪動指針到下一個位置。反復(fù)上述步驟直至找到一個訪問位為反復(fù)上述步驟直至找到一個訪問位為0的頁面。的頁面。n可以看出，時鐘算法與二次時機(jī)算法的淘汰效果是根可以看出，時鐘算法與二次時機(jī)算法的淘汰效果是根本一樣的，差別在于二者所

16、采用的數(shù)據(jù)構(gòu)造不同，二本一樣的，差別在于二者所采用的數(shù)據(jù)構(gòu)造不同，二次時機(jī)運(yùn)用的是鏈表，需求額外存儲空間，且摘鏈入次時機(jī)運(yùn)用的是鏈表，需求額外存儲空間，且摘鏈入鏈速度很慢。而時鐘算法可直接利用頁表中的援用位，鏈速度很慢。而時鐘算法可直接利用頁表中的援用位，外加一個指針，速度快且節(jié)省空間。外加一個指針，速度快且節(jié)省空間。頁頁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=

17、1頁頁9/r=0頁頁0/r=0頁頁1/r=1框框12框框23框框51框框6框框81框框96框框60框框5訪問第訪問第18頁頁時鐘算法時鐘算法頁頁6/r=1頁頁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/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頁頁時鐘算法時鐘算法改良的時鐘算法改良的時鐘算法n思索修正標(biāo)

18、志思索修正標(biāo)志mnr=0, m=0：最正確淘汰頁面：最正確淘汰頁面nr=0, m=1：淘汰前回寫：淘汰前回寫nr=1, m=0：不淘汰：不淘汰nr=1, m=1：不淘汰：不淘汰改良的時鐘算法改良的時鐘算法n步驟步驟1：n由指針當(dāng)前位置開場掃描，選擇最正確淘汰頁由指針當(dāng)前位置開場掃描，選擇最正確淘汰頁面，不改動援用位，將第一個遇到的面，不改動援用位，將第一個遇到的r=0且且m=0的頁面作為淘汰頁面；的頁面作為淘汰頁面；n步驟步驟2：n如步驟如步驟1失敗，再次從原位置開場，找失敗，再次從原位置開場，找r=0且且m=1的頁面，將第一個滿足上述要求的頁面的頁面，將第一個滿足上述要求的頁面作為淘汰頁面，

19、同時將掃描過頁面的作為淘汰頁面，同時將掃描過頁面的r位清位清0；n步驟步驟3：n假設(shè)步驟假設(shè)步驟2失敗，指針再次回到原位置，重新失敗，指針再次回到原位置，重新執(zhí)行步驟執(zhí)行步驟1。假設(shè)還失敗再次執(zhí)行步驟。假設(shè)還失敗再次執(zhí)行步驟2，此時，此時定能找到。定能找到。頁頁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/r=1 m=1頁頁3/r=1 m=1頁頁18/

20、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/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/r=1 m=1頁頁3/r=1 m=1頁頁18/r=1 m=0頁頁8/r

21、=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/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時鐘算法時鐘算法2019年考研試題年考研試題n某虛擬頁式系統(tǒng)，進(jìn)程空間和內(nèi)存空間都是某虛擬頁式系統(tǒng)，進(jìn)程空間和內(nèi)存空間都是64k，頁長，頁長1K，某進(jìn)程，某進(jìn)程

22、6個頁，內(nèi)存分配個頁，內(nèi)存分配4個個頁框，采用部分置換，頁框，采用部分置換，280時辰頁表和時辰頁表和Clock數(shù)據(jù)構(gòu)造如下：數(shù)據(jù)構(gòu)造如下：邏輯頁號邏輯頁號 頁框號頁框號 裝入時間裝入時間 訪問標(biāo)志訪問標(biāo)志 0 5 110 1 1 - - - 2 12 160 1 3 8 230 1 4 - - - 5 3 80 10頁2頁3頁5頁框框5框框12框框8框框3(順時針)2019年考研試題年考研試題n(1)280時辰訪問時辰訪問13B7H，邏輯頁號是，邏輯頁號是多少？多少？n(2)采用采用FIFO置換算法，物理頁框號是置換算法，物理頁框號是多少？物理地址是多少？多少？物理地址是多少？n(3)采用采

23、用CLOCK置換算法，頁框號是多置換算法，頁框號是多少？物理地址是多少？少？物理地址是多少？2019年考研試題年考研試題n1邏輯地址邏輯地址13B7H化為二進(jìn)制數(shù)為化為二進(jìn)制數(shù)為0001001110110111，其中后，其中后10位為頁內(nèi)位為頁內(nèi)地址，前地址，前6位為邏輯頁號，即邏輯頁號為位為邏輯頁號，即邏輯頁號為4。n24號頁不在內(nèi)存，發(fā)生缺頁中斷，按號頁不在內(nèi)存，發(fā)生缺頁中斷，按FIFO置換算法，應(yīng)置換第置換算法，應(yīng)置換第5頁，所得頁框號頁，所得頁框號3，構(gòu)成物理地址構(gòu)成物理地址0000111110110111，劃成，劃成16進(jìn)制為進(jìn)制為0FB7H。n3采用采用CLOCK置換算法，淘汰第置

24、換算法，淘汰第0頁，得頁，得頁框頁框5，構(gòu)成物理地址為，構(gòu)成物理地址為0001011110110111，劃成，劃成16進(jìn)制為進(jìn)制為17B7H。6.5.1.6 顛簸顛簸(thrashing) 頁面在內(nèi)存與外存之間頻繁換入換出。頁面在內(nèi)存與外存之間頻繁換入換出。 緣由：緣由：(1) 分給進(jìn)程物理頁架過少；分給進(jìn)程物理頁架過少； (2) 淘汰算法不合理。淘汰算法不合理。 處置：處置：(1) 添加分給進(jìn)程物理頁架數(shù)；添加分給進(jìn)程物理頁架數(shù)；(2) 改良淘汰算法。改良淘汰算法。思索題：思索題：在某些虛擬頁式存儲管理系統(tǒng)中，內(nèi)存中總堅持一個在某些虛擬頁式存儲管理系統(tǒng)中，內(nèi)存中總堅持一個空閑的物理頁架，這樣

25、做有什么益處？空閑的物理頁架，這樣做有什么益處？6.5.1.7 任務(wù)集模型任務(wù)集模型(working set model) 任務(wù)集任務(wù)集(working set): 進(jìn)程在一段時間內(nèi)所訪問頁面的集合。進(jìn)程在一段時間內(nèi)所訪問頁面的集合。 WS(t,)=5,7,1,6,22 6 1 5 7 7 7 7 5 1 6 2 2 1 2 3 (page reference) t ：稱為窗口尺寸：稱為窗口尺寸(window size)。Denning 以為：為使程序有效運(yùn)轉(zhuǎn)，任務(wù)集應(yīng)能放入內(nèi)存。以為：為使程序有效運(yùn)轉(zhuǎn)，任務(wù)集應(yīng)能放入內(nèi)存。TWS(t1,)=5,7,1,6,22 6 1 5 7 7 7 7 5

26、 1 6 2 2 1 2 3 4 4 4 3 4 3 4 4 4 1 3 4 . WS(t2,)=2,3,4 t1t2任務(wù)集與時間有關(guān)：任務(wù)集與時間有關(guān)：任務(wù)集與窗口尺寸有關(guān)：任務(wù)集與窗口尺寸有關(guān)：程序大小程序大小 WS窗口尺寸確定：窗口尺寸確定： 過?。夯顒禹撁娌荒苋垦b入，頁缺點率高；過?。夯顒禹撁娌荒苋垦b入，頁缺點率高； 過大：內(nèi)存浪費(fèi)。過大：內(nèi)存浪費(fèi)。Madnick, Donovan建議：建議： 1萬次訪內(nèi)。萬次訪內(nèi)。實現(xiàn)：頁表中添加訪問位：實現(xiàn)：頁表中添加訪問位： 訪問位訪問位頁表：頁表： 開場時，全部清開場時，全部清0,訪問：置訪問：置1, 終了時終了時(新新 開場時開場時)訪問

27、標(biāo)志為訪問標(biāo)志為1的，為該的，為該 期間任務(wù)集，期間任務(wù)集， n+1=wn+(1-) n6.5.1.8 頁缺點率反響模型頁缺點率反響模型PFFB(Page Fault Feed Back)頁缺點率高頁缺點率高(到達(dá)某上界閾值到達(dá)某上界閾值)：內(nèi)存頁面少，添加。：內(nèi)存頁面少，添加。頁缺點率低頁缺點率低(到達(dá)某下界閾值到達(dá)某下界閾值)：內(nèi)存頁面多，減少。：內(nèi)存頁面多，減少。6.5.2 虛擬段式存儲系統(tǒng)虛擬段式存儲系統(tǒng)n進(jìn)程運(yùn)轉(zhuǎn)前，全部裝入外存，部分裝入進(jìn)程運(yùn)轉(zhuǎn)前，全部裝入外存，部分裝入內(nèi)存，訪問段不再內(nèi)存時，發(fā)生缺段中內(nèi)存，訪問段不再內(nèi)存時，發(fā)生缺段中斷。斷。6.5.2 虛擬段式存儲系統(tǒng)虛擬段式存

28、儲系統(tǒng)(Cont.)虛擬段式存儲管理地址映射虛擬段式存儲管理地址映射指令確定邏輯地址指令確定邏輯地址(s,d)由由s查快表得到查快表得到b 和和 l查查到到 b+d 得到物理地址得到物理地址0sl-1越界中斷越界中斷由由b、s查找段表查找段表該段在該段在內(nèi)存內(nèi)存缺段中斷缺段中斷保管現(xiàn)場保管現(xiàn)場內(nèi)存可內(nèi)存可滿足滿足選一段淘汰選一段淘汰該段修該段修正正正正寫回外存寫回外存讀入讀入該段該段修正段表和快表修正段表和快表恢復(fù)現(xiàn)場恢復(fù)現(xiàn)場FFFTTT( s, b,l) 快表快表如快表滿，淘如快表滿，淘汰一表項汰一表項硬硬件件完完成成軟軟件件完完成成T0dl-1T越界中斷越界中斷F0dl-1越界越界中斷中斷

29、 b+d 得物得物理地址理地址找到該段在外存的位置找到該段在外存的位置緊湊夠緊湊夠緊湊緊湊TTF修正段表修正段表 . . . . 段號段號 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) . . . . (1)段表的改良：段表的改良：()快表的改良：快表的改良： . . . . 段號段號 段長段長 內(nèi)存首址內(nèi)存首址 訪問權(quán)限訪問權(quán)限 修正標(biāo)志修正標(biāo)志 s l b rwe (0,1) . . . .6.5.2.2 段的動態(tài)銜接段的動態(tài)銜接(dynamic linking)n動態(tài)銜接動態(tài)銜接 vs. 靜

30、態(tài)銜接靜態(tài)銜接n靜態(tài)銜接：運(yùn)轉(zhuǎn)前銜接，由靜態(tài)銜接：運(yùn)轉(zhuǎn)前銜接，由link完成；完成；n動態(tài)銜接：運(yùn)轉(zhuǎn)時銜接，由動態(tài)銜接：運(yùn)轉(zhuǎn)時銜接，由OS完成完成.n靜態(tài)銜接的缺陷靜態(tài)銜接的缺陷n銜接時間長；銜接時間長；n目的代碼長；目的代碼長；n銜接段能夠并不執(zhí)行銜接段能夠并不執(zhí)行(未用到未用到)。動態(tài)銜接的實現(xiàn)動態(tài)銜接的實現(xiàn)(Multics為例為例)段名段名-段號對照表：每進(jìn)程一個段號對照表：每進(jìn)程一個段名段名 段號段號sname snum . .符號名符號名 段內(nèi)位移段內(nèi)位移 func 150 . .符號表：每段一個符號表：每段一個段方式：段方式：符號表符號表目的代碼目的代碼或者數(shù)據(jù)或者數(shù)據(jù) 靜態(tài)銜接由

31、靜態(tài)銜接由link運(yùn)用運(yùn)用銜接完不再需求銜接完不再需求(1) 編譯編譯(匯編匯編)時：時： 遇到訪問外段指令，采用間接尋址，指向一個間接字：遇到訪問外段指令，采用間接尋址，指向一個間接字：LD1: 未銜接未銜接0: 已銜接已銜接符號地址：符號地址：“X|邏輯地址：邏輯地址：(段號段號,段內(nèi)地址段內(nèi)地址)(2) 執(zhí)行時：執(zhí)行時： 遇到間接指令，且遇到間接指令，且L=1, 發(fā)生鏈接中斷，處置程序：發(fā)生鏈接中斷，處置程序：(a) 由由D取出符號地址；取出符號地址；(b) 由段名查段名由段名查段名-段號對照表，能否分配段號。段號對照表，能否分配段號。 已分配段號：取出該段號，查段表找到該段已分配段號：

32、取出該段號，查段表找到該段(內(nèi)存內(nèi)存或或 外存外存)，由入口名查符號表得段內(nèi)地址；，由入口名查符號表得段內(nèi)地址； (段號，段內(nèi)地址段號，段內(nèi)地址)D, 0 L 未分配段號：找到該段所在文件，讀入內(nèi)存，讀未分配段號：找到該段所在文件，讀入內(nèi)存，讀入入 外存，分配段號，填寫段名外存，分配段號，填寫段名-段號對照表，填寫段段號對照表，填寫段 表，轉(zhuǎn)表，轉(zhuǎn)(b)例子：匯編前：例子：匯編前：.Load 1, X|Load 2, X|.W段段X段段12345678.Y:Z:匯編后，銜接前：匯編后，銜接前：100:Load *1, 2|100;Load *2, 2|150;“7X|.“7X|1 2 2001

33、 2 250150:200:250:W段段號段段號=2)X段段 300 40012345678300400段表段表 段首址段首址 .段號段號 0 1 2 3 .段名段名 段號段號Main 0A 1W 2段名段名-段號對照表段號對照表第一次銜接后：第一次銜接后：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 .段名段名 段號段號Main 0A 1W 2段名段名-段號對照表段號對照表X 3

34、第一次銜接后：第一次銜接后：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 3100:Load *1, 2|100;Load *2, 2|150;“7X|.“7X|0 3 3000 3 400150:200:250:W段段號段段號=2)X段段 300 40012345678300400段表段表 段首址段首址

35、.段號段號 0 1 2 3 .段名段名 段號段號Main 0A 1W 2段名段名-段號對照表段號對照表X 3第二次銜接后：第二次銜接后：動態(tài)銜接問題動態(tài)銜接問題n動態(tài)銜接與共享的矛盾動態(tài)銜接與共享的矛盾n動態(tài)銜接：修正銜接字代碼動態(tài)銜接：修正銜接字代碼n段的共享：要求純代碼段的共享：要求純代碼pure code)n處理方法處理方法n共享代碼分為共享代碼分為“純段和純段和“雜段雜段n純段共享，純段共享，n雜段私用。雜段私用。6.5.3 虛擬段頁式存儲系統(tǒng)虛擬段頁式存儲系統(tǒng)n思索思索n段的動態(tài)銜接段的動態(tài)銜接n段的共享段的共享n段長度的動態(tài)變化段長度的動態(tài)變化所需表目：所需表目：(1) 段表：每進(jìn)

36、程一個段表：每進(jìn)程一個頁表長度頁表長度 頁表首址頁表首址 訪問權(quán)限訪問權(quán)限 擴(kuò)展標(biāo)志擴(kuò)展標(biāo)志 共享段入口共享段入口 段號段號(2) 頁表：每段一個頁表：每段一個內(nèi)存頁號內(nèi)存頁號 外存塊號外存塊號 內(nèi)外標(biāo)志內(nèi)外標(biāo)志 修正標(biāo)志修正標(biāo)志 .邏輯頁號邏輯頁號(3) 共享段表：系一致個共享段表：系一致個段名段名 頁表長度頁表長度 頁表首址頁表首址 擴(kuò)展標(biāo)志擴(kuò)展標(biāo)志 共享計數(shù)共享計數(shù) (4) 段名段名-段號對照表：每進(jìn)程一個段號對照表：每進(jìn)程一個對應(yīng)關(guān)系：對應(yīng)關(guān)系：私用段私用段共享段共享段共享段表共享段表P1段表：段表：P2段表：段表：共享段表共享段表P1段表：段表：P2段表：段表： 15 16 17 1

37、8 19 20 21 22 23 24 25 . .頁表頁表頁表頁表存儲空間：存儲空間：sisjsk所需存放器：所需存放器：(1) 段表長度存放器：保管正運(yùn)轉(zhuǎn)進(jìn)程段表長度段表長度存放器：保管正運(yùn)轉(zhuǎn)進(jìn)程段表長度(2) 段表首址存放器：保管正運(yùn)轉(zhuǎn)進(jìn)程段表首址段表首址存放器：保管正運(yùn)轉(zhuǎn)進(jìn)程段表首址(3) 快表快表段號段號 邏輯頁號邏輯頁號 頁架號頁架號 訪問權(quán)限訪問權(quán)限 修正標(biāo)志修正標(biāo)志 地址映射：地址映射： : (s,p,d) (f,d) 邏輯地址邏輯地址(s,p,d)物理地址物理地址(f,d)由由(s,p)查快表得查快表得f查到查到訪問合法訪問合法構(gòu)成物理地址構(gòu)成物理地址(f,d)是間址是間址有

38、妨礙位有妨礙位繼續(xù)繼續(xù)0sl-10pl-1由由(s,b)查段表得查段表得b,l越界中斷越界中斷越界中斷越界中斷由由b和和p查頁表得查頁表得f該頁在內(nèi)存該頁在內(nèi)存缺頁中斷缺頁中斷(s,p,f)快表快表越權(quán)中斷越權(quán)中斷TFTF銜接中斷銜接中斷TFTFTFTFTl:段表長度段表長度b:段表首地址段表首地址l: 頁表長度頁表長度b: 頁表首地址頁表首地址構(gòu)成物理地址構(gòu)成物理地址(f,d)中斷處置：中斷處置：1. 銜接中斷銜接中斷(1) 一切進(jìn)程均未銜接一切進(jìn)程均未銜接(共享段表、段名共享段表、段名-段號對照表均無段號對照表均無) 建立頁表，由文件讀入外存建立頁表，由文件讀入外存swap，部分頁讀入內(nèi)存

39、，分配，部分頁讀入內(nèi)存，分配 段號，填段名段號，填段名-段號對照表，如是共享段填共享段表，填段號對照表，如是共享段填共享段表，填 段表段表 ，構(gòu)成邏輯地址。，構(gòu)成邏輯地址。(2) 其它進(jìn)程銜接過，本進(jìn)程未銜接過其它進(jìn)程銜接過，本進(jìn)程未銜接過(共享段表有，段名共享段表有，段名-段段 號對照表無號對照表無) 分配段號，填段名分配段號，填段名-段號對照表，填段表段號對照表，填段表(指向共享段表指向共享段表)， 共享記數(shù)加共享記數(shù)加1, 構(gòu)成邏輯地址。構(gòu)成邏輯地址。(3) 本進(jìn)程銜接過本進(jìn)程銜接過(段名段名-段號對照表有，共享段表有或無段號對照表有，共享段表有或無) 構(gòu)成邏輯地址。構(gòu)成邏輯地址。2.

40、缺頁中斷缺頁中斷 調(diào)入所需頁面，更新頁表和總頁表。調(diào)入所需頁面，更新頁表和總頁表。3. 越界中斷越界中斷 (1) 段號越界：錯誤處置。段號越界：錯誤處置。 (2) 頁號越界：如可擴(kuò)展，擴(kuò)展該段頁號越界：如可擴(kuò)展，擴(kuò)展該段(添加頁添加頁)，修正頁表和段，修正頁表和段 表表(頁表長度頁表長度); 如不可擴(kuò)展，錯誤處置。如不可擴(kuò)展，錯誤處置。4. 越權(quán)中斷越權(quán)中斷 錯誤處置。錯誤處置。6.6 系統(tǒng)舉例nLinux存儲管理nWindows2000/XP存儲管理lPhysical memory-management物理存儲管理物理存儲管理lThree level page table三級頁表三級頁表lB

41、uddy heap algorithm for managing memory pages (frames) 同伴堆算法管理內(nèi)存同伴堆算法管理內(nèi)存lVirtual Memory management虛擬存儲管理虛擬存儲管理lDemand paging懇求調(diào)頁懇求調(diào)頁lno pre-paging, 無預(yù)調(diào)無預(yù)調(diào)lno working set.無任務(wù)集無任務(wù)集Page replacementpage daemon: kswapd, runs once a second , keep enough free pages in memory. 頁守護(hù)進(jìn)頁守護(hù)進(jìn)程程flush daemon: bdflu

42、sh, wakes up periodically, “dirty page out.刷新守護(hù)進(jìn)程刷新守護(hù)進(jìn)程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算法記載可用存儲區(qū)算法記載可用存儲區(qū) lEach allocatable memory r

43、egion 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 by allocating an existing small free region, then a l

44、arger free region will be subdivided into two partners to satisfy the request.小區(qū)域小區(qū)域不能滿足時，分割大區(qū)域不能滿足時，分割大區(qū)域6432323216163216888321688-req(8)8req(8)-req(4)rel(8)32844164rel(8)8328883244888884432810(29)9(28) 8(27)4(23)3(22)2(21)1(20)數(shù)據(jù)構(gòu)造：數(shù)據(jù)構(gòu)造：組號空閑塊數(shù)組號空閑塊數(shù) ：鏈頭指針：鏈頭指針249681632256一樣長度的空閑塊一樣長度的空閑塊構(gòu)成一組構(gòu)成一組51210(29)9(28) 8(27)4(23)3(22)2(21)1(20)懇求長度為懇求長度為128，在第，在第8組中取一塊。假組中取一塊。假設(shè)第設(shè)第8組已空，在第組已空，在第9組取一塊，分配其組取一塊，分配其中的中的128頁，并將剩余的頁，并將剩余的128頁記入第頁記入第8組。假設(shè)第組。假設(shè)第9組也空，在第組也空，在第10組取一塊，組取一塊，進(jìn)展兩次分割，