操作系統(tǒng)習(xí)題及答案

1、CH4 應(yīng)用題參考答案1 在一個(gè)請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理系統(tǒng)中，一個(gè)程序運(yùn)行的頁(yè)面走向是：1 、2 、3 、4 、2 、1 、5 、6 、2 、1 、2 、3 、7 、6 、3 、2 、1 、2 、3 、6 。分別用FIFO 、OPT 和LRU 算法，對(duì)分配給程序3 個(gè)頁(yè)框、4 個(gè)頁(yè)框、5 個(gè)頁(yè)框和6 個(gè)頁(yè)框的情況下，分別求出缺頁(yè)中斷次數(shù)和缺頁(yè)中斷率。答：頁(yè)框數(shù)FIFOLRUOPT3456161412915108711877只要把表中缺頁(yè)中斷次數(shù)除以20，便得到缺頁(yè)中斷率。2 在一個(gè)請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理系統(tǒng)中，一個(gè)作業(yè)共有5 頁(yè)，執(zhí)行時(shí)其訪問頁(yè)面次序?yàn)椋? 1 ) 1 、4 、3 、1 、2 、5

2、 、1 、4 、2 、1 、4 、5( 2 ) 3 、2 、1 、4 、4 、5 、5 、3 、4、3、2、1、5若分配給該作業(yè)三個(gè)頁(yè)框，分別采用FIFO和LRU 面替換算法，求出各自的缺頁(yè)中斷次數(shù)和缺頁(yè)中斷率。答：( 1 ）采用FIFO 為9 次，9 / 12 = 75 。采用LRU 為8 次，8 / 12 = 67 。( 2 ）采用FIFO 和LRU 均為9 次，9 / 13 = 69 。3 一個(gè)頁(yè)式存儲(chǔ)管理系統(tǒng)使用FIFO 、OPT 和LRU 頁(yè)面替換算法，如果一個(gè)作業(yè)的頁(yè)面走向?yàn)椋? l ) 2 、3 、2 、l 、5 、2 、4 、5 、3 、2 、5 、2 。( 2 ) 4 、3

