CH4 應用題參考答案1 在一個請求分頁虛擬存儲管理系統(tǒng)中，一個程序運行的頁面走向是：1 、2 、3 、4 、2 、1 、5 、6 、2 、1 、2 、3 、7 、6 、3 、2 、1 、2 、3 、6 。分別用FIFO 、OPT 和LRU 算法，對分配給程序3 個頁框、4 個頁框、5 個頁框和6 個頁框的情況下，分別求出缺頁中斷次數(shù)和缺頁中斷率。答：頁框數(shù)FIFOLRUOPT3456161412915108711877只要把表中缺頁中斷次數(shù)除以20，便得到缺頁中斷率。2 在一個請求分頁虛擬存儲管理系統(tǒng)中，一個作業(yè)共有5 頁，執(zhí)行時其訪問頁面次序為：( 1 ) 1 、4 、3 、1 、2 、5 、1 、4 、2 、1 、4 、5( 2 ) 3 、2 、1 、4 、4 、5 、5 、3 、4、3、2、1、5若分配給該作業(yè)三個頁框，分別采用FIFO和LRU 面替換算法，求出各自的缺頁中斷次數(shù)和缺頁中斷率。答：( 1 ）采用FIFO 為9 次，9 / 12 = 75 。采用LRU 為8 次，8 / 12 = 67 。( 2 ）采用FIFO 和LRU 均為9 次，9 / 13 = 69 。3 一個頁式存儲管理系統(tǒng)使用FIFO 、OPT 和LRU 頁面替換算法，如果一個作業(yè)的頁面走向為：( l ) 2 、3 、2 、l 、5 、2 、4 、5 、3 、2 、5 、2 。( 2 ) 4 、3 、2 、l 、4 、3 、5 、4 、3 、2 、l 、5 。( 3 ) 1 、2 、3 、4 、1 、2 、5 、l 、2 、3 、4 、5 。當分配給該作業(yè)的物理塊數(shù)分別為3 和4 時，試計算訪問過程中發(fā)生的缺頁中斷次數(shù)和缺頁中斷率。答：( l ）作業(yè)的物理塊數(shù)為3 塊，使用FIFO 為9 次，9 / 12 = 75 。使用LRU 為7 次，7 / 12 = 58 。使用OPT 為6 次，6 / 12 = = 50 。 作業(yè)的物理塊數(shù)為4 塊，使用FIFO 為6 次，6 / 12 = 50 。使用LRU 為6 次，6 / 12 = 50 。使用OPT 為5 次，5 /12 = 42 。( 2 ）作業(yè)的物理塊數(shù)為3 塊，使用FIFO 為9 次，9 / 12 = 75 。使用LRU 為10 次，10 / 12 = 83 。使用OPT 為7 次，7/12 = 58 。 作業(yè)的物理塊數(shù)為4 塊，使用FIFO 為10 次，10 / 12 = 83 。 使用LRU 為8 次，8/1266。使用OPT為6次，6/1250%.其中，出現(xiàn)了Belady 現(xiàn)象，增加分給作業(yè)的內(nèi)存塊數(shù)，反使缺頁中斷率上升。4、在可變分區(qū)存儲管理下，按地址排列的內(nèi)存空閑區(qū)為：10K 、4K 、20K 、18K 、7K 、9K 、12K 和15K 。對于下列的連續(xù)存儲區(qū)的請求：( l ) 12K 、10K 、9K , ( 2 ) 12K 、10K 、15K 、18K 試問：使用首次適應算法、最佳適應算法、最差適應算法和下次適應算法，哪個空閑區(qū)被使用？答：( 1 ）空閑分區(qū)如圖所示。答分區(qū)號分區(qū)長1234567810K4K20K18K7K9K12K15K1）首次適應算法12KB 選中分區(qū)3 ，這時分區(qū)3 還剩8KB 。10KB 選中分區(qū)1 ，恰好分配故應刪去分區(qū)1 。9KB 選中分區(qū)4 ，這時分區(qū)4 還剩9KB 。2 ）最佳適應算法12KB 選中分區(qū)7 ，恰好分配故應刪去分區(qū)7 。1OKB 選中分區(qū)1 ，恰好分配故應刪去分區(qū)1 。9KB 選中分區(qū)6 ，恰好分配故應刪去分區(qū)6 。3 ）最差適應算法12KB 選中分區(qū)3 ，這時分區(qū)3 還剩8KB 。1OKB 選中分區(qū)4 ，這時分區(qū)4 還剩8KB 。9KB 選中分區(qū)8 ，這時分區(qū)8 還剩6KB 。4 ）下次適應算法12KB 選中分區(qū)3 ，這時分區(qū)3 還剩8KB 。10KB 選中分區(qū)4 ，這時分區(qū)4 還剩8KB 。9KB 選中分區(qū)6 ，恰好分配故應刪去分區(qū)6 。( 2 ）原始分區(qū)情況同上圖。1 ）首次適應算法12KB 選中分區(qū)3 ，這時分區(qū)3 還剩8KB 。10KB 選中分區(qū)1 ，恰好分配故應刪去分區(qū)1 。15KB 選中分區(qū)4 ，這時分區(qū)4 還剩3KB 。最后無法滿足18KB 的申請，應該等待。2 ）最佳適應算法12KB 選中分區(qū)7 ，恰好分配故應刪去分區(qū)7 。1OKB 選中分區(qū)1 ，恰好分配故應刪去分區(qū)1 。15KB 選中分區(qū)8 ，恰好分配故應刪去分區(qū)8 。18KB 選中分區(qū)4 ，恰好分配故應刪去分區(qū)4 。3 ）最差適應算法12KB 選中分區(qū)3 ，這時分區(qū)3 還剩8KB 。10KB 選中分區(qū)4 ，這時分區(qū)4 還剩8KB 。15KB 選中分區(qū)8 ，恰好分配故應刪去分區(qū)8 。最后無法滿足18KB 的申請，應該等待。4 ）下次適應算法12KB 選中分區(qū)3 ，這時分區(qū)3 還剩8KB 。1OKB 選中分區(qū)4 ，這時分區(qū)4 還剩8KB 。15KB 選中分區(qū)8 ，恰好分配故應刪去分區(qū)8 。最后無法滿足15KB 的申請，應該等待。5 給定內(nèi)存空閑分區(qū)，按地址從小到大為：100K 、500K 、200K 、300K 和600K ?，F(xiàn)有用戶進程依次分別為212K 、417K 、112K 和426K , ( l ）分別用first-fit 、best-fit 和worst-fit 算法將它們裝入到內(nèi)存的哪個分區(qū)？( 2 ）哪個算法能最有效利用內(nèi)存？答：按題意地址從小到大進行分區(qū)如圖所示。分區(qū)號分區(qū)長12345100KB500KB200KB300KB600KB( 1 ) 1）first-fit 212KB 選中分區(qū)2 ，這時分區(qū)2 還剩288KB 。417KB 選中分區(qū)5 ，這時分區(qū)5 還剩183KB 。112KB 選中分區(qū)2 ，這時分區(qū)2 還剩176KB 。426KB 無分區(qū)能滿足，應該等待。2 ) best-fit 212KB 選中分區(qū)4 ，這時分區(qū)4 還剩88KB 。417KB 選中分區(qū)2 ，這時分區(qū)2 還剩83KB 。112KB 選中分區(qū)3 ，這時分區(qū)3 還剩88KB 。426KB 選中分區(qū)5 ，這時分區(qū)5 還剩174KB 。3 ) worst-fit 212KB 選中分區(qū)5 ，這時分區(qū)5 還剩388KB 。417KB 選中分區(qū)2 , 這時分區(qū)2 還剩83KB 。112KB 選中分區(qū)5 ，這時分區(qū)5 還剩176KB 。426KB 無分區(qū)能滿足，應該等待。( 2 ）對于該作業(yè)序列，best-fit 算法能最有效利用內(nèi)存6、 一個32 位地址的計算機系統(tǒng)使用二級頁表，虛地址被分為9 位頂級頁表，11位二級頁表和偏移。試問：頁面長度是多少？虛地址空間共有多少個頁面？答：由于32-9 -11 12 ，所以，頁面大小為4KB ，頁面的個數(shù)為220個。7、 一進程以下列次序訪問5 個頁：A 、B 、C 、D 、A 、B 、E 、A 、B 、C 、D 、E ：假定使用FIFO 替換算法，在內(nèi)存有3 個和4 個空閑頁框的情況下，分別給出頁面替換次數(shù)。答：內(nèi)存有3 個和4 個空閑頁框的情況下，頁面替換次數(shù)為9 次和10 次。出現(xiàn)了Belady 即現(xiàn)象，增加分給作業(yè)的內(nèi)存塊數(shù)，反使缺頁中斷率上升。8、 某計算機有緩存、內(nèi)存、輔存來實現(xiàn)虛擬存儲器。如果數(shù)據(jù)在緩存中，訪問它需要Ans；如果在內(nèi)存但不在緩存，需要Bns 將其裝入緩存，然后才能訪問；如果不在內(nèi)存而在輔存，需要Cns 將其讀入內(nèi)存，然后，用Bns 再讀入緩存，然后才能訪問。假設緩存命中率為（n-1) / n ，內(nèi)存命中率為（m -1) / m ，則數(shù)據(jù)平均訪問時間是多少？答：數(shù)據(jù)在緩存中的比率為：( n - 1 ) / n 數(shù)據(jù)在內(nèi)存中的比率為：( 1 -（n - 1 ) / n )( m - 1 ) / m = ( m - 1 ）/nm 數(shù)據(jù)在輔存中的比率為：( 1 -（n 1 ) / n )( 1（m 1 ) / m ）1/nm 故數(shù)據(jù)平均訪問時間是( ( n- 1 ) / n ) A + ( ( 1 -（n - 1 ) / n ) ( m-1 ) / m ) ( A + B ) + ( ( 1-（n -1 ) / n ) ( 1-（m-1）/ m ) ) ( A + B + C ) = A + B / n + C / nm 9、某計算機有cache 、內(nèi)存、輔存來實現(xiàn)虛擬存儲器。如果數(shù)據(jù)在cache 中，訪問它需要20ns ；如果在內(nèi)存但不在cache ，需要60ns 將其裝入緩存，然后才能訪問；如果不在內(nèi)存而在輔存，需要12us將其讀入內(nèi)存，然后，用60ns 再讀入cache ，然后才能訪問。假設cache 命中率為0 .9 ，內(nèi)存命中率為0.6 ，則數(shù)據(jù)平均訪問時間是多少（ns ) ? 答：506ns 。10 有一個分頁系統(tǒng)，其頁表存放在主存里，( 1 ）如果對內(nèi)存的一次存取要1.2 微秒，試問實現(xiàn)一次頁面訪問的存取需花多少時間？( 2 ）若系統(tǒng)配置了聯(lián)想存儲器，命中率為80 % ，假定頁表表目在聯(lián)想存儲器的查找時間忽略不計，試問實現(xiàn)一次頁面訪問的存取時間是多少？答：(1) 2.4 微秒 （2 )0.8 1.2 + 0.2 2.4 = 0.76 + 0.45 = 1.24 微秒11 給定段表如下：段號段首址段長02196001230014290100313275804195296給定地址為段號和位移： 1 ) 0 , 430 、2 ) 3 , 400 、3 ) 1 , 1 、4 ) 2 , 500 、5 ) 4 , 42 ) ，試求出對應的內(nèi)存物理地址。答：1) 649 2) 1 727 3) 2301 4）越界 5) 1994 12、 某計算機系統(tǒng)提供24 位虛存空間，主存為2 18 B ，采用分頁式虛擬存儲管理，頁面尺寸為1KB 。假定用戶程序產(chǎn)生了虛擬地址11123456 （八進制），而該頁面分得塊號為100 ( 八進制），說明該系統(tǒng)如何產(chǎn)生相應的物理地址及寫出物理地址。答：虛擬地址11123456 （八進制）轉(zhuǎn)化為二進制為： 001 001 001 010 011 100 101 110其中前面為頁號，而后10 位為位移：001 001 001 010 01-1 100 101 110 。由于主存大小為218 B，頁面尺寸為1KB ，所以，主存共有256 塊。所以，塊號為100 （八進制）是合法地址，于是，物理地址為100 （八進制）與位移1 100 101 110 并接，得到：八進制物理地址001000000 1 100 101 110 = = 201456 （八進制）。13 主存中有兩個空間區(qū)如圖所示，100K50K0K15K125K現(xiàn)有作業(yè)序列依次為：Job1 要求30K ; Job2 要求70K ; Job3 要求50K ；使用首次適應、最壞適應和最佳適應算法處理這個作業(yè)序列，試問哪種算法可以滿足分配？為什么？答：首次適應、最壞適應算法處理這個作業(yè)序列可以滿足分配，最佳適應算法不行。因為后者會分割出無法使用的碎片，浪費內(nèi)存，從而，不能滿足所有作業(yè)的內(nèi)存需求。14 設有一頁式存儲管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16 頁，每頁2048 字節(jié)，內(nèi)存總共有8 個存儲塊。試問邏輯地址至少應為多少位？內(nèi)存空間有多大？答：邏輯地址21124 ，故為15 位。內(nèi)存大小為23211 = 214B = 16KB 。15、在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16 位，頁面大小為4096 字節(jié)，現(xiàn)有一邏輯地址為ZF6AH ，且第0 、1 、2 頁依次存在物理塊10 、12 、14 號中，問相應的物理地址為多少？答：因為邏輯地址長度為16 位，而頁面大小為4096字節(jié)，所以，前面的4 位表示頁號。把ZF6AH 轉(zhuǎn)換成二進制為：00 10 1 1 11 0110 1010 ，可知頁號為2 。故放在14 號物理塊中，寫成十六進制為：EF6AH 。16 有矩陣：VAR A : ARRAY 1 100 , 1 100 OF integer；元素按行存儲。在一虛存系統(tǒng)中，采用LRU 淘汰算法，一個進程有3 頁內(nèi)存空間，每頁可以存放200 個整數(shù)。其中第1 頁存放程序，且假定程序已在內(nèi)存。程序A : FOR i : = 1 TO 100 DO FOR j : = 1 TO 100 DO A i，j : = 0 ; 程序B : FOR j : = 1 TO 100 DO FOR i : = 1 TO 100 DO A i,j : = 0 ; 分別就程序A 和B 的執(zhí)行進程計算缺頁次數(shù)。答：100 * 100 = 10000 個數(shù)據(jù)，每頁可以存放200 個整數(shù)，故一共存放在50 個第99 行、第100 行缺頁中斷為5000 次。由于元素按行存儲，第1 行、第2 行放在第1 頁， 第99行、第100行放在第50 頁。故對于程序A ，缺頁中斷為50 次。對于程序B，缺頁中斷為5000次。17、一臺機器有48 位虛地址和32 位物理地址，若頁長為8KB ，問頁表共有多少個頁表項？如果設計一個反置頁表，則有多少個頁表項？答：因為頁長8KB 占用13 位，所以，頁表項有235個。反置頁表項有219 個。18 在虛擬頁式存儲管理中，為解決抖動問題，可采用工作集模型以決定分給進程的物理塊數(shù)，有如下頁面訪問序列： 2 5 1 6 3 3 7 8 9 1 6 2 3 4 3 4 3 4 4 4 3 4 4 3 | t1 | | t2 | 窗口尺寸 9 ，試求t1 、t2 時刻的工作集。答：t1 時刻的工作集為： l , 2 , 3 , 6 , 7 , 8 , 9 。t 時刻的工作集為： 3 , 4 。19 有一個分頁虛存系統(tǒng)，測得CPU 和磁盤的利用率如下，試指出每種情況下的存在問題和可采取的措施：( 1 ) CPU 利用率為13 % ，磁盤利用率為97 % ( 2 ) CPU 利用率為87 % ，磁盤利用率為3 % ( 3 ) CPU 利用率為13 % ，磁盤利用率為3 。答：( 1 ）系統(tǒng)可能出現(xiàn)抖動，可把暫停部分進程運行。（2 ）系統(tǒng)運行正常，可增加運行進程數(shù)以進一步提高資源利用率。（3 ）處理器和設備和利用率均很低，可增加并發(fā)運行的進程數(shù)。20、在一個分頁虛存系統(tǒng)中，用戶編程空間32 個頁，頁長IKB ，主存為16KBo 如果用戶程序有10 頁長，若己知虛頁0 、1 、2 、3 ，己分到頁框8 、7 、4 、10 , 試把虛地址OACSH 和IACSH 轉(zhuǎn)換成對應的物理地址。答：虛地址OACSH 對應的物理地址為：12CSH 。而執(zhí)行虛地址IACSH 會發(fā)現(xiàn)頁表中尚未有分配的頁框而發(fā)生缺頁中斷，由系統(tǒng)另行分配頁框。21 某計算機有4 個頁框，每頁的裝入時間、最后訪問時間、訪問位R 、修改位D 如下所示（時間用時鐘點數(shù)表示）: page loaded last ref R D 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1 分別用FIFO 、LRU 、二次機會算法分別淘汰哪一頁？答：( 1 ) FIFO 淘汰page2 。( 2 ) LRU 淘汰page1 。( 3 ）二次機會淘汰page122 考慮下面的程序：for ( i = 0;i 20 ; i+） For(j=0;j 2 ) 3 ) 4 ) 5 ) 6 ) . 答：l ) 680 ( 2 ) 915(3 ) 904(4 ）越界(5 ) 1750(6 ）越界。28請頁式存儲管理中，進程訪問地址序序列為：10 , 11 , 104 , 170 , 73 , 305 , 180 , 240 , 2 科，科5 , 467 , 366。試問(1 ）如果頁面大小為100 ，給出頁面訪問序列。2 、講程若分3個頁框采用FIFO 和LRU 替換算法，求缺頁中斷率？答：l ）頁面訪問序列為l , l , 2 , 2 , 1 , 4 , 2 , 3 , 3 , 5 , 5 , 4 。2 ) FIFO 為5 次，缺頁中斷率為5 / 12 科41.6 。LRU 為6 次，缺頁中斷率為6 / 12 = 50 。LRU 反比FIFO 缺頁中斷率高。29 假設計算機有2M 內(nèi)存，其中，操作系統(tǒng)占用512K ，每個用戶程序也使用512K 內(nèi)存。如果所有程序都有70 的I/O 等待時間，那么，再增加1M 內(nèi)存，吞吐率增加多少？答：由題意可知，內(nèi)存中可以存放3 個用戶進程，而CPU 的利用率為：1-（70 % )3 , = 1 一（0 . 7 )3 = 65 . 7 。再增加1M 內(nèi)存，可增加2 個用戶進程，這時CPU 的利用率為：1 -（70 % )5 , = 1 一（0 7）583 . 2 。故再增加1M 內(nèi)存，吞吐率增加了：83 . 2 /65 . 7 -100 % =27 。30 一個計算機系統(tǒng)有足夠的內(nèi)存空間存放4 道程序，這些程序有一半時間在空閑等待I/O 操作。問多大比例的CPU 時間被浪費掉了？答：( 500 % )( l / 2 ) = 1 / 16 。31 如果一條指令平均需1 微秒，處理一個缺頁中斷另需n 微秒，給出當缺頁中斷每k 條指令發(fā)生一次時，指令的實際執(zhí)行時間。答：( 1 +n/k)微秒。32 一臺計算機的內(nèi)存空間為1024 個頁面，頁表放在內(nèi)存中，從頁表中讀一個字的開銷是50Ons 。為了減少開銷，使用了有32 個字的快表，查找速度為10Ons 。要把平均開銷降到20Ons 需要的快表命中率是多少？答：設快表命中率是x ，則內(nèi)存命中率為1-x。于是：500 ( 1-x）+ 100x = = 2 00 ，解方程得x=75 。33 假設一條指令平均需花1 微秒，但若發(fā)生了缺頁中斷就需2001 微秒。如果一個程序運行了60 秒，期間發(fā)生了15000 次缺頁中斷，若可用內(nèi)存是原來的兩倍，這個程序壇行需要多少時間？答：一個程序運行期間發(fā)生了15000 次缺頁中斷，由于缺頁中斷處理花2000 微秒（1 微秒是指令執(zhí)行時間，于是這個程序缺頁中斷處理花了：2000 微秒米1 5000 = 30 秒。占了運行時間60 秒的一半。當可用內(nèi)存是原來的兩倍時，缺頁中斷次數(shù)減為一半，故有巧秒就能處理完。所以，這個程序運行需要時間為：45 秒。34 在分頁式虛存管理中，若采用FIFO替換算法，會發(fā)生：分給作業(yè)頁面越多，進程執(zhí)行時缺頁中斷率越高的奇怪現(xiàn)象。試舉例說明這個現(xiàn)象。答：見本章應用題7 。35 假設一個任務被劃分成4 個大小相等的段，每段有8 項的頁描述符表，若頁面大小一為ZKB 。試問段頁式存儲系統(tǒng)中：( a ）每段最大尺寸是多少？偽）該任務的邏輯地址空間最大為多少？( c ）若該任務訪問到邏輯地址空間5ABCH 中的一個數(shù)據(jù)，試給出邏輯地址的格式。答：段數(shù)2 2 = 4 ，每段有23 = 8 頁，頁大小為211= ZKB 。（a ）故每段最大為214B = 16KB 。偽）邏輯她曳匕勿風爆七尺4 又、曰KB = 64KB 。( c ）若該任務訪問到邏輯地址空間SABCH ，其二進制表示為：0 101 1010 1011 1100 所以，邏輯地址表示為：01 011 010 1011 1100 SABCH 的邏輯地址為：第1 段第3 頁，位移由后11 位給出。36.對已知某系統(tǒng)頁面長4KB ，頁表項4B ，采用多級頁表映射64 位虛地址空間。若限定最高層頁表占1 頁，問它可以采用幾級頁表？答：由于頁面長4KB ，頁表項4B ，故每頁可 包含IKB 個頁表項。由于限定最高層頁表占1 頁，即它的頁表項為210個；而每個頁表項指向一頁，每頁又存放頁表項個數(shù)為210 個，依此類推，最多可以采用硯巧取整為6 級頁表。37 在請求分頁虛存管理系統(tǒng)中，若駐留集為m 個頁框，頁框初始為空，在長為p 的引用串中具有n 個不同頁面nm ) ，對于FIFO、LRU 兩種頁面替換算法，試給出缺頁中斷的上限和下限，并舉例說明。答：對于FIFO 、LRU 兩種頁面替換算法，缺頁中斷的上限和下限：為p 和n 。因為有n 個不同頁面，無論怎樣安排，不同頁面進入內(nèi)存至少要產(chǎn)生一次缺頁中斷，故下限為n 次。由于mn ，引用串中有些頁可能進入內(nèi)存后又被調(diào)出，而多次發(fā)生缺頁中斷。極端情況，訪問的頁都不在內(nèi)存，這樣共發(fā)生了p 次缺頁中斷。例如，當vm =3 ，p=12 , n =4 時，有如下訪問中：1 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 , 4 。缺頁中斷為下限4 次。而訪問串：2 , 3 , 4 , 1 , 2 , 3 , 4 , 1 , 2 , 3 , 4 , 1 。缺頁中斷為上限12 次。38 在請求分頁虛存管理系統(tǒng)中，頁表保存在寄存器中。若替換一個未修改過頁面的缺頁中斷處理需8 毫秒，若替換一個己修改過頁面的缺頁中斷處理需另加寫盤時間12 毫秒，內(nèi)存存取周期為1 微秒。假定70 被替換的頁面被修改過，為保證有效存取時間不超過2 微秒，允許的最大缺頁中斷率為多少？答：設最大缺頁中斷率為x ，則