計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)總復(fù)習(xí)習(xí)題PPT學(xué)習(xí)教案

1、會計(jì)學(xué)1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)總復(fù)習(xí)習(xí)題計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)總復(fù)習(xí)習(xí)題2001.9.12第1頁/共147頁3eeenonSFFTTS)1 (1其中：Sn 全局加速比； To 原執(zhí)行時(shí)間（old）； Tn 新執(zhí)行時(shí)間（new）； Se 被改進(jìn)部分的局部加速比； Fe 被改進(jìn)部分原執(zhí)行時(shí)間占原來總時(shí)間的百分比。第2頁/共147頁4eeenoneeeoneeooSFFTTSSFFTTFFTT)1 (1 )1 ( )1 (根據(jù)加速比定義，有：操作加快，總時(shí)間降為改進(jìn)之后由于其中部分，間可寫為：改進(jìn)之前程序運(yùn)行總時(shí)第3頁/共147頁5 Sn 極限 2 = 211eF 極限 1 = 111eF Fe=Fe2 Fe=Fe

2、1 1.0 （設(shè) Fe2 Fe1） 0.0 1.0 Se圖 1.2 Amdahl 定律的圖形 從圖1.2可以看出，增大Se和Fe對Sn都有提升作用；但當(dāng)Fe固定時(shí)，一味增大Se對Sn的作用會越來越不顯著。第4頁/共147頁作作1.12 假定利用增加向量模塊來提高計(jì)算機(jī)的運(yùn)假定利用增加向量模塊來提高計(jì)算機(jī)的運(yùn)算速度。計(jì)算機(jī)處理向量的速度比其通常的運(yùn)算速度。計(jì)算機(jī)處理向量的速度比其通常的運(yùn)算要快算要快20倍，將可用向量處理部分所花費(fèi)的時(shí)倍，將可用向量處理部分所花費(fèi)的時(shí)間占總時(shí)間的百分比稱為可向量化百分比。間占總時(shí)間的百分比稱為可向量化百分比。 （1）求出加速比）求出加速比S和向量化百分比之間的關(guān)系

3、和向量化百分比之間的關(guān)系式式作作1.13 （2）當(dāng)要得到加速比為當(dāng)要得到加速比為2時(shí)的可向量化百時(shí)的可向量化百分比分比F為多少？為多少？作作1.14 （3）為了獲得在向量模式所得到的最大為了獲得在向量模式所得到的最大加速比的一半，可向量化百分比加速比的一半，可向量化百分比F為多少？為多少？第5頁/共147頁FFFS*192020)20/()1 (153.01910)20/()1(12FFF(1)第6頁/共147頁95.01918)20/()1(110FFF第7頁/共147頁作作1.17 假設(shè)高速緩存假設(shè)高速緩存Cache工作速度為主存的工作速度為主存的5倍，倍，且且Cache被訪問命中的概率為

4、被訪問命中的概率為90，則采用，則采用Cache后后，能使整個(gè)存儲系統(tǒng)獲得多高的加速比？，能使整個(gè)存儲系統(tǒng)獲得多高的加速比？57.328.015/9.0)9.01(1oePTTS解：解：fe=0.9 ，re=5第8頁/共147頁題題1.1 某計(jì)算機(jī)系統(tǒng)同時(shí)采用兩種措施改進(jìn)性能某計(jì)算機(jī)系統(tǒng)同時(shí)采用兩種措施改進(jìn)性能，使得兩個(gè)功能部件的性能分別提高到原來的，使得兩個(gè)功能部件的性能分別提高到原來的re1倍和倍和re2 ，這兩個(gè)部件在運(yùn)行時(shí)使用的時(shí)間，這兩個(gè)部件在運(yùn)行時(shí)使用的時(shí)間比例分別為比例分別為fe1和和fe2 。試分析系統(tǒng)性能提高的。試分析系統(tǒng)性能提高的總體加速比。總體加速比。111121/)1

