4 ms·

The Multi-Generational LRU

89 points by chmaynard 6y ago

devit 6y ago
Why are multiple lists needed instead of a single list where pages that are found to be accessed are put in the front and reclaim acts on the back?
- teraflop 6y ago
  That's explained in the second paragraph of the article: > Chances are that pages that have been accessed in the recent past will be useful again in the future, but there are exceptions. Consider, for example, an application that is reading sequentially through a file. Each page of the file will be put into the page cache as it is read, but the application will never need it again; in this case, recent access is not a sign that the page will be used again soon.
  - dllthomas 6y ago
    In a similar vein I once found a sharp decrease in cache misses when I started proactively evicting outbound messages from cache after sending, in a system passing messages between CPUs in circular buffers. (The reasoning generalizes but I would be skeptical that the results do without measuring.)
marcodiego 6y ago
Related: https://news.ycombinator.com/item?id=26451220 https://news.ycombinator.com/item?id=26451220
pengaru 6y ago
It always seemed odd to me that page reclaim was completely ignorant of CPU/IO priority of the accessing processes. If I run a backup job with a low priority, especially before cgroups existed where I could scope the task's memory use, there's nothing preventing it from displacing everything else from the page cache as it churns through an entire filesystem. Even if everything else in the page cache was put there by equal or higher priority processes. It seems like the priority should at least hint reclaim some amount rather than just age and activity levels... like the page struct should record the highest priority process accessing its contents, and not let lower priority processes evict that page for reclaim unless pressure is high enough.
- KMag 6y ago
  > like the page struct should record the highest priority process accessing its contents I'm not aware of any architecture where the MMU knows anything about task scheduling priority when marking pages as dirty or accessed, so there's a hardware limitation there. A close approximation might be to look at the task's (at the kernel level, threads and processes are tasks) scheduling priority when page-faulting in a page, to set some score on the page, and decrementing the score when the eviction algorithm finds the page is untouched. I guess it would then evict the first page found with a score of zero, or after examining N pages, evicting the lowest scored page found. (One could also use weighted reservoir sampling to achieve something closer to fairness, so high priority tasks don't always starve low priority tasks.) In the case of multiple generations of LRUs, presumably one could use the I/O priority of the faulting task to determine the initial generation of a newly faulted-in page. This would be a pretty minimal change (and might already be implemented but that detail left out of the LWN article) and wouldn't require any extra state in the page struct. Though, maybe you get close enough to the same effect simply by taking scheduling priority into effect when paging in pages. Some university OS courses must have some rough kernel simulators where these sorts of policy changes can be simulated, right? Or is it easier to actually just modify a Linux or *BSD kernel and run some benchmarks?
  - pengaru 6y ago
    I assumed it'd be maintained when the processes mapped pages into their address space, not at page fault time. Then if the process' priority increased, I guess it would have to walk the mapped pages to bump their priorities too for completeness. Not that I spent much time thinking about the implementation details or seriously exploring how to go about making it happen. Having to touch all mapped pages when a process changes its priority sounds painful, so it probably requires more sophistication to make things optimal.
    - KMag 6y ago
      Ahh, by "accessing its[the page's] contents", I thought you meant keeping track of the priorities of the tasks actually making the read and write operations that cause the MMU to set the dirty and accessed bits. It sounds like by "accesed" you weren't referring to the page access bit set by the MMU, but rather just having the page mapped in the address space.
curt15 6y ago
Would ZFS's Adaptive Replacement Cache be considered for inclusion after IBM's patent expires?
greggyb 6y ago
Bryan Cantrill does a pretty good survey of caching strategies in the intro to this Papers We Love talk on the ARC in ZFS. https://www.youtube.com/watch?v=F8sZRBdmqc0 https://www.youtube.com/watch?v=F8sZRBdmqc0

89 points by chmaynard 6y ago

Why are multiple lists needed instead of a single list where pages that are found to be accessed are put in the front and reclaim acts on the back?

teraflop 6y ago
That's explained in the second paragraph of the article: > Chances are that pages that have been accessed in the recent past will be useful again in the future, but there are exceptions. Consider, for example, an application that is reading sequentially through a file. Each page of the file will be put into the page cache as it is read, but the application will never need it again; in this case, recent access is not a sign that the page will be used again soon.
- dllthomas 6y ago
  In a similar vein I once found a sharp decrease in cache misses when I started proactively evicting outbound messages from cache after sending, in a system passing messages between CPUs in circular buffers. (The reasoning generalizes but I would be skeptical that the results do without measuring.)

marcodiego 6y ago

Related: https://news.ycombinator.com/item?id=26451220 https://news.ycombinator.com/item?id=26451220

pengaru 6y ago

It always seemed odd to me that page reclaim was completely ignorant of CPU/IO priority of the accessing processes. If I run a backup job with a low priority, especially before cgroups existed where I could scope the task's memory use, there's nothing preventing it from displacing everything else from the page cache as it churns through an entire filesystem. Even if everything else in the page cache was put there by equal or higher priority processes. It seems like the priority should at least hint reclaim some amount rather than just age and activity levels... like the page struct should record the highest priority process accessing its contents, and not let lower priority processes evict that page for reclaim unless pressure is high enough.

KMag 6y ago
> like the page struct should record the highest priority process accessing its contents I'm not aware of any architecture where the MMU knows anything about task scheduling priority when marking pages as dirty or accessed, so there's a hardware limitation there. A close approximation might be to look at the task's (at the kernel level, threads and processes are tasks) scheduling priority when page-faulting in a page, to set some score on the page, and decrementing the score when the eviction algorithm finds the page is untouched. I guess it would then evict the first page found with a score of zero, or after examining N pages, evicting the lowest scored page found. (One could also use weighted reservoir sampling to achieve something closer to fairness, so high priority tasks don't always starve low priority tasks.) In the case of multiple generations of LRUs, presumably one could use the I/O priority of the faulting task to determine the initial generation of a newly faulted-in page. This would be a pretty minimal change (and might already be implemented but that detail left out of the LWN article) and wouldn't require any extra state in the page struct. Though, maybe you get close enough to the same effect simply by taking scheduling priority into effect when paging in pages. Some university OS courses must have some rough kernel simulators where these sorts of policy changes can be simulated, right? Or is it easier to actually just modify a Linux or *BSD kernel and run some benchmarks?
- pengaru 6y ago
  I assumed it'd be maintained when the processes mapped pages into their address space, not at page fault time. Then if the process' priority increased, I guess it would have to walk the mapped pages to bump their priorities too for completeness. Not that I spent much time thinking about the implementation details or seriously exploring how to go about making it happen. Having to touch all mapped pages when a process changes its priority sounds painful, so it probably requires more sophistication to make things optimal.
  - KMag 6y ago
    Ahh, by "accessing its[the page's] contents", I thought you meant keeping track of the priorities of the tasks actually making the read and write operations that cause the MMU to set the dirty and accessed bits. It sounds like by "accesed" you weren't referring to the page access bit set by the MMU, but rather just having the page mapped in the address space.

curt15 6y ago

Would ZFS's Adaptive Replacement Cache be considered for inclusion after IBM's patent expires?

greggyb 6y ago

Bryan Cantrill does a pretty good survey of caching strategies in the intro to this Papers We Love talk on the ARC in ZFS. https://www.youtube.com/watch?v=F8sZRBdmqc0 https://www.youtube.com/watch?v=F8sZRBdmqc0