操作系統(tǒng)第六章存儲(chǔ)課件

6.4外存資源管理外存空間劃分靜態(tài)等長(zhǎng)，2i,稱為一塊(block)，塊是外存分配的基本單位，也是IO傳輸?shù)幕締挝?。外存空間分配空閑塊鏈(慢)空閑塊表(UNIX)字位映像圖Swap空間File空間輸入井輸出井整理ppt6.4外存資源管理外存空間劃分SwapFile輸入井輸出井1進(jìn)程與外存對(duì)應(yīng)關(guān)系界地址每進(jìn)程占一組外存連續(xù)塊；每進(jìn)程占二組外存連續(xù)塊（雙對(duì)界）。頁(yè)式內(nèi)存一頁(yè)，外存一塊。段式每段占外存若干連續(xù)塊。段頁(yè)式內(nèi)存一頁(yè)，外存一塊。整理ppt進(jìn)程與外存對(duì)應(yīng)關(guān)系界地址整理ppt26.5虛擬存儲(chǔ)系統(tǒng)無(wú)虛擬問(wèn)題不能運(yùn)行比內(nèi)存大的程序；進(jìn)程全部裝入內(nèi)存，浪費(fèi)空間（進(jìn)程活動(dòng)具有局部性)。單控制流的進(jìn)程需要較少部分在內(nèi)存；多控制流的進(jìn)程需要較多部分在內(nèi)存。虛擬存儲(chǔ)進(jìn)程部分裝入內(nèi)存，部分（或全部）裝入外存，運(yùn)行時(shí)訪問(wèn)在外存部分動(dòng)態(tài)調(diào)入，內(nèi)存不夠淘汰。整理ppt6.5虛擬存儲(chǔ)系統(tǒng)整理ppt36.5.1虛擬頁(yè)式存儲(chǔ)系統(tǒng)基本原理進(jìn)程運(yùn)行前：全部裝入外存，部分裝入內(nèi)存。進(jìn)程運(yùn)行時(shí)：訪問(wèn)頁(yè)不在內(nèi)存，發(fā)生缺頁(yè)中斷，中斷處理程序：找到訪問(wèn)頁(yè)在外存的地址；在內(nèi)存找一空閑頁(yè)面；如沒(méi)有，按淘汰算法淘汰一個(gè)；如需要，將淘汰頁(yè)面寫(xiě)回外存，修改頁(yè)表和總頁(yè)表；讀入所需頁(yè)面（切換進(jìn)程）；重新啟動(dòng)中斷指令。整理ppt6.5.1虛擬頁(yè)式存儲(chǔ)系統(tǒng)基本原理整理ppt46.5.1虛擬頁(yè)式存儲(chǔ)管理(Cont.)虛擬頁(yè)式存儲(chǔ)管理地址映射指令給出邏輯地址(p,d)由p查快表得到f查到f、d合并得物理地址0≤p≤l-1越界中斷由b、p查找頁(yè)表得f該頁(yè)在內(nèi)存缺頁(yè)中斷保存現(xiàn)場(chǎng)有空閑頁(yè)框選一頁(yè)面淘汰該頁(yè)面修改過(guò)寫(xiě)回外存讀入所需頁(yè)面更新頁(yè)表和快表恢復(fù)現(xiàn)場(chǎng)FFFTTT(f,d)快表如快表滿，淘汰一表項(xiàng)硬件完成軟件完成Tf、d合并得物理地址整理ppt6.5.1虛擬頁(yè)式存儲(chǔ)管理(Cont.)虛擬頁(yè)式存儲(chǔ)管理地5對(duì)頁(yè)表的改進(jìn)：對(duì)快表的改進(jìn)：邏輯頁(yè)號(hào)…p......

...

…

...

...頁(yè)框號(hào)外存塊號(hào)內(nèi)外標(biāo)識(shí)訪問(wèn)權(quán)限修改標(biāo)志fb’(0,1){r,w,e}(0,1)...

...

…

...

......

...

…

...

邏輯頁(yè)號(hào)頁(yè)框號(hào)訪問(wèn)權(quán)限修改標(biāo)志pf{r,w,e}(0,1)...

...

…

...

