操作系統(tǒng)存儲管理綜合試題

1、存儲管理綜合題1 試述缺頁中斷與一般中斷的主要區(qū)別。解：缺頁中斷作為中斷，同樣需要經(jīng)歷保護 CPU現(xiàn)場、分析中斷原因、轉(zhuǎn)缺 頁中斷處理程序進行處理、恢復(fù) CPU!場等步驟。但缺頁中斷又是一種特殊的中 斷，它與一般中斷的主要區(qū)別是：(1) 在指令執(zhí)行期間產(chǎn)生和處理中斷信號。通常，CPU都是在一條指令執(zhí) 行完后去檢查是否有中斷請求到達。若有便去響應(yīng)中斷；否則繼續(xù)執(zhí)行下一條指 令。而缺頁中斷是在指令執(zhí)行期間，發(fā)現(xiàn)所要訪問的指令或數(shù)據(jù)不在內(nèi)存時產(chǎn)生和 處理的。(2) 一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。例如，對于一條讀取 數(shù)據(jù)的多字節(jié)指令，指令本身跨越兩個頁面，假定指令后一部分所在頁面和數(shù)據(jù)所

2、在頁面均不在內(nèi)存，則該指令的執(zhí)行至少產(chǎn)生兩次缺頁中斷。2. 已知頁面走向為1、2、1、3、1、2、4、2、1、3、4,且開始執(zhí)行時主 存中沒有頁面。若只給該作業(yè)分配 2個物理塊，當(dāng)采用FIFO頁面淘汰算法時缺頁 率為多少？假定現(xiàn)有一種淘汰算法，該算法淘汰頁面的策略為當(dāng)需要淘汰頁面時， 就把剛使用過的頁面作為淘汰對象，試問就相同的頁面走向，缺頁率又為多少？分析及相關(guān)知識在進行內(nèi)存訪問時，若所訪問的頁已在主存，則稱此次訪問成功；若所訪問的頁不在主存，則稱此次訪問失敗，并產(chǎn)生缺頁中斷。若 程序P在運行過程中訪問頁面的總次數(shù)為 S,其中產(chǎn)生缺頁中斷的訪問次數(shù)為 F,則 其缺頁率為：F/s.解：根據(jù)所給

3、頁面走向，采用 FIFO淘汰算法的頁面置換情況如下: 頁面走向1 2 1 3 1 2 4 2 1 3 4從上述頁面置換圖可以看出：頁面引用次數(shù)為11次，缺頁次數(shù)為9次，所以缺頁率為9/11。若采用后一種頁面淘汰策略，其頁面置換情況如下:頁面走向1 2 1 3 1 2 4 2 1 3 4物理塊1 1 1 3 1 1 1 3 4物理塊2 2 2 2 4 2 2 2缺頁缺缺缺缺缺缺缺缺9某操作系統(tǒng)采用可孌分區(qū)分配存儲管理方法，用戶區(qū)為512K且始址為0,用空閑分區(qū)管理空閑分區(qū)。若分配采用分配空閑區(qū)低地址部分的方案，且初始 時用戶區(qū)的512K空間空閑，對下述申請序列：申請300K,申請100K,釋放3

4、00K,申請150K,申請30K,申請40K,申請 60K,釋放 30K回答下列問題：（1）采用首次適應(yīng)算法，空閑分區(qū)中有哪些空塊（給出始址，大小）？（2）采用最佳適應(yīng)算法，空閑分區(qū)中有哪些空塊（給出始址，大小）？ （3）臺再申請100K,針對（1）和（2）各有什么結(jié)果?初始無(0，512K)申請 300K(0，300K)(300K，212K)申請 100K(0，300K)(400K，112K)(300K，100K)釋放 300K(300K，100K)(0，300K)(400K，112K)申請 150K(0，150K)(150K，150K)(300K，100K)(400K，112K)申請 30

