了解物理地址和逻辑地址之间的关系以及 LRU 的使用
Understanding relationship between Physical and Logical addresses and use of LRU
通过分页实现内存的计算机CPU生成如下逻辑地址（十进制）：
777, 2047, 1199, 1100, 546, 129, 3201
页面大小为512 Byte
CPU生成长度为12 Bit
主存可按字节寻址，总共可以接收4页
512 Byte page size 表示2^9 Bytes，所以逻辑地址的偏移量将由9 Bits组成。我们总共得到了 12 Bits 的长度，所以 12 - 9 = 3，所以第一个 3 Bits 将用于页面！
这就是我完全理解的逻辑地址。但是物理地址呢？ 物理地址的偏移量与逻辑地址的偏移量相同。但是页面不同，我不明白这是为什么？我也没有看到模式，开始第一页是 00，然后是 01.. 等等为什么？
任务提供的唯一附加信息：如果所有页框都在使用，将应用 LRU...
您获得了以下信息：
- 页面大小为 512 字节
- CPU生成长度为12位的逻辑地址
- 主存是按字节寻址的，总共可以接收4页
从中可以得出很多东西：
- 页为512字节，主存共有4页。 4 * 512 = 2048。这意味着物理主内存有 2048 字节（2^11 字节 = 4 * 2^9）。
- 物理地址的高 2 位（值 0 到 3）也代表物理页码
- 逻辑地址为 12 位，即 8512 字节页面或 4096 字节（2^12 字节）。
- 逻辑地址的前 3 位 (0-7) 表示逻辑页码。
我的假设：
- 如果有空闲物理页（未映射到任何逻辑页），则假定首先使用编号最小的物理页。
所以你有4096字节的逻辑内存但是只有2048字节的物理内存。所以你不能同时在内存中拥有每个逻辑页。您一次可以有 4 页。这就是Least Recently Used（LRU）算法的用武之地。当发现逻辑地址不在内存中并且所有物理页面已满时，然后找到最近最少使用的物理页面并将其从内存中驱逐；将新的逻辑页面与该物理页面相关联。通常 OS 会将页面从内存中逐出并在需要时将其加载回磁盘（后备存储）。
所以我们得到了逻辑地址：
777, 2047, 1199, 1100, 546, 129, 3201
如果我们将这些逻辑地址转换为 12 位二进制，我们有：
777 = 001 100001001
2047 = 011 111111111
1199 = 010 010101111
1100 = 010 001001100
546 = 001 000100010
129 = 000 010000001
3201 = 110 010000001
假设一开始所有 4 个物理页面 0(00)、1(01)、2(10) 和页面 3(11) 都是空的。 为方便起见，其余答案使用二进制页码：
Page 00 = empty, page 01 = empty, page 10 = empty, page 11 = empty
假设处理器按顺序收到对上述每个逻辑地址的请求 - 它必须将它们转换为物理地址，如果物理页面都已满，则使用 LRU 查找要删除的页面，并且将它与新的逻辑页面相关联。
777 = 001 100001001
看看我们的逻辑页001是否映射到物理页。如果没有，找一个空的物理页（使用第一个）。物理页 00 是空闲的。将逻辑页号 001 与物理页 00 相关联。因此，完成此转换后我们有：
Page 00 = 001, page 01 = empty, page 10 = empty, page 11 = empty
逻辑地址：001 100001001等于物理地址00 100001001
2047 = 011 111111111
查看物理页以查看逻辑页 011 是否在内存中。它不是。我们找到下一个可用的物理页 01。我们将物理页 01 与逻辑页 011 相关联。
Page 00 = 001, page 01 = 011, page 10 = empty, page 11 = empty
逻辑地址：011 111111111等于物理地址01 111111111
1199 = 010 010101111
查看物理页以查看逻辑页 010 是否在内存中。它不是。我们找到下一个可用的物理页 10。我们将物理页 10 与逻辑页 010 相关联。
Page 00 = 001, page 01 = 011, page 10 = 010, page 11 = empty
逻辑地址：010 010101111等于物理地址10 010101111
1100 = 010 001001100
查看物理页以查看逻辑页 010 是否在内存中。这是。第 10 页已经有逻辑页 010！没事做。重新排序列表，以便最近使用物理页面 10。它已经上次使用了，所以不需要做任何事情。:
Page 00 = 001, page 01 = 011, page 10 = 010, page 11 = empty
逻辑地址：010 001001100 等于物理地址10 001001100
546 = 001 000100010
查看物理页面以查看逻辑页面 001 是否在内存中。这是。页 00 已经有逻辑页 001！没事做。重新排序列表，以便最近使用物理页 00，因此将其移至我们列表的末尾：
Page 00 = 001, page 01 = 011, page 10 = 010, page 11 = empty
变为：
page 01 = 011, page 10 = 010, Page 00 = 001, page 11 = empty
逻辑地址：001 000100010等于物理地址00 000100010
129 = 000 010000001
查看物理页以查看逻辑页 000 是否在内存中。它不是。我们找到下一个可用的物理页 11。我们将物理页 11 与逻辑页 000 相关联。
page 01 = 011, page 10 = 010, Page 00 = 001, page 11 = 000
逻辑地址：000 010000001等于物理地址11 010000001
注意：此时我们所有的物理页面都已满。
3201 = 110 010000001
查看物理页面以查看逻辑页面 110 是否在内存中。它不是。我们寻找下一个可用的物理页面——但不存在这样的空闲页面。使用 LRU，我们查看最近最少使用的条目（它将始终位于此列表的左侧）：
page 01 = 011, page 10 = 010, Page 00 = 001, page 11 = 000
第 01 页在左侧，因此是最近最少使用的页面。我们从物理页 01 中逐出逻辑页 011 并用 110 替换它：
page 01 = 110, page 10 = 010, Page 00 = 001, page 11 = 000
现在，由于物理页 01 最近被使用，因此将其移至列表末尾：
page 10 = 010, Page 00 = 001, page 11 = 000, page 01 = 110
逻辑地址：110 010000001等于物理地址01 010000001
观察
以上与您提供的 table 中的 answer/solution 相比如何？如果你接受上面所有以 Logical address: 开头的行，你会得到。
Logical address: 001 100001001 equals physical address 00 100001001
Logical address: 011 111111111 equals physical address 01 111111111
Logical address: 010 010101111 equals physical address 10 010101111
Logical address: 010 001001100 equals physical address 10 001001100
Logical address: 001 000100010 equals physical address 00 000100010
Logical address: 000 010000001 equals physical address 11 010000001
Logical address: 110 010000001 equals physical address 01 010000001
将它与给你的 table 进行比较，如果我没有出错，它们应该是等价的。从上面的方法我们还知道的一件事是，在翻译最后一个逻辑地址后，我们在物理（主）内存中有这些页面：
page 10 = 010, Page 00 = 001, page 11 = 000, page 01 = 110
你的问题可能既是关于学生理解 LRU 的，也是关于理解物理和逻辑内存的。
通过分页实现内存的计算机CPU生成如下逻辑地址（十进制）：
777, 2047, 1199, 1100, 546, 129, 3201
页面大小为
512 ByteCPU生成长度为
12 Bit的逻辑地址
主存可按字节寻址，总共可以接收
4页
512 Byte page size 表示2^9 Bytes，所以逻辑地址的偏移量将由9 Bits组成。我们总共得到了 12 Bits 的长度，所以 12 - 9 = 3，所以第一个 3 Bits 将用于页面！
这就是我完全理解的逻辑地址。但是物理地址呢？ 物理地址的偏移量与逻辑地址的偏移量相同。但是页面不同，我不明白这是为什么？我也没有看到模式，开始第一页是 00，然后是 01.. 等等为什么？
任务提供的唯一附加信息：如果所有页框都在使用，将应用 LRU...
您获得了以下信息：
- 页面大小为 512 字节
- CPU生成长度为12位的逻辑地址
- 主存是按字节寻址的，总共可以接收4页
从中可以得出很多东西：
- 页为512字节，主存共有4页。 4 * 512 = 2048。这意味着物理主内存有 2048 字节（2^11 字节 = 4 * 2^9）。
- 物理地址的高 2 位（值 0 到 3）也代表物理页码
- 逻辑地址为 12 位，即 8512 字节页面或 4096 字节（2^12 字节）。
- 逻辑地址的前 3 位 (0-7) 表示逻辑页码。
我的假设：
- 如果有空闲物理页（未映射到任何逻辑页），则假定首先使用编号最小的物理页。
所以你有4096字节的逻辑内存但是只有2048字节的物理内存。所以你不能同时在内存中拥有每个逻辑页。您一次可以有 4 页。这就是Least Recently Used（LRU）算法的用武之地。当发现逻辑地址不在内存中并且所有物理页面已满时，然后找到最近最少使用的物理页面并将其从内存中驱逐；将新的逻辑页面与该物理页面相关联。通常 OS 会将页面从内存中逐出并在需要时将其加载回磁盘（后备存储）。
所以我们得到了逻辑地址：
777, 2047, 1199, 1100, 546, 129, 3201
如果我们将这些逻辑地址转换为 12 位二进制，我们有：
777 = 001 100001001 2047 = 011 111111111 1199 = 010 010101111 1100 = 010 001001100 546 = 001 000100010 129 = 000 010000001 3201 = 110 010000001
假设一开始所有 4 个物理页面 0(00)、1(01)、2(10) 和页面 3(11) 都是空的。 为方便起见，其余答案使用二进制页码：
Page 00 = empty, page 01 = empty, page 10 = empty, page 11 = empty
假设处理器按顺序收到对上述每个逻辑地址的请求 - 它必须将它们转换为物理地址，如果物理页面都已满，则使用 LRU 查找要删除的页面，并且将它与新的逻辑页面相关联。
777 = 001 100001001
看看我们的逻辑页001是否映射到物理页。如果没有，找一个空的物理页（使用第一个）。物理页 00 是空闲的。将逻辑页号 001 与物理页 00 相关联。因此，完成此转换后我们有：
Page 00 = 001, page 01 = empty, page 10 = empty, page 11 = empty
逻辑地址：001 100001001等于物理地址00 100001001
2047 = 011 111111111
查看物理页以查看逻辑页 011 是否在内存中。它不是。我们找到下一个可用的物理页 01。我们将物理页 01 与逻辑页 011 相关联。
Page 00 = 001, page 01 = 011, page 10 = empty, page 11 = empty
逻辑地址：011 111111111等于物理地址01 111111111
1199 = 010 010101111
查看物理页以查看逻辑页 010 是否在内存中。它不是。我们找到下一个可用的物理页 10。我们将物理页 10 与逻辑页 010 相关联。
Page 00 = 001, page 01 = 011, page 10 = 010, page 11 = empty
逻辑地址：010 010101111等于物理地址10 010101111
1100 = 010 001001100
查看物理页以查看逻辑页 010 是否在内存中。这是。第 10 页已经有逻辑页 010！没事做。重新排序列表，以便最近使用物理页面 10。它已经上次使用了，所以不需要做任何事情。:
Page 00 = 001, page 01 = 011, page 10 = 010, page 11 = empty
逻辑地址：010 001001100 等于物理地址10 001001100
546 = 001 000100010
查看物理页面以查看逻辑页面 001 是否在内存中。这是。页 00 已经有逻辑页 001！没事做。重新排序列表，以便最近使用物理页 00，因此将其移至我们列表的末尾：
Page 00 = 001, page 01 = 011, page 10 = 010, page 11 = empty
变为：
page 01 = 011, page 10 = 010, Page 00 = 001, page 11 = empty
逻辑地址：001 000100010等于物理地址00 000100010
129 = 000 010000001
查看物理页以查看逻辑页 000 是否在内存中。它不是。我们找到下一个可用的物理页 11。我们将物理页 11 与逻辑页 000 相关联。
page 01 = 011, page 10 = 010, Page 00 = 001, page 11 = 000
逻辑地址：000 010000001等于物理地址11 010000001
注意：此时我们所有的物理页面都已满。
3201 = 110 010000001
查看物理页面以查看逻辑页面 110 是否在内存中。它不是。我们寻找下一个可用的物理页面——但不存在这样的空闲页面。使用 LRU，我们查看最近最少使用的条目（它将始终位于此列表的左侧）：
page 01 = 011, page 10 = 010, Page 00 = 001, page 11 = 000
第 01 页在左侧，因此是最近最少使用的页面。我们从物理页 01 中逐出逻辑页 011 并用 110 替换它：
page 01 = 110, page 10 = 010, Page 00 = 001, page 11 = 000
现在，由于物理页 01 最近被使用，因此将其移至列表末尾：
page 10 = 010, Page 00 = 001, page 11 = 000, page 01 = 110
逻辑地址：110 010000001等于物理地址01 010000001
观察
以上与您提供的 table 中的 answer/solution 相比如何？如果你接受上面所有以 Logical address: 开头的行，你会得到。
Logical address: 001 100001001 equals physical address 00 100001001 Logical address: 011 111111111 equals physical address 01 111111111 Logical address: 010 010101111 equals physical address 10 010101111 Logical address: 010 001001100 equals physical address 10 001001100 Logical address: 001 000100010 equals physical address 00 000100010 Logical address: 000 010000001 equals physical address 11 010000001 Logical address: 110 010000001 equals physical address 01 010000001
将它与给你的 table 进行比较，如果我没有出错，它们应该是等价的。从上面的方法我们还知道的一件事是，在翻译最后一个逻辑地址后，我们在物理（主）内存中有这些页面：
page 10 = 010, Page 00 = 001, page 11 = 000, page 01 = 110
你的问题可能既是关于学生理解 LRU 的，也是关于理解物理和逻辑内存的。