整理ppt對(duì)頁(yè)表的改進(jìn)：對(duì)快表的改進(jìn)：邏輯頁(yè)號(hào)...內(nèi)存頁(yè)框分配策略（靜態(tài)策略）1.平均分配如內(nèi)存128頁(yè)，進(jìn)程25個(gè)，每個(gè)進(jìn)程5個(gè)頁(yè)架2.按進(jìn)程長(zhǎng)度比例分配pi共si個(gè)頁(yè)面；S=si；內(nèi)存共m個(gè)頁(yè)架ai=(si/S)m3.按進(jìn)程優(yōu)先級(jí)比例分配4.按進(jìn)程長(zhǎng)度和優(yōu)先級(jí)別比例分配靜態(tài)策略沒(méi)有反映：(1)程序結(jié)構(gòu)；(2)程序在不同時(shí)刻的行為特性。整理ppt內(nèi)存頁(yè)框分配策略（靜態(tài)策略）整理ppt外存塊的分配策略1.靜態(tài)分配外存保持進(jìn)程的全部頁(yè)面：優(yōu)點(diǎn)：速度快--淘汰時(shí)不必寫(xiě)回(未修改情況)缺點(diǎn)：外存浪費(fèi)2.動(dòng)態(tài)分配外存僅保持進(jìn)程不在內(nèi)存的頁(yè)面：優(yōu)點(diǎn)：節(jié)省外存缺點(diǎn)：速度慢--淘汰時(shí)必須寫(xiě)回整理ppt外存塊的分配策略整理ppt頁(yè)面調(diào)入時(shí)機(jī)1.請(qǐng)調(diào)(demandpaging)uponpagefault,發(fā)生缺頁(yè)中斷時(shí)調(diào)入。2.預(yù)調(diào)(prepaging)beforepagefault,將要訪問(wèn)時(shí)調(diào)入(根據(jù)程序順序行為，不一定準(zhǔn)）預(yù)調(diào)必須輔以請(qǐng)調(diào)。整理ppt頁(yè)面調(diào)入時(shí)機(jī)整理ppt9用于：頁(yè)淘汰、段淘汰、快表淘汰。Objective:lowestfaultrate.1.最佳淘汰算法(OPT--optimal)淘汰將來(lái)最長(zhǎng)時(shí)間以后才用到的。效率最高，notfeasible。

601203042303212016016662222260000400011333置換算法(replacementalgorithm)整理ppt用于：頁(yè)淘汰、段淘汰、快表淘汰。60120304230102.先進(jìn)先出(FIFO)淘汰最先調(diào)入的。依據(jù):先進(jìn)入的可能已經(jīng)使用完畢。實(shí)現(xiàn)：隊(duì)列negativecase:有些代碼和數(shù)據(jù)可能整個(gè)程序運(yùn)行中用到。Belady異常:例子：1，2，3，4，1，2，5，1，2，3，4，5內(nèi)存3個(gè)物理頁(yè)面：頁(yè)故障率=9/12內(nèi)存4個(gè)物理頁(yè)面：頁(yè)故障率=10/12

整理ppt2.先進(jìn)先出(FIFO)整理ppt11FIFO淘汰算法(belady異常)1234125123451114445552221113333322241234125123451111555544222211115333322224444333頁(yè)故障率=10/12頁(yè)故障率=9/12訪問(wèn)序列:訪問(wèn)序列:內(nèi)存頁(yè)面:內(nèi)存頁(yè)面:整理pptFIFO淘汰算法(belady異常)123412512345123.使用過(guò)最久的先淘汰（LRU）淘汰最近一次訪問(wèn)距當(dāng)前時(shí)間最長(zhǎng)的。Replacepagethathasn’tbeenusedforthelongestperiodoftime.實(shí)現(xiàn)：stack當(dāng)一頁(yè)面被訪問(wèn)時(shí),從棧中取出壓到棧頂,棧底是:LRUpage.例子：referencestring:4,7,0,7,1,0,1,2,1,2,7,1,22107472104StackbeforeaStackbeforebab整理ppt3.使用過(guò)最久的先淘汰（LRU）27Stackbefor13LRU算法60120304230321201601666224440111000000333001133222226整理pptLRU算法6012030423032120160166622144.最近不用的先淘汰(notusedrecently)淘汰最近一段時(shí)間未用到的。實(shí)現(xiàn)：每頁(yè)增加一個(gè)訪問(wèn)標(biāo)志，訪問(wèn)置1，定時(shí)清0，淘汰時(shí)取標(biāo)志為0的。LRU算法的近似：Referencestring:2,3,5,6,4,2,5,6,7,5,6,8,標(biāo)志清0選擇淘汰LRU：3NUR：2，3，4任意整理ppt4.最近不用的先淘汰(notusedrecently)155.最不經(jīng)常使用的先淘汰(LFU)淘汰使用次數(shù)最少的。依據(jù):活躍訪問(wèn)頁(yè)面應(yīng)有較大的訪問(wèn)次數(shù).Suffer:(1)前期使用多，但以后不用，難換出；(2)剛調(diào)入的頁(yè)面，引用少，被換出可能大。實(shí)現(xiàn)：記數(shù)器，調(diào)入清0，訪問(wèn)增1，淘汰選取最小者。6.最經(jīng)常使用的先淘汰(MFU)淘汰使用次數(shù)最多的。依據(jù):使用多的可能已經(jīng)用完了。Suffer:程序有些成分是在整個(gè)程序運(yùn)行中都使用的。整理ppt5.最不經(jīng)常使用的先淘汰(LFU)整理ppt167.二次機(jī)會(huì)(secondchance)淘汰裝入最久且最近未被訪問(wèn)的頁(yè)面。實(shí)現(xiàn)時(shí)：采用拉鏈數(shù)據(jù)結(jié)構(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/1整理ppt7.二次機(jī)會(huì)(secondchance)淘汰裝入最久且最178.時(shí)鐘算法(clockalgorithm)將頁(yè)面組織成環(huán)形，有一個(gè)指針指向當(dāng)前位置。每次需要淘汰頁(yè)面時(shí)，從指針?biāo)傅捻?yè)面開(kāi)始檢查。如果當(dāng)前頁(yè)面的訪問(wèn)位為0，即從上次檢測(cè)到目前，該頁(yè)沒(méi)有訪問(wèn)過(guò)，則將該頁(yè)替換。如果當(dāng)前頁(yè)面的訪問(wèn)位為1，則將其清0，并順時(shí)針移動(dòng)指針到下一個(gè)位置。重復(fù)上述步驟直至找到一個(gè)訪問(wèn)位為0的頁(yè)面。可以看出，時(shí)鐘算法與二次機(jī)會(huì)算法的淘汰效果是基本相同的，差別在于二者所采用的數(shù)據(jù)結(jié)構(gòu)不同，二次機(jī)會(huì)使用的是鏈表，需要額外存儲(chǔ)空間，且摘鏈入鏈速度很慢。而時(shí)鐘算法可直接利用頁(yè)表中的引用位，外加一個(gè)指針，速度快且節(jié)省空間。整理ppt8.時(shí)鐘算法(clockalgorithm)將頁(yè)面組織成18頁(yè)6/r=1頁(yè)3/r=1頁(yè)4/r=0頁(yè)8/r=0頁(yè)10/r=1頁(yè)9/r=0頁(yè)0/r=0頁(yè)1/r=1框12框23框51框6框81框96框60框5訪問(wèn)第18頁(yè)時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=1頁(yè)4/r=0頁(yè)8/r=0頁(yè)10/r=19頁(yè)6/r=0頁(yè)3/r=1頁(yè)4/r=0頁(yè)8/r=0頁(yè)10/r=1頁(yè)9/r=0頁(yè)0/r=0頁(yè)1/r=1框12框23框51框6框81框96框60框5訪問(wèn)第18頁(yè)時(shí)鐘算法整理ppt頁(yè)6/r=0頁(yè)3/r=1頁(yè)4/r=0頁(yè)8/r=0頁(yè)10/r=20頁(yè)6/r=1頁(yè)3/r=0頁(yè)4/r=0頁(yè)8/r=0頁(yè)10/r=1頁(yè)9/r=0頁(yè)0/r=0頁(yè)1/r=1框12框23框51框6框81框96框60框5訪問(wèn)第18頁(yè)時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=0頁(yè)4/r=0頁(yè)8/r=0頁(yè)10/r=21頁(yè)6/r=0頁(yè)3/r=0頁(yè)18/r=1頁(yè)8/r=0頁(yè)10/r=1頁(yè)9/r=0頁(yè)0/r=0頁(yè)1/r=1框12框23框51框6框81框96框60框5替換第4頁(yè)時(shí)鐘算法整理ppt頁(yè)6/r=0頁(yè)3/r=0頁(yè)18/r=1頁(yè)8/r=0頁(yè)10/r22改進(jìn)的時(shí)鐘算法考慮修改標(biāo)志mr=0,m=0：最佳淘汰頁(yè)面r=0,m=1：淘汰前回寫(xiě)r=1,m=0：不淘汰r=1,m=1：不淘汰整理ppt改進(jìn)的時(shí)鐘算法考慮修改標(biāo)志m整理ppt23改進(jìn)的時(shí)鐘算法步驟1：由指針當(dāng)前位置開(kāi)始掃描，選擇最佳淘汰頁(yè)面，不改變引用位，將第一個(gè)遇到的r=0且m=0的頁(yè)面作為淘汰頁(yè)面；步驟2：如步驟1失敗，再次從原位置開(kāi)始，找r=0且m=1的頁(yè)面，將第一個(gè)滿足上述要求的頁(yè)面作為淘汰頁(yè)面，同時(shí)將掃描過(guò)頁(yè)面的r位清0；步驟3：若步驟2失敗，指針再次回到原位置，重新執(zhí)行步驟1。若還失敗再次執(zhí)行步驟2，此時(shí)定能找到。整理ppt改進(jìn)的時(shí)鐘算法步驟1：整理ppt24頁(yè)6/r=1m=1頁(yè)3/r=1m=1頁(yè)18/r=1m=0頁(yè)8/r=1m=0頁(yè)10/r=1m=0頁(yè)9/r=0m=1頁(yè)0/r=0m=1頁(yè)1/r=1m=0框12框23框51框6框81框96框60框5訪問(wèn)第15頁(yè)改進(jìn)的時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=1頁(yè)18/r=1頁(yè)8/r=1頁(yè)10/r25頁(yè)6/r=1m=1頁(yè)3/r=1m=1頁(yè)18/r=1m=0頁(yè)8/r=1m=0頁(yè)10/r=1m=0頁(yè)9/r=0m=1頁(yè)0/r=0m=1頁(yè)1/r=1m=0框12框23框51框6框81框96框60框5訪問(wèn)第15頁(yè)改進(jìn)的時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=1頁(yè)18/r=1頁(yè)8/r=1頁(yè)10/r26頁(yè)6/r=1m=1頁(yè)3/r=1m=1頁(yè)18/r=1m=0頁(yè)8/r=0m=0頁(yè)10/r=1m=0頁(yè)9/r=0m=1頁(yè)0/r=0m=1頁(yè)1/r=1m=0框12框23框51框6框81框96框60框5訪問(wèn)第15頁(yè)改進(jìn)的時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=1頁(yè)18/r=1頁(yè)8/r=0頁(yè)10/r27頁(yè)6/r=1m=1頁(yè)3/r=1m=1頁(yè)18/r=1m=0頁(yè)8/r=0m=0頁(yè)10/r=0m=0頁(yè)9/r=0m=1頁(yè)0/r=0m=1頁(yè)1/r=1m=0框12框23框51框6框81框96框60框5訪問(wèn)第15頁(yè)時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=1頁(yè)18/r=1頁(yè)8/r=0頁(yè)10/r28頁(yè)6/r=1m=1頁(yè)3/r=1m=1頁(yè)18/r=1m=0頁(yè)8/r=0m=0頁(yè)10/r=0m=0頁(yè)15/r=1m=0頁(yè)0/r=0m=1頁(yè)1/r=1m=0框12框23框51框6框81框96框60框5時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=1頁(yè)18/r=1頁(yè)8/r=0頁(yè)10/r292010年考研試題某虛擬頁(yè)式系統(tǒng)，進(jìn)程空間和內(nèi)存空間都是64k，頁(yè)長(zhǎng)1K，某進(jìn)程6個(gè)頁(yè)，內(nèi)存分配4個(gè)頁(yè)框，采用局部置換，280時(shí)刻頁(yè)表和Clock數(shù)據(jù)結(jié)構(gòu)如下：邏輯頁(yè)號(hào)頁(yè)框號(hào)裝入時(shí)間訪問(wèn)標(biāo)志0511011---2121601

