操作系统第五版答案第8章复习题及习题解答30377.pdf

《操作系统第五版答案第8章复习题及习题解答30377.pdf》由会员分享，可在线阅读，更多相关《操作系统第五版答案第8章复习题及习题解答30377.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、虚拟内存 简单分页与虚拟分页有什么区别 简单分页：一个程序中的所有的页都必须在主存储器中程序才能正常运行，除非使用覆盖技术。虚拟内存分页：不是程序的每一页都必须在主存储器的帧中来使程序运行，页在需要的时候进行读取。解释什么是抖动。虚拟内存结构的震动现象，在这个过程中处理器大部分的时间都用于交换块，而不是执行指令。为什么在使用虚拟内存时，局部性原理是至关重要的 可以根据局部性原理设计算法来避免抖动。总的来说，局部性原理允许算法预测哪一个当前页在最近的未来是最少可能被使用的，并由此就决定候选的替换出的页。哪些元素是页表项中可以找到的元素简单定义每个元素。帧号：用来表示主存中的页来按顺序排列的号码。

2、存在位（P）：表示这一页是否当前在主存中。修改位（M）：表示这一页在放进主存后是否被修改过。转移后备缓冲器的目的是什么 转移后备缓冲器（TLB）是一个包含最近经常被使用过的页表项的高速缓冲存储器。它的目的是为了减少从磁盘中恢复一个页表项所需的时间。简单定义两种可供选择的页读取策略。在请求式分页中，只有当访问到某页中的一个单元时才将该页取入主存。在预约式分页中，读取的并不是页错误请求的页。驻留集管理和页替换策略有什么区别 驻留集管理主要关注以下两个问题：（1）给每个活动进程分配多少个页帧。（2）被考虑替换的页集是仅限在引起页错误的进程的驻留集中选择还是在主存中所有的页帧中选择。页替换策略关注的是

3、以下问题：在考虑的页集中，哪一个特殊的页应该被选择替换。FIFO 和 Clock 页替换算法有什么区别 时钟算法与 FIFO 算法很接近，除了在时钟算法中，任何一个使用位为一的页被忽略。页缓冲实现的是什么（1）被替换出驻留集的页不久又被访问到时，仍在主存中，减少了一次磁盘读写。（2）被修改的页以簇的方式被写回，而不是一次只写一个，这就大大减少了 I/O 操作的数目，从而减少了磁盘访问的时间。为什么不可能把全局替换策略和固定分配策略组合起来 固定分配策略要求分配给一个进程的帧的数目是确定的，当一个进程中取入一个新的页时，这个进程的驻留页集中的一页必须被替换出来（保持分配的帧的数目不变），这是一种

4、局部替换策略。驻留集和工作集有什么区别 一个进程的驻留集是指当前在主存中的这个进程的页的个数。一个进程的工作集是指这个进程最近被使用过的页的个数。请求式清除和预约式清除有什么区别 在请求式清除中，只有当一页被选择用于替换时才被写回辅存；在预约式清除中，将这些被修改的多个页在需要用到它们所占据的页帧之前成批的写回辅存。习题解答 假设在处理器上执行的进程的也表如下所示。所有数字均为十进制数，每一项都是从 0 开始记数的，并且所有的地址都是内存字节地址。页尺寸为 1024 个字节。虚拟页号 有效位 访问位 修改位 页帧号 0 1 1 0 4 1 1 1 1 7 2 0 0 0 3 1 0 0 2 4

5、 0 0 0 5 1 0 1 0 a 描述 CPU 产生的虚拟地址通常是如何转化成一个物理主存地址的。b 下列虚拟地址对应于哪个物理地址（不用考略页错误）（i）1052 （ii）2221 （iii）5499 解答 a：由虚拟地址求得页号和偏移量，用虚拟页号作为索引页表，得到页帧号，联系偏移量得到物理地址 b:(i)1052=1024+28 查表对应的页帧号是 7，因此物理地址为 7*1024+28=7196(ii)2221=2*1024+173 此时出现页错误(iii)5499=5*1024+379 对应的页帧号为 0 因此物理地址是 379 考虑一个使用 32 位的地址和 1KB 大小的页的