5、(1eeeeeeprfrfffS解解:第9頁/共147頁CPI是衡量CPU執(zhí)行指令效率的重要指標(biāo)。讓我們先考慮一個(gè)標(biāo)準(zhǔn)測速程序的全部執(zhí)行時(shí)間Te和其中所有第i種指令的累計(jì)時(shí)間Ti，易知的加權(quán)平均值。為所有，它表明）（或者寫為）（的關(guān)系與一式，可以得到比較上面第一式與最后寫另一方面，我們又可以，iniiiniiiniiiniiiniieniiiiieCPICPICPIICICCPICPIICCPIICCYCLECPIICCYCLECPIICTTICICfCYCLECYCLECPIICTCYCLECPIICT CPICPI)()( 1 其中： 11i1111第10頁/共147頁12。，主要用于向量

6、計(jì)算機(jī)條數(shù)每次浮點(diǎn)運(yùn)算所需指令；，主要用于標(biāo)量計(jì)算機(jī)MIPSMFLOPSCPIfCYCLECPIICICTICMIPSe666101010例題：P10，例1.1例1.5。 P33，題12 ，題13 ，題14 。第11頁/共147頁第12頁/共147頁55.1)08.0215.0232.0245.01 ()(411iniNiiIICPICPI8 .251055. 1104010666CPIfMIPSC)(875. 31040/155. 11065msTCPIITCNCPU第13頁/共147頁作作1.201.20 某工作站采用時(shí)鐘頻率為某工作站采用時(shí)鐘頻率為15MHz15MHz、處理速率為、處理速

7、率為10MIPS10MIPS的處理機(jī)來執(zhí)行一個(gè)巳知混合程序。假定每次的處理機(jī)來執(zhí)行一個(gè)巳知混合程序。假定每次存儲器存取為存儲器存取為1 1周期延遲、試問：周期延遲、試問： (1)(1) 此計(jì)算機(jī)的有效此計(jì)算機(jī)的有效CPICPI是多少是多少? ? (2) (2) 假定將處理機(jī)的時(shí)鐘提高到假定將處理機(jī)的時(shí)鐘提高到30MHz30MHz，但存儲器子，但存儲器子 系統(tǒng)速率不變。這樣，每次存儲器存取需要兩個(gè)時(shí)鐘系統(tǒng)速率不變。這樣，每次存儲器存取需要兩個(gè)時(shí)鐘 周期。如果周期。如果3030指令每條只需要一次存儲存取，而另指令每條只需要一次存儲存取，而另 外外5 5每條需要兩次存儲存取，還假定已知混合程序每條需

8、要兩次存儲存取，還假定已知混合程序 的指令數(shù)不變，并與原工作站兼容，試求改進(jìn)后的處的指令數(shù)不變，并與原工作站兼容，試求改進(jìn)后的處 理機(jī)性能。理機(jī)性能。 解解 (1)5 . 11010101510666MIPSfCPIoldold第14頁/共147頁(2) 依題意可知：依題意可知：30%的指令需要一次存儲存取，則的指令需要一次存儲存取，則這些指令在處理器提高時(shí)鐘頻率之后需要增加這些指令在處理器提高時(shí)鐘頻率之后需要增加1個(gè)時(shí)個(gè)時(shí)鐘周期；另外鐘周期；另外5%的指令需要增加的指令需要增加2個(gè)時(shí)鐘周期。個(gè)時(shí)鐘周期。 改進(jìn)后性能提高情況可用改進(jìn)后性能提高情況可用CPU時(shí)間之比表示：時(shí)間之比表示： 9 .

9、12%51%30oldnewCPICPI79.15109 . 1103010666newnewnewCPIfMIPS58. 1/)()(newNnewoldNoldnewCPUoldCPUfICPIfICPITT第15頁/共147頁11. 16421 . 09 . 01)/()1 (1eeeprffS解：解：第16頁/共147頁作作1.121.12 假設(shè)在一臺假設(shè)在一臺40MHz40MHz處理機(jī)上運(yùn)行處理機(jī)上運(yùn)行200 000200 000條條指令的目標(biāo)代碼，程序主要由四種指令組成。根指令的目標(biāo)代碼，程序主要由四種指令組成。根據(jù)程序跟蹤實(shí)驗(yàn)結(jié)果，已知指令混合比和每種指據(jù)程序跟蹤實(shí)驗(yàn)結(jié)果，已知指

10、令混合比和每種指令所需的指令數(shù)如下：令所需的指令數(shù)如下： 指令類型指令類型CPI指令混合百分比算術(shù)和邏輯運(yùn)算算術(shù)和邏輯運(yùn)算160%CacheCache命中的加載命中的加載/ /存儲存儲 218%轉(zhuǎn)移轉(zhuǎn)移 412%CacheCache失效時(shí)訪問主存失效時(shí)訪問主存810%(1)(1)計(jì)算在單處理機(jī)上用上述蹤數(shù)據(jù)運(yùn)行程序的平均計(jì)算在單處理機(jī)上用上述蹤數(shù)據(jù)運(yùn)行程序的平均CPICPI(2)(2)根據(jù)根據(jù)(1)(1)所得所得CPICPI，計(jì)算相應(yīng)的，計(jì)算相應(yīng)的MIPS MIPS 速率和程序的執(zhí)行時(shí)間速率和程序的執(zhí)行時(shí)間第17頁/共147頁24.2)1 .0812.0418.026 .01 ()(411in

11、iNiiIICPICPI86.17102 . 2104010666CPIfMIPSC)(2 .111024.210264015msTCPIITCNCPU第18頁/共147頁20 本章介紹指令系統(tǒng)設(shè)計(jì)中2個(gè)最基本的內(nèi)容：數(shù)據(jù)表示、操作碼優(yōu)化。本章重點(diǎn)本章重點(diǎn) (1) Huffman編碼方法；(2) 等長擴(kuò)展編碼方法（15/15/15法，8/64/512法）；(3) 編碼方法性能指標(biāo)（平均碼長L，信息冗余量R）。第19頁/共147頁2001.9.121第20頁/共147頁22niiilPL1)( 信息冗余量信息冗余量：它表明消息編碼中“無用成分”所占的百分比。%100LHLR第21頁/共147頁2

12、3第22頁/共147頁10000001110.090.300.601.000.1510.0610.030.030.040.050.150.300.40第23頁/共147頁由此可得到哈夫曼編碼如下：由此可得到哈夫曼編碼如下： I1: 0 I2: 10 I3: 110 I4: 11100 I1: 0 I2: 10 I3: 110 I4: 11100 I5: 11101 I6: 11110 I7: 11111 I5: 11101 I6: 11110 I7: 11111 平均碼長平均碼長L L=0.4=0.4* *1+0.31+0.3* *2+0.152+0.15* *3+0.053+0.05* *5

13、+0.045+0.04* *5 5 +0.03 +0.03* *5+0.035+0.03* *5 = 2.205 = 2.20位位 信息冗余量信息冗余量R=(2.20-2.17)/2.20=1.36%R=(2.20-2.17)/2.20=1.36% 指令長度個(gè)數(shù)指令長度個(gè)數(shù)=4=4第24頁/共147頁第25頁/共147頁41 1 1 151 1 1 1 10.03I741 1 1 051 1 1 1 00.03I641 1 0 151 1 1 0 10.04I541 1 0 051 1 1 0 00.05I421 031 1 00.15I320 1 2 1 00.30I220 0100.40I

14、1OP長度長度lihuffman擴(kuò)展編擴(kuò)展編碼碼OP長長度度li操作碼操作碼OP使用哈夫使用哈夫曼編碼曼編碼 頻頻 度度（Pi） 指指 令令平均碼長： 2. 2 2.3第26頁/共147頁例例2.22.2 指令系統(tǒng)共有指令系統(tǒng)共有4242種指令，前種指令，前1515種使用頻率平均種使用頻率平均為為0.050.05，中間，中間1313種使用頻率平均為種使用頻率平均為0.0150.015，最后，最后1414種種使用頻率平均為使用頻率平均為0.0040.004。如何編碼？。如何編碼？00000000 ： 1515種種111011101111 00001111 0000 ： ： 1515種種1111

15、11101111 11101111 1111 00001111 1111 0000 ： ： ： 1515種種1111 1111 11101111 1111 1110解：解：因頻率分布有三種，故因頻率分布有三種，故碼長可有三種；碼長可有三種； 因每段指令數(shù)基本相同，因每段指令數(shù)基本相同，故可采用故可采用等長擴(kuò)展等長擴(kuò)展(4-8-12(4-8-12位位) )， 保留特征碼的每段指令保留特征碼的每段指令數(shù)相同數(shù)相同(15-15-15)(15-15-15)方法。結(jié)方法。結(jié)果如圖所示；果如圖所示； 結(jié)果：采用結(jié)果：采用15-15-1515-15-15擴(kuò)展方法，最后一種編碼用擴(kuò)展方法，最后一種編碼用于擴(kuò)展

16、，每段于擴(kuò)展，每段0000000011101110用于編碼，用于編碼，11111111用于擴(kuò)展用于擴(kuò)展。第27頁/共147頁例例2.32.3 指令系統(tǒng)共有指令系統(tǒng)共有7474種指令，前種指令，前4 4種使用頻率平均種使用頻率平均為為0.120.12，中間，中間1515種使用頻率平均為種使用頻率平均為0.020.02，最后，最后5555種使種使用頻率平均為用頻率平均為0.0040.004。如何編碼？。如何編碼？解：解：同上例方法，同上例方法，碼長可有三種；碼長可有三種； 因每段指令數(shù)成比例因每段指令數(shù)成比例(1(1：4)4)，故可采用，故可采用等長等長擴(kuò)展方法擴(kuò)展方法(3-6-9(3-6-9位位

17、) )擴(kuò)擴(kuò)展展，保留標(biāo)志位方法，保留標(biāo)志位方法，結(jié)果如圖所示；結(jié)果如圖所示； 結(jié)果：采用結(jié)果：采用4-16-64擴(kuò)展方法，編碼第一位用于擴(kuò)展擴(kuò)展方法，編碼第一位用于擴(kuò)展，每段，每段0XX用于編碼，用于編碼，1XX用于擴(kuò)展。用于擴(kuò)展。0 xx 40 xx 4種種1xx 0 xx 161xx 0 xx 16種種1xx 1xx 0 xx 641xx 1xx 0 xx 64種種 4-16-64 4-16-64平均碼長平均碼長 =0.12=0.12* *4 4* *3+0.023+0.02* *1515* *6+0.0046+0.004* *5555* *9=5.229=5.22；第28頁/共147頁例

18、例2.4 2.4 指令系統(tǒng)共有指令系統(tǒng)共有7878種指令，前種指令，前1010種使用頻率平種使用頻率平均為均為0.0490.049，中間，中間1818種使用頻率平均為種使用頻率平均為0.020.02，最后，最后5050種使用頻率平均為種使用頻率平均為0.0030.003。如何編碼？。如何編碼？ 解：解：同上例方法，碼長可有三種；因每段指令數(shù)比同上例方法，碼長可有三種；因每段指令數(shù)比例為例為1 1：2 2：5 5，故不可采用等長擴(kuò)展，采用不等長編，故不可采用等長擴(kuò)展，采用不等長編碼碼( 4-6-10( 4-6-10位位) )較能減少平均碼長。較能減少平均碼長。00000000 ： 1010種種1

19、00110011010 001010 00 ： ： 2020種種1110 111110 111111 00 00001111 00 0000 ： ： ： 6464種種1111 11 11111111 11 1111 第一種采用第一種采用4 4位編碼中前位編碼中前1010種種(00001001)(00001001)； 第二種采用第一種頻率編第二種采用第一種頻率編碼中的后碼中的后5 5種編碼種編碼(10101110)(10101110)與擴(kuò)展的與擴(kuò)展的2 2位共位共2020種編碼；種編碼； 第三種采用第一種頻率編第三種采用第一種頻率編碼中的最后一種碼中的最后一種(1111)(1111)與擴(kuò)與擴(kuò)展的

20、展的6 6位共位共6464種編碼。種編碼。第29頁/共147頁第30頁/共147頁0.010.020.03010.030.06010.060.12010.070.070.14010.260100.300.200.240.44010.5610011第31頁/共147頁位61.291iiilpl第32頁/共147頁位78. 2526. 02)20. 024. 030. 0(91iiilp第33頁/共147頁OP(2位位)R1(3位位)R2(3位位)OP(5位位)R1(3位位)X(2位位)相對位移相對位移d(6位位)(5) 訪主存操作數(shù)地址尋址的最大相對位移量為訪主存操作數(shù)地址尋址的最大相對位移量為

21、64個(gè)字節(jié)個(gè)字節(jié)(-32+31個(gè)字節(jié)個(gè)字節(jié))長指令為寄存器長指令為寄存器-主存型，格式如下：主存型，格式如下：第34頁/共147頁作作2.152.15 某處理機(jī)的指令字長為某處理機(jī)的指令字長為1616位，有雙地址位，有雙地址指令、單地址指令和零地址指令三類，并假設(shè)每指令、單地址指令和零地址指令三類，并假設(shè)每個(gè)地址字段的長度為個(gè)地址字段的長度為1616位。位。（1 1）如果雙地址指令有）如果雙地址指令有1515條，單地址和零地址條，單地址和零地址指令的條數(shù)基本相同，問單地址指令和零地址指指令的條數(shù)基本相同，問單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。令各有多少條？并且為這三類

22、指令分配操作碼。（2 2）如果三類指令的比例為）如果三類指令的比例為1 1：9 9：9 9，問雙地址，問雙地址指令、單地址指令和零地址指令各有多少條？并指令、單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。且為這三類指令分配操作碼。第35頁/共147頁解解：（1 1）雙地址指令）雙地址指令1515條，地址碼：條，地址碼： 0000000011101110單地址指令單地址指令2 26 61 16363條，地址碼：條，地址碼：1111 0000001111 000000 1111 111110 1111 111110零地址指令零地址指令6464條，地址碼：條，地址碼： 1111 11

23、1111 0000001111 111111 000000 1111 111111 111111 1111 111111 111111（2 2）雙地址指令）雙地址指令1414條，地址碼：條，地址碼：0000000011011101單地址指令單地址指令2 26 62 22 2126126條，條， 1110 0000001110 000000 1110 111110 1110 111110 零地址指令零地址指令128128條，地址碼：條，地址碼：1111 111110 0000001111 111110 000000 1111 111111 111111 1111 111111 111111第36

24、頁/共147頁2001.9.138第37頁/共147頁2001.9.139第38頁/共147頁57. 35 . 09 . 05)1 (52112AAAAApTHHTTTTS第39頁/共147頁l例例3.2 假設(shè)高速緩存假設(shè)高速緩存Cache的訪問周期為的訪問周期為50ns，主存的訪問周期為，主存的訪問周期為400ns ，且，且Cache被訪問命中的概率為被訪問命中的概率為95，則采用，則采用Cache后，能使整個(gè)存儲系統(tǒng)等效的訪問后，能使整個(gè)存儲系統(tǒng)等效的訪問周期為多少？獲得多高的加速比？周期為多少？獲得多高的加速比？ 解：解：9 .55 .674002AApTTSnsTHHTTAAA5 .6

25、740005. 05095. 0)1 (21第40頁/共147頁2001.9.142 根據(jù)程序的局部化性質(zhì)，存儲層次機(jī)構(gòu)對用戶文件的管理應(yīng)該劃分成較小的基本調(diào)度單位來進(jìn)行。依劃分標(biāo)準(zhǔn)不同，存在3種存儲層次管理方式。(1)段式管理段式管理(P148)。段是程序中的一個(gè)邏輯單位，可以是一個(gè)程序模塊，或者是一個(gè)數(shù)據(jù)結(jié)構(gòu)。段的長度不一，但段內(nèi)所有數(shù)據(jù)的信息屬性一般是相同的，便于統(tǒng)一進(jìn)行信息保護(hù)。 每段使用獨(dú)立的邏輯地址空間，即都從0開始計(jì)算地址。 段式管理方法的主要缺點(diǎn)是各段長短不一，調(diào)進(jìn)調(diào)出之后容易形成大量不規(guī)則的零碎空間。 段式管理方法的虛實(shí)變換算法是查段表(P150)。第41頁/共147頁200

26、1.9.143(2)頁式管理頁式管理(P151)。頁是系統(tǒng)規(guī)定的固定長度單位。按頁劃分用戶文件可以避免上述零碎空間浪費(fèi)。 我們把用戶文件劃分得到的一個(gè)長度單位稱為“虛頁虛頁”，因?yàn)樗捻撎柺窃谔摰刂房臻g中編排的；實(shí)地址空間按頁的大小劃分得到的一個(gè)長度單位稱為“實(shí)頁實(shí)頁”。 頁式管理方法的主要缺點(diǎn)是按固定長度分出來的同一頁內(nèi)常有不同屬性的信息，不便于信息保護(hù)的實(shí)現(xiàn)。 頁式管理方法的虛實(shí)變換算法是查頁表(P152)。(3)段頁式管理段頁式管理(P153)。它把上述兩種管理方式結(jié)合起來，首先將整個(gè)文件分段，然后在各段內(nèi)分頁，所以有一個(gè)段表和若干個(gè)頁表。其虛實(shí)變換算法是先查段表，查出該段的頁表起始地址

