計算機系統(tǒng)結構期末重點題目及考點

1、計算機系統(tǒng)結構期末重點題目及考點第1章 ：.2.如有一個經解釋實現(xiàn)的計算機,可以按功能劃分成4級。每一級為了執(zhí)行一條指令需要下一級的n條指令解釋，若執(zhí)行第一級的一條指令需kns，那執(zhí)行第2級、第3級、第4級的指令需要多少時間？第1級 1條級指令 k ns第級 1條2級指令 n條1級指令 1nk n = k ns第3級 1條3級指令 n條級指令 1nn ns n2k s第4級 條4級指令 n條3級指令 1nn s = 3k s18.從機器（匯編）語言程序員看，以下哪些是透明的？n 指令地址寄存器;指令緩沖器;時標發(fā)生器；條件碼寄存器;乘法器;主存地址寄存器；磁盤外設；先行進位鏈；移位器;通用寄存

2、器；中斷字寄存器。見下表，“”為透明性概念指令地址寄存器，,指令緩沖器,，時標發(fā)生器,條件碼寄存器,，乘法器，主存地址寄存器，,磁盤，,先行進位鏈,移位器，,通用寄存器 ,中斷字寄存器，,第2章 :.2在尾數(shù)采用補碼、小數(shù)表示且p=,階碼采用移碼、整數(shù)表示且q=6，尾數(shù)基rm為16，階碼基re為2的情況下：(1)最大尾數(shù)為：1-m-=1-16-,0.ffffff(2) 最小正尾數(shù)為:1rm=1/1,01000(3)最小尾數(shù)為：-1,.00000(4) 最大負尾數(shù)為:-（rm-1+ rm)=（16-1+ 16-6)，effff(5) 最大階碼為:req1616，7，包括符號位共7個1(6） 最小

3、階碼為:-req=26-64,，包括符號位共7個0(7）最大正數(shù)為：（11-6)166,7fffff(8)最小正數(shù)為:1665，010000（) 最大負數(shù)為：(6- + 16-) 1664,80fffff（10）最小負數(shù)為:13,ff000000() 浮點零為:0000(12) 表數(shù)精度為:165/2=2-11) 表數(shù)效率為:15/16=975（14)能表示的規(guī)格化浮點數(shù)個數(shù)為：25162+12.13 一個處理機共有10條指令,各指令在程序中出現(xiàn)的概率如下表:指令信號 出現(xiàn)概率 hfman編砝碼 2擴展編砝碼 3/擴展編砝碼i1 0.25 0 0 00i .2 1 013 .15 001 10

