Fragmentation
wikipedia Fragmentation (computing)
Basic principle
NOTE: 理解这一段的核心是理解"chunk"这个词，它表示的是连续的内存空间
When a computer program requests blocks of memory from the computer system, the blocks are allocated in chunks. When the computer program is finished with a chunk, it can free it back to the system, making it available to later be allocated again to another or the same program. The size and the amount of time a chunk is held by a program varies. During its lifespan, a computer program can request and free many chunks of memory.
When a program is started, the free memory areas are long and contiguous. Over time and with use, the long contiguous regions become fragmented into smaller and smaller contiguous areas. Eventually, it may become impossible for the program to obtain large contiguous chunks of memory.
Types
Internal fragmentation
NOTE: 于此相关的是alignment，参见工程hardware的
CPU\Memory-access\Memory-alignment章节。显然这种fragmentation是由computer的internal机制所决定的，可以说是它天生的
Due to the rules governing memory allocation, more computer memory is sometimes allocated than is needed. For example, memory can only be provided to programs in chunks (multiple of 4), and as a result if a program requests perhaps 29 bytes, it will actually get a chunk of 32 bytes. When this happens, the excess memory goes to waste. In this scenario, the unusable memory is contained within an allocated region. This arrangement, termed fixed partitions, suffers from inefficient memory use - any process, no matter how small, occupies an entire partition. This waste is called internal fragmentation.[1][2]
Unlike other types of fragmentation, internal fragmentation is difficult to reclaim; usually the best way to remove it is with a design change. For example, in dynamic memory allocation, memory pools drastically cut internal fragmentation by spreading the space overhead over a larger number of objects.
External fragmentation
External fragmentation arises when free memory is separated into small blocks and is interspersed by allocated memory. It is a weakness of certain storage allocation algorithms, when they fail to order memory used by programs efficiently. The result is that, although free storage is available, it is effectively unusable because it is divided into pieces that are too small individually to satisfy the demands of the application. The term "external" refers to the fact that the unusable storage is outside the allocated regions.
Data fragmentation
NOTE: TODO
stackoverflow Memory fragmentation
As per ISO/IEC 9899:201x -> 7.22.3
The order and contiguity of storage allocated by successive calls to the aligned_alloc, calloc, malloc, and realloc functions is unspecified.
A good memory manager will be able to tackle the issue to an extent. However, there are other aspects like data alignment [1] which causes internal fragmentation.
What you could do if you rely on inbuilt memory management?
-
Use a profiler - say valgrind - with memory check option to find the memory which is not freed after use. Example:
valgrind --leak-check=yes myprog arg1 arg2 -
Follow good practices. Example - In C++, if you intend others to inherit from your polymorphic class, you may declare its destructor virtual.
-
Use smart pointers.
Notes:
- Internal fragmentation.
- If you were to use your own memory management system, you may consider Boehm-Demers-Weiser garbage collector.
- Valgrind Instrumentation Framework.
- Memory not freed after use will contribute to fragmentation.
Example
1) wikipedia Memory-mapped file:
For small files, memory-mapped files can result in a waste of slack space[7] as memory maps are always aligned to the page size, which is mostly 4 KiB. Therefore, a 5 KiB file will allocate 8 KiB and thus 3 KiB are wasted.