27、再查相應(yīng)的頁表(P154)。 段頁式管理的主要缺點(diǎn)是多查一次表，虛實(shí)變換費(fèi)時(shí)較多，占用空間也較大。 由于段頁式管理方法的最小調(diào)度單位仍是頁，或者說它是分段之后的分頁管理，為了敘述簡單，下面的分析還是以頁式管理為模型。第42頁/共147頁2001.9.144基本術(shù)語：基本術(shù)語： 邏輯地址邏輯地址（又稱為相對地址相對地址、虛地址虛地址）是程序員在編寫和編譯一個(gè)程序模塊時(shí)分配指令和數(shù)據(jù)的空間單位序號，總是從0開始（可以按字節(jié)編址、按CPU字編址等）。邏輯地址的取值范圍稱為邏輯地址空間邏輯地址空間、虛空間虛空間或虛存虛存。 物理地址物理地址（又稱為絕對地址絕對地址、實(shí)地址實(shí)地址）是任一級存儲器為全部存

28、儲單元分配的序號。物理地址的取值范圍稱為物理地址空間物理地址空間、實(shí)空間實(shí)空間或?qū)嵈鎸?shí)存。 從M1到Mn各層都有自己的物理地址空間，而對當(dāng)前執(zhí)行的程序模塊來說，邏輯地址空間只有一個(gè)。 地址映象地址映象方式指的是虛頁集合與實(shí)頁集合的對應(yīng)規(guī)則，或者說是約束關(guān)系。 地址變換地址變換（又叫虛實(shí)變換虛實(shí)變換）指邏輯地址到物理地址的變換過程或者算法。 頁失效頁失效指當(dāng)前被訪問存儲級中沒有所需的信息，也就是不命中現(xiàn)象。 實(shí)頁爭用實(shí)頁爭用又叫實(shí)頁沖突實(shí)頁沖突，指虛頁調(diào)入時(shí)，根據(jù)地址映象方式劃定的實(shí)空間范圍內(nèi)已沒有空閑實(shí)頁的狀況。第43頁/共147頁2001.9.1451.1.頁表占用空間過大問題頁表占用空間過

