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

1、第1章 ：1.2.如有一個經解釋實現的計算機，可以按功能劃分成4級。每一級為了執(zhí)行一條指令需要下一級的N條指令解釋，若執(zhí)行第一級的一條指令需kns，那執(zhí)行第2級、第3級、第4級的指令需要多少時間？第1級 1條1級指令 k ns第2級 1條2級指令 N條1級指令 1·N·k ns = Nk ns第3級 1條3級指令 N條2級指令 1·N·N·k ns = N2k ns第4級 1條4級指令 N條3級指令 1·N·N·N·k ns = N3k ns1.8.從機器（匯編）語言程序員看，以下哪些是透明的？n 指令地

2、址寄存器；指令緩沖器；時標發(fā)生器；條件碼寄存器；乘法器；主存地址寄存器；磁盤外設；先行進位鏈；移位器；通用寄存器；中斷字寄存器。見下表，“”為透明性概念指令地址寄存器，×，指令緩沖器，時標發(fā)生器，條件碼寄存器，×，乘法器，主存地址寄存器，磁盤，×，先行進位鏈，移位器，通用寄存器 ，×，中斷字寄存器，×，第2章 ：2.2 在尾數采用補碼、小數表示且p=6，階碼采用移碼、整數表示且q=6，尾數基rm為16，階碼基re為2的情況下：(1) 最大尾數為：1rm-p116-6，0.FFFFFF(2) 最小正尾數為：1/rm1/16，0.100000(3)

3、 最小尾數為： -1， 1.000000(4) 最大負尾數為：-(rm-1 + rm-p)(16-1 + 16-6)，1.EFFFFF(5) 最大階碼為：req126163，7F，包括符號位共7個1(6) 最小階碼為：-req-26-64，00，包括符號位共7個0(7) 最大正數為：(116-6)1663，7FFFFFFF(8) 最小正數為：16-65，00100000(9) 最大負數為：-(16-1 + 16-6) 16-64，80EFFFFF(10) 最小負數為：-1663，FF000000(11) 浮點零為：00000000(12) 表數精度為：16-5/22-2113) 表數效率為：1

4、5/1693.75(14) 能表示的規(guī)格化浮點數個數為：2×15×165×27+12.13 一個處理機共有10條指令，各指令在程序中出現的概率如下表：指令信號  出現概率  Huffman編砝碼  2/8擴展編砝碼  3/7擴展編砝碼I1 0.25 01 00 00I2 0.20 11 01 01I3 0.15 001 1000 10I4 0.10 101 1001 11000I5 0.08 0000 1010 11001I6 0.08 1001 1011 11010I7 0.05 1000 1100 11011I8 0.0

5、4 00011 1101 11100I9 0.03 000101 1110 11101I10 0.02 000100 1111 111100已知10條指令使用頻度，求3種編碼方法的平均碼長與信息冗余量。(1)此問中的“最優(yōu)Huffman編碼法”實際是指碼長下限，即信源的平均信息量熵，代公式得H=2.9566。(2)Huffman編碼性能如下表；(3)2/8擴展編碼是8/64/512法的變種，第一組2條指令，碼長為2（1位擴展標志，1位編碼）,第二組8條指令，碼長為4（1位擴展標志，與第一組區(qū)別，加3位編碼），編碼性能如下表；(4)3/7擴展編碼是15/15/15法的變種，第一組3條指令，碼長為

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

7、器型變址尋址方式指令4條，變址范圍不小于±127。請設計指令格式，并給出各字段的長度和操作碼的編碼。解：(1)要使得到的操作碼長度最短，應采用Huffman編碼，構造Huffman樹如下：由此可以得到7條指令的編碼分別如下：這樣，采用Huffman編碼法得到的操作碼的平均長度為：H = 2×(0.35+0.25+0.20) + 3×0.10 + 4 ×0.05 + 5×(0.03 + 0.02) = 1.6+0.3+0.2+0.25 =2.35(2)設計8位字長的寄存器-寄存器型變址尋址方式指令如下，因為只有8個通用寄存器，所以寄存器地址需3位

