通道极限流量应大于或等于设备对通道要求的流量fbyte。 6台设备同时发出请求开始，画出此通道在数据传送期内响应和处理各外设请求的时间示意图。由此你发现了什么问题?
(3)在(2)的基础上，在哪台设备内设置多少个字节的缓冲器就可以避免设备信息丢失?那么，这是否说书中关于流量设计的基本要求是没有必要的了呢?为什么?
如果字节多路通道上所挂设备台数为m,设备的速率为fi，为了不丢失信息，应满足： 1/(TS+TD)>=m*fi
fi也就是设备发出字节传送请求间隔时间(500μs)的倒数，所以： m<=1/((TS+TD)*f)=500/(9.8+0.2)=50(台)
(2)设备B,C,E,F可以挂在此通道上，设备A,D则不能。 剖析：
思路一：从传送字节速率上入手。
A~F是高速设备，应挂接在选择通道上，选择通道的极限流量为： fmax.select=N/(TS+N*TD)=1/((TS/N)+TD)=1/((9.8/1024)+0.2)=1/0.21(约)
通道上所挂设备的最大速率fi.max应小于或等于通道的极限流量。 由表3-5可得出
设备 A B C D E F 传送速率(B/μs) 1/0.2 1/0.25 1/0.5 1/0.19 1/0.4 1/0.21
所以，B、C、E、F可挂在该通道上。A、D不能。 思路二：从传送字节时间上入手。
对于高速设备，由于一次传送字节数不少于1024byte
∴该通道一次传送数据的时间为9.8μs+1024×0.2μs＝214.6μs
由表3-5可得出每台设备发送1024字节的时间间隔分别为:
设备 A B C D E F 传送时间(μs) 204.8 256 512 194.56 409.6 215.04
∴为使数据不丢失，B、C、E、F可挂在该通道上。A、D不能。
6.某字节多路通道连接6台外设，某数据传送速率分别如表中所列。
设备 1 2 3 4 5 6 传送速率(KB/s) 50 15 100 25 40 20
(1)计算所有设备都工作时的通道实际最大流量：
(2)如果设计的通道工作周期使通道极限流量恰好与通道最大流量相等，以满足流量设计的基本要求，同时让速率越高的设备被响应的优先级越高。当
解： (1)实际最大流量＝50+15+l00+25+40+20＝250KB/S。 (2)通道响应和处理各设备请求的时间示意图
由此发现由于高速设备的响应优先级高，使低速设备2造成数据丢失。 (3)在2中各设两个字节的缓冲区即可。这并不说明流量设计的基本条件是不必要的，因为若基本条件不满足，无论设备优先级如何确定总有设备的信息会丢失。 剖析：
(2)由各设备的传送字节速率可解其连续发出传送请求的时间间隔分别为：
设备 1 2 3 4 5 6 发申请间隔(μs) 20 67(约) 10 40 25 50
7.通道型I/O系统由一个字节多路通道A(其中包括两个子通道Al和A2)，两个数组多路通道B1和B2及一个选择通道C构成，各通道所接设备和设备的数据传送速率如表所示。
(1)分别求出各通道应具有多大设计流量才不会丢失信息；
(2)设I/O系统流量占主存流量的1/2时才算流量平衡，则主存流量应达到多少?
通道号 所接设备的数据传送速率(KB/s) 子通道A1 50 35 20 20 50 35 20 20 字节多路通道 子通道A2 50 35 20 20 50 35 20 20 数组多路通道B1 500 400 350 250 数组多路通道B2 500 400 350 250 选择通道C 500 400 350 250
解： (1)要不丢失信息，各通道需要达到的流量：字节多路通道子通道A1:0.25KB/S;字节多路通道子通道A2:0.25KB/S;数组多路通道B1:500KB/s;数组多路通道B2:500KB/s;选择通道C:500KB/s。 (2)主存流量应达到4MB/S。
剖析:
(1)设备要求字节多路通道或其子通道的实际最大流量，是该通道所接各设备的字节传送速率之和;
设备要求数组多路通道或选择通道的实际最大流量，是该通道所接各设备的字节传送速率中的最大者。
(2)I/O系统中，各种通道和子通道可以并行工作，因此，I/O系统的最大流量应等于各通道最大流量之和。
第四章 存储体系
1.设二级虚拟存储器的TA1=10-7s、TA2=10-2s,为使存储层次的访问效
5
率e达到最大值的80%以上，命中率H至少要求达到多少？实际上
这样高的命中率是很难达到的，那么从存储层次上如何改进？
解： e=TA1/TA=TA1/(H*TA1+(1-H)*TA2)≥80%，H≥(10^5-5/4)/(10^5-1)。
这样的命中率很难达到。为了降低对H的要求，可以选择高命中率的算法，可以减少相邻两级的访问速度差和容量差(这样做不利于降低存储器的平均每位价格)，可在主、辅存储器间加一层电子磁盘，使存储体系中相邻两级的访问时间比不太大。
2、程序存放在模32单字交叉存储器中，设访存申请队的转移概率λ为25%,求每个存储周期能访问到的平均字数。当模数为16呢？由此你可得到什么结论？ 解：B=[ 1-(1-λ)^m] /λ
解： 由λ=0.25,m=32 求得：B=4-4*(3/4)^32 同理，m=16时 ,B=4-4*(3/4)^16
可得出，在λ=0.25时，m=32的平均访问字数大于m=16时的平均访问字数。
3、设主存每个分体的存取周期为2μs，宽度为4个字节。采用模m多分体交叉存取，但实际频宽只能达到最大频宽的0.6倍。现要求主存实际频宽为4MB/S,问主存模数m应取多少方能使两者速度基本适配？其中m取2的幂。 解： m=4 剖析：
根据题意，模m多分体交叉的最大频宽为：分体数*单体频宽=m*分体的宽度/分体的存取周期=m*4B/2μs，所以有0.6*m*4/2>=4。
4.某虚拟存储器共8个页面，每页1024个字，实际主存为4096个字，采用页表法进行地址映象。映象表的内容如下表所示。 虚页号 0 1 2 3 4 5 6 7 实页号 3 1 2 3 2 1 0 0 装入位 1 1 0 0 1 0 1 0 注：我把虚页号加上了。
(1)列出会发生页面失效的全部虚页号；
(2)按以下虚地址计算主存实地址：0，3728，1023，1024，2055，7800，4096，6800。 解:
(1)会发生页面失效的全部虚页号为：2,3,5,7。 (2)
虚地址 虚页号 页内位移 装入位 实页号 页内位移 实地址 0 0 0 1 3 0 3072 3278 3 656 0 页面失效 页面失效 无 1023 0 1023 1 3 1023 4095 1024 1 0 1 1 0 1024 2055 2 7 0 页面失效 页面失效 无 7800 7 632 0 页面失效 页面失效 无 4096 4 0 1 2 0 2048 6800 6 656 1 0 656 656 剖析：
(1)根据页表法列出表2，当装入位为0时，即为页面失效，再找出相对应的虚页号即可。
(2)虚页号=虚地址/页面大小
页内位移量=虚地址－虚页号*页面大小 实地址＝实页号*页面大小＋页内位移量
由于可以用替换算法解决页面失效的问题，所以，发生页面失效的虚页2,3,5,7仍然可以有相应的实地址，但这样要在页表中建立新的虚实地址对应关系，新的虚实地址对应关系和原来的对应关系相同的可能性就很小了。
5、一个段页式虚拟存储器。虚地址有2位段号、2位页号、11位页内位移（按字编址），主存容量为32K字。每段可有访问方式保护，其页表和保护位如下表所示。
段号 0 1 2 3 访问方式 只读 可读/执行 可读/写/执行 可读/写 虚页0所在位置 实页9 在辅存上 页表不在主存内 实页14 虚页1所在位置 实页3 实页0 页表不在主存内 实页1 虚页2所在位置 在辅存上 实页15 页表不在主存内 实页6 虚页3所在位置 实页12 实页8 页表不在主存内 在辅存上 (1)此地址空间中共有多少个虚页？ (2)当程序中遇到下列情况时
方式 段 页 页内位移 取数 0 1 1 取数 1 1 10 取数 3 3 2047 存数 0 1 4 存数 2 1 2 存数 1 0 14 转移至此 1 3 100 取数 0 2 50 取数 2 0 5 转移至此 3 0 60 写出由虚地址计算出实地址。说明哪个会发生段失效、页面或保护失效失效。 解答: (1)该地址空间中共有16个虚页。
(2)程序中遇到上表中各情况时，是否会发生段失效、页失效或保护失效及相应的主存实地址的情况如下表所示：
方式 段 页 页内位移 段失效 页失效 实页号 实地址 保护失效 取数 0 1 1 无 无 3 6145 无 取数 1 1 10 无 无 0 10 无 6
取数 3 3 2047 无 有 无 无 / 存数 0 1 4 无 无 3 6184 有 存数 2 1 2 有 / 无 无 / 存数 1 0 14 无 有 无 无 / 转移至此 1 3 100 无 无 8 16484 无 取数 0 2 50 无 有 无 无 / 取数 2 0 5 有 / 无 无 / 转移至此 3 0 60 无 无 14 28732 有 剖析：
(1)虚地址中段号有2位，页号有2位，也就是每个程序最多只能有2^2=4个段，每个段至多只能有2^2=4页，所以该地址空间中共有4*4=16个虚页。
(2)先从题意得知：
实地址：15位，其中实页号4位，页内位移11位 页大小为2K字（由页内位移得知）
6.设某程序包含5个虚页，其页地址为4，5，3，2，5，1，3，2，2，5，1，3。当使用LRU算法替换时，为获得最高命中率，至少应分配给该程序几个实页？其可能的最高命中率为多少？
7.采用页式管理的虚拟存储器，分时运行两道程序。其中，程序X为 DO 50 I=1,3 B(I)=A(I)-C(I)
IF(B(I)·LE·0)GOTO 40 D(I)=2*C(I)-A(I) IF(D(I)·EQ·0)GOTO 50 40 E(I)=0 50 CONTINUE Data: A=(-4,+2,0) C=(-3,0,+1)
每个数组分别放在不同的页面中;而程序Y在运行过程中，其数组将依次用到程序空间的第3,5,4,2,5,3,1,3,2,5,1,3,1,5,2页。如果采用LRU算法，实存却只有8页位置可供存放数组之用。试问为这两首程序的数组分别分配多少个实页最为合适？为什么？
解答： 分别分配给程序X和Y的数组4个实页最为合适。
根据题意，程序X依次调用数组A,C,B,B,E, A,C,B,B,C,A,D,D,E, A,C,B,B,E中的数据。
设程序X中的数组A,B,C,D,E分别存放于程序空间的第1,2,3,4,5页，则程序的页地址流为：1，3，2，2，5， 1，3，2，2，3，1，4，4，5， 1，3，2，2，5。
分析使用LRU算法对程序X的页地址流进行堆栈处理的过程可知，分配给程序X的数组5个实页最为合适;分析使用LRU算法对程序Y的页地址流进行堆栈处理的过程可知，分配给程序Y的数组4个实页最为合适。 但实存只有8页位置可供存放数组之用，所以，分别分配给程序X和Y的数组4个实页。 note:
分时运行在微观上是串行的，就是说，分时运行时把时间划分为若干时间片，每个程序轮流占用时间片;在宏观上是并行的，就是说，每个程序在一个时间片内并不能运行完。总的来看，是同时运行的，所以两个程序分配的实页和不能大于8。
我不了解FORTRAN，找朋友把上面的源代码转成C了： main() {
int A[]={-4,2,0}; int C[]={-3,0,1}; for (i=0,i<>0) E[i]=0; }; }; }
8.设一个按位编址的虚拟存储器，它应可对应1K个任务，但在一段较长时间内，一般只有4个任务在使用，故用容量为4行的相联寄存器组硬件来缩短被变换的虚地址中的用户位位数；每个任务的程序空间最大可达4096页，每页为512个字节，实主存容量为2＾20位；设快表用按地址访问存储器构成，行数为32，快表的地址是经散列形成；为减少散列冲突，配有两套独立相等比较电路。请设计该地址变换机构，内容包括： (1)画出其虚、实地址经快表变换之逻辑结构示意图；
(2)相联寄存器组中每个寄存器的相联比较位数； (3)相联寄存器组中每个寄存器的总位数； (4)散列变换硬件的输入位数和输出位数； (5)每个相等比较器的位数； (6)快表的总容量（以位为单位）。 解:
(1)依题意得知：
虚地址为34位，其中用户号为10位（对应1K的任务）、虚页号12位（每个任务4096页）、页内位移12位（每页512字节，512字节=512*8=1024*4=2^12）
实地址为20位，其中实页号8位，页内位移12位（与虚页页内位移对应）
相联寄存器的作用：把10位的用户号转换为2位的ID（因为一般只有4个任务在使用），并把ID与虚地址的虚页号合并到快表中查实页号。 快表的作用：相当于页表，即虚页号对实页号的对应关系。但又有所简化（原因是如果用用户号和虚页号与实页号对应，前者就有22位，现改进后虚页号只有14位了）
7
(2)相联寄存器组中每个寄存器的相联比较位数为10（与虚地址中的用户号宽度对应）
(3)相联寄存器组中每个寄存器的总数为12（用户号宽度+ID宽度） (4)散列变换硬件的输入位数为14位（虚页号宽度+相联寄存器中ID的宽度），输出位数为8位（与主存中的实页号宽度对应）
(5)每个相等比较器的位数=ID+用户虚页号nv'=2+12=14(位)。 (6)快表的总容量：32行*（14(输入位数)+8（输出位数））*2=32*22*2
9.考虑一个920个字的程序，其访问虚存的地址流为20，22，208，214，146，618，370，490，492，868，916，728。
(1)若页面大小为200字，主存容量为400字，采用FIFO替换算法，请按访存的各个时刻，写出其虚页地址流，计算主存的命中率； (2)若页面大小为100字，再做一遍； (3)若页面大小为400字，再做一遍；
(4)由(1)、(2)、(3)的结果可得出什么结论？
(5)若把主存容量增加到800字，按第(1)小题再做一遍，又可得出什么结论？
解： (1)主存容量400字，页面大小200字，所以主存实页数为2； 把地址流转换为页地址流，以第一个虚地址流转换为页地址流为例说明：求模公式为：INT（地址/页面大小），就是把地址整除于页面大小，得
INT（20/200）=0，下同，所以页地址流为：
0,0,1,1,0,3,1,2,2,4,4,3
按FIFO算法得出替换过程为：0（调入），0（命中），1（调入），1（命中），0（命中），3（替换0，0比1先入队，所以被替换，下同），1（命中），2（替换1），2（命中），4（替换3），4（命中），3（替换2），所以总共命中6次。 故命中率H=6/12=50% (2)方法同（1）H=25% (3)H=50%
(4)由以上结论可得，FIFO算法的条件下，当页面大小发生变化时，其命中率变化是：一开始随页面大小增大命中率（第一步与第二步比较），但当页面大小增到一定时，命中率不再增加（第一步与第三步比较）。 (5)命中率为58%，结论是如果分配给主存容量增加时可以搞高命中
率。
10. 在一个页式二级虚拟存储器中，采用FIFO算法进行页面替换，发现命中率H太低，因此有下列建议： (1)增大辅存容量; (2)增大主存容量(页数); (3)FIFO改为LRU;
(4)FIFO改为LRU，并增大主存容量(页数); (5)FIFO改为LRU，并增大页面大小。 试分析上述各建议对命中率的影响情况。
解答： (1)增大辅存容量，对命中率H无影响。 (2)增大主存容量(页数)，可普遍提高命中率。 (3)FIFO改为LRU，一般可提高命中率。
(4)FIFO改为LRU，并增大主存容量(页数)，一般可使命中率有较大
提高。
(5)FIFO改为LRU，并增大页面大小，如果原来页面很小，则会使命中率显著上升，如果原来页面很大，则会使命中率下降。
11.采用组相联映象的Cache存储器，Cache为1KB，要求Cache的每一块在一个主存周期内能从主存取得。主存模4交叉，每个分体宽为32位，总容量为256KB。用按地址访问存储器构成相联目录表实现主存地址到Cache地址的变换，并约定用4个外相等比较电路。请设计此相联目录表，求出该表之行数、总位数及每个比较电路的位数。
解答： 设Cache地址中的组内块号为s，相联目录表的行数是2^(13-s)，总位数是(8+2s)*2^(15-s)，每个比较电路的位数为8+s。 剖析：
在一个主存周期内主存能访问到的字节数为mW=4*32/8=16(Byte)。要求Cache的每一块在一个主存周期内能从主存取得，所以，Cache中每块的块内字数不能大于16Bytes。为了加速调块，一般让每块的大小等于在一个主存周期内主存能访问到的字数，即16Bytes。
设Cache地址中的组内块号为s，相联目录表的行数=Cache地址内的组数
Q=Cache
容量/(每组块数*每块大
小)=1KB/(S*4*32)=2^13/(2^s*2^7)=2^(6-s)。
主存块数/Cache块数=256=2*8，所以，主存地址中的区号nd=8。每个比较电路的位数=nd+s'=nd+s=8+s。
相联目录表的总位数=表中子目录表的个数*每个子目录表的位数*相联
目
录
表
的
行
数
=4*(nd+s'+s)*Q=4*(8+2s)*2^(6-s)=(8+2s)*2^(8-s)。 note：
若认为相等比较电路的个数=组内块数，则相联目录表的行数=2^4，每个比较电路的位数=10，相联目录表的总位数=12*2^6。
12.有一个Cache存储器。主存共分8个块(0~7),Cache为4个块(0~3),采用组相联映象，组内块数为2块，替换算法为近期最少使用算法(LRU)。 (1)画出主存、Cache地址的各字段对应关系(标出位数)图; (2)画出主存、Cache空间块的映象对应关系示意图;
(3)对于如下主存块地址流：1,2,4,1,3,7,0,1,2,5,4,6,4,7,2,如主
8