Q: How does Linux reduce physical memory fragmentation in real-time? The Linux memory allocator works by mapping pages from physical memory to virtual memory. It can either map a contiguous area or sparse chunks from physical memory, to a contiguous area in virtual memory.
Using the buddy algorithm, physical memory can be arranged in contiguous sets of pages (let's call them buckets). The number of pages contained in one bucket is always a power of 2, as this makes it easy to group smaller buckets into one big bucket (e.g. 1 page makes up an order-0 bucket, 2 order-0 buckets make up an order-1 bucket, 2 order-1 buckets make up an order-2 bucket etc.)
Over time, physical memory gets fragmented, such that it is no longer possible to allocate a bucket of a certain size, and thus the kernel is forced to allocate smaller buckets that are scattered across physical memory.
The question is: Does the Linux kernel rearrange those buckets in real time in order to increase the probability that a larger bucket is available? If so, how does it achieve this?

A: You are describing here the memory allocation that is used in the Linux kernel,
not for process RAM allocation which is rather by pages.
This algorithm deals with small amounts of memory, up to the size of a page.
Only in modern kernels is it now possible for requests to be larger than one page.
As far as I know the kernel does not rearrange memory, meaning no garbage collection,
as some of the allocated objects may not be movable when used by critical
processes.
When the memory is too fragmented to allocate the requested amount,
the kernel can either:


*

*Fail the request with the condition of no memory available.

*Schedule the request for later execution, in the hope that the fragmentation
will be taken care of by the buddy system.
This is only possible for non-critical sections of the kernel.

*Critical subsystems may be allocated a chunk of memory from the beginning,
to manage its parceling themselves.

*Some kernel memory may be swappable and will be written out if requested by
higher-priority routines.


The fundamental rule when writing kernel software is not to commit to
executing without having guaranteed the needed resources in order to complete.
A well-written kernel routine will allocate first all resources, including
memory, before starting. This will avoid backtracking and the need to save the
old state, which will be required if the error happens after the routine
already did some work, so now before returning a fail condition it has to
undo everything it did.
For more information see the Linux Journal article of
Memory Allocation.
