Confusion about a practical example of FIFO Page Replacement Algorithm?

user_9364436 0
Viewed 171

I'm doing some theoretical examples with different page replacement algorithms, in order to get a better understanding for when I actually write the code. I'm kind of confused about this example.

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.

I know that when a page needs to be swapped in, the operating system swaps out the page which has been in the memory for the longest period of time. In practice I'll have:

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

I'm not sure what happens at time = 8. I know that it won't replace page 5 and 4, but I'm not sure between 3 and 2. Since at time = 4 we have a 2, does it mean that page 3 will be replaced? Or is it that, since at time = 4, we already had 2 in the memory, therefore at time = 8 we replace 2?

fifo memory memory-management algorithm
1 Answers

FIFO (First In, First out) means here: If space is needed for a new entry, the oldest entry will be replaced. This is in contrast to LRU (Last recently Used), wherever the entry that has not been used for the longest time is replaced. Consider your memory with four tiles at time 5:

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

At time 6, space for page 5 is needed, so you had to replace one of the pages in the memory. According to the FIFO principle, page 1 is replaced here:

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

This event repeats itself at the time 8, the oldest page in memory will be replaced:

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

So it is helpful here to write the time of creation while doing this assignment.

user_138654760
Related