（精選）計算機系統(tǒng)結(jié)構(gòu)習(xí)題答案(鄭偉民)

1、第一章重點：1. P2 1.1.1計算機系統(tǒng)層次結(jié)構(gòu)（1.1.2透明性概念）2. P9 1.2.1計算機系統(tǒng)設(shè)計的定量原理（Amdahl law及CPU性能公式）3. P22 1.4.1 Von Neumann結(jié)構(gòu)（模擬與仿真）1 習(xí)題 題1.5 硬件和軟件在什么意義上是等效的?在什么意義上又是不等效的?試舉例說明。 解答 硬件和軟件在邏輯功能上是等效的。在原理上，用軟件實現(xiàn)的功能完全可以用硬件或固件(微程序解釋)來完成。用硬件實現(xiàn)的功能也可以通過用軟件進行模擬來完成，只是反映在速度、價格、實現(xiàn)的難易程度上，這兩者是不同的。 例如，編譯程序、操作系統(tǒng)等許多用機器語言軟件子程序?qū)崿F(xiàn)的功能完全可以

2、用組合電路硬件或微程序固件來解釋實現(xiàn)。它們的差別只是軟件實現(xiàn)的速度慢，軟件的編制復(fù)雜，編程工作量大，程序所占的存貯空間量較多，這些都是不利的；但是，這樣所花硬件少，硬件實現(xiàn)上也就因此而簡單容易，硬件的成本低，解題的靈活性和適應(yīng)性較好，這些都是有利的。又如，乘除法運算可以經(jīng)機器專門設(shè)計的乘法指令用硬件電路或乘除部件來實現(xiàn)，也可以通過執(zhí)行一個使用相加、移位、比較、循環(huán)等機器指令組成的機器語言子程序來實現(xiàn)。向量、數(shù)組運算在向量處理機中是直接使用向量、數(shù)組類指令和流水或陣列等向量運算部件的硬件方式來實現(xiàn)，但在標(biāo)量處理機上也可以通過執(zhí)行用標(biāo)量指令組成的循環(huán)程序的軟件方式來完成。 浮點數(shù)運算可以直接通過設(shè)

3、置浮點運算指令用硬件來實現(xiàn)，也可以用兩個定點數(shù)分別表示浮點數(shù)的階碼和尾數(shù)，通過程序方法把浮點數(shù)階碼和尾數(shù)的運算映象變換成兩個定點數(shù)的運算，用于程序軟的方式來實現(xiàn)。十進制數(shù)的運算可以通過專門設(shè)置十進制運算類指令和專門的十進制運算部件硬的方式來完成，或者通過設(shè)置BCD數(shù)的表示和若干BCD數(shù)運算的校正指令來軟硬結(jié)合地實現(xiàn)，也可以先經(jīng)10轉(zhuǎn)2的數(shù)制轉(zhuǎn)換子程序?qū)⑹M制數(shù)轉(zhuǎn)成二進制數(shù)，再用二進制運算類指令運算，所得結(jié)果又調(diào)用2轉(zhuǎn)10的數(shù)制轉(zhuǎn)換子程序轉(zhuǎn)換成十進制數(shù)結(jié)果，用全軟的方式實現(xiàn)。 題1.7 什么是透明性概念?對于計算機系統(tǒng)結(jié)構(gòu)，下列哪些是透明的?哪些是不透明的? 存貯器的模m交叉存?。焊↑c數(shù)據(jù)表示：

4、IO系統(tǒng)是采用通道方式還是外圍處理機方式；數(shù)據(jù)總線寬度；字符行運算指令；陣列運算部件；通道是采用結(jié)合型還是獨立型：PDP11系列中的單總線結(jié)構(gòu)；訪問方式保護；程序性中斷；串行、重疊還是流水控制方式；堆棧指令；存貯器的最小編址單位；Cache存貯器。 分析 所謂透明就是看不到，不屬于其管理的部分。對計算機系統(tǒng)結(jié)構(gòu)是否透明，首先要弄清教材1.2.1節(jié)中有關(guān)計算機系統(tǒng)結(jié)構(gòu)的定義和所包含的屬性內(nèi)容。簡單來說，凡是編寫機器語言和匯編語言程序要用到的數(shù)據(jù)表示、指令系統(tǒng)、尋址方式、寄存器組織、機器級IO結(jié)構(gòu)、存貯容量及其編址方式、中斷機構(gòu)、系統(tǒng)管態(tài)和目態(tài)間的切換、信息保護方式和機構(gòu)等對計算機系統(tǒng)結(jié)構(gòu)都是不透

