4005 （R3）←（R3）+C（R1）使用索引记录R1加上C[i] 4006 A（R1）←（R3）使用索引记录R1将总和存入A[i]中 4007 （R1）←（R1）+1 i加一 4008 跳到4002 6000—6999 存储A 7000—7999 存储B 8000—8999 存储C 9000 存储1 9001 存储n

由这个循环产生的参考串为 494944（47484649444）1000

包括11.000个参考，但仅包括5个不寻常的页

8.9 IBM System/370体系结构使用两级存储器结构，并且分别把这两级称为段和页，这里的分段方法缺少本章所描述的关于段的许多特征。对于这个基本的370体系结构，页尺寸可以是2KB或4KB，段大小固定为64KB或1MB。这种方案缺少一般分段系统的那些优点？370的分段方法有什么好处？ 解答

S/370分段系统是固定的且对程序员是不可见的，因此没有一个分段系统的优点在S/370中实现（无保护情况下）每一个段表项的P位提供整个段表的保护。

8.10 假设页尺寸为4KB，页表项大小位4字节。如果要映射一个64位地址空间，并且最顶层的页表对应于一页，则需要几级页表？ 解答

因为每个页表项有4bytes，每个页表有4Kbytes，所以每个页表可以映射1024=210个页，标识出210×212=222bytes的地址空间。然而，地址空间是264bytes。增加一个二层页表，顶层页表指向210个页表，标识出232个页表，将这个过程继续下去就得到：

深度 地址空间 1 222bytes 2 232bytes 3 242bytes 4 252bytes 5 262bytes 6 272bytes（﹥264bytes） 我们可以看到5层是不够表示64位的地址空间，但是6层达到了要求。但是6层中只有2位被使用，而不是全部的10位。所以不是使用72位的虚拟地址空间，而是将除了最低两位外的其他位全部屏蔽忽略。这样将会得到一个64位地址空间，顶层页只有4个页表项。另外一种方法是修改规则将顶层页做成一个单独的物理页并且让它适合4个页。这样将会节省一个页。

8.11 考虑一个系统该系统采用基于页的内存映射，并使用一级页表。假设页表总是在主存中。 a.如果一次存储器访问需要200ns，那么一次需要调页的存储器访问要多长时间？

b.现在增加一个MMU，在命中或未命中时有20ns的开销。如果假设有85%的存储器访问命中都在MMU TLB中，那么哪些是有效的存储器访问时间？ c.解释TLB命中率如何影响有效的存储器访问时间。 解答

a.400ns。200ns用来得到页表项，200ns用来到达存储位置 b.这是一个常见的有效时间计算公式： （220×0.85）+（420×0.15）=250

33

两种情况：第一种，TLB中包含所需的页表项。在这种情况下在200ns外多了20ns的存储访问时间。第二种，TLB中不包含所需的页表项。这时我们会再多花200ns来把所需的页表项取入TLB。

c.TLB命中率越高有效存储器访问时间就越短，因为额外的200ns来得到页表项的时间被节省了。

8.12 考虑一个进程的页访问序列，工作集为M帧，最初都是空的。页访问串的长度为P，包含N个不同的页号。对任何一种页替换算法， a.页错误次数的下限是多少？ b.页错误次数的上限是多少？ 解答 a.N b.P

8.13 在论述一种页替换算法时，一位作者用一个在循环轨道上来回移动的雪犁机来模拟说明：雪均匀地落在轨道上，雪犁机一恒定的速度在轨道上不断的循环，轨道上被扫落的雪从系统中消失。

a.8.2节讨论的哪一种页替换算法可以用它来模拟？ b.这个模拟说明了页替换算法的那些行为？ 解答

a.这是一个很好的时钟算法的类似。雪落在轨道上类似于页到达循环页缓存中。时钟算法时钟算法指针的移动类似于雪犁机的移动。

b.注意到在时钟指针最近的前面可替换页的密度是最高的，就好像在雪犁机最近的前面的雪是最厚的一样。因此我们可以认为时钟算法在寻找替换页时是非常有效的。事实上可以看到雪犁机前雪的厚度是轨道上雪平均厚度的两倍。通过这种类似，在单循环中被时钟策略替换的页的号码是被随机替换的页的号码的两倍。这个近似不是最完美的，因为时钟指针并不是以一个确定的速率移动，但是直观意义还是有的。

8.14 在S/370体系结构中，存储关键字是与实存中每个页帧相关联的控制字段。这个关键字中与页替换有关的有两位：访问位和修改位。当在帧中的任何单元执行写操作时，修改位被置为1；当一个新页被装入到该帧中时，访问位被置为1。请给出一种方法，仅仅使用访问位来确定哪个页帧是最近最少使用的。 解答

处理器硬件置访问位为0当一个新页被加入到帧时，置为1当这个页帧的位置被访问到时。操作系统可以维护几个页帧表队列，一个页帧表项从一个队列移动到另一个队列取决于这个页帧的访问位被值为零的时间长短。当必须有页被替换时，被替换的页将从具有最长未被访问时间的页帧队列中选取。

8.15 考虑如下的页访问序列（序列中的每一个元素都是页号）： 12345213323454511325

定义经过k次访问后平均工作集大小为Sk（△）=1/k∑W（t，△）（t=1—k），并且定义经过k次访问后错过页的概率为Mk（△）=1/k∑F（t，△）（t=1—k），其中如果页错误发生在虚拟时间t，则F（t，△）=1，否则F（t，△）=0。

a.当△=1，2，3，4，5，6时，绘制与图8.19类似的图标来说明刚定义的页访问序列的工作集。

b.写出S20（△）关于△的表达式。 b.写出M20（△）关于△的表达式。 解答 a.

34

b.c.

S20是一个△的增函数，M20是一个△的非增函数。

8.16 VSWS驻留集管理策略的性能关键是Q的值。经验表明，如果对于一个进程使用固定的的Q值，则在不同的执行阶段，页错误发生的频率有很大的差别。此外对不同的进程使用相同的Q值，则发生页错误的频率会完全不同。这些差别表明，如果有一种机制可以在一个进程的生命周期中动态的调整Q得知，则会提高算法的性能。请基于这种目标设计一种简单的机制。 解答

[PIZZ89]推荐使用如下策略。在窗口中使用一个机构在窗口时间调整Q的值作为实际页错误率的函数，页错误率被计算出并且同作为系统值的作业理想页错误率比较。Q的值被上调（下调）当实际的页错误率比理想值高（低）。使用这种调整机制的实验证明可以动态调整Q值的测试作业在每次运行时产生较少的页错误和减小的驻留集，相比于固定Q值的作业的运行（在很大程度上）。存储时间在相对于Q值使用可调整机制时也会产生一个固定且可观的改进，比较于使用固定的Q值。

8.17 假设一个任务被划分为4个大小相等的段，并且系统为每个段建立了一个有8项的页描述符表。因此，该系统是分段与分页的组合。假设页尺寸为2KB。 a.每段的最大尺寸为多少？

b.该任务的逻辑地址空间最大为多少？

c.假设该任务访问到物理单元00021ABC中的一个元素，那么为它产生的逻辑地址的格式是什么？该系统的物理地址最大为多少？ 解答

35

a.8×2K=16k b.16K×4=64K c.232=4GBytes

8.18 考虑一个分页式的逻辑地址空间（由32个2KB的页组成），将它映射到一个1MB的物理内存空间。

a.该处理器的逻辑地址空间格式是什么？

b.页表的长度和宽度是多少（忽略“访问权限”位）？ c.如果物理内存空间减少了一半，则会对页表有什么影响？ 解答 a. 页码（5） 偏移量（11） 36