3823014---538010頁(yè)2頁(yè)3頁(yè)5頁(yè)框5框12框8框3(順時(shí)針)整理ppt2010年考研試題某虛擬頁(yè)式系統(tǒng)，進(jìn)程空間和內(nèi)存空間都是64302010年考研試題(1)280時(shí)刻訪問(wèn)13B7H，邏輯頁(yè)號(hào)是多少？(2)采用FIFO置換算法，物理頁(yè)框號(hào)是多少？物理地址是多少？(3)采用CLOCK置換算法，頁(yè)框號(hào)是多少？物理地址是多少？整理ppt2010年考研試題(1)280時(shí)刻訪問(wèn)13B7H，邏輯頁(yè)號(hào)是312010年考研試題（1）邏輯地址13B7H化為二進(jìn)制數(shù)為0001001110110111，其中后10位為頁(yè)內(nèi)地址，前6位為邏輯頁(yè)號(hào)，即邏輯頁(yè)號(hào)為4。（2）4號(hào)頁(yè)不在內(nèi)存，發(fā)生缺頁(yè)中斷，按FIFO置換算法，應(yīng)置換第5頁(yè)，所得頁(yè)框號(hào)3，形成物理地址0000111110110111，劃成16進(jìn)制為0FB7H。（3）采用CLOCK置換算法，淘汰第0頁(yè)，得頁(yè)框5，形成物理地址為0001011110110111，劃成16進(jìn)制為17B7H。整理ppt2010年考研試題（1）邏輯地址13B7H化為二進(jìn)制數(shù)為003顛簸(thrashing)

頁(yè)面在內(nèi)存與外存之間頻繁換入換出。原因：(1)分給進(jìn)程物理頁(yè)架過(guò)少；(2)淘汰算法不合理。處理：(1)增加分給進(jìn)程物理頁(yè)架數(shù)；(2)改進(jìn)淘汰算法。思考題：在某些虛擬頁(yè)式存儲(chǔ)管理系統(tǒng)中，內(nèi)存中總保持一個(gè)空閑的物理頁(yè)架，這樣做有什么好處？整理ppt顛簸(thrashing)思考題：整理ppt3工作集模型(workingsetmodel)

工作集(workingset):進(jìn)程在一段時(shí)間內(nèi)所訪問(wèn)頁(yè)面的集合。

WS(t,)={5,7,1,6,2}…2615777751622123…(pagereference)t：稱為窗口尺寸(windowsize)。Denning認(rèn)為：為使程序有效運(yùn)行，工作集應(yīng)能放入內(nèi)存。T整理ppt工作集模型(workingsetmode34WS(t1,)={5,7,1,6,2}…2615777751622123444343444134...WS(t2,)={2,3,4}t1t2工作集與時(shí)間有關(guān)：工作集與窗口尺寸有關(guān)：程序大小WS整理pptWS(t1,)={5,7,1,6,2}…2615735窗口尺寸確定：過(guò)?。夯顒?dòng)頁(yè)面不能全部裝入，頁(yè)故障率高；過(guò)大：內(nèi)存浪費(fèi)。Madnick,Donovan建議：＝1萬(wàn)次訪內(nèi)。實(shí)現(xiàn)：頁(yè)表中增加訪問(wèn)位：

…訪問(wèn)位頁(yè)表：開(kāi)始時(shí)，全部清0,訪問(wèn)：置1,結(jié)束時(shí)(新開(kāi)始時(shí))訪問(wèn)標(biāo)志為1的，為該期間工作集，τn+1=αwn+(1-α)τn整理ppt窗口尺寸確定：…訪問(wèn)位頁(yè)3頁(yè)故障率反饋模型PFFB(PageFaultFeedBack)頁(yè)故障率高(達(dá)到某上界閾值)：內(nèi)存頁(yè)面少，增加。頁(yè)故障率低(達(dá)到某下界閾值)：內(nèi)存頁(yè)面多，減少。整理ppt頁(yè)故障率反饋模型整理ppt376.5.2虛擬段式存儲(chǔ)系統(tǒng)進(jìn)程運(yùn)行前，全部裝入外存，部分裝入內(nèi)存，訪問(wèn)段不再內(nèi)存時(shí)，發(fā)生缺段中斷。整理ppt6.5.2虛擬段式存儲(chǔ)系統(tǒng)進(jìn)程運(yùn)行前，全部裝入外存，部分裝386.5.2虛擬段式存儲(chǔ)系統(tǒng)(Cont.)虛擬段式存儲(chǔ)管理地址映射指令確定邏輯地址(s,d)由s查快表得到b’和l’查到b’+d得到物理地址0≤s≤l-1越界中斷由b、s查找段表該段在內(nèi)存缺段中斷保存現(xiàn)場(chǎng)內(nèi)存可滿足選一段淘汰該段修改過(guò)寫(xiě)回外存讀入該段修改段表和快表恢復(fù)現(xiàn)場(chǎng)FFFTTT(s,b’,l’)快表如快表滿，淘汰一表項(xiàng)硬件完成軟件完成T0≤d≤l’-1T越界中斷F0≤d≤l’-1越界中斷b’+d得物理地址找到該段在外存的位置緊湊夠緊湊TTF修改段表整理ppt6.5.2虛擬段式存儲(chǔ)系統(tǒng)(Cont.)虛擬段式存儲(chǔ)管理地39...

...

…

...

...…段號(hào)…s...段長(zhǎng)內(nèi)存首址外存首址權(quán)限內(nèi)外標(biāo)識(shí)修改標(biāo)志l’b’b”{rwe}(0,1)(0,1)...

