操作系统第五版答案第8章复习题及习题解答(2)

8.11 考虑一个系统该系统采用基于页的内存映射，并使用一级页表。假设页表总是在主存中。

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

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

两种情况：第一种，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.

操作系统第五版答案

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中的一个元素，那么为它产生的逻辑地址的格式是

操作系统第五版答案

什么？该系统的物理地址最大为多少？ 解答

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

c.232=4GBytes

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

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

b.页表的长度和宽度是多少（忽略“访问权限”位）？

操作系统第五版答案

c.如果物理内存空间减少了一半，则会对页表有什么影响？ 解答

c.如果页表项还是32个且页大小不变，那么每个页表项变为8bits宽

8.19 UNIX内核可以在需要时动态地在虚存中增加一个进程的栈，但却从不缩小这个栈。考虑下面的例子：一个程序调用一个C语言程序，这个子程序在栈中分配一个本地数组，一共需要10KB大小，内核扩展这个栈段来适应它。当这个子程序返回时，内核应该调整栈指针并释放空间，但它却未被释放。解释为什么可以缩小栈以及UNIX内核为什么没有缩小栈。 解答

可以通过释放再分配不使用的页来缩减栈的大小。按照惯例，在超出当前栈顶范围内内存中的值没有定义。在全部的体系结构中，标志栈顶部的指针在一个定义完好的记录中。因此可以读取栈的内容且按要求释放不使用的页。不缩小栈的原因是这样做的效果很小。如果用户程序重复调用子程序需要附加的空间来分配给局部变量（一个很可能的情况），然后许多时间会被浪费在释放重分配栈空间