6 ms·

> 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 t

by 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.
toast0 6y ago
I'm x86 centric, but the MMU doesn't make decisions about which pages to evict; it just handles mapping virtual addresses to physical addresses based on the page table, and marking pages in the page table as dirty/accessed. The OS would need to manage priority information to evict lower priority pages. That may be part of what's done with posix_fadvise information, but I haven't dug deeply into that. With this mutli-generational LRU, you could probably add a memory priority to a process, and use that to decide which generation to put pages in when a process needs them. If a low (memory) priority process's pages always go in the oldest generation, they would get considered for reclaim much more often than a high priority process whose pages get put in the youngest generation.
- KMag 6y ago
  I know the MMU doesn't make eviction decisions, but it does mark the "dirty" and "accessed" bits for pages. The GP was suggesting keeping track of the scheduling priorities of tasks that were "accessing its[the page's] contents", not just keeping track of the highest priority task mapping a given page. This would require the MMU, as it's setting the dirty and accessed bits, to also keep track of the maximum priority that has set either the dirty or accessed bit. Edit: from the GP's reply, it sounds like by "accessing" they really just meant mapping, not accessing is the sense of the accessed and dirty bits.
  - johncolanduoni 6y ago
    The dirty and accessed bits are per page table structure, so they are per-process. So you can at least take process priority into account, if not thread. In theory you could take thread priority into account by observing and resetting the dirty/accessed bits every context switch, but this would be unlikely to be worth it.
    - toast0 6y ago
      > In theory you could take thread priority into account by observing and resetting the dirty/accessed bits every context switch, but this would be unlikely to be worth it. That would be most likely terrible (as you suggest). You might have better luck giving each thread a copy of the process page table, and keeping that in sync somehow (which also sounds terrible, but might be more workable)

by KMag 6y ago

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.

toast0 6y ago

I'm x86 centric, but the MMU doesn't make decisions about which pages to evict; it just handles mapping virtual addresses to physical addresses based on the page table, and marking pages in the page table as dirty/accessed. The OS would need to manage priority information to evict lower priority pages. That may be part of what's done with posix_fadvise information, but I haven't dug deeply into that. With this mutli-generational LRU, you could probably add a memory priority to a process, and use that to decide which generation to put pages in when a process needs them. If a low (memory) priority process's pages always go in the oldest generation, they would get considered for reclaim much more often than a high priority process whose pages get put in the youngest generation.

KMag 6y ago
I know the MMU doesn't make eviction decisions, but it does mark the "dirty" and "accessed" bits for pages. The GP was suggesting keeping track of the scheduling priorities of tasks that were "accessing its[the page's] contents", not just keeping track of the highest priority task mapping a given page. This would require the MMU, as it's setting the dirty and accessed bits, to also keep track of the maximum priority that has set either the dirty or accessed bit. Edit: from the GP's reply, it sounds like by "accessing" they really just meant mapping, not accessing is the sense of the accessed and dirty bits.
- johncolanduoni 6y ago
  The dirty and accessed bits are per page table structure, so they are per-process. So you can at least take process priority into account, if not thread. In theory you could take thread priority into account by observing and resetting the dirty/accessed bits every context switch, but this would be unlikely to be worth it.
  - toast0 6y ago
    > In theory you could take thread priority into account by observing and resetting the dirty/accessed bits every context switch, but this would be unlikely to be worth it. That would be most likely terrible (as you suggest). You might have better luck giving each thread a copy of the process page table, and keeping that in sync somehow (which also sounds terrible, but might be more workable)