Linux Kernel Architecture

Chapter3:MemoryManagement

cannot be moved to an arbitrary location. Therefore, the kernel’s approach isanti-fragmentation:Tryto
prevent fragmentation as well as possible from the very beginning.

How does anti-fragmentation work? To understand the approach, we must be aware that the kernel
distinguishes three different types of reserved pages:

❑ Non-movable pageshave a fixed position in memory and cannot be moved anywhere else. Most

allocations of the core kernel fall into this category.

❑ Reclaimable pagescannot be moved directly, but they can be deleted and their contents regener-

ated from some source. Data mapped from files fall into this category, for instance.

Reclaimable pages are periodically freed by thekswapddaemon depending on how often

they are accessed. This is a complicated process that merits a detailed discussion of its own:

Chapter 18 that describes page reclaim in detail. In the meanwhile, it suffices to know that the

kernel will take care of removing reclaimable pages when they start to use up too much RAM.

It is also possible to initiate page reclaim when there is an acute shortage of memory, that is,

when an allocation has failed. You will see further below when the kernel deems it necessary to

do so.

❑ Movable pagescan be moved around as desired. Pages that belong to userspace applications fall

into this category. They are mapped via page tables. If they are copied into a new location, the

page table entries can be updated accordingly, and the application won’t notice anything.

A page has a certainmobilitydepending into which of the three categories it falls. The anti-fragmentation
technique used by the kernel is based on the idea of grouping pages with identical mobility together.
Why does this approach help to reduce fragmentation? Recall from Figure 3-25 that a page that cannot
be moved somewhere else can prevent continuous allocations in an otherwise nearly completely empty
RAM area. By distributing pages onto different lists depending on their mobility, this situation is pre-
vented. For instance, a non-movable page cannot be located in the middle of a block of movable pages
and effectively prevent any larger part of the block from being used.

Imagine that most of the free pages in Figure 3-25 belong to the reclaimable category, while the reserved
pages are non-movable. If the pages had been collected on two different lists, the situation might, how-
ever, look as shown in Figure 3-26. It is still hard to find a large continuous free space for non-movable
pages, but much easier for reclaimable pages.

Reclaimable

pages

Un-movable pages

Figure 3-26: Memory fragmentation is reduced by

grouping pages together depending on their

mobility.

Note, however, that the memory is not partitioned into different mobility regions from the very
beginning. They will be populated at runtime. A second approach of the kerneldoespartition the
memory into regions for movable and non-movable allocations, and I will discuss how this works below.
Such a partitioning, however, is not essential for the approach described here.