4、0 14 0.10 1001 11i5 0.08 0000 1010 1101i6 0. 1001 01 110107 00 1000 110 101i 0.04 0001 111 11109 00 00010 110 1110i 0.02 0100 1111 1100已知10條指令使用頻度,求種編碼方法的平均碼長與信息冗余量。()此問中的“最優(yōu)uffma編碼法”實際是指碼長下限,即信源的平均信息量熵，代公式得h=2956。(2）uffa編碼性能如下表；(3)2/8擴展編碼是/64512法的變種，第一組條指令,碼長為（位擴展標志,1位編碼）,第二組8條指令，碼長為4（1位擴展標志,與第一組區(qū)別

5、，加位編碼）,編碼性能如下表;(4)3/7擴展編碼是15/15/15法的變種，第一組3條指令,碼長為2（共有4種組合，其中3種組合分別代表條指令，留1種組合作為擴展前綴標志),第二組7條指令,碼長為5(2位固定的前綴擴展標志,與第一組區(qū)別,加3位編碼,只用其中7種組合），編碼性能如下表。hufman編碼擴展編碼3/擴展編碼平均碼長l2993.1.信息冗余量r1.0%4.61%79%2.1一臺模型機共有7條指令，各指令的使用頻率分別為%，25%,20%,1%，5%,3和2%,有8個通用數(shù)據寄存器，2個變址寄存器。()要求操作碼的平均長度最短，請設計操作碼的編碼,并計算所設計操作碼的平均長度。(2

6、）設計8字長的寄存器-寄存器型指令條,1位字長的寄存器-存儲器型變址尋址方式指令4條，變址范圍不小于17。請設計指令格式,并給出各字段的長度和操作碼的編碼。解:(1）要使得到的操作碼長度最短,應采用huffan編碼，構造ffman樹如下:由此可以得到7條指令的編碼分別如下：這樣，采用huffma編碼法得到的操作碼的平均長度為： = 2(035+025+0.0) 3010 + .05 5(0 +0.0) =1+.+0.2+0.5 =25()設計位字長的寄存器-寄存器型變址尋址方式指令如下,因為只有個通用寄存器，所以寄存器地址需位，操作碼只有兩位,設計格式如下:三條指令的操作碼分別為0,10設計1

7、6位字長的寄存器-存儲器型變址尋址方式指令如下:四條指令的操作碼分別為1100，11,1110,11125某處理機的指令字長為16位,有雙地址指令、單地址指令和零地址指令三類,并假設每個地址字段的長度均為6位。(1)如果雙地址指令有15條,單地址指令和零地址指令的條數(shù)基本相同，問單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。（2)如果要求三類指令的比例大致為1:9,問雙地址指令、單地址指令和零地址指令各有多少條?并且為這三類指令分配操作碼。解:(）15條/63條/6條(2) 14條2條128條()根據指令地址的數(shù)量來決定各種指令在指令空間上的分布:如果我們按照從小到大的順序分配

8、操作碼,這樣，按照指令數(shù)值從小到大的順序，分別為雙地址指令、單地址指令和零地址指令。其次可以根據指令的條數(shù)來大致的估計操作碼的長度:雙指令1條，需要4位操作碼來區(qū)分，剩下的1位操作碼平均分給單地址和零地址指令，每種指令可以用6位操作碼來區(qū)分，這樣,各指令的條數(shù)為:雙地址指令5條，操作碼：0001110；單地址指令26-=6條,操作碼：110000011 11110；零地址指令6條，操作碼：1111 11111 0000111111 1111。 (2)與上面的分析相同,可以得出答案：雙地址指令4條,操作碼:000111;單地址指令2 x 2-2 = 126條，111 000000110 1111

9、1,111100000111111111;零地址指令128條11011111000001 1111111,111 111 00000011 111111 11111（2）b雙地址指令同上，1條，操作碼:00001;單地址指令4 + 6 126條，64 條單地址指令操作碼1110000001110 11111,6 條單地址指令操作碼111100000011111;零地址指令128條111111000000110 11111011111,1111 1111 000111 111111 11111第3章 :3.9 :一個頁式虛擬存儲器的虛存空間大小為4b,頁面大小為4k，每個頁表存儲子要占用個字節(jié)。

10、（1） 計算這個頁式虛擬存儲器需要采用幾級頁表？答:log2(4g/4)lg2(4k/4)=2.0取整得2,所以需要級頁表（2） 如果要求頁表所占用的總主存頁面數(shù)最小,請分配每一級頁表的實際存儲容量各為多少字節(jié)?答:第一季頁表為一個頁面大小，為kb,第二級頁表被占用1個頁面，為4b（3） 頁表的哪些部分必須存放在主存中？哪些可以放在輔存中？答：第一級頁表必須放在主存中,二級頁表只需將正在運行的程序的相關頁表放在主存中,其他都可以放在輔存中。3.12 一個有快表和慢表的頁式虛擬存儲器，最多有64個用戶，每個用戶最多要用1024個頁面，每頁4k字節(jié)，主存容量8m字節(jié)。()寫出多用戶虛地址的格式,并

11、標出各字段的長度。(2)寫出主存地址的格式,并標出各字段的長度。(3)快表的字長為多少位？分幾個字段？各字段的長度為多少位?（）慢表的容量是多少個存儲字？每個存儲字的長度為多少位？答：用戶號：26,虛頁號：1024=210，頁內地址：4k=212,主存頁數(shù)：8/4k21（1)多用戶虛地址:用戶號(位）虛頁號(0位）+頁內地址(2位）共28位（2)主存地址:主存實頁號（11位）頁內地址（12位)共3位（3） 快表字長7位;分3個字段：用戶號6位，虛頁號10位,實頁號11位（4） （4）慢表容量為2(6+1),每個存儲字長為：主存頁號+11位。.1.在頁式虛擬存儲器中，一個程序由p5共5個虛頁組成

12、。在程序執(zhí)行過程中依次訪問到的頁面如下:p ,p3，p，p1，p5 ,p2 ，p4 ，p5 ,p3 ，p，p ,2 假設系統(tǒng)分配給這個程序的主存有個頁面,分別采用fo、lu和opt三種替換算法對這三頁主存進行調度。（1)畫出主存頁面調入、替換和命中的情況表。()統(tǒng)計三種頁面替換算法的頁命中率。答案：解:三種替換算法的替換過程：頁地址流 3 21 5 24 5 2 5 fifo 22 25 5 3 3 3命中3次 3 3 3 3 22 51 1 4 4 4 4 2調調 命 調 替 替 替 命 替 命 替 替進 進 中 進 換 換 換 中 換 中 換換2 2 1 52 4 5 2ru33 1 5

13、5 3 25命中5次 3 2 1 5 2 5 3調 調命 調 替 命 替命替替 命 命進進 中進 換中 換 中 換換 中 中pt2 2 2 22 2 4 4 4 2 2 命中次3 3 33 3 3 31 5 55 55 5 5調調 命 調 替 命 替 命命替 命 命進 進 中 進 換 中 換 中 中 換 中 中3.15.一個程序由五個虛頁組成，采用lfu替換算法，在程序中依次訪問的頁地址流如下：p4,5，p3，p,p5，1,3，2,p3,p5，p1,p3(1) 可能的最高頁命中率是多少?(2) 至少要分配給該程序多少個主存頁面才能獲得最高的命中率?(3) 如果在程序中每訪問一個頁面，平均要對該

14、頁面內的存儲單元訪問104次,求訪問單元的命中率?答案:(1)在分配的主存頁面數(shù)目大于等于5的情況下，這時,除了第一次調入不命中,以后的訪問均命中，可以達到最高的頁面命中率：實際命中的次數(shù)為7次，所以可能達到的最高頁面命中率為:（)由于在頁面數(shù)大于等于5的情況下,肯定可以達到最高命中率,所以我們來看頁面數(shù)小于5時能否達到該命中率：分配的主存頁面數(shù)等于4時,調度過程如下: lfu算法44444*11111*11命中7次555*55555*5553333*33*333*32222*22222調入調入調入調入命中調入命中命中命中命中命中命中此時也可以達到最高命中率;分配的主存頁面等于3時，調度過程如

15、下： lfu算法444*222*33*333*3命中3次555*555*222*11333*1111*555調入調入調入調入命中調入調入調入命中調入調入命中此時不能達到最高命中率。所以至少應該分配個主存頁面。（3) 我們假設程序每次只訪問一個存儲單元，這樣，對每一個特定頁面的訪問過程可以描述如下:因為第一次總是不命中的，而平均起來，隨后的13次總是命中的,然后再次被調出主存,并再次重復先前的過程。所以訪問存儲單元的命中率為:欲知可能的最高命中率及所需的最少主存頁數(shù),較好的辦法是通過“堆棧模擬法”,求得命中次數(shù)隨主存頁數(shù)變化的函數(shù)關系。下圖就是“堆棧模擬圖”，其中“”表示命中。p53251325

