計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課堂習(xí)題答案

1、1.經(jīng)統(tǒng)計(jì)，某機(jī)器14條指令的使用頻度分別為：，.分別求出用等長(zhǎng)碼、 哈夫曼碼、只有兩種碼長(zhǎng)的擴(kuò)展操作碼等3種編碼方式的操作碼平均碼長(zhǎng).答：分析等長(zhǎng)操作碼的意思是不管其指令的頻度如何，都用同樣長(zhǎng)度的二進(jìn)制碼位 數(shù)來(lái)對(duì)指令操作碼編碼。 顯然，當(dāng)指令系統(tǒng)中的指令條數(shù)為n時(shí)，等長(zhǎng)操作碼的二進(jìn)制碼位數(shù)應(yīng)當(dāng)是 10g 2 n 。Huffman編碼是用 Huffman算法構(gòu)造出 Huffman樹(shù)來(lái)得到的。它的平均碼長(zhǎng)是用 nPi 1計(jì)算求得的。i 1只有兩種碼長(zhǎng)的擴(kuò)展操作碼編碼，則需要對(duì)指令使用頻度進(jìn)行按大小分群。將高頻的指令分在同一群中，對(duì)其用短的操作碼編碼，而將低頻的指令分在另一群中，使用長(zhǎng) 操作碼編

2、碼。每一群都各自用等長(zhǎng)操作碼編碼。這時(shí)，為能唯一解碼和立即解碼，在短 操作碼中還要使用某些碼來(lái)作為擴(kuò)展成長(zhǎng)操作碼的擴(kuò)展標(biāo)志碼。經(jīng)過(guò)綜合權(quán)衡，使平均n碼長(zhǎng)盡可能短，來(lái)定好長(zhǎng)、短碼的碼長(zhǎng)組配關(guān)系。從而，再用Pi li來(lái)求得其平均碼i1長(zhǎng)。解答14條指令的等長(zhǎng)操作碼的平均碼長(zhǎng)是log 214位，即4位。Huffman編碼可先用 Huffman算法構(gòu)造出 Huffman樹(shù)。本題的Huffman樹(shù)如圖所示。 圖中，葉子上用圓括號(hào)所括起的數(shù)字是表示該頻度指令所用的二進(jìn)位編碼的碼位14數(shù)，所以Huffman編碼的操作碼平均碼長(zhǎng)為Pi h 二位。i1（曲）0 2. 1 2* 10 的 Huffman 用采用只

3、有兩種碼長(zhǎng)的擴(kuò)展操作碼，可根據(jù)14條指令所給出的使用頻度值分成兩群。讓使用頻度較高的 6種指令用3位操作碼編碼表示。例如，用 000101分別表示 使用頻度為的指令的操作碼。留下 110和111兩個(gè)3位碼作為長(zhǎng)碼的擴(kuò)展標(biāo)志，擴(kuò)展出2位碼。從而用5位碼就可以各擴(kuò)展出4條使用頻度較低的指令，這樣，共有 8 條使用頻度較低的指令符合題目的要求。由此可求得操作碼的平均碼長(zhǎng)為14Pi i 1li=30.80 5 0.203.4位.設(shè)中斷級(jí)屏蔽位” 1對(duì)應(yīng)于開(kāi)放，”網(wǎng)應(yīng)于屏蔽，各級(jí)中斷處理程序的中斷級(jí)屏蔽位 設(shè)置如表3-4所示。表3-4習(xí)題3-5中的中斷級(jí)屏蔽位位置中斷處理程序級(jí)別中斷級(jí)屏蔽位第1級(jí)第2級(jí)

4、第3級(jí)第4級(jí)第1級(jí)0000第2級(jí)1011第3級(jí)1000第4級(jí)1010(1)當(dāng)中斷響應(yīng)優(yōu)先次序?yàn)?1-2-3-4時(shí)，其中斷處理次序是什么(2)如果所有的中斷處理都各需 3個(gè)單位時(shí)間，中斷響應(yīng)和中斷返回時(shí)間相對(duì)中斷處理時(shí)間少很多。當(dāng)機(jī)器正在運(yùn)行用戶(hù)程序時(shí)，同時(shí)發(fā)生第2、3級(jí)中斷請(qǐng)求，過(guò)兩個(gè)單位時(shí)間后，又同時(shí)發(fā)生第 1、4級(jí)中斷請(qǐng)求，試畫(huà)出程序運(yùn)行過(guò)程示意圖。答:(1)中斷處理(完)的次序?yàn)? 一 3一 4一Z(2)由題目所給出的條件，其 CPU運(yùn)行程序的過(guò)程示意田如圖3. 2所示。圖中，粗短 線(xiàn)部分代表進(jìn)行交換程序狀態(tài)字的時(shí)間，t為1個(gè)單位時(shí)間。中廝處理狎序幽I求用”序 J_ _2_ 2_4圖露