6、分页虚拟内存系统。每个页表项需要 32 位。需要限制页表的大小为一个页。a页表一共需要使用几级 b每一级页表的大小是多少提示：一个页表的大小比较小。c在第一级使用的页较小与在最底下一级使用的页较小相比，那种策略使用最小个数的页 解答 a：虚拟内存可以分为 232/210=222 页，所以需要 22 个 bit 来区别虚拟内存中的一页，每一个页表可以包含 210/4=28 项，因此每个页表可以包含 22bit 中的 8 个 bit，所以需要三级索引。b：第二级页表有 28 个页表项，第一级页表有 26 个页表项。c：如果顶层有 26 个页表项将会减少使用空间，在这种情况下，中间层页表有 26 个

7、并且每个都有 28 个页表项，底层有 214 个页并且每个都有 28 个页表项，因此共有 1+26+214 页=16,449 页。如果中间层有 26 个页表项，那么总的页数有 1+28+214 页=16,641 页。如果底层有 26 个页表项，那么总的页表数是 1+28+216 页=65,973 页。a：图中的用户表需要多少内存空间 b：假设需要设计一个哈希反向页表来实现与图中相同的寻址机制，使用一个哈希函数来将 20 位页号映射到 6 位哈希表。表项包含页号帧号和链指针。如果页表可以给每个哈希表项分配最多 3 个溢出项的空间，则哈希反向页表需要占用多大的内存空间 解答 a：4Mbyte b：

8、行数：26+2=128 项。每项包含：20（页号）+20（帧号）+8bits（链索引）=48bits=6bytes。总共：128*6=768bytes 一个进程分配给 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

9、 20 163 1 1 当虚拟页 4 发生错误时，使用下列内存管理策略，哪一个页帧将用于置换解释原因。（先进先出）算法（最近最少使用）算法 算法 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:换

10、出的是页帧 3 中的虚拟页 3，因为它将最晚被访问到。e:一共有 6 个错误，如下 一个进程访问 5 页：A,B,C,D 和 E，访问顺序如下：A;B;C;D;A;B;E;A;B;C;D;E 假设置换算法为先进后出，该进程在主存中有三个页帧，开始时为空，请查找在这个访问顺序中传送的页号。对于 4 个页帧的情况，请重复上面的过程。解答 分别有 9 次和 10 次页错误，这被称之为“Beladys 现象”（An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine,by Belad

11、y et al,Communications of the ACM,June 1969.）一个进程在磁盘上包含 8 个虚拟页，在主存中固定分配给 4 个页帧。发生如下顺序的页访问：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:F

12、IFO：命中率=16/33 c:这两种策略对这个特殊的页轨迹（执行顺序）是等效的。在 VAX 中，用户页表以系统空间的虚拟地址进行定位。让用户页表位于虚存而不是主存中有什么好处有什么缺点 解答 最主要的优点是在物理内存空间上的节省。这主要是两方面的原因：（1）一个用户页表可以仅当使用时才取入内存。（2）操作系统可以动态的分配用户页表，产生一个页表仅当程序被创建时。当然，也有一个缺点：地址转换需要多余的工作。假设在主存中执行下列程序语句：for(i=1;in;i+)ai=bi+ci;页尺寸为 1000 个字。令 n=1000。使用一台具有所有寄存器指令并使用了索引寄存器的机器，写出实现上述语句的

13、一个假想程序，然后给出在执行过程中的页访问顺序。解答 由机器语言编写的程序，在主存中地址 4000 处开始运行。运行情况如下：4000 （R1）1 建立索引记录 i 4001 （R1）n 在 R2 中建立 n 4002 比较 R2，R1 检查 in 4003 如果大于则跳转到 4009 4004 （R3）B（R1）使用索引记录 R1 到达 Bi 4005 （R3）（R3）+C（R1）使用索引记录 R1 加上 Ci 4006 A（R1）（R3）使用索引记录 R1 将总和存入 Ai中 4007 （R1）（R1）+1 i 加一 4008 跳到 4002 60006999 存储 A 70007999