29、大問題 頁表必須存放在實(shí)存M1里。實(shí)際上，命中情況下的訪存時(shí)間等于查表時(shí)間加上訪問目標(biāo)數(shù)據(jù)的時(shí)間，所以頁表不能放在M2。 頁表占用空間 = 頁表行數(shù) 每行寬度 其中，頁表行數(shù) = 虛存容量 / 頁面大小 以PC機(jī)為例，頁表行數(shù) 60G / 4K = 236 / 212 = 224 1600萬！按每行寬度6字節(jié)估算約需96MB。 減少頁表空間的思路分減少行數(shù)和減少行寬兩類。2.相聯(lián)目錄表方法（P158） 僅保留頁表中已裝入的虛頁記錄。為避免逐行比對，利用相聯(lián)存儲器存放此表，它具有并行比較功能，但價(jià)格遠(yuǎn)高于普通存儲器。3.快慢表方法（P159）4.通過地址映象減少行寬 如下文所示第44頁/共147

30、頁2001.9.1463.3.1 全相聯(lián)(P174) 全相聯(lián)全相聯(lián)就是無約束對應(yīng)，或者說是一個(gè)完全關(guān)系，意思就是一個(gè)虛頁可以調(diào)入任何一個(gè)實(shí)頁。這種關(guān)系可用下頁示意圖(a)、(b)表示。 全相聯(lián)的虛實(shí)變換信息完全來自于變換表，查表過程如圖(c)所示。 全相聯(lián)映象方式使虛頁調(diào)入有最大的選擇范圍，發(fā)生實(shí)頁爭用的可能性最小，調(diào)入/調(diào)出的操作開銷也最少，有利于命中率提高。但這種方式的頁表占用空間和查表時(shí)間開銷都比較大,也就是說實(shí)現(xiàn)成本比較高，在命中情況下花費(fèi)在虛實(shí)變換上的時(shí)間也比較多。 由于頁表必須常駐在實(shí)存中，而主存-輔存層次的實(shí)存（即主存）相對Cache-主存層次的實(shí)存（即Cache存儲器）要低廉一

31、些，所以全相聯(lián)映象方式一般用于主存-輔存層次。第45頁/共147頁2001.9.147 虛存 實(shí)頁0123 00 1 實(shí)存1 202 31虛 3 42頁 4 535 66 77 (a) 虛頁集合與實(shí)頁集合的對應(yīng)關(guān)系 (b) 對應(yīng)關(guān)系表（為有關(guān)系）第46頁/共147頁2001.9.148虛地址虛頁號 P頁內(nèi)偏移量 D實(shí)地址實(shí)頁號 p頁內(nèi)偏移量d實(shí)頁號 裝入位 修改位表項(xiàng) 0 ： ： ： ： ：表項(xiàng) P p1 0 ： ： ：表項(xiàng) 7 ： ：(c) 通過查表進(jìn)行虛實(shí)變換第47頁/共147頁2001.9.149 直接相聯(lián)直接相聯(lián)是一種最強(qiáng)的約束關(guān)系，它規(guī)定每個(gè)虛頁只對應(yīng)唯一的實(shí)頁。為了便于虛實(shí)變換，用

32、求模運(yùn)算作為變換關(guān)系式：將虛頁號對實(shí)頁總數(shù)求模得到實(shí)頁號。實(shí)現(xiàn)起來非常簡單，因?yàn)樵诙M(jìn)制中，任何數(shù)X對2的整次冪n求模等價(jià)于截取X的最低log2n位，如下頁示意圖(c)所示。 例3.3 已知虛頁號 = 7，實(shí)頁總數(shù) = 4，用直接相聯(lián)求實(shí)頁號。解： 可用十進(jìn)制形式求：7 mod 4 = 3； 也可用二進(jìn)制形式求：由于n = 4，所以log2n = 2，取7的二進(jìn)制形式111B的最低2位，得11B，即3。 直接相聯(lián)映象方式不需要借助頁表來進(jìn)行虛實(shí)變換，顯然大大節(jié)省了相應(yīng)的空間與時(shí)間（當(dāng)然頁表中的裝入位和修改位還得保留），但是由于每個(gè)虛頁的選擇范圍太小，實(shí)頁爭用的發(fā)生頻率較高，常出現(xiàn)明明實(shí)存有空閑