3、、2 、l 、4 、3 、5 、4 、3 、2 、l 、5 。( 3 ) 1 、2 、3 、4 、1 、2 、5 、l 、2 、3 、4 、5 。當(dāng)分配給該作業(yè)的物理塊數(shù)分別為3 和4 時(shí)，試計(jì)算訪問過程中發(fā)生的缺頁(yè)中斷次數(shù)和缺頁(yè)中斷率。答：( 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 。(

4、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ù)，反使缺頁(yè)中斷率上升。4、在可變分區(qū)存儲(chǔ)管理下，按地址排列的內(nèi)存空閑區(qū)為：10K 、4K 、20K 、18K 、7K 、9K 、12K 和15K 。對(duì)于下列的連續(xù)存儲(chǔ)區(qū)的請(qǐng)求：( l ) 12K 、10K 、9K ,

5、( 2 ) 12K 、10K 、15K 、18K 試問：使用首次適應(yīng)算法、最佳適應(yīng)算法、最差適應(yīng)算法和下次適應(yīng)算法，哪個(gè)空閑區(qū)被使用？答：( 1 ）空閑分區(qū)如圖所示。答分區(qū)號(hào)分區(qū)長(zhǎng)1234567810K4K20K18K7K9K12K15K1）首次適應(yīng)算法12KB 選中分區(qū)3 ，這時(shí)分區(qū)3 還剩8KB 。10KB 選中分區(qū)1 ，恰好分配故應(yīng)刪去分區(qū)1 。9KB 選中分區(qū)4 ，這時(shí)分區(qū)4 還剩9KB 。2 ）最佳適應(yīng)算法12KB 選中分區(qū)7 ，恰好分配故應(yīng)刪去分區(qū)7 。1OKB 選中分區(qū)1 ，恰好分配故應(yīng)刪去分區(qū)1 。9KB 選中分區(qū)6 ，恰好分配故應(yīng)刪去分區(qū)6 。3 ）最差適應(yīng)算法12KB 選中

6、分區(qū)3 ，這時(shí)分區(qū)3 還剩8KB 。1OKB 選中分區(qū)4 ，這時(shí)分區(qū)4 還剩8KB 。9KB 選中分區(qū)8 ，這時(shí)分區(qū)8 還剩6KB 。4 ）下次適應(yīng)算法12KB 選中分區(qū)3 ，這時(shí)分區(qū)3 還剩8KB 。10KB 選中分區(qū)4 ，這時(shí)分區(qū)4 還剩8KB 。9KB 選中分區(qū)6 ，恰好分配故應(yīng)刪去分區(qū)6 。( 2 ）原始分區(qū)情況同上圖。1 ）首次適應(yīng)算法12KB 選中分區(qū)3 ，這時(shí)分區(qū)3 還剩8KB 。10KB 選中分區(qū)1 ，恰好分配故應(yīng)刪去分區(qū)1 。15KB 選中分區(qū)4 ，這時(shí)分區(qū)4 還剩3KB 。最后無法滿足18KB 的申請(qǐng)，應(yīng)該等待。2 ）最佳適應(yīng)算法12KB 選中分區(qū)7 ，恰好分配故應(yīng)刪去分區(qū)

7、7 。1OKB 選中分區(qū)1 ，恰好分配故應(yīng)刪去分區(qū)1 。15KB 選中分區(qū)8 ，恰好分配故應(yīng)刪去分區(qū)8 。18KB 選中分區(qū)4 ，恰好分配故應(yīng)刪去分區(qū)4 。3 ）最差適應(yīng)算法12KB 選中分區(qū)3 ，這時(shí)分區(qū)3 還剩8KB 。10KB 選中分區(qū)4 ，這時(shí)分區(qū)4 還剩8KB 。15KB 選中分區(qū)8 ，恰好分配故應(yīng)刪去分區(qū)8 。最后無法滿足18KB 的申請(qǐng)，應(yīng)該等待。4 ）下次適應(yīng)算法12KB 選中分區(qū)3 ，這時(shí)分區(qū)3 還剩8KB 。1OKB 選中分區(qū)4 ，這時(shí)分區(qū)4 還剩8KB 。15KB 選中分區(qū)8 ，恰好分配故應(yīng)刪去分區(qū)8 。最后無法滿足15KB 的申請(qǐng)，應(yīng)該等待。5 給定內(nèi)存空閑分區(qū)，按地址

8、從小到大為：100K 、500K 、200K 、300K 和600K ?，F(xiàn)有用戶進(jìn)程依次分別為212K 、417K 、112K 和426K , ( l ）分別用first-fit 、best-fit 和worst-fit 算法將它們裝入到內(nèi)存的哪個(gè)分區(qū)？( 2 ）哪個(gè)算法能最有效利用內(nèi)存？答：按題意地址從小到大進(jìn)行分區(qū)如圖所示。分區(qū)號(hào)分區(qū)長(zhǎng)12345100KB500KB200KB300KB600KB( 1 ) 1）first-fit 212KB 選中分區(qū)2 ，這時(shí)分區(qū)2 還剩288KB 。417KB 選中分區(qū)5 ，這時(shí)分區(qū)5 還剩183KB 。112KB 選中分區(qū)2 ，這時(shí)分區(qū)2 還剩176K

9、B 。426KB 無分區(qū)能滿足，應(yīng)該等待。2 ) best-fit 212KB 選中分區(qū)4 ，這時(shí)分區(qū)4 還剩88KB 。417KB 選中分區(qū)2 ，這時(shí)分區(qū)2 還剩83KB 。112KB 選中分區(qū)3 ，這時(shí)分區(qū)3 還剩88KB 。426KB 選中分區(qū)5 ，這時(shí)分區(qū)5 還剩174KB 。3 ) worst-fit 212KB 選中分區(qū)5 ，這時(shí)分區(qū)5 還剩388KB 。417KB 選中分區(qū)2 , 這時(shí)分區(qū)2 還剩83KB 。112KB 選中分區(qū)5 ，這時(shí)分區(qū)5 還剩176KB 。426KB 無分區(qū)能滿足，應(yīng)該等待。( 2 ）對(duì)于該作業(yè)序列，best-fit 算法能最有效利用內(nèi)存6、 一個(gè)32 位

10、地址的計(jì)算機(jī)系統(tǒng)使用二級(jí)頁(yè)表，虛地址被分為9 位頂級(jí)頁(yè)表，11位二級(jí)頁(yè)表和偏移。試問：頁(yè)面長(zhǎng)度是多少？虛地址空間共有多少個(gè)頁(yè)面？答：由于32-9 -11 12 ，所以，頁(yè)面大小為4KB ，頁(yè)面的個(gè)數(shù)為220個(gè)。7、 一進(jìn)程以下列次序訪問5 個(gè)頁(yè)：A 、B 、C 、D 、A 、B 、E 、A 、B 、C 、D 、E ：假定使用FIFO 替換算法，在內(nèi)存有3 個(gè)和4 個(gè)空閑頁(yè)框的情況下，分別給出頁(yè)面替換次數(shù)。答：內(nèi)存有3 個(gè)和4 個(gè)空閑頁(yè)框的情況下，頁(yè)面替換次數(shù)為9 次和10 次。出現(xiàn)了Belady 即現(xiàn)象，增加分給作業(yè)的內(nèi)存塊數(shù)，反使缺頁(yè)中斷率上升。8、 某計(jì)算機(jī)有緩存、內(nèi)存、輔存來實(shí)現(xiàn)虛擬存儲(chǔ)

11、器。如果數(shù)據(jù)在緩存中，訪問它需要Ans；如果在內(nèi)存但不在緩存，需要Bns 將其裝入緩存，然后才能訪問；如果不在內(nèi)存而在輔存，需要Cns 將其讀入內(nèi)存，然后，用Bns 再讀入緩存，然后才能訪問。假設(shè)緩存命中率為（n-1) / n ，內(nèi)存命中率為（m -1) / m ，則數(shù)據(jù)平均訪問時(shí)間是多少？答：數(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ù)平均訪問時(shí)

12、間是( ( 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、某計(jì)算機(jī)有cache 、內(nèi)存、輔存來實(shí)現(xiàn)虛擬存儲(chǔ)器。如果數(shù)據(jù)在cache 中，訪問它需要20ns ；如果在內(nèi)存但不在cache ，需要60ns 將其裝入緩存，然后才能訪問；如果不在內(nèi)存而在輔存，需要12us將其讀入內(nèi)存，然后，用60ns 再讀

13、入cache ，然后才能訪問。假設(shè)cache 命中率為0 .9 ，內(nèi)存命中率為0.6 ，則數(shù)據(jù)平均訪問時(shí)間是多少（ns ) ? 答：506ns 。10 有一個(gè)分頁(yè)系統(tǒng)，其頁(yè)表存放在主存里，( 1 ）如果對(duì)內(nèi)存的一次存取要1.2 微秒，試問實(shí)現(xiàn)一次頁(yè)面訪問的存取需花多少時(shí)間？( 2 ）若系統(tǒng)配置了聯(lián)想存儲(chǔ)器，命中率為80 % ，假定頁(yè)表表目在聯(lián)想存儲(chǔ)器的查找時(shí)間忽略不計(jì)，試問實(shí)現(xiàn)一次頁(yè)面訪問的存取時(shí)間是多少？答：(1) 2.4 微秒 （2 )0.8 × 1.2 + 0.2 × 2.4 = 0.76 + 0.45 = 1.24 微秒11 給定段表如下：段號(hào)段首址段長(zhǎng)021960

14、01230014290100313275804195296給定地址為段號(hào)和位移： 1 ) 0 , 430 、2 ) 3 , 400 、3 ) 1 , 1 、4 ) 2 , 500 、5 ) 4 , 42 ) ，試求出對(duì)應(yīng)的內(nèi)存物理地址。答：1) 649 2) 1 727 3) 2301 4）越界 5) 1994 12、 某計(jì)算機(jī)系統(tǒng)提供24 位虛存空間，主存為2 18 B ，采用分頁(yè)式虛擬存儲(chǔ)管理，頁(yè)面尺寸為1KB 。假定用戶程序產(chǎn)生了虛擬地址11123456 （八進(jìn)制），而該頁(yè)面分得塊號(hào)為100 ( 八進(jìn)制），說明該系統(tǒng)如何產(chǎn)生相應(yīng)的物理地址及寫出物理地址。答：虛擬地址11123456 （八

15、進(jìn)制）轉(zhuǎn)化為二進(jìn)制為： 001 001 001 010 011 100 101 110其中前面為頁(yè)號(hào)，而后10 位為位移：001 001 001 010 01-1 100 101 110 。由于主存大小為218 B，頁(yè)面尺寸為1KB ，所以，主存共有256 塊。所以，塊號(hào)為100 （八進(jìn)制）是合法地址，于是，物理地址為100 （八進(jìn)制）與位移1 100 101 110 并接，得到：八進(jìn)制物理地址001000000 1 100 101 110 = = 201456 （八進(jìn)制）。13 主存中有兩個(gè)空間區(qū)如圖所示，100K50K0K15K125K現(xiàn)有作業(yè)序列依次為：Job1 要求30K ; Job2

16、 要求70K ; Job3 要求50K ；使用首次適應(yīng)、最壞適應(yīng)和最佳適應(yīng)算法處理這個(gè)作業(yè)序列，試問哪種算法可以滿足分配？為什么？答：首次適應(yīng)、最壞適應(yīng)算法處理這個(gè)作業(yè)序列可以滿足分配，最佳適應(yīng)算法不行。因?yàn)楹笳邥?huì)分割出無法使用的碎片，浪費(fèi)內(nèi)存，從而，不能滿足所有作業(yè)的內(nèi)存需求。14 設(shè)有一頁(yè)式存儲(chǔ)管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16 頁(yè)，每頁(yè)2048 字節(jié)，內(nèi)存總共有8 個(gè)存儲(chǔ)塊。試問邏輯地址至少應(yīng)為多少位？?jī)?nèi)存空間有多大？答：邏輯地址211×24 ，故為15 位。內(nèi)存大小為23×211 = 214B = 16KB 。15、在一分頁(yè)存儲(chǔ)管理系統(tǒng)中，邏輯地址長(zhǎng)度為1