5、K(0，150K)(180K，120K)(150K，30K)(400K，112K)申請 40K(0，150K)(220K，80K)操作：已分配空間空閑塊150K，30K)400K，112K)170K，40K)（300K，100）申請 60K（ 0，150K）（150K，30K）（180K，40K）（220K，60K）（300K，100K）釋放 30K150K）（180K，40K）（300K，100K） 采用最佳適應(yīng)算法時的操作流程： 操作： 已分配空間 初始 無512K）申請 300K0, 300K)280K，20K)(400K,112K)150K，30K)( 280K, 20K)( 400K

6、, 112K)空閑塊( 0,300K,212K)申請 100K0，300K）400K，112K）（300K，100K）釋放 300K（300K，100K）（400K，112K）申請 150K （0，150K）（300K，100K）申請 30K（0，150K）（300K，100K）（400K，30K）申請 40K（0，150K）（300K，100K）（400K，30K）（430K，40）申請 60K（ 0，150K）（0，300K）150K，150K）（400K，112K）150K，150K）（430K，82K）150K，150K）（470K，42K）210K，90K）(470K, 42K)(2

7、10K, 90K)(400K, 30K)(470K, 42K)(150K 60K)(300K, 100K)(400K, 30K)(430K, 40K)釋放30K150K)(150K 60K)(300K, 100K(430K, 40K)解：（1）采用首次適應(yīng)算法，在完成了題目所給的毓申請及釋放內(nèi)存操作 后，內(nèi)存分配情況如圖5，11,空閑分區(qū)表如下所示。0150K180K220K280K300K400K 512K-1150K40K60K100K圖5.11采用首次適應(yīng)算法的內(nèi)存分配情況分區(qū)大起始地址1 30K150K20K280K112400K(2)采用最佳適應(yīng)算法，完成了題目所給的系列申請及釋放內(nèi)

8、存操作后，內(nèi)存分配情況如圖5.12所示(用陰影表示空閑空間)，空閑分區(qū)表如下：0150K150K60K210K300K400K430K470K512K-1100K40K圖5.12采用最佳適應(yīng)算法的內(nèi)存分配情況分區(qū)小大起始地址30K400K142K470K290K210K(3)如再申請空間100K空間，由上述結(jié)果可知，采用首次適應(yīng)算法后剩下的 空閑分區(qū)能滿足這一申請要求；而采用最佳適應(yīng)算法后剩下的空閑分區(qū)不能滿足這 一申請要求。10.有一頁式系統(tǒng)，其頁表存放在主存中。(1) 如果對主存的一次存取需要1.5微秒，試問實現(xiàn)一次頁面訪問的存取 時間是多少？(2) 如果系統(tǒng)加有快表，平均命中率為 85%

9、當(dāng)頁表項在快表中時，其查 找時間忽略為0，試問此時的存取時間為多少？解：若頁表存放在主存中，則要實現(xiàn)一次頁面訪問需要兩次訪問主存，一次 是訪問頁表，確定所存取頁面的物理地址，第二次才根據(jù)該地址存取頁面數(shù)據(jù)。(1) 由于頁表存放在主存，因此 CPU必須兩次訪問主存才能獲得所需數(shù) 據(jù)，所以實現(xiàn)一次頁面訪問的存取時間是：1.5 X 2=3 微秒 在系統(tǒng)增加了快表后，在快表中找到頁表項的概率為85%所以實現(xiàn)一次頁面的訪問的存取時間是0.85 X 1.5+(1 - 0.85) X 2X 1.5=1.725 微秒11 若在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如下所示。已知頁面大小為1024字節(jié)，試將邏輯地址

10、1011，2148, 3000, 4000, 5012轉(zhuǎn)化為相應(yīng)的物理地 址。頁號塊號解:面大小為本題中，為了描述方便，設(shè)頁號為P,頁內(nèi)位移為L，貝W邏輯地址為A,p=int(A/L)w=A mod L對于邏輯地址 1011p=int(1011/1024)=0w=1011 mod 1024=1011查頁表第 0 頁在第二塊，所以物理地址為對于邏輯地址 2148p=int(2148/1024)=2w=2148 mod 1024=100查頁表第 2 頁在第 1 塊，所以物理地址為對于邏輯地址 3000p=int(3000/1024)=2w=3000 mod 1024=928查頁表第 2 頁在第 1

11、 塊, 所以物理地址為對于邏輯地址 4000p=int(4000/1024)=33059。1124。1796。w=4000mod 1024=928查頁表第3頁在第6塊,所以物理地址為7072 對于邏輯地址5012p=i nt(5012/1024)=4w=5012mod1024=916 因頁號超過頁表長度，該邏輯地址非法。12.在一個請求分頁存儲管理系統(tǒng)中，一個作業(yè)的頁面走向為4，3，2，1,4,3,5,4,3,2，1,5,當(dāng)分配給該作業(yè)的物理塊數(shù)分別為3, 4時，試計算采用下述頁面淘汰算法時的缺頁率(假設(shè)開始執(zhí)行時主存中沒有頁面)，并比較所得 結(jié)果。(1) 最佳置換淘汰算法(2) 先進先出淘汰

12、算法(3) 最近最久未使用淘汰算法解：(1)根據(jù)所給頁面走向，使用最佳頁面淘汰 算法時，頁面置換情況如 下：塊1444442 2塊233333 1塊32 1555缺頁缺缺 缺缺缺缺缺缺頁率為：7/12走向432143543215缺頁缺頁率為:1444446/12由上述結(jié)果可以看出，增加分配 給作業(yè) 的內(nèi)存塊數(shù)可以降低缺頁率(2)根據(jù)所給頁面走向，使用最佳頁面淘汰 算法時，頁面置換情況如下:走向432143543215缺頁塊1塊2塊3缺缺頁率為:444111555333444322223321缺 缺缺缺缺 缺9/12塊 2333塊322塊4134444522333311

13、12 2 2缺頁缺頁率為：10/12由上述結(jié)果可以看出，對先進先出算法而言，增加分配給作業(yè)的內(nèi)存塊數(shù)反 而使缺頁率上升，這種異?，F(xiàn)象稱為Belady現(xiàn)象。(3) 根據(jù)所給頁面走向，使用最佳頁面淘汰算法時，頁面置換情況如下:走向432143543215塊144411152 22塊23244441 1塊323233335缺頁 缺 缺 缺缺缺缺 缺缺頁率為：10/12走向 4 3 2 1 4 3 5 4 3 2 1 5塊 1 4 4 4 4 4 4 4 5塊 2 3 3 3 3 3 3 3塊 3 2 2 5 5 1 1塊 4 1 1 2 2 2缺頁缺缺缺缺缺缺缺缺缺頁率為：8/12由上述結(jié)果可以看出

14、，增加分配給作業(yè)的內(nèi)存塊數(shù)可以降低缺頁率.13. 在一分頁存儲管理系統(tǒng)中,邏輯地址長度為16位,頁面大小為4096字節(jié), 現(xiàn)有一邏輯地址為2F6AH且第0, 1,2 頁依次存放在物理塊5, 10 ,11中，問相應(yīng) 的物理地址為多少？解:由題目所給給條件可知，本頁式系統(tǒng)的邏輯地址結(jié)構(gòu)為：邏輯地址2F6AH的二進制表示如下：由此可知邏輯地址2F6AH的頁號為2,該頁存放在第11號物理塊中,用十六進 制表示志號為B,所以物理地址為BF6AH.14. 在虛擬頁式存儲管理中，為解決抖動問題，可采用工作集模型以決定因素 分給進程的物理塊數(shù)，有如下頁面訪問序列：窗口尺寸 =9, 試求 t1,t2 時刻的工作

15、集 .解: 一個進程在時間 t 的工作集可形成化地定義為 :w(t,h)= 在時間 t-h 到 t 之間所訪問的一串頁面 其中 ,h 為工作集窗口尺寸 .由題目所給條件可知 ,t1 時刻的工作集為 :1,2,3,6,7,8,9t2 時刻的工作集為 :3,415. ( 北京大學(xué) 1993年試題)有一距陣 :VAR A:ARRAY1.100,1 .100 OF integer;按先行后列次序存儲 .200在一虛存系統(tǒng)中，采用LRU淘汰算法,一個進程有3頁內(nèi)存空間，每頁可以存放個整數(shù).其中第一頁存放程序 ,且假定程序已在內(nèi)存 .程序 A:FOR I:=1 TO 100 DOFORj:=1 TO 10

16、0 DOAi,j:0;程序 B:FOR j:=1 TO 100 DOFOR I:=1 TO 100 DOAi,j:=0;分別就程序 A 和 B 的執(zhí)行過程計算缺頁次數(shù) . 分析及相關(guān)知識 由于每一進程在內(nèi)存中有 3 個頁面且其中的確良頁用于存 放程序,所以可用作存放數(shù)據(jù)的頁面只有 2 個.由題目中的定義可知,數(shù)組A中有10000個整數(shù),每頁存放200個整數(shù),數(shù)組占 用空間50頁.假設(shè)數(shù)據(jù)從該作業(yè)的第 M頁開始存放，則數(shù)組分布在第M頁到第M+49 頁中 . 因數(shù)據(jù)是按先行后列次序存儲 , 它的存儲順序為 :A99,1,A99,2,A99,100,A100,1,A100,2,A100,100A1,

17、1,A1,2,A1,100,A2,1,A2,2,A2,100第M頁A3,1,A3,2,A3,100,A4,1,A4,2,A4,100第M+1頁第M+49頁解 : 對于程序 A:由于程序A對矩陣A的訪問是按行進行，即按照存儲順序進行因此每次缺頁 中斷調(diào)進一頁后 ,位于該頁內(nèi)的數(shù)組元素全部賦予 0值,然后再調(diào)入下一頁 ,所以涉 及的頁面走向為M,M+1,M+49，故缺頁次數(shù)為50次.對于程序B：由于程序B對矩陣A的訪問是按列進行,而矩陣A每行有100個數(shù)據(jù),每頁可 以存放 200個數(shù)據(jù),因此每頁中有 2個數(shù)據(jù)屬于同一列 ,每次缺頁中斷調(diào)進一頁時 , 只有其中的2個數(shù)據(jù)被賦予0值,即程序B對矩陣A每

18、兩次訪問會遇到一次缺頁所 以波及的頁面走向為 :M, M+1,.,M+49處理 1 列M, M+1,.,M+49處理 2 列M, M+1,.,M+49處理 100 列故缺頁次數(shù)為 :100 x 50=5000 次16（中國科學(xué)院軟件研究所 1999 年試題）在一個請求分頁的系統(tǒng)中，假 定系統(tǒng)分配給一個作業(yè)的物理塊數(shù)字為 3，并且此作業(yè)的頁面走向為 2、3、2、1、5、2、4、5、3、2、5、2。試用FIFO和LUO兩種算法分別計算出程序訪問過程中所發(fā)生的缺頁。解：在本題中，分配給作業(yè)的物理塊數(shù)為 3（1）根據(jù)所給頁面走向，使用 FIFO算法時，頁面置換情況如下:缺頁次數(shù)為：9（2）根據(jù)所給頁面走向，使用LRU算法時，頁面置換情況如下:缺頁次數(shù)為：717.（南開大