1、现代操作系统第四版本第三章含答案第三章 内存管理 习题 有一个设计，为了对 2KB 大小的块进行加锁，会对每个块分配一个4bit 的密钥，这个密钥存在 PSW（程序状态字）中，每次内存引用时， CPU 都会进行密钥比较。 但该设计有诸多弊端， 除了描述中所言， 请其他提出最少两条弊端。A：密钥只有四位，故内存只能同时容纳最多十六个进度；需要用特别硬件进行比较，同时保证操作迅速。2.在图 3-3 中基址和界线寄存器含有相同的值 16384 ，这是巧合，还是它们总是相等？若是这可是巧合，为什么在这个例子里它们是相等的？A：巧合。基地址寄存器的值是进度在内存上加载的地址；界线寄存器指示储藏区的长度。
2、3.交换系统经过缩短来除掉悠闲区。假设有很多悠闲区和数据段随机分布，而且读或写 32 位长的字需要 10ns 的时间，缩短 128MB 大概需要多长时间？为了简单起见，假设悠闲区中含有字 0，内存中最高地址处含有有效数据。A：32bit=4Byte= 每字节 10/4=2.5ns 128MB=128220=227Byte 对每个字节既要读又要写， 22.5*227=671ms4.在一个交换系统中，按内存地址排列的悠闲区大小是 10MB ，4MB ，20MB ，18MB ，7MB ，9MB ，12MB ，和 15MB 。对于连续的段央求：(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：变换为二进制分别为： 虚假地址应该是 16 位 页面偏移量范围 04027 ，需要12 位来储藏偏移量，剩下 4 位作为页号； 同理 8KB 页面需要 13 位来储藏偏移量，剩下 3 位作为页号； 因此， 4KB | 8KB 页号 | 偏移量 | 页号 | 偏移量20000 | 0100 | 010 32768 | 1000000000000000 | 100 0000000000000 60000 | 1110 | 1117. 使用图 3-9 的页表，给出下面每个虚假地址对应的物理地址：(a)20(b)4100(c)8300A
5、： （ a） 20+40962=8212 （ b） 4100=4096+ （4100-4096 ） =4100 （ c）8300=64096+ （8300-4096*2 ）=246848.Inlel 8086 办理器不支持虚假内存，但是一些公司从前设计过包括未作任何改动的 8086 CPU 的分页系统。猜想一下，他们是怎样做到这一点的。 （提示：考虑 MMU 的逻辑地址。）A：他们制作了 MMU ，并连接在 CPU 与地址总线之间，这样从办理器进入 MMU的地址全部被视为虚假地址， 并被变换为物理地址， 尔后被送到地址总线， 照射到内存中。9.为了让分页虚假内存工作，需要怎样的硬件支持？A：需
6、要一个 MMU 能够将虚假页面重新照射到物理页面。 其他，当缺页中断时，需要对操作系统设置骗局，以便能够获取页面。10.写时复制是使用在服务器系统上的好方法，它可否在手机上起作用。A： “写时复制 “技术，也就是只有进度空间的各段的内容要发生变化时， 才会将父进度的内容复制一份给子进度。 若是智妙手机支持多重编程， iPhone 、Android 和 Windows 手机都支持多重编程，那么支持多个进度。若是进度发出fork() 系统调用和页面在父进度和子进度之间共享，则复制对写是有意义的。智妙手机比服务器小，但从逻辑上讲，它并没有什么不相同。11.考虑下面的 C 程序：int XN;int
7、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 ，以保证对 X 元素的每一次接见都有一个 TLB 缺失。因为 N 只影响 X 接见多少次， N 取大于 M 的任何值都能够。 b)M 应该最少是1024 ，以保证对 X 元素的每次接见都遗漏 TLB。但是现在 N 应
8、该大于 64K，以便办理 TLB，也就是说， X 应该高出 256KB 。12.储藏页面必定可用的磁盘空间和以下因素有关： 最大进度数 n ，虚假地址空间的字节数 v，RAM 的字节数 r，给出最坏状况下磁盘空间需求的表达式。这个数量的真实性怎样？A：全部进度的整个虚假地址空间为 nv ，这就是页面储藏所需的。但是，能够在RAM 中储藏量为 r，因此需要的磁盘储藏量仅为 nv-r 。该量比本质所需的要大得多，因为很稀有 n 个进度本质运行， 而且这些进度也极少需要其最大赞同的虚拟内存。13.若是一条指令执行 1ns，缺页中断执行额外的 Nns ，且每条 k 指令产生一个缺页，请给出一个公式，计
9、算有效指令时间。A： (1*(k-1)+(1+N)/k = 1+N/k ns14.一个机器有 32 位地址空间和 8KB 页面，页表完好用硬件实现，页表的每一表项为一个 32 位字。进度启动时，以每个字 100ns 的速度将页表从内存复制到硬件中。若是每个进度运行 100ms（包括装入页表的时间） 用来装人页表的 CPU时间的比率是多少？A:32 位地址空间构成 4GB 内存空间， 4GB/8KB=512 个页面，页表项 512 项，页表大小 512 32=214 bit,复制页表的时间 =214/25*10ns = 5120 ns, 时间比率 5120ns/100ms=5120 -10(9)
10、/ 100 -3)10(=51.2% 8KB 页面大小，需要13 位偏移量，故页号有 19 位，页面有 219 个，页表项也是 219 个，每项 32位字。 219 100ns/100ms=52.4288%15.假设一个机器有 48 位的虚假地址和 32 位的物理地址。a)假设页面大小是 4KB，若是只有一级页表，那么在页表里有多少页表项？ 请讲解。b)假设同一系统有 32 个 TLB 表项，而且假设一个程序的指令正好能放入一个页，而且该程序次序地从有数千个页的数组中读取长整型元素。 在这种状况下 TLB 的收效怎样？A： a）页面大小 4KB，偏移量有 12 位，则页号有 36 位，有 23
11、6 项页表项；b）TLB 接见的命中率达 100%。在指令接见下一个页面从前读取数据的命中率是100%，一个 4KB 大小的页面包括 1024 个长整型数据， 每接见 1024 个数据就会有一次 TLB 无效。16.给定一个虚假内存系统的以下数据：（a） TLB 有 1024 项，能够在 1 个时钟周期（ 1ns）内接见。（b）页表项能够在 100 时钟周期（ 100ns ）内接见。（c）平均页面取代时间是 6ms。若是 TLB 办理的页面接见占 99%，而且 0.01%的页面接见会发生缺页中断，那么有效地址变换时间是多少？A ： 99%1ns+1%99.99%100ns+1%0.01%6ms
12、=7.99%8991ns+0.99%100ns+0.01%17.假设一个机器有 38 位的虚假地址和 32 位的物理地址。a)与一级页表比较，多级页表的主要优点是什么？b)若采用二级页表，页面大小为 16KB，每个页表项为 4 字节，应该对第一级页表域分配多少位 ,对第二级页表域分配多少位？请讲解原因A： a）防备把全部页表素来保存在内存中。 b ） ”16KB个页 “估计是指这个二级页表的大小是 16KB，故页表项有 16KB/4B=4K 个，二级页表域需要 12 位，四字节表项说明页面大小是 12 页面大小 16KB，则偏移量需要 14 位，每个条目4字节18.在3.3.4 节的陈述中，奔
13、跑Pro将多级页表中的每个页表项扩展到64 位，但仍只能对 4GB 的内存进行寻址。请讲解页表项为A：诚然页表项扩展了，但是虚假内存地址仍旧只有64 位时，为什么这个陈述正确。32 位。19.个 32 位地址的计算机使用两级页表。 虚假地址被分成 9 位的顶级页表域、11位的二级页表域和一个偏移量，页面大小是多少？在地址空间中一共有多少个页面？A： 页面大小与偏移量位数有关 =212Byte=4KB, 每个地址对应内存一个字节，地址空间的页面数量 =220 个。20.一个计算机使用 32 位的虚假地址， 4KB 大小的页面。程序和数据都位于最低的页面（ 04095 ），栈位于最高的页面。若是使
14、用传统（一级）分页，页表中需要多少个表项？若是使用两级分页，每部分有 10 位，需要多少个页表项？A：32 位地址对应 4GB 内存，有 4GB/4KB=220 个页面 ,若是使用传统（一级）分页：需要 220 个页表项；若是使用两级分页，顶级页表有 210 个页表项，其中三项指向二级页表 （程序段、 数据段、货仓段），二级页表每个也有有 210个页表项，总合 212 个页表项。21.以下是在页大小为 512 字节的计算机上，一个程序片段的执行轨迹。这个程序在 1020 地址，其栈指针在 8192 （栈向 0 生长）。请给出该程序产生的页面访问串。每个指令（包括马上常数）占 4 个字节（ 1
15、个字）。指令和数据的接见都要在接见串受骗数。将字 6144 载入寄存器 0寄存器 0 压栈调用 5120 处的程序，将返回地址压栈栈指针减去马上数 16比较实参和马上数 4若是相等，跳转到 5152 处A：程序地址范围 1020 1532 。 页面接见串： 6144-8191 5120 8190 8184 5152. A ：每个页面 512B ，1020 地址属于 512 1023 ，即页面1；栈指针 8192 属于 8192 8704 ，即页面 16，但是栈向 0 生长，故寄存器压栈到 8191 8188 ，属于页面 15 ；5152 地址属于 5120 5631 ，即页面 10. 每条指令
16、 4 个字节，故第一条指令在地址范围 1020 1023 ，属于页面 1；第二条指令在地址范围 1024 1027 ，属于页面 2；第三条指令地址也在页面 2，但是将数据压栈到页面 15 了。 LOAD 6144,R0 1(I), 12(D) PUSH R0 2(I), 15(D) CALL5120 2(I), 15(D) JEQ 5152 10(I) 代码（ I ）指示指令引用，而（ D）指示数据引用。22.一台计算机的进度在其地址空间有 1024 个页面，页表保存在内存中。 从页表中读取一个字的开销是 5n 。为了减小这一开销，该计算机使用了 TLB，它有 32个（虚假页面，物理页框）对，
17、能在 1ns 内完成查找。请问把平均开销降到 2ns需要的命中率是多少？A： p1+(5+1)（1-p ）23.TLB 需要的相联储藏设备怎样用硬件实现，这种设计对扩展性意味着什么？A:相联储藏器本质大将 key 与多个寄存器的内容同时进行比较。对于每个寄存器，必定有一组比较器， 将寄存器内容中的每个位与正在找寻的键进行比较。 实现这种设备所需的门 （或晶体管） 的数量是寄存器数量的线性函数， 因此这种设计对扩展性意味着成本变得昂贵。24.一台机器有 48 位虚假地址和 32 位物理地址，页面大小是 8KB，试问页表中需要多少个表项？A:物理内存是 4GB，页面数量是 4GB/8KB=219
18、项，页面偏移量需要 213 位，页表域总合 35 位。25.一个计算机的页面大小为 8KB，内存大小为 256KB ，虚假地址空间为 64GB，使用倒排页表实现虚假内存。为了保证平均散列链的长度小于 1，散列表应该多大？假设散列表的大小为 2 的幂。A：（原答案）内存有 228(256KB) / 213(8KB) =(215)32768 页。32K 的哈希表的平均链长为 1。为了使之小于 1，必定使用下一个尺寸 (216)65536 项。将32768 项放入 65536 格中使其平均链长为 0.5 ，以保证迅速的盘问。 （这个题目有错吧？内存应该是 256MB 才对） 物理页面数 =256MB
19、/8KB=215 ，若散列表为 215 ，则平均散列长度为 1，为保证平均散列链长度小于 1，散列表最少为 216.26.一个学生在 器 程中向教授提 了一个 目： 写一个 器，用来 生 面 列表， 列表能够用于 最 面置 算法。 可否可能？ 什么？有什么方法能够改 运行 的分 效率？A： 是不能能的，除了程序的 行 程在 是完好可 的少许状况。如果 器收集程序有关 用代 中的地址信息， 能够在 接 使用此信息来重新排列目 代 ， 以便程序位于它 用的代 周边。 将使得 程更可能与所 用的代 在同一个 面上。自然 从 多地方 行 用的程序来 是无效的。27.假 虚 索引流中有一些 的 索引序列
20、的重复，序列此后有 会是一个随机的 索引。比方，序列 0 ，1，511 ，431 ，0，1，511 ，332 ，0，1，中就包括了 0，1，511 的重复，以及随从在它 此后的随机 索引 431 和 332。a)在工作 比 序列短的状况下， 准的 面置 算法（ LRU，FIFO，Clock)在 理 什么收效不好？ b)若是一个程序分配了 500 个 框， 描述一个收效 于 LRU、FIFO 或 Clock 算法的 面置 方法。A： a) 准的 面置 算法是 已 在内存中的 面研究的。 当工作 比序列短 ，会出 内存容量不 而 生 簸， 种状况下 LRU、Clock 、FIFO 算法达不到 期的
21、收效，任何 都会引起缺 除非内存的 框数量大于 512 。 b)若是分配了 500 个 框，那么 0498 号 框是固定的，只有一个 框 行 面置 。28.若是将 FIFO 页面罝换算法用到 4 个页框和 8 个页面上，若初始时页框为空，接见字符串为 0172327103 ，请问会发生多少次缺页中断？若是使用 LRU 算法呢？A： FIFO 6 LRU 729.考虑图 3- 15b 中的页面序列。假设从页面 B 到页面 A 的 R 位分别是 11011011 。使用第二次机遇算法，被移走的是哪个页面？A：D。30.一台小计算机有 4 个页框。在第一个时钟滴答时 R 位是 0111（页面 0 是
22、 0，其他页面是 1），在随后的时钟滴答中这个值是 1011 、1010 、1101 、0010 、1010 、1100 、 0001 。若是使用带有 8 位计数器的老化算法，给出最后一个滴答后 4 个计数器的值。A： 0 号页框： 01101110 ； 1 号页框： 01001001 ； 2 号页框： 00110111 ； 3号页框： 10001011 。31.请给出一个页面接见序列， 使得对于这个接见序列， 使用 Clock 和 LRU 算法获取的第一个被选择置换的页面不相同。 假设一个进度分配了 3 个页框，接见串中的页号属于会集 0，1，2，3。A： 0130123 。 LRU 将第
23、3 页取代为第 2 页。 Clock 将第 0 页取代为第 2 页。32.在图 3-21c 的工作集时钟算法中， 表针指向那个 R = 0 的页面。若是 =400，这个页面将被移出吗？若是 = 1000呢？（当前时间 2204 ）A：该页面的生计时间是 2204 - 1213 = 991 。若是 = 400，它就不在工作集中，近来没有被引用，因此它将被移出。 = 1000的状况不相同，此时页面在工作集中，因此它不会被删除。34.一个学生声称： “抽象来看，除了采用取代页面使用的属性不相同外，基本页面置换算法（ FIFO，LRU，最优算法）都相同。 ”（a）FIFO、LRU、最优算法使用的属性是
24、什么？（ b）请给出这些页面置换算法的通用算法。A： a）FIFO：加载时间； LRU：近来接见时间； OPT：在未来的近来接见时间b）有标签算法和取代算法。标记算法用部分 a 给出的属性从大到小标记每个页面。取代算法删除标签最小的页面。35.从平均寻道时间 10ms 、旋转延缓时间 10ms 、 每磁道 32KB 的磁盘上载入一个 64KB 的程序，对于以下页面大小分别需要多少时间？a)页面大小为 2KB；b)页面大小为 4KB。假设页面随机地分布在磁盘上，柱面的数量特别大以致于两个页面在同一个柱面的机遇能够忽略不计。A： a）页面有 64KB/2KB=32 个， 32（10+10 ）=64
25、0msb）页面 16 个， 1620=320ms原答案：（很迷啊，怎么算的传输时间啊？） ：找寻加旋转等待时间为 10 毫秒。对于 2-KB 页面，传输时间约为 0.009766 毫秒，总合约 10.009766 毫秒。加载这些页面的 32 将开销大概 320.21 毫秒。对于 4-KB 页面，传输时间加倍到大概 0.01953 毫秒，因此每页的总时间是 毫秒。加载这些页面的 16 需要大概 160.3125 毫秒。使用这样快的磁盘，全部重要的是减少传输的数量（也许连续地将页面放在磁盘上） 。现在我知道是怎样计算的了，参照 现代操作系统中文第四版 第 4 章文件系统 4.4.1 的例子：假设磁
26、盘每道有单位，读取一个和：1MB ，其旋转时间是 8.33ms ，平均寻道时间为 5ms 。以毫秒为k字节的块所需要的时间是寻道时间、旋转延和缓传达时间之从中能够得知单位容量传达时间 = 旋转时间 / 每道容量故本题中单位容量传达时间 = 23/215 x 10 = 0.00244 ms/KB42.人们已经观察到在两次缺页中断之间执行的指令数与分配给程序的页框数直接成比率。若是可用内存加倍， 缺页中断间的平均间隔也加倍。 假设一条一般指令需要 1 m，但是若是发生了缺页中断，就需要 2001 （s即 2ms 办理缺页中断），若是一个程序运行了 60s，期间发生了 15000 次缺页中断，若是可
27、用内存是原来的两倍，那么这个程序运行需要多少时间？A：该程序发生了 15000 次缺页中断，每个缺页中断都需要 2ms 的额外办理时间。办理缺页中断的总开销为 30s。这意味着在程序运行的 60s 内，一半用于缺页中断开销， 一半用于运行程序。 若是我们运行程序的内存是内存的两倍， 我们会获取一半的内存页错误，只有 15 秒的页面错误开销，因此总的运行时间将是45秒。43.Frugal 计算机公司的一组操作系统设计人员正在考虑在他们的新操作系统中减少对后备储藏数量的需求。 老板建议根本不要把程序正文保存在交换区中， 而是在需要的时候直接从二进制文件中调页进来。 在什么条件下（若是有这样的条件话
28、）这种想法适用于程前言本？在什么条件下 （若是有这样的条件话） 这种想法适用于数据？A：这种想法适用于无法更正的程序和不能够被更正的数据。但是，平时程序不能够更正，数据却极少许无法更正。若是二进制文件中的数据区被更新的页面覆盖，下一次程序启动时，它将不会有原始数据。44.有一条机器语言指令将要被调入，该指令可把一个 32 位字装入含有 32 位字地址的寄存器。这个指令可能引起的最大缺页中断次数是多少？A：该指令可能超越页面界线，为了获取指令将以致两个缺页中断。获取的字也可能超越页界线， 产生两个以上的缺页中断， 总合四个。 若是字必定在内存中对齐，则数据字只能以致一个缺页中断，但是在某些机器（包括奔跑）上，在拥有4 KB 页面的机器上的 4094 地址上加载 32 位字的指令是合法的。46.像在 MULT1CS 中那样，当同时使用分段和分页时， 第一必定查找段描述符，尔后是页描述符。 TLB 也是这样按两级查找