17、6 位，頁(yè)面大小為4096 字節(jié)，現(xiàn)有一邏輯地址為ZF6AH ，且第0 、1 、2 頁(yè)依次存在物理塊10 、12 、14 號(hào)中，問相應(yīng)的物理地址為多少？答：因?yàn)檫壿嫷刂烽L(zhǎng)度為16 位，而頁(yè)面大小為4096字節(jié)，所以，前面的4 位表示頁(yè)號(hào)。把ZF6AH 轉(zhuǎn)換成二進(jìn)制為：00 10 1 1 11 0110 1010 ，可知頁(yè)號(hào)為2 。故放在14 號(hào)物理塊中，寫成十六進(jìn)制為：EF6AH 。16 有矩陣：VAR A : ARRAY 1 100 , 1 100 OF integer；元素按行存儲(chǔ)。在一虛存系統(tǒng)中，采用LRU 淘汰算法，一個(gè)進(jìn)程有3 頁(yè)內(nèi)存空間，每頁(yè)可以存放200 個(gè)整數(shù)。其中第1 頁(yè)存放

18、程序，且假定程序已在內(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í)行進(jìn)程計(jì)算缺頁(yè)次數(shù)。答：100 * 100 = 10000 個(gè)數(shù)據(jù)，每頁(yè)可以存放200 個(gè)整數(shù)，故一共存放在50 個(gè)第99 行、第100 行缺頁(yè)中斷為5000 次。由于元素按行存儲(chǔ)，第1 行、第2 行放在第1 頁(yè)， 第99行、第100行放在第50 頁(yè)。故對(duì)于程序A ，缺頁(yè)中斷為50 次。對(duì)于程

