《现代操作系统第四版》第三章答案

1、第三章 内存管理 习题1.IBM360 有一个设计，为了对 2KB 大小的块进行加锁，会对每个块分配一个4bit的密钥，这个密钥存在PSW (程序状态字)中，每次内存引用时， CPU都 会进行密钥比较。 但该设计有诸多缺陷， 除了描述中所言， 请另外提出至少两条 缺点。A:密钥只有四位，故内存只能同时容纳最多十六个进程；需要用特殊硬件进行 比较，同时保证操作迅速。2. 在图 3-3 中基址和界限寄存器含有相同的值 16384 ，这是巧合， 还是它们总是 相等？如果这只是巧合，为什么在这个例子里它们是相等的？A :巧合。基地址寄存器的值是进程在内存上加载的地址；界限寄存器指示存储 区的长度。3.

2、 交换系统通过紧缩来消除空闲区。假设有很多空闲区和数据段随机分布，并且读或写32位长的字需要10ns的时间，紧缩128MB大概需要多长时间？为了简 单起见，假设空闲区中含有字 0，内存中最高地址处含有有效数据。A: 32bit=4Byte= 每字节 10/4=2.5 ns 128MB=1282A20=2A27Byte对每个字节既要读又要写，22.5*2A27=671ms4. 在一个交换系统中，按内存地址排列的空闲区大小是10MB， 4MB， 20MB，18MB， 7MB， 9MB， 1 2 M B ，和1 5 M B 。对于连续的段请求：(a) 12MB(b) 10MB(c) 9MB 使用首次

3、适配算法， 将找出哪个空闲区？使用最佳适配、 最差适配、 下次适配算 法呢？A： 首次适配算法： 20MB ，10MB ，18MB ； 最佳适配算法： 12MB ，10MB ，9MB； 最差适配算法： 20MB ；18MB ；15MB ； 下次适配算法： 20MB ；18MB ； 9MB；5. 物理地址和虚拟地址有什么区别？A :实际内存使用物理地址。这些是存储器芯片在总线上反应的数字。虚拟地址是指一个进程的地址空间的逻辑地址。因此，具有 32 位字的机器可以生成高达4GB 的虚拟地址，而不管机器的内存是否多于或少于 4GB。6. 对下面的每个十进制虚拟地址，分別使用4KB页面和8KB页面计算

4、虚拟页号和偏移量: 20000 ， 32768， 60000 。A: 转换为二进制分别为: 0100111000100000 虚拟地址应该是 16 位 1000000000000000 1110101001100000 4KB 页面偏移量范围 0 4027，需要 12位来存储偏移量，剩下4位作为页号；同理8KB页面需要13位来存储偏移 量，剩下 3 位作为页号； 所以， 4KB | 8KB 页号 | 偏移量 | 页号 | 偏移量 20000 | 0100 111000100000 | 010 0111000100000 32768 | 1000 000000000000 | 100 00000

5、00000000 60000 | 1110 101001100000 | 111 01010011000007. 使用图 3-9 的页表，给出下面每个虚拟地址对应的物理地址:(a) 20(b) 4100(c) 8300A： (a)20+40962=8212 (b) 4100=4096+ (4100-4096 ) =4100 (c)8300=64096+ (8300-4096*2 )=246848. Inlel 8086 处理器不支持虚拟内存，然而一些公司曾经设计过包含未作任何改 动的 8086 CPU 的分页系统。猜想一下，他们是如何做到这一点的。 (提示：考 虑 MMU 的逻辑位置。)A :

6、他们制作了 MMU，并连接在CPU与地址总线之间，这样从处理器进入 MMU 的地址全部被视为虚拟地址， 并被转换为物理地址， 然后被送到地址总线， 映射 到内存中。9. 为了让分页虚拟内存工作，需要怎样的硬件支持？A :需要一个 MMU 能够将虚拟页面重新映射到物理页面。 此外，当缺页中断时， 需要对操作系统设置陷阱，以便可以获取页面。10. 写时复制是使用在服务器系统上的好方法，它能否在手机上起作用。A: “写时复制 “技术，也就是只有进程空间的各段的内容要发生变化时， 才会将 父进程的内容复制一份给子进程。 如果智能手机支持多重编程， iPhone 、 Android 和 Windows

