1、计算机系统结构习题讲解计算机系统结构习题讲解第第4章章 存储系统存储系统题题4.11l 步骤步骤1：通过运行典型程序，实测虚拟存储器的等效访问：通过运行典型程序，实测虚拟存储器的等效访问周期周期T和主存命中率和主存命中率H，将实测的，将实测的T与主存访问周期与主存访问周期T1进进行比较；若行比较；若T已非常接近已非常接近T1，则转到步骤，则转到步骤5；否则，根据；否则，根据T=HT1+(1-H)T2可知，问题可能是主存命中率可知，问题可能是主存命中率H较低，或较低，或者是者是CPU访问主存的周期访问主存的周期T1太长，转到步骤太长，转到步骤2。l 步骤步骤2：综合采取下列措施提高主存命中率：综
2、合采取下列措施提高主存命中率： 增大主存增大主存容量；容量； 适当调整页面大小，使适当调整页面大小，使H提升到最佳值；提升到最佳值； 修修改页面替换策略。然后，转到步骤改页面替换策略。然后，转到步骤1。如果主存命中率。如果主存命中率H已经较高，则转到步骤已经较高，则转到步骤3。l 步骤步骤3：主存命中率：主存命中率H已经较高，表明问题是主存访问周已经较高，表明问题是主存访问周期期T1太长。太长。T1包括虚实地址变换的时间和按实地址访问包括虚实地址变换的时间和按实地址访问主存的存取时间。此时，应检查系统是否配置有加快地址主存的存取时间。此时，应检查系统是否配置有加快地址变换速度的机构，若已经配置
3、，则转到步骤变换速度的机构，若已经配置，则转到步骤5；若没有配；若没有配置，则转到步骤置，则转到步骤4。l 步骤步骤4：提高虚实地址变换速度。一种措施是用目录表代：提高虚实地址变换速度。一种措施是用目录表代替页表，但是，目录表需要有相联存储器，造价较高；另替页表，但是，目录表需要有相联存储器，造价较高；另一种可行的措施是采用快慢表，即把页表分成快表和慢表一种可行的措施是采用快慢表，即把页表分成快表和慢表两级，提高查表速度两级，提高查表速度l 提高主存频宽可综合采取下列措施：提高主存频宽可综合采取下列措施： 主存采用更高速主存采用更高速的器件；的器件； 主存采用多体交叉编址并行存储器，调整存主存
4、采用多体交叉编址并行存储器，调整存 储体个数储体个数m； 增设增设Cache存储器存储器题题4.2020 22 208 214 146 618 370 490 492 868 916 7280 0 1 1 0 3 1 2 2 4 4 30装入装入0命中命中0*1装入装入0*1命中命中0*1命中命中31*替换替换31*命中命中3*2替换替换3*2命中命中42*替换替换42*命中命中4*3替换替换命中命中6次，主存命中率为次，主存命中率为6/12=0.520 22 208 214 146 618 370 490 492 868 916 7280 0 2 2 1 6 3 4 4 8 9 70装入装入
5、命中命中替换替换002装入装入02命中命中021装入装入0*216装入装入32*16341*6替换替换341*6命中命中3486*替换替换3*489替换替换74*89替换替换命中命中3次，主存命中率为次，主存命中率为3/12=0.2520 22 208 214 146 618 370 490 492 868 916 7280 0 0 0 0 1 0 1 1 2 2 10装入装入 命中命中替换替换00命中命中0命中命中0命中命中10替换替换1替换替换1命中命中2替换替换2命中命中1替换替换命中命中6次，主存命中率为次，主存命中率为6/12=0.5l 由结果可以看出，在分配给程序的实存空间一定的条
6、件由结果可以看出，在分配给程序的实存空间一定的条件下，有：下，有：l 页面大小页面大小Sp过小时，命中率过小时，命中率H较低，因为两个访存地较低，因为两个访存地 址在同一个虚页内的可能性随址在同一个虚页内的可能性随Sp减小而降低。减小而降低。l 当页面大小当页面大小Sp增大后，命中率增大后，命中率H有所增大，因为两个有所增大，因为两个访存地址在同一个虚页内的可能性随访存地址在同一个虚页内的可能性随Sp增大而升高，前一增大而升高，前一个地址访存将该虚页装入主存，后一个地址访存时就会命个地址访存将该虚页装入主存，后一个地址访存时就会命中。中。l 页面大小页面大小Sp进一步增大，使分配的实页数过少，
7、如果进一步增大，使分配的实页数过少，如果访存页地址流有大量的远距离转移，那么，将导致频繁的访存页地址流有大量的远距离转移，那么，将导致频繁的页面替换，从而使命中率明显下降页面替换，从而使命中率明显下降20 22 208 214 146 618 370 490 492 868 916 7280 0 1 1 0 3 1 2 2 4 4 30装入装入命中命中命中命中001装入装入01命中命中01命中命中013装入装入0130*132装入装入0*132命中命中41*32替换替换41*32命中命中41*32命中命中命中命中7次，主存命中率为次，主存命中率为7/120.58l （5）从结果可以看出，分配给
8、程序的实页数增大后，命）从结果可以看出，分配给程序的实页数增大后，命中率中率H会有所上升。但是，只有堆栈型替换算法能保证主会有所上升。但是，只有堆栈型替换算法能保证主存命中率随分配的实页数的增加而提高，至少不降低。存命中率随分配的实页数的增加而提高，至少不降低。FIFO算法不是堆栈型替换算法，所以，此结果只能看成算法不是堆栈型替换算法，所以，此结果只能看成是是FIFO替换算法的一个特例，不具备普遍意义。替换算法的一个特例，不具备普遍意义。题题4.210 7 0 6 7 1 6 3 0 7 2 7 1 4 0 2007070760760*7610*76137*613061*306*73*0273
9、*02710*27142*71407*1*402命命中中命命中中命命中中命命中中调调入入调调入入调调入入调调入入替替换换替替换换替替换换替替换换替替换换替替换换替替换换替替换换命中率命中率=4/16=0.25缺失率缺失率=12/16=0.75时间时间t1 2 3 4 5 6 7 8 9 10虚页地虚页地址流址流0 1 0 4 3 0 2 3 1 3001010*14调调进进调调进进命命中中调调进进替替换换31*4304*替替换换3*02替替换换3*02命命中中10*2替替换换132*替替换换先进先出先进先出 FIFO命中命中2次次题题4.22时间时间t1 2 3 4 5 6 7 8 9 10虚
10、页地虚页地址流址流0 1 0 4 3 0 2 3 1 30010101*4调调进进调调进进命命中中调调进进替替换换0*34034*03*2替替换换0*32命命中中132*替替换换132*近期最近期最少使用少使用 LRU命中命中4次次命命中中命命中中时间时间t1 2 3 4 5 6 7 8 9 10虚页地虚页地址流址流0 1 0 4 3 0 2 3 1 300101014*调调进进调调进进命命中中调调进进替替换换01*30*132*13替替换换2*13命命中中2*132*13最优替最优替换算法换算法 OPT命中命中5次次命命中中命命中中命命中中34214021240234214021240342
11、140012433214401133333333 4 2 1 4 0 2 1 2 4 0 2S(1)S(2)S(3)S(4)S(5)命中命中n=1n=2n=3n=4n=5命中命中命中命中命中命中命中命中命中命中命中命中 命中命中 命中命中 命中命中命中命中命中命中命中命中命中命中 命中命中 命中命中 命中命中命中命中至少应分配至少应分配4个实页，达到最大命中率为个实页，达到最大命中率为7/120.58题题4.23题题4.24 12 40 260 280 180 800 500 560 600 1100 1200 1000 0 0 1 1 0 3 1 2 2 4 4 3000*0*0*333*3
12、*444*1111*1*222*2*3命命中中命命中中命命中中命命中中命命中中命命中中主存命中率主存命中率H1为为6/12=0.5 12 40 260 280 180 800 500 560 600 1100 1200 1000 0 0 2 2 1 6 3 4 4 8 9 7000000*33333*722222*44444*1111*1*88866666*99命命中中命命中中命命中中主存命中率主存命中率H2为为3/12=0.25 12 40 260 280 180 800 500 560 600 1100 1200 1000 0 0 0 0 0 1 0 1 1 2 2 10000010112
13、21命命中中命命中中命命中中命命中中命命中中命命中中主存命中率主存命中率H3为为6/12=0.5l 有有H2H1，说明当分配给程序的主存容量不，说明当分配给程序的主存容量不变时，减小页长，会使主存命中率下降。因为变时，减小页长，会使主存命中率下降。因为减小页长使程序划分的虚、实页数增加，从而减小页长使程序划分的虚、实页数增加，从而增大了程序跨页访问的概率。增大了程序跨页访问的概率。 12 40 260 280 180 800 500 560 600 1100 1200 1000 0 0 1 1 0 3 1 2 2 4 4 300000000*0*44411111111*1*1*33333332
14、2222命命中中命命中中命命中中主存命中率主存命中率H4为为7/120.58命命中中命命中中命命中中命命中中l 从（从（1）和（）和（5）的结果可以看出，当分配给）的结果可以看出，当分配给的主存容量或实页数增大时，主存命中率也会的主存容量或实页数增大时，主存命中率也会随着提高。但是，只有堆栈型替换算法能保证随着提高。但是，只有堆栈型替换算法能保证命中率随分配的实页数的增加而提高。命中率随分配的实页数的增加而提高。FIFO算法不是堆栈型替换算法，不能保证命中率能算法不是堆栈型替换算法，不能保证命中率能随分配的实页数的增加而提高。随分配的实页数的增加而提高。块号块号B块内地址块内地址W主存块号主存
15、块号BCache块号块号b有效位有效位Bb1相联比较相联比较块号块号b块内地址块内地址w主存地址主存地址Cache地址地址命中命中目录表（由相联存储目录表（由相联存储器存储，共器存储，共Cb个字）个字）log2CB位位log2WB位位log2Cb位位CB：主存总块数：主存总块数Cb：Cache总块数总块数WB：每块存储字数：每块存储字数l 相联目录表为相联目录表为512行，相联目录表的比较位数行，相联目录表的比较位数为为17位，相联目录表的宽度为位，相联目录表的宽度为27位，相联目录位，相联目录表的总位数为表的总位数为27*512=13824题题4.26（1）主存地址）主存地址( E, G,
16、B, W )，E、G、B各各1位位 Cache地址地址(g,b,w)，g、b各各1位位 W和和w无法确定，取决于块的大小无法确定，取决于块的大小（2）主存块）主存块0、1、4、5只能装入只能装入Cache块块0、1 的任何位置上的任何位置上 主存块主存块2、3、6、7只能装入只能装入Cache块块2、3 的任何位置上的任何位置上111*1111*111*4444444* 4* 4*00* 0*55* 5* 5* 5* 5*2222*7777* 7* 7*666*233* 3* 3*2222* 2*77*1 2 4 1 3 7 0 1 2 5 4 6 4 7 2命命中中命命中中命命中中发生块失效
17、且块争用的时刻有：发生块失效且块争用的时刻有：t6, t7, t9, t10, t11, t12, t14, t15。命中率为。命中率为3/15=0.2区号区号E区内组号区内组号G组内块号组内块号B块内地址块内地址W组号组号g组内块号组内块号b块内地址块内地址wE,BbeE,BbeE,BbeE,BbeE,BbeE,Bbe相等比较相等比较相等比较相等比较相等比较相等比较或或与与块失效块失效主存主存地址地址Cache地址地址块表（按地址访问的单体多字存储器）块表（按地址访问的单体多字存储器）题题4.27l 主存地址主存地址( E, G, B, W ) 中的中的E为为14位，位，G为为8位，位，B为
18、为2位，位，W为为2位。位。Cache地址地址( g, b, w ) 中的中的g为为8位，位，b为为2位，位，w为为2位。位。l 块表的行数为块表的行数为28行，容量为行，容量为(14+2+2+1)*4*28= 19456位。每个比较电路进行相等比较的位数位。每个比较电路进行相等比较的位数为为14+2=16位。位。题题4.28l （1）主存地址为）主存地址为( E, G, B, W )，E的长度为的长度为9，G的长度为的长度为8，B的长度为的长度为3，W的长度为的长度为3。 Cache地址为地址为(g, b, w)，g的长度为的长度为8，b的长度的长度为为3，w的长度为的长度为3。（2）块表的
19、行数为）块表的行数为28，宽度为，宽度为16*8=16B，容量，容量为为16*8*28=4096B。每个比较电路进行相等比。每个比较电路进行相等比较的位数为较的位数为9+3=12位。位。题题4.29（1）主存地址）主存地址( E, G, B, W )的各字段长度分别的各字段长度分别为为5, 3, 6, 6。Cache地址地址(g, b, w)的各字段长度的各字段长度分别为分别为3, 6, 6。（2） 可得可得TM=380nsTM20ns*0.95+TM*0.05=10题题4.30000008888660 8 0 6 8命中命中命中命中Cache块块0Cache块块1Cache块块2Cache块
20、块3命中次数为命中次数为2次，缺失次数为次，缺失次数为3次。次。00*000*88*8*8660 8 0 6 8命中命中命中命中Cache块块0Cache块块1Cache块块2Cache块块3命中次数为命中次数为2次，缺失次数为次，缺失次数为3次。次。0800860 8 0 6 8Cache块块0Cache块块1Cache块块2Cache块块3命中次数为命中次数为0次，缺失次数为次，缺失次数为5次。次。题题4.31不设置不设置Cache的情况下的情况下: 1.33*50+2=68.5设置设置Cache的情况下：的情况下： 1.33*(98%*2+2%*50)+25.94加速比为加速比为: S=
21、68.5/5.9411.53题题4.32 CPU平均访存次数平均访存次数=109*4%*(3+25%*2) =109*0.14次次/s CPU访存占用主存带宽的百分比为访存占用主存带宽的百分比为 109*0.145*108=28%若现有外设的输入若现有外设的输入/输出占用主存频宽的输出占用主存频宽的1/2，那么，那么，现有主存还允许接入新的外设，新接入的外设占用现有主存还允许接入新的外设，新接入的外设占用主存频宽不能超过现有主存频宽的主存频宽不能超过现有主存频宽的22%。题题4.33l t1=30时钟周期时钟周期*256*50%=3840时钟周期时钟周期l t2=(30+30)时钟周期时钟周期*256*95%=14640时钟周时钟周期期l t=t1+t2=18480时钟周期时钟周期l T1=30时钟周期时钟周期*7500+(30+30)*7500时钟周期时钟周期=67500时钟周期时钟周期l T=106+T1=1675000时钟周期时钟周期l t/T=18480/1675000=1.1%
