計算機系統(tǒng)結構課后答案unit4

1、第四章課后題1、 設二級虛擬存儲器的TA1=10A(-7)s 、TA2=10A(-2)s, 為使存儲層次的訪問效率 e 達到最大值的80% 以上，命中率H 至少要求達到多少？實際上這樣高的命中率是很難達到的，那么從存儲層次上如何改進？解： Te=1/H+(1-H)r且r=TA2/TA1二 H 至少達到99.9%這樣的命中率很難達到，可在二級存儲器間加一層電子磁盤，降低r,從而降低對 H 的要求。2、 程序存放在模 32 單字交叉存儲器中，設訪存申請隊的轉(zhuǎn)移概率 入為 25%, 每個存儲周期能訪問到的平均字數(shù)。當模數(shù)為 16 呢？由此你可得到什么結 論？求解： B= 1-(1-入)Am /入由入

2、 =0.25,m=32 求得： B=4-4*(3/4F32=4同理， m=16 時，B=4-4*(3/4F16=3.96由此可看出，當轉(zhuǎn)移概率入為 25% 比較大時，采用模期能訪問的平均字數(shù)非常相近。就是說，此時，提高模數(shù)32 與模 16 的每個存儲周m 對提高主存實際頻寬已不顯著。實際上，模數(shù)m 的進一步增大，會因工程實現(xiàn)上的問題，導致實際性能反而可能比模16 的還要低，且價格更高。所以模數(shù)m 不宜太大。對于入 為25% 的情況，可以計算機出m=8時，其B 已經(jīng)接近于3.6 了。3、 設主存每個分體的存取周期為2 ys,寬度為4 個字節(jié)。采用模m 多分體 交叉存取，但實際頻寬只能達到最大頻寬

3、的0.6 倍?，F(xiàn)要求主存實際頻寬為4M B/S, 問主存模數(shù)m 應取多少方能使兩者速度基本適配？其中m 取2 的幕。解：由題意已知存取周期Tm=2*10A(-6)s, 寬度 W=4B,B 實=0.6Bm=4*2A20B/S,Bm=W*m/Tm=6.99*10A6B/Sm=Bm*Tm/W=6.99*10A6*2*10A-6/4=3.495所以 m 取 4 能滿足要求P.S. 微秒 ( 百萬分之一秒)1 ys=10A-6s 計量單位中的M(兆)是10 的6 次方，見到M 自然想起要在該數(shù)值的后邊續(xù)上六個0，即擴大一百萬倍。在二進制中，MB也表示到了百萬級的數(shù)量級，但1 MB不正好等于1000000

4、字節(jié)，而是1048576字節(jié)，即1MB = 2E+20 Bytes =1048576Bytes。4、某虛擬存儲器共8 個頁面，每頁1024個字，實際主存為4096個字，采用頁表法進行地址映象。映象表的內(nèi)容如下表1 所示。實頁號 裝入位3 11 12 03 02 11 00 10 0表 1虛頁號 實頁號裝入位0 3 11 1 12 2 03 3 02 11 00 10 0表 2列出會發(fā)生頁面失效的全部虛頁號；解：根據(jù)頁表法列出表2，當裝入位為0 時，即為頁面失效，再找出相對應的虛頁號即可。會發(fā)生頁面失效的全部虛頁號為：2,3,5,7按以下虛地址計算主存實地址： 0，3728 ，1023 ，102

5、4 ，2055 ，7800 ，409 6，6800 。解：虛頁號 =IJ 虛地址 /頁面大小 _丨實地址 =(實頁號 *頁面大小 ) + (虛地址 - 虛頁號 *頁面大小 )虛地址03728102310242055780040966800虛頁號0 30 127 4 6實頁號3 33 120 2 0裝入位1 01 100 1 1實地址 3072372840951024205563220486565、一個段頁式虛擬存儲器。虛地址有2 位段號、 2 位頁號、 11 位頁內(nèi)位移 ( 按字編址 ) ，主存容量為32K 字。每段可有訪問方式保護，其頁表和保護位如下表所示。此地址空間中共有多少個虛頁？解：

6、2Nv 頁，而 Nv= 用戶虛頁號 =段號 S+頁號 P此地址空間中共有2ANv=2 A(2+2)=16 個虛頁6、設某程序包含5 個虛頁，其頁地址為4，5，3，2，5，1，3，2，2，5，1，3。當使用LRU 算法替 換時，為獲得最高命中率，至少應分配給該程序幾個實頁？其可能的最高命中率為多少？7.采用頁式管理的虛擬存儲器，分時運行兩道程序。其中，程序X 為DO 50 I=1,3B(I)=A(I)-C(I)IF(B(I) LE ? 0)GOTO 40D(I)=2*C(I)-A(I)IF(D(I) EQ ? 0)GOTO 5040 E(I)=0CONTINUE Data: A=(-4,+2,0

7、)C=(-3,0,+1) 每個數(shù)組分別放在不同的頁面中;而程序 Y 在運行過程中，其數(shù)組將依次用到程序空間的第3,5,4,2,5,3,1,3,2,5,1,3,1,5,2頁。如果采用LRU 算法，實存卻只有8 頁位置可供存放數(shù)組之用。試問為這兩首程序的數(shù)組分別分配多少個實頁最為合適？為什么？解答：分別分配給程序X 和 Y 的數(shù)組 4 個實頁最為合適。根據(jù)題意，程序X 依次調(diào)用數(shù)組A,C,B,B,E, A,C,B,B,C,A,D,D,E, A,C,B,B,E中 的數(shù)據(jù)。設程序X 中的數(shù)組A,B,C,D,E 分別存放于程序空間的第1,2,3,4,5 頁，則程序的頁地址流為：1，3，2，2，5， 1，

8、3，2，2，3，1，4，4，5， 1，3，2，2，5。分析使用LRU 算法對程序X 的頁地址流進行堆棧處理的過程可知，分配給程序X 的數(shù)組 5 個實頁最為合適 ； 分析使用 LRU 算法對程序 Y 的頁地址流進行堆棧處理的過程可知，分配給程序Y 的數(shù)組 4 個實頁最為合適。但實存只有 8 頁位置可供存放數(shù)組之用，所以，分別分配給程序X 和丫的數(shù)組個實頁。note:分時運行在微觀上是串行的，就是說，分時運行時把時間劃分為若干時間片，每個程序輪流占用時間片；在宏觀上是并行的，就是說，每個程序在一個時間片內(nèi)并不能運行完。總的來看，是同時運行的，所以兩個程序分配的實頁和不能大于參8?？迹荷厦娴腇ORT

9、RAN 源代碼轉(zhuǎn)成C 后main() int A=-4,2,0; int C=-3,0,1; for (i=0,i3,i+) Bi=Ai-Ci; if (Bi0) Ei=0;else Di=2*Ci-Ai;if (Di0) Ei=0;設一個按位編址的虛擬存儲器， 它應可對應 1K 個任務，但在一段較長時間內(nèi)，一般只有4 個任務在使用，故用容量為4 行的相聯(lián)寄存器組硬件來縮短被變換的虛地址中的用戶位位數(shù)；每個任務的程序空間最大可達4096 頁，每頁為512 個字節(jié)，實主存容量為2 人 20 位；設快表用按地址訪問存儲器構成，行數(shù)為32,快表的地址是經(jīng)散列形成；為減少散列沖突，配有兩套獨立相等比較

10、電路。請設 計該地址變換機構，內(nèi)容包括：畫出其虛、實地址經(jīng)快表變換之邏輯結構示意圖；相聯(lián)寄存器組中每個寄存器的相聯(lián)比較位數(shù)；相聯(lián)寄存器組中每個寄存器的總位數(shù)；散列變換硬件的輸入位數(shù)和輸出位數(shù)；每個相等比較器的位數(shù)；快表的總容量 ( 以位為單位 ) 。解:依題意得知：虛地址為34 位，其中用戶號為10 位( 對應 1K 的任務 ) 、虛頁號12 位( 每個 任務4096 頁) 、頁內(nèi)位移12 位( 每頁 512 字節(jié)，512 字節(jié) =512*8=1024*4=2A12)實地址為20 位，其中實頁號8 位，頁內(nèi)位移12 位( 與虛頁頁內(nèi)位移對應 ) 相聯(lián)寄存器的作用：把 10 位的用戶號轉(zhuǎn)換為2

11、位的 ID ( 因為一般只有 4 個任務 在使用 ) ，并把 ID 與虛地址的虛頁號合并到快表中查實頁號。快表的作用：相當于頁表，即虛頁號對實頁號的對應關系。但又有所簡化(原因 是如果用用戶號和虛頁號與實頁號對應，前者就有22 位，現(xiàn)改進后虛頁號只有14 位了)相聯(lián)寄存器組中每個寄存器的相聯(lián)比較位數(shù)為 10( 與虛地址中的用戶號寬度對應 )(3) 相聯(lián)寄存器組中每個寄存器的總數(shù)為12( 用戶號寬度+ID 寬度 )散列變換硬件的輸入位數(shù)為 14 位( 虛頁號寬度 +相聯(lián)寄存器中 ID 的寬度 ) ， 輸出位數(shù)為 8 位( 與主存中的實頁號寬度對應 )每個相等比較器的位數(shù)=ID+ 用戶虛頁號 nv

12、=2+12=14(6)快表的總容量：32 行*( 14( 輸入位數(shù))+8( 輸出位數(shù) )位)。*2=32*22*29.考慮一個920 個字的程序，其訪問虛存的地址流為46，618，370，490 ，492，868，916，728 。20，22，208，214 ，1若頁面大小為 200 字，主存容量為 400 字，采用 FIFO 替換算法，請按訪存 的各個時刻，寫出其虛頁地址流，計算主存的命中率；若頁面大小為 100 字，再做一遍；若頁面大小為 400 字，再做一遍；由(1)、(2) 、(3)的結果可得出什么結論？若把主存容量增加到 800 字，按第 (1) 小題再做一遍，又可得出什么結論？解：

13、（1）主存容量400 字，頁面大小200 字，所以主存實頁數(shù)為2； 把地址流轉(zhuǎn)換為頁地址流，以第一個虛地址流轉(zhuǎn)換為頁地址流為例說明：求模公 式為：INT（地址/頁面大?。?，就是把地址整除于頁面大小，得INT（20/200）=0，下同，所以頁地址流為：0,0,1,1,0,3,1,2,2,4,4,3按 FIFO 算法得出替換過程為：0（調(diào)入），0（命中），1（調(diào)入），1（命中）， 0（命中），3（替換 0， 0 比 1 先入隊，所以被替換，下同），1（命中）， 2（替換 1）， 2（命中）， 4（替換 3）， 4（命中）， 3（替換 2） ，所以總共命中 6次。故命中率H=6/12=50%2）方法

14、同（ 1 ） H=25%3）H=50%4） 由以上結論可得， FIFO 算法的條件下，當頁面大小發(fā)生變化時，其命中率變 化是：一開始隨頁面大小增大命中率（第一步與第二步比較），但當頁面大小增到一定時，命中率不再增加（第一步與第三步比較）。（5）命中率為58% ，結論是如果分配給主存容量增加時可以搞高命中率。10. 在一個頁式二級虛擬存儲器中，采用FIFO 算法進行頁面替換，發(fā)現(xiàn)命中率太低，因此有下列建議：（1） 增大輔存容量 ;2） 增大主存容量 （頁數(shù) ）;3） FIFO 改為 LRU;4） FIFO 改為 LRU ，并增大主存容量 （頁數(shù)）；5） FIFO 改為 LRU ，并增大頁面大小。

15、試分析上述各建議對命中率的影響情況。解答：1） 增大輔存容量，對命中率 H 無影響。2） 增大主存容量 （頁數(shù)），可普遍提高命中率。3） FIFO 改為 LRU ，一般可提高命中率。4） FIFO 改為 LRU ，并增大主存容量 （頁數(shù)），一般可使命中率有較大提高。FIFO 改為 LRU ，并增大頁面大小， 如果原來頁面很小， 則會使命中率顯著上 升，如果原來頁面很大，則會使命中率下降。采用組相聯(lián)映象的 Cache 存儲器， Cache 為 1KB , 要求 Cache 的每一塊 在一個主存周期內(nèi)能從主存取得。主存模 4 交叉，每個分體寬為 32 位，總容量 為256KB 。用按地址訪問存儲器

16、構成相聯(lián)目錄表實現(xiàn)主存地址到Cache 地址的 變換，并約定用4 個外相等比較電路。請設計此相聯(lián)目錄表，求出該表之行數(shù)、總位數(shù)及每個比較電路的位數(shù)。解答：設 Cache 地址中的組內(nèi)塊號為 s，相聯(lián)目錄表的行數(shù)是 2A(13-s) ，總位數(shù)是 ( 8+ 2s)*2A(15-s) ，每個比較電路的位數(shù)為 8+s 。剖析：在一個主存周期內(nèi)主存能訪問到的字節(jié)數(shù)為mW=4*32/8=16(Byte)。要求Cach e的每一塊在一個主存周期內(nèi)能從主存取得，所以，Cache 中每塊的塊內(nèi)字數(shù)不能大于 16Bytes 。為了加速調(diào)塊，一般讓每塊的大小等于在一個主存周期內(nèi)主存能訪問到的字數(shù)，即16Bytes

17、。設 Cache 地址中的組內(nèi)塊號為 s，相聯(lián)目錄表的行數(shù) =Cache 地址內(nèi)的組數(shù) Q= Cache 容量 /(每組塊數(shù) *每塊大小 ) =1KB/(S*4*32)=2M3/(2As*2A7)=2A(6-s) 。主存塊數(shù) /Cache 塊數(shù) =256=2*8 ，所以，主存地址中的區(qū)號nd=8 。每個比較電路的位數(shù)=nd+s=nd+s=8+s。相聯(lián)目錄表的總位數(shù)=表中子目錄表的個數(shù)*每個子目錄表的位數(shù)*相聯(lián)目錄表的行數(shù)=4*( nd+s+s)*Q=4*(8+2s)*2A(6-s)=(8+2s)*2A(8-s)。note ：若認為相等比較電路的個數(shù)=組內(nèi)塊數(shù)，則相聯(lián)目錄表的行數(shù)=2A4，每個比

18、較電路的位數(shù) =10，相聯(lián)目錄表的總位數(shù)=12*2 A6。有一個 Cache 存儲器。主存共分 8 個塊 (07),Cache 為 4 個塊 (03), 采用 組相聯(lián)映象，組內(nèi)塊數(shù)為 2 塊，替換算法為近期最少使用算法 (LRU) 。畫出主存、 Cache 地址的各字段對應關系 (標出位數(shù) )圖;畫出主存、 Cache 空間塊的映象對應關系示意圖 ;對于如下主存塊地址流： 1,2,4,1,3,7,0,1,2,5,4,6,4,7,2, 如主存中內(nèi)容一開始未裝入 Cache 中，請列出 Cache 中各塊隨時間的使用狀況 ;對于 (3), 指出塊失效又發(fā)生塊爭用的時刻 ;對于 (3), 求出此期間

19、 Cache 的命中率。解答：(1)主存地址、Cache 地址的各字段的位數(shù)及其對應關系如下圖所示主存塊、 Cache 塊的映象對應關系如下圖所示Cache 中各塊隨時間的使用狀況如下圖所示。 圖中標 *號的是候選替換塊的塊號， H: 命中 ;R: 替換 ;L: 失效。發(fā)生塊失效又發(fā)生塊爭用的時刻有 6、7、9、10、11、 12、14 、15。Cache 的塊命中率 Hc=3/15=0.2 。剖析 :由于主存塊、Cache 塊之間存在上述的映象對應關系，主存的第0、1、4、5 塊 只能映象裝入或替換物理Cache 的第 0、1 塊;主存的第2、3、6、7 塊只能映象裝入或替換物理Cache 的第 2、3 塊。采用組相聯(lián)映象， LRU 替換算法的 Cache 存儲器，發(fā)現(xiàn)等效訪問速度不高，為此建議 :增大主存容量 ;增大 Cache 的塊數(shù) (塊的大小不變 );增大組相聯(lián)組的大小 (塊的大小不變 );增大塊的大小 (組的大小和 Cache 總容量不變 );提高 Cache 本身器件的訪問速度。解答 :(1)增大主存容量對Cache 的訪問時間ta 基本不影響，從而對Cache