algorithm - 对 FIFO 页替换算法的实际示例感到困惑？

Question

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

Given below is a physical memory with 4 tiles (4 sections?). The following pages are visited one after the other:

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

Run the FIFO page replacement algorithm on R with 4 tiles.

我知道当一个页面需要换入时，操作系统会换出在内存中存在时间最长的页面。在实践中，我将有:

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(上次最近使用)形成对比，其中最长时间未使用的条目被替换。考虑你在时间 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

所以在做这个作业的时候写下创作时间是很有帮助的。