Page replacement Algorithm


(Abdullah Emad) #1

I ran into some confusion when designing the page replacement algorithm. Before I ask my question, here is my understanding of how memory references are handled:

  1. A user program references certain memory location in a page using a virtual address.
  2. The hardware MMU looks at the TLB, if the address is there the MMU returns the content of the memory successfully without consulting the Operating System. Otherwise the hardware traps into the OS which has to add the new TLB entry and bring the page from the disk if it is not already there.

implementing page replacement algorithms requires the OS to be able to estimate when was a page last referenced (as taught in the course and mentioned in OS books) usually using the reference bit, which is set by the TLB when an entry is referenced. My question is, I don’t seem to notice that the TLB entry has any similar bit in MIPS and OS161 and the only time the OS gets involved is when an entry is not present in the memory. How can I implement algorithms such as LRU when I dont have this information? Am I missing something?

Summary

Is there a reference bit or something similar that allows to estimate when was a page last referenced ? How can implement algorithms such as LRU without it ?