Least Recently Used

Question

Define Least Recently Used(LRU)?

Answer 1

Least Recently Used (LRU): use the past to predict the future.

Replace the page which hasn't been referenced for the longest time

Strange but true: for some placement policies, like FIFO, adding up more memory can sometimes cause paging performance to be worse. It is called "Belady's Anomaly" .

Implementing LRU: need hardware support to keep track of which pages have been utilized recently .

•  Perfect LRU

+ Keep a register for each of the page, store system clock in that register onto each memory reference.

+ To select page for placement, scan through all pages to search the one with the oldest clock.

+ Hardware costs would have been unaffordable in the early days of paging; also, costly to scan all pages throughout replacement.