19、序B，缺頁(yè)中斷為5000次。17、一臺(tái)機(jī)器有48 位虛地址和32 位物理地址，若頁(yè)長(zhǎng)為8KB ，問頁(yè)表共有多少個(gè)頁(yè)表項(xiàng)？如果設(shè)計(jì)一個(gè)反置頁(yè)表，則有多少個(gè)頁(yè)表項(xiàng)？答：因?yàn)轫?yè)長(zhǎng)8KB 占用13 位，所以，頁(yè)表項(xiàng)有235個(gè)。反置頁(yè)表項(xiàng)有219 個(gè)。18 在虛擬頁(yè)式存儲(chǔ)管理中，為解決抖動(dòng)問題，可采用工作集模型以決定分給進(jìn)程的物理塊數(shù)，有如下頁(yè)面訪問序列： 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 時(shí)刻的工作集。答：t1 時(shí)刻的工作集為： l , 2 , 3 , 6 , 7 , 8 , 9

20、 。t 時(shí)刻的工作集為： 3 , 4 。19 有一個(gè)分頁(yè)虛存系統(tǒng)，測(cè)得CPU 和磁盤的利用率如下，試指出每種情況下的存在問題和可采取的措施：( 1 ) CPU 利用率為13 % ，磁盤利用率為97 % ( 2 ) CPU 利用率為87 % ，磁盤利用率為3 % ( 3 ) CPU 利用率為13 % ，磁盤利用率為3 。答：( 1 ）系統(tǒng)可能出現(xiàn)抖動(dòng)，可把暫停部分進(jìn)程運(yùn)行。（2 ）系統(tǒng)運(yùn)行正常，可增加運(yùn)行進(jìn)程數(shù)以進(jìn)一步提高資源利用率。（3 ）處理器和設(shè)備和利用率均很低，可增加并發(fā)運(yùn)行的進(jìn)程數(shù)。20、在一個(gè)分頁(yè)虛存系統(tǒng)中，用戶編程空間32 個(gè)頁(yè)，頁(yè)長(zhǎng)IKB ，主存為16KBo 如果用戶程序有10

21、頁(yè)長(zhǎng)，若己知虛頁(yè)0 、1 、2 、3 ，己分到頁(yè)框8 、7 、4 、10 , 試把虛地址OACSH 和IACSH 轉(zhuǎn)換成對(duì)應(yīng)的物理地址。答：虛地址OACSH 對(duì)應(yīng)的物理地址為：12CSH 。而執(zhí)行虛地址IACSH 會(huì)發(fā)現(xiàn)頁(yè)表中尚未有分配的頁(yè)框而發(fā)生缺頁(yè)中斷，由系統(tǒng)另行分配頁(yè)框。21 某計(jì)算機(jī)有4 個(gè)頁(yè)框，每頁(yè)的裝入時(shí)間、最后訪問時(shí)間、訪問位R 、修改位D 如下所示（時(shí)間用時(shí)鐘點(diǎn)數(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 、二次機(jī)會(huì)算法分別淘

22、汰哪一頁(yè)？答：( 1 ) FIFO 淘汰page2 。( 2 ) LRU 淘汰page1 。( 3 ）二次機(jī)會(huì)淘汰page122 考慮下面的程序：for ( i = 0;i < 20 ; i+） For(j=0;j<10;j+)a i : = a i ×j 試舉例說明該程序的空間局部性和時(shí)間局部性。答：當(dāng)數(shù)組元素a 0 , a1 ， ，a 19 存放在一個(gè)頁(yè)面中時(shí)，其空間局部性和時(shí)間局部性較好，也就是說，在很短時(shí)間內(nèi)執(zhí)行都掛行循環(huán)乘法程序，而且數(shù)組元素分布在緊鄰連續(xù)的存儲(chǔ)單元中。當(dāng)數(shù)組元素存放在不同頁(yè)面中時(shí)，其時(shí)間局部性雖相同，但空間局部性較差，因?yàn)樘幚淼臄?shù)組元素分布在不

23、連續(xù)的存儲(chǔ)單元中。23 一個(gè)有快表的請(qǐng)頁(yè)式虛存系統(tǒng)，設(shè)內(nèi)存訪問周期為1 微秒，內(nèi)外存?zhèn)魉鸵粋€(gè)頁(yè)面的平均時(shí)間為5 毫秒。如果快表命中率為75 % ，缺頁(yè)中斷率為10 。忽略快表訪問時(shí)間，試求內(nèi)存的有效存取時(shí)間。答：快表命中率為75 % ，缺頁(yè)中斷率為10 % ，所以，內(nèi)存命中率為15。故內(nèi)存的有效存取時(shí)間1×75 % + 2*15%+( 5000+2) *10%=501.25 微秒。24 假設(shè)某虛存的用戶空間為IO24KB ，頁(yè)面大小為4KB ，內(nèi)存空間為512KB 。已知用戶的虛頁(yè)10 、11 、12 、13 頁(yè)分得內(nèi)存頁(yè)框號(hào)為62 、78 、25 、36 ，求出虛地址OBEBC (

24、 16 進(jìn)制）的實(shí)地址（16 進(jìn)制）是多少？答：虛地址0BEBC ( 16 進(jìn)制）的二進(jìn)制形式為：0000 1 011 1110 1011 1100 。由于頁(yè)面大小為4KB ，故其中后12 位是位移，所以，虛地址的頁(yè)號(hào)為：11 。查頁(yè)表分得內(nèi)存對(duì)應(yīng)頁(yè)框號(hào)為：78 。己知內(nèi)存空間為512KB ，故內(nèi)存共有128 個(gè)頁(yè)框，78 是合法物理塊。把78 化為16 進(jìn)制是4E ，虛地址OBEBC ( 16 進(jìn)制）的實(shí)地址（16 進(jìn)制）是：4EEBC 。25 某請(qǐng)求分頁(yè)存儲(chǔ)系統(tǒng)使用一級(jí)頁(yè)表，假設(shè)頁(yè)表全部放在主存內(nèi)，: 1 ）若一次訪問主存花120ns ，那么，訪問一個(gè)數(shù)據(jù)的時(shí)間是多少？2 ）若增加一個(gè)快表

25、，在命中或失誤時(shí)需有20ns 開銷，如果快表命中率為80 % ，則訪問一個(gè)數(shù)據(jù)的時(shí)間為答：1 ) 120ns*2 = 240ns 2 ) ( 120 + 20 ) *80 % +(120+120+20)*20%=174ns26 設(shè)某系統(tǒng)中作業(yè)J . , JZ , J3 占用主存的情況如圖。今有一個(gè)長(zhǎng)度為20k 的作業(yè)J4 要裝入主存，當(dāng)采用可變分區(qū)分配方式時(shí)，請(qǐng)回答：( l ) J4 裝入前的主存己分配表和未分配表的內(nèi)容。( 2 ）寫出裝入J4 時(shí)的工作流程，并說明你采用什么分配算法。10k 18k 30k 40k 54k70k 答：( 1 ）主存已分配表共有三項(xiàng)，由作業(yè)j1 、j2 、j3

26、占用，長(zhǎng)度依次為：10k 、30k 和54k 未分配表共有三項(xiàng)：空閑區(qū)1 、空閑區(qū)2 和空閑區(qū)3 ，長(zhǎng)度依次為18k 、40k 和70k 。( 2 ）作業(yè)J4 裝入時(shí)，采用直接分配，搜索未分配表，空閑區(qū)1 不能滿足。所以，要繼續(xù)搜索未分配表，空閑區(qū)2 可以滿足J4 的裝入要求。27 考慮下列的段表：段號(hào)始址段長(zhǎng): 段號(hào) 始址 段長(zhǎng) 0 200 500 1 890 30 2 120 100 3 1250 600 4 1800 88 對(duì)下面的邏輯地址，求物理地址，如越界請(qǐng)指明。l ) 0,480 > 2 ) < l ,25 > 3 ) < l ,14 > 4 ) &l

27、t; 2 , 200> 5 ) < 3 ,500 > 6 ) < 4 ,100 > . 答：l ) 680 ( 2 ) 915(3 ) 904(4 ）越界(5 ) 1750(6 ）越界。28請(qǐng)頁(yè)式存儲(chǔ)管理中，進(jìn)程訪問地址序序列為：10 , 11 , 104 , 170 , 73 , 305 , 180 , 240 , 2 科，科5 , 467 , 366。試問(1 ）如果頁(yè)面大小為100 ，給出頁(yè)面訪問序列。2 、講程若分3個(gè)頁(yè)框采用FIFO 和LRU 替換算法，求缺頁(yè)中斷率？答：l ）頁(yè)面訪問序列為l , l , 2 , 2 , 1 , 4 , 2 , 3 ,

28、3 , 5 , 5 , 4 。2 ) FIFO 為5 次，缺頁(yè)中斷率為5 / 12 科41.6 。LRU 為6 次，缺頁(yè)中斷率為6 / 12 = 50 。LRU 反比FIFO 缺頁(yè)中斷率高。29 假設(shè)計(jì)算機(jī)有2M 內(nèi)存，其中，操作系統(tǒng)占用512K ，每個(gè)用戶程序也使用512K 內(nèi)存。如果所有程序都有70 的I/O 等待時(shí)間，那么，再增加1M 內(nèi)存，吞吐率增加多少？答：由題意可知，內(nèi)存中可以存放3 個(gè)用戶進(jìn)程，而CPU 的利用率為：1-（70 % )3 , = 1 一（0 . 7 )3 = 65 . 7 。再增加1M 內(nèi)存，可增加2 個(gè)用戶進(jìn)程，這時(shí)CPU 的利用率為：1 -（70 % )5 ,

