4.8.4請(qǐng)求分頁系統(tǒng)的性能分析（補(bǔ)充）,1.缺頁率對(duì)有效訪問時(shí)間的影響在請(qǐng)求分頁系統(tǒng)中，假設(shè)存儲(chǔ)器的訪問時(shí)間ma為100ns（一般為10ns幾百ns），缺頁率為p，缺頁中斷時(shí)間為25ms，則：ma=100ns=0.1s,缺頁中斷時(shí)間25000s有效訪問時(shí)間=(1-p)0.1+p（25000+0.1)=0.1+25000p可見,有效訪問時(shí)間與缺頁率成正比。,如果缺頁率為0.1%，則有效訪問時(shí)間約為25s，與直接訪問存儲(chǔ)器的有效訪問時(shí)間(0.1s)相比，程序的性能大大降低。如果希望在缺頁時(shí)，僅使有效訪問時(shí)間延長(zhǎng)不超過10%，即:25000*P+0.10.1(1+0.1)因此,P4*10-7即:要求在2.5*106次的訪問中至多發(fā)生一次缺頁，即請(qǐng)求分頁方式應(yīng)保持非常低的缺頁率,才不至于影響程序執(zhí)行速度。此外，提高磁盤I/O的速度，對(duì)改善請(qǐng)求分頁系統(tǒng)的性能至關(guān)重要(為此，應(yīng)選用高速磁盤和高速磁盤接口),練習(xí)：,現(xiàn)有一請(qǐng)求調(diào)頁系統(tǒng)，頁表保存在寄存器中。若有一個(gè)被替換的頁未被修改過，則處理一個(gè)缺頁中斷需要8ms；若被替換的頁被修改過，則處理一個(gè)缺頁中斷需要20ms。內(nèi)存存取時(shí)間為1s,訪問頁表的時(shí)間可以忽略不計(jì)。假設(shè)70%被替換的頁被修改過，為保證有效存取時(shí)間不超過2s，則可接受的最大缺頁率是多少？,p*(0.7*20+0.3*8+0.001)+(1-p)*0.001=0.002,16.4p+0.001=0.00216.4p=0.001P=1/164000.00006,駐留集指虛擬頁式管理中給進(jìn)程分配的物理頁面數(shù)目。,駐留集與缺頁率的關(guān)系：每個(gè)進(jìn)程的駐留集越小，則同時(shí)駐留內(nèi)存的進(jìn)程就越多，可以提高并行度和處理器利用率；另一方面，進(jìn)程的缺頁率上升，使調(diào)頁的開銷增大。進(jìn)程的駐留集達(dá)到某個(gè)數(shù)目之后，再給它分配更多頁面，缺頁率不再明顯下降。該數(shù)目是“缺頁率駐留集大小曲線上的拐點(diǎn)。,2.駐留集(residentset),物理塊數(shù)(駐留集),缺頁率,拐點(diǎn),3.工作集模型（Workingset1968年由Denning提出）,基本思想：根據(jù)程序的局部性原理，一般情況下進(jìn)程在一段時(shí)間內(nèi)總是集中訪問一些頁面，這些頁面稱為活躍頁面，如果分配給一個(gè)進(jìn)程的物理塊數(shù)太少了，使該進(jìn)程所需的活躍頁面不能全部裝入內(nèi)存，則進(jìn)程在運(yùn)行過程中則不斷發(fā)生中斷。如果能為進(jìn)程提供與活躍頁面數(shù)相等的物理塊數(shù)(駐留集)，則可減少缺頁中斷次數(shù)。,工作集是在某段時(shí)間間隔里，進(jìn)程實(shí)際要訪問頁面的集合，可用一個(gè)二元函數(shù)W(t,)表示。,其中,t指某一特定的時(shí)刻,是對(duì)于給定訪問序列所選取的定長(zhǎng)區(qū)間，也稱為工作集窗口.,進(jìn)程開始執(zhí)行后，隨著訪問新頁面逐步建立較穩(wěn)定的工作集。當(dāng)內(nèi)存訪問的局部性區(qū)域的位置大致穩(wěn)定時(shí)，工作集大小也大致穩(wěn)定；局部性區(qū)域的位置改變時(shí)，工作集快速擴(kuò)張和收縮過渡到下一個(gè)穩(wěn)定值。,工作集大小的變化,引入工作集的目的是依據(jù)進(jìn)程在過去的一段時(shí)間內(nèi)訪問的頁面來調(diào)整駐留集大小。即：駐留集大小的動(dòng)態(tài)調(diào)整策略：,記錄一個(gè)進(jìn)程的工作集變化；定期從駐留集中刪除不在工作集中的頁面；總是讓駐留集包含工作集；,4.抖動(dòng)問題(顛簸Thrashing),Ifaprocessdoesnothave“enough”pages,thePagefaultrateisveryhigh.Thisleadsto:lowCPUutilizationoperatingsystemthinksthatitneedstoincreasethedegreeofmultiprogramminganotherprocessaddedtothesystemThrashingaprocessisbusyswappingpagesinandout,Thrashing,可見，不適當(dāng)?shù)靥岣叨嗟莱绦蚨?不僅不會(huì)提高系統(tǒng)吞吐量，反而會(huì)使之下降。OS要選擇一個(gè)適當(dāng)?shù)倪M(jìn)程數(shù)目，以在并發(fā)水平和缺頁率之間達(dá)到一個(gè)平衡。,5、影響缺頁次數(shù)的因素,分配給進(jìn)程的物理塊數(shù)一個(gè)程序運(yùn)行時(shí)遇到缺頁中斷的次數(shù)，是和分配給該道程序的物理塊數(shù)成反比的，但當(dāng)主存容量達(dá)到某個(gè)值時(shí)，缺頁次數(shù)減少不再明顯。多數(shù)程序都有一個(gè)確定值拐點(diǎn)(2)頁面本身的大小頁面大，頁表小，省空間且查找快；缺頁次數(shù)相對(duì)也少；一次換頁的時(shí)間長(zhǎng)，頁內(nèi)碎片空間浪費(fèi)的可能性較大。頁面小則相反.(3)頁面置換算法(頁面淘汰算法)選擇最合適的置換算法。(4)程序的編制方法盡可能使編出的程序具有高度的局部性，則執(zhí)行時(shí)可經(jīng)常集中在幾個(gè)頁面上進(jìn)行訪問，減少缺頁率.,程序的編制方法選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu),增強(qiáng)程序訪問的局部性,例：二維數(shù)組(512*512)清零問題：假設(shè)內(nèi)存分配2個(gè)物理塊，一個(gè)塊用來裝入程序和變量i、j;另一塊用來存放數(shù)組數(shù)據(jù)。初始時(shí)調(diào)第一頁進(jìn)入內(nèi)存,頁面大小為512個(gè)整數(shù)。,ex:數(shù)組在主存中存放順序與使用順序的一致性：,行優(yōu)先存放：法1發(fā)生512*512=262144次缺頁，法2只發(fā)生512次缺頁。,法1：intA512512;法2：intA512512for(j=0;j512;j+)for(i=0;i512;i+)for(i=0;i512;i+)for(j=0;j512;j+)Aij=0;Aij=0;,程序的編制方法加強(qiáng)編譯程序和裝入程序的效能：,編譯程序：能把程序代碼和程序的數(shù)據(jù)分離開來，減少常用的程序純代碼被換出的機(jī)會(huì)；裝入程序：應(yīng)將純代碼部分裝入同一頁或幾頁中，切不要把純代碼部分與非純代碼或數(shù)據(jù)部分放入同一頁中，以減少那些常用子程序所在的頁被換出的機(jī)會(huì)。,4.8.5請(qǐng)求分段存儲(chǔ)管理方式虛擬分段(virtualsegmentation),1)需要在進(jìn)程段表中添加若干項(xiàng)：存取方式：如讀R，寫W，執(zhí)行X訪問字段A：被訪問的頻繁程度存在位P(presentbit)，即狀態(tài)位：是否已經(jīng)調(diào)入內(nèi)存修改位(modifiedbit/dirtybit)：進(jìn)入內(nèi)存后，是否被修改過增補(bǔ)位（該段是否增長(zhǎng)過，在虛擬頁式中沒有該位）外存始址(本段在外存中的起始地址,起始盤塊號(hào)),硬件支持,在簡(jiǎn)單段式存儲(chǔ)管理的基礎(chǔ)上，增加請(qǐng)求調(diào)段和段置換功能。,2)缺段中斷：指令和操作數(shù)必定不會(huì)跨越在段邊界上，所以，頻繁缺段現(xiàn)象較少。但由于段長(zhǎng)不定，所以處理較缺頁復(fù)雜。,啟動(dòng)要處理指令,計(jì)算有效地址,訪問地址v=(s,p,d),S段表長(zhǎng)嗎？,段鏈接了嗎？,段在主存嗎？,P頁表長(zhǎng)嗎？,訪問類型合法嗎？,頁在主存嗎？,缺頁中斷處理,執(zhí)行下一條指令,訪問該地址完成指令,形成主存地址,出錯(cuò)處理,越界中斷處理,鏈接中斷處理,缺段中斷處理,允許動(dòng)態(tài)增長(zhǎng)嗎？,出錯(cuò)處理,N,N,N,N,N,N,N,4)請(qǐng)求段頁式地址變換機(jī)構(gòu),引入共享段表實(shí)現(xiàn)對(duì)共享段的共享：,共享段的分配與回收：,分段共享與保護(hù),分段共享,存儲(chǔ)保護(hù)的目的：1)保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯（有意或無意的）2)不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù)（系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）,在多道程序設(shè)計(jì)的環(huán)境下，系統(tǒng)中有系統(tǒng)程序和多個(gè)用戶程序同時(shí)存在，如何保證用戶程序不破壞系統(tǒng)程序，用戶程序之間不相互干擾？這就是存儲(chǔ)保護(hù)所要解決的問題。,分段保護(hù),越界保護(hù)：邏輯地址段號(hào)與段表長(zhǎng)度比較段內(nèi)地址與段長(zhǎng)比較上下界保護(hù)存取控制檢查：使用“存取控制”字段規(guī)定對(duì)段的訪問方式只讀、只執(zhí)行、讀/寫。環(huán)保護(hù)：處理器狀態(tài)分為多個(gè)環(huán)(ring)，分別具有不同的存儲(chǔ)訪問特權(quán)級(jí)別(privilege)，通常是級(jí)別高的在內(nèi)環(huán)，編號(hào)小（如0環(huán)級(jí)別最高）；在環(huán)系統(tǒng)中,程序的訪問和調(diào)用遵循如下規(guī)則:可訪問同環(huán)或更低級(jí)別環(huán)的數(shù)據(jù)；可調(diào)用同環(huán)或更高級(jí)別環(huán)的服務(wù)。,分段保護(hù)的幾種措施,存儲(chǔ)保護(hù)通常通過存儲(chǔ)保護(hù)檢查來實(shí)現(xiàn)，是針對(duì)每個(gè)存儲(chǔ)訪問操作進(jìn)行的，必須由相應(yīng)的處理器硬件機(jī)構(gòu)支持。,上下界保護(hù),下界寄存器存放程序段裝入內(nèi)存后的開始地址（首址）上界寄存器存放程序段裝入內(nèi)存后的末地址判別式：下界寄存器物理地址上界寄存器,例：有一程序裝入內(nèi)存的首地址是500，末地址是1500，訪問內(nèi)存的邏輯地址是500、345、1000。下界寄存器：500上界寄存器：1500邏輯地址裝入內(nèi)存的首地物理地址1、5005001000500100015002、34550084550084515003、1000500150050015001500,對(duì)同環(huán)或更低級(jí)環(huán)數(shù)據(jù)的訪問,對(duì)同環(huán)或更高級(jí)別環(huán)服務(wù)的調(diào)用,練習(xí)：,一個(gè)程序的段表如下表，其中存在位為1表示段在內(nèi)存，存取控制字段中W表示可寫，R表示可讀，E表示可執(zhí)行。對(duì)下面的5條指令，在執(zhí)行時(shí)會(huì)產(chǎn)生什么樣的結(jié)果？,STORER1,0,70STORER1,1,20LOADR1,3,20LOADR1,3,100JMP2,100,缺段中斷只讀，保護(hù)性中斷合法，形成物理地址8020，將該單元內(nèi)容讀入寄存器R1中越界中斷合法，跳到3100處繼續(xù)執(zhí)行,STORER1,0,70STORER1,1,20LOADR1,3,20LOADR1,3,100JMP2,100,答：,第三章存儲(chǔ)管理,存儲(chǔ)分配存儲(chǔ)擴(kuò)充存儲(chǔ)保護(hù),連續(xù)分配存儲(chǔ)管理方式：?jiǎn)我贿B續(xù)、固定分區(qū)，動(dòng)態(tài)分區(qū)、伙伴