16、13命中次數(shù)4352354532513345112354212444n=1n=1n3n=57(1)hax=7/1258.%(2)n=4(）當1次頁面訪問代表連續(xù)14次該頁內存儲單元訪問時,后2次單元訪問肯定是命中的,而第1次單元訪問的命中情況與這1次頁面訪問的命中情況相同。根據上圖中最高命中情況,共有7次頁命中(折算為24次單元命中），次頁不命中(折算為5103次單元命中，也可寫為102-5），單元訪問總次數(shù)為210,故有:hell=(121024-）/(11024）=2282288996%3.16一個程序由1200條指令組成,每條指令的字長均為4b。假設這個程訪問虛擬存儲器的字地址流為:12

17、,40，260,280,10,80，500,560，60，110，20,10。采用ffo替換算法，分配給這個程序的主存容量為2048b。在下列不同的頁面大小情況下,分別寫出該程序執(zhí)行過程中訪存的虛頁地址流,并分別計算主存命中率。(1)頁的大小為102。（2)頁的大小為51b。()頁的大小為2048b。解：(1)（分)頁的大小為124，即頁面大小為26字；主存容量為04b，即分配=個實頁。給定的程序訪存字地址流對主存空間的使用過程如圖所示。主存命中率h1=612=0.50(2) (分）頁的大小為512b，即頁面大小為128字;主存容量為2048b,即分配n=個實頁。給定的程序訪存字地址流對主存空

18、間的使用過程如圖所示。主存命中率為h2=/12=02(3) 頁的大小為208，即頁面大小為2字，主存容量為20b,即分配n=個實頁。給定的程序訪存字地址流對主存空間的使用過程如圖所示。主存命中率為h3=/1=053.19在一個采用組相聯(lián)映象方式的cache存儲系統(tǒng)中,主存由b0共塊組成,cche有2組,每組2塊,每塊大小為16b。在一個程序執(zhí)行過程中，訪存的主存塊地址流為:b,b2，4,b1，b4,b,b3，0,b,b5，b7，。(1）寫出主存地址的格式，并標出各字段的長度。(2)寫出cache地址的格式，并標出各字段的長度。（)指出主存與cche之間各個塊的映象關系。()若cahe的4個塊號

19、為c0、1、2和3,列出程序執(zhí)行過程中的cache塊地址流。(5)若采用ffo替換算法，計算cache的塊命中率。(6)若采用lu替換算法,計算cahe的塊命中率。(7)若改為全相聯(lián)映象方式,再做(5)和(6）。（8)若在程序執(zhí)行過程中，每從主存裝入一塊到ache，平均要對這個塊訪問6次,計算在這種情況下的ch命中率。答案：解:(1)（2)采用組相聯(lián)映象時,主存和cahe地址的格式分別為:主存按cach的大小分區(qū),現(xiàn)主存有個塊,cace有24個塊,則主存分為8/42個區(qū),區(qū)號e的長度為1位。又每區(qū)有2個組,則組號g、g的長度都為1位。而每組有個塊,則塊號、b的長度又都為1位。每塊大小為個存儲字

20、,故塊內地址w、的長度都為4位。(）根據組相聯(lián)映象的規(guī)則,主存塊7與ce塊03之間的映象關系為:主存塊0、1、4、5與ach塊0、1之間全相聯(lián)，主存塊2、3、7與cch塊2、3之間全相聯(lián)。（4）根據組相聯(lián)映象的規(guī)則,該主存塊地址流相應的一種cache塊地址流如下表所示(組內替換算法為fif）。時間：12367810112主存塊地址流：bbb4b1b4b6b30bb5bb3ache塊地址流:230c1cc2c2c0c0c（5)組內替換算法采用fo時，cae塊的使用過程如下表所示。時間：1235679012主存塊地址流：64b1b4b3b0b4bb7b3cah塊0ache塊1ch塊2cche塊3命

21、中命中命中可見命中三次，cache塊命中率為h=3/120.25。（6） 組內替換算法采用lru時，ach塊03的使用過程如下表所示。時間：2567112主存塊地址流：b2b4b1b46bb0b45b7b3ah塊0ah塊1cache塊cache塊命中命中命中命中可見命中四次,che塊命中率為hi=42=0.33。（7） 全相聯(lián)映象的規(guī)則是主存塊7可裝入cache塊0的任一塊上。當替換算法采用fifo時,cache塊03的使用過程如下表所示。時間:2345671012主存塊地址流：b6b2b4b1b4b6b3b0bb5b7b3cache塊cche塊1cah塊ahe塊3命中命中命中命中可見命中四次

22、,cach塊命中率為i=4120.33。當替換算法采用r時，ch塊0的使用過程如下表所示。時間：1345678901112主存塊地址流：bbb4b1b4b6b3bb45b7塊0cache塊1cahe塊2ch塊命中命中命中可見命中三次,cace塊命中率為h/1=0.25。（8)當命中三次時，cach的命中率為hi=(1216-9）/(1216）1,當命中四次時,che的命中率為（12168）/（1216)1。.0.23對于一個采用組相聯(lián)映象方式和fio替換算法的cach,發(fā)現(xiàn)它的等效訪問時間太長，為此，提出如下建議:（1） 增大主存的容量。答案:基本無關（2） (2)提高主存的速度。 答案：能夠

23、減小等效訪問時間，=tch+tm(-h）,通過減小t能夠減小t。（3） （3）增大ahe的容量答案:當cche比較小時,增大ache對減少等效訪問時間效果明顯;當cach容量達到一定程度時效果逐漸不明顯。（4） （)提高cce的速度。（5） che的總容量和組大小不變,增大塊的大小。（6） （6）cace的總容量和塊大小不變,增大組的大小。答案:有一個極大值，在這個極大值點,等效訪問時間最小。（7） (7）ace的總容量和塊大小不變,增加組數(shù)。（8） (）替換算法由io改為lfu第4章 ：.4有5個中斷源d1、2、d3、d4和d，它們的中斷優(yōu)先級從高到低依次是1-5級別。這些中斷源的中斷優(yōu)先級

24、、正常情況下的中斷屏蔽碼和改變后的中斷屏蔽碼如下表所示。每個中斷源有5位中斷屏蔽碼，其中0表示該中斷源開放，1表示該中斷源被屏蔽。(1)當使用正常的中斷屏蔽碼時，處理器響應各中斷源的中斷請求的先后順序是什么?實際上中斷處理的先后次序是什么?(2）當使用改變后的中斷屏蔽碼時，處理器響應各中斷源的中斷請求的先后順序是什么？實際上中斷處理的先后次序是什么？（3）如果采用改變后的中斷屏蔽碼，、d2、d、d和d5同時請求中斷時，畫出處理器響應各中斷源的中斷請求和實際運行中斷服務程序過程的示意圖。答案：（1)當使用正常的中斷屏蔽碼時,處理器響應各中斷源的中斷請求的先后順序是d1、2、3、d4、5。實際上中

25、斷處理的先后次序是d、d、d3、4、5。（2)當使用改變后的中斷屏蔽碼時，處理器響應各中斷源的中斷請求的先后順序是d1、d2、d3、d4、d5。實際上中斷處理的先后次序是d4、d、d3、d2、d1。(3) 如果采用改變后的中斷屏蔽碼，d、2、d3、d4和d同時請求中斷時,處理器響應各中斷源的中斷請求和實際運行中斷服務程序過程如下圖所示：4.某處理機共有4個中斷源,分別為d1、2、d3、d4,要求處理機響應中斷源的中斷服務請求的次序從高到低分別是1、d、d3、,而處理機實際為各中斷源服務的先后次序為3，d3,d4,d1.每個中斷源有4位中斷屏蔽碼，其中,表示該中斷源被屏蔽,表示該中斷源開放。已知

26、中斷服務次序為3-4-1，。（1)中斷屏蔽字表如下圖;d1d2d4d11d000d3000401(）中斷過程示意圖如右圖。時間 中斷請求主程序1級 2級 級 級 d，2 d3，d44.74.一個字節(jié)多路通道連接有4臺外圍設備,每臺設備發(fā)出輸入輸出服務請求的時間間隔,他們的服務優(yōu)先級和發(fā)出第一次服務請求的時刻表如下:設備名稱d1dd3d4發(fā)服務請求間隔107555服務優(yōu)先級1423發(fā)第一次請求時刻0s70s2s(1）計算這個字節(jié)多路通道的實際流量和工作周期(2）在數(shù)據傳送期間，如果通道選擇一次設備的時間為3s,傳送一個字節(jié)的時間為s,畫出這個字節(jié)多路通道響應各設備請求和為設備服務的時間關系圖。(

27、1)f=1字節(jié)秒，t5us(2)tt=5u,通道時間圖如下。作圖時注意:至少要畫到最慢設備的第二次請求出現(xiàn)，才能確定是否丟失數(shù)據(因為響應優(yōu)先級低的設備較易丟失數(shù)據)。設優(yōu)備先號級d d2 4d3 d 3時間(us) 0 1 20 30 40 5 60 70 0 90 100 10 120 130 140 10 160 70(3)5，10,20，0;(4)d2丟失第一次請求的數(shù)據;()參見p24。第5章 :5.8用一條5個功能段的浮點加法器流水線計算每個功能段的延遲時間均相等,流水線的輸出端和輸入端之間有直接數(shù)據通路，而且設置有足夠的緩沖寄存器。要求用盡可能短的時間完成計算，畫出流水線時空圖，并計算流水線的實際吞吐率、加速比和效率。解答 首先需要考慮的是，個數(shù)的的和最少需要做幾次加法。我們可以發(fā)現(xiàn),加法的次數(shù)是不能減少的:9次;于是我們要盡可能快的完成任務,就只有考慮如何讓流水線盡可能充滿,這需要消除前后指令之間的相關。由于加法滿足交換率和結合率，我們可以調整運算次序如以下的指令序列,我們把中間結果寄存器稱為r,源操作數(shù)寄存器稱為a,最后結