8、，操作碼只有兩位，設計格式如下：三條指令的操作碼分別為00，01，10設計16位字長的寄存器-存儲器型變址尋址方式指令如下：四條指令的操作碼分別為1100，1101，1110，11112.15某處理機的指令字長為16位，有雙地址指令、單地址指令和零地址指令三類，并假設每個地址字段的長度均為6位。(1)如果雙地址指令有15條，單地址指令和零地址指令的條數基本相同，問單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。(2)如果要求三類指令的比例大致為1：9：9，問雙地址指令、單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。解：(1) 15條/63條/64條(2) 14條/

9、126條/128條(1)根據指令地址的數量來決定各種指令在指令空間上的分布：如果我們按照從小到大的順序分配操作碼，這樣，按照指令數值從小到大的順序，分別為雙地址指令、單地址指令和零地址指令。其次可以根據指令的條數來大致的估計操作碼的長度：雙指令15條，需要4位操作碼來區(qū)分，剩下的12位操作碼平均分給單地址和零地址指令，每種指令可以用6位操作碼來區(qū)分，這樣，各指令的條數為：雙地址指令15條，操作碼：00001110；單地址指令26-1=63條，操作碼：1111 0000001111 111110；零地址指令64條，操作碼：1111 111111 0000001111 111111 111111。

10、 (2)與上面的分析相同，可以得出答案：雙地址指令14條，操作碼：00001101；單地址指令26 x 2-2 = 126條，1110 0000001110 111110，1111 0000001111 111110；零地址指令128條1110 111111 0000001110 111111 111111,1111 111111 0000001111 111111 111111(2)B雙地址指令同上,14條，操作碼：00001101；單地址指令64 + 62 = 126條，64 條單地址指令操作碼1110 0000001110 111111，62 條單地址指令操作碼1111 00000011

11、11 111101；零地址指令128條1111 111110 0000001110 111110 111111,1111 111111 0000001111 111111 111111第3章 ：3.9 ：一個頁式虛擬存儲器的虛存空間大小為4Gb，頁面大小為4KB，每個頁表存儲子要占用4個字節(jié)。（1） 計算這個頁式虛擬存儲器需要采用幾級頁表？答：Log2（4G/4K）/Log2（4K/4）=2.0.取整得2，所以需要2級頁表（2） 如果要求頁表所占用的總主存頁面數最小，請分配每一級頁表的實際存儲容量各為多少字節(jié)？答：第一季頁表為一個頁面大小，為4kb，第二級頁表被占用1k個頁面，為4mb（3）

12、頁表的哪些部分必須存放在主存中？哪些可以放在輔存中？答：第一級頁表必須放在主存中，二級頁表只需將正在運行的程序的相關頁表放在主存中，其他都可以放在輔存中。3.12 一個有快表和慢表的頁式虛擬存儲器，最多有64個用戶，每個用戶最多要用1024個頁面，每頁4K字節(jié)，主存容量8M字節(jié)。 （1）寫出多用戶虛地址的格式，并標出各字段的長度。 （2）寫出主存地址的格式，并標出各字段的長度。 （3）快表的字長為多少位？分幾個字段？各字段的長度為多少位？ （4）慢表的容量是多少個存儲字？每個存儲字的長度為多少位？  答：用戶號：6426，虛頁號：10

13、24210，頁內地址：4K212，主存頁數：8M/4K211 （1）多用戶虛地址：         用戶號（6位）虛頁號（10位）頁內地址（12位）                 共28位 （2）主存地址：         &#

14、160;主存實頁號（11位）頁內地址（12位）      共23位 （3） 快表字長27位；分3個字段：用戶號6位，虛頁號10位，實頁號11位 （4） （4）慢表容量為2(6+10)，每個存儲字長為：主存頁號112位。3.143.14在頁式虛擬存儲器中，一個程序由P1P5共5個虛頁組成。在程序執(zhí)行過程中依次訪問到的頁面如下： P2 ，P3，P2，P1 ，P5 ，P2 ，P4 ，P5 ，P3 ，P2 ，P5 ，P2 假設系統(tǒng)分配給這個程序的主存有3個頁面，分別采用FIFO、LRU和OPT三種替換算法對這三頁主存進行調