5、明的。而全部由硬件實現(xiàn)，或是在機器語言、匯編語言編程中不會出現(xiàn)和不需要了解的部分，以及只影響機器的速度和價格的邏輯實現(xiàn)(計算機組成)和物理實現(xiàn)(計算機實現(xiàn))的那些部分，對計算機系統(tǒng)結(jié)構(gòu)都是透明的。 解答 客觀存在的事物或?qū)傩?。從某個角度去看，卻看不到，稱這些事物和屬性對他是透明的。透明了就可以簡化這部分的設(shè)計，然而因為透明而無法控制和干預(yù)，就會帶來不利。因此，透明性的取舍要正確選擇。 對計算機系統(tǒng)結(jié)構(gòu)透明的有：存貯器的模m交叉存取，數(shù)據(jù)總線寬度，陣列運算部件，通道是采用結(jié)合型還是獨立型，PDP一11系列的單總線結(jié)構(gòu)，串行、重疊還是流水控制方式，Cache存貯器。 對計算機系統(tǒng)結(jié)構(gòu)不透明的有：浮

6、點數(shù)據(jù)表示，IO系統(tǒng)采用通道方式還是外圍處理機方式，字符行運算指令，訪問方式保護，程序性中斷，堆棧指令，存貯器最小編址單位。 題1.8 從機器(匯編)語言程序員的角度來看，以下哪些是透明的? 指令地址寄存器；指令緩沖器；時標(biāo)發(fā)生器；條件碼寄存器；乘法器；主存地址寄存器；磁盤外設(shè)；先行進位鏈；移位器；通用寄存器；中斷字寄存器。 分析 從機器(匯編)語言程序員看，實際上也就是從計算機系統(tǒng)結(jié)構(gòu)看的內(nèi)容。 指令地址寄存器就是程序計數(shù)器，匯編語言或機器語言程序都要用到它的，其位數(shù)多少會影響到可執(zhí)行程序的空間大小。指令緩沖器、主存地址寄存器都屬于計算機組成中的緩沖器技術(shù)，是由全硬件實現(xiàn)的，系統(tǒng)程序不參預(yù)對

7、它們的管理。時標(biāo)發(fā)生器、乘法器、先行進位鏈、移位器等都屬于計算機組成中的專用部件配臀，它只影響機器的速度和價格，與軟件編程無關(guān)。條件碼寄存器是存放指令執(zhí)行后生成反映結(jié)果狀態(tài)或特征的標(biāo)志碼，它要供轉(zhuǎn)移等指令使用，是編程要用到的。磁盤外設(shè)的種類、編址方式、容量等都是磁盤管理服務(wù)程序要用到的。通用寄存器的數(shù)量、位效、編址、使用規(guī)定在匯編語言程序和機器語言程序中都是會直接用到的。中斷字寄存器是用來記錄每一個中斷類中，各個中斷源發(fā)生中斷請求的狀況的，它是中斷服務(wù)程序在處理中斷時要用到的。 解答 從機器(匯編)語言程序員來看，透明的有：指令緩沖器，時標(biāo)發(fā)生器，乘法器，主存地址寄存器，先行進位鏈，移位器。