14、存储 B 80008999 存储 C 9000 存储 1 9001 存储 n 由这个循环产生的参考串为 494944（444）1000 包括个参考，但仅包括 5 个不寻常的页 IBM System/370 体系结构使用两级存储器结构，并且分别把这两级称为段和页，这里的分段方法缺少本章所描述的关于段的许多特征。对于这个基本的 370 体系结构，页尺寸可以是2KB 或 4KB，段大小固定为 64KB 或 1MB。这种方案缺少一般分段系统的那些优点 370 的分段方法有什么好处 解答 S/370 分段系统是固定的且对程序员是不可见的，因此没有一个分段系统的优点在 S/370 中实现（无保护情况下）每

15、一个段表项的 P 位提供整个段表的保护。假设页尺寸为 4KB，页表项大小位 4 字节。如果要映射一个 64 位地址空间，并且最顶层的页表对应于一页，则需要几级页表 解答 因为每个页表项有 4bytes，每个页表有 4Kbytes，所以每个页表可以映射 1024=210 个页，标识出 210212=222bytes 的地址空间。然而，地址空间是 264bytes。增加一个二层页表，顶层页表指向 210 个页表，标识出 232 个页表，将这个过程继续下去就得到：深度 地址空间 1 222bytes 2 232bytes 3 242bytes 4 252bytes 5 262bytes 6 272b

16、ytes（264bytes）我们可以看到 5 层是不够表示 64 位的地址空间，但是 6 层达到了要求。但是 6 层中只有 2位被使用，而不是全部的 10 位。所以不是使用 72 位的虚拟地址空间，而是将除了最低两位外的其他位全部屏蔽忽略。这样将会得到一个 64 位地址空间，顶层页只有 4 个页表项。另外一种方法是修改规则将顶层页做成一个单独的物理页并且让它适合 4 个页。这样将会节省一个页。考虑一个系统该系统采用基于页的内存映射，并使用一级页表。假设页表总是在主存中。a.如果一次存储器访问需要 200ns，那么一次需要调页的存储器访问要多长时间 b.现在增加一个 MMU，在命中或未命中时有

17、20ns 的开销。如果假设有 85%的存储器访问命中都在 MMU TLB 中，那么哪些是有效的存储器访问时间 c.解释 TLB 命中率如何影响有效的存储器访问时间。解答。200ns 用来得到页表项，200ns 用来到达存储位置 b.这是一个常见的有效时间计算公式：（220）+（420）=250 两种情况：第一种，TLB 中包含所需的页表项。在这种情况下在 200ns 外多了 20ns 的存储访问时间。第二种，TLB 中不包含所需的页表项。这时我们会再多花 200ns 来把所需的页表项取入 TLB。命中率越高有效存储器访问时间就越短，因为额外的 200ns 来得到页表项的时间被节省了。考虑一个进

18、程的页访问序列，工作集为 M 帧，最初都是空的。页访问串的长度为 P，包含N 个不同的页号。对任何一种页替换算法，a.页错误次数的下限是多少 b.页错误次数的上限是多少 解答 在论述一种页替换算法时，一位作者用一个在循环轨道上来回移动的雪犁机来模拟说明：雪均匀地落在轨道上，雪犁机一恒定的速度在轨道上不断的循环，轨道上被扫落的雪从系统中消失。节讨论的哪一种页替换算法可以用它来模拟 b.这个模拟说明了页替换算法的那些行为 解答 a.这是一个很好的时钟算法的类似。雪落在轨道上类似于页到达循环页缓存中。时钟算法时钟算法指针的移动类似于雪犁机的移动。b.注意到在时钟指针最近的前面可替换页的密度是最高的，

19、就好像在雪犁机最近的前面的雪是最厚的一样。因此我们可以认为时钟算法在寻找替换页时是非常有效的。事实上可以看到雪犁机前雪的厚度是轨道上雪平均厚度的两倍。通过这种类似，在单循环中被时钟策略替换的页的号码是被随机替换的页的号码的两倍。这个近似不是最完美的，因为时钟指针并不是以一个确定的速率移动，但是直观意义还是有的。在 S/370 体系结构中，存储关键字是与实存中每个页帧相关联的控制字段。这个关键字中与页替换有关的有两位：访问位和修改位。当在帧中的任何单元执行写操作时，修改位被置为 1；当一个新页被装入到该帧中时，访问位被置为 1。请给出一种方法，仅仅使用访问位来确定哪个页帧是最近最少使用的。解答

