六、(15%)某请求分页式系统中，某进程的页表如下： Page number(页号) Frame(物理帧号) Valid/Invalid bit(有效位) 0 0 1 9H 1 2 254H 1 3 0 假定页面大小为4K,为该进程分配的物理帧数固定为2,采用最近最少使用页面置换算法(LRU)和本地帧分配策略，假设按虚拟地址10A0H,3542H,2408H,256H的序列顺序访问： 1.请给出访问10A0H时的完整地址转换过程(步骤)和对应的物理地址； 2.请给出访问3542H时的完整地址转换过程(步骤)和对应的物理地址； 3.如果采用最优页面置换算法和本地帧分配策略，请给出上述序列(10A0H,3542H,2408H,256H)对应的物理地址，并给出分析过程。

1. 访问10A0H的完整地址转换过程：

首先，将10A0H转换成二进制：0001 0000 1010 0000。

页号为0001，对应的页表项为：

Page number(页号) Frame(物理帧号) Valid/Invalid bit(有效位)

0 0 1

有效位为1，表示该页已在内存中，物理帧号为0。

将页号和页内偏移量合并成物理地址：

0000 0000 1010 0000 -> 0000 0000 0000 0000 0000 0000 1010 0000

物理地址为：00A0H。

2. 访问3542H的完整地址转换过程：

首先，将3542H转换成二进制：0011 0101 0100 0010。

页号为0011，对应的页表项为：

Page number(页号) Frame(物理帧号) Valid/Invalid bit(有效位)

1 2 1

有效位为1，表示该页已在内存中，物理帧号为2。

将页号和页内偏移量合并成物理地址：

0000 0010 0100 0010 -> 0000 0000 0000 0010 0100 0010

物理地址为：0242H。

3. 如果采用最优页面置换算法和本地帧分配策略，请给出上述序列(10A0H,3542H,2408H,256H)对应的物理地址，并给出分析过程。

a. 访问10A0H：

首先，将10A0H转换成二进制：0001 0000 1010 0000。

页号为0001，对应的页表项为：

Page number(页号) Frame(物理帧号) Valid/Invalid bit(有效位)

0 0 1

有效位为1，表示该页已在内存中，物理帧号为0。

将页号和页内偏移量合并成物理地址：

0000 0000 1010 0000 -> 0000 0000 0000 0000 0000 0000 1010 0000

物理地址为：00A0H。

b. 访问3542H：

首先，将3542H转换成二进制：0011 0101 0100 0010。

页号为0011，对应的页表项为：

Page number(页号) Frame(物理帧号) Valid/Invalid bit(有效位)

1 2 1

有效位为1，表示该页已在内存中，物理帧号为2。

将页号和页内偏移量合并成物理地址：

0000 0010 0100 0010 -> 0000 0000 0000 0010 0100 0010

物理地址为：0242H。

c. 访问2408H：

首先，将2408H转换成二进制：0010 0100 0000 1000。

页号为0010，对应的页表项为：

Page number(页号) Frame(物理帧号) Valid/Invalid bit(有效位)

254 3 1

有效位为1，表示该页已在内存中，物理帧号为3。

将页号和页内偏移量合并成物理地址：

0000 0011 0000 1000 -> 0000 0000 0000 0011 0000 1000

物理地址为：0308H。

d. 访问256H：

首先，将256H转换成二进制：0000 0001 0000 0000。

页号为0000，对应的页表项为：

Page number(页号) Frame(物理帧号) Valid/Invalid bit(有效位)

1 2 1

页表中不存在页号为0000的页表项，需要进行页面置换。

最优页面置换算法选择在未来最久的时间内不再被访问的页面进行置换。

在未来的访问序列中，最久时间未被访问的页面是2408H，所以选择将其置换出去。

将2408H页表项的有效位设为0，表示该页不在内存中。

新分配一个物理帧号给页号为0000的页面，由于本地帧分配策略固定为2帧，因此只能使用未分配的物理帧号1，即将页号为0000的页面放入物理帧号为1的帧中。

将新分配的物理帧号1写入页号为0000的页表项中，并将有效位设为1。

将页号为0000和页内偏移量合并成物理地址：

0000 0001 0000 0000 -> 0000 0000 0000 0001 0000 0000

物理地址为：0100H。