8、題1.9 下列哪些對系統(tǒng)程序員是透明的?哪些對應(yīng)用程序員是透明的? 系列機各檔不同的數(shù)據(jù)通路寬度；虛擬存貯器；Cache存貯器；程序狀態(tài)字：“啟動IO”指令；“執(zhí)行”指令；指令緩沖寄存器。 分析 系統(tǒng)程序員是編寫諸如操作系統(tǒng)、編譯程序等各種系統(tǒng)軟件的人員。應(yīng)用程序員是指利用計算機及所配的系統(tǒng)軟件支持來編寫解決具體應(yīng)用問題的程序員。他們都可以使用匯編語言或機器語言來編寫程序，當(dāng)然也可以用高級語言來編寫程序。所以，對系統(tǒng)程序員或應(yīng)用程序員是不透明的，應(yīng)包括計算機系統(tǒng)結(jié)構(gòu)所包含的各個方面。而屬全硬件實現(xiàn)的計算機組成所包含的方面，如系列機各檔不同的數(shù)據(jù)通路寬度、Cache存貯器、指令緩沖寄存器等，無論

9、是對系統(tǒng)程序員，還是對應(yīng)用程序員都應(yīng)當(dāng)是透明的。對目前高性能計算機系統(tǒng)來講，大多數(shù)都是多用戶環(huán)境，應(yīng)用程序(也稱算態(tài)，目態(tài)或用戶態(tài)程序)中不允許使用管態(tài)(也林系統(tǒng)態(tài)，監(jiān)督態(tài))中所用的特權(quán)指令。 例如，大型多用戶系統(tǒng)中，程序狀態(tài)字是用于反映計算機系統(tǒng)在當(dāng)前程序的各種關(guān)鍵狀態(tài)(它并不是IBM PC計算機那種狹義的所謂程序狀態(tài)字)的，它是操作系統(tǒng)用于管理計算機系統(tǒng)資源及其使用狀況的，用戶是不能直接對程序狀態(tài)字內(nèi)容進行讀，寫和訪問的，只能由系統(tǒng)來管理?！皢覫O”指令是大型機中的種管態(tài)指令，屬于特權(quán)指令，只能在操作系繞程序中使用(見教材中第3章3.4.1節(jié)的介紹)。用戶程序是不能用它來直接啟動IO通道

10、和設(shè)備的。虛擬存貯器(參看教材第4章4.1.3節(jié))是一個主存輔存兩級存貯層次。它對應(yīng)用程序員是完全透明的，使應(yīng)用程序不必作任何修改就可以在系統(tǒng)上運行。但是，在操作系統(tǒng)中必須配置有相應(yīng)的管理軟件，能對其虛實外部地址的映象和變換、程序的換道、程序由輔存調(diào)入主存、主存頁面的替換、存貯保護等進行管理，所以對系統(tǒng)程序員來說是不透明的?！皥?zhí)行”指令(參看教材中第5章5.1.2節(jié))是IBM 370等系列機上用于解決程序在執(zhí)行過程中不準(zhǔn)修改指令，又允許將指令放在操作數(shù)區(qū)中作修改，以滿足指令在執(zhí)行過程中允許修改的要求。這種指令無論是用戶程序，還是系統(tǒng)程序，都希望可以被使用，所以，“執(zhí)行”指令應(yīng)設(shè)計成對應(yīng)用程序員

11、和系統(tǒng)程序員都是不透明的。 解答 系列機各檔不同的數(shù)據(jù)通路寬度、Cache存貯器、指令緩沖寄存器屬計算機組成，對系統(tǒng)程序員和應(yīng)用程序員都是透明的。虛擬存貯器、程序狀態(tài)字、“啟動IO”指令，對系統(tǒng)程序員是不透明的，面對應(yīng)用程序員卻是透明的?！皥?zhí)行”指令則對系統(tǒng)程序員和應(yīng)用程序員都是不透明的。1.7(1)從指定角度來看，不必要了解的知識稱為透明性概念。(2)見下表，“”為透明性概念，“P”表示相關(guān)課文頁數(shù)。模m交叉，浮點數(shù)據(jù)，×，P4通道與I/O處理機，×，P4總線寬度，陣列運算部件，×，結(jié)合型與獨立型通道，單總線，訪問保護，×，中斷，×，指令控制

