計算機(jī)系統(tǒng)結(jié)構(gòu)期末重點(diǎn)題目及考點(diǎn)

1、第1章 ：1.2.如有一個經(jīng)解釋實(shí)現(xiàn)的計算機(jī)，可以按功能劃分成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.從機(jī)器（匯編）語言程序員看，以下哪些是透明的？n 指令地

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

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

4、5/1693.75(14) 能表示的規(guī)格化浮點(diǎn)數(shù)個數(shù)為：2×15×165×27+12.13 一個處理機(jī)共有10條指令，各指令在程序中出現(xiàn)的概率如下表：指令信號  出現(xiàn)概率  Huffman編砝碼  2/8擴(kuò)展編砝碼  3/7擴(kuò)展編砝碼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編碼法”實(shí)際是指碼長下限，即信源的平均信息量熵，代公式得H=2.9566。(2)Huffman編碼性能如下表；(3)2/8擴(kuò)展編碼是8/64/512法的變種，第一組2條指令，碼長為2（1位擴(kuò)展標(biāo)志，1位編碼）,第二組8條指令，碼長為4（1位擴(kuò)展標(biāo)志，與第一組區(qū)別，加3位編碼），編碼性能如下表；(4)3/7擴(kuò)展編碼是15/15/15法的變種，第一組3條指令，碼長為

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

7、器型變址尋址方式指令4條，變址范圍不小于±127。請設(shè)計指令格式，并給出各字段的長度和操作碼的編碼。解：(1)要使得到的操作碼長度最短，應(yīng)采用Huffman編碼，構(gòu)造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)設(shè)計8位字長的寄存器-寄存器型變址尋址方式指令如下，因?yàn)橹挥?個通用寄存器，所以寄存器地址需3位

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

9、126條/128條(1)根據(jù)指令地址的數(shù)量來決定各種指令在指令空間上的分布：如果我們按照從小到大的順序分配操作碼，這樣，按照指令數(shù)值從小到大的順序，分別為雙地址指令、單地址指令和零地址指令。其次可以根據(jù)指令的條數(shù)來大致的估計操作碼的長度：雙指令15條，需要4位操作碼來區(qū)分，剩下的12位操作碼平均分給單地址和零地址指令，每種指令可以用6位操作碼來區(qū)分，這樣，各指令的條數(shù)為：雙地址指令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） 如果要求頁表所占用的總主存頁面數(shù)最小，請分配每一級頁表的實(shí)際存儲容量各為多少字節(jié)？答：第一季頁表為一個頁面大小，為4kb，第二級頁表被占用1k個頁面，為4mb（3）

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

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

14、160;主存實(shí)頁號（11位）頁內(nèi)地址（12位）      共23位 （3） 快表字長27位；分3個字段：用戶號6位，虛頁號10位，實(shí)頁號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 假設(shè)系統(tǒng)分配給這個程序的主存有3個頁面，分別采用FIFO、LRU和OPT三種替換算法對這三頁主存進(jìn)行調(diào)

15、度。（1）畫出主存頁面調(diào)入、替換和命中的情況表。（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調(diào) 調(diào) 命 調(diào) 替 替 替 命 替 命 替 替進(jìn) 進(jìn) 中 進(jìn) 換 換 換 中 換 中 換 換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調(diào) 調(diào) 命 調(diào) 替 命 替 命 替 替 命 命進(jìn)

16、進(jìn) 中 進(jìn) 換 中 換 中 換 換 中 中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調(diào) 調(diào) 命 調(diào) 替 命 替 命 命 替 命 命進(jìn) 進(jìn) 中 進(jìn) 換 中 換 中 中 換 中 中3.15.一個程序由五個虛頁組成，采用lfu替換算法，在程序中依次訪問的頁地址流如下：P4，P5，P3，P2，P5，P1，P3，P2，P3，P5，P1，P3(1) 可能的最高頁命中率是多少？(2) 至少要分配給該程序多少個主存頁面才能獲得最高的命中率?(3) 如果在程序中每訪問一個頁面，平均要對該頁面內(nèi)的存儲單元訪問10

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

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

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

20、215;1024-5），單元訪問總次數(shù)為12×1024，故有：Hcell=(12×1024-5)/(12×1024)=12283/1228899.96%3.16.一個程序由1200條指令組成，每條指令的字長均為4B。假設(shè)這個程訪問虛擬存儲器的字地址流為：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個實(shí)頁。給定的程序訪存字地址流對主存空間的使用過程如圖所示。主存命中率H1=612 = 050  (2)  （8分）頁的大小為512B，即頁面大小為128字；主存容量為2&#

22、160;048B，即分配n=4個實(shí)頁。給定的程序訪存字地址流對主存空間的使用過程如圖所示。主存命中率為H2 = 312 = 025(3)  頁的大小為2048B，即頁面大小為512字，主存容量為2048B，即分配n=1個實(shí)頁。給定的程序訪存字地址流對主存空間的使用過程如圖所示。主存命中率為H3 = 612 = 0503.19 在一個采用組相聯(lián)映象方式的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)寫出主存地址的格式，并標(biāo)出各字段的長度。 (2)寫出Cache地址的格式，并標(biāo)出各字段的長度。 (3)指出主存與Cache之間各個塊的映象關(guān)系。 (4)若Cache的4個塊號為C0、C1、C2和C3，列出程序執(zhí)行過程中的Cache塊地址流。 (5)若采用FIFO替換算法，計算Cache的塊命中率。 (6)若采用LRU替換算法，計算Cache的塊命中率。 (7)若改為全相聯(lián)映象方式，再做(5)和(6)。 (8)若在程序執(zhí)行過程中，每從主存裝入一塊

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

25、塊07與Cache塊03之間的映象關(guān)系為：主存塊0、1、4、5與Cache塊0、1之間全相聯(lián)，主存塊2、3、6、7與Cache塊2、3之間全相聯(lián)。     （4）根據(jù)組相聯(lián)映象的規(guī)則，該主存塊地址流相應(yīng)的一種Cache塊地址流如下表所示（組內(nèi)替換算法為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）組內(nèi)替換算法采用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、） 組內(nèi)替換算法采用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） 全相聯(lián)映象的規(guī)則是主存塊07可裝入Cache塊03的任一塊上。 當(dāng)替換算法采用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。 當(dāng)替換算法

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

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

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)當(dāng)使用正常的中斷屏蔽碼時，處理器響應(yīng)各中斷源的中斷請求的先后順序是什么？實(shí)際上中斷處理的先后次序是什么？ (2)當(dāng)使用改變后的中斷屏蔽碼時，處理器響應(yīng)各中斷源的中斷請求的先后順序是什么？實(shí)際上中斷處理的先后次序是什么？ (3)如果采用改變后的中斷屏

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

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

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

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

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