7、手机都支持多重编程，那么支持多个进程。如果进程发出fork() 系统调用和页面在父进程和子进程之间共享，则复制对写是有意义的。智能手机比服务器小，但从逻辑上讲，它并没有什么不同11. 考虑下面的 C 程序：int XN;int step = M; /M 是某个预定义的常量for (int i = 0; i N; i += step) Xi = Xi + 1;a) 如果这个程序运行在一个页面大小为 4KB且有64个TLB表项的机器上时，M 和 N 取什么值会使得内层循环的每次执行都会引起 TLB 失效 ?b) 如果循环重复很多遍，结果会和 a)的答案相同吗？请解释。A: a)M必须至少为1024

8、，以确保对X元素的每一次访问都有一个 TLB缺失。因 为 N 只影响 X 访问多少次， N 取大于 M 的任何值都可以。 b)M 应该至少是 1024，以确保对X元素的每次访问都遗漏 TLB。但是现在N应该大于64K，以 便处理TLB，也就是说，X应该超过256KB。12. 存储页面必须可用的磁盘空间和下列因素有关： 最大进程数 n ，虚拟地址空间的字节数v，RAM的字节数r，给出最坏情况下磁盘空间需求的表达式。这个数 量的真实性如何？A :所有进程的整个虚拟地址空间为 nv,这就是页面存储所需的。不过，可以在 RAM中存储量为r，因此需要的磁盘存储量仅为 nv-r。该量比实际所需的要大 得多

9、，因为极少有 n 个进程实际运行， 而且这些进程也极少需要其最大允许的虚拟内存13. 如果一条指令执行1ns,缺页中断执行额外的Nns,且每条k指令产生一个缺页，请给出一个公式，计算有效指令时间。A： (1*(k-1)+(1+N)/k = 1+N/k ns14. 一个机器有 32 位地址空间和 8KB 页面,页表完全用硬件实现,页表的每一 表项为一个 32 位字。进程启动时,以每个字 100ns 的速度将页表从内存复制到 硬件中。如果每个进程运行100ms (包含装入页表的时间)用来装人页表的CPU 时间的比例是多少？A: 32 位地址空间构成 4GB 内存空间, 4GB/8KB=512 个页

10、面,页表项 512 项,页表大小512 32=2X4 bit复制页表的时间=2A14/2A5*10ns = 5120 ns, 时间 比例 5120ns/100ms=5120 -10)A( 100 -3)0=51.2% 8KB 页面大小，需要13 位偏移量,故页号有 19 位,页面有 2A19 个,页表项也是 2A19 个,每项 32位字。 2A19 100ns/100ms=52.4288%15. 假设一个机器有 48 位的虚拟地址和 32 位的物理地址。a) 假设页面大小是4KB，如果只有一级页表，那么在页表里有多少页表项？请解释。b) 假设同一系统有32个TLB表项，并且假设一个程序的指令正

11、好能放入一个页，并且该程序顺序地从有数千个页的数组中读取长整型元素。在这种情况下TLB的 效果如何？A:a)页面大小4KB,偏移量有12位，则页号有36位，有2A36项页表项;b)TLB 访问的命中率达 100%。在指令访问下一个页面之前读取数据的命中率是 100%，一个 4KB 大小的页面包含 1024 个长整型数据， 每访问 1024 个数据就会 有一次 TLB 失效。16. 给定一个虚拟内存系统的如下数据：(a) TLB有1024项，可以在1个时钟周期(1ns)内访问。(b) 页表项可以在100时钟周期(100ns)内访问。(c) 平均页面替换时间是6ms。如果TLB处理的页面访问占99