15、度。（1）畫出主存頁面調入、替換和命中的情況表。（2）統(tǒng)計三種頁面替換算法的頁命中率。答案：解：三種替換算法的替換過程：頁地址流 2 3 2 1 5 2 4 5 3 2 5 2FIFO 2 2 2 2 5 5 5 5 3 3 3 3命中3次 3 3 3 3 2 2 2 2 2 5 51 1 1 4 4 4 4 4 2調 調 命 調 替 替 替 命 替 命 替 替進 進 中 進 換 換 換 中 換 中 換 換2 2 2 1 5 2 4 5 3 2 5 2LRU 3 3 2 1 5 2 4 5 3 2 5命中5次 3 2 1 5 2 4 5 3 3調 調 命 調 替 命 替 命 替 替 命 命進

16、進 中 進 換 中 換 中 換 換 中 中OPT 2 2 2 2 2 2 4 4 4 2 2 2命中6次 3 3 3 3 3 3 3 3 3 3 31 5 5 5 5 5 5 5 5 5調 調 命 調 替 命 替 命 命 替 命 命進 進 中 進 換 中 換 中 中 換 中 中3.15.一個程序由五個虛頁組成，采用lfu替換算法，在程序中依次訪問的頁地址流如下：P4，P5，P3，P2，P5，P1，P3，P2，P3，P5，P1，P3(1) 可能的最高頁命中率是多少？(2) 至少要分配給該程序多少個主存頁面才能獲得最高的命中率?(3) 如果在程序中每訪問一個頁面，平均要對該頁面內的存儲單元訪問10

17、24次，求訪問單元的命中率？答案：（1）在分配的主存頁面數目大于等于5的情況下，這時，除了第一次調入不命中，以后的訪問均命中，可以達到最高的頁面命中率：實際命中的次數為7次，所以可能達到的最高頁面命中率為：（2）由于在頁面數大于等于5的情況下，肯定可以達到最高命中率，所以我們來看頁面數小于5時能否達到該命中率：分配的主存頁面數等于4時，調度過程如下： LFU算法44444*11111*11命中7次 555*55555*555  3333*33*333*3   2222*22222調入調入調入調入命中調入命中命中命中命中命中命中此時也可

18、以達到最高命中率；分配的主存頁面等于3時，調度過程如下： LFU算法444*222*33*333*3命中3次 555*555*222*11  333*1111*555調入調入調入調入命中調入調入調入命中調入調入命中此時不能達到最高命中率。所以至少應該分配4個主存頁面。（3) 我們假設程序每次只訪問一個存儲單元，這樣，對每一個特定頁面的訪問過程可以描述如下：因為第一次總是不命中的，而平均起來，隨后的1023次總是命中的，然后再次被調出主存，并再次重復先前的過程。所以訪問存儲單元的命中率為： 欲知可能的最高命中率及所需的最少主存頁數，較好的辦法是通過“堆棧模擬法”，求

19、得命中次數隨主存頁數變化的函數關系。下圖就是“堆棧模擬圖”，其中“”表示命中。P=453251323513命中次數4532513235134532513235145325112354432551224444444n=10n=21n=33n=47n=57(1)Hmax=7/1258.3%(2)n=4(3)當1次頁面訪問代表連續(xù)1024次該頁內存儲單元訪問時，后1023次單元訪問肯定是命中的，而第1次單元訪問的命中情況與這1次頁面訪問的命中情況相同。根據上圖中最高命中情況，共有7次頁命中（折算為7×1024次單元命中），5次頁不命中（折算為5×1023次單元命中，也可寫為5&#

20、215;1024-5），單元訪問總次數為12×1024，故有：Hcell=(12×1024-5)/(12×1024)=12283/1228899.96%3.16.一個程序由1200條指令組成，每條指令的字長均為4B。假設這個程訪問虛擬存儲器的字地址流為：12，40，260，280，180，800，500，560，600，1100，1200，1000。采用FIFO替換算法，分配給這個程序的主存容量為2048B。 在下列不同的頁面大小情況下，分別寫出該程序執(zhí)行過程中訪存的虛頁地址流，并分別計算主存命中率。 (1) 頁的大小為1024B。&

21、#160;   (2) 頁的大小為512B。      (3) 頁的大小為2048B。     解：(1) （6分）頁的大小為1 024B，即頁面大小為256字；主存容量為2048B，即分配n=2個實頁。給定的程序訪存字地址流對主存空間的使用過程如圖所示。主存命中率H1=612 = 050  (2)  （8分）頁的大小為512B，即頁面大小為128字；主存容量為2&#