20、处理器硬件置访问位为 0 当一个新页被加入到帧时，置为 1 当这个页帧的位置被访问到时。操作系统可以维护几个页帧表队列，一个页帧表项从一个队列移动到另一个队列取决于这个页帧的访问位被值为零的时间长短。当必须有页被替换时，被替换的页将从具有最长未被访问时间的页帧队列中选取。考虑如下的页访问序列（序列中的每一个元素都是页号）：4511325 定义经过 k 次访问后平均工作集大小为 Sk（）=1/kW（t，）（t=1k），并且定义经过k 次访问后错过页的概率为 Mk（）=1/kF（t，）（t=1k），其中如果页错误发生在虚拟时间 t，则 F（t，）=1，否则 F（t，）=0。a.当=1，2，3，4，

21、5，6 时，绘制与图类似的图标来说明刚定义的页访问序列的工作集。b.写出 S20（）关于的表达式。b.写出 M20（）关于的表达式。解答 a.S20 是一个的增函数，M20 是一个的非增函数。VSWS 驻留集管理策略的性能关键是 Q 的值。经验表明，如果对于一个进程使用固定的的Q 值，则在不同的执行阶段，页错误发生的频率有很大的差别。此外对不同的进程使用相同的 Q 值，则发生页错误的频率会完全不同。这些差别表明，如果有一种机制可以在一个进程的生命周期中动态的调整 Q 得知，则会提高算法的性能。请基于这种目标设计一种简单的机制。解答 PIZZ89推荐使用如下策略。在窗口中使用一个机构在窗口时间调

22、整 Q 的值作为实际页错误率的函数，页错误率被计算出并且同作为系统值的作业理想页错误率比较。Q 的值被上调（下调）当实际的页错误率比理想值高（低）。使用这种调整机制的实验证明可以动态调整 Q 值的测试作业在每次运行时产生较少的页错误和减小的驻留集，相比于固定 Q 值的作业的运行（在很大程度上）。存储时间在相对于 Q 值使用可调整机制时也会产生一个固定且可观的改进，比较于使用固定的 Q 值。假设一个任务被划分为 4 个大小相等的段，并且系统为每个段建立了一个有 8 项的页描述符表。因此，该系统是分段与分页的组合。假设页尺寸为 2KB。a.每段的最大尺寸为多少 b.该任务的逻辑地址空间最大为多少

23、c.假设该任务访问到物理单元 00021ABC 中的一个元素，那么为它产生的逻辑地址的格式是什么该系统的物理地址最大为多少 解答 2K=16k 4=64K=4GBytes 考虑一个分页式的逻辑地址空间（由 32 个 2KB 的页组成），将它映射到一个 1MB 的物理内存空间。a.该处理器的逻辑地址空间格式是什么 b.页表的长度和宽度是多少（忽略“访问权限”位）c.如果物理内存空间减少了一半，则会对页表有什么影响 解答 a.页码（5）偏移量（11）个页表项长，每个页表项 9 个 bits 宽 c.如果页表项还是 32 个且页大小不变，那么每个页表项变为 8bits 宽 UNIX 内核可以在需要时

24、动态地在虚存中增加一个进程的栈，但却从不缩小这个栈。考虑下面的例子：一个程序调用一个 C 语言程序，这个子程序在栈中分配一个本地数组，一共需要10KB 大小，内核扩展这个栈段来适应它。当这个子程序返回时，内核应该调整栈指针并释放空间，但它却未被释放。解释为什么可以缩小栈以及 UNIX 内核为什么没有缩小栈。解答 可以通过释放再分配不使用的页来缩减栈的大小。按照惯例，在超出当前栈顶范围内内存中的值没有定义。在全部的体系结构中，标志栈顶部的指针在一个定义完好的记录中。因此可以读取栈的内容且按要求释放不使用的页。不缩小栈的原因是这样做的效果很小。如果用户程序重复调用子程序需要附加的空间来分配给局部变量（一个很可能的情况），然后许多时间会被浪费在释放重分配栈空间