12、%并且0.01%勺页面访问会发生缺页中断，那么 有效地址转换时间是多少？A: 99% 1 ns+1% 99.99% 100ns+1% 0.01% 6ms=7.9999 1ns+0.99% 100ns+0 .01% 6ms601.98ns17. 假设一个机器有 38 位的虚拟地址和 32 位的物理地址。a) 与一级页表比较，多级页表的主要优点是什么？b) 若采用二级页表，页面大小为16KB，每个页表项为4字节，应该对第一级页 表域分配多少位 ,对第二级页表域分配多少位？请解释原因A: a)避免把全部页表一直保存在内存中。 b) ” 16KB个页 估计是指这个二 级页表的大小是16KB，故页表项有

13、16KB/4B=4K个，二级页表域需要12位， 四字节表项说明页面大小是12页面大小16KB，则偏移量需要14位，每个条目4 字节18. 在 3.3.4 节的陈述中，奔腾 Pro 将多级页表中的每个页表项扩展到 64 位，但 仍只能对 4GB 的内存进行寻址。请解释页表项为 64 位时，为何这个陈述正确。A:虽然页表项扩展了，但是虚拟内存地址依然只有32位。19. 个 32 位地址的计算机使用两级页表。 虚拟地址被分成 9 位的顶级页表域、11 位的二级页表域和一个偏移量，页面大小是多少？在地址空间中一共有多少 个页面？A:页面大小与偏移量位数有关=2A12Byte=4KB,每个地址对应内存一

14、个字节， 地址空间的页面数量=2八20个。20. 一个计算机使用 32 位的虚拟地址， 4KB 大小的页面。 程序和数据都位于最低 的页面（04095 ），栈位于最高的页面。如果使用传统（一级）分页，页表中需 要多少个表项？如果使用两级分页，每部分有 10 位，需要多少个页表项？A：32 位地址对应 4GB 内存，有 4GB/4KB=2A20 个页面 ,如果使用传统（一级） 分页：需要 2A20 个页表项；如果使用两级分页，顶级页表有 2A10 个页表项， 其中三项指向二级页表 （程序段、 数据段、堆栈段），二级页表每个也有有 2A10 个页表项，总共 2A12 个页表项。21. 如下是在页大

15、小为 512 字节的计算机上，一个程序片段的执行轨迹。这个程 序在 1020 地址，其栈指针在 8192（栈向 0 生长）。请给出该程序产生的页面访 问串。每个指令（包括立即常数）占 4 个字节（ 1 个字）。指令和数据的访问都要在访问串中计数 将字 6144 载入寄存器 0寄存器 0 压栈调用 5120 处的程序，将返回地址压栈栈指针减去立即数 16比较实参和立即数 4如果相等，跳转到 5152 处A:程序地址范围10201532。页面访问串：6144-8191 5120 8190 81845152. A :每个页面512B , 1020地址属于5121023，即页面1；栈指针 8192 属

16、于 81928704 ，即页面 16，但是栈向 0 生长，故寄存器压 栈到 81918188，属于页面 15；5152 地址属于 51205631，即页面 10. 每 条指令 4 个字节，故第一条指令在地址范围 10201023，属于页面 1；第二条 指令在地址范围 10241027，属于页面 2；第三条指令地址也在页面 2，但是 将数据压栈到页面 15 了。 LOAD 6144,R0 1(I), 12(D) PUSH R0 2(I), 15(D) CALL 5120 2(1), 15(D) JEQ 5152 10(1) 代码(I)指示指令引用，而(D)指示数据引 用。22. 一台计算机的进程

17、在其地址空间有 1024 个页面，页表保存在内存中。 从页表 中读取一个字的开销是5n。为了减小这一开销，该计算机使用了 TLB,它有32 个(虚拟页面，物理页框)对，能在 1ns 内完成查找。请问把平均开销降到 2ns 需要的命中率是多少？23. TLB 需要的相联存储设备如何用硬件实现，这种设计对扩展性意味着什么？A：相联存储器本质上将 key与多个寄存器的内容同时进行比较。对于每个寄存 器，必须有一组比较器， 将寄存器内容中的每个位与正在搜索的键进行比较。 实 现这种设备所需的门 （或晶体管） 的数量是寄存器数量的线性函数， 因此这种设 计对扩展性意味着成本变得昂贵。24. 台机器有48