29、 = 1 一（0 7）583 . 2 。故再增加1M 內(nèi)存，吞吐率增加了：83 . 2 /65 . 7 -100 % =27 。30 一個(gè)計(jì)算機(jī)系統(tǒng)有足夠的內(nèi)存空間存放4 道程序，這些程序有一半時(shí)間在空閑等待I/O 操作。問多大比例的CPU 時(shí)間被浪費(fèi)掉了？答：( 500 % )( l / 2 ) = 1 / 16 。31 如果一條指令平均需1 微秒，處理一個(gè)缺頁(yè)中斷另需n 微秒，給出當(dāng)缺頁(yè)中斷每k 條指令發(fā)生一次時(shí)，指令的實(shí)際執(zhí)行時(shí)間。答：( 1 +n/k)微秒。32 一臺(tái)計(jì)算機(jī)的內(nèi)存空間為1024 個(gè)頁(yè)面，頁(yè)表放在內(nèi)存中，從頁(yè)表中讀一個(gè)字的開銷是50Ons 。為了減少開銷，使用了有32 個(gè)

30、字的快表，查找速度為10Ons 。要把平均開銷降到20Ons 需要的快表命中率是多少？答：設(shè)快表命中率是x ，則內(nèi)存命中率為1-x。于是：500 ( 1-x）+ 100x = = 2 00 ，解方程得x=75 。33 假設(shè)一條指令平均需花1 微秒，但若發(fā)生了缺頁(yè)中斷就需2001 微秒。如果一個(gè)程序運(yùn)行了60 秒，期間發(fā)生了15000 次缺頁(yè)中斷，若可用內(nèi)存是原來的兩倍，這個(gè)程序壇行需要多少時(shí)間？答：一個(gè)程序運(yùn)行期間發(fā)生了15000 次缺頁(yè)中斷，由于缺頁(yè)中斷處理花2000 微秒（1 微秒是指令執(zhí)行時(shí)間，于是這個(gè)程序缺頁(yè)中斷處理花了：2000 微秒米1 5000 = 30 秒。占了運(yùn)行時(shí)間60 秒

31、的一半。當(dāng)可用內(nèi)存是原來的兩倍時(shí)，缺頁(yè)中斷次數(shù)減為一半，故有巧秒就能處理完。所以，這個(gè)程序運(yùn)行需要時(shí)間為：45 秒。34 在分頁(yè)式虛存管理中，若采用FIFO替換算法，會(huì)發(fā)生：分給作業(yè)頁(yè)面越多，進(jìn)程執(zhí)行時(shí)缺頁(yè)中斷率越高的奇怪現(xiàn)象。試舉例說明這個(gè)現(xiàn)象。答：見本章應(yīng)用題7 。35 假設(shè)一個(gè)任務(wù)被劃分成4 個(gè)大小相等的段，每段有8 項(xiàng)的頁(yè)描述符表，若頁(yè)面大小一為ZKB 。試問段頁(yè)式存儲(chǔ)系統(tǒng)中：( a ）每段最大尺寸是多少？偽）該任務(wù)的邏輯地址空間最大為多少？( c ）若該任務(wù)訪問到邏輯地址空間5ABCH 中的一個(gè)數(shù)據(jù)，試給出邏輯地址的格式。答：段數(shù)2 2 = 4 ，每段有23 = 8 頁(yè)，頁(yè)大小為21

32、1= ZKB 。（a ）故每段最大為214B = 16KB 。偽）邏輯她曳匕勿風(fēng)爆七尺4 又、曰KB = 64KB 。( c ）若該任務(wù)訪問到邏輯地址空間SABCH ，其二進(jìn)制表示為：0 101 1010 1011 1100 所以，邏輯地址表示為：01 011 010 1011 1100 SABCH 的邏輯地址為：第1 段第3 頁(yè)，位移由后11 位給出。36.對(duì)已知某系統(tǒng)頁(yè)面長(zhǎng)4KB ，頁(yè)表項(xiàng)4B ，采用多級(jí)頁(yè)表映射64 位虛地址空間。若限定最高層頁(yè)表占1 頁(yè)，問它可以采用幾級(jí)頁(yè)表？答：由于頁(yè)面長(zhǎng)4KB ，頁(yè)表項(xiàng)4B ，故每頁(yè)可· 包含IKB 個(gè)頁(yè)表項(xiàng)。由于限定最高層頁(yè)表占1 頁(yè)，即

33、它的頁(yè)表項(xiàng)為210個(gè)；而每個(gè)頁(yè)表項(xiàng)指向一頁(yè)，每頁(yè)又存放頁(yè)表項(xiàng)個(gè)數(shù)為210 個(gè)，依此類推，最多可以采用硯巧取整為6 級(jí)頁(yè)表。37 在請(qǐng)求分頁(yè)虛存管理系統(tǒng)中，若駐留集為m 個(gè)頁(yè)框，頁(yè)框初始為空，在長(zhǎng)為p 的引用串中具有n 個(gè)不同頁(yè)面nm ) ，對(duì)于FIFO、LRU 兩種頁(yè)面替換算法，試給出缺頁(yè)中斷的上限和下限，并舉例說明。答：對(duì)于FIFO 、LRU 兩種頁(yè)面替換算法，缺頁(yè)中斷的上限和下限：為p 和n 。因?yàn)橛衝 個(gè)不同頁(yè)面，無論怎樣安排，不同頁(yè)面進(jìn)入內(nèi)存至少要產(chǎn)生一次缺頁(yè)中斷，故下限為n 次。由于m<n ，引用串中有些頁(yè)可能進(jìn)入內(nèi)存后又被調(diào)出，而多次發(fā)生缺頁(yè)中斷。極端情況，訪問的頁(yè)都不在內(nèi)存，這樣共發(fā)生了p 次缺頁(yè)中斷。例如，當(dāng)vm =3 ，p=12 , n =4 時(shí)，有如下訪問中：1 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 , 4 。缺頁(yè)中斷為下限4 次。而訪問串：2 , 3 , 4 , 1 , 2 , 3 , 4 , 1 , 2 , 3 , 4 , 1 。缺頁(yè)中斷為上限12 次。38