計算機系統(tǒng)系統(tǒng)最終答案

1.11層次結構：按照計算機語言從低級到高級的次序，把計算機系統(tǒng)按功能劃分成多級層次結構，每一層以一種不同的語言為特征。這些層次依次為：微程序機器級，傳統(tǒng)機器語言機器級，匯編語言機器級，高級語言機器級，應用語言機器級等。計算機系統(tǒng)由硬件/器件和軟件組成，按功能劃分成多級層次結構第0級級和第1級是具體實現(xiàn)機器指定功能的中央控制部分。第2級是傳統(tǒng)機器語言機器第3級是操作系統(tǒng)機器。第4級是匯編語言機器第5級是高級語言機器第6級是應用語言機器 2計算機系統(tǒng)結構：傳統(tǒng)機器程序員所看到的計算機屬性，即概念性結構與功能特性。 3計算機組成：計算機系統(tǒng)結構的邏輯實現(xiàn)，包含物理機器級中的數(shù)據(jù)流和控制流的組成以及邏輯設計等。 4計算機實現(xiàn)：計算機組成的物理實現(xiàn)，包括處理機、主存等部件的物理結構，器件的集成度和速度，模塊、插件、底板的劃分與連接，信號傳輸，電源、冷卻及整機裝配技術等。 5透明性：在計算機技術中，把這種本來存在的事物或?qū)傩?，但從某種角度看又好像不存在的概念稱為透明性。6由上往下設計：也稱“由頂向低”設計。根據(jù)滿足應用要求，定好面向應用的那個虛擬機器級的特性和工作環(huán)境，再逐級向下設計。由上向下設計師一種串行設計方法，設計周期長，是一種對環(huán)境要求比較穩(wěn)定的專用機設計方法。7由下往上設計：也稱“由底向頂”設計，根據(jù)目前能用的器件，參照、吸收已有各種機器的特點，將微程序機器級和傳統(tǒng)機器級研制出來。然后加配適用的操作系統(tǒng)和編譯系統(tǒng)軟件。該類設計一體式串行設計，同樣會延長設計周期，現(xiàn)在已經(jīng)很少使用。 8系列機：由同一廠家生產(chǎn)的具有相同系統(tǒng)結構、但具有不同組成和實現(xiàn)的一系列不同型號的計算機。 9軟件兼容：一個軟件可以不經(jīng)修改或者只需少量修改就可以由一臺計算機移植到另一臺計算機上運行。差別只是執(zhí)行時間的不同。 10兼容機：由不同公司廠家生產(chǎn)的具有相同系統(tǒng)結構的計算機。 11模擬：用軟件的方法在一臺現(xiàn)有的計算機（稱為宿主機）上實現(xiàn)另一臺計算機（稱為虛擬機）的指令系統(tǒng)。 12仿真：用一臺現(xiàn)有計算機（稱為宿主機）上的微程序去解釋實現(xiàn)另一臺計算機（稱為目標機）的指令系統(tǒng)。 13虛擬機：用軟件實現(xiàn)的機器。 14宿主機：指要安裝虛擬機軟件的計算機。如果A計算機上實現(xiàn)B計算機的指令系統(tǒng)，通常采用解釋方法完成，即B機器的每一條指令用一段A機器的指令進行解釋執(zhí)行，如同A機器上也有B機器的指令系統(tǒng)一樣。A機器成為宿主機，被模擬的B機器成為虛擬機。 15指令流：是指操作過程中涉及到的信息流動。機器執(zhí)行的指令序列 16數(shù)據(jù)流：是一組有序，有起點和終點的字節(jié)的數(shù)據(jù)序列。 17Amdahl定律：當對一個系統(tǒng)中的某個部件進行改進后，所能獲得的整個系統(tǒng)性能的提高，受限于該部件的執(zhí)行時間占總執(zhí)行時間的百分比。Amdahl定律：加速比=（采用改進措施后的性能）/（沒有采用改進措施前的性能） =（沒有采用改進措施前執(zhí)行某任務的時間）/（采用改進措施執(zhí)行某任務的時間） 18CPI：每條指令執(zhí)行的平均時鐘周期數(shù)。CPU時鐘周期數(shù)目/IC 19MIPS：單字長定點指令平均執(zhí)行速度的縮寫，每秒處理的百萬級的機器語言指令數(shù)。每秒百萬條指令數(shù)。=指令條數(shù)/執(zhí)行時間X10^6=時鐘評率/CPIX10^6 20MFLOPS：衡量計算機系統(tǒng)的技術指標。程序中的浮點操作數(shù)/執(zhí)行時間X10^6每秒百萬次浮點數(shù)1.2解：這兒要注意的是第一級是最低的級別，而不是最高的級別。第二級：NKns 第三級：N2Kns 第四級：N3Kns1.3 可以加快操作系統(tǒng)操作命令解釋的速度。同時也節(jié)省了存放解釋操作命令這部分解釋程序所占用的空間。簡化了操作系統(tǒng)機器級的設計。也有利于減少傳統(tǒng)機器級的指令條數(shù)。1.41.5硬件和軟件在實現(xiàn)邏輯功能上是等效的。在原理上用軟件實現(xiàn)的功能完全可以用硬件或固件來實現(xiàn)用硬件實現(xiàn)的功能也可以用軟件進行模擬來完成。但在速度、價格、實現(xiàn)的難易程度上是不同的。對于任何一種功能來說用軟件實現(xiàn)的優(yōu)點是設計容易、修改簡單而且可以減少硬件成本。但其缺點是所實現(xiàn)的功能的速度較慢。用硬件實現(xiàn)的優(yōu)點是速度快、性能高但它修改困難靈活性差。等效：實現(xiàn)邏輯功能，原理上軟件的功能可用硬件或者固件完成，硬件的功能也可以用軟件模擬完成不等效：實現(xiàn)性能上1.6計算機系統(tǒng)結構、計算機組成和計算機實現(xiàn)是3個不同的概念。計算機系統(tǒng)結構是指令系統(tǒng)及其模型；計算機組成是計算機系統(tǒng)結構的邏輯實現(xiàn)；計算機實現(xiàn)是計算機組成的物理實現(xiàn)。它們各自包含不同的內(nèi)容和采用不同的技術，但又有緊密的關系。下面是具體比較：(1)