33、空間卻不得不調(diào)出一個(gè)現(xiàn)有虛頁以騰出所在實(shí)頁的情況，這使系統(tǒng)的命中率和運(yùn)行效率大大下降。 這種映象方式主要用于一些對實(shí)存價(jià)格非常敏感的Cache-主存層次。第48頁/共147頁2001.9.150 虛存 實(shí)頁0123 00 1 實(shí)存1 202 31虛 3 42頁 4 535 66 77(a) 虛頁集合與實(shí)頁集合的對應(yīng)關(guān)系 (b) 對應(yīng)關(guān)系表（為有關(guān)系）虛地址 虛頁號 1 1 1頁內(nèi)偏移量 D實(shí)地址實(shí)頁號 1 1頁內(nèi)偏移量d(c) 通過求模運(yùn)算進(jìn)行虛實(shí)變換示例第49頁/共147頁2001.9.151 組相聯(lián)映象方式是全相聯(lián)與直接相聯(lián)的一個(gè)折中方案，性能也是二者的折中。具體做法是先將實(shí)存分組，每組內(nèi)

34、有若干實(shí)頁，然后將虛存空間也以同樣大小分組。所有虛組按照直接相聯(lián)方式映射到實(shí)組集合，對應(yīng)的虛實(shí)組之間各頁則用全相聯(lián)映射，如下頁示意圖(a)、(b)所示（設(shè)實(shí)組數(shù)為2）。 由于包含了兩層不同的映射關(guān)系，頁表須按虛組劃分成許多子表。在虛實(shí)變換時(shí)，首先根據(jù)虛頁號所在的虛組號，通過求模運(yùn)算確定實(shí)組號，再按虛組號在相應(yīng)的子表內(nèi)讀出組內(nèi)頁號，拼接在一起就是實(shí)頁號。簡記為“組號計(jì)算、組內(nèi)查表”。如圖(c)所示。 采用組相聯(lián)映象方式時(shí)，每個(gè)虛頁在對應(yīng)實(shí)組范圍內(nèi)有若干映象實(shí)頁可供選擇，實(shí)頁爭用的發(fā)生頻率比直接相聯(lián)要低；另一方面，由于頁表內(nèi)原來存放的實(shí)頁號改成存組內(nèi)頁號，省略了實(shí)組號字段，所以頁表占用空間也減少了

35、。當(dāng)然這兩方面優(yōu)點(diǎn)是互相抵觸的：組內(nèi)頁數(shù)越多，實(shí)存空間劃分的組數(shù)就越少，實(shí)組號字段所占位數(shù)也少，這時(shí)改善實(shí)頁爭用現(xiàn)象的效果較好，而節(jié)省頁表空間的效果較差，反之亦然。實(shí)際使用中可根據(jù)性能要求選取合適參數(shù)。 這種映象方式性價(jià)比較好，在Cache-主存層次中被普遍使用。第50頁/共147頁2001.9.152 虛存 實(shí)頁0123虛組 0 00 1 實(shí)存1虛組 1 20 實(shí)組 02 31虛 3 虛組 2 42 實(shí)組 1頁 4 535虛組 3 66 77 (a) 虛頁集合與實(shí)頁集合的對應(yīng)關(guān)系 (b) 對應(yīng)關(guān)系表（為有關(guān)系）第51頁/共147頁2001.9.153虛地址 虛組號 1 0 組內(nèi)頁號 1 頁內(nèi)

36、偏移量 D實(shí)地址實(shí)組號 0 組內(nèi)頁號 0 頁內(nèi)偏移量 d0 組子表 項(xiàng) 0 ： ： ： 項(xiàng) 1 ： ： ：1 組子表 項(xiàng) 0 ： ： ： 項(xiàng) 1 ： ： ：2 組子表 項(xiàng) 0 ： ： ： 項(xiàng) 1 0 裝入位 1 ：3 組子表 項(xiàng) 0 ： ： ： 項(xiàng) 1 ： ： ：(c) 求模運(yùn)算與分組查表結(jié)合進(jìn)行虛實(shí)變換示例第52頁/共147頁2001.9.154 段相聯(lián)映象方式也是全相聯(lián)與直接相聯(lián)的一個(gè)折中方案。它的分段方法與組相聯(lián)相同，不同的是所有虛段按照全相聯(lián)方式映射到實(shí)段集合，對應(yīng)的虛實(shí)段之間各頁則用直接相聯(lián)映射（因?yàn)樘搶?shí)段大小相同，所以實(shí)際上是一一對應(yīng)），如下頁示意圖(a)、(b)所示（設(shè)實(shí)段數(shù)為2

37、）。 段相聯(lián)的虛實(shí)變換與組相聯(lián)類似，不過可以通過計(jì)算來確定的部分不是在段外，而是在段內(nèi)，即頁表內(nèi)只儲存各虛頁對應(yīng)的實(shí)段號，段內(nèi)頁號則從虛頁號中簡單直接復(fù)制，拼接在一起就是實(shí)頁號，簡記為“段號查表、段內(nèi)復(fù)制”。如圖 (c)所示。 段相聯(lián)映象方式的虛實(shí)段內(nèi)頁號對應(yīng)關(guān)系是固定的，每個(gè)虛頁在調(diào)入時(shí)可以選擇的只是實(shí)段號。由于虛實(shí)段大小相同，所以虛段號比實(shí)段號位數(shù)多，也就意味著“多少”的映射（組相聯(lián)是等量映射），其實(shí)頁爭用的發(fā)生頻率比組相聯(lián)要高。在節(jié)省頁表存儲空間方面，性能與組相聯(lián)差不多。第53頁/共147頁2001.9.155 虛存 實(shí)頁0123虛段 0 00 1 實(shí)存1虛段 1 20 實(shí)段 02 31

38、虛 3虛段 2 42 實(shí)段 1頁 4 535虛段 3 66 77(a) 虛頁集合與實(shí)頁集合的對應(yīng)關(guān)系 (b) 對應(yīng)關(guān)系表（為有關(guān)系）第54頁/共147頁2001.9.156虛地址 虛段號 1 0 段內(nèi)頁號 1 頁內(nèi)偏移量 D實(shí)地址實(shí)段號 0 段內(nèi)頁號 1 頁內(nèi)偏移量 d0 段子表 項(xiàng) 0： ： ： 項(xiàng) 1： ： ：1 段子表 項(xiàng) 0： ： ： 項(xiàng) 1： ： ：2 段子表 項(xiàng) 0： ： ： 項(xiàng) 10 裝入位 1 ：3 段子表 項(xiàng) 0： ： ： 項(xiàng) 1： ： ：(c) 查表求實(shí)段號進(jìn)行虛實(shí)變換示例第55頁/共147頁2001.9.157 在多用戶或多進(jìn)程并發(fā)環(huán)境下，由于機(jī)器中同時(shí)保存并交替運(yùn)行多個(gè)

39、程序模塊，各模塊中的相同虛頁號會發(fā)生混淆。這時(shí)從CPU發(fā)出的虛地址還需要在前面拼接上一個(gè)“當(dāng)前用戶號”字段，形成“多用戶虛地址”，如下圖所示(參見P154)。 在虛實(shí)變換時(shí)，上面所說的各種查表操作之前還得先去查一個(gè)“段表基址寄存器組”或“頁表基址寄存器組”的小表格(P150，P152)，確定現(xiàn)在該查哪一張段表或頁表。這個(gè)小表格建立在CPU里，讀寫時(shí)間很短。 當(dāng)前用戶號 虛段號 虛頁號 頁內(nèi)偏移量 第56頁/共147頁2001.9.158 上面所講的地址映象方式是在虛頁調(diào)入時(shí)的“選址”規(guī)則，而地址變換方法則是命中時(shí)獲得實(shí)地址的手段。 不命中時(shí)需要增加的操作就是首先調(diào)出一頁，調(diào)出之后再調(diào)入稱為 “

