操作系统 作业九

操作系统

陆一洲 5140309557 of F1403020

9.4

某个计算机给它的用户提供了 $2^{32}$ 的虚拟内存空间，计算机有 $2^{14}$ B 的物理内存，虚拟内存使用页面大小为 4094B 的分页机制实现。一个用户进程产生虚拟地址 11123456，现在说明一下系统怎么样建立相应的物理地址，区分一下软件操作和硬件操作。

该虚拟地址的二进制形式是 0001 0001 0001 0010 0011 0100 0101 0110。
由于页面大小为 212，页表大小为 220，因此：

• 低 12 位的“0100 0101 0110 ”被用来替换页
• 前 20 位“0001 0001 0001 0010 0011”被用来替换页表。

9.8

讨论在哪一种情况下，MFU（最不经常使用）页置换比 LRU（最近最少使用）页置换法产生较少的页面错误，什么情况下则相反？

考虑可容纳 4 页的内存：1 2 3 4 4 4 5 1

• MFU 算法会用 5 替换 4
• LRU 算法刚用 5 替换 1

LRU 算法做得更正确。

9.13

一个页面置换算法应使发生页错误的次数最小化。怎样才能通过将使用频率高的页平均分配到整个内存而不只是竞争少数几个页帧页来达到这种最小化。可以对每个页帧设置一个计数器来记录与此帧相关的页数。那么当置换一个页时，就可以查找计数器值最小的页帧。

• 定义一个页面置换算法：
  
  • 计数器初始值：0；
  • 计数器值增加：每当新的一页与此帧相关联；
  • 计数器值减少：每当与此帧相关联的一个页不再需要；
  • 怎样选择被置换页：找到带有最小计数器值的帧。使用先进先出算法解除其关系
• 设有 4 个帧，对于下面的页引用序列，你的算法会发生多少次页错误？ ：14 个页错误
  
  • 1 2 3 4 5 4 5 1 6 7 8 7 8 9 7 8 9 5 4 5 4 2
• 最优页置换算法对于 4 帧的 b 中的页引用序列最小页错误数为多少？ ：11 个页错误

9.14

假设一个请求调页系统具有一个平均访问和传输时间为 20ms 的分页磁盘。为 地址转换是通过在主存中的页表来进行的，每次内存访问时间为 1µs。这样，每个通过页表进行的内存引用都要访问内存两次。为了提高性能，加入一个相关内存，当页表项在相关内存中时，可以减少内存引用的访问次数。
假设 80% 的访问发生在相关内存中，而且剩下中的 10% （总量的 2% ）会导致页错误。内存的有效访问时间是多少？

$$\begin{align*} T&= 0.8\times(1\ \mathrm{\mu s})+ 0.1\times (2\ \mathrm{\mu s})+0.1\times(5002\ \mathrm{\mu s})\\ &= 501.2\ \mathrm{\mu s}\\ &\approx 0.5\ \mathrm{ms} \end{align*}$$