計算機的系統(tǒng)結構相同，但可采用不同的組成。如IBM370系列

有115、125、135、

158、

168等

由低檔到高檔的多種型號機器。從匯編語言、機器語言程序設計者看到的概念性結構相同，均是由中央處理機/主存，通道、設備控制器，外設4級構成。其中，中央處理機都有相同的機器指令和匯編指令系統(tǒng)，只是指令的分析、執(zhí)行在低檔機上采用順序進行，在高檔機上采用重疊、流水或其它并行處理方式。

(2)相同的組成可有多種不同的實現(xiàn)。如主存器件可用雙極型的，也可用MOS型的;可用VLSI單片，也可用多片小規(guī)模集成電路組搭。

(3)計算機的系統(tǒng)結構不同，會使采用的組成技術不同，反之組成也會影響結構。

如為實現(xiàn)A:=B+CD:=E*F,可采用面向寄存器的系統(tǒng)結構，也可采用面向主存的三地址尋址方式的系統(tǒng)結構。要提高運行速度，可讓相加與相乘并行，為此這兩種結構在組成上都要求設置獨立的加法器和乘法器。但對面向寄存器的系統(tǒng)結構還要求寄存器能同時被訪問，而對面向主存的三地址尋址方式的系統(tǒng)結構并無此要求，倒是要求能同時形成多個訪存操作數(shù)地址和能同時訪存。又如微程序控制是組成影響結構的典型。通過改變控制存儲器中的微程序，就可改變系統(tǒng)的機器指令，改變結構。如果沒有組成技術的進步，結構的進展是不可能的。

綜上所述，系統(tǒng)結構的設計必須結合應用考慮，為軟件和算法的實現(xiàn)提供更多更好的支持，同時要考慮可能采用和準備采用的組

