Page Frame Allocation: Difference between revisions

These are the algorithms that will provide you with a new page frame when you'll need it. The client of this algorithm is usually indifferent to which frame is returned, and especially, a request for n frames needndoesn't need to return contiguous frames (unless you are allocating memory for DMA operations like network packet buffers).

The address of each available physical frame is stored in a [[stack]]-like dynamic structure. Allocating a page is fast (O(1)), freeing a page too but checking the state of a page is not practical, unless additional metadata is stored sorted by physical address.

A buddy for N pages is about twice the size of a bitmap for the same area, but it allows a faster location of collections of pages. FigureThe figure above shows a 4-buddy with free pages/blocks denoted as . and used pages/blocks denoted as #. When a block contains at least one used sub-block, it is itself marked as used and sub-blocks that are part of a larger block are also marked as used (x onin the figure). Say we want to allocate a 12-K region on this buddy, we'll lookuplook up the bitmap of free 16K blocks (which says we have one such starting at page #12 and another starting at page #36). buddy[2]->bit[4] is then set to 'used'. Now we only want 3 pages out of the 4 we got, so the remaining page is returned to the appropriated buddy bitmap (e.g. the single pages map). The resulting buddy is