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

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

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

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

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

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

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

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

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

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

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

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

12、方式，堆棧指令，×，最小編址單位，×，Cache存儲(chǔ)器，1.8見(jiàn)下表，“”為透明性概念，“P”表示相關(guān)課文頁(yè)數(shù)。指令地址寄存器，×，指令緩沖器，時(shí)標(biāo)發(fā)生器，條件碼寄存器，×，乘法器，主存地址寄存器，磁盤(pán)，×，先行進(jìn)位鏈，移位器，通用寄存器 ，×，中斷字寄存器，×，1.9見(jiàn)下表，“”表示都透明，“應(yīng)”表示僅對(duì)應(yīng)用程序員透明，“×”表示都不透明。數(shù)據(jù)通路寬度，虛擬存儲(chǔ)器，應(yīng)，Cache存儲(chǔ)器，程序狀態(tài)字，×，“啟動(dòng)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 已知兩種方法可使性能得到相同的提高，問(wèn)哪一種方法更好。(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é)論：軟件組方法更好。因?yàn)橛布M需要將Se再提高100%（2040），而軟件組只需將Fe再提高1.84%（0.

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

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

16、p=24； 第2小問(wèn)中，階碼全部位數(shù)為11，作無(wú)符號(hào)數(shù)看待真值為02047，作移-1023碼看待真值為-1023+1024；尾數(shù)（不計(jì)符號(hào)位）有52位小數(shù)，另加1位整數(shù)隱藏位，所以尾數(shù)絕對(duì)值為1.02.0 2-52，有效位數(shù)p=53。 最大絕對(duì)值為最大階碼與最大尾數(shù)絕對(duì)值的組合，最小絕對(duì)值為最小階碼與最小尾數(shù)絕對(duì)值的組合。代入相關(guān)公式后得最終結(jié)果如下表。32位64位±最大絕對(duì)值±(1-2-24)·2129±(1-2-53)·21025±最小絕對(duì)值±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) 符號(hào)位不變，（階碼 63）×4 + 127；尾數(shù)左規(guī)，除去最高位；(3) 符號(hào)位不變，（階碼 127）/ 4 + 63；尾數(shù)補(bǔ)最高位，按除法余數(shù)右移若干位，左補(bǔ)0。2.11 從地址的整數(shù)倍位置開(kāi)始訪問(wèn)20% |字節(jié)8位|浪費(fèi)8位|半字16位|單子32位2.5% |半字16位|半字16位|半字16位|半字16位|30% |雙字64位|2.13 已知10條指令使用頻度，求3種編碼方法的平均碼長(zhǎng)與信息冗余量。(1)此問(wèn)中的“最優(yōu)Huffman編碼法”實(shí)際是指碼長(zhǎng)下限，即信源的平均信息量熵，代公式得H=2.9566。(2)Huffman編碼性能如下表； 公式：(

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

20、4.61%7.59%2.142.15(1) 15條/63條/64條 (2) 14條/126條/128條說(shuō)明：每種擴(kuò)展劉兩種組合：0000共1411011110 0000001110 111111 000000共26共26-11110 擴(kuò)充碼1110 111111 1110 1111101110 111111 11111111110000001111 111111 000000共26共26-11111 擴(kuò)充碼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個(gè)周期，循環(huán)體前后浪費(fèi)3個(gè)周期，故能節(jié)省97個(gè)指令周期（3）start: move as,r1Mov num,r2Dec r2Dec r1Inc r1Loop:move (r1),ad-as(r1)Bgt loopInc r1Dec r2HaltNum:N第三章難點(diǎn)：3.1.4.2交叉訪問(wèn)存儲(chǔ)器重點(diǎn)：地址映射及替換算法P146 3.2 虛擬存儲(chǔ)器 P174 3.3 Cache3.2 T=H1T1+H2T2+H3T3；S=S1+S3+S2；

22、C=(C1S1+C2S2+C3S3)/S3.3 直接代公式計(jì)算存儲(chǔ)層次性能指標(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，也對(duì)。3.73.9 =2,Nv:虛存大?。籒p：頁(yè)面大??；Nd

23、：頁(yè)表存儲(chǔ)字大?。?）4KB/4B=1K，故而二級(jí)頁(yè)表空間為：4GB/1K=4MB，需4MB/4KB=1024頁(yè)；4MB/1K=4KB，故一級(jí)頁(yè)表空間為4KB，即1頁(yè)（3）一級(jí)頁(yè)表必須駐立主存3.10 令TM為主存的平均訪問(wèn)時(shí)間，TD為硬盤(pán)的訪問(wèn)時(shí)間，則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,故實(shí)頁(yè)號(hào)p=23-12=11；（3）快表：多用戶虛頁(yè)號(hào)（U+P）+

24、實(shí)頁(yè)號(hào)p，即16+11=17（4）每個(gè)實(shí)頁(yè)在頁(yè)表中都存在一行與之對(duì)應(yīng)，故共需211=2K=2048（個(gè)存儲(chǔ)字）；慢表包括主存頁(yè)號(hào)（實(shí)頁(yè)號(hào)）+裝入位及其它標(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入入中入換中換中換換中中向頁(yè)地址流回看，最后出現(xiàn)的為待換出的OPT222222*4*4*4*22263

25、333*33333*3*3*50%1*55555555入入中入換中換中中換中中向頁(yè)地址流后看，最遠(yuǎn)才訪問(wèn)的為待換出的注：最好的辦法是堆棧模擬。3.15 欲知可能的最高命中率及所需的最少主存頁(yè)數(shù)，較好的辦法是通過(guò)“堆棧模擬法”，求得命中次數(shù)隨主存頁(yè)數(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次頁(yè)面訪問(wèn)代表連續(xù)1024次該頁(yè)內(nèi)存儲(chǔ)單元訪問(wèn)時(shí)，后1023次單

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

27、如耍再增加分配給該道程序的實(shí)頁(yè)數(shù)，只會(huì)導(dǎo)致實(shí)存空間的利用率下降所以，只要分別求出分配給該道程序不同實(shí)頁(yè)數(shù)時(shí)的頁(yè)命中率，找出達(dá)到最高命中率時(shí)所分配的最少實(shí)頁(yè)數(shù)即可 既然LRU替換算法是堆棧型的替換算法，對(duì)虛頁(yè)地址流只需要用堆棧處理技術(shù)處理一次，就可以同時(shí)求出不同實(shí)頁(yè)數(shù)時(shí)各自的命中率這樣，可以大大減少模擬的工作量。解答 用堆棧對(duì)頁(yè)地址流處理一次的過(guò)程見(jiàn)表46所示，其中H表示命中。頁(yè)地址流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實(shí) n=2頁(yè) 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替換算法替換，對(duì)該程序至少應(yīng)分配4個(gè)實(shí)頁(yè)如果只分配3個(gè)實(shí)頁(yè)，其頁(yè)命中率只有212，太低：而分配實(shí)頁(yè)數(shù)多于4頁(yè)后，其頁(yè)命中率不會(huì)再有提高所以，分配給該程序4個(gè)實(shí)頁(yè)即可，其可能的最高命中串為H7123.15加1題 一個(gè)二級(jí)存儲(chǔ)層次，采用全相聯(lián)映象和最久沒(méi)有使用算法，實(shí)存共5頁(yè)，為2道程序分享，頁(yè)地址流分別如下P1 = 1 2 3 4 1 3 2 1P2 = 1 2 3 4 2 2 3 3試作2個(gè)實(shí)存分

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個(gè)分配方案的命中率情況表如下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ū)號(hào)：；格式為：|1E|1G|1B|4W|（2）cache格式為：|組號(hào)g：1位|組內(nèi)塊號(hào)：1位|塊內(nèi)地址W：4| 虛存 實(shí)頁(yè)0123虛組0 00 1 實(shí)存1虛組1 2·0 實(shí)組02 3·1虛3虛組2 4·2 實(shí)組1頁(yè)4 5·35虛組3 66 77(a) 虛頁(yè)集合與實(shí)頁(yè)集合的對(duì)應(yīng)關(guān)系 (b) 對(duì)應(yīng)關(guān)系表（為有關(guān)系）(3)(4)通過(guò)作“實(shí)存狀況圖”模擬各虛塊的調(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此問(wèn)最容易出錯(cuò)的地方是忽略“組相聯(lián)”地址約束，將虛頁(yè)裝錯(cuò)實(shí)組。另外沒(méi)有及時(shí)標(biāo)注“*”號(hào)也容易導(dǎo)致淘汰對(duì)象錯(cuò)誤。（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)問(wèn)，Hcell=(12×16-8)/(12×16)95.8%3.21（2）一個(gè)主存周期從主存中取出數(shù)據(jù)為：4體交叉×體字長(zhǎng)4B=16B，故cache塊大小為16B，共1KB/16B=64塊，每組4塊，故共64/4=16組，故cache的地址為：|組號(hào)g：4位|組內(nèi)塊號(hào)b：2位|塊內(nèi)地址W：4位|（1）主存的塊與cache的組是直接映像，故主存每區(qū)有16塊（cache共16組），每塊大小16B，共有區(qū)數(shù)1MB/16

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

34、 FIFO改為L(zhǎng)RU (5) FIFO改為L(zhǎng)RU，井增大主存容量(頁(yè)數(shù)) (6) FIFO改為L(zhǎng)RU，且增大頁(yè)面大小 試分析上述各建議對(duì)命中率的影響情況。 解答 (1) 增大輔存容量，對(duì)主存命中率H不會(huì)有什么影響。因?yàn)檩o存容量增大，并不是程序空間的增大，程序空間與實(shí)主存空間的容量差并未改變。所以，增大物理輔存容量，不會(huì)對(duì)主存的命中率H有什么影響。 (2) 如果主存容量(頁(yè)數(shù))增加較多時(shí)，將使主存命中率有明顯提高的趨勢(shì)。但如果主存容量增加較少，命中率片可能會(huì)略有增大，也可能不變，甚至還可能會(huì)有少許下降。這是因?yàn)槠淝疤崾敲新蔋太低。如果主存容量顯著增加，要訪問(wèn)的程序頁(yè)面在主存中的機(jī)會(huì)會(huì)大大增加，

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

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

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

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