12、方式，堆棧指令，×，最小編址單位，×，Cache存儲器，1.8見下表，“”為透明性概念，“P”表示相關(guān)課文頁數(shù)。指令地址寄存器，×，指令緩沖器，時標(biāo)發(fā)生器，條件碼寄存器，×，乘法器，主存地址寄存器，磁盤，×，先行進位鏈，移位器，通用寄存器 ，×，中斷字寄存器，×，1.9見下表，“”表示都透明，“應(yīng)”表示僅對應(yīng)用程序員透明，“×”表示都不透明。數(shù)據(jù)通路寬度，虛擬存儲器，應(yīng)，Cache存儲器，程序狀態(tài)字，×，“啟動I/O”指令，應(yīng)，“執(zhí)行”指令，×，指令緩沖寄存器，Sn20 1 01 Fe1.12

13、已知Se=20 , 求作Fe-Sn關(guān)系曲線。 將Se代入Amdahl定律得1.13 上式中令Sn=2，解出Fe=10/190.5261.14 上式中令Sn=10，解出Fe=18/190.9471.15 已知兩種方法可使性能得到相同的提高，問哪一種方法更好。(1)用硬件組方法，已知Se=40，F(xiàn)e=0.7，解出Sn=40/12.73.1496（兩種方法得到的相同性能）(2)用軟件組方法，已知Se=20，Sn=40/12.7，解出Fe=27.3/380.7184（第二種方法的百分比）(3)結(jié)論：軟件組方法更好。因為硬件組需要將Se再提高100%（2040），而軟件組只需將Fe再提高1.84%（0.

14、70.7184）。1.17 1.18 記f 時鐘頻率，T=1/f 時鐘周期，B 帶寬（Byte/s）。方案一：方案二：1.19 由各種指令條數(shù)可以得到總條數(shù)，以及各百分比，然后代公式計算。(1)(2)(3)1.21(1)(2)1.24 記Tc 新方案時鐘周期，已知CPI = CPIi = 1原時間 = CPI × IC × 0.95Tc = 0.95IC×Tc新時間 = （0.3×2/3+0.7）× IC × Tc = 0.9IC×Tc二者比較，新時間較短。第二章重點：P91 2.3.2.2Huffman編碼法2.3（忽略P

15、124倒1行 P125第8行文字，以簡化題意）已知2種浮點數(shù)，求性能指標(biāo)。 此題關(guān)鍵是分析階碼、尾數(shù)各自的最大值、最小值。 原圖為數(shù)據(jù)在內(nèi)存中的格式，階碼的小數(shù)點在其右端，尾數(shù)的小數(shù)點在其左端，遵守規(guī)格化要求。 由于尾數(shù)均為原碼，原碼的絕對值與符號位無關(guān)，所以最大正數(shù)與最小負(fù)數(shù)的絕對值相同，可用“±最大絕對值”回答；最小正數(shù)與最大負(fù)數(shù)的絕對值相同，可用“±最小絕對值”回答。 第1小問中，階碼全部位數(shù)為8，作無符號數(shù)看待真值為0255，作移-127碼看待真值為-127+128；尾數(shù)（不計符號位）有23位小數(shù)，另加1位整數(shù)隱藏位，所以尾數(shù)絕對值為1.02.0 2-23，有效位數(shù)

16、p=24； 第2小問中，階碼全部位數(shù)為11，作無符號數(shù)看待真值為02047，作移-1023碼看待真值為-1023+1024；尾數(shù)（不計符號位）有52位小數(shù)，另加1位整數(shù)隱藏位，所以尾數(shù)絕對值為1.02.0 2-52，有效位數(shù)p=53。 最大絕對值為最大階碼與最大尾數(shù)絕對值的組合，最小絕對值為最小階碼與最小尾數(shù)絕對值的組合。代入相關(guān)公式后得最終結(jié)果如下表。32位64位±最大絕對值±(1-2-24)·2129±(1-2-53)·21025±最小絕對值±2-127±2-1023表數(shù)精度2-242-53表數(shù)效率100%10

