Page 269 - DCAP403_Operating System

Operating System

Notes Each platform that Linux runs on must provide translation macros that allow the kernel to
traverse the page tables for a particular process. This way, the kernel does not need to know the
format of the page table entries or how they are arranged.
This is so successful that Linux uses the same page table manipulation code for the Alpha
processor, which has three levels of page tables, and for Intel x86 processors, which have two
levels of page tables.

13.5.8 Page Allocation and Deallocation

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 which is initialized at boot time. Each mem_map_t describes a

single physical page in the system. Important fields (so far as memory management is concerned)
are:
count: This is a count of the number of users of this page. The count is greater than one when the
page is shared between many processes,
age: This field describes the age of the page and is used to decide if the page is a good candidate

for discarding or swapping,
map_nr: This is the physical page frame number that this mem_map_t describes.

The free_area vector 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 processor 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, the next blocks of 4 pages and so on
upwards in powers of two. The list element is used as a queue head and has pointers to the page
data 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 13.5 shows the free_area structure. Element 0 has one free page (page frame number 0)

and element 2 has 2 free blocks of 4 pages, the first starting at page frame number 4 and the
second at page frame number 56.

Page Allocation

Linux uses the Buddy algorithm to effectively allocate and deallocate blocks of pages. The page
allocation code and attempts to allocate a block of one or more physical pages. Pages are allocated
in blocks which are powers of 2 in size. That means that it can allocate a block 1 page, 2 pages,
4 pages and so on. So long as there are enough free pages in the system to grant this request
(nr_free_pages ?min_free_pages) the allocation code will search the free_area for a block of pages
of the size requested. Each element of the free_area has a map of the allocated and free blocks of
pages for that sized block. For example, element 2 of the array has a memory map that describes
free and allocated blocks each of 4 pages long.

262 LOVELY PROFESSIONAL UNIVERSITY