The OS guarantees that some bit of the VPN will remain unchanged through address translation, i.e. the low bits of the VPN and PFN are identical
The low bits are like a color. The color of the virtual address must match the color of the physical address.
This means that a virtual page can only occupy a subset of page frames in which the low bits of the VPN match the low bits of the PFN.
Page Replacement Algorithms has to keep track of this.
It could be harded to fit a working set into physical memmory, but it’s often fine because processes tend to use continguous pages, so the VPNs of the pages are spread evenly amoung the colors.
(VPN and PFN happen to be the same size here)
Example
size(Colored Bits)
- 64-bit virtual address
- 32-bit physical address
- Virtually-indexed, physically-tagged, 4-way set associative cache
- Page size of 4 KB
- Memory is byte-addressable
- Total cache size of 512 KB
- Cache block size of 64 bytes
How many of the least significant bits of the VPN must remain unchanged in the VPN-PFN translation?
If you look at the above figures,