40、替換”。 替換算法要解決的是選擇調(diào)出對象的問題。 替換算法的目的是在發(fā)生實(shí)頁爭用（即根據(jù)地址映象方式，將要調(diào)入的虛頁被允許進(jìn)入的所有實(shí)頁均被其它虛頁占用）時(shí)，選擇將來不太可能使用或者使用最晚的虛頁作為調(diào)出對象，以騰出一個(gè)實(shí)頁來。第57頁/共147頁2001.9.159(1)隨機(jī)算法RAND 在比較范圍內(nèi)任取一頁作為淘汰頁；(2)先進(jìn)先出算法FIFO 在比較范圍內(nèi)選取調(diào)入最早的一頁作為淘汰頁；(3)最不經(jīng)常使用算法LFU 在比較范圍內(nèi)選取最近單位時(shí)間內(nèi)使用次數(shù)最少的一頁作為淘汰頁；(4)最不接近使用算法LRU 在比較范圍內(nèi)選取最后一次使用離現(xiàn)在最久的一頁作為淘汰頁；(5)最優(yōu)替換算法OPT 在比

41、較范圍內(nèi)選取下一次使用時(shí)間離現(xiàn)在最久的一頁作為淘汰頁。第58頁/共147頁60例如 LRU 算法（其中*號表示被選中的淘汰頁）：已訪問次數(shù) t012345678910被訪問虛頁號無1215413424命中總次數(shù)0空11111*111*221空空222*444*444實(shí)存空間使用情況（實(shí)頁號為 0、1、2）2空空空空555*333*3*操作名稱初態(tài)(空)調(diào)入調(diào)入命中調(diào)入替換命中替換命中替換命中4 次被訪問實(shí)頁號0102102101第59頁/共147頁提示：注意頁表中虛、 實(shí)頁對應(yīng)關(guān)系頁表虛頁號虛頁號 實(shí)頁號實(shí)頁號 裝入位裝入位 0 3 1 1 1 1 2 2 0 3 3 0 4 2 1 5 1

42、0 6 0 1 7 0 0第60頁/共147頁第0頁01023第1頁10242047第2頁20483071第3頁30724095第4頁40965119第5頁51206143第6頁61447167第7頁7168-8191解：解：頁號與地址對應(yīng)關(guān)系頁號與地址對應(yīng)關(guān)系虛地址虛地址1023，虛頁號為，虛頁號為0，頁內(nèi)位移，頁內(nèi)位移為為1023；根據(jù)虛頁號查頁表得知實(shí)；根據(jù)虛頁號查頁表得知實(shí)頁號為頁號為3，且裝入位為，且裝入位為1。主存實(shí)地址主存實(shí)地址PA=3072+1023=4095虛地址虛地址6800，虛頁號為，虛頁號為6，頁內(nèi)位移，頁內(nèi)位移為為656；根據(jù)虛頁號查頁表得知實(shí)頁；根據(jù)虛頁號查頁表得知

43、實(shí)頁號為號為0，且裝入位為，且裝入位為1。主存實(shí)地址主存實(shí)地址PA=0+656=656虛頁號虛地址虛頁號虛地址 / 1024第61頁/共147頁 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 主存實(shí)地址查頁表（已裝入）直直接接dp125CH 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 0 單用戶的虛地址PD0A5CH解：解：第62頁/共147頁 0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 查頁表（未裝入）單用戶的虛地址頁面失效，無對應(yīng)的主存實(shí)地址。PD直直接接1A5CH解：解：用戶的虛頁并未裝入主存中，當(dāng)執(zhí)行該虛頁用戶的虛頁并未裝入主存中，

44、當(dāng)執(zhí)行該虛頁程序時(shí)，找不到對應(yīng)的實(shí)頁。程序時(shí)，找不到對應(yīng)的實(shí)頁。第63頁/共147頁相等比較位數(shù)？相等比較位數(shù)？相等寄存器位數(shù)？相等寄存器位數(shù)？快表行數(shù)？快表行數(shù)？快表每行的位數(shù)？快表每行的位數(shù)？用戶數(shù)？用戶數(shù)？每個(gè)用戶虛頁數(shù)？每個(gè)用戶虛頁數(shù)？每頁大??？每頁大小？如何減少散列沖突如何減少散列沖突？快表為何采用兩組快表為何采用兩組？相等比較的作用？相等比較的作用？224212=4K212=4KB15位30位64行24+24位9位第64頁/共147頁假若一計(jì)算機(jī)的主存儲器按假若一計(jì)算機(jī)的主存儲器按64塊組織，塊大小塊組織，塊大小為為8個(gè)字，高速緩存有個(gè)字，高速緩存有8塊。試按下述要求畫圖塊。試按下

45、述要求畫圖回答問題?；卮饐栴}。（1）畫出全相聯(lián)映像示意圖、指定標(biāo)記字段）畫出全相聯(lián)映像示意圖、指定標(biāo)記字段和主存地址格式。和主存地址格式。（2）畫出直接映像示意圖、指定標(biāo)記字段和）畫出直接映像示意圖、指定標(biāo)記字段和主存地址格式。主存地址格式。（3）畫出）畫出2路組相聯(lián)映像示意圖、指定標(biāo)記字段路組相聯(lián)映像示意圖、指定標(biāo)記字段和主存地址格式。和主存地址格式。例例 3.6第65頁/共147頁b0b1b7 解解：（1）全相聯(lián)映像）全相聯(lián)映像標(biāo)記標(biāo)記6位的高速緩存位的高速緩存B7B8B9 B1B0B56B57B63 主存儲器主存儲器（塊號）標(biāo)記（塊號）標(biāo)記（6位）字（位）字（3位）位） 行號（行號（3位

46、）位） 字（字（3位）位）主存地址主存地址緩存地址緩存地址 標(biāo)記標(biāo)記第66頁/共147頁b0b1b7 （2）直接映像）直接映像標(biāo)記標(biāo)記3位的高速緩存位的高速緩存主存儲器主存儲器行號行號L 字字w主存地址主存地址緩存地址緩存地址 標(biāo)記標(biāo)記 B7B8B9 B1B0B56B57B63 區(qū)區(qū)0區(qū)區(qū)7區(qū)號區(qū)號E（標(biāo)記）（標(biāo)記） 塊號塊號B 字字W3位3位3位3位3位第67頁/共147頁（3）2路組相聯(lián)映像路組相聯(lián)映像標(biāo)記標(biāo)記4位的高速緩存位的高速緩存主存儲器主存儲器主存地址主存地址緩存地址緩存地址 B3B4B5B2B1B0B60B61B63 B62區(qū)區(qū)0區(qū)區(qū)15區(qū)號區(qū)號E（標(biāo)記）（標(biāo)記） 組號組號G 字

