Virtual memory cont. #

Page replacement algorithms cont. #

Recall:

• FIFO looks at the time the page was initially brought in
• LRU looks at the last time the page was accessed

Implementing LRU (least recently used)

• counter implementation has an exhaustive search, so \( \Theta(n) \) runtime
• stack implementation has the least recently used at the bottom of the stack, each update is expensive because items are moved to the top of the stack when replaced

• circles indicate page fault
• top shows 3 frame memory, bottom shows 4 frame memory, for comparison

• second chance is like a warning before an eviction