18、位虚拟地址和32位物理地址，页面大小是8KB，试问页表中 需要多少个表项？A:物理内存是4GB,页面数量是4GB/8KB=2M9 项，页面偏移量需要2A13位， 页表域总共 35 位。25. 一个计算机的页面大小为8KB，内存大小为256KB，虚拟地址空间为64GB， 使用倒排页表实现虚拟内存。为了保证平均散列链的长度小于 1 ，散列表应该多 大？假设散列表的大小为 2 的幂。A:（原答案）内存有 2A28（256KB） / 2A13（8KB） =（2八15）32768 页。32K 的哈希 表的平均链长为 1。为了使之小于 1，必须使用下一个尺寸 （2A16）65536 项。将 32768 项

19、放入 65536 格中使其平均链长为 0.5，以保证快速的查询。 （这个题 目有错吧？内存应该是 256MB 才对） 物理页面数 =256MB/8KB=2A15，若散列表为 2A15 ，则平均散列长度为 1 ，为保证平均散列链长度小于 1 ，散列 表至少为 2A16.26. 一个学生在编译器设计课程中向教授提议了一个项目：编写一个编译器，用来产生页面访问列表， 该列表可以用于实现最优页面置换算法。 试问这是否可能？ 为什么？有什么方法可以改进运行时的分页效率？A :这是不可能的，除了程序的执行过程在编译时是完全可预测的少数情况。如 果编译器收集程序有关调用代码中的位置信息， 则可以在链接时使用

20、此信息来重 新排列目标代码， 以便程序位于它们调用的代码附近。 这将使得进程更可能与所 调用的代码在同一个页面上。当然这从许多地方进行调用的程序来说是无效的。27. 假设虚拟页码索引流中有一些长的页码索引序列的重复，序列之后有时会是 一个随机的页码索引。例如，序列 0 , 1 ,，511 ,431 , 0, 1,，511 , 332 , 0, 1 ,中就包含了 0, 1 ,，511的重复，以及跟随在它们之后的随机页码索 引 431 和 332。a) 在工作负载比该序列短的情况下，标准的页面置换算法( LRU, FIFO, Clock) 在处理换页时为什么效果不好？ b)如果一个程序分配了 50

21、0个页框，请描述一 个效果优于LRU、FIFO或Clock算法的页面置换方法。A: a)标准的页面置换算法是针对已经在内存中的页面研究的。 当工作负载比序 列短时，会出现内存容量不够而长生颠簸，这种情况下 LRU、Clock、FIFO算法 达不到预期的效果，任何访问都会引起缺页除非内存的页框数量大于 512。 b) 如果分配了 500 个页框，那么 0498 号页框是固定的，只有一个页框进行页面 置换28. 如果将FIFO页面罝换算法用到4个页框和8个页面上，若初始时页框为空， 访问字符串为 0172327103 ，请问会发生多少次缺页中断？如果使用 LRU 算法 呢？A： FIFO 6 LR

22、U 729. 考虑图3- 15b中的页面序列。假设从页面B到页面A的R位分别是11011011使用第二次机会算法，被移走的是哪个页面？A：D。30. 一台小计算机有4个页框。在第一个时钟滴答时R位是0111 （页面0是0， 其他页面是 1），在随后的时钟滴答中这个值是 1011、1010、1101、0010、1010、 1100、0001。如果使用带有 8位计数器的老化算法，给出最后一个滴答后 4个 计数器的值。A:0 号页框: 01101110 ； 1 号页框: 01001001 ； 2 号页框: 00110111 ； 3号页框： 10001011 。31. 请给出一个页面访问序列，使得对于