22、160;048B，即分配n=4個實頁。給定的程序訪存字地址流對主存空間的使用過程如圖所示。主存命中率為H2 = 312 = 025(3)  頁的大小為2048B，即頁面大小為512字，主存容量為2048B，即分配n=1個實頁。給定的程序訪存字地址流對主存空間的使用過程如圖所示。主存命中率為H3 = 612 = 0503.19 在一個采用組相聯映象方式的Cache存儲系統(tǒng)中，主存由B0B7共8塊組成，Cache有2組，每組2塊，每塊大小為16B。在一個程序執(zhí)行過程中，訪存的主存塊地址流為：B6，B

23、2，B4，B1，B4，B6，B3，B0，B4，B5，B7，B3。 (1)寫出主存地址的格式，并標出各字段的長度。 (2)寫出Cache地址的格式，并標出各字段的長度。 (3)指出主存與Cache之間各個塊的映象關系。 (4)若Cache的4個塊號為C0、C1、C2和C3，列出程序執(zhí)行過程中的Cache塊地址流。 (5)若采用FIFO替換算法，計算Cache的塊命中率。 (6)若采用LRU替換算法，計算Cache的塊命中率。 (7)若改為全相聯映象方式，再做(5)和(6)。 (8)若在程序執(zhí)行過程中，每從主存裝入一塊

24、到Cache，平均要對這個塊訪問16次，計算在這種情況下的Cache命中率。答案：解：（1）（2）采用組相聯映象時，主存和Cache地址的格式分別為：       主存按Cache的大小分區(qū)，現主存有8個塊，Cache有2×2=4個塊，則主存分為8/4=2個區(qū)，區(qū)號E的長度為1位。又每區(qū)有2個組，則組號G、g的長度都為1位。而每組有2個塊，則塊號B、b的長度又都為1位。每塊大小為16個存儲字，故塊內地址W、w的長度都為4位。     （3）根據組相聯映象的規(guī)則，主存

25、塊07與Cache塊03之間的映象關系為：主存塊0、1、4、5與Cache塊0、1之間全相聯，主存塊2、3、6、7與Cache塊2、3之間全相聯。     （4）根據組相聯映象的規(guī)則，該主存塊地址流相應的一種Cache塊地址流如下表所示（組內替換算法為FIFO）。 時間：  1    2    3    4    5   

26、60;6    7    8    9    10    11   12 主存塊地址流：  B6   B2    B4   B1    B4   B6 

27、0;  B3   B0    B4   B5     B7    B3 Cache塊地址流：  C2   C3    C0   C1    C0   C2   

28、 C2   C0    C0    C0    C3    C（5）組內替換算法采用FIFO時，Cache塊03的使用過程如下表所示。 時間：   1   2    3   4    5   

29、;6    7   8    9   10  11  12 主存塊地址流：   B6   B2   B4   B1   B4   B6   B3   B0 &#

30、160; B4   B5  B7   B3 Cache塊0 Cache塊1 Cache塊2 Cache塊3                              &#

31、160;        命中  命中                           命中 可見命中三次，Cache塊命中率為Hi = 3/12 = 0.25。 （6

32、） 組內替換算法采用LRU時，Cache塊03的使用過程如下表所示。時間：  1   2    3   4   5   6    7   8    9   10  11  12 主存塊地址流：  B6 

33、;  B2   B4  B1   B4   B6   B3   B0   B4   B5  B7   B3 Cache塊0 Cache塊1 Cache塊2 Cache塊3       

34、60;                             命中  命中           命中      

35、60;     命中 可見命中四次，Cache塊命中率為Hi = 4/12 = 0.33。 （7） 全相聯映象的規(guī)則是主存塊07可裝入Cache塊03的任一塊上。 當替換算法采用FIFO時，Cache塊03的使用過程如下表所示。時間：  1   2    3   4    5   6

36、60;   7   8    9   10  11  12 主存塊地址流：  B6   B2   B4   B1   B4   B6   B3   B0   B

37、4   B5  B7   B3       Cache塊0 Cache塊1 Cache塊2 Cache塊3                          &

38、#160;           命中  命中           命中            命中 可見命中四次，Cache塊命中率為Hi = 4/12 = 0.33。 當替換算法

39、采用LRU時，Cache塊03的使用過程如下表所示。 時間：  1   2    3   4    5   6    7   8    9   10  11  12 主存塊地址流：  B6&