5、遇3的程中足懺過(guò)程加息圖.若機(jī)器共有5級(jí)中斷，中斷響應(yīng)優(yōu)先次序?yàn)?-2-3-4-5,現(xiàn)要求其實(shí)際的中斷處理次序?yàn)?-4-5-2-3,回答下面問(wèn)題：(1)設(shè)計(jì)各級(jí)中斷處理程序的中斷級(jí)屏蔽位(令”例應(yīng)于屏蔽，”網(wǎng)應(yīng)于開(kāi)放)；(2)若在運(yùn)行用戶(hù)程序時(shí)，同時(shí)出現(xiàn)第4、2級(jí)中斷請(qǐng)求，而在處理第 2級(jí)中斷未完成時(shí)，又同時(shí)出現(xiàn)第1、3、5級(jí)中斷請(qǐng)求，請(qǐng)畫(huà)出此程序運(yùn)行過(guò)程示意圖。答：(1)各級(jí)中斷處理程序中的中斷級(jí)屏蔽位的設(shè)置，如表3. 2所示。(2)由已知條件可得程序運(yùn)行過(guò)程的示意圖如圖3. 3所示。圖中，粗短線(xiàn)表示交換程序狀態(tài)宇的時(shí)間。表3. 2中斷級(jí)屏蔽位的位置中斷處理程序級(jí)別中斷級(jí)屏敝位1234511

6、1111201100300100401111501100中所請(qǐng)求用戶(hù)飄幅處理期_2_ _3_ _4_ _5_H3.3蜃&3的程朋g行過(guò)程示意圖.設(shè)某程序包含5個(gè)虛頁(yè)，其頁(yè)地址為4,5,3,2,5, 1, 3,2,2,5,1 ,3。當(dāng)使用LRU算法替換時(shí)，為獲得最高的命中率，至少應(yīng)分配給該程序幾個(gè)實(shí)頁(yè)其可能的最高命 中率為多少答：用堆棧對(duì)頁(yè)地址流處理一次的過(guò)程如附表7所示，其中H表示命中。附表7用堆棧對(duì)頁(yè)地址流處理一次的過(guò)程頁(yè)地址流453251322513堆 S(1)453251322251棧 S(2)45325133325內(nèi) S(3)4532511132容 S(4)443255513S(5)4

7、444444S(6)實(shí) n=1H頁(yè) n=2H數(shù) n=3HHn=4HHHHHHHn5HHHHHHH模擬結(jié)果表明，使用LRU替換算法進(jìn)行替換，對(duì)該程序至少應(yīng)分配 4個(gè)實(shí)頁(yè)。如果只分 配3個(gè)實(shí)頁(yè)，其頁(yè)命中率只有 2/12,太低；而分配實(shí)頁(yè)數(shù)多于 4頁(yè)后，其頁(yè)命中率不會(huì) 再有提高。所以，分配給該程序 4個(gè)實(shí)頁(yè)即可，其可能的最高命中率為H=7/12o.有一個(gè)Cache存儲(chǔ)器。主存共分 8個(gè)塊(07), Cache為4個(gè)塊(03),采用組相聯(lián)映像，組內(nèi)塊數(shù)為2塊，替換算法為近期最久未用過(guò)的算法(LRU)(1)畫(huà)出主存、Cache地址的各字段對(duì)應(yīng)關(guān)系(標(biāo)出位數(shù))圖； 畫(huà)出主存、Cache空間塊的映像對(duì)應(yīng)關(guān)系

8、示意圖；(3)對(duì)應(yīng)如下主存塊地址流：1, 2, 4, 1 ,3,7,0,1,2,5, 4, 6,4,7, 2,如主存中內(nèi)容一開(kāi)始未裝入 Cache中，請(qǐng)列出Cache中各塊隨時(shí)間的使用狀況；(4)對(duì)于(3),指出塊失效又發(fā)生塊爭(zhēng)用的時(shí)刻； 對(duì)于(3),求出此期間Cache之命中率。答：(1)主存、Cache地址中各個(gè)字段的含義、位數(shù)及其映像的對(duì)應(yīng)關(guān)系如附圖14所示。 主存、Cache空間塊的映像對(duì)應(yīng)關(guān)系如附圖15所示。主存的第0、1、4、5塊只可映像裝入或替換掉物理Cache中的第0、1塊的內(nèi)容。主存的第2、3、6、7塊只可映像裝入或替換物理Cache中的第2、3塊的內(nèi)容。(3)程序運(yùn)行時(shí)，由

9、給出的主存塊地址流可得到Cache中的各個(gè)塊的使用狀況，如附表13所示，表中標(biāo)”*的是候選替換塊的塊號(hào)。附表13 Cache中的各個(gè)塊的使用情況時(shí)間t123456789101112131415主存塊地址124137012546472Cache塊0111*1111*111*44444144*4*4*00*0*55*5*5*5*5*22222*7777*7*7*666*2333*3*3*2222*2*77*命中情況失失失H失替替H替替替替H替替(4)發(fā)生Cache塊失效又發(fā)生塊爭(zhēng)用的時(shí)刻有 6、7、9、10、11、12、14、15Cache的塊命中率為Hc=3/15=.假設(shè)指令的解釋分取指、分析與