23、这个访问序列，使用Clock和LRU算法 得到的第一个被选择置换的页面不同。 假设一个进程分配了 3个页框，访问串中 的页号属于集合 0， 1， 2， 3。A: 0130123 。 LRU将第3页替换为第2页。Clock将第0页替换为第2页32. 在图3-21c的工作集时钟算法中，表针指向那个R = 0的页面。如果t =400,这个页面将被移出吗？如果 t = 1000呢？（当前时间2204）A:该页面的生存时间是 2204 - 1213 = 991 。如果t = 40Q它就不在工作集中， 最近没有被引用， 所以它将被移出。 t = 1000的情况不同，此时页面在工作集中， 所以它不会被删除。

24、34. 一个学生声称: “抽象来看，除了选取替代页面使用的属性不同外，基本页面 置换算法（FIFO, LRU,最优算法）都相同。”（a） FIFO、LRU、最优算法使用 的属性是什么？（ b）请给出这些页面置换算法的通用算法。A: a） FIFO:加载时间；LRU:最近访问时间；OPT:在未来的最近访问时间 b ）有标签算法和替换算法。标记算法用部分 a给出的属性从大到小标记每个页 面。替换算法删除标签最小的页面。35. 从平均寻道时间10ms、旋转延迟时间10ms、每磁道32KB的磁盘上载入一 个 64KB 的程序，对于下列页面大小分别需要多少时间？a）页面大小为2KB;b）页面大小为 4K

25、B。 假设页面随机地分布在磁盘上，柱面的数目非常大以至于两个页面在同一个柱面的机会可以忽略不计A：a)页面有 64KB/2KB=32 个，32 (10+10 ) =640ms b）页面 16 个，16 20=320ms原答案：（很迷啊，怎么算的传输时间啊？） ：搜索加旋转等待时间为 10 毫秒。对于 2-KB 页面，传输时间约为 0.009766 毫 秒，总共约 10.009766 毫秒。加载这些页面的 32 将花费大约 320.21 毫秒。对 于 4-KB 页面，传输时间加倍到大约 0.01953 毫秒，因此每页的总时间是 10.01953 毫秒。加载这些页面的 16 需要大约 160.31

26、25 毫秒。使用这样快的磁盘，所有 重要的是减少传输的数量（或者连续地将页面放在磁盘上） 。现在我知道是如何计算的了，参考 现代操作系统中文第四版 第 4 章文件 系统 4.4.1 的例子：假设磁盘每道有 1MB ，其旋转时间是 8.33ms ，平均寻道时间为 5m s 。以毫秒为 单位，读取一个 k 字节的块所需要的时间是寻道时间、旋转延迟和传送时间之 和：5 + 4.165 + （k/1000000） x 8.33从中可以得知单位容量传送时间 = 旋转时间 / 每道容量故本题中单位容量传送时间 =2A3/2A15 x 10 = 0.00244 ms/KB42. 人们已经观察到在两次缺页中断

27、之间执行的指令数与分配给程序的页框数直 接成比例。如果可用内存加倍， 缺页中断间的平均间隔也加倍。 假设一条普通指 令需要1 ym,但是如果发生了缺页中断，就需要 2001卩（即2ms处理缺页中 断），如果一个程序运行了 60s，期间发生了 15000次缺页中断，如果可用内存 是原来的两倍，那么这个程序运行需要多少时间？A:该程序发生了 15000次缺页中断，每个缺页中断都需要 2ms的额外处理时 间。处理缺页中断的总开销为30s。这意味着在程序运行的60s内，一半用于缺 页中断开销， 一半用于运行程序。 如果我们运行程序的内存是内存的两倍， 我们 会得到一半的内存页错误，只有 15 秒的页面错误开销，所以总的运行时间将是 45 秒。43. Frugal 计算机公司的一组操作系统设计人员正在考虑在他们的新操作系统中 减少对后备存储数量的需求。 老板建议根本不要把程序正文保存在交换区中， 而 是在需要的时候直接从二进制文件中调页进来。 在什么条件下（如果有这样的条 件话）这种想法适用于程序文本？在什么条件下 （如果有这样的