《操作系统精髓与设计原理·第五版》习题答案(7)

希表项分配最多3个溢出项的空间，则哈希反向页表需要占用多大的内存空间？ 解答

a：4Mbyte

b：行数：26+2=128项。每项包含：20（页号）+20（帧号）+8bits（链索引）=48bits=6bytes。总共：128*6=768bytes

8.4 一个进程分配给4个页帧（下面的所有数字均为十进制数，每一项都是从0开始计数的）。上一次把一页装入到一个页帧的时间，上一次访问页帧中的页的时间，每个页帧中的虚拟页号以及每个页帧的访问位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之间的时钟时间，而不是从事件发生到当前的时钟值）。 虚拟页号 页帧 加载时间 访问时间 R位 M位 2 0 60 161 0 1 1 1 130 160 1 0 0 2 26 162 1 0 3 3 20 163 1 1 当虚拟页4发生错误时，使用下列内存管理策略，哪一个页帧将用于置换？解释原因。 a.FIFO（先进先出）算法 b.LRU（最近最少使用）算法 c.Clock算法

d.最佳（使用下面的访问串）算法

e.在页错误之前给定上述内存状态，考虑下面的虚拟页访问序列： 4,0,0,2,4,2,1,0,3,2

如果使用窗口大小为4的工作集策略来代替固定分配，会发生多少页错误？每个页错误何时发生？ 解答

a:页帧3，在时间20加载，时间最长。

b:页帧1，在时间160访问距现在时间最长。 c:清除页帧3的R位（最早加载），清除页帧2的R位，（次最早加载），换出的是页帧0因为它的R位为0。

d:换出的是页帧3中的虚拟页3，因为它将最晚被访问到。 e:一共有6个错误，如下

8.5 一个进程访问5页：A,B,C,D和E，访问顺序如下： A;B;C;D;A;B;E;A;B;C;D;E

假设置换算法为先进后出，该进程在主存中有三个页帧，开始时为空，请查找在这个访问顺序中传送的页号。对于4个页帧的情况，请重复上面的过程。 解答

分别有9次和10次页错误，这被称之为“Belady′s现象”（\Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine,\by Belady et al, Communications of the ACM, June 1969.）

8.6 一个进程在磁盘上包含8个虚拟页，在主存中固定分配给4个页帧。发生如下顺序的页访问：

31

1,0,2,2,1,7,0,1,2,0,3,0,4,5,1,5,2,4,5,6,7,6,7,2,4,2,7,3,3,2,3

a.如果使用LRU替换策略，给出相继驻留在这4个页帧中的页。计算主存的命中率。假设这些帧最初是空的。

b.如果使用FIFO策略，重复问题（a）。

c.比较使用这两种策略的命中率。解释为什么这个特殊的访问顺序，使用FIFO的效率接近于LRU。 解答

a:LRU：命中率=16/33

b:FIFO：命中率=16/33

c:这两种策略对这个特殊的页轨迹（执行顺序）是等效的。

8.7 在VAX中，用户页表以系统空间的虚拟地址进行定位。让用户页表位于虚存而不是主存中有什么好处？有什么缺点？ 解答

最主要的优点是在物理内存空间上的节省。这主要是两方面的原因：（1）一个用户页表可以仅当使用时才取入内存。（2）操作系统可以动态的分配用户页表，产生一个页表仅当程序被创建时。

当然，也有一个缺点：地址转换需要多余的工作。 8.8 假设在主存中执行下列程序语句： for(i=1;i≤n;i++)

a[i]=b[i]+c[i]; 页尺寸为1000个字。令n=1000。使用一台具有所有寄存器指令并使用了索引寄存器的机器，写出实现上述语句的一个假想程序，然后给出在执行过程中的页访问顺序。 解答

由机器语言编写的程序，在主存中地址4000处开始运行。运行情况如下： 4000 （R1）←1 建立索引记录i 4001 （R1）←n 在R2中建立n 4002 比较R2，R1 检查i﹥n 4003 如果大于则跳转到4009

4004 （R3）←B（R1） 使用索引记录R1到达B[i]

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

32

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

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

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

8.12 考虑一个进程的页访问序列，工作集为M帧，最初都是空的。页访问串的长度为P，包

33

含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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库《操作系统精髓与设计原理·第五版》习题答案(7)在线全文阅读。