There are many demands on the physical pages in the system. For example, when an image is loaded into memory the operating system needs to allocate pages. These will be freed when the image has finished executing and is unloaded. Another use for physical pages is to hold kernel specific data structures such as the page tables themselves. The mechanisms and data structures used for page allocation and deallocation are perhaps the most critical in maintaining the efficiency of the virtual memory subsystem. All of the physical pages in the system are described by the mem_map data structure which is a list of mem_map_t
structures. Each mem_map_t describes a single physical page in the system. Important fields (so far as memory management is concerned) are:
The free_area structure is used by the page allocation code to find and free pages. The whole buffer management scheme is supported by this mechanism and so far as the code is concerned, the size of the page and physical paging mechanisms used by the CPU are irrelevant.
Each element of free_area contains information about blocks of pages. The first element in the array describes single pages, the next blocks of 2 pages and so on upwards in powers of two. The list element is used as a queue head and has pointers to the page structures in the mem_map array. Free blocks of pages are queued here. map is a pointer to a bitmap which keeps track of allocated groups of pages of this size. Bit N of the bitmap is set if the Nth block of pages is free.
Figure shows the free_area structure. Element 0 has one free page (PFN 0) and element 2 has 2 free blocks of 4 pages, the first starting at PFN 4 and the second at PFN 56.