能方便地在低檔機上用簡單便宜的組成實現(xiàn)，又能在高檔機上用復雜較貴的組成實現(xiàn)，這樣，結構才有生命力;組成設計上面決定于結構，下面受限于實現(xiàn)技術。然而，它可與實現(xiàn)折衷權衡。例如，為達到速度要求，可用簡單的組成但卻是復雜的實現(xiàn)技術，也可用復雜的組成但卻是一般速度的實現(xiàn)技術。前者要求高性能的器件，后者可能造成組成設計復雜化和更多地采用專用芯片。組成和實現(xiàn)的權衡取決于性能價格比等因素;結構、組成和實現(xiàn)所包含的具體內(nèi)容隨不同時期及不同的計算機系統(tǒng)會有差異。軟件的硬化和硬件的軟件都反映了這一事實。VLSI的發(fā)展更使結構組成和實現(xiàn)融為一體，難以分開。1.7(1)從指定角度來看，不必要了解的知識稱為透明性概念。模m交叉，√，浮點數(shù)據(jù)，×，P4通道與I/O處理機，×，P4總線寬度，√，陣列運算部件，×，結合型與獨立型通道，√，單總線，√，訪問保護，×，中斷，×，指令控制方式，√，堆棧指令，×，最小編址單位，×，Cache存儲器，√，(2)見下表，“√”為透明性概念，“P”表示相關課文頁數(shù)。指令地址寄存器，×，指令緩沖器，√，時標發(fā)生器，√，條件碼寄存器，×，乘法器，√，主存地址寄存器，√，磁盤，×，先行進位鏈，√，移位器，√，通用寄存器，×，中斷字寄存器，×，1.8見下表，“√”為透明性概念，“P”表示相關課文頁數(shù)。數(shù)據(jù)通路寬度，√，虛擬存儲器，應，Cache存儲器，√，程序狀態(tài)字，×，“啟動I/O”指令，應，“執(zhí)行”指令，×，指令緩沖寄存器，√，1.9見下表，“√”表示都透明，“應”表示僅對應用程序員透明，“×”表示都不透明。1.10但是，要統(tǒng)一高級語言，語言的標準化很重要，但難以在短期內(nèi)解決。1.11解：系列機是指由同一廠家生產(chǎn)并具有相同系統(tǒng)結構的計算機，但具有不同的計算機組成與實現(xiàn)。可行：(1)(3)(4)(6)(7)Sn2010 1Fe不可行：(2)(5)(8)1.12已知Se=20,求作Fe-Sn關系曲線。 將Se代入Amdahl定律得 1.13上式中令Sn=2，解出Fe=10/19≈0.5261.14上式中令Sn=10，解出Fe=18/19≈0.9471.15已知兩種方法可使性能得到相同的提高，問哪一種方法更好。(1)用硬件組方法，已知Se=40，F(xiàn)e=0.7，解出Sn=40/12.7≈3.1496（兩種方法得到的相同性能）(2)用軟件組方法，已知Se=20，Sn=40/12.7，解出Fe=27.3/38≈0.7184（第二種方法的百分比）(3)結論：軟件組方法更好。因為硬件組需要將Se再提高100%（20→40），而軟件組只需將Fe再提高1.84%（0.7→0.7184）。1.161.171.18記f──時鐘頻率，T=1/f──時鐘周期，B──帶寬（Byte/s）。 方案一： 方案二：1.19由各種指令條數(shù)可以得到總條數(shù)，以及各百分比，然后代公式計算。(1)(2)(3)1.201.21(1)(2)1.221.231.24記Tc──新方案時鐘周期，已知CPI=CPIi=1原時間=CPI×IC×0.95Tc=0.95IC×Tc新時間=（0.3×2/3+0.7）×IC×Tc=0.9IC×Tc二者比較，新時間較短。1.28解：原始MFLOPS＝195578/（10.8×106）＝0.018正則化后MFLOPS＝195578/（13.6×106）＝0.014指令正則化后的具體值＝f/CPI＝16.6M/（6×106）＝2.772.2解：注意：位數(shù)用補碼、小數(shù)表示，階碼用移碼、整數(shù)表示。1)最大正尾數(shù)：1－16-62)最小正尾數(shù)：16-13)最小負尾數(shù)：－14)最大負尾數(shù)：－(16-1＋16-6)5)最大階碼：26－16)最小階碼:－267)最大正數(shù)：(1－16-6)*16638)最小正數(shù)：16-1*16-649)最大負數(shù)：-(16-1＋16-6)*16-6410)最小負數(shù)：－166311)浮點零：012)表數(shù)精度：1/2×16-(6-1)13)表數(shù)效率：15/1614)能表示的規(guī)格數(shù)浮點數(shù)個數(shù)：2×15×165×2×26+12.3（忽略P124倒1行～P125第8行文字，以簡化題意）已知2種浮點數(shù)，求性能指標。 此題關鍵是分析階碼、尾數(shù)各自的最大值、最小值。 原圖為數(shù)據(jù)在內(nèi)存中的格式，階碼的小數(shù)點在其右端，尾數(shù)的小數(shù)點在其左端，遵守規(guī)格化要求。 由于尾數(shù)均為原碼，原碼的絕對值與符號位無關，所以最大正數(shù)與最小負數(shù)的絕對值相同，可用“±最大絕對值”回答；最小正數(shù)與最大負數(shù)的絕對值相同，可用“±最小絕對值”回答。 第1小問中，階碼全部位數(shù)為8，作無符號數(shù)看待真值為0～255，作移-127碼看待真值為-127～+128；尾數(shù)（不計符號位）有23位小數(shù)，另加1位整數(shù)隱藏位，所以尾數(shù)絕對值為1.0～2.0–2-23，有效位數(shù)p=24 第2小問中，階碼全部位數(shù)為11，作無符號數(shù)看待真值為0～2047，作移-1023碼看待真值為-1023～+1024；尾數(shù)（不計符號位）有52位小數(shù)，另加1位整數(shù)隱藏位，所以尾數(shù)絕對值為1.0～2.0–2-52，有效位數(shù)p=5332位64位±最大絕對值±(1-2-24)·2±(1-2-53)·2±最小絕對值±2-127±2-1023表數(shù)精度δ2-242-53表數(shù)效率η100%100% 最大絕對值為最大階碼與最大尾數(shù)絕對值的組合，最小絕對值為最小階碼與最小尾數(shù)絕對值的組合。代入相關公式后得最終結果如下表。2.51)設計浮點數(shù)的格式：2-P=10-7.2,P=－log210-7.2=7.2×log210尾數(shù)為24位（隱藏最高位），階碼為7+1位（-128－127）。2)計算：①最大正數(shù)：（1－2-24）×2127②最大負數(shù)：-2-1×2-128③表數(shù)精度：1/2×2-23＝2-24＝10-7.22④表數(shù)效率：50%（如果尾數(shù)采用隱藏位，那么表數(shù)效率為100%）2.61位7位6位00111111333333(1)0.2=0.333333H×160 設階碼為移-63碼（即-26+1 0.2=0.110011001100110011001101B×2-21位8位23位00111110110011001100110011001101 （其中最高有效位需隱藏） 階碼為移-127碼（即-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編碼性能如下表；公式：(3)2/8擴展編碼是8/64/512法的變種，第一組2條指令，碼長為2（1位擴展標志，1位編碼）,第二組8條指令，碼長為4（1位擴展標志，與第一組區(qū)別，加3位編碼），編碼性能如下表；00；01；1***；Huffman編碼2/8擴展編碼3/7擴展編碼平均碼長L2.993.13.2信息冗余量R1.10%4.61%7.59%(4)3/7擴展編碼是15/15/15法的變種，第一組3條指令，碼長為2（共有4種組合，其中3種組合分別代表3條指令，留1種組合作為擴展前綴標志）,第二組7條指令，碼長為5（2位固定的前綴擴展標志，與第一組區(qū)別，加3位編碼，只用其中7種組合），編碼性能如下表。00；01；10；11***（只用7種）；2.141)讓操作的平均長度最短,用Huffman編碼得到的Huffman操作碼編碼是：指令序號使用的頻度Huffman編碼操作碼長度135%002225%012320%102410%110355%1110463%11110572%111115操作碼的平均長度=35%*2+25%*2+20%*2+10%*3+5%*4+3%*5+2%*5=2.352）8位字長的寄存器-寄存器型指令:

