操作系统 分页存储+最久最近页面置换算法

Question

某计算机主存按字节编址，使用一级页表的请求分页存储管理方式，逻辑地址和物理地址都是32位。若逻辑地址中后12位用于记录页内偏移量，页表项大小为4字节。 页的大小是（ ）字节，页表最大占用（ ）字节？ 页表内容如下表（标记为0表示页未调入），设采用局部置换策略、最近最久未使用页面置换算法，页面历史使用序列为3 2 1 0 1，现要访问逻辑地址0000 2160H的数据，则其物理地址是（ ）。 页号 物理块号 存在标记 0 5 1 1 10 1 2 0 3 0

第三个空，页内偏移量应该是160H，然后对应的页面应该是2，然后2的标记是0 后面就不知道了，搜了一下答案发现是00005160H

Answer 1

引自免费微信小程序：皆我百晓生

根据题目描述，逻辑地址由页号和页内偏移量组成，其中页内偏移量占用了后12位，也就是4个二进制位可以表示的最大数是(2^4 - 1 = 15)，因此每一页的大小是 (2^{12}) 字节，这是因为2的12次方正好是1024，即1KB。

接下来，我们来计算总共有多少个不同的页。由于逻辑地址是32位，除去后12位的页内偏移量，剩下的20位用来标识不同的页。所以，总共可以有 (2^{20}) 个不同的页面。

每个页表项是4字节，因此页表最多占用的字节数就是页的数量乘以每个页表项的大小，即 (2^{20} \times 4) 字节。

对于第三个空，我们要找到逻辑地址00002160H对应的物理地址。这个地址由页号和页内偏移量两部分构成。逻辑地址的前20位作为页号，即00002160H转换成十进制是8768，这是页号。页内偏移量是后12位，即160H，转换成十进制是640。

现在我们查看页表，找到页号为8768（即2的十进制表示）的行，可以看到对应的是物理块号5，存在标记为0，这意味着该页未被调入内存。

按照最近最久未使用页面置换算法(LRU)，我们需要从已有的页面中选择一个最近最少使用的页面进行替换。根据页面历史使用序列3、2、1、0、1，我们可以看出最近访问过的页面是1，因此应该将页号为1的页面替换掉。页号为1的物理块号是10，存在标记也是1，所以我们需要将其替换，并将当前访问的页号为8768的页面放入物理块号10的位置。

新的页表状态如下：

页号 | 物理块号 | 存在标记
-----|----------|---------
  0  |    5     |   1    
  1  |    10    |   0    （这里被替换）
  2  |    1     |   1    
  3  |    0     |   0    

现在，我们将页号8768的页面放入物理块号10，同时更新存在标记为1。

因此，逻辑地址00002160H对应的物理地址将是物理块号10加上页内偏移量640，即物理地址是00005160H。