17、0%2.5(1) rm = 2，re = 2，p = 24（隱藏最高位）,q = 7。(2) Nmax = 1.7×1038，-|N|min = -1.47×10-39 5.96×10-8 10-7.22， = 100%2.61位7位6位00111111333333(1) 0.2 = 0.333333H×160 設(shè)階碼為移-63碼（即-26+1，原題未指明）0.2 = 0.110011001100110011001101B×2-2 1位8位23位00111110110011001100110011001101（其中最高有效位需隱藏）階碼為移-1

18、27碼（即-27+1）(2) 符號位不變，（階碼 63）×4 + 127；尾數(shù)左規(guī)，除去最高位；(3) 符號位不變，（階碼 127）/ 4 + 63；尾數(shù)補最高位，按除法余數(shù)右移若干位，左補0。2.11 從地址的整數(shù)倍位置開始訪問20% |字節(jié)8位|浪費8位|半字16位|單子32位2.5% |半字16位|半字16位|半字16位|半字16位|30% |雙字64位|2.13 已知10條指令使用頻度，求3種編碼方法的平均碼長與信息冗余量。(1)此問中的“最優(yōu)Huffman編碼法”實際是指碼長下限，即信源的平均信息量熵，代公式得H=2.9566。(2)Huffman編碼性能如下表； 公式：(

19、3)2/8擴展編碼是8/64/512法的變種，第一組2條指令，碼長為2（1位擴展標(biāo)志，1位編碼）,第二組8條指令，碼長為4（1位擴展標(biāo)志，與第一組區(qū)別，加3位編碼），編碼性能如下表； 00；01；1*；(4)3/7擴展編碼是15/15/15法的變種，第一組3條指令，碼長為2（共有4種組合，其中3種組合分別代表3條指令，留1種組合作為擴展前綴標(biāo)志）,第二組7條指令，碼長為5（2位固定的前綴擴展標(biāo)志，與第一組區(qū)別，加3位編碼，只用其中7種組合），編碼性能如下表。 00；01；10；11*（只用7種）；Huffman編碼2/8擴展編碼3/7擴展編碼平均碼長L2.993.13.2信息冗余量R1.10%

20、4.61%7.59%2.142.15(1) 15條/63條/64條 (2) 14條/126條/128條說明：每種擴展劉兩種組合：0000共1411011110 0000001110 111111 000000共26共26-11110 擴充碼1110 111111 1110 1111101110 111111 11111111110000001111 111111 000000共26共26-11111 擴充碼1111 111111 11111111101111 111111 1111112.18 P1172.20 向后轉(zhuǎn)移（1）start: move as,r1Mov num,r2dec r1i

21、nc r1Loop:move (r1),ad-as(r1)Dec r2Bgt loopInc r1HaltNum:N(2)N=100，循環(huán)100次，節(jié)省100個周期，循環(huán)體前后浪費3個周期，故能節(jié)省97個指令周期（3）start: move as,r1Mov num,r2Dec r2Dec r1Inc r1Loop:move (r1),ad-as(r1)Bgt loopInc r1Dec r2HaltNum:N第三章難點：3.1.4.2交叉訪問存儲器重點：地址映射及替換算法P146 3.2 虛擬存儲器 P174 3.3 Cache3.2 T=H1T1+H2T2+H3T3；S=S1+S3+S2；

22、C=(C1S1+C2S2+C3S3)/S3.3 直接代公式計算存儲層次性能指標(biāo)。(1)74ns，38ns，23.6nsH*t1+(1-h)*t2(2)0.258，0.315，0.424(c1s1+c2s2)/(s1+s2)(3)T256K < T128K < T64K c256K > c128K > c64K(4)T*C分別得 19.092，11.97，10.0064。答案是256K方案最優(yōu)。3.5 已知，其中g(shù)=0.1依題意有整理得0.9n0.2，解出，向下取整，得15；按另一種題意理解是向上取整，得16，也對。3.73.9 =2,Nv:虛存大??；Np：頁面大小；Nd

