虚拟内存中LRU算法下操作系统追踪内存帧使用的方法问询
Great question—this is a classic deep dive into OS memory management that’s way more interesting once you peek under the hood! Let’s break down the two main approaches systems use to track which pages are being used, even when they’re in a valid state:
1. Hardware-Assisted Access Tracking (Most Common)
Nearly all modern CPUs include a tiny flag in each page table entry (PTE) called the Accessed Bit (or Use Bit), managed directly by the MMU. Here’s how it works:
- Whenever a process reads from or writes to a valid page, the MMU automatically flips this bit to
1—no OS intervention required. - The OS periodically scans the page tables to check these bits. Pages with the bit set get marked as "recently used," and the OS resets the bit to
0to start fresh tracking for the next interval. - This is an approximation of LRU (since it only tracks "used vs. not used" in a window, not exact access order), but it’s efficient enough for most systems. Variations like the Second Chance Algorithm build directly on this bit to prioritize pages that were recently accessed.
2. Software-Only Simulation (For Systems Without Hardware Support)
If the MMU doesn’t have an Accessed Bit, the OS can simulate LRU tracking using a clever trick with temporary invalidation:
- The OS iterates through valid pages and temporarily sets their Valid Bit to
0—but it doesn’t actually evict the page from memory. - When a process tries to access this now-"invalid" page, it triggers a minor page fault. The OS catches this fault, notes the page was just accessed, sets the Valid Bit back to
1, and marks the page as "used." - After scanning all pages, any page that didn’t trigger a fault is one that hasn’t been accessed since the last scan—this becomes the top candidate for eviction in LRU.
- This method has some overhead from the minor faults, but it’s a reliable way to track usage without hardware help.
Hybrid Approaches
Some systems combine both methods: using the hardware Accessed Bit to cut down on how often the OS needs to run full invalidation scans, or leveraging more advanced (though rare) hardware counters to track access frequency more granularly.
内容的提问来源于stack exchange，提问作者Camion