...

…

...

...…(1)段表的改進(jìn)：(２)快表的改進(jìn)：...

...

…

...

...段號(hào)段長(zhǎng)內(nèi)存首址訪問(wèn)權(quán)限修改標(biāo)志sl’b’{rwe}(0,1)...

...

…

...

...整理ppt......40段的動(dòng)態(tài)連接(dynamiclinking)動(dòng)態(tài)連接vs.靜態(tài)連接靜態(tài)連接：運(yùn)行前連接，由link完成；動(dòng)態(tài)連接：運(yùn)行時(shí)連接，由OS完成.靜態(tài)連接的缺點(diǎn)連接時(shí)間長(zhǎng)；目標(biāo)代碼長(zhǎng)；連接段可能并不執(zhí)行(未用到)。整理ppt段的動(dòng)態(tài)連接(dynamiclinking41動(dòng)態(tài)連接的實(shí)現(xiàn)(Multics為例)段名-段號(hào)對(duì)照表：每進(jìn)程一個(gè)段名段號(hào)snamesnum…...…...符號(hào)名段內(nèi)位移func150…...…...符號(hào)表：每段一個(gè)段形式：符號(hào)表目標(biāo)代碼或者數(shù)據(jù)靜態(tài)連接由link使用連接完不再需要整理ppt動(dòng)態(tài)連接的實(shí)現(xiàn)(Multics為例)段名段號(hào)sna42(1)編譯(匯編)時(shí)：遇到訪問(wèn)外段指令，采用間接尋址，指向一個(gè)間接字：LD1:未連接0:已連接符號(hào)地址：“[X]|<Y>”邏輯地址：(段號(hào),段內(nèi)地址)(2)執(zhí)行時(shí)：遇到間接指令，且L=1,發(fā)生鏈接中斷，處理程序：(a)由D取出符號(hào)地址；(b)由段名查段名-段號(hào)對(duì)照表，是否分配段號(hào)。整理ppt(1)編譯(匯編)時(shí)：LD1:未連接0:已連接符號(hào)地址43

已分配段號(hào)：取出該段號(hào)，查段表找到該段(內(nèi)存或外存)，由入口名查符號(hào)表得段內(nèi)地址；(段號(hào)，段內(nèi)地址)D,0L未分配段號(hào)：找到該段所在文件，讀入內(nèi)存，讀入外存，分配段號(hào)，填寫(xiě)段名-段號(hào)對(duì)照表，填寫(xiě)段表，轉(zhuǎn)(b)例子：匯編前：...Load1,[X]|<Y>…Load2,[X]|<Z>...[W]段[X]段…1234…5678...Y:Z:整理ppt已分配段號(hào)：取出該段號(hào)，查段表找到44匯編后，連接前：100:Load*1,2|100;…Load*2,2|150;……“7[X]|<Y>”...“7[X]|<Z>”1…22001…2250150:200:250:[W]段（段號(hào)=2)[X]段<Y>300<Z>40012345678300400段表…段首址…...段號(hào)0123

...段名段號(hào)[Main]

0[A]1[W]2段名-段號(hào)對(duì)照表整理ppt匯編后，連接前：100:Load*1,2|100;145第一次連接后：100:Load*1,2|100;…Load*2,2|150;……“7[X]|<Y>”...“7[X]|<Z>”1

…

22001…2250150:200:250:[W]段（段號(hào)=2)[X]段<Y>300<Z>40012345678300400段表…段首址…...段號(hào)0123

...段名段號(hào)[Main]

0[A]1[W]2段名-段號(hào)對(duì)照表[X]3整理ppt第一次連接后：100:Load*1,2|100;146第一次連接后：100:Load*1,2|100;…Load*2,2|150;……“7[X]|<Y>”...“7[X]|<Z>”0

…

33001…2250150:200:250:[W]段（段號(hào)=2)[X]段<Y>300<Z>40012345678300400段表…段首址…...段號(hào)0123

...段名段號(hào)[Main]

0[A]1[W]2段名-段號(hào)對(duì)照表[X]3整理ppt第一次連接后：100:Load*1,2|100;047100:Load*1,2|100;…Load*2,2|150;……“7[X]|<Y>”...“7[X]|<Z>”0…33000

…

3400150:200:250:[W]段（段號(hào)=2)[X]段<Y>300<Z>40012345678300400段表…段首址…...段號(hào)0123

...段名段號(hào)[Main]

0[A]1[W]2段名-段號(hào)對(duì)照表[X]3第二次連接后：整理ppt100:Load*1,2|100;0…48動(dòng)態(tài)連接問(wèn)題動(dòng)態(tài)連接與共享的矛盾動(dòng)態(tài)連接：修改連接字（代碼）段的共享：要求純代碼（purecode)解決方法共享代碼分為“純段”和“雜段”純段共享，雜段私用。整理ppt動(dòng)態(tài)連接問(wèn)題動(dòng)態(tài)連接與共享的矛盾整理ppt496.5.3虛擬段頁(yè)式存儲(chǔ)系統(tǒng)考慮段的動(dòng)態(tài)連接段的共享段長(zhǎng)度的動(dòng)態(tài)變化整理ppt6.5.3虛擬段頁(yè)式存儲(chǔ)系統(tǒng)考慮整理ppt50所需表目：(1)段表：每進(jìn)程一個(gè)頁(yè)表長(zhǎng)度頁(yè)表首址訪問(wèn)權(quán)限擴(kuò)展標(biāo)志共享段入口……………

段號(hào)(2)頁(yè)表：每段一個(gè)內(nèi)存頁(yè)號(hào)外存塊號(hào)內(nèi)外標(biāo)志修改標(biāo)志

………...邏輯頁(yè)號(hào)(3)共享段表：系統(tǒng)一個(gè)段名頁(yè)表長(zhǎng)度頁(yè)表首址擴(kuò)充標(biāo)志共享計(jì)數(shù)……………

整理ppt所需表目：(1)段表：每進(jìn)程一個(gè)頁(yè)表長(zhǎng)度頁(yè)表首址訪51(4)段名-段號(hào)對(duì)照表：每進(jìn)程一個(gè)對(duì)應(yīng)關(guān)系：私用段共享段共享段表P1段表：P2段表：整理ppt(4)段名-段號(hào)對(duì)照表：每進(jìn)程一個(gè)私用段共享段共享段表P152共享段表P1段表：P2段表：1516171819202122232425

...

