对FIFO页面替换算法的一个实际例子感到困惑

Question

我正在用不同的页面替换算法做一些理论示例，以便更好地了解我实际编写代码的时间。我对这个例子有点困惑。

下面给出的是一个具有4个瓦片(4个部分？(的物理内存。以下页面被一个接一个地访问：

R = 1, 2, 3, 2, 4, 5, 3, 6, 1, 4, 2, 3, 1, 4

在具有4个瓦片的R上运行FIFO页面替换算法。

我知道，当需要交换页面时，操作系统会交换掉内存中时间最长的页面。在实践中，我会有：

Time    1 2 3 4 5 6 7 8 9 10 11 12 13 14
Page    1 2 3 2 4 5 3 6 1 4  2  3  1  4
Tile 1  1 1 1 1 1 5 5
Tile 2    2 2 2 2 2 2
Tile 3      3 3 3 3 3
Tile 4          4 4 4

我不确定时间=8时会发生什么。我知道它不会取代第5页和第4页，但我不确定在第3页和第2页之间。由于在时间=4，我们有一个2，这是否意味着第3页将被替换？或者是因为在时间=4时，我们在内存中已经有了2，所以在时间=8时我们替换了2？

Answer 1

FIFO(先进先出(的意思是：如果新条目需要空间，则最旧的条目将被替换。这与LRU(最近一次使用(形成对比，在LRU中，最长时间未使用的条目被替换。考虑你的记忆在时间5:时有四个瓦片

Tile  Page   Time of loading
1     1      1
2     2      2
3     3      3
4     4      5

在时间6，需要第5页的空间，所以您必须替换内存中的一个页面。根据先进先出原则，此处替换第1页：

Tile  Page   Time of loading
1     5      6
2     2      2
3     3      3
4     4      5

此事件在时间8重复，内存中最旧的页面将被替换：

Tile  Page   Time of loading
1     5      6
2     6      8
3     3      3
4     4      5

因此，在做这项作业的同时写下创作时间是很有帮助的。