23、：頁表存儲字大小（2）4KB/4B=1K，故而二級頁表空間為：4GB/1K=4MB，需4MB/4KB=1024頁；4MB/1K=4KB，故一級頁表空間為4KB，即1頁（3）一級頁表必須駐立主存3.10 令TM為主存的平均訪問時間，TD為硬盤的訪問時間，則T=HTM+(1-H)TD=(10000-9999*0.9999)TM=1.9999TM=TM/T=1/1.9999=50.0025%3.12 (1) U=log264=6;P=log21024=10;D=log24K=12(2)總數(shù)為log28M=23;D=log24K=12,故實頁號p=23-12=11；（3）快表：多用戶虛頁號（U+P）+

24、實頁號p，即16+11=17（4）每個實頁在頁表中都存在一行與之對應(yīng)，故共需211=2K=2048（個存儲字）；慢表包括主存頁號（實頁號）+裝入位及其它標(biāo)志位，即11+1+其它（5）P159 圖3.273.14P=232152453252命中次數(shù)FIFO2222*555*5*333333333*2222*2*5525%111*4444*4*2入入中入換換換中換中換換向每行回看，最大的為待換出的LFU22222*222*333*3*5333*555*555*5541.67%111*444*222入入中入換中換中換換中中向頁地址流回看，最后出現(xiàn)的為待換出的OPT222222*4*4*4*22263

