Figure 325 Memory fragmentation where few reserved pages prevent the allocation of larger contiguous blocks

I have mentioned that memory fragmentation only concerns the kernel, but this is only partially true: Most modern CPUs provide the possibility to work with huge pages whose page size is much bigger than for regular pages. This has benefits for memory-intensive applications. When bigger pages are used, the translation lookaside buffer has to handle fewer entries, and the chance of a TLB cache miss is reduced. Allocating huge pages, however, requires free contiguous areas of physical RAM!

Fragmentation of physical memory has, indeed, belonged to the weaker points of Linux for an unusually long time span. Although many approaches have been suggested, none could satisfy the demanding needs of the numerous workloads that Linux has to face without having too great an impact on others. During the development of kernel 2.6.24, means to prevent fragmentation finally found their way into the kernel. Before I discuss their strategy, one point calls for clarification: Fragmentation is also known from filesystems, and in this area the problem is typically solved by defragmentation tools: They analyze the filesystem and rearrange the allocated blocks such that larger continuous areas arise. This approach would also be possible for RAM, in principle, but is complicated by the fact that many physical pages cannot be moved to an arbitrary location. Therefore, the kernel's approach is anti-fragmentation-. Try to 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 pages have a fixed position in memory and cannot be moved anywhere else. Most allocations of the core kernel fall into this category.

□ Reclaimable pages cannot be moved directly, but they can be deleted and their contents regenerated from some source. Data mapped from files fall into this category, for instance.

Reclaimable pages are periodically freed by the kswapd daemon 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 pages can 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 certain mobility depending 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 prevented. 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, however, 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 I

Continue reading here: Data Structure

Was this article helpful?

0 0