已知有8個通用寄存器，用一個3位的地址碼可表示一個通用數(shù)據(jù)寄存器。指令格式：操作碼地址碼1地址碼2操作碼2位地址碼均3位具體的3條指令格式：00xxxxxx01xxxxxx10xxxxxx16位字長的寄存器-存儲器型變址尋址方式指令:已知有8個通用數(shù)據(jù)寄存器，用一個3位的地址碼可表示一個通用數(shù)據(jù)寄存器已知有2個變址寄存器，用一個1位的地址碼可表示一個變址寄存器已知變址范圍不小于正負127，用一個8位的立即數(shù)可以表示一個變址寄存器內(nèi)的偏移量。指令格式：操作碼地址碼1地址碼2立即數(shù)其中操作碼4位地址碼1為3位地址碼2為1位立即數(shù)8位具體4條指令：1100xxxxxxxxxxxx1101xxxxxxxxxxxx1110xxxxxxxxxxxx1111xxxxxxxxxxxx2.15(1)15條/63條/64條(2)14條/126條/128條說明：每種擴展劉兩種組合：0000共14 ……共141101 1110000000 1110111111000000共26共26-11110 …… 擴充碼1110111111共26共26-1 1110111110 1110111111111111 1111000000 1111111111000000共26共26-11111 …… 擴充碼1111111111共26共26-1 1111111110 11111111111111112.18P1172.20向后轉移（1）start:moveas,r1 Movnum,r2 decr1 incr1Loop: move(r1),ad-as(r1) Decr2 Bgtloop Incr1 HaltNum: N(2)N=100，循環(huán)100次，節(jié)省100個周期，循環(huán)體前后浪費3個周期，故能節(jié)省97個指令周期（3）start:moveas,r1 Movnum,r2 Decr2 Decr1 Incr1Loop: move(r1),ad-as(r1) Bgtloop Incr1 Decr2 HaltNum: N第三章難點：3.1.4.2交叉訪問存儲器重點：地址映射及替換算法P1463.2虛擬存儲器 P1743.3Cache3.1解：（1） 當S2>>S1時，平均價格接近C2。（2） ta=h*t1+(1-h)*t2（3） e=1/[h+(1-h)r]（4） 略（5） 當r=100時，h>0.99947（6）P134公式，H’=(H+n-1)/n=(0.96+5D-1)/5D=0.99947計算得：D>15.05，取D=163.2T=H1T1+H2T2+H3T3；S=S1+S3+S2；C=(C1S1+C2S2+C3S3)/S3.3直接代公式計算存儲層次性能指標。(1)74ns，38ns，23.6ns H*t1+(1-h)*t2(2)0.258，0.315，0.424 (c1s(3)T256K<T128K<T64Kc256K>c128K>c64K(4)T*C分別得19.092，11.97，10.0064。答案是256K方案最優(yōu)。//（1）t=ht1+(1–h)t2,cache為64k時，t=0.7*20ns+(1-0.7)*200ns=74ns；cache=128k時，t=38ns；cache=256k時，t=23.6ns（2）按照公式：cache=64k,c=0.2585美元/k字節(jié)；cache=128k,c=0.3152美元/k字節(jié)；cache=256k，c=0.4235美元/k字節(jié)（3）按等效訪問時間由小到大排序，容量分別為：256k，128k，64k按每字節(jié)平均價格由小到大排序，分別為：64k,128k,256k（4）①19.129ns.美元/k字節(jié)；②11.9776ns.美元/k字節(jié)；9.9946ns.美元/k字節(jié)；256k的cache最優(yōu)3.4（1）、由c1*s1+c2*s2≤150000.01*512+0.5*s2≤1500s2≤14.6MB（2）、由t=t1*h+t2*(1-h)40=20*0.95+(1-0.95)*t2t2=420ns3.5已知，其中g=0.1依題意有整理得0.9n≥0.2，解出，向下取整，得15；按另一種題意理解是向上取整，得16，也對。3.7（1）方式一、體號：4位；體內(nèi)地址：20位；方式二、存貯地址：20位；多路選擇器：4位；方式三、體內(nèi)地址：20位；存儲器體號：4位；方式四、高位體號：1位；低位體號：3位；體內(nèi)地址：20位；方式五、高位體號：2位；低位體號：2位；體內(nèi)地址：20位；方式六、體內(nèi)地址：20位；多路選擇器：2位；低位體號：2位；（2）①擴大容量；②比較簡單；③速度比較快；④速度快，容量大；⑤速度快，容量大；⑥提高速度（3）①1；②16；③接近16；④接近8；⑤接近4；⑥接近163.8由P.Budnik和D.J.Kuck提出的方法可知并行存儲體的個數(shù)至少為m=17;再由^(2*p)+1=17得p=2;按公式體號=(2^p)*i+jmodm,體內(nèi)地址=i得出無沖突的訪問圖如下:3.9(1)由公式：g=(log2Nv-log2Np)/(log2Np-log2Nd)得：g=(log24G-log24K)/(log24k-log24)=2,故需用2級頁表；（2）一級頁表存儲容量為1KB，共256個頁面；二級頁表為4K個頁面，共1M。（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.11（1）2、5、9（2）2098、1084、無、0060、1124、無、3116、2128、1124、無（3）2（4）1、3、4、6虛地址虛頁號實頁號頁內(nèi)偏移實地址操作合法性020402502098合法1306031601084非法266006無無無無3586050600060非法43740311001124非法546164無無無無6168013803116非法746002642128合法83200311001124合法948564無無無無3.12(1)U=log264=6;P=log21024=10;D=log24K=12用戶號6位,虛頁號10位,頁內(nèi)偏移地址12位(2)總數(shù)為log28M=23;D=log24K=12,故實頁號p=23-1（3）快表：多用戶虛頁號（U+P）+實頁號p，即16+11=27多用戶虛頁號：16位，實頁號：11位（4）每個實頁在頁表中都存在一行與之對應，故共需211=2K=2048（個存儲字）；慢表包括主存頁號（實頁號）+裝入位及其它標志位，即11+1+其他另解：慢表容量：64k個存儲字（26*210），每個字長：裝入位1位＋實頁號11位＝12（5）P159圖3.273.13(1)多用戶虛地址：用戶號-8位；虛頁號-12位；頁內(nèi)偏移地址-10位；實地址格式：實頁號-14位；頁內(nèi)偏移-10位；問題實質(zhì)：（用戶號-8位；虛頁號-12位）->（實頁號：14位）(2)輸入位：20（8+12）；輸出位：5；(3)相等比較電路的位數(shù)：20；(4)快表存儲字長度：68位，每組分為：多用戶虛頁號：20位；實頁號：14位；注意：有2套獨立的比較電路(5)略（P160）3.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*22263333*33333*3*3*50%1*55555555入入中入換中換中中換中中向頁地址流后看，最遠才訪問的為待換出的注：最好的辦法是堆棧模擬。3.15欲知可能的最高命中率及所需的最少主存頁數(shù)，較好的辦法是通過“堆棧模擬法”，求得命中次數(shù)隨主存頁數(shù)變化的函數(shù)關系。下圖就是“堆棧模擬圖”，其中“√”表示命中。P=453251323513命中次數(shù)4532513235134532513235145325112354432551224444444n=10n=2√1n=3√√√3n=4√√√√√√√7n=5√√√√√√√7(1)Hmax=7/12≈58.3%(2)n=4(3)當1次頁面訪問代表連續(xù)1024次該頁內(nèi)存儲單元訪問時，后1023次單元訪問肯定是命中的，而第1次單元訪問的命中情況與這1次頁面訪問的命中情況相同。根據(jù)上圖中最高命中情況，共有7次頁命中（折算為7×1024次單元命中），5次頁不命中（折算為5×1023次單元命中，也可寫為5×1024-5），單元訪問總次數(shù)為12×1024，故有：Hcell=(12×1024-5)/(12×1024)=12283/12288≈99.96%改LRU替換算法：[分析]由于LRU替換算法是堆棧型的替換算法，因而隨著分配給該程序的實頁數(shù)增加，實頁命中率只會上升，至少是不會下降的。但是，當實頁數(shù)增加到一定程度之后，其命中率就不會再提高了．如耍再增加分配給該道程序的實頁數(shù)，只會導致實存空間的利用率下降．所以，只要分別求出分配給該道程序不同實頁數(shù)時的頁命中率，找出達到最高命中率時所分配的最少實頁數(shù)即可．既然LRU替換算法是堆棧型的替換算法，對虛頁地址流只需要用堆棧處理技術處理一次，就可以同時求出不同實頁數(shù)時各自的命中率．這樣，可以大大減少模擬的工作量。[解答]用堆棧對頁地址流處理一次的過程見表4．6所示，其中H表示命中。頁地址流453251322513S(1)S(2)S(3)S(4)S(5)S(6)45325132251345325l3325145325l1325443255132n=1實n=2頁n=3數(shù)n=4n=5HHHHHHHHHHHHHHHHHH模擬結果表明，使用LRU替換算法替換，對該程序至少應分配4個實頁．如果只分配3個實頁，其頁命中率只有2／12，太低：而分配實頁數(shù)多于4頁后，其頁命中率不會再有提高．所以，分配給該程序4個實頁即可，其可能的最高命中串為H＝7／12．3.15加1題一個二級存儲層次，采用全相聯(lián)映象和最久沒有使用算法，實存共5頁，為2道程序分享，頁地址流分別如下P1=12341321P2=12342233試作2個實存分配方案，分別使2道程序滿足(1)命中率相同；(2)命中次數(shù)之和最大。P1=12341321命中次數(shù)N(1)12341321123413212341312244n1=10n1=20n1=3√√2n1=4√√√√4解：分別為2道程序作“堆棧模擬圖”，其中“√”表示命中。P2=12342233命中次數(shù)N(2)12342233123442212334411111n2=1√√2n2=2√√2n2=3√√√√4n2=4√√√√465N(1)+N(2)432N(1)N(2)11+42+33+24+1將兩圖結果綜合，得到4個分配方案的命中率情況表如下n11234N(1)0024n24321N(2)4422N(1)+N(2)4446結論如下(1)命中率相同的方案是n1=3而n2=2；(2)命中次數(shù)之和最大的方案是n1=4而n2=1。3.16（1）、頁地址流為：0，0，1，1，0，3，1，2，2，4，4，4；（2）、頁地址流為：0，0，2，2，1，6，3，4，4，8，9，7；（3）、頁地址流為：0，0，0，0，0，1，0，1，1，1，1，1；（4）、頁面越大，則命中的可能性比較大。3.17設置虛擬存儲器的主要目的是擴展存儲空間，設置Cache的主要目的是提高訪問速度。兩種存儲系統(tǒng)實現(xiàn)時的主要差別有：（1）、實現(xiàn)方法不同，Cache全部用硬件實現(xiàn)，而虛擬存儲器則以軟件為主，硬件為輔；（2）、兩級存儲器的速度比不一樣；（3）、頁塊大小不一樣，Cache系統(tǒng)一般1字——16字，虛擬存儲系統(tǒng)則為1KB——16KB；（4）、等效存儲容量不同，Cache等效于主存，而虛擬存儲系統(tǒng)等效于虛存；（5）、不命中進處理方式不同，Cache系統(tǒng)采用等待方式，而虛擬系統(tǒng)采用任務切換。3.18直接映象的優(yōu)點在于最簡單、最直接，不需要聯(lián)想查找，不需要頁面替換算法，因而成本較低且速度較高。缺點是命中率較低，而且它還禁止并行虛擬地址轉換。全相聯(lián)的優(yōu)點是提供最大的靈活性，可以實現(xiàn)較好的塊替換策略，以減少塊的沖突。缺點是檢索過程昂貴，需要的硬件成本比較高。組相聯(lián)可以提供較好的性能價格比，替換策略可以更加經(jīng)濟地實現(xiàn)，聯(lián)想檢索實現(xiàn)容易，設計靈活可以獲得更高的高速緩存的命中率。。段相聯(lián)的優(yōu)點在于，實現(xiàn)各種塊替換算法比較靈活和對有限數(shù)量區(qū)段標記完成全聯(lián)想檢索比較經(jīng)濟。位選擇組相聯(lián)映象在塊表中存放參與相聯(lián)比較的只有主存地址中的區(qū)號，而沒有組內(nèi)塊號B，使B實現(xiàn)起來比組相聯(lián)要容易.直接映象<段相聯(lián)<位選擇<組相聯(lián)<全相聯(lián)。直接映射不需要聯(lián)想查找，不需要頁面替換算法；區(qū)段映射只對有限數(shù)量區(qū)段標記，所以完成全聯(lián)想檢索比較經(jīng)濟；組聯(lián)想在做k路聯(lián)想檢索中，由于k實際上是相當小的，因此比全聯(lián)想要經(jīng)濟得多；全聯(lián)想標記長度大，檢索耗時。3.19（1）區(qū)號：；格式為：|1E|1G|1B|4W|（2）cache格式為：|組號g：1位|組內(nèi)塊號：1位|塊內(nèi)地址W：4| 虛存 實頁 0 1 2 3虛組0 0 0 √ √ 1 實存 1 √ √ 虛組1 2 · 0 實組0 2 √ √ 3 · 1 虛 3 √ √虛組2 4 · 2 實組1 頁 4 √ √ 5 · 3 5 √ √ 虛組3 6 6 √ √ 7 7 √ √ (a)虛頁集合與實頁集合的對應關系 (b)對應關系表（√為有關系）主存與Cache中各個塊的映象對應關系：B6B2B4B1B4B6B3B0B4B5B7B3C2C3C0C1C0C2C3C1C0C1C2C3FIFO中Cache的塊命中率：3/12＝25%LFU中Cache的塊命中率：4/12＝33.3%改為全相聯(lián)映象后：FIFO中塊命中率：4/12＝33.3%LFU中塊命中率：3/12＝25%這時Cache的命中率：1－8/(16×12)＝95.8%3.20(1)主存8×8＝64MB，每個存儲體為8M/16K＝512區(qū)，每區(qū)16K/(32×4)＝128組。區(qū)號：9位，組號：7位，組內(nèi)塊號：2位，偏移地址：5位，存儲體號：3位(2)Cache中每塊32Byte，共16K/32＝512塊，512/4＝128組組號：7位，組內(nèi)塊號：2位，塊內(nèi)偏移：5位。(3)相聯(lián)目錄表共有128行。(4)相聯(lián)目錄表如下：192119211921E，B1beE，B2be……E，B8be其中，（E，B）表示區(qū)號和區(qū)內(nèi)組號，b表示組內(nèi)塊號，e表示有效位。比較電路的位數(shù)：19（其中1為為有效位標志）P181圖3.463.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×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ū)才在塊表中有對應記錄。（4）每個比較電路的位數(shù)12位（5）P183圖3.483.23引1：在一個頁式二級虛擬存貯器中，采用FIFO算法進行頁面替換，發(fā)現(xiàn)命中率H太低，因此有下列建議：(1)增大輔存容量(2)增大主存容量(頁數(shù))(3)增大主、輔存的頁面大小(4)FIFO改為LRU(5)FIFO改為LRU，井增大主存容量(頁數(shù))(6)FIFO改為LRU，且增大頁面大小試分析上述各建議對命中率的影響情況。[解答](1)增大輔存容量，對主存命中率H不會有什么影響。因為輔存容量增大，并不是程序空間的增大，程序空間與實主存空間的容量差并未改變。所以，增大物理輔存容量，不會對主存的命中率H有什么影響。(2)如果主存容量(頁數(shù))增加較多時，將使主存命中率有明顯提高的趨勢。但如果主存容量增加較少，命中率片可能會略有增大，也可能不變，甚至還可能會有少許下降。這是因為其前提是命中率H太低。如果主存容量顯著增加，要訪問的程序頁面在主存中的機會會大大增加，命中率會顯著上升。但如果主存容量(頁數(shù))增加較少，加上使用的FIFO替換算法不是堆棧型的替換算法，所以對命中率的提高可能不明顯，甚至還可能有所下降。(3)因為前提是主存的命中率H很低，在增大主、輔存的頁面大小時，如果增加量較小，主存命中率可能沒有太大的波動。因為FIFO是非堆棧型的替換算法，主存命中事可能會有所增加，也可能降低或不變。而當頁面大小增加量較大時，可能會出現(xiàn)兩種相反的情況。當原頁面大小較小時，在顯著增大了頁面大小之后，一般會使主存命中率有較大提高。但當原頁面大小已較大時，再顯著增大頁面大小后，由于在主存中的頁面數(shù)過少，將會使主存命中宰繼續(xù)有所下降。(4)頁面替換算法由FIFO改為LRU后，一般會使主存的命中率提高。因為LRU替換算法比FIFO替換算法能更好地體現(xiàn)出程序工作的局部性特點。然而，主存命中率還與頁地址流、分配給主存的實頁數(shù)多少等有關，所以，主存命中率也可能仍然較低，沒有明顯改進。(5)頁面替換算法由FIFO改為LRU，同時增大主存的容量(頁數(shù))，一般會使主存命中率有較大的提高。因為LRU替換算法比FIFO替換算法更能體現(xiàn)出程序的局部性，又由于原先主存的命中宰太低，現(xiàn)增大主存容量(頁數(shù))，一般會使主存命中率上升。如果主存容量增加量大些，主存命中率H將會顯著上升。(6)FIFO改為LRU，且增大頁面大小時，如果原先頁面大小很小，則會使命中率顯著上升；如果原先頁面大小已經(jīng)很大了，因為主存頁數(shù)進一步減少而使命中率還會繼續(xù)有所下降。引2：采用組相聯(lián)映象、LRU替換算法的Cache存貯器，發(fā)現(xiàn)等效訪問速度不高，為此提議：(1)增大主存容量(2)增大Cache中的塊數(shù)(塊的大小不變)(3)增大組相聯(lián)組的大小(塊的大小不變)（4）增大塊的大?。ńM的大小和Cache總容量不變）（5）提高Cache本身器件的訪問速度試問分別采用上述措施后，對等效訪問速度可能會有什么樣的顯著變化？其變化趨勢如何？如果采取措施后并未能使等效訪問速