40、#160;  B2   B4   B1   B4   B6   B3   B0   B4   B5  B7   B塊0 Cache塊1 Cache塊2 Cache塊3        

41、;                             命中  命中           命中 可見命中三次，Cache塊命中率為Hi = 3/1

42、2 = 0.25。     （8）當命中三次時，Cache的命中率為Hi = （12×16-9）/（12×16）1，當命中四次時，Cache的命中率為Hi = （12×16-8）/（12×16）1。3.203.23對于一個采用組相聯映象方式和FIFO替換算法的Cache，發(fā)現它的等效訪問時間太長，為此，提出如下建議： （1）  增大主存的容量。答案：基本無關（2）  （2） 提高主存的速度。  答

43、案：能夠減小等效訪問時間，T=TcH+Tm(1-H),通過減小Tm能夠減小T。（3） （3） 增大Cache的容量 答案：當cache比較小時，增大cache對減少等效訪問時間效果明顯；當cache容量達到一定程度時效果逐漸不明顯。（4） （4） 提高Cache的速度。 （5）  Cache的總容量和組大小不變，增大塊的大小。（6）  （6） Cache的總容量和塊大小不變，增大組的大小。答案：有一個極大值，在這個極大值點，等效訪問時間最小。 （7） （7） Cache的總容量和塊大小不變，增加組數。&#

44、160;（8） （8） 替換算法由FIFO改為LFU 第4章 ：4.4有5個中斷源D1、D2、D3、D4和D5，它們的中斷優(yōu)先級從高到低依次是1-5級別。這些中斷源的中斷優(yōu)先級、正常情況下的中斷屏蔽碼和改變后的中斷屏蔽碼如下表所示。每個中斷源有5位中斷屏蔽碼，其中0表示該中斷源開放，1表示該中斷源被屏蔽。(1)當使用正常的中斷屏蔽碼時，處理器響應各中斷源的中斷請求的先后順序是什么？實際上中斷處理的先后次序是什么？ (2)當使用改變后的中斷屏蔽碼時，處理器響應各中斷源的中斷請求的先后順序是什么？實際上中斷處理的先后次序是什么？ (3)如果采用改變后的中斷屏

45、蔽碼， D1、D2、D3、D4和D5同時請求中斷時，畫出處理器響應各中斷源的中斷請求和實際運行中斷服務程序過程的示意圖。答案：(1) 當使用正常的中斷屏蔽碼時，處理器響應各中斷源的中斷請求的先后順序是D1、D2、D3、D4、D5。 實際上中斷處理的先后次序是D1、D2、D3、D4、D5。 (2) 當使用改變后的中斷屏蔽碼時，處理器響應各中斷源的中斷請求的先后順序是D1、D2、D3、D4、D5。 實際上中斷處理的先后次序是D4、D5、D3、D2、D1。 (3)  如果采用改變后的中斷屏蔽碼， D1、D2、D

46、3、D4和D5同時請求中斷時，處理器響應各中斷源的中斷請求和實際運行中斷服務程序過程如下圖所示：4.5某處理機共有4個中斷源，分別為D1、D2、D3、D4,要求處理機響應中斷源的中斷服務請求的次序從高到低分別是D1、D2、D3、D4，而處理機實際為各中斷源服務的先后次序為D3，D3，D4，D1.每個中斷源有4位中斷屏蔽碼，其中，0表示該中斷源被屏蔽，1表示該中斷源開放。已知中斷服務次序為3-2-4-1，。(1)中斷屏蔽字表如下圖；D1D2D3D4D10111D20010D30000D40110(2)中斷過程示意圖如右圖。時間 中斷請求主程序1級 2級 3級 4級 D1，D2 D3，D44.74

47、.8一個字節(jié)多路通道連接有4臺外圍設備，每臺設備發(fā)出輸入輸出服務請求的時間間隔，他們的服務優(yōu)先級和發(fā)出第一次服務請求的時刻表如下：設備名稱            D1      D2         D3          D4&

48、#160;發(fā)服務請求間隔       10µs     75 µs       15 µs      50 µs  服務優(yōu)先級           &

49、#160;1        4           2          3 發(fā)第一次請求時刻     0 µs    70 µs     10 µs      20 µs  （1）計算這個字節(jié)多路通道的實際流量和工作周期 （2）在數據傳送期間，如果通道選擇一次設備的時間為3