47、字W4位2位3位1位3位b0b1b7b2b3b4b5b60組組1組組2組組3組組組號組號g 行號行號L 字字w2位第68頁/共147頁 例例 3.7 有有1K個(gè)任務(wù)，短期內(nèi)只有個(gè)任務(wù)，短期內(nèi)只有4個(gè)用戶，個(gè)用戶，每個(gè)用戶程序空間可達(dá)每個(gè)用戶程序空間可達(dá)4096頁，每頁頁，每頁512B，主存地址長度為主存地址長度為20位，虛實(shí)地址經(jīng)快表變換，位，虛實(shí)地址經(jīng)快表變換，問相關(guān)設(shè)計(jì)：問相關(guān)設(shè)計(jì)： (1) (1) 實(shí)頁位數(shù)實(shí)頁位數(shù) ？（2 2）每個(gè)相聯(lián)寄存器的相聯(lián)比較位數(shù)）每個(gè)相聯(lián)寄存器的相聯(lián)比較位數(shù) （3 3）每個(gè)相聯(lián)寄存器的總位數(shù)）每個(gè)相聯(lián)寄存器的總位數(shù) （4 4）散列變換硬件的輸入和輸出位數(shù)）散列

48、變換硬件的輸入和輸出位數(shù) （5 5）每個(gè)相等比較器的位數(shù)為）每個(gè)相等比較器的位數(shù)為 （6 6）快表的總?cè)萘浚┛毂淼目側(cè)萘?第69頁/共147頁l3.7 解：解：（1）可有可有1K個(gè)任務(wù)，短期內(nèi)只有個(gè)任務(wù)，短期內(nèi)只有4個(gè)用戶，個(gè)用戶， 指示用戶號的地址字段指示用戶號的地址字段U=10位；位；ID=2位；位；又又每個(gè)用戶程序空間可達(dá)每個(gè)用戶程序空間可達(dá)4096頁，頁，P=12, 每頁每頁512B，512512* *8= 4096 8= 4096 位位 D=( (9+3) )=12位位；又又主存地址長度為主存地址長度為20位，位， 實(shí)頁號實(shí)頁號p=20-12=8p=20-12=8位位（2 2）每個(gè)相

49、聯(lián)寄存器的相聯(lián)比較位數(shù)為）每個(gè)相聯(lián)寄存器的相聯(lián)比較位數(shù)為U=10U=10位；位；（3 3）每個(gè)相聯(lián)寄存器的總位數(shù)為）每個(gè)相聯(lián)寄存器的總位數(shù)為U+ID=12U+ID=12位；位；（4 4）散列變換硬件的輸入和輸出位數(shù)為）散列變換硬件的輸入和輸出位數(shù)為1414位和位和4 4位位（5 5）每個(gè)相等比較器的位數(shù)為）每個(gè)相等比較器的位數(shù)為P+ID=12+2=14P+ID=12+2=14位；位；（6 6）快表的總?cè)萘繛椋┛毂淼目側(cè)萘繛?616(12+2+8)(12+2+8)2=7042=704（位）（位）第70頁/共147頁用戶號用戶號U 虛頁號虛頁號P 頁內(nèi)位移頁內(nèi)位移D多用戶的虛地多用戶的虛地址址34

50、位實(shí)頁實(shí)頁p 頁內(nèi)位移頁內(nèi)位移d主 存 實(shí) 地址20位8位12位12位12位10位散列變換散列變換相等？相等？14位4位16行直接P+IDP+IDppU1U2U3U300011011虛實(shí)地址經(jīng)快表變換的邏輯示意圖虛實(shí)地址經(jīng)快表變換的邏輯示意圖第71頁/共147頁第72頁/共147頁主存地址主存地址cache地址地址區(qū)號區(qū)號 組號組號 塊號塊號 字字W1位1位2位1位2位組號組號 塊號塊號 字字w1位解：解：B3B4 B2B1B0B7B5B6主存儲器主存儲器 組0組1區(qū)0區(qū)13位B4 B7B5B6區(qū)7 第73頁/共147頁時(shí)間時(shí)間 t 1 2 3 4 5 6 7 8 9 10 11 12 13

51、14 15 16字地址流字地址流（2路組相聯(lián)路組相聯(lián)FIFO）調(diào)調(diào)進(jìn)進(jìn)調(diào)調(diào)進(jìn)進(jìn)調(diào)調(diào)進(jìn)進(jìn)替替換換替替換換替替換換替替換換命命中中命中命中1次次組0組1替替換換替替換換替替換換1114 1450195689 89 89 8920*50*17171911175617 1719191450142014 14*89*891 14 50 89 20 17 19 56 19 11 14 43 15 16 9 17替替換換1756*43171614*191411*19174317*151943*161519 916 1519* 9151 1*調(diào)調(diào)進(jìn)進(jìn)替替換換替替換換替替換換第74頁/共147頁2001.9.1

