OSDev.org

I've been thinking about how to arrange a virtual memory manager to keep track of what's what inside address spaces. The general consensus appears to be that the most efficient structures to use are binary trees, and I've come up with a node type for one of those: As you can see, I've tried to optimize for size by turning two Boolean values into flags and shrinking the numerical values stored for pages in order to make the signed integer type usable.

However, I've been reading "Modern Operating Systems" and don't see any page replacement algorithm that operates on such trees. There are some things I can do (such as implement an algorithm modified for the tree), but I'm wondering what algorithms are available for the lazy man who doesn't want to implement a new one.

In the meantime, I'll be thinking of a new one. My ideas are this: Essentially, operating on a tree is most efficient if we know what node to operate on. So possibly (given that the OS will do like everyone does and put kernel, process image, libraries in specific regions of address space), an algorithm could seek out and operate specifically on the process image (useful for working set), or libraries or some other part of virtual memory. The real issue with the tree is that page replacement algorithms tend to operate best on entire address spaces. Perhaps if a node in say... a linked list for an aging algorithm corresponded to each VMM node the alternate treatment would become easier. Or perhaps VMM nodes could be given an extra pointer to link to each other address-wise for a page replacement algorithm.

These have been random thoughts for this post.

Why use the highest BIT when you got the lowest BITS free...
$FFF (4096 byte pages) can be used for all kind of flags... addresses have to be page aligned.

Why just use the signs? 1. I've only figured out one flag to store in each integer so far, and 2. It simplifies actually coding using those values (take AbsoluteValue(pNode^.iVirtualPage) or AbsoluteValue(pNode^.iPhysicalPage)). At least, I think an absolute value is easier than a bitmask in the sense of being easier to read and understand.

Wait a minute, though. For a 4096-aligned address (say I make them addresses), wouldn't I have twelve bits free? If so, then I could save a bit of space by sticking the aging counter inside the physical page frame address ALONG with the flag currently in use. I'll check and see how that would convolute/simplify the coding I've managed to do.

And THANK YOU O MIGHTY ADMIN for allowing .pas attachments! The VirtualMemory unit I wrote is attached for anyone who wants a look.

[edit]Anding the values wouldn't do much to make the code look worse. However, I'm wondering if there isn't a nicer algorithm than crossing traversal of a linked list for one thing (broad operations such as aging that are done on most or all pages) with traversal of a binary search tree (finding pages by page number to change some status bit or something). I came up with something earlier, actually. The algorithm is simply a doubly-linked list that keeps pointers to its head, its tail and the exact center node. Nodes are stored in virtual address order, and whenever a search needs to be done the entry node (head,tail,center) closest to the desired node is found and searched from in the apparent direction. For small trees (10+ish nodes) this was actually more efficient than a randomly arranged binary search tree! However, I have awfully bad feelings about how that will work as node numbers go up. Still, I think I'm on a good track, if not THE right one.[/edit]

Not sure how much this info helps you, but here goes....

In NT, a binary tree is used to organize the VADs "virtual address space descriptors" for each process. This is used for system calls that reserve regions of address space, commit storage to them, and change their protection attributes. It's also used during page fault handling to determine if the process has reserved and committed the page on which the fault occurred (if so, the page is brought in, if not, it's an access violation).

AFAIK the VADs aren't used at all for page replacement. NT uses page buffering -- it attempts to keep a bunch of pages free at all times by occasionally "trimming" the working set of each process. It ages a process' pages to determine which ones to steal, then every so often (on the order of seconds) it steals a page (possibly more than one, I don't remember) from a victim process and puts the stolen page(s) on the "standby" list. If a page fault occurs on that page in the near future, it is simply mapped back to the process. Otherwise, it is freed up completely.

I don't think any special data structure is used when keeping track of the age of the pages in a process' working set. I think NT just scans the process' page tables, checking the Accessed bit in each PTE, looking for pages that haven't been accessed and clearing the Accessed bit of the ones that have (unless they're dirty I guess...). I doubt that it would do a complete scan each time -- it probably uses the "clock algorithm" so that it picks up where it left off on the last scan.

Hmmm... It seems like the easy thing to do is to change iPhysicalPage to a pointer to a physical page info structure, and these would be in their own seperate datastructure with seperate algorithm. They would also include a pointer to their virtual page information, such that pPhysical->pVirtual->iVirtualPage could be used to look up a page in the page tables for checking bits and things. However, this could result in a situation where a physical page doesn't have a virtual, or vice versa.