19.2. Sampled LRU Implementation

So, if I do not implement this counter method or the stack method in hardware I have to implement that in software, meaning that whenever there is a memory reference, I have to go to the OS and update data structures, which is also impractical because memory references are a very frequent phenomenon. So therefore, the exact version of ALU is not often used and instead approximate LRU is commonly used.

This chunk explains why the exact implementation of the Least Recently Used (LRU) algorithm is not practical in hardware. If one doesn’t implement LRU in hardware, it needs to be done via software, which could involve frequent communication with the operating system every time there’s a memory access. This constant updating can slow down system performance significantly. Hence, an approximate version of LRU is preferred, which saves computational resources and keeps things more efficient.

Imagine a busy restaurant where each table needs to be updated every time a customer leaves or orders something. If every single update required a manager to come and check, it would slow down service immensely. Instead, servers often just keep a mental note of which tables are occupied and which ones are free, which is much faster and keeps the restaurant running smoothly.

So, one of the most common implementations is to use an approximate version of ALU, which uses a reference bit in the page table for each page. On a reference to a page this bit is set to 1. Each page has a reference bit that when I am referring to this page and this page is in memory I am setting this bit from 0 to 1, if it is not already 1.

The reference bit is a key feature of the approximate LRU implementation. Each page in memory has a reference bit associated with it. When a page is accessed, its reference bit is set to 1, indicating that it has been used. This bit helps the system track which pages have been referenced and which haven't during the LRU page replacement process.

Imagine you are a teacher marking attendance in a classroom. Each time a student raises their hand to answer a question, you make a note next to their name on the attendance sheet. In this way, you keep track of who has been active in class recently. In this analogy, the attendance note represents the reference bit that tracks page usage.

Now, at fixed size intervals, after which I check for the after which I set the bits of all pages to 0. At the start of a time interval, I set the reference bits of all pages to 0, and then within that particular interval, every page that is referenced, their reference bits are set to 1.

The system periodically resets all reference bits to 0 at the beginning of defined time intervals. During these intervals, any page that is accessed has its reference bit updated to 1. This approach allows the system to maintain a time-based view of page usage, where older access patterns can naturally fall outside the reference window.

Think of it as a weekly summary report versus daily attendance in a gym. At the start of each week, the gym resets its system to start fresh for the new week. As members check in during the week, their attendance is noted. At week’s end, the gym looks back at that week to determine who frequently attended, resetting everything for the next week. This way, it stays updated without constantly tracking every minute.

When a particular page has to be replaced, I will try to use a page for which the reference bit is 0. A reference bit of 0 means that in the current time interval it has not been accessed; therefore, it has a higher probability that it will not be used in the near future.

When it comes time to replace a page that is no longer needed, the system looks for a page with a reference bit of 0, meaning that it hasn’t been accessed during the current interval. This indicates that the page has a lower likelihood of being needed soon, making it a suitable candidate for removal.

Imagine a library with shelves of books where each book is checked out or returned. If a book hasn’t been checked out in a while, it’s more likely to be ignored by visitors. Hence, if the library needed to make room for new books, it would be wise to clear out those seldom-read books first.

If all bits are the same for a given reference bit, I may choose the one which came into memory at the earliest, meaning I will use FIFO for given pages with the same reference bit.

In cases where multiple pages have a reference bit of 0 (indicating they haven't been used), the system uses a first-in-first-out (FIFO) method to decide which page to replace. The system prefers to evict the page that has been in memory the longest, ensuring fairness in resource allocation.

Consider a queue at a bakery: if multiple customers (pages) want similar bread (memory resources), but there’s only one loaf, the first customer in line would receive it. This ensures that patrons get served in the order they arrived, maintaining order even when choices are identical.

The next one is sampled LRU, which is an extension over the approximate LRU that we studied using just one reference bit. It has a slightly higher hardware cost; the first byte of each page is used by this strategy. In addition to the reference bit, I have a reference byte for each page.

Sampled LRU builds upon the approximate LRU by introducing a reference byte for each page. This allows for a more detailed history of page accesses over time, especially when the system samples the reference bits at regular intervals. This strategy strikes a balance between performance and resource utilization, though it incurs a slight increase in hardware costs.

Consider a gardener keeping track of which plants are watered and their past watering schedule. Instead of just marking a single watering event (like a reference bit), they can use a small notebook (reference byte) to record the last few weeks of watering. This gives a fuller picture when deciding which plants to focus on.

At the end of each time interval, the OS reads the reference bit for each page and stores it into the reference byte. Then all reference bits are cleared just like the previous scheme.

At the conclusion of each specified time interval, the operating system plays an active role in resetting the reference bits for all pages. It captures the state of each reference bit and updates the reference byte accordingly, ensuring that the entire process is synchronized with the operating system's management of memory resources.

This is akin to a school principal gathering attendance data at the end of each month. They compile the attendance records (reference bits) and summarize them in a report (reference byte). Then, they reset the attendance sheets for the following month, maintaining an organized overview of student participation over time.

On a page fault, I replace the page with the smallest reference byte. The numerical value of this byte tells me in the last 8 intervals what was the access pattern. A lower value of this byte implies a better candidate for replacement.

The system evaluates potential pages for replacement not just based on the reference bit, but also using the numerical value of the reference byte. Lower numerical values indicate that the page was accessed infrequently in the recent past, thereby making it a prime candidate for replacement if a page fault occurs.

Think of this as a restaurant evaluating its menu. The dishes that sell the least frequently (indicated by small sales numbers, akin to the reference byte) are likely to be removed. This ensures that only the most popular dishes remain on the menu, optimizing offerings for customers.

For all pages having the same numerical value of the reference byte, I will choose that page which came into memory at the earliest using the FIFO strategy.

If multiple pages present equal numerical values in their reference bytes during the page replacement process, the system resorts to the FIFO method to decide which page to evict. This maintains fairness, ensuring that pages that have been in memory the longest are replaced last.

In a queue for a popular amusement park ride, if multiple visitors have purchased the same type of ticket (indicating they entered the line at similar times), the park attendants will let those who arrived earliest onto the ride first. This keeps the line moving while respecting the order of arrivals.

--