The sequence of page accesses is shown as the top row in each example. The next line shows which accesses are hits. The column below each page access shows the pages that are in physical memory after the access. The pages in a column are in order of vulnerability, with the most vulnerable page at the bottom of the column. That is, the bottom page in a column is the one that is replaced if replacement is needed.
| 3 | 1 | 2 | 0 | 2 | 1 | 3 | 0 | 4 | 2 | 0 | 1 | 3 | 2 | 3 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| H | H | H | H | H | H | ||||||||||
| 3 | 1 | 2 | 2 | 1 | 0 | 0 | 2 | 2 | 0 | 2 | 2 | 2 | 3 | 0 | 0 |
| 3 | 1 | 1 | 0 | 2 | 2 | 0 | 0 | 2 | 0 | 0 | 3 | 0 | 3 | 3 | |
| 3 | 0 | 2 | 1 | 3 | 3 | 4 | 4 | 4 | 1 | 0 | 2 | 2 | 2 |
| 3 | 1 | 2 | 0 | 2 | 1 | 3 | 0 | 4 | 2 | 0 | 1 | 3 | 2 | 3 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| H | H | H | H | ||||||||||||
| 3 | 1 | 2 | 0 | 2 | 1 | 3 | 0 | 4 | 2 | 0 | 1 | 3 | 2 | 3 | 0 |
| 3 | 1 | 2 | 0 | 2 | 1 | 3 | 0 | 4 | 2 | 0 | 1 | 3 | 2 | 3 | |
| 3 | 1 | 1 | 0 | 2 | 1 | 3 | 0 | 4 | 2 | 0 | 1 | 1 | 2 |
| 3 | 1 | 2 | 0 | 2 | 1 | 3 | 0 | 4 | 2 | 0 | 1 | 3 | 2 | 3 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| H | H | H | H | ||||||||||||
| 3 | 1 | 2 | 0 | 0 | 0 | 3 | 3 | 4 | 2 | 0 | 1 | 3 | 2 | 2 | 0 |
| 3 | 1 | 2 | 2 | 2 | 0 | 0 | 3 | 4 | 2 | 0 | 1 | 3 | 3 | 2 | |
| 3 | 1 | 1 | 1 | 2 | 2 | 0 | 3 | 4 | 2 | 0 | 1 | 1 | 3 |
Note the difference between LRU and FIFO that begins to appear in the fifth column. With LRU, when you have a hit the new page goes to the top of a column because it is the most recently used page. With FIFO the accessesed page remains in the same position in the column since the current access has no effect on how long it has been in physical memory. However, if there are no hits then the order within columns is identical for LRU and FIFO. With LRU or FIFO, after a miss the accessed page always goes to the top of the column and the page at the bottom of the column is lost.
With OPT, rearranging the column after a page access is a bit more tedious. Again, on a miss the bottom page in the column is lost. For either a hit or a miss the pages in a column retain their order except for the the accessed page and possibly the replaced page. The accessed page is placed according to where its next access is in relation to the next access of the other pages in the column.