25、333*33333*3*3*50%1*55555555入入中入換中換中中換中中向頁地址流后看，最遠(yuǎn)才訪問的為待換出的注：最好的辦法是堆棧模擬。3.15 欲知可能的最高命中率及所需的最少主存頁數(shù)，較好的辦法是通過“堆棧模擬法”，求得命中次數(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次單

26、元訪問肯定是命中的，而第1次單元訪問的命中情況與這1次頁面訪問的命中情況相同。根據(jù)上圖中最高命中情況，共有7次頁命中（折算為7×1024次單元命中），5次頁不命中（折算為5×1023次單元命中，也可寫為5×1024-5），單元訪問總次數(shù)為12×1024，故有：Hcell=(12×1024-5)/(12×1024)=12283/1228899.96%改LRU替換算法：分析 由于LRU替換算法是堆棧型的替換算法，因而隨著分配給該程序的實頁數(shù)增加，實頁命中率只會上升，至少是不會下降的。但是，當(dāng)實頁數(shù)增加到一定程度之后，其命中率就不會再提高了

27、如耍再增加分配給該道程序的實頁數(shù)，只會導(dǎo)致實存空間的利用率下降所以，只要分別求出分配給該道程序不同實頁數(shù)時的頁命中率，找出達到最高命中率時所分配的最少實頁數(shù)即可 既然LRU替換算法是堆棧型的替換算法，對虛頁地址流只需要用堆棧處理技術(shù)處理一次，就可以同時求出不同實頁數(shù)時各自的命中率這樣，可以大大減少模擬的工作量。解答 用堆棧對頁地址流處理一次的過程見表46所示，其中H表示命中。頁地址流4 5 3 2 5 1 3 2 2 5 1 3 S(1) S(2) S(3) S(4) S(5) S(6)4 5 3 2 5 1 3 2 2 5 1 34 5 3 2 5 l 3 3 2 5 1 4 5 3 2 5

28、 l 1 3 2 5 4 4 3 2 5 5 1 3 2 n=1實 n=2頁 n=3 數(shù) n=4 n=5H H H H H H H H H H H H H H H H H H 模擬結(jié)果表明，使用LRU替換算法替換，對該程序至少應(yīng)分配4個實頁如果只分配3個實頁，其頁命中率只有212，太低：而分配實頁數(shù)多于4頁后，其頁命中率不會再有提高所以，分配給該程序4個實頁即可，其可能的最高命中串為H7123.15加1題 一個二級存儲層次，采用全相聯(lián)映象和最久沒有使用算法，實存共5頁，為2道程序分享，頁地址流分別如下P1 = 1 2 3 4 1 3 2 1P2 = 1 2 3 4 2 2 3 3試作2個實存分

29、配方案，分別使2道程序滿足(1)命中率相同；(2)命中次數(shù)之和最大。P1 =12341321命中次數(shù)N(1)12341321123413212341312244n1= 10n1= 20n1= 32n1= 44解：分別為2道程序作“堆棧模擬圖”，其中“”表示命中。P2 =12342233命中次數(shù)N(2)12342233123442212334411111n2= 12n2= 22n2= 34n2= 4465 N(1)+N(2)432 N(1) N(2)1 1+4 2+3 3+2 4+1將兩圖結(jié)果綜合，得到4個分配方案的命中率情況表如下n11234N(1)0024n24321N(2)4422N(1)

30、+N(2)4446結(jié)論如下(1)命中率相同的方案是n1= 3而n2= 2；(2)命中次數(shù)之和最大的方案是n1= 4而n2= 1。3.19（1）區(qū)號：；格式為：|1E|1G|1B|4W|（2）cache格式為：|組號g：1位|組內(nèi)塊號：1位|塊內(nèi)地址W：4| 虛存 實頁0123虛組0 00 1 實存1虛組1 2·0 實組02 3·1虛3虛組2 4·2 實組1頁4 5·35虛組3 66 77(a) 虛頁集合與實頁集合的對應(yīng)關(guān)系 (b) 對應(yīng)關(guān)系表（為有關(guān)系）(3)(4)通過作“實存狀況圖”模擬各虛塊的調(diào)度情況，可獲得Cache的塊地址流序列。P=624146

31、304573C044*4444*44*4*4*C111*1*1*00*555C266*6*6*6*66*6*6*6*77*C322222*33333*3入入入入中中替替中替替中C=230102310123此問最容易出錯的地方是忽略“組相聯(lián)”地址約束，將虛頁裝錯實組。另外沒有及時標(biāo)注“*”號也容易導(dǎo)致淘汰對象錯誤。（5）P=624146304573C044*4*4*4*00*555C111111*44*4*4*C266*6*6*6*6*33333*3*C3222222*2*2*2*77入入入入中中替替替替替中（7）LFUP=624146304573C06666*6*6666*555C122222

32、*3333*77C2444444*4444*C31111*0000*3入入入入中中替替中替替替(6)H=4/1233%(8)做法同3.15題(3)問，Hcell=(12×16-8)/(12×16)95.8%3.21（2）一個主存周期從主存中取出數(shù)據(jù)為：4體交叉×體字長4B=16B，故cache塊大小為16B，共1KB/16B=64塊，每組4塊，故共64/4=16組，故cache的地址為：|組號g：4位|組內(nèi)塊號b：2位|塊內(nèi)地址W：4位|（1）主存的塊與cache的組是直接映像，故主存每區(qū)有16塊（cache共16組），每塊大小16B，共有區(qū)數(shù)1MB/16

33、5;16B=4K個區(qū)。故主存地址為：|區(qū)號E：12位|區(qū)內(nèi)塊號B：4位|塊內(nèi)地址W：4位|（3）cache的每一組在塊表中要有一行，故要有16行，由于有四個比較電路，故每行如下：|區(qū)號E|塊號b|區(qū)號E|塊號b|區(qū)號E|塊號b|區(qū)號E|塊號b|；其中區(qū)號E12位，塊號b2位注：塊表中并不包含所有的區(qū)，只有在cache中的區(qū)才在塊表中有對應(yīng)記錄。（4）每個比較電路的位數(shù)12位（5）P183 圖3.483.23引1：在一個頁式二級虛擬存貯器中，采用FIFO算法進行頁面替換，發(fā)現(xiàn)命中率H太低，因此有下列建議： (1) 增大輔存容量 (2) 增大主存容量(頁數(shù)) (3) 增大主、輔存的頁面大小 (4)

34、 FIFO改為LRU (5) FIFO改為LRU，井增大主存容量(頁數(shù)) (6) FIFO改為LRU，且增大頁面大小 試分析上述各建議對命中率的影響情況。 解答 (1) 增大輔存容量，對主存命中率H不會有什么影響。因為輔存容量增大，并不是程序空間的增大，程序空間與實主存空間的容量差并未改變。所以，增大物理輔存容量，不會對主存的命中率H有什么影響。 (2) 如果主存容量(頁數(shù))增加較多時，將使主存命中率有明顯提高的趨勢。但如果主存容量增加較少，命中率片可能會略有增大，也可能不變，甚至還可能會有少許下降。這是因為其前提是命中率H太低。如果主存容量顯著增加，要訪問的程序頁面在主存中的機會會大大增加，

35、命中率會顯著上升。但如果主存容量(頁數(shù))增加較少，加上使用的FIFO替換算法不是堆棧型的替換算法，所以對命中率的提高可能不明顯，甚至還可能有所下降。 (3) 因為前提是主存的命中率H很低，在增大主、輔存的頁面大小時，如果增加量較 小，主存命中率可能沒有太大的波動。因為FIFO是非堆棧型的替換算法，主存命中事可能會有所增加，也可能降低或不變。而當(dāng)頁面大小增加量較大時，可能會出現(xiàn)兩種相反的情況。當(dāng)原頁面大小較小時，在顯著增大了頁面大小之后，一般會使主存命中率有較大提高。但當(dāng)原頁面大小已較大時，再顯著增大頁面大小后，由于在主存中的頁面數(shù)過少，將會使主存命中宰繼續(xù)有所下降。 (4) 頁面替換算法由FI

36、FO改為LRU后，一般會使主存的命中率提高。因為LRU替換算法比FIFO替換算法能更好地體現(xiàn)出程序工作的局部性特點。然而，主存命中率還與頁地址流、分配給主存的實頁數(shù)多少等有關(guān)，所以，主存命中率也可能仍然較低，沒有明顯改進。 (5) 頁面替換算法由FIFO改為LRU，同時增大主存的容量(頁數(shù))，一般會使主存命中率有較大的提高。因為LRU替換算法比FIFO替換算法更能體現(xiàn)出程序的局部性，又由于原先主存的命中宰太低，現(xiàn)增大主存容量(頁數(shù))，一般會使主存命中率上升。如果主存容量增加量大些，主存命中率H將會顯著上升。 (6) FIFO改為LRU，且增大頁面大小時，如果原先頁面大小很小，則會使命中率顯著上

37、升；如果原先頁面大小已經(jīng)很大了，因為主存頁數(shù)進一步減少而使命中率還會繼續(xù)有所下降。引2：采用組相聯(lián)映象、LRU替換算法的Cache存貯器，發(fā)現(xiàn)等效訪問速度不高，為此提議： (1 ) 增大主存容量 (2 ) 增大Cache中的塊數(shù)(塊的大小不變) (3 ) 增大組相聯(lián)組的大小(塊的大小不變) （4）增大塊的大小（組的大小和Cache總?cè)萘坎蛔儯?（5）提高Cache本身器件的訪問速度 試問分別采用上述措施后，對等效訪問速度可能會有什么樣的顯著變化？其變化趨勢如何？如果采取措施后并未能使等效訪問速度有明顯提高的話，又是什么原因？ 分析 Cache存儲器的等效訪問時間 ta = Hc tc + (1

38、-Hc)tm 等效訪問速度不高，就是ta太長。要想縮短ta，一是要使Hc命中率盡可能提高，這樣 (1-Hc)tm的分量就會越小，使ta縮短，越來越接近于tc。但如果ta已非常接近于tc時，表明Hc已趨于1，還想要提高等效訪問速度，則只有減小tc，即更換成更高速的Cache物理芯片，才能縮短ta。另外，還應(yīng)考慮Cache存貯器內(nèi)部，在查映象表進行Cache地址變換的過程時，是否是與訪物理Cache流水地進行，因為它也會影響到ta。當(dāng)Hc命中率已很高時，內(nèi)部的查映象表與訪Cache由不流水改成流水，會對tc有明顯的改進，可縮短近一半的時間。所以，分析時要根據(jù)不同情況做出不同的結(jié)論。 如果Cache存貯器的等效訪問速度不高是由于Hc太低引起的，在采用LRU替換算法的基礎(chǔ)上，就要設(shè)法調(diào)整塊的大小、組相聯(lián)映象中組的大小，使之適當(dāng)增大，這將會使Hc有所提高在此基礎(chǔ)上再考慮增大Cache的容量Cache存貯器中，只要Cache的容量比較大時，由于塊