...頁(yè)表頁(yè)表存儲(chǔ)空間：sisjsk整理ppt共享段表P1段表：P2段表：15161753所需寄存器：(1)段表長(zhǎng)度寄存器：保存正運(yùn)行進(jìn)程段表長(zhǎng)度(2)段表首址寄存器：保存正運(yùn)行進(jìn)程段表首址(3)快表段號(hào)邏輯頁(yè)號(hào)頁(yè)架號(hào)訪問(wèn)權(quán)限修改標(biāo)志……………地址映射：:(s,p,d)(f,d){}邏輯地址(s,p,d)物理地址(f,d)整理ppt所需寄存器：段號(hào)邏輯頁(yè)號(hào)頁(yè)架號(hào)54由(s,p)查快表得f查到訪問(wèn)合法形成物理地址(f,d)是間址有障礙位繼續(xù)0sl-10pl’-1由(s,b)查段表得b’,l’越界中斷越界中斷由b’和p查頁(yè)表得f該頁(yè)在內(nèi)存缺頁(yè)中斷(s,p,f)快表越權(quán)中斷TFTF連接中斷TFTFTFTFTl:段表長(zhǎng)度b:段表首地址l’:頁(yè)表長(zhǎng)度b’:頁(yè)表首地址形成物理地址(f,d)整理ppt由(s,p)查快表得f查到訪問(wèn)合法形成物理地址(f,d)是間55中斷處理：1.連接中斷(1)所有進(jìn)程均未連接(共享段表、段名-段號(hào)對(duì)照表均無(wú))建立頁(yè)表，由文件讀入外存swap，部分頁(yè)讀入內(nèi)存，分配段號(hào)，填段名-段號(hào)對(duì)照表，如是共享段填共享段表，填段表，形成邏輯地址。(2)其它進(jìn)程連接過(guò)，本進(jìn)程未連接過(guò)(共享段表有，段名-段號(hào)對(duì)照表無(wú))分配段號(hào)，填段名-段號(hào)對(duì)照表，填段表(指向共享段表)，共享記數(shù)加1,形成邏輯地址。(3)本進(jìn)程連接過(guò)(段名-段號(hào)對(duì)照表有，共享段表有或無(wú))形成邏輯地址。整理ppt中斷處理：整理ppt562.缺頁(yè)中斷調(diào)入所需頁(yè)面，更新頁(yè)表和總頁(yè)表。3.越界中斷(1)段號(hào)越界：錯(cuò)誤處理。(2)頁(yè)號(hào)越界：如可擴(kuò)展，擴(kuò)展該段(增加頁(yè))，修改頁(yè)表和段表(頁(yè)表長(zhǎng)度);如不可擴(kuò)展，錯(cuò)誤處理。4.越權(quán)中斷錯(cuò)誤處理。整理ppt2.缺頁(yè)中斷整理ppt576.6系統(tǒng)舉例Linux存儲(chǔ)管理Windows2000/XP存儲(chǔ)管理整理ppt6.6系統(tǒng)舉例Linux存儲(chǔ)管理整理ppt586.6.1Linux存儲(chǔ)管理Physicalmemory-management（物理存儲(chǔ)管理）Threelevelpagetable（三級(jí)頁(yè)表）Buddyheapalgorithmformanagingmemorypages(frames)（伙伴堆算法管理內(nèi)存）VirtualMemorymanagement（虛擬存儲(chǔ)管理）Demandpaging（請(qǐng)求調(diào)頁(yè)）nopre-paging,（無(wú)預(yù)調(diào)）noworkingset.（無(wú)工作集）整理ppt6.6.1Linux存儲(chǔ)管理Physicalmemor596.6.1Linux存儲(chǔ)管理Pagereplacementpagedaemon:kswapd,runsonceasecond,keepenoughfreepagesinmemory.（頁(yè)守護(hù)進(jìn)程）flushdaemon:bdflush,wakesupperiodically,“dirtypageout”.（刷新守護(hù)進(jìn)程）整理ppt6.6.1Linux存儲(chǔ)管理Pagereplaceme60ManagingPhysicalMemoryAllocaterangesofphysically-contiguouspagesonrequest.（為進(jìn)程分配連續(xù)存儲(chǔ)區(qū)）Theallocatorusesabuddy-heapalgorithmtokeeptrackofavailablephysicalpages.(Buddyheap算法記載可用存儲(chǔ)區(qū)）

Eachallocatablememoryregionispairedwithanadjacentpartner.（每個(gè)可用存儲(chǔ)區(qū)有一個(gè)伙伴）整理pptManagingPhysicalMemoryAlloca61ManagingPhysicalMemoryWhenevertwoallocatedpartnerregionsarebothfreeduptheyarecombinedtoformalargerregion.（兩個(gè)相鄰的伙伴被釋放時(shí)，合并為一個(gè)大空閑區(qū)）

Ifamemoryrequestcannotbesatisfiedbyallocatinganexistingsmallfreeregion,thenalargerfreeregionwillbesubdividedintotwopartnerstosatisfytherequest.（小區(qū)域不能滿足時(shí)，分割大區(qū)域）整理pptManagingPhysicalMemoryWhenev62Buddyheap存儲(chǔ)分配

6432323216163216888321688req(8)8req(8)req(4)rel(8)32844164rel(8)83288832448888844328整理pptBuddyheap存儲(chǔ)分配6432161688168--6310(29)9(28)8(27)…4(23)3(22)2(21)1(20)數(shù)據(jù)結(jié)構(gòu)：組號(hào)（空閑塊數(shù)

）：鏈頭指針BuddyHeapImplementation249681632256相同長(zhǎng)度的空閑塊構(gòu)成一組512整理ppt10(29)9(28)8(27)…4(23)3(22)2(6410(29)9(28)8(27)…4(23)3(22)2(21)1(20)申請(qǐng)長(zhǎng)度為128，在第8組中取一塊。若第8組已空，在第9組取一塊，分配其中的128頁(yè)，并將剩余的128頁(yè)記入第8組。若第9組也空，在第10組取一塊，進(jìn)行兩次分割，分配128頁(yè)，剩余的128頁(yè)和256頁(yè)分別記入第8組和第9組。釋放是上述操作的逆過(guò)程，考慮伙伴的合并。兩個(gè)塊為伙伴的條件是:（1）兩個(gè)塊的大小相同，如b個(gè)頁(yè)面；（2）兩個(gè)塊的物理地址連續(xù)；（3）位于后面塊的最后頁(yè)面編號(hào)必須是2b的整數(shù)倍。BuddyHeapImplementation整理ppt10(29)9(28)8(27)…4(23)3(22)2(65BuddyHeapImplementationIunitblockhead2unitblockhead4unitblockhead8unitblockheadI6unitblockhead32unitblockhead...Problem:internalfragmentationeg:req(17)secondmemoryallocationcarvesslabs(smallunits)andmanagethemseparatelythirdmemoryallocationforallocationofno-contiguousmemory整理pptBuddyHeapImplementationIuni66作業(yè)總結(jié)：P109，#17VarB:Array[0..k-1]Ofobject;i,j:0..k-1;(0,k-1)S1,S2,S3,S4,S5,mutex:semaphore;(k,0,0,k-2,k-1,1);W1:CycleProduceaframe;P(S4);P(S1);P(mutex);B[I]:=frame;i:=i+1;V(mutex);V(S2);End;W2:CycleProduceacycle;P(S5);P(S1);P(mutex);B[j]:=cycle;j:=j-1;V(mutex);V(S3);End;W3:CycleP(S2);P(mutex);I:=I-1;f:=B[I];V(mutex);V(S4);V(S1);P(S3);P(S3);P(mutex);j:=j+1;c1:=B[j];j:=j+1;c2:=B[j];V(mutex);V(S5);V(S5);V(S1);V(S1);makeabikeEnd;整理ppt作業(yè)總結(jié)：P109，#17W1:W2:W3:P(m67Readersandwritersproblem,Adasolution.task

bodyreaders_writersisrcount,wcount:integer;beginrcount:=0;wcount:=0;

loop

select

whenwcount=0=>

acceptstart_readdorcount:=rcount+1;

endstart_read

or

whenrcount>0

acceptfinish_readdorcount:=rcount-1;

endfinish_read整理pptReadersandwritersproblem,A68

or

whenwcount=0=>

acceptstart_writedo

whilercount<>0do

acceptfinish_readdorcount:=rcount-1;

endfinish_read

end

while

endstart_write

or

whenwcount>0=>

acceptfinish_writedowcount:=wcount-1

endfinish_write

end

select

end

loopendreaders_writers;整理pptorwhenwcount=0=>整696.4外存資源管理外存空間劃分靜態(tài)等長(zhǎng)，2i,稱為一塊(block)，塊是外存分配的基本單位，也是IO傳輸?shù)幕締挝?。外存空間分配空閑塊鏈(慢)空閑塊表(UNIX)字位映像圖Swap空間File空間輸入井輸出井整理ppt6.4外存資源管理外存空間劃分SwapFile輸入井輸出井70進(jìn)程與外存對(duì)應(yīng)關(guān)系界地址每進(jìn)程占一組外存連續(xù)塊；每進(jìn)程占二組外存連續(xù)塊（雙對(duì)界）。頁(yè)式內(nèi)存一頁(yè)，外存一塊。段式每段占外存若干連續(xù)塊。段頁(yè)式內(nèi)存一頁(yè)，外存一塊。整理ppt進(jìn)程與外存對(duì)應(yīng)關(guān)系界地址整理ppt716.5虛擬存儲(chǔ)系統(tǒng)無(wú)虛擬問(wèn)題不能運(yùn)行比內(nèi)存大的程序；進(jìn)程全部裝入內(nèi)存，浪費(fèi)空間（進(jìn)程活動(dòng)具有局部性)。單控制流的進(jìn)程需要較少部分在內(nèi)存；多控制流的進(jìn)程需要較多部分在內(nèi)存。虛擬存儲(chǔ)進(jìn)程部分裝入內(nèi)存，部分（或全部）裝入外存，運(yùn)行時(shí)訪問(wèn)在外存部分動(dòng)態(tài)調(diào)入，內(nèi)存不夠淘汰。整理ppt6.5虛擬存儲(chǔ)系統(tǒng)整理ppt726.5.1虛擬頁(yè)式存儲(chǔ)系統(tǒng)基本原理進(jìn)程運(yùn)行前：全部裝入外存，部分裝入內(nèi)存。進(jìn)程運(yùn)行時(shí)：訪問(wèn)頁(yè)不在內(nèi)存，發(fā)生缺頁(yè)中斷，中斷處理程序：找到訪問(wèn)頁(yè)在外存的地址；在內(nèi)存找一空閑頁(yè)面；如沒(méi)有，按淘汰算法淘汰一個(gè)；如需要，將淘汰頁(yè)面寫(xiě)回外存，修改頁(yè)表和總頁(yè)表；讀入所需頁(yè)面（切換進(jìn)程）；重新啟動(dòng)中斷指令。整理ppt6.5.1虛擬頁(yè)式存儲(chǔ)系統(tǒng)基本原理整理ppt736.5.1虛擬頁(yè)式存儲(chǔ)管理(Cont.)虛擬頁(yè)式存儲(chǔ)管理地址映射指令給出邏輯地址(p,d)由p查快表得到f查到f、d合并得物理地址0≤p≤l-1越界中斷由b、p查找頁(yè)表得f該頁(yè)在內(nèi)存缺頁(yè)中斷保存現(xiàn)場(chǎng)有空閑頁(yè)框選一頁(yè)面淘汰該頁(yè)面修改過(guò)寫(xiě)回外存讀入所需頁(yè)面更新頁(yè)表和快表恢復(fù)現(xiàn)場(chǎng)FFFTTT(f,d)快表如快表滿，淘汰一表項(xiàng)硬件完成軟件完成Tf、d合并得物理地址整理ppt6.5.1虛擬頁(yè)式存儲(chǔ)管理(Cont.)虛擬頁(yè)式存儲(chǔ)管理地74對(duì)頁(yè)表的改進(jìn)：對(duì)快表的改進(jìn)：邏輯頁(yè)號(hào)…p......

...

…

...

...頁(yè)框號(hào)外存塊號(hào)內(nèi)外標(biāo)識(shí)訪問(wèn)權(quán)限修改標(biāo)志fb’(0,1){r,w,e}(0,1)...

...

…

...

......

...

…

...

邏輯頁(yè)號(hào)頁(yè)框號(hào)訪問(wèn)權(quán)限修改標(biāo)志pf{r,w,e}(0,1)...

...

…

...

整理ppt對(duì)頁(yè)表的改進(jìn)：對(duì)快表的改進(jìn)：邏輯頁(yè)號(hào)...7內(nèi)存頁(yè)框分配策略（靜態(tài)策略）1.平均分配如內(nèi)存128頁(yè)，進(jìn)程25個(gè)，每個(gè)進(jìn)程5個(gè)頁(yè)架2.按進(jìn)程長(zhǎng)度比例分配pi共si個(gè)頁(yè)面；S=si；內(nèi)存共m個(gè)頁(yè)架ai=(si/S)m3.按進(jìn)程優(yōu)先級(jí)比例分配4.按進(jìn)程長(zhǎng)度和優(yōu)先級(jí)別比例分配靜態(tài)策略沒(méi)有反映：(1)程序結(jié)構(gòu)；(2)程序在不同時(shí)刻的行為特性。整理ppt內(nèi)存頁(yè)框分配策略（靜態(tài)策略）整理ppt7外存塊的分配策略1.靜態(tài)分配外存保持進(jìn)程的全部頁(yè)面：優(yōu)點(diǎn)：速度快--淘汰時(shí)不必寫(xiě)回(未修改情況)缺點(diǎn)：外存浪費(fèi)2.動(dòng)態(tài)分配外存僅保持進(jìn)程不在內(nèi)存的頁(yè)面：優(yōu)點(diǎn)：節(jié)省外存缺點(diǎn)：速度慢--淘汰時(shí)必須寫(xiě)回整理ppt外存塊的分配策略整理ppt7頁(yè)面調(diào)入時(shí)機(jī)1.請(qǐng)調(diào)(demandpaging)uponpagefault,發(fā)生缺頁(yè)中斷時(shí)調(diào)入。2.預(yù)調(diào)(prepaging)beforepagefault,將要訪問(wèn)時(shí)調(diào)入(根據(jù)程序順序行為，不一定準(zhǔn)）預(yù)調(diào)必須輔以請(qǐng)調(diào)。整理ppt頁(yè)面調(diào)入時(shí)機(jī)整理ppt78用于：頁(yè)淘汰、段淘汰、快表淘汰。Objective:lowestfaultrate.1.最佳淘汰算法(OPT--optimal)淘汰將來(lái)最長(zhǎng)時(shí)間以后才用到的。效率最高，notfeasible。

601203042303212016016662222260000400011333置換算法(replacementalgorithm)整理ppt用于：頁(yè)淘汰、段淘汰、快表淘汰。60120304230792.先進(jìn)先出(FIFO)淘汰最先調(diào)入的。依據(jù):先進(jìn)入的可能已經(jīng)使用完畢。實(shí)現(xiàn)：隊(duì)列negativecase:有些代碼和數(shù)據(jù)可能整個(gè)程序運(yùn)行中用到。Belady異常:例子：1，2，3，4，1，2，5，1，2，3，4，5內(nèi)存3個(gè)物理頁(yè)面：頁(yè)故障率=9/12內(nèi)存4個(gè)物理頁(yè)面：頁(yè)故障率=10/12

整理ppt2.先進(jìn)先出(FIFO)整理ppt80FIFO淘汰算法(belady異常)1234125123451114445552221113333322241234125123451111555544222211115333322224444333頁(yè)故障率=10/12頁(yè)故障率=9/12訪問(wèn)序列:訪問(wèn)序列:內(nèi)存頁(yè)面:內(nèi)存頁(yè)面:整理pptFIFO淘汰算法(belady異常)123412512345813.使用過(guò)最久的先淘汰（LRU）淘汰最近一次訪問(wèn)距當(dāng)前時(shí)間最長(zhǎng)的。Replacepagethathasn’tbeenusedforthelongestperiodoftime.實(shí)現(xiàn)：stack當(dāng)一頁(yè)面被訪問(wèn)時(shí),從棧中取出壓到棧頂,棧底是:LRUpage.例子：referencestring:4,7,0,7,1,0,1,2,1,2,7,1,22107472104StackbeforeaStackbeforebab整理ppt3.使用過(guò)最久的先淘汰（LRU）27Stackbefor82LRU算法60120304230321201601666224440111000000333001133222226整理pptLRU算法6012030423032120160166622834.最近不用的先淘汰(notusedrecently)淘汰最近一段時(shí)間未用到的。實(shí)現(xiàn)：每頁(yè)增加一個(gè)訪問(wèn)標(biāo)志，訪問(wèn)置1，定時(shí)清0，淘汰時(shí)取標(biāo)志為0的。LRU算法的近似：Referencestring:2,3,5,6,4,2,5,6,7,5,6,8,標(biāo)志清0選擇淘汰LRU：3NUR：2，3，4任意整理ppt4.最近不用的先淘汰(notusedrecently)845.最不經(jīng)常使用的先淘汰(LFU)淘汰使用次數(shù)最少的。依據(jù):活躍訪問(wèn)頁(yè)面應(yīng)有較大的訪問(wèn)次數(shù).Suffer:(1)前期使用多，但以后不用，難換出；(2)剛調(diào)入的頁(yè)面，引用少，被換出可能大。實(shí)現(xiàn)：記數(shù)器，調(diào)入清0，訪問(wèn)增1，淘汰選取最小者。6.最經(jīng)常使用的先淘汰(MFU)淘汰使用次數(shù)最多的。依據(jù):使用多的可能已經(jīng)用完了。Suffer:程序有些成分是在整個(gè)程序運(yùn)行中都使用的。整理ppt5.最不經(jīng)常使用的先淘汰(LFU)整理ppt857.二次機(jī)會(huì)(secondchance)淘汰裝入最久且最近未被訪問(wèn)的頁(yè)面。實(shí)現(xiàn)時(shí)：采用拉鏈數(shù)據(jù)結(jié)構(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/1整理ppt7.二次機(jī)會(huì)(secondchance)淘汰裝入最久且最868.時(shí)鐘算法(clockalgorithm)將頁(yè)面組織成環(huán)形，有一個(gè)指針指向當(dāng)前位置。每次需要淘汰頁(yè)面時(shí)，從指針?biāo)傅捻?yè)面開(kāi)始檢查。如果當(dāng)前頁(yè)面的訪問(wèn)位為0，即從上次檢測(cè)到目前，該頁(yè)沒(méi)有訪問(wèn)過(guò)，則將該頁(yè)替換。如果當(dāng)前頁(yè)面的訪問(wèn)位為1，則將其清0，并順時(shí)針移動(dòng)指針到下一個(gè)位置。重復(fù)上述步驟直至找到一個(gè)訪問(wèn)位為0的頁(yè)面。可以看出，時(shí)鐘算法與二次機(jī)會(huì)算法的淘汰效果是基本相同的，差別在于二者所采用的數(shù)據(jù)結(jié)構(gòu)不同，二次機(jī)會(huì)使用的是鏈表，需要額外存儲(chǔ)空間，且摘鏈入鏈速度很慢。而時(shí)鐘算法可直接利用頁(yè)表中的引用位，外加一個(gè)指針，速度快且節(jié)省空間。整理ppt8.時(shí)鐘算法(clockalgorithm)將頁(yè)面組織成87頁(yè)6/r=1頁(yè)3/r=1頁(yè)4/r=0頁(yè)8/r=0頁(yè)10/r=1頁(yè)9/r=0頁(yè)0/r=0頁(yè)1/r=1框12框23框51框6框81框96框60框5訪問(wèn)第18頁(yè)時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=1頁(yè)4/r=0頁(yè)8/r=0頁(yè)10/r=88頁(yè)6/r=0頁(yè)3/r=1頁(yè)4/r=0頁(yè)8/r=0頁(yè)10/r=1頁(yè)9/r=0頁(yè)0/r=0頁(yè)1/r=1框12框23框51框6框81框96框60框5訪問(wèn)第18頁(yè)時(shí)鐘算法整理ppt頁(yè)6/r=0頁(yè)3/r=1頁(yè)4/r=0頁(yè)8/r=0頁(yè)10/r=89頁(yè)6/r=1頁(yè)3/r=0頁(yè)4/r=0頁(yè)8/r=0頁(yè)10/r=1頁(yè)9/r=0頁(yè)0/r=0頁(yè)1/r=1框12框23框51框6框81框96框60框5訪問(wèn)第18頁(yè)時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=0頁(yè)4/r=0頁(yè)8/r=0頁(yè)10/r=90頁(yè)6/r=0頁(yè)3/r=0頁(yè)18/r=1頁(yè)8/r=0頁(yè)10/r=1頁(yè)9/r=0頁(yè)0/r=0頁(yè)1/r=1框12框23框51框6框81框96框60框5替換第4頁(yè)時(shí)鐘算法整理ppt頁(yè)6/r=0頁(yè)3/r=0頁(yè)18/r=1頁(yè)8/r=0頁(yè)10/r91改進(jìn)的時(shí)鐘算法考慮修改標(biāo)志mr=0,m=0：最佳淘汰頁(yè)面r=0,m=1：淘汰前回寫(xiě)r=1,m=0：不淘汰r=1,m=1：不淘汰整理ppt改進(jìn)的時(shí)鐘算法考慮修改標(biāo)志m整理ppt92改進(jìn)的時(shí)鐘算法步驟1：由指針當(dāng)前位置開(kāi)始掃描，選擇最佳淘汰頁(yè)面，不改變引用位，將第一個(gè)遇到的r=0且m=0的頁(yè)面作為淘汰頁(yè)面；步驟2：如步驟1失敗，再次從原位置開(kāi)始，找r=0且m=1的頁(yè)面，將第一個(gè)滿足上述要求的頁(yè)面作為淘汰頁(yè)面，同時(shí)將掃描過(guò)頁(yè)面的r位清0；步驟3：若步驟2失敗，指針再次回到原位置，重新執(zhí)行步驟1。若還失敗再次執(zhí)行步驟2，此時(shí)定能找到。整理ppt改進(jìn)的時(shí)鐘算法步驟1：整理ppt93頁(yè)6/r=1m=1頁(yè)3/r=1m=1頁(yè)18/r=1m=0頁(yè)8/r=1m=0頁(yè)10/r=1m=0頁(yè)9/r=0m=1頁(yè)0/r=0m=1頁(yè)1/r=1m=0框12框23框51框6框81框96框60框5訪問(wèn)第15頁(yè)改進(jìn)的時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=1頁(yè)18/r=1頁(yè)8/r=1頁(yè)10/r94頁(yè)6/r=1m=1頁(yè)3/r=1m=1頁(yè)18/r=1m=0頁(yè)8/r=1m=0頁(yè)10/r=1m=0頁(yè)9/r=0m=1頁(yè)0/r=0m=1頁(yè)1/r=1m=0框12框23框51框6框81框96框60框5訪問(wèn)第15頁(yè)改進(jìn)的時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=1頁(yè)18/r=1頁(yè)8/r=1頁(yè)10/r95頁(yè)6/r=1m=1頁(yè)3/r=1m=1頁(yè)18/r=1m=0頁(yè)8/r=0m=0頁(yè)10/r=1m=0頁(yè)9/r=0m=1頁(yè)0/r=0m=1頁(yè)1/r=1m=0框12框23框51框6框81框96框60框5訪問(wèn)第15頁(yè)改進(jìn)的時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=1頁(yè)18/r=1頁(yè)8/r=0頁(yè)10/r96頁(yè)6/r=1m=1頁(yè)3/r=1m=1頁(yè)18/r=1m=0頁(yè)8/r=0m=0頁(yè)10/r=0m=0頁(yè)9/r=0m=1頁(yè)0/r=0m=1頁(yè)1/r=1m=0框12框23框51框6框81框96框60框5訪問(wèn)第15頁(yè)時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=1頁(yè)18/r=1頁(yè)8/r=0頁(yè)10/r97頁(yè)6/r=1m=1頁(yè)3/r=1m=1頁(yè)18/r=1m=0頁(yè)8/r=0m=0頁(yè)10/r=0m=0頁(yè)15/r=1m=0頁(yè)0/r=0m=1頁(yè)1/r=1m=0框12框23框51框6框81框96框60框5時(shí)鐘算法整理ppt頁(yè)6/r=1頁(yè)3/r=1頁(yè)18/r=1頁(yè)8/r=0頁(yè)10/r982010年考研試題某虛擬頁(yè)式系統(tǒng)，進(jìn)程空間和內(nèi)存空間都是64k，頁(yè)長(zhǎng)1K，某進(jìn)程6個(gè)頁(yè)，內(nèi)存分配4個(gè)頁(yè)框，采用局部置換，280時(shí)刻頁(yè)表和Clock數(shù)據(jù)結(jié)構(gòu)如下：邏輯頁(yè)號(hào)頁(yè)框號(hào)裝入時(shí)間訪問(wèn)標(biāo)志0511011---2121601

3823014---538010頁(yè)2頁(yè)3頁(yè)5頁(yè)框5框12框8框3(順時(shí)針)整理ppt2010年考研試題某虛擬頁(yè)式系統(tǒng)，進(jìn)程空間和內(nèi)存空間都是64992010年考研試題(1)280時(shí)刻訪問(wèn)13B7H，邏輯頁(yè)號(hào)是多少？(2)采用FIFO置換算法，物理頁(yè)框號(hào)是多少？物理地址是多少？(3)采用CLOCK置換算法，頁(yè)框號(hào)是多少？物理地址是多少？整理ppt2010年考研試題(1)280時(shí)刻訪問(wèn)13B7H，邏輯頁(yè)號(hào)是1002010年考研試題（1）邏輯地址13B7H化為二進(jìn)制數(shù)為0001001110110111，其中后10位為頁(yè)內(nèi)地址，前6位為邏輯頁(yè)號(hào)，即邏輯頁(yè)號(hào)為4。（2）4號(hào)頁(yè)不在內(nèi)存，發(fā)生缺頁(yè)中斷，按FIFO置換算法，應(yīng)置換第5頁(yè)，所得頁(yè)框號(hào)3，形成物理地址0000111110110111，劃成16進(jìn)制為0FB7H。（3）采用CLOCK置換算法，淘汰第0頁(yè)，得頁(yè)框5，形成物理地址為0001011110110111，劃成16進(jìn)制為17B7H。整理ppt2010年考研試題（1）邏輯地址13B7H化為二進(jìn)制數(shù)為0010顛簸(thrashing)

頁(yè)面在內(nèi)存與外存之間頻繁換入換出。原因：(1)分給進(jìn)程物理頁(yè)架過(guò)少；(2)淘汰算法不合理。處理：(1)增加分給進(jìn)程物理頁(yè)架數(shù)；(2)改進(jìn)淘汰算法。思考題：在某些虛擬頁(yè)式存儲(chǔ)管理系統(tǒng)中，內(nèi)存中總保持一個(gè)空閑的物理頁(yè)架，這樣做有什么好處？整理ppt顛簸(thrashing)思考題：整理ppt10工作集模型(workingsetmodel)

工作集(workingset):進(jìn)程在一段時(shí)間內(nèi)所訪問(wèn)頁(yè)面的集合。

WS(t,)={5,7,1,6,2}…2615777751622123…(pagereference)t：稱為窗口尺寸(windowsize)。Denning認(rèn)為：為使程序有效運(yùn)行，工作集應(yīng)能放入內(nèi)存。T整理ppt工作集模型(workingsetmode103WS(t1,)={5,7,1,6,2}…2615777751622123444343444134...WS(t2,)={2,3,4}t1t2工作集與時(shí)間有關(guān)：工作集與窗口尺寸有關(guān)：程序大小WS整理pptWS(t1,)={5,7,1,6,2}…26157104窗口尺寸確定：過(guò)?。夯顒?dòng)頁(yè)面不能全部裝入，頁(yè)故障率高；過(guò)大：內(nèi)存浪費(fèi)。Madnick,Donovan建議：＝1萬(wàn)次訪內(nèi)。實(shí)現(xiàn)：頁(yè)表中增加訪問(wèn)位：

…訪問(wèn)位頁(yè)表：開(kāi)始時(shí)，全部清0,訪問(wèn)：置1,結(jié)束時(shí)(新開(kāi)始時(shí))訪問(wèn)標(biāo)志為1的，為該期間工作集，τn+1=αwn+(1-α)τn整理ppt窗口尺寸確定：…訪問(wèn)位頁(yè)10頁(yè)故障率反饋模型PFFB(PageFaultFeedBack)頁(yè)故障率高(達(dá)到某上界閾值)：內(nèi)存頁(yè)面少，增加。頁(yè)故障率低(達(dá)到某下界閾值)：內(nèi)存頁(yè)面多，減少。整理ppt頁(yè)故障率反饋模型整理ppt1066.5.2虛擬段式存儲(chǔ)系統(tǒng)進(jìn)程運(yùn)行前，全部裝入外存，部分裝入內(nèi)存，訪問(wèn)段不再內(nèi)存時(shí)，發(fā)生缺段中斷。整理ppt6.5.2虛擬段式存儲(chǔ)系統(tǒng)進(jìn)程運(yùn)行前，全部裝入外存，部分裝1076.5.2虛擬段式存儲(chǔ)系統(tǒng)(Cont.)虛擬段式存儲(chǔ)管理地址映射指令確定邏輯地址(s,d)由s查快表得到b’和l’查到b’+d得到物理地址0≤s≤l-1越界中斷由b、s查找段表該段在內(nèi)存缺段中斷保存現(xiàn)場(chǎng)內(nèi)存可滿足選一段淘汰該段修改過(guò)寫(xiě)回外存讀入該段修改段表和快表恢復(fù)現(xiàn)場(chǎng)FFFTTT(s,b’,l’)快表如快表滿，淘汰一表項(xiàng)硬件完成軟件完成T0≤d≤l’-1T越界中斷F0≤d≤l’-1越界中斷b’+d得物理地址找到該段在外存的位置緊湊夠緊湊TTF修改段表整理ppt6.5.2虛擬段式存儲(chǔ)系統(tǒng)(Cont.)虛擬段式存儲(chǔ)管理地108...

...

…

...