Page management in OS kernels
Page frame management is conceptually very simple; all you really need is a linked list. However, there are two main factors which complicate things:


DMA. DMA is one of the few things that might need a physical buffer larger than a page in size. In addition, there are legacy devices to contend with; on x86, for example, 32-bit devices can only do DMA from physical addresses below the 4G limit. For ISA it's even worse.
Cache colouring, which is an extremely important optimisation.


Most operating systems use surprisingly simple techniques.

Windows, for example, just uses a bunch of linked lists (or at least it did, last time anyone said anything about it). It's hard to say since we can't see the source code, but there are probably N*M linked lists where N is the number of possible states a page can be in (e.g. in-use, free, waiting to be paged out) and M is the number of colours.

Linux famously uses a buddy allocator to manage physical pages, which is only slightly more complicated than a bunch of linked lists when you think about it.

Probably the most sophisticated management scheme that has been documented extensively is that of Solaris. See Bonwick &amp; Adams, Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources, USENIX 2001. There is also an extended discussion in the book Solaris Internals. The Solaris slab allocator goes to a lot of trouble to avoid lock contention, cache thrashing, and the like, and also can tune its implementation for different data types as needed.

What's interesting is that Solaris uses the same memory allocator to handle page frames that it uses to handle kernel objects, by nesting slab allocators inside slab allocators. The paper is definitely worth a read.