Page 433 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes The size of the page descriptor is 32 bytes, therefore the entire memory map can consume
less than 1% of the physical memory (for a page frame of 4 KB). Since the physical memory is
divided into zones, for each zone Linux maintains a zone descriptor. The zone descriptor contains
information about the memory utilization within each zone, such as number of active or inactive
pages, low and high watermarks to be used by the page replacement algorithm described later
in this chapter, as well as many other fields.
In addition, a zone descriptor contains an array of free areas. The i element in this array,
th
identifies the first page descriptor of the first block of 2i free pages. Since there may be multiple
blocks of 2i free pages, Linux uses the pair of page descriptor pointers in each page element,
to link these together. This information is used in the memory allocation operations supported
in Linux. In Figure 14.15 free area[0], which identifies all free areas of main memory consisting
of only one page frame (since 20 is one), points to page 70, the first one of the three free areas.
The other free blocks of size one can be reached through the links in each.
Figure 14.16: Linux Uses Four-level Page Tables
Page

Page global Page upper Page middle
directory directory directory Page table

Virtual
Global directory Upper directory Middle directory Page Offset
address
Physical memory is used for various purposes. The kernel itself is fully hardwired; no part
of it is ever paged out. The rest of memory is available for user pages, the paging cache, and
other purposes. The page cache holds pages containing file blocks that have recently been read
or have been read in advance in expectation of being used in the near future, or pages of file
blocks which need to be written to disk, such as those which have been created from user mode
processes which have been swapped out to disk. It is dynamic in size and competes for the same
pool of pages as the user processes. The paging cache is not really a separate cache, but simply
the set of user pages that are no longer needed and are waiting around to be paged out. If a
page in the paging cache is reused before it is evicted from memory, it can be reclaimed quickly.
In addition, Linux supports dynamically loaded modules, generally device drivers. These can
be of arbitrary size and each one must be allocated a contiguous piece of kernel memory. As a
consequence of these requirements, Linux manages physical memory in such a way that it can
acquire an arbitrary-sized piece of memory at will. The algorithm it uses is known as the buddy
algorithm and is described below.
14.4.5 Memory Allocation Mechanisms
Linux supports several mechanisms for memory allocation. The main mechanism for allocating
new page frames of physical memory is the page allocator, which operates using the so called
buddy algorithm. The basic idea for managing a chunk of memory is as follows. Initially memory
consists of a single contiguous piece, 64 pages in the simple example of Figure 14.17: When a
request for memory comes in, it is first rounded up to a power of two, say 8 pages. The full
memory chunk is then divided in half, as shown in (b). Since each of these pieces is still too
large, the lower piece is divided in half again (c) and again (d). Now we have a chunk of the
correct size, so it is allocated to the caller, as shown shaded in (d).

426 LOVELY PROFESSIONAL UNIVERSITY