习题四1.教材P88 存储层次的访问效率e计算公式。
e=T A1/(H T A1+(1-H) T A2)e H T A1+ e(1-H) T A2= T A1H T A1+ (1-H) T A2= T A1/ eH T A1 -H T A2= T A1/ e- T A2H (T A1 - T A2) = T A1/ e- T A2H = T A1/ e- T A2/ (T A1 - T A2)H = T A1(1/ e- T A2/ T A1)/ T A1 (1- T A2/ T A1)H = (1/ e- T A2/ T A1)/ (1- T A2/ T A1)把题意的条件带入，命中率H=(1/ e- T A2/ T A1)/ (1- T A2/ T A1)=(1/ 0.8- 10-2/ 10-7)/ (1- 10-2/ 10-7)=0.999999975实际上，这样高的命中率是极难达到的。
在主辅存之间增设一级存储器，让其速度介于主存辅存之间，让主存与中间级的访问时间比为1：100，中间级与辅存之间的访问时间比为1：1000，将它们配上相应辅助软硬件，组成一个三级存储层次，这样，可以使第1级主存的命中率降低到H=(1/ 0.8- 10-5/ 10-7)/ (1- 10-5/ 10-7)=0.9971.教材P84 每个存储周期能访问到的平均字数B=(1-(1-λ)m)/λ=(1-0.7532)/0.25≈4既每个存储周期能访问到的平均字数为4。
若将λ=25%，m=16代入得B=(1-(1-λ)m)/λ=(1-0.7516)/0.25=3.96既每个存储周期能访问到的平均字数为3.96。
可见，模数m不宜太大，否则性能改进不大。
3．教材P81。
m个存储体并行的最大频宽B m=W*m/T M，根据题意，实际频宽要低于最大频宽。
即实际频宽≤0.6最大频宽。
4*106B/s≤0.6*4 B*m/(2*10-6 s)4≤0.6* m*4/22≤0.6* m3.333≤ mm取2的幂，即m为4。
4.教材P91。
根据题意，画出页表。
虚存页号实页号装入位0 3 11 1 12 2 03 3 04 2 15 1 06 0 17 0 0⑴发生页面失效的全部虚页号就是页映像表中所有装入位为0的行所对应的虚页号的集合。
本题为2，3，5，7。
⑵按以下虚地址计算主存实地址的情况列表虚地址虚存页号页内位移装入位实页号页内位移实地址0 0 0 1 3 0 （3*1024+0）3072 3728（3*1024+656） 3 656 0 页面失效页面失效无1023（0*1024+1023）0 1023 1 3 1023 （3*1024+1023）4095 1024（1*1024+0） 1 0 1 1 0 （1*1024+0）1024 2055（2*1024+7） 2 7 0 页面失效页面失效无7800（7*1024+632）7 632 0 页面失效页面失效无4096（4*1024+0） 4 0 1 2 0 （2*1024+0）2048 6800（6*1024+656） 6 656 1 0 656 （0*1024+656）6565.教材P93。
图4.14⑴用户标志段号页号页内位移段号2位，页号2位，最多可以有4*4=16个虚页。
⑵页表和保护位如下表所示段号段0 段1 段2 段3访问方式只读可读/执行可读/写/执行可读/写虚页0所在位置实页9 在辅存上实页14虚页1所在位置实页3 实页0 页表不在实页1虚页2所在位置在辅存上实页15 主存内实页6虚页3所在位置实页12 实页8 在辅存上实地址=实页号*211+页内位移方式段页页内位移段失效页失效实页号实地址保护失效取数0 1 1 无无 3 3*2048+1=6145 无取数 1 1 10 无无0 0*2048+10=10 无取数 3 3 2047 无有(在辅存) 无无/存数0 1 4 无无 3 3*2048+4=6148 有（写）存数 2 1 2 有(无页表) / 无无/存数 1 0 14 无有(在辅存) 无无/转移至此 1 3 100 无无8 8*2048+100=16484无取数0 2 50 无有(在辅存) 无无/取数 2 0 5 有/ 无无/转移至此 3 0 60 无无14 14*2048+60=28732 有（执行）6．L RU算法、OPT算法都是堆栈型替换算法。
教材P101。
4 5 3 2 5 1 3 2 2 5 1 3S⑴4 5 3 2 5 1 3 2 2 5 1 3S⑵4 5 3 2 5 1 3 3 2 5 1S⑶4 5 3 2 5 1 1 3 2 5S⑷4 4 3 25 5 1 3 2S⑸4 4 4 4 4 4 4S⑹n=1 Hn=2 Hn=3 H Hn=4 H H H H H H H n=5 H H H H H H H n=1时，S8=｛2｝，A9=2∈S8，所以命中。
其余都不命中。
n=2时，S8=｛2，3｝，A9=2∈S8，所以命中。
其余都不命中。
n=3时，S4=｛2，3，5｝，A5=5∈S4，所以命中。
S8=｛2，3，1｝，A9=2∈S8，所以命中。
其余都不命中。
n=4时，S4=｛2，3，5，4｝，A5=5∈S4，所以命中。
S5=｛2，3，5，4｝，A6=1不属于 S5，所以不命中。
余类推。
模拟结果表明，使用LRU算法替换，对该程序至少应分配4个实页。
如果只分配3个实页，命中率只有2/12，太低。
如果分配5个实页，命中率虽有7/12，和分配4个实页比较没有增长。
7．A B C D E -4 -3+2 00 +1当I=1时，B(1)=A(1)-C(1)= -4-(-3)=-1。
B(1)<0 GOTO 40 E(1)=0 程序X的页面地址流 A C B EA B C D E-4 -1 -3 0+2 00 +1当I=2时，B(2)=A(2)-C(2)= +2-0 =2。
B(2)>0D(2)=2* C(2)- A(2) =2*0-2=-2。
D(2)≠0 GOTO 40 E(2)=0程序X的页面地址流 A C B C A D EA B C D E-4 -1 -3 0+2 2 0 -2 00 +1当I=3时，B(3)=A(3)-C(3)= 0-1 =-1。
B(3) <0 GOTO 40 E(3)=0 程序X的页面地址流 A C B EA B C D E -4 -1 -3 0 +2 2 0 -2 0 0 -1 +1 0程序X 程序Y H x H y H3 5 3/15 10/15 6.5/154 4 8/15 10/15 9/155 3 10/15 4/15 7/15程序X和程序Y各占4个页最佳。
8.⑴画出其虚、实地址经快表变换的逻辑结构示意图。
教材P105。
图4.25教材P106。
图4.26 教材P107。
图4.27①可对应1K个任务，即需要10位二进制表示，u需要10位。
②每个任务的程序空间最大可达4096页。
即需要12位二进制表示，N r N’v需要12位。
③只有4个任务在使用。
容量为4行的相联寄存器组。
ID为2位二进制表示。
④实主存容量为220，与虚地址N r对应，实地址的n r为12位二进制表示，实页号n v为20-12=8位二进制表示。
⑵由图示可知，相联寄存器组中的每个寄存器的相联比较位数为u，需要10位。
⑶由图示可知，相联寄存器组中的每个寄存器的总位数为u+ID=12位。
⑷散列变换硬件的输入位数为ID+N’v=2+12=14位。
快表的行数为32，即散列变换硬件的输出位数为A=log232=5位。
⑸每个相等比较器的位数为N’v + ID =12+2=14位。
⑹快表的总容量（位）为快表的行数*（N’v + ID+n v）*2=32*（12+2+8）*2=1408位。
9.⑴页面大小为200字，主存容量为400字，可以知道实存页数为2页。
根据虚地址和页面的关系，虚页地址流为0，0，1，1，0，3，1，2，2，4，4，3。
由图A7给出采用FIFO替换算法时的实际装入和替换过程。
其中，“*”标记的是候选替换的虚页页号，H表示命中。
由图A7计算可得主存的命中率H=6/12=0.5。
⑵页面大小为100字，主存容量为400字，可以知道实存页数为4页。
根据虚地址和页面的关系，虚页地址流为0，0，2，2，1，6，3，4，4，8，9，7。
由图A8给出采用FIFO替换算法时的实际装入和替换过程。
其中，“*”标记的是候选替换的虚页页号，H表示命中。
由图A8计算可得主存的命中率H=3/12=0.25。
⑶页面大小为400字，主存容量为400字，可以知道实存页数为1页。
根据虚地址和页面的关系，虚页地址流为0，0，0，0，0，1，0，1，1，2，2，1。
由图A9给出采用FIFO替换算法时的实际装入和替换过程。
其中，“*”标记的是候选替换的虚页页号，H表示命中。
由图A9计算可得主存的命中率H=6/12=0.5。
⑷由⑴⑵⑶的结果可以看出，当实存容量一定时，页面大小过小时，命中率H 较低。
页面大小增大后，命中率H会有所上升。
⑸页面大小为200字，主存容量为800字，可以知道实存页数为4页。
根据虚地址和页面的关系，虚页地址流为0，0，1，1，0，3，1，2，2，4，4，3。
由图A10给出采用FIFO替换算法时的实际装入和替换过程。
其中，“*”标记的是候选替换的虚页页号，H表示命中。
由图A10计算可得主存的命中率H=7/12=0.583。
可以看出，实存容量增大，命中率会有所上升。
但不显著。
命中率提高趋于平缓。
10．⑴增大辅存容量，对主存命中率H不会有什么影响。
⑵增大主存容量较多，对主存命中率H有明显提高的趋势。
增大主存容量较少，命中率H可能略有增大，也可能不变，甚至会少许下降。
⑶因为前提是主存的命中率H很低，在增大主、辅存的页面大小时，如果增加量较小，主存命中率H可能没有太大的波动。
因为FIFO是非堆栈型的替换算法，主存命中率H可能会有所增加，也可能降低或不变。
而当页面大小增加量较大时，可能会出现两种相反的情况。
当原页面大小较小时，在显著增大了页面大小之后，一般会使主存命中率H有较大的提高。
当原页面大小已经较大时，在显著增大了页面大小之后，由于在主存中的页面数过少，将会使主存命中率H 继续有所下降。
⑷页面替换算法由FIFO改为LRU，一般会使主存命中率H提高。
⑸页面替换算法由FIFO改为LRU，同时增大主存的容量（页数），一般会使主存命中率H有较大的提高。
⑹页面替换算法由FIFO改为LRU，且增大页面大小时，如果原先页面大小很小，则会使命中率H显著上升，如果原先页面大小已经很大了，因为主存页数进一步减少而使命中率H继续有所下降。
11.教材P113-P116。