計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課后答案unit4

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

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

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

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

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

6、2Nv 頁(yè)，而 Nv= 用戶虛頁(yè)號(hào) =段號(hào) S+頁(yè)號(hào) P此地址空間中共有2ANv=2 A(2+2)=16 個(gè)虛頁(yè)6、設(shè)某程序包含5 個(gè)虛頁(yè)，其頁(yè)地址為4，5，3，2，5，1，3，2，2，5，1，3。當(dāng)使用LRU 算法替 換時(shí)，為獲得最高命中率，至少應(yīng)分配給該程序幾個(gè)實(shí)頁(yè)？其可能的最高命中率為多少？7.采用頁(yè)式管理的虛擬存儲(chǔ)器，分時(shí)運(yùn)行兩道程序。其中，程序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) 每個(gè)數(shù)組分別放在不同的頁(yè)面中;而程序 Y 在運(yùn)行過(guò)程中，其數(shù)組將依次用到程序空間的第3,5,4,2,5,3,1,3,2,5,1,3,1,5,2頁(yè)。如果采用LRU 算法，實(shí)存卻只有8 頁(yè)位置可供存放數(shù)組之用。試問(wèn)為這兩首程序的數(shù)組分別分配多少個(gè)實(shí)頁(yè)最為合適？為什么？解答：分別分配給程序X 和 Y 的數(shù)組 4 個(gè)實(shí)頁(yè)最為合適。根據(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ù)。設(shè)程序X 中的數(shù)組A,B,C,D,E 分別存放于程序空間的第1,2,3,4,5 頁(yè)，則程序的頁(yè)地址流為：1，3，2，2，5， 1，

8、3，2，2，3，1，4，4，5， 1，3，2，2，5。分析使用LRU 算法對(duì)程序X 的頁(yè)地址流進(jìn)行堆棧處理的過(guò)程可知，分配給程序X 的數(shù)組 5 個(gè)實(shí)頁(yè)最為合適 ； 分析使用 LRU 算法對(duì)程序 Y 的頁(yè)地址流進(jìn)行堆棧處理的過(guò)程可知，分配給程序Y 的數(shù)組 4 個(gè)實(shí)頁(yè)最為合適。但實(shí)存只有 8 頁(yè)位置可供存放數(shù)組之用，所以，分別分配給程序X 和丫的數(shù)組個(gè)實(shí)頁(yè)。note:分時(shí)運(yùn)行在微觀上是串行的，就是說(shuō)，分時(shí)運(yùn)行時(shí)把時(shí)間劃分為若干時(shí)間片，每個(gè)程序輪流占用時(shí)間片；在宏觀上是并行的，就是說(shuō)，每個(gè)程序在一個(gè)時(shí)間片內(nèi)并不能運(yùn)行完?？偟膩?lái)看，是同時(shí)運(yùn)行的，所以兩個(gè)程序分配的實(shí)頁(yè)和不能大于參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;設(shè)一個(gè)按位編址的虛擬存儲(chǔ)器， 它應(yīng)可對(duì)應(yīng) 1K 個(gè)任務(wù)，但在一段較長(zhǎng)時(shí)間內(nèi)，一般只有4 個(gè)任務(wù)在使用，故用容量為4 行的相聯(lián)寄存器組硬件來(lái)縮短被變換的虛地址中的用戶位位數(shù)；每個(gè)任務(wù)的程序空間最大可達(dá)4096 頁(yè)，每頁(yè)為512 個(gè)字節(jié)，實(shí)主存容量為2 人 20 位；設(shè)快表用按地址訪問(wèn)存儲(chǔ)器構(gòu)成，行數(shù)為32,快表的地址是經(jīng)散列形成；為減少散列沖突，配有兩套獨(dú)立相等比較

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

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

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

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

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

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

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

17、。設(shè) Cache 地址中的組內(nèi)塊號(hào)為 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ū)號(hào)nd=8 。每個(gè)比較電路的位數(shù)=nd+s=nd+s=8+s。相聯(lián)目錄表的總位數(shù)=表中子目錄表的個(gè)數(shù)*每個(gè)子目錄表的位數(shù)*相聯(lián)目錄表的行數(shù)=4*( nd+s+s)*Q=4*(8+2s)*2A(6-s)=(8+2s)*2A(8-s)。note ：若認(rèn)為相等比較電路的個(gè)數(shù)=組內(nèi)塊數(shù)，則相聯(lián)目錄表的行數(shù)=2A4，每個(gè)比

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

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