1、计算机系统结构习题讲解,第4章 存储系统,题4.11,步骤1：通过运行典型程序，实测虚拟存储器的等效访问周期T和主存命中率H，将实测的T与主存访问周期T1进行比较；若T已非常接近T1，则转到步骤5；否则，根据T=HT1+(1-H)T2可知，问题可能是主存命中率H较低，或者是CPU访问主存的周期T1太长，转到步骤2。 步骤2：综合采取下列措施提高主存命中率： 增大主存容量； 适当调整页面大小，使H提升到最佳值； 修改页面替换策略。然后，转到步骤1。如果主存命中率H已经较高，则转到步骤3。,步骤3：主存命中率H已经较高，表明问题是主存访问周期T1太长。T1包括虚实地址变换的时间和按实地址访问主存的
2、存取时间。此时，应检查系统是否配置有加快地址变换速度的机构，若已经配置，则转到步骤5；若没有配置，则转到步骤4。 步骤4：提高虚实地址变换速度。一种措施是用目录表代替页表，但是，目录表需要有相联存储器，造价较高；另一种可行的措施是采用快慢表，即把页表分成快表和慢表两级，提高查表速度,提高主存频宽可综合采取下列措施： 主存采用更高速的器件； 主存采用多体交叉编址并行存储器，调整存 储体个数m； 增设Cache存储器,题4.20,20 22 208 214 146 618 370 490 492 868 916 7280 0 1 1 0 3 1 2 2 4 4 3,装入,命中,装入,命中,命中,替
3、换,命中,替换,命中,替换,命中,替换,命中6次，主存命中率为6/12=0.5,20 22 208 214 146 618 370 490 492 868 916 7280 0 2 2 1 6 3 4 4 8 9 7,装入,命中,替换,装入,命中,装入,装入,替换,命中,替换,替换,替换,命中3次，主存命中率为3/12=0.25,20 22 208 214 146 618 370 490 492 868 916 7280 0 0 0 0 1 0 1 1 2 2 1,装入,命中,替换,命中,命中,命中,替换,替换,命中,替换,命中,替换,命中6次，主存命中率为6/12=0.5,由结果可以看出，在
4、分配给程序的实存空间一定的条件下，有： 页面大小Sp过小时，命中率H较低，因为两个访存地 址在同一个虚页内的可能性随Sp减小而降低。 当页面大小Sp增大后，命中率H有所增大，因为两个访存地址在同一个虚页内的可能性随Sp增大而升高，前一个地址访存将该虚页装入主存，后一个地址访存时就会命中。 页面大小Sp进一步增大，使分配的实页数过少，如果访存页地址流有大量的远距离转移，那么，将导致频繁的页面替换，从而使命中率明显下降,20 22 208 214 146 618 370 490 492 868 916 7280 0 1 1 0 3 1 2 2 4 4 3,装入,命中,命中,装入,命中,命中,装入,
5、装入,命中,替换,命中,命中,命中7次，主存命中率为7/120.58,（5）从结果可以看出，分配给程序的实页数增大后，命中率H会有所上升。但是，只有堆栈型替换算法能保证主存命中率随分配的实页数的增加而提高，至少不降低。FIFO算法不是堆栈型替换算法，所以，此结果只能看成是FIFO替换算法的一个特例，不具备普遍意义。,题4.21,命中率=4/16=0.25缺失率=12/16=0.75,时间t,1 2 3 4 5 6 7 8 9 10,虚页地址流,0 1 0 4 3 0 2 3 1 3,0,0,1,0,1,0*,1,4,调进,调进,命中,调进,替换,3,1*,4,3,0,4*,替换,3*,0,2,
6、替换,3*,0,2,命中,1,0*,2,替换,1,3,2*,替换,先进先出 FIFO,命中2次,题4.22,时间t,1 2 3 4 5 6 7 8 9 10,虚页地址流,0 1 0 4 3 0 2 3 1 3,0,0,1,0,1,0,1*,4,调进,调进,命中,调进,替换,0*,3,4,0,3,4*,0,3*,2,替换,0*,3,2,命中,1,3,2*,替换,1,3,2*,近期最少使用 LRU,命中4次,命中,命中,时间t,1 2 3 4 5 6 7 8 9 10,虚页地址流,0 1 0 4 3 0 2 3 1 3,0,0,1,0,1,0,1,4*,调进,调进,命中,调进,替换,0,1*,3,
7、0*,1,3,2*,1,3,替换,2*,1,3,命中,2*,1,3,2*,1,3,最优替换算法 OPT,命中5次,命中,命中,命中,3 4 2 1 4 0 2 1 2 4 0 2,S(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 3,命中,
8、命中,命中,命中,命中,命中,主存命中率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 7,命中,命中,命中,主存命中率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 1,命中,命中,命中,命中,命中,命中,主存命中率H3为6/12=0.5,有H2H1，说明当分配给程序的主存容量不变时，减小页长，会使主存命中率下降。因为减小页长使程序划分的虚、实页数增加，从而
9、增大了程序跨页访问的概率。,12 40 260 280 180 800 500 560 600 1100 1200 1000 0 0 1 1 0 3 1 2 2 4 4 3,命中,命中,命中,主存命中率H4为7/120.58,命中,命中,命中,命中,从（1）和（5）的结果可以看出，当分配给的主存容量或实页数增大时，主存命中率也会随着提高。但是，只有堆栈型替换算法能保证命中率随分配的实页数的增加而提高。FIFO算法不是堆栈型替换算法，不能保证命中率能随分配的实页数的增加而提高。,块号B,块内地址W,主存块号B,Cache块号b,有效位,B,b,1,相联比较,块号b,块内地址w,主存地址,Cach
10、e地址,命中,目录表（由相联存储器存储，共Cb个字）,log2CB位,log2WB位,log2Cb位,CB：主存总块数Cb：Cache总块数WB：每块存储字数,相联目录表为512行，相联目录表的比较位数为17位，相联目录表的宽度为27位，相联目录表的总位数为27*512=13824,题4.26,（1）主存地址( E, G, 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 的任何位置上,1 2 4 1 3 7 0 1 2 5
11、 4 6 4 7 2,命中,命中,命中,发生块失效且块争用的时刻有：t6, t7, t9, t10, t11, t12, t14, t15。命中率为3/15=0.2,区号E,区内组号G,组内块号B,块内地址W,组号g,组内块号b,块内地址w,E,B,b,e,E,B,b,e,E,B,b,e,E,B,b,e,E,B,b,e,E,B,b,e,相等比较,相等比较,相等比较,或,与,块失效,主存地址,Cache地址,块表（按地址访问的单体多字存储器）,题4.27,主存地址( E, G, B, W ) 中的E为14位，G为8位，B为2位，W为2位。Cache地址( g, b, w ) 中的g为8位，b为2
12、位，w为2位。 块表的行数为28行，容量为(14+2+2+1)*4*28= 19456位。每个比较电路进行相等比较的位数为14+2=16位。,题4.28,（1）主存地址为( E, G, B, W )，E的长度为9，G的长度为8，B的长度为3，W的长度为3。 Cache地址为(g, b, w)，g的长度为8，b的长度为3，w的长度为3。（2）块表的行数为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)的各字
13、段长度分别为3, 6, 6。（2） 可得TM=380ns,题4.30,0 8 0 6 8,命中,命中,Cache块0,Cache块1,Cache块2,Cache块3,命中次数为2次，缺失次数为3次。,0 8 0 6 8,命中,命中,Cache块0,Cache块1,Cache块2,Cache块3,命中次数为2次，缺失次数为3次。,0 8 0 6 8,Cache块0,Cache块1,Cache块2,Cache块3,命中次数为0次，缺失次数为5次。,题4.31,不设置Cache的情况下: 1.33*50+2=68.5设置Cache的情况下： 1.33*(98%*2+2%*50)+25.94加速比为:
14、 S=68.5/5.9411.53,题4.32,CPU平均访存次数=109*4%*(3+25%*2) =109*0.14次/s CPU访存占用主存带宽的百分比为 109*0.14,5*108,=28%,若现有外设的输入/输出占用主存频宽的1/2，那么，现有主存还允许接入新的外设，新接入的外设占用主存频宽不能超过现有主存频宽的22%。,题4.33,t1=30时钟周期*256*50%=3840时钟周期 t2=(30+30)时钟周期*256*95%=14640时钟周期 t=t1+t2=18480时钟周期 T1=30时钟周期*7500+(30+30)*7500时钟周期=67500时钟周期 T=106+T1=1675000时钟周期 t/T=18480/1675000=1.1%,