52、76 (1) 容量：S=S2 （理論上） (2) 單價(jià)：（美分/bit）2021212121221121lim1ccSSccSSSSScSccSS它的最小值是第75頁/共147頁2001.9.177 命中率：反映被訪問數(shù)據(jù)事先已在M1的發(fā)生概率 等效訪問時(shí)間：命中時(shí)的訪問時(shí)間為T1，不命中時(shí)的訪問時(shí)間為T2，等效訪問時(shí)間則是它們的概率均值10211HNNNH，21)1 (THTHT1%100limTTH第76頁/共147頁78訪問效率e受H和r的影響（參見右圖）：。，ereH e r = 11.0 r = 20.5 r = 100.10.0 0 1 HH 和 r 對 e的作用是鄰級速度比）。（

53、，其中rTTre11012HrrrHHTHTHTTTe)1 (1)1 (1)1 (2111第77頁/共147頁2001.9.179 這里所說的“預(yù)取”技術(shù)，并不是根據(jù)對程序執(zhí)行的未來趨勢進(jìn)行猜測以提前調(diào)入數(shù)據(jù)，而僅僅是在發(fā)生不命中情況時(shí)把調(diào)入1個(gè)數(shù)據(jù)字改為調(diào)入1個(gè)數(shù)據(jù)塊的策略。根據(jù)程序的局部化原理，在當(dāng)前使用數(shù)據(jù)周圍的其它數(shù)據(jù)未來被使用的幾率大于遠(yuǎn)處數(shù)據(jù)，所以該數(shù)據(jù)塊中被提前調(diào)入的鄰近數(shù)據(jù)很可能成為未來的命中點(diǎn)，從而提高命中率。 采用這種預(yù)取技術(shù)后新的命中率為其中：H 原命中率（即按照不命中時(shí)取入1字的策略）； H 新命中率（即按照不命中時(shí)取入1塊的策略）； n 每塊數(shù)據(jù)平均被訪問次數(shù)。nnH

54、H1第78頁/共147頁2001.9.180 按照定義，原不命中率 ，新不命中率 ，并且有 。由于預(yù)取使得每塊數(shù)據(jù)中的不命中次數(shù)由n次降低到1次，所以有 。此式可改寫為 ，整理得 。2121NNNH1212NNNH2121NNNN221NnN nnHH1第79頁/共147頁2001.9.181 Cache-主存層次的主要作用是提高訪問速度，系統(tǒng)的等效速度應(yīng)高于主存（即M2）的原有速度，兩個(gè)速度之比稱為加速比。 增加中間層對e的影響rHHTHTHTTTMMSp/)1 (1)1 (212222等效時(shí)間時(shí)間速度等效速度第80頁/共147頁第81頁/共147頁解解:（1）當(dāng)存儲系統(tǒng)的訪問效率為）當(dāng)存儲

55、系統(tǒng)的訪問效率為0.5時(shí)，由表達(dá)式時(shí)，由表達(dá)式122111/)1 (1)1 (AAAAAAATTHHTHHTTTTe可求出命中率為10/60)1 (15 . 011HH8 . 01H等效訪問周期為)(202 . 0608 . 01011nsTHHTTmccc或由5 . 010111TTTTTecAA得)(201nsT 第82頁/共147頁（2）當(dāng)存儲系統(tǒng)的訪問效率提高到）當(dāng)存儲系統(tǒng)的訪問效率提高到0.94時(shí)，命中率時(shí)，命中率應(yīng)該提高到應(yīng)該提高到H210/60)1 (194. 022HH987. 02H等效訪問周期應(yīng)提高為)(64.10)987. 01 (60987. 0102nsT或由94.

56、010221TTTTTecAA得)(64.101nsT 第83頁/共147頁（3）為了使存儲系統(tǒng)的訪問效率由0.5提高到0.94，塊大小應(yīng)為B個(gè)字。則有nnHH112在上式中代入相關(guān)參數(shù)，可求出4BBBHH41412其中n為Cache的塊大小與數(shù)據(jù)重復(fù)使用次數(shù)的乘積，H1是原來的命中率，H是塊大小增加后的命中率。第84頁/共147頁2001.9.186 虛擬存儲器與Cache的主要區(qū)別(P173表3.4) Cache的主要組成與工作流程(P173圖3.38)第85頁/共147頁87(1) 并行存儲系統(tǒng)原理；(2) 存儲層次的原理及5項(xiàng)性能指標(biāo)；(3) 存儲層次的3種管理方式；(4) 4種地址映

57、象與地址變換方式；(5) 5種替換算法；(6) 堆棧型替換算法；(7) 主存-輔存層次與Cache-主存層次的特點(diǎn)；第86頁/共147頁2001.9.188 輸入輸出系統(tǒng)輸入輸出系統(tǒng)是計(jì)算機(jī)系統(tǒng)中實(shí)現(xiàn)各種輸入輸出任務(wù)的資源總稱。它包括各種輸入輸出設(shè)備、相關(guān)的管理軟件等等。由于輸入輸出設(shè)備的特殊工作性質(zhì)使其數(shù)據(jù)吞吐率通常遠(yuǎn)低于主機(jī)，設(shè)計(jì)輸入輸出系統(tǒng)就是要建立數(shù)據(jù)交換的最佳方案，使雙方都能高效率地工作。 本章重點(diǎn)是中斷優(yōu)先級管理、通道流量設(shè)計(jì)。第87頁/共147頁2001.9.1894.1.1 程序控制I/O方式4.1.2 中斷I/O方式4.1.3 DMA方式4.1.4 通道方式4.1.5 I/O

58、處理機(jī)方式第88頁/共147頁2001.9.190 中斷是為實(shí)時(shí)任務(wù)優(yōu)先獲得處理機(jī)資源而采用的一種調(diào)度技術(shù)，當(dāng)系統(tǒng)中存在多個(gè)中斷源時(shí)必須根據(jù)實(shí)時(shí)性強(qiáng)弱設(shè)定優(yōu)先順序，這也被稱為中斷的分級。為了兼顧中斷響應(yīng)的時(shí)效與配置的靈活，通常采用兩套機(jī)制結(jié)合組成中斷優(yōu)先序管理體系。 (1)硬件響應(yīng)優(yōu)先序：未被屏蔽的幾個(gè)中斷源同時(shí)提出申請時(shí)，CPU選擇服務(wù)對象的順序。它由硬件電路實(shí)現(xiàn)，用戶不能修改。如P226圖4.11所示。 (2)軟件服務(wù)優(yōu)先序：在各中斷服務(wù)程序開頭，用軟件設(shè)置自己的中斷屏蔽字（在主程序中也設(shè)置）。以此改變實(shí)際服務(wù)順序(P230)。 例如某個(gè)硬件響應(yīng)優(yōu)先級高的中斷源，其中斷服務(wù)程序執(zhí)行中屏蔽了

59、自身，而開放了某個(gè)硬件響應(yīng)優(yōu)先級比它低的中斷源，后者就可以在前者剛開放中斷時(shí)就打斷它，從而在實(shí)際上先得到服務(wù)。 中斷服務(wù)過程示意圖如P231圖4.14所示。 由于常規(guī)用戶主程序?qū)μ幚頇C(jī)的需求緊迫性最低，所以它的中斷屏蔽字是“全部開放”。 (3)實(shí)例分析：屏蔽字表、中斷服務(wù)過程圖。 例4.1（P230倒數(shù)第8行開始）第89頁/共147頁91(1)定義： 通道處理機(jī)（簡稱通道）是隸屬于主處理機(jī)的輸入輸出專用協(xié)處理機(jī)。(2)特點(diǎn)： 有一套輸入輸出功能很強(qiáng)的專用指令系統(tǒng)； 與主處理機(jī)共享主存，存放相應(yīng)的程序和數(shù)據(jù)； 一個(gè)通道可以連接多臺外部設(shè)備； 主處理機(jī)可用啟動I/O指令來啟動一個(gè)通道； 當(dāng)通道訪存

60、與主處理機(jī)沖突時(shí)，存控部件賦予通道較高的優(yōu)先權(quán)； 通道程序執(zhí)行完畢自動轉(zhuǎn)入休眠狀態(tài)，同時(shí)向主處理機(jī)發(fā)出一個(gè)特定的中斷申請，通知該事件。(3)地位： 從屬于主處理機(jī)。第90頁/共147頁92 字節(jié)多路通道：以字節(jié)為單位交叉為多臺設(shè)備傳輸。子通道的概念。 選擇通道：完成一臺設(shè)備的全部傳輸再去為另一臺設(shè)備服務(wù)。 數(shù)組多路通道：以數(shù)組為單位交叉為多臺設(shè)備傳輸。(5)通道傳輸過程的時(shí)間分配 (P241，其中P是設(shè)備臺數(shù))： 字節(jié)多路通道： ，其中n是單臺設(shè)備的數(shù)據(jù)傳輸量； 選擇通道： 數(shù)組多路通道： ，其中k是塊尺寸， 。nPTTTDSBYTE)(nPTnTTDSSELECT)(nPTkTTDSBLOC