10、執(zhí)行3步，每步的時(shí)間相應(yīng)為t取值、t分析、t執(zhí)行,(1)分別計(jì)算下列幾種情況下，執(zhí)行完100條指令所需時(shí)間的一般關(guān)系式：順序方式；僅”執(zhí)行k與”取值k+1”重疊；僅“執(zhí)行k”、”分析k+1與”取值k+2”。(2)分另1在t取值=t分析=2、t執(zhí)行=1和t取值=t分析=5、t執(zhí)行=2兩種情況下，計(jì)算出上述各結(jié)果。答：分析可先按指令間所要求的時(shí)間關(guān)系畫(huà)出指令間的時(shí)間重疊關(guān)系圖，由圖就可以列 出各種情況下，計(jì)算100條指令所需時(shí)間的一般關(guān)系式。再將給出的時(shí)間值代入，實(shí)際 完成100條指令所需的時(shí)間就可以求得。順序方式工作的時(shí)間關(guān)系如圖 5. 1所示。取指k i分析k :執(zhí)行k ；取指k+1 ;分析k

11、+1 :執(zhí)行k+1；取指k+2分析k+2 ；執(zhí)行k+2 IIIIIIIII圖 順序方式工作的時(shí)間關(guān)系圖僅，執(zhí)行k ”與 取指k+1 ”、重疊方式工作的時(shí)間關(guān)系如圖 5. 2所示.取指k 1分析k 1執(zhí)行k取指k+1 ：分析k+1 ；執(zhí)行k+1取指k+2 ；分析k+2；執(zhí)行k+2圖5. 2 僅“執(zhí)彳Tk ”，與“取指k+1 ”重疊方式工作的時(shí)間關(guān)系圖僅 啾行k ”、 “分析k+1 ”、 “取指k+2 ”重疊方式工作的時(shí)間關(guān)系如圖5. 3所示.取指k+1 ；分析k+1 ；執(zhí)行k+1取指k+2 :分析k+2 :執(zhí)行k+2圖5. 3 僅執(zhí)彳k ”、 吩析k+1 ”、 “取指k+2 ”重疊方式工作的時(shí)間

12、關(guān)系圖(1)計(jì)算執(zhí)行完100條指令所需要的時(shí)間：(i)順序方式工作時(shí)為100 (t取指t分析t執(zhí)行)(ii)僅“執(zhí)行k ”，與“取指k+1 ”重疊方式工作時(shí)為t取指100t分析99 max t取指，t執(zhí)行t執(zhí)行(iii)僅執(zhí)行k 、吩析k+1 ”、 “取指k+2 ”重疊方式工作時(shí)為t取指max t分析,t取指 98 max t取指,t分析,t執(zhí)行max t執(zhí)行，t分析t執(zhí)行當(dāng),取指=t分析=2、t執(zhí)行=l時(shí)，代入上面的各式，可求得 100條指令執(zhí)行所 需要的時(shí)間是：順序方式工作時(shí)為500。僅“執(zhí)行k ”，與“取指k+1 ”重疊方式工作時(shí)為401。僅“執(zhí)行k ”、“分析k+1 ”、取指k+2 ”

13、重疊方式工作時(shí)為203。當(dāng)t取指=t執(zhí)行=5, t分析 =2,代入上面的各式，可求得100條指令執(zhí)行所需 要的時(shí)間是：順序方式工作時(shí)為1200。僅“執(zhí)行k ”，與“取指k+1 ”重疊方式工作時(shí)為 705。僅“執(zhí)行k ”、 吩析k+1 ”、 “取指k+2 ”重疊方式工作時(shí)為510。.在一個(gè)5段的流水線(xiàn)處理機(jī)上需經(jīng) 9拍才能完成一個(gè)任務(wù)，其預(yù)約表如表 54所示。 表5 49拍才能完成一個(gè)任務(wù)的預(yù)約表間段、t。t1t2t3t4t5t6t7t8S1SS3與S分別寫(xiě)出延遲禁止表 F、沖突向量C;畫(huà)出流水線(xiàn)狀態(tài)轉(zhuǎn)移圖；求出最小平均延遲及流水線(xiàn)的最大吞吐率及其調(diào)用方案。按此流水調(diào)度方案輸入6個(gè)任務(wù)，求實(shí)際吞吐率。答：對(duì)預(yù)約表中各個(gè)行中打”的拍數(shù)求出差值，并將這些差值匯集在一起， 就可得到延遲禁止表：F=1, 3, 4, 8由延遲禁止表F